TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4175
  • 题目
  • P4175填数字
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    问题描述

    何老板在报纸上发现了一个有趣的填数字游戏。报纸上有一个n*n的方格矩阵,需要往里面填入数字,使得这些数字能构成一个高度为n的直角三角形。填涂的规则如下:
        1.第i行填i个数字,其中第1个和第i个数字都是1;

    1. 坐标为x,y的格子里填入的数字a[x][y]跟y的奇偶性有关:

    若y是奇数a[x][y]=a[x-1][y-1]+a[x-1][y]

    若y是偶数a[x][y]=a[x-1][y-1]-a[x-1][y]

    如下图所示,何老板饶有兴趣的填了几行后,发现太难算了,他拜托你把剩下的部分填完。

    1

     

     

     

     

     

     

    1

    1

     

     

     

     

     

    1

    0

    1

     

     

     

     

    1

    1

    1

    1

     

     

     

    1

    0

    2

    0

    1

     

     

    1

    1

    2

    2

    1

    1

     

    ......

     

     

    为了检查你是否认真完成了这个游戏,何老板会向你提出k个问题,每个问题都是x和y两个整数,你需要快速回答出坐标为(x,y)的格子里填入的数字。

    输入格式

    一行,两个整数n和k

    接下来k行,每行两个整数x,y表示一次询问

    输出格式

    k行,每行一个整数,表示对应问题的答案,结果可能很大,mod 100000007再输出。

    样例输入

    14 3
    7 6
    10 5
    14 8

    样例输出

    0
    6
    20

    提示

    对于30%的数据:1<=n<=100          1<=k<=10    1<=x<=n   1<=y<=x

    对于100%的数据:1<=n<=100000000    1<=k<=10    1<=x<=n   1<=y<=x