Sum of Powers Version I

Input

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

Each of the following $T$ lines contains two integers $N$ and $K$ (1 \leq N \leq 10^9, 1 \leq K \leq 4).

Output

For each test case, output the value of the expression modulo $1000000007$.

Examples