1541. 千层塔 III

在最终极之渊,有一座无限高的塔,它的最低层是第 1 层。

每一个楼层都设置有只允许下行的特级遗物电梯。具体而言,第 k 层设置有一座直达第 k-1 层的电梯(若 k>1)和一座直达第 k-2 层的电梯(若 k>2)。特别地,如果 k \bmod 3 = 1,还额外设置有一座直达第 k-3 层的电梯(若 k>3),此处 \bmod 是取余运算。

假设你一开始位于第 a 层,想要前往第 b 层,你只允许乘坐前面所述的下行电梯,求前往的方案数。

由于在给定数据范围下,答案可能远大于 2^{64},你只需要输出答案对 10^9+7 取余的结果。

以下的取余性质可能会对帮助你避免潜在的溢出问题有帮助,对于正整数 x,y,p,有:

(x+y) \bmod p = ((x \bmod p) + (y \bmod p)) \bmod p \\ (x \times y) \bmod p = ((x \bmod p) \times (y \bmod p)) \bmod p

评测环境一秒可以做约 10^8 次运算,请充分优化你的代码避免运行超时。

输入

输入包含多组测试用例。

第一行包含一个整数 t \ (1 \leq t \leq 10^5),表示你需要处理 t 组测试用例。

接下来 t 行每行一组测试用例,各包含两个用空格间隔的整数 a,b \ (1 \leq b < a \leq 10^{18}, a-b \leq 10^{18}),含义如题目描述所示。

输出

对于每组测试用例,在单独的一行输出一个整数,表示答案对 10^9+7 取余的结果

样例

标准输入 复制文本
3
4 1
5 2
580123456712345678 123456712345678580
标准输出 复制文本
4
3
644236091

提示

对于测试用例 1,四种方案如下:

  • 4 \to 3 \to 2 \to 1
  • 4 \to 3 \to 1
  • 4 \to 2 \to 1
  • 4 \to 1

对于测试用例 2,三种方案如下:

  • 5 \to 4 \to 3 \to 2
  • 5 \to 4 \to 2
  • 5 \to 3 \to 2

对于测试用例 3,记得输出的是答案对 10^9+7 取余的结果。

来源

lr580

登录以提交代码。
单点时限 4 秒
内存限制 256 MB
提交 10
通过 7