计算

$$\sum_{i=l}^{r} f^k(i, B, d)$$

其中 $f(x, B, d)$ 表示数字 $d$ 在 $x$ 的 $B$ 进制表示中出现的次数（忽略前导零）。 在本题中，我们规定 $0^0 = 0$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 对于每个测试用例，唯一的一行包含五个整数 $k, B, d, l, r$ ($0 \le k \le 10^9, 2 \le B \le 10^9, 0 \le d < B, 1 \le l \le r \le 10^{18}$)，如题目所示。

输出格式

对于每个测试用例，输出一行，表示答案对 $10^9 + 7$ 取模后的结果。

样例

样例输入 1

3
2 2 0 1 5
1 4 3 11 45
10 14 11 19 198

样例输出 1

6
19
1049

说明

对于样例中的第一个测试用例，答案为

$$\sum_{i=1}^{5} f^2(i, 2, 0)$$ $$= 0^2 + 1^2 + 0^2 + 2^2 + 1^2$$ $$= 6$$