tokitsukaze and Unlimited Array
题号：NC21194
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

I am the bone of my number.
Variable is my structure, and function is my member.
I have created over a thousand array.
Unknown to infinity.
Nor known to endless.
Have withstood pain to create many number.
Yet, those hands will never hold anything.
So as I pray, Unlimited Array Works.

tokitsukaze有一个n次多项式函数F(x)。
她按照如下规则定义了一个二维无限数组。

a[i][j] = <br />\begin{cases} <br />F(j) & \text{while } i = 0 \\<br />a[i-1][j] & \text{while } i \neq 0 \text{ and } j = 0 \\<br />a[i-1][j-1]-a[i-1][j-1] & \text{others}<br />\end{cases}
tokitsukaze发现，由任意一个n次多项式函数F(x)确定出的这个无限数组，无穷级数 \sum_{i=0}^{\infty} a[n + 1][i]  总是收敛的。
求无穷级数 \sum_{i=0}^{\infty} a[n + 1][i]  的和，为了避免这个数过于庞大，你只用输出级数和mod 1000000007后的结果即可。

输入描述:

第一行是两个整数n(0≤n≤10^9)表示多项式函数F(x)的最高次数。m(1≤m≤100)表示多项式函数的项数。
接下来一行共2*m个非负整数，这2*m个非负整数分为m组，每组两个非负整数。
对于每一组：第一个整数x(1≤x≤10^9)表示该项的系数，第二个整数y(0≤y≤n)代表该项的次数。
输入数据保证F(x)的最高次项系数不为0且次数为n，保证次数唯一，不保证输入多项式的幂次是递减的。
例如当n=3,m=3时，则输入6个非负整数，如：4 3 2 2 5 0，表示多项式函数F(x)=4x^3+2x^2+5。

输出描述:

对于每一组案例,输出一行一个非负整数，表示级数和mod 1000000007后的结果。
示例1

输入

复制 
3 3
4 3 2 2 5 0

输出

复制 
24

说明

F(x)=4x^3+2x^2+5
a[0]=5,11,45,131,293,555,941,1475,2181,3083,4205,5571,7205,9131,11373……(这里仅给出一部分)
a[1]=5,6,34,86,162,262,386,534,706,902,1122,1366,1634,1926,2242,2582……(这里仅给出一部分)
a[2]=5,1,28,52,76,100,124,148,172,196,220,244,268,292,316,340,364,388……(这里仅给出一部分)
a[3]=5,-4,27,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24……(这里仅给出一部分)
a[4]=5,-9,31,-3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0……(这里仅给出一部分，并且后面都是0)
所以\sum_{i=0}^{\infty}a[n+1][i]=5-9+31-3=24