Background

Warning: Malicious submissions for this problem will result in an account ban.

Lord Divine Tree wants to make a magic wand, so that he can use the “Pigeon-Fixing Spell” to fix God J in place.

On the first day, Lord Divine Tree found a piece of wood on himself. He used a branch at the top of the tree that even God J could not reach. Because this wood cannot be understood by mortals, Lord Divine Tree called it the “Mysterious Wood”.

On the second day, Lord Divine Tree needed to create an environment for casting spells. So he spent several hours building a complete magical world. Because this world cannot be understood by mortals, Lord Divine Tree called it the “Elephant World”.

On the third day, Lord Divine Tree needed to enchant the Mysterious Wood. So he wrote an incantation and let it run in the Elephant World. Because this incantation cannot be understood by mortals, Lord Divine Tree called it the “Language of Flowers”.

Lord Divine Tree invited God J to visit the Elephant World. God J arrived several days late. Seeing Lord Divine Tree muttering to himself, God J asked, “What are you doing?” Lord Divine Tree immediately pulled out the Mysterious Wood, aimed it at God J, and shouted:

“system call Joker remove pigeon protection！system call Joker Δεσμευτική！system call Joker ログアウト禁止！...”

God J was fixed in place at once. Lord Divine Tree was very satisfied, so he left the Elephant World and ordered God J to stay inside and solve problems. Because these problems cannot be understood by mortals, God J only gave you a simplified version.

Problem 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