Problem Background

LMX gives HQZ an interesting sequence, and HQZ, wanting to understand LMX's interests, wants to solve the following problem.

Problem Description

Given an initial sequence of length $n$ filled with zeros, we will perform the following operations $q$ times:

• Arbitrarily select a position $t$ and modify the number at that position to any number between $1$ and $k$.

This means we will have $(nk)^q$ different query sequences, and for each different query sequence, there are $(nk)^q$ result sequences.

Next, given a matching sequence $B$ of length $m$, we need to find the total number of times this matching sequence appears in each result sequence. Note that if a matching sequence appears multiple times in a result sequence, it should be counted repeatedly.

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

This problem uses a specific method to generate input data.

The generation format is as follows: $x_i = (a \times i + b) \mod k + 1$, where $x_i$ represents the required number at the $i$-th position 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

A single line containing one integer representing the answer.

Sample Input and Output

Sample Input #1

3 2 2 2
1 1

Sample Output #1

4

Sample Input #2

2 1 2 2
1 1

Sample Output #2

12

Sample Input #3

10 3 114 51419
19 2

Sample Output #3

266405589

Notes

Sample Explanation #1

The following operation sequences contain sequence $B$:
- $[1,1], [2,2]$ results in sequence $[1,2,0]$
- $[2,2], [1,1]$ results in sequence $[1,2,0]$
- $[2,1], [3,2]$ results in sequence $[0,1,2]$
- $[3,2], [2,1]$ results in 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$.

见题面 Input 部分

见题面 Output 部分