AT_utpc2021_h.Quantum Multiplication

我们称一个数列为「好的数列」，如果序列中每一对相邻项的差的绝对值都等于1。

定义一个「好的数列」$X$ 的分数如下：

• 对于所有满足条件的 $i$，即 $X_i - X_{i-1} = 1$ 的情形，计算相应的 $X_i$ 的乘积。
• 若没有满足条件的 $i$，则分数为 $1$。

你的任务是计算所有满足以下条件的「好的数列」的分数总和，并输出该总和除以 $998244353$ 的余数：

• 数列长度为 $N$；
• 数列的首项为 $A$；
• 数列的末项为 $B$。

输入包含三个整数 $N$、$A$ 和 $B$，它们表示数列的长度以及数列的首项和末项。

输出一个整数，为所有符合条件的「好的数列」的分数总和对 $998244353$ 取模后的结果。

• 输入的三个数均为整数。
• $2 \leq N \leq 2 \times 10^7$
• $0 \leq A, B \leq 2 \times 10^7$

样例解释 1

唯一符合条件的「好的数列」为 $(0, 1, 2)$，其分数计算为 $1 \times 2 = 2$。

样例解释 2

符合条件的「好的数列」有4个：$(0, 1, 2, 3, 2)$、$(0, 1, 2, 1, 2)$、$(0, 1, 0, 1, 2)$ 和 $(0, -1, 0, 1, 2)$。它们的分数分别为 $6, 4, 2, 0$。

本翻译由 AI 自动生成