← 返回题目列表

AtCoder · arc212_f

F. 添加整数

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

分数: 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