小汪作为一个有数学天分的程序猿，设计了一套密码生成器来搞定自己的密码问题。 密码生成器由 N 个槽位组成，槽位的下标为 0~N-1 ，每个槽位存储一个数。起初每个槽位都是 0 。 密码生成器会进行 M 轮计算，每轮计算，小汪会输入两个数 L , R (L M轮计算完成后，密码生成器会根据槽位的最终值生成一条密码，密码的生成规则为： （0*a[0] + 1*a[1] + 2*a[2] + ... + (N-1)*a[N-1]) mod 100000009 其中a[i]表示第i个槽位的最终值。 请帮助小汪把他的密码生成器实现为代码。 数据范围： 对于前30%的测试数据，保证 N,M
输入描述:
第一行为两个整数N,M,表示槽位个数和计算轮数。接下来M行，每行两个整数Li,Ri，表示第i轮计算的输入。
输出描述:
输出一行，一个整数A,表示小汪的开机密码。
示例1
说明
对于输入样例，密码生成过程如下：
初始： 0 0 0 0 0
第1轮：0 0 1 1 0
第2轮：0 2 2 1 0
第3轮：0 3 2 1 0
密码生成器最终生成 0 3 2 1 0，则密码为(0*0 + 3*1 + 2*2 + 1*3 + 0*4) mod 100000009 = 10
备注:
mod 表示取余操作，a mod b表示a,b相除得到的余数对于前30%的测试数据，保证 N,M对于前50%的测试数据，保证 N,M对于100%的测试数据，保证 N=1.5*10^7,M=200000
加载中...