Description

There is a row of $n$ cells and $m$ people, all starting at cell $1$.

Each person may choose to jump forward by $1$ cell or by $2$ cells. The number of ways to make a $1$-cell jump is $p$, and the number of ways to make a $2$-cell jump is $q$. Once a person jumps out of the $n$ cells, they stop. Note that even on cell $n$, one can still choose to jump by $1$ or $2$ cells.

You need to compute how many ways there are such that every cell 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$.

10 3 5 6

273459417

2 1 3 4

21

20010910 666 1 1

773849796

Hint

Constraints and Conventions

• For $100\%$ of the testdata, $1 \le n \le 10^9$, $1 \le m \le 6 \times 10^4$, and $1 \le p,q \in [0,998244353)$.

The limits for each subtask 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 limits.

Translated by ChatGPT 5