Background

In the last five minutes before collecting the papers, pg found that there was still a major problem on the back side of the paper.

Problem Description

Compute

Since the answer may be too large, output the value of the answer modulo $10^9+7$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain $3$ integers: $n, m, p$.

Output Format

Output $T$ lines. Each line contains one integer, the answer.

2
10 12 11
30 20 25

25302
573830

Hint

For the first $10\%$ of the testdata, $T = 5$, and $40 \le n, m, p \le 100$.

For another $20\%$ of the testdata, $T = 50$, and $100 \le n, m, p \le 5 \times 10^4$.

For another $20\%$ of the testdata, $T = 20$, and $4 \times 10^6 \le n, m, p \le 5 \times 10^6$.

For the remaining $50\%$ of the testdata, $T = 10^3$, and $10^7 \le n, m, p \le 2 \times 10^7$.

Translated by ChatGPT 5