何老板在报纸上发现了一个有趣的填数字游戏.报纸上有一个n*n的方格矩阵,需要往里面填入数字,使得这些数字能构成一个高度为n的直角三角形.填涂的规则如下:
1.第i行填i个数字,其中第1个和第i个数字都是1;
坐标为xy的格子里填入的数字a[x][y]跟y的奇偶性有关:
如下图所示,何老板饶有兴趣的填了几行后,发现太难算了,他拜托你把剩下的部分填完.
为了检查你是否认真完成了这个游戏,何老板会向你提出k个问题,每个问题都是x和y两个整数,你需要快速回答出坐标为(xy)的格子里填入的数字.
k行,每行一个整数,表示对应问题的答案,结果可能很大,mod 49999再输出.
对于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