Problem Description

There is a row of $n$ grids, and $m$ people, all initially at the 1st grid.

Each person can choose to jump one grid forward or two grids forward. The number of ways to jump one grid is $p$, and the number of ways to jump two grids is $q$. Once they jump out of the $n$ grids, they stop. Note that even at the $n$th grid, they can still choose to jump one or two grids.

You need to calculate the number of ways such that every grid is stepped on by at least one person.

Input Format

The first line contains four integers, $n, m, p, q$.

Output Format

Output the answer modulo $998244353$.

Sample Input and Output

Sample Input #1

10 3 5 6

Sample Output #1

273459417

Sample Input #2

2 1 3 4

Sample Output #2

21

Sample Input #3

20010910 666 1 1

Sample Output #3

773849796

Notes

Data Range and Constraints

• For $100\%$ of the data, it satisfies $1 \le n \le 10^9$, $1 \le m \le 6 \times 10^4$, $1 \le p, q < 998244353$.

Subtask constraints are as follows:

• Subtask $1$ ($20$ points): $1 \le n \le 10^9$, $1 \le m \le 100$;
• Subtask $2$ ($10$ points): $1 \le n \le 10^3$;
• Subtask $3$ ($10$ points): $1 \le n \le 10^5$;
• Subtask $4$ ($20$ points): $1 \le n \le 10^9$, $1 \le m \le 3 \times 10^4$, $p = q = 1$;
• Subtask $5$ ($40$ points): No special constraints;

见题面 Input 部分

见题面 Output 部分