DZY loves partitioning numbers. He wants to know whether it is possible to partition $n$ into the sum of exactly $k$ distinct positive integers.
After some thinking he finds this problem is Too Simple. So he decides to maximize the product of these $k$ numbers. Can you help him?
The answer may be large. Please output it modulo $10^9+7$.
Input
First line contains $t$ denoting the number of testcases.
$t$ testcases follow. Each testcase contains two positive integers $n,k$ in a line.
($1\le t\le 50, 2\le n,k \le 10^9$)
Output
For each testcase, if such partition does not exist, please output $-1$. Otherwise output the maximum product mudulo $10^9 + 7$.
Sample Input
4
3 4
3 2
9 3
666666 2
Sample Output
-1
2
24
110888111
Hint
In 1st testcase, there is no valid partition.
In 2nd testcase, the partition is $3=1+2$. Answer is $1\times 2 = 2$.
In 3rd testcase, the partition is $9=2+3+4$. Answer is $2\times 3 \times 4 = 24$. Note that $9=3+3+3$ is not a valid partition, because it has repetition.
In 4th testcase, the partition is $666666=333332+333334$. Answer is $333332\times 333334= 111110888888$. Remember to output it mudulo $10^9 + 7$, which is $110888111$.
