题目描述

题目背景

神树大人想要做一根魔杖，这样他就可以使用「鸽子固定咒」把神 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

数据范围与提示

对于所有数据，$N\leq 10^9,M\leq 60000,p,q\in[0,998244353)$。

各子任务限制如下：

• 子任务 $1$（$20$ 分）：$N\leq 10^9,M\leq 100$；
• 子任务 $2$（$10$ 分）：$N\leq 10^3$；
• 子任务 $3$（$10$ 分）：$N\leq 10^5$；
• 子任务 $4$（$20$ 分）：$N\leq 10^9,M\leq 30000,p=q=1$；
• 子任务 $5$（$40$ 分）：无特殊限制。