← 返回题目列表

AtCoder · kupc2019_k

K. 一项或全部

中文机器翻译题面 查看原题

配点 : 500 点

問題文

安吉尔喜欢玩弄变量。

今天 3 变量 我准备了 x,~y,~z 并决定和他们一起玩。 3 变量是 它用 0 初始化。

Angier 选择对这些变量执行以下操作之一: 我要重复 n 次。

  • 变量 1 选择一项。该变量的值 1 增加或 1 减少。
  • 3 所有变量的值 增加 1 或 减少 1 。 执行

n 操作后, 除以x,~y,~z 的 m 后的余数为 p,~q,~r 当 安杰很满意。

安格正在寻找让她快乐的事情。 n 我对有多少种操作序列感兴趣。 代替她,统计这样的操作序列的类型数量, 请打印除以998244353 后的余数。

这里 2 运算序列为整数 i\ (1 \leq i \leq n) 存在,i 第一次操作后 1 当两个或多个变量具有不同的值时,它们被认为是不同的类型。

制約

  • 所有输入均为整数。
  • 1 \leq n \leq 10^6
  • 1 \leq m \leq 10^6
  • 0 \leq p,\ q,\ r < m

入力

输入是按以下格式从标准输入给出的。

n m p q r

出力

找出满足Angier的操作序列类型的数量。 打印除以 998244353 后的余数。 通过


入力例 1

1 3 1 2 2

出力例 1

0

1 操作, 1 仅一个变量的值 1 增加,剩余 2 两个变量的值为 1 无法减少。


入力例 2

2 3 1 2 2

出力例 2

2

首先, 如果3 所有变量的值 1 减少。下一步 仅 x 的值 1 通过减少x 的值为 -2、 y 的值为 -1、z 的值为 -1 。 这些 除以 3 的余数为 安吉尔对这一系列操作感到满意,因为 1,~2,~2 。

满足Angier的操作序列包括该操作序列。 2 有不同的类型。


入力例 3

1000000 4 1 2 3

出力例 3

333551635