Yet Another LIS Problem

 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.

You are given 3$3$ integers M$M$, P$P$ and N$N$.

For an array A$A$, let f(A)$f(A)$ be defined as the length of the longest strictly increasing subsequence of A$A$ and let g(A)=(f(A))P$g(A)=(f(A){)}^P$.

Consider all distinct arrays A$A$ of length N$N$ such that 1≤Ai≤M$1\le A_i\le M$ for all (1≤i≤N)$(1\le i\le N)$. Calculate the sum of g(A)$g(A)$ over all such MN$M^N$ arrays. Since the answer can be huge, print it modulo 754974721$754974721$.

Each test case has Q$Q$ queries. For all Q$Q$ queries, M$M$ and P$P$ remain the same, only N$N$ varies.

Input Format

• First line will contain T$T$, the number of test cases. Then the test cases follow.
• First line of each test case contains three integers M,P,$M,P,$ and Q$Q$.
• Second line of each test case contains Q$Q$ integers, values of N$N$ for each query.

Output Format

For each testcase, output in a single line containing Q$Q$ space-separated integers, answers for each query modulo 754974721$754974721$.

Constraints

• 1≤T≤4$1\le T\le 4$
• 1≤M≤14$1\le M\le 14$
• 1≤P≤106$1\le P\le {10}^6$
• 1≤N≤109$1\le N\le {10}^9$
• 1≤Q≤50$1\le Q\le 50$

Sample Input 1 

4
1 1 2
1 2
2 1 2
1 2
2 2 2
1 2
2 1000000 2
1 2

Sample Output 1 

1 1 
2 5 
2 7 
2 392816544 

Explanation

Test case 1$1$: In the first query there are 11=1$1^1=1$ distinct arrays. The array is : [1]$[1]$.

• f([1])=$f([1])=$ LIS of [1]=1$[1]=1$. Also, g([1])=(f([1]))1=11=1$g([1])=(f([1]){)}^1=1^1=1$.

Sum of g(A)$g(A)$ is 1$1$.

In the second query there are 12=1$1^2=1$ distinct arrays. The array is : [1,1]$[1,1]$.

• f([1,1])=$f([1,1])=$ LIS of [1,1]=1$[1,1]=1$. Also, g([1,1])=(f([1,1]))1=11=1$g([1,1])=(f([1,1]){)}^1=1^1=1$.

Sum of g(A)$g(A)$ is 1$1$.

Test case 2$2$: In the first query there are 21=2$2^1=2$ distinct arrays. The arrays are : [1]$[1]$ and [2]$[2]$.

• f([1])=$f([1])=$ LIS of [1]=1$[1]=1$. Also, g([1])=(f([1]))1=11=1$g([1])=(f([1]){)}^1=1^1=1$.
• f([2])=$f([2])=$ LIS of [2]=1$[2]=1$. Also, g([2])=(f([2]))1=11=1$g([2])=(f([2]){)}^1=1^1=1$. Sum of g(A)$g(A)$ is 1+1=2$1+1=2$.

In the second query there are 22=4$2^2=4$ distinct arrays. The arrays are : [1,1],[1,2],[2,1]$[1,1],[1,2],[2,1]$ and [2,2]$[2,2]$.

• f([1,1])=$f([1,1])=$ LIS of [1,1]=1$[1,1]=1$. Also, g([1,1])=(f([1,1]))1=11=1$g([1,1])=(f([1,1]){)}^1=1^1=1$.
• f([1,2])=$f([1,2])=$ LIS of [1,2]=2$[1,2]=2$. Also, g([1,2])=(f([1,2]))1=21=2$g([1,2])=(f([1,2]){)}^1=2^1=2$.
• f([2,1])=$f([2,1])=$ LIS of [2,1]=1$[2,1]=1$. Also, g([2,1])=(f([2,1]))1=11=1$g([2,1])=(f([2,1]){)}^1=1^1=1$.
• f([2,2])=$f([2,2])=$ LIS of [2,2]=1$[2,2]=1$. Also, g([2,2])=(f([2,2]))1=11=1$g([2,2])=(f([2,2]){)}^1=1^1=1$.

Sum of g(A)$g(A)$ is 1+2+1+1=5$1+2+1+1=5$.