Problem Description

When the absolute value of the difference between every pair of adjacent terms in a sequence is $1$, we call that sequence a good sequence.

The score of a good sequence $X$ is defined as follows:

• The product of all $X_i$ for every $i$ where $X_i - X_{i-1} = 1$
• If no such $i$ exists, the score is $1$

Output the sum of the scores for all good sequences of length $N$ with the first term $A$ and the last term $B$, modulo $998244353$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A $ $ B $

Output Format

Print the answer in one line.

Sample Input and Output

Sample Input #1

3 0 2

Sample Output #1

2

Sample Input #2

5 0 2

Sample Output #2

12

Sample Input #3

1877 4 12

Sample Output #3

672408519

Notes/Hints

Constraints

• All inputs are integers
• $2 \leq N \leq 2 \times 10^7$
• $0 \leq A, B \leq 2 \times 10^7$

Sample Explanation 1

The only good sequence that satisfies the conditions is $ (0, 1, 2) $, and the score of this sequence is $1 \times 2 = 2$.

Sample Explanation 2

The good sequences that satisfy the conditions are $ (0, 1, 2, 3, 2), (0, 1, 2, 1, 2), (0, 1, 0, 1, 2), (0, -1, 0, 1, 2) $, with four types in total. The scores of these sequences are $ 6, 4, 2, 0 $ respectively.

见题面 Input 部分

见题面 Output 部分