sacul

Problem Description

Patrick Star found a kind of magical matrixs, he named them $HMBB$ !!! We use $p$ to express the $c$-th prime number. The size of $HMBB_i$ is $p^i * p^i$ ! What is more surprising is that :

1. For any $n$, the element on the i-th row j-th column $HMBB_n[i][j]$ = $(C(i, j)\ mod\ p) > 0)$ ? $1$ : $0$.
2. Where $C(i, j)$ is count of method to choose $j$ balls (unordered) from $i$ balls which are pairwise distinct.
3. Note that rows and columns both count from zero. Patrick Star defined $F[n][k]$ the sum of all elements of $(HMBB_n)^k$, $F[n][k] = \sum_{i = 0}^{p^n-1}\sum_{j=0}^{p^n-1}HMBB_n^k[i][j]$ Now Patrick wants to know $(\sum_{i=1}^n\sum_{j=1}^kF[i][j])\ mod\ (10^9 + 7)$ !

Input

The first line contain a integer $T$ (no morn than 10), the following is $T$ test case, for each test case : Each line contains contains three integer c, n, k ($0 < n \le 10^9$, $0 < c, k \le 10^5$). Separated by an white space.

Output

For each test case output one line denotes the answer that Patrick Star wants to know.

Sample Input

1

1 1 1

Sample Output

3

Source

2018 Multi-University Training Contest 6