AT_arc212_f [ARC212F] Add Integer

题目描述

给定整数 $N, M, X$。

通过以下操作构造一个长度为 $N$ 的非负整数序列 $A$：

• 首先，自由选择一个长度为 $2$ 的整数序列 $A = (A_1, A_2)$。
• 然后，对 $A$ 执行 $N - 2$ 次如下操作：
  • 设当前序列长度为 $k = |A|$，令 $x = A_{k-1}$，$y = A_k$。
  • 在序列末尾追加 $x + y$ 或 $y - x$ 中的一个。

称一个序列 $A$ 为好序列，当且仅当满足：

• 对所有 $1 \le i \le N$，有 $0 \le A_i \le M$；
• $A_N = X$。

求所有可通过上述操作得到的好序列的 $A_1 \times A_2$ 之和，结果对 $998244353$ 取模。

输入格式

输入从标准输入按以下格式给出：

$N$ $M$ $X$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 4 3

输出 #1

8

输入输出样例 #2

输入 #2

150000 160000 140000

输出 #2

791841701

说明/提示

样例解释 1

一些可能的序列为 $(0,3,3)$、$(1,4,3)$、$(2,1,3)$。

所有可能序列的 $A_1 \times A_2$ 之和为 $8$。

约束条件

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq X \leq M \leq 2 \times 10^5$
• 所有输入值均为整数。