J. Carryless Addition Pairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Joshi is trying to add numbers in non-traditional base systems. However, he is terrible at arithmetic, so he can only compute $$$x+y$$$ in base $$$p$$$ if no carries are required. Formally, if $$$x = \sum a_i k^i$$$ and $$$y = \sum b_i p^i$$$ for integer sequences $$$a$$$ and $$$b$$$ satisfying $$$0 \leq a_i, b_i \lt p$$$ for all $$$i$$$, then Joshi can compute $$$x+y$$$ if and only if $$$a_i + b_i \lt p$$$ for all $$$i$$$. For example, joshi can compute 67+33 in base 8, but not in base 10. You are given 4 integers: $$$p, a, b,$$$ and $$$k$$$. Compute the number of ordered pairs $$$(x, y)$$$ such that $$$0 \leq x, y \lt p^k$$$ and Joshi can compute $$$x+y$$$ in both base $$$p^a$$$ and base $$$p^b$$$. Give your answer modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases, $$$t$$$ $$$(1 \leq t \lt 10^5)$$$. The description of the test cases follows Every testcase contains 4 integers: $$$p, a, b,$$$ and $$$k$$$ ($$$1 \lt p \lt 10^9$$$, $$$1 \leq a \leq b \lt 10^5, 0 \lt = k \lt 10^{18}$$$) It is guaranteed that the sum of $$$a+b$$$ across all testcases doesn't exceed $$$2 \cdot 10^5$$$

—

Tests are numbered from $$$1-20$$$ and each test is worth $$$5$$$ points.

Tests $$$1-3$$$ satisfy $$$r \lt 2 \cdot 10^5$$$.

Tests $$$4-7$$$ satisfy $$$a = b$$$.

Tests $$$8-20$$$ satisfy no additional constraints.

Output

Print the number of ordered pairs $$$(x, y)$$$ such that $$$0 \leq x, y \lt p^r$$$ and $$$(x, y)$$$ is both $$$p^a$$$ good and $$$p^b$$$ good, given modulo $$$10^9+7$$$

Example
Input
7
2 2 3 0
2 2 3 1
2 2 3 2
2 2 3 3
5 2 2 4
3 3 4 9
7 11 13 1000
Output
1
4
10
30
105625
27556200
467115580