Problem Description

Calculate

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

where $f(x,B,d)$ means the number of times that digit $d$ appears in the base-$B$ form of $x$ (ignoring leading zeros).

In this problem, we consider that $0^0=0$.

Input

The first line contains one integer $T$ ($1\le T\le 10^4)$, denoting the number of test cases.

For each test case, the only line contains five integers $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})$, as the statement shows.

Output

For each test case, output an integer indicating the answer modulo $10^9+7$ in a single line.

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

6
19
1049

Hint

For the first case in the sample, the answer is

$$
\begin{aligned}
&\sum_{i=1}^5 f^2(i,2,0)\\\\
&=0^2+1^2+0^2+2^2+1^2\nonumber\\\\
&=6\nonumber
\end{aligned}
$$