题目背景

警告：恶意提交本题将被封号。

神树大人想要做一根魔杖，这样他就可以使用「鸽子固定咒」把神 J 固定住了。

第一天，神树大人在自己身上找了一根木头。神树大人使用了树顶上连神 J 都够不到的树枝。由于这根木头不能被凡人所理解，所以神树大人称它为「迷之木」。

第二天，神树大人需要为施法创造环境。于是神树大人花了数小时造了一个完整的魔法世界，由于这个世界不能被凡人所理解，所以神树大人称它为「大象世界」。

第三天，神树大人需要对迷之木附魔。于是神树大人写了一段咒语并让它在大象世界里运行，由于这段咒语不能被凡人所理解，所以神树大人称它为「花之语」。

神树大人邀请神 J 来到大象世界游玩，神 J 迟了若干天才到。神 J 见神树大人嘴里念念有词，便问道：「你在干什么？」神树大人立即掏出迷之木，对准神 J 大喊道：

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

神 J 立刻被固定住了。神树大人很满意，于是离开了大象世界，并命令神 J 留在里面做题。由于这些题不能被凡人所理解，所以神 J 只把简化版给了你。

题目描述

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

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

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

输入格式

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

输出格式

输出答案对 $998244353$ 取模。

10 3 5 6

273459417

2 1 3 4

21

20010910 666 1 1

773849796

提示

数据范围及约定

• 对于 $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$ 分）：无特殊限制；