QQQQQQQ现在有一个数字三角形。这个三角形一共有 n 层，它的特征是其中第i层共有i个数，且第1个数和第i个数均为i。其余的数中，第 j个数是上一层中第 j-1个数和第 j个数的和。QQQQQQQ现在想知道这个三角形第 x 层到第 y 层所有数的和,一共有 m个询问。 （良心签到题,手速快抢一血）
单组输入。
第一行两个正整数 n,m表示这个三角形的层数和询问个数。接下来 m 行，每行两个正整数 x,y，表示一次询问。
其中1<=n<=1e5，1<=m<=1e5 , 1<=x<=y<=n
输出共m行，每行一个整数，表示一组询问的答案，对109取模。
5 3 1 2 1 5 3 5
5 83 78