# Yet Another Mex Problem Codechef Solution | APRIL CHALLENGE Share:

Yet Another Mex Problem Codechef Solution

Nayra doesn’t like stories of people receiving random arrays as birthday presents, but this time she received random arrays as presents for her own birthday! After struggling for a day trying to figure out what to do with the array, she asked Aryan for help. He gave her the following problem.

Given 33 integers N,P,N,P, and MM.

• Let f(A)f(A) be the MEX of the array AA.
• Let g(A)=(f(A))Pg(A)=(f(A))P for the array AA .

There are (M+1)N(M+1)N distinct arrays A=[A1,A2,…,AN]A=[A1,A2,…,AN] such that (0≤Ai≤M)(0≤Ai≤M) ∀∀ (1≤i≤N)(1≤i≤N).

Calculate the sum of g(A)g(A) over all such (M+1)N(M+1)N arrays. Since the answer can be huge, print it modulo 754974721754974721.

### Input Format

• First line will contain TT, the number of test cases. Then the test cases follow.
• Each test case contains a single line of input, three integers N,P,N,P, and MM.

### Output Format

For each test case, output a single line containing the value of the given sum modulo 754974721754974721.

### Constraints

• 1≤T≤1041≤T≤104
• 1≤M≤1051≤M≤105
• 1≤P≤1091≤P≤109
• 1≤N≤1091≤N≤109
• Sum of MM over all test cases does not exceed 106106.

### Sample Input 1

``````6
1 1 1
2 2 1
3 1 2
2 2 3
2 2 2
2 10000000 1
``````

### Sample Output 1

``````1
9
37
13
11
432888326
``````

### Explanation

Test case 11: There are (1+1)1=2(1+1)1=2 distinct arrays. The arrays are :  and .

• f()=f()= MEX of =1=1. Also, g()=(f())1=11=1g()=(f())1=11=1.
• f()=f()= MEX of =0=0. Also, g()=(f())1=01=0g()=(f())1=01=0.

Sum of g(A)g(A) is 1+0=11+0=1.

Test case 22: There are (1+1)2=4(1+1)2=4 distinct arrays. The arrays are : [0,0],[0,1],[1,0][0,0],[0,1],[1,0] and [1,1][1,1].

• f([0,0])=f([0,0])= MEX of [0,0]=1[0,0]=1. Also, g([0,0])=(f([0,0]))2=12=1g([0,0])=(f([0,0]))2=12=1.
• f([0,1])=f([0,1])= MEX of [0,1]=2[0,1]=2. Also, g([0,1])=(f([0,1]))2=22=4g([0,1])=(f([0,1]))2=22=4.
• f([1,0])=f([1,0])= MEX of [1,0]=2[1,0]=2. Also, g([1,0])=(f([1,0]))2=22=4g([1,0])=(f([1,0]))2=22=4.
• f([1,1])=f([1,1])= MEX of [1,1]=0[1,1]=0. Also, g([1,1])=(f([1,1]))2=02=0g([1,1])=(f([1,1]))2=02=0.

Sum of g(A)g(A) is 1+4+4+0=91+4+4+0=9.