B - Tuple of Integers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 2 点

問題文

整数 N が与えられます。次の条件を全て満たす非負整数の組 (a, b, c, d) の個数を 998244353 で割った余りを求めてください。

  • a + b + c + d = N
  • a は 0 または 1
  • b は 0 または 1 または 2
  • c は偶数
  • d は 3 の倍数

制約

  • 0 \leq N \leq 10^9
  • N は整数

入力

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

N

出力

答えを出力せよ。

入力例 1

5

出力例 1

6

条件を満たす (a,b,c,d) は次の 6 個です。

  • (0,0,2,3)
  • (0,1,4,0)
  • (0,2,0,3)
  • (1,0,4,0)
  • (1,1,0,3)
  • (1,2,2,0)

入力例 2

1000000000

出力例 2

1755648

Score: 2 points

Problem Statement

You are given an integer N.
Find the number of non-negative integer quadruples (a, b, c, d) that satisfy all of the following conditions, and output the result modulo 998244353:

  • a + b + c + d = N
  • a is 0 or 1
  • b is 0, 1, or 2
  • c is even
  • d is a multiple of 3

Constraints

  • 0 \leq N \leq 10^9
  • N is an integer

Input

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

N

Output

Print the answer.

Sample Input 1

5

Sample Output 1

6

The following 6 quadruples (a,b,c,d) satisfy the conditions:

  • (0,0,2,3)
  • (0,1,4,0)
  • (0,2,0,3)
  • (1,0,4,0)
  • (1,1,0,3)
  • (1,2,2,0)

Sample Input 2

1000000000

Sample Output 2

1755648