F - Add Integer 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

整数 N,M,X が与えられます。

以下の一連の操作を行い、長さ N の非負整数列 A を作ります。

  • 長さ 2 の整数列 A=(A_1,A_2) を自由に決める。
  • その後、A に対して以下の操作を N-2 回行う。
    • k=|A| とする。x=A_{k-1}, y=A_k とする。A の末尾に x+y または y-x を追加する。

また、整数列 A が良い数列であるとは、以下を満たすことを言います。

  • 0 \le A_i \le M \ (1 \le i \le N)
  • A_N=X

操作によって得られる全ての良い数列に対する A_1 \times A_2 の総和を 998244353 で割ったあまりを求めてください。

制約

  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq X \leq M \leq 2 \times 10^5
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M X

出力

答えを出力せよ。

入力例 1

3 4 3

出力例 1

8

(0,3,3),(1,4,3),(2,1,3) などが考えられます。

あり得る数列全ての A_1 \times A_2 の和は 8 となります。

入力例 2

150000 160000 140000

出力例 2

791841701

Score : 700 points

Problem Statement

You are given integers N,M,X.

Perform the following series of operations to create a sequence A of length N consisting of non-negative integers.

  • Freely decide an integer sequence A=(A_1,A_2) of length 2.
  • Then, perform the following operation N-2 times on A.
    • Let k=|A|. Let x=A_{k-1}, y=A_k. Append either x+y or y-x to the end of A.

A sequence A is a good sequence if and only if it satisfies the following:

  • 0 \le A_i \le M \ (1 \le i \le N)
  • A_N=X

Find the sum, modulo 998244353, of A_1 \times A_2 over all good sequences that can be obtained by the operations.

Constraints

  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq X \leq M \leq 2 \times 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M X

Output

Output the answer.

Sample Input 1

3 4 3

Sample Output 1

8

Some possible sequences are (0,3,3),(1,4,3),(2,1,3).

The sum of A_1 \times A_2 over all possible sequences is 8.

Sample Input 2

150000 160000 140000

Sample Output 2

791841701