Description

Given $n, m, k$, compute

and output the result modulo $10^9 + 7$.

Input Format

There are multiple test cases in a single test file.

The first line contains two integers, the number of test cases $T$ and the given $k$.

The next $T$ lines each contain two integers, $n$ and $m$, for one test case.

Output Format

For each test case, output one line with a single integer representing the answer.

1 2
3 3

20

Hint

Constraints

For all test points, it is guaranteed that $1 \leq T \leq 2 \times 10^3$, $1 \leq n, m, k \leq 5 \times 10^6$.

Translated by ChatGPT 5