果冻看到白茶满载而归，于是也跃跃欲试。然而，这一次的挑战难度更高，率先到达塔底者将获得一次穿越到任意异世界的机会。果冻毫不犹豫地前往挑战。

《白茶与千层之塔》和《果冻与千层之塔》仅存在少量差别，你可以使用《果冻与千层之塔》的代码通过《白茶与千层之塔》。

在来无回之都，有一座无限高的塔，它的最低层是第 $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 5 \times 10^4)$，表示你需要处理 $t$ 组测试用例。

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

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

对于测试用例 $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$ 取余的结果。