Background

LMX gives HQZ an interesting sequence. To understand LMX’s preferences, HQZ wants to solve the following problem.

Problem Description

Given an initial sequence of length $n$ that is all $0$, we will perform the following operation $q$ times.

• Choose any position $t$ and change the number at that position to any integer between $1$ and $k$.

That is, in total there are $(nk)^q$ different operation sequences. For each different operation sequence, there is a corresponding resulting sequence.

Next, a matching sequence $B$ of length $m$ is given. You need to compute the total number of occurrences of this matching sequence across every resulting sequence. Note that if a resulting sequence contains multiple occurrences of the matching sequence, they should be counted repeatedly.

Since the answer is too large, you only need to output the answer modulo $998244353$.

This problem uses a special method to generate the input data.

The generation format is: $x_i=(a \times i+b)\bmod k +1$, where $x_i$ denotes the required number at position $i$ of sequence $B$.

Input Format

The first line contains four integers $n,m,q,k$, where $m$ is the length of sequence $B$.

The second line contains two integers $a,b$.

Output Format

Output one integer representing the answer.

3 2 2 2
1 1

4

2 1 2 2
1 1

12

10 3 114 51419
19 2

266405589

Hint

Sample Explanation #1

For the following operation sequences, sequence $B$ appears:

• $[1,1],[2,2]$ produces the sequence $[1,2,0]$.
• $[2,2],[1,1]$ produces the sequence $[1,2,0]$.
• $[2,1],[3,2]$ produces the sequence $[0,1,2]$.
• $[3,2],[2,1]$ produces the sequence $[0,1,2]$.

For $100\%$ of the data, it is guaranteed that $\forall x_i \in B, 1\le x_i\le k$, $0 \le a,b\le 10^9$, and $m\le n$.

Translated by ChatGPT 5