【筆試題目】搜狗2020秋招測試卷

# -*- coding:utf-8 -*-

import sys

if __name__ == "__main__":
    # 讀取第一行的n
    input_1= map(int,raw_input().split())

    #n = int(sys.stdin.readline().strip())
    n =input_1[1]
    #ans = 0
    list1=[]
    for i in range(input_1[0]):
        list1.append(0)


    index=1
    for i in range(n):
        # 讀取每一行
        line = sys.stdin.readline().strip()
        # 把每一行的數字分隔後轉化成int清單
        values = map(int, line.split())
        for i in range(values[0],values[1]+1):
            list1[i]=index
        index+=1
        #print list1
    index2=0
    mima=0
    #print list1
    for j in list1:
        mima+=j*index2
        #print j*index2
        index2+=1
    print mima % 100000009