Yet Another Mex Problem ~ Multiplex Coder

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 $3$

integers

N, P,

and

M

Let $f (A)$

be the MEX of the array

A

Let

g (A) = (f (A))^{P}

for the array

A

There are $(M + 1)^{N}$

distinct arrays

A = [A_{1}, A_{2}, \dots, A_{N}]

such that

(0 \leq A_{i} \leq M)

\forall

(1 \leq i \leq N)

Calculate the sum of $g (A)$

over all such

(M + 1)^{N}

arrays. Since the answer can be huge, print it modulo

754974721

Input Format

First line will contain $T$

, the number of test cases. Then the test cases follow.

Each test case contains a single line of input, three integers

N, P,

and

M

Output Format

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

Constraints

$1 \leq T \leq 10^{4}$

1 \leq M \leq 10^{5}

1 \leq P \leq 10^{9}

1 \leq N \leq 10^{9}

Sum of

M

over all test cases does not exceed

10^{6}

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

Explanation

Test case $1$

: There are

(1 + 1)^{1} = 2

distinct arrays. The arrays are :

[0]

and

[1]

$f ([0]) =$

MEX of

[0] = 1

. Also,

g ([0]) = (f ([0]))^{1} = 1^{1} = 1

f ([1]) =

MEX of

[1] = 0

. Also,

g ([1]) = (f ([1]))^{1} = 0^{1} = 0

Sum of $g (A)$

1 + 0 = 1

Test case $2$

: There are

(1 + 1)^{2} = 4

distinct arrays. The arrays are :

[0, 0], [0, 1], [1, 0]

and

[1, 1]

$f ([0, 0]) =$

MEX of

[0, 0] = 1

. Also,

g ([0, 0]) = (f ([0, 0]))^{2} = 1^{2} = 1

f ([0, 1]) =

MEX of

[0, 1] = 2

. Also,

g ([0, 1]) = (f ([0, 1]))^{2} = 2^{2} = 4

f ([1, 0]) =

MEX of

[1, 0] = 2

. Also,

g ([1, 0]) = (f ([1, 0]))^{2} = 2^{2} = 4

f ([1, 1]) =

MEX of

[1, 1] = 0

. Also,

g ([1, 1]) = (f ([1, 1]))^{2} = 0^{2} = 0

Sum of $g (A)$

1 + 4 + 4 + 0 = 9