The output of a function

1.1

16 votes
Combinatorics, Math, Number Theory
Problem

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 nm. For each test case, print a single line containing answer (nm1)%1000000007, that is, the modulo inverse.

Constraints

1t10

1p, q10000

2r5

Sample Input
1
2 3 2
Sample Output
953125007
Time Limit: 4
Memory Limit: 256
Source Limit:
Explanation

.After putting the values in the function we get 63/448 as output and taking modulo inverse we get 265625002

Editor Image

?