K. Homsi was sleeping
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Homsi had a strange dream involving two positive integers $$$k$$$ and $$$b$$$.

In his dream, he saw a strictly increasing infinite array $$$a$$$ such that for every non-negative integer $$$x$$$, there exist exactly one ordered tuple of indices $$$i_1, i_2, \ldots, i_k$$$ (where the indices are not necessarily distinct and are not required to be in non-decreasing order) satisfying

$$$$$$x = a_{i_1} + b \cdot a_{i_2} + b^2 \cdot a_{i_3} + \cdots + b^{k-1} \cdot a_{i_k}$$$$$$

In other words, every non-negative integer has a unique representation of the above form.

After waking up, Homsi told his friends about the dream. Hussain doubted that such an array could even exist, so he challenged Homsi with the following task.

For each test case, given the integers $$$b$$$, $$$k$$$, $$$l$$$, and $$$r$$$, determine the value of $$$a_l + a_{l+1} + \cdots + a_r$$$ modulo $$$10^9+7$$$.

If no array satisfying the required property exists, output -1.

Input

The first line contains a single integer $$$t$$$ — the number of test cases ($$$1 \le t \le 10^5$$$).

Each of the next $$$t$$$ lines contains three integers $$$b$$$, $$$k$$$, $$$l$$$, and $$$r$$$ ($$$2 \le b, k \le 10^{18}, 1 \le l \le r \le 10^{18}$$$).

Output

For each test case, print the sum $$$a_l + a_{l+1} + \cdots + a_r \bmod (10^9+7)$$$ if such an array exists, -1 otherwise.

Example
Input
3
2 2 1 3
2 3 1 1
3 4 5 6
Output
5
0
165