Given an array of length , it undergoes a transformation every second.

In each transformation, the number in the first position will be merged with the number in the second position, the number in the third position will be merged with the number in the fourth position, and so on. This will continue until there are only two numbers left in the array.

When merging two numbers, their sum will be calculated. For example, the array [1, 2, 3, 4, 5] will become [3, 7, 5] after the first second (the first two numbers are merged, the third and fourth numbers are merged, and since there is no sixth number, the fifth number remains unchanged). It will become [10, 5] after the second second, at which point only two numbers remain, and the transformation ends. Christina wants to know the sum of the squares of the last two numbers. For example, in the above array, the square sum is .

Since the length of this array can be very large, Christina used a new method when giving you the data. Christina will give you pieces of information. Each piece of information contains two positive integers , indicating that there is a segment of length in the array, and all the numbers in the segment are . Since the answer may be very large, please take the result modulo .

The first line contains two positive integers  and  , as described in the problem statement. 

The next  lines give two positive integers  and   respectively, indicating that there are  numbers of  in the array. This problem ensures that the sum of all  values is equal to .

Output the sum of the squares of the last two numbers after all transformations have been made.

5 5
1 1
1 2
1 3
1 4
1 5

125

7 2
3 1
4 2

61