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$