問題文

数列内の隣接する二項の差の絶対値が全て 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}

入力例 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