← 返回题目列表

AtCoder · xmascon22_d

D. 二分法

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

配点 : 100 点

描述兔子们跳来跳去玩耍的情况,鳗鱼用数学公式表示。这是二叉树的问题。

問題文

非負整数 N, A, B, C 。

正整数列 (x_0, x_1, \ldots, x_N) ,并求满足以下所有条件的个数 998244353 除以多少的余数:

  • x_0 = 2^A \times 2^B.
  • x_N = ((2^A + 1) \times 2^C) - 1.
  • 各 i = 0, 1, \ldots, N - 1 , 定义x_{i+1} \in \{ \lfloor x_i/2 \rfloor, 2 x_i, 2 x_i + 1 \}.

制約

  • 0 \le N, A, B, C \le 10^7.

入力

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

N A B C

出力

个数为 998244353 后的余数。 对于


入力例 1

4 1 1 1

出力例 1

7

满足条件的集合 (x_0, x_1, x_2, x_3, x_4) 如下 7 个为:

  • (4, 2, 1, 2, 5)
  • (4, 2, 4, 2, 5)
  • (4, 2, 5, 2, 5)
  • (4, 2, 5, 10, 5)
  • (4, 2, 5, 11, 5)
  • (4, 8, 4, 2, 5)
  • (4, 9, 4, 2, 5)

入力例 2

9 2 0 1

出力例 2

1164

入力例 3

1 0 2 4

出力例 3

0

入力例 4

2022 12 24 14

出力例 4

426021617