分数: 700 点
问题陈述
给你整数 N,M,X.
执行以下一系列操作来创建序列 A 长度 N 由非负整数组成。
- 自由决定整数序列 A=(A_1,A_2) 长度 2.
- 然后,执行以下操作 N-2 次 A.
- 让 k=|A|。让 x=A_{k-1}, y=A_k。附加任一 x+y or y-x 到年底 A.
一个序列 A 是一个好的序列当且仅当它满足以下条件:
- 0 \le A_i \le M \ (1 \le i \le N)
- A_N=X
求总和,模 998244353,属于 A_1 \times A_2 超过可以通过操作获得的所有好的序列。
约束
- 3 \leq N \leq 2 \times 10^5
- 1 \leq X \leq M \leq 2 \times 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X
输出
输出答案。
样本输入 1
3 4 3
示例输出 1
8
一些可能的序列是 (0,3,3),(1,4,3),(2,1,3).
总和 一个输入文件中的 A_1 \times A_2 所有可能的序列是 8.
示例输入 2
150000 160000 140000
示例输出 2
791841701