Counting Pattern Occurrences in Randomly Updated Sequences

You are given an initial sequence \(S\) of length \(n\) with all entries equal to 0. Then, you perform \(q\) operations. In each operation, you choose an index \(t\) (\(1 \le t \le n\)) and update \(S_t\) to any integer from \(1\) to \(k\) (inclusive).

Thus, there are \((n\,k)^q\) different sequences of operations. Note that different sequences of operations may lead to the same final sequence, but we count each sequence of operations separately.

You are also given a matching pattern sequence \(B\) of length \(m\). The pattern \(B\) is generated in a special way:

[ x_i = (a \times i + b) \bmod k + 1, \quad 1 \le i \le m. ]

Your task is to compute, over all \((n\,k)^q\) operation sequences, the total number of occurrences of \(B\) as a contiguous subsequence in the corresponding final sequence \(S\). If \(B\) appears multiple times in one final sequence, count all occurrences. Since the answer can be very large, output it modulo \(998244353\).

Explanation

For a fixed interval \(i\) (where \(1 \le i \le n-m+1\)), we want to count, over all operation sequences, the number of times \(S[i..i+m-1]=B\). An important observation is that the final value at any position \(j\) is determined by whether that position was updated at least once: if never updated, \(S_j=0\); if updated, \(S_j\) becomes the number chosen in the last update for that position. Since the updating number is chosen arbitrarily from \(1\) to \(k\), if \(S_j\) is updated then it is equal to any particular number in \(\{1,\dots,k\}\) with probability \(1/k\).

By an inclusion–exclusion argument on the \(m\) positions of the interval we get that the total answer is given by the formula below (modulo \(998244353\)):

[ \text{answer} = (n-m+1),k^{q-m},\sum_{j=0}^{m} (-1)^j \binom{m}{j} (n-j)^q \mod 998244353. ]

Note that even though the pattern \(B\) is generated using the formula \(x_i = (a\, i + b) \bmod k + 1\), the final answer depends only on \(n, m, q\) and \(k\).

inputFormat

The input consists of a single line containing six integers separated by spaces:

• \(n\) \(\;\;(\;1 \le n\;)\)
• \(m\) \(\;\;(\;1 \le m \le n)\)
• \(q\) \(\;\;(\;q \ge 0)\)
• \(k\) \(\;\;(\;k \ge 1)\) - the range of numbers for updates.
• \(a\) and \(b\) - integers used to generate the pattern \(B\) by the formula: \(x_i = (a\, i + b) \bmod k + 1\) for \(1 \le i \le m\).

Note: The input is generated in a special way. However, your solution only needs to compute the answer using the provided formulas.

outputFormat

Output a single integer: the total number of occurrences of \(B\) in all final sequences, modulo \(998244353\).

sample

3 2 1 2 1 1

0