Melodious Strings

We are given a positive integer \(k\) which is the size of the character set. The characters are represented by positive integers from \(1\) to \(k\) (the \(i\)th character is represented by \(i\)).

Given a positive integer \(m\), a string \(\mathcal{S}\) is defined as melodious if and only if either:

• \(|\mathcal{S}| < m+2\), or
• for every way of deleting exactly \(m\) characters from \(\mathcal{S}\), the resulting string does not contain any contiguous palindromic substring of length greater than \(1\).

A little thought shows that for any string of length at least \(m+2\) the condition is equivalent to requiring that all characters in the string are distinct. (Indeed, for any two positions \(i<j\) one can delete all other characters so that \(\mathcal{S}_i\) and \(\mathcal{S}_j\) become consecutive. Thus a repeated character would yield a palindromic block of length \(2\), and similarly a palindromic substring of length \(3\) cannot occur if all characters are distinct.)

You are to process \(q\) queries. In each query, you are given:

• A melodious string \(T\) of length \(m+2\) (so \(T\) consists of \(m+2\) distinct characters), which must appear as the prefix of the string \(S\) that you form.
• A set \(U\) of distinct characters (each represented as a positive integer), with the property that the last character of \(S\) must be chosen from \(U\).

Your task is to count, modulo \(998244353\), the number of strings \(S\) of length \(n\) that satisfy:

1. The prefix of \(S\) is \(T\) (i.e. \(T\) appears as the first \(m+2\) characters).
2. \(S\) is melodious (and hence, when \(n \ge m+2\), all characters in \(S\) are distinct).
3. The last character of \(S\) is in \(U\).

Note: It is guaranteed that \(k - m \ge 3\) (so there are enough characters to choose from).

---

Observations:

Since \(T\) (of length \(m+2\)) is fixed and melodious, its characters are all distinct. For \(S\) to be melodious (given \(n \ge m+2\)), every character in \(S\) must be distinct. Thus, after fixing the prefix \(T\), the remaining \(n - (m+2)\) positions of \(S\) must be filled with distinct characters chosen from the set of available characters \([1,k]\setminus T\). Moreover, the last character of \(S\) (which may come from this available set) must belong to \(U\;\setminus\;T\; (\)if any element of \(U\) already appears in \(T\) then they cannot appear again due to the distinctness requirement).

Let \(L_0 = m+2\) and let \(r = n - L_0\). If \(r=0\) then \(S = T\) and the answer is \(1\) if the last character of \(T\) is in \(U\) and \(0\) otherwise. If \(r > 0\), then the number of ways to choose the remaining characters is given by:

[ \text{answer} = \Big|U \setminus T\Big| \times P\Big(k - L_0 - 1, r - 1\Big) \quad\text{(mod }998244353\text{)}, ]

where \(P(n,r)\) is the permutation function \(n \times (n-1) \times \cdots \times (n-r+1)\). (The idea is to first choose the character for the last position from \(U\setminus T\) and then fill the rest of the positions arbitrarily with the remaining available characters.)

inputFormat

The input begins with a line containing four integers \(k\), \(m\), \(n\) and \(q\): the size of the alphabet, the parameter \(m\) for the definition of melodious strings, the length of the string \(S\) to be formed, and the number of queries, respectively.

Then, for each query:

• A line containing \(m+2\) integers representing the string \(T\) (which is melodious, i.e. all \(m+2\) characters are distinct).
• A line beginning with an integer \(r_U\) (the number of characters in the set \(U\)), followed by \(r_U\) distinct integers representing the set \(U\).

All numbers are separated by spaces.

outputFormat

For each query, output a single line containing the number of strings \(S\) of length \(n\) satisfying the given conditions, modulo \(998244353\).

sample

10 3 6 3
1 2 3 4 5
3 5 7
1 2 3 4 6
2 2 7
2 4 6 8 9
3 3 1 10

1
1
0

</p>