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
Output format
f(p,q,r) can be represented as nm. For each test case, print a single line containing answer (n∗m−1)%1000000007, that is, the modulo inverse.
Constraints
1≤t≤10
1≤p, q≤10000
2≤r≤5
.After putting the values in the function we get 63/448 as output and taking modulo inverse we get 265625002