← 返回题目列表

AtCoder · utpc2021_h

H. 量子倍增

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

配点 : 100 点

問題文

序列中相邻两项之差的绝对值为全部 1 ,那么序列是 良好的数列 我们称之为 。 所有满足

良好的数列 我们称之为 X 的分数确定如下。

  • X_{i} - X_{i-1} = 1 该值乘以 i 关于 X_i 乘以的值
  • 这样的 i 不存在,则 1

长度是 N 首项为 A末项为 B 似乎是 良好的数列 我们称之为 对所有的分数总和为 998244353 后的余数。

制約

  • 所有输入均为整数
  • 2 \leq N \leq 2 \times 10^{7}
  • 0 \leq A,B \leq 2 \times 10^{7}

入力

输入是按以下格式从标准输入给出的。

N A B

出力

答案 请打印除以 1 行输出。


入力例 1

3 0 2

出力例 1

2

满足条件的优良数列是 (0, 1, 2) 仅有这一种,该数列的分数为 1 \times 2=2 。


入力例 2

5 0 2

出力例 2

12

满足条件的优良数列是 (0, 1, 2, 3, 2), (0, 1, 2, 1, 2), (0, 1, 0, 1, 2), (0, -1, 0, 1, 2) 可以得到第 4 种类为, 每个数列的分数为 6, 4, 2, 0 。


入力例 3

1877 4 12

出力例 3

672408519