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$。在 $A$ 的末尾添加 $x + y$ 或 $y - x$。

当且仅当序列 $A$ 满足下列条件时，称之为“好序列”：

• $0 \leq A_i \leq M\quad (1 \leq i \leq N)$
• $A_N = X$

请你求出所有通过上述操作得到的“好序列”的 $A_1 \times A_2$ 之和，答案对 $998244353$ 取模。

输入由标准输入给出，格式如下：

$N$ $M$ $X$

输出答案。

样例解释 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$
• 所有输入均为整数。

由 ChatGPT 5 翻译