配点 : 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