3423: JX 的数列

拾扒兢课室里， 老刘刚讲完数列。

老刘看到打盹的 JX 很生气， 立即问他： “ 你来说说什么是 Fibonacci 数列？ ”

JX 打着哈欠说： “ F[1]=1， F[2]=1， F[n]=F[n-1]+F[n-2]（ n>=3） 。 满足这个递推关系的数
列叫 Fibonacci 数列。 ”

老刘有点尴尬， 没想到 JX 居然不听课也会！

还没完， JX 对老刘说： “ 你这个问题不行， 我来问你一个问题： 有这么个数列 G， 其中
G[1]=F[1]， G[2]=F[2]， ……， G[k]=F[k]， G[n]=G[n-k] xor G[n-k+1] xor G[n-k+2] xor …… xor G[n-1]
（ n>k） 。 这里的 F[i]表示 Fibonacci 数列的第 i 项模 10^9+7。

“我现在给你两个数 L 和 R， 你告诉我数列 G 的第 L 项到第 R 项的异或和， 即 G[L] xor
G[L+1] xor G[L+2] xor …… xor G[R]。

“ 我会问你很多次， 你必须每一次都答对。 ”

老刘非常尴尬， 只得求助于你。

第一行两个正整数 k 和 Q。

接下来 Q 行， 每行两个正整数 L 和 R， 表示询问的区间。

输出共 Q 行， 每行一个整数， 表示答案。

4 4
1 4
2 6
3 9
5 10

1 
0 
1 
1