You are given the following pseudocode that determines the value of a function \(f(p,q,r)\):

def f(p,q,r):
     ans=0
     for(int i=0;i<=p;i++) {
          temp = 0
           for(int j=1;j<=q;j++) {
                  ta = pow(r,i);              // where pow() is the power function 
                  tb = (ta-1)/ta
                  temp + = pow(tb,j);
              }
           temp2 = fact(p)/(fact(p-i)*fact(i)) // where fact() is the factorial function
           if(i&1) ans-=temp*temp2;
           else ans+=temp*temp2;
         }
     return ans

Your task is to determine the value of function \(f(p,q,r)\).

Input format

The first line contains \(t\) denoting the number of test cases.
Next \(t\) lines contain three space-separated integers \(p\), \(q\), and \(r\).

Output format

\(f(p,q,r) \) can be represented as \(n \over m\). For each test case, print a single line containing answer \((n*m^{-1})\%1000000007 \), that is, the modulo inverse.

Constraints

\(1 \le t \le 10 \)

\(1\le p,\ q\le10000\)

\(2 \le r \le 5\)