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\)