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$.
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$)
For each testcase, if such partition does not exist, please output $-1$. Otherwise output the maximum product mudulo $10^9 + 7$.