#3071. 「2019 集训队互测 Day 2」神树大人挥动魔杖

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

题目背景

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

样例

样例输入 1

10 3 5 6

样例输出 1

273459417

样例输入 2

2 1 3 4

样例输出 2

21

样例输入 3

20010910 666 1 1

样例输出 3

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 分):无特殊限制。