Furniture Arrangement Transitions

You are given k distinct pieces of furniture and n distinct rooms (numbered 0 to n-1). A furniture arrangement is specified by placing each of the k furniture items into one of the n rooms. (We do not care about the placement within a room.) Thus, there are exactly n^k possible arrangements. We number the arrangements from 0 to n^k - 1 using the following rule:

If in an arrangement the i-th furniture (0 ≤ i ≤ k-1) is in room p_i, then the arrangement’s number is defined as

[ A = \sum_{i=0}^{k-1} p_i,n^i. ]

It turns out that every arrangement gets a unique number.

For each arrangement, a score is given as input. Now, you are also given an initial arrangement and a number T. Then, you perform exactly T rounds of the following operation:

• In one round, you choose one piece of furniture (there are k choices) and move it to any other room (each has n-1 choices, as it cannot remain in the same room).

Thus, in each round there are k(n-1) decision choices and, over T rounds, there are exactly k^T(n-1)^T possible decision sequences. Note that different decision sequences may result in the same final arrangement. Your task is to compute, for an online series of q queries, the sum of the scores for the final arrangements over all decision sequences (modulo P = 998244353). In other words, if you denote by S(a) the score of arrangement a and by A the transition matrix describing one move (with A(a, b) equal to the number of ways to go from arrangement a to b in one move), then for a query with initial arrangement u and T rounds, you need to compute

[ \sum_{b=0}^{n^k-1} (A^T)[u,b] \cdot S(b) \mod 998244353. ]

Input/Output format are described below.

---

Input Description

The first line contains two integers n and k.

The second line contains n^k integers, where the i-th integer (0-indexed) is the score of the arrangement with number i.

The third line contains an integer q – the number of queries.

Each of the following q lines contains two integers: the initial arrangement number and T (the number of rounds).

---

Output Description

For each query, output a single integer – the required sum modulo 998244353.

---

Note: In each move, when a furniture item is moved, its transition (from its current room r to a room s with s≠r) can be analyzed independently. In fact, for a single piece of furniture, if we define

[ A(t)=\frac{(n-1)^t+(n-1)(-1)^t}{n}, \quad B(t)=\frac{(n-1)^t-(-1)^t}{n}, ]

then when a furniture item originally in room r is moved exactly t times, the number of ways to end in room s is A(t) if s=r and B(t) otherwise. Using combinatorial convolution (together with the multinomial coefficient coming from the ordering of moves), one can show that the answer for a query can be expressed in closed‐form using only small summations. (See explanation in the sample section.)

You may assume that all input numbers are such that a solution using the above approach will run in time.

inputFormat

The input begins with two integers n and k.

The next line contains n^k integers – the scores for arrangement 0, 1, …, n^k−1.

The next line contains an integer q, the number of queries.

Each of the next q lines contains two integers: the initial arrangement number and T.

outputFormat

For each query, output a single integer – the sum over all decision sequences of the final arrangement scores, modulo 998244353.

sample

2 2
1 2 3 4
2
0 1
3 2

5
10

</p>