H - Quantum Multiplication
解説
/
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 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