Description

有一排 $n$ 个格子，有 $m$ 个人，初始都在 $1$ 号格。

每个人可以选择往前跳一格或者跳两格，跳一格的方法数为 $p$，跳两格的方法数为 $q$，跳出 $n$ 个格子则停止，注意在第 $n$ 个格子仍然能选择跳一或两格。

你需要计算有多少种方法使得每个格子都至少被一个人踩过。

Input Format

第一行输入四个整数，$n,m,p,q$。

Output Format

输出答案对 $998244353$ 取模。

10 3 5 6

273459417

2 1 3 4

21

20010910 666 1 1

773849796

Hint

数据范围及约定

• 对于 $100\%$ 的数据，满足 $1 \le n \le 10^9$，$1 \le m \le 6 \times 10^4$，$1 \le p,q \in [0,998244353)$。

各子任务限制如下：

• 子任务 $1$（ $20$ 分）：$1 \le n \le 10^9$，$1 \le m \le 100$；
• 子任务 $2$（ $10$ 分）：$1 \le n \le 10^3$；
• 子任务 $3$（ $10$ 分）：$1 \le n \le 10^5$；
• 子任务 $4$（ $20$ 分）：$1 \le n \le 10^9$，$1 \le m \le 3 \times 10^4$，$p=q=1$；
• 子任务 $5$（ $40$ 分）：无特殊限制；