F - Cube Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

立方体の各面に 1 つずつ正の整数を書きます。書かれた 6 つの数の和が S になるような書き込み方は何通りありますか？

ただし、立方体を回転した時に一致するような書き込み方は区別しないものとします(数に向きはありません)。

答えは非常に大きくなる可能性があるので、998244353 で割ったあまりを求めてください。

制約

  • 6 \leq S \leq 10^{18}
  • S は整数

入力

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

S

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

8

出力例 1

3

書かれた 6 つの数が (1,1,1,1,1,3) であるような書き込み方が 1 通り、(1,1,1,1,2,2) であるような書き込み方が 2 通り (2 が書かれた面が隣り合うものと反対側に配置されるもの) の、計 3 通りの書き込み方があります。

入力例 2

9

出力例 2

5

入力例 3

50

出力例 3

80132

入力例 4

10000000000

出力例 4

2239716

答えを 998244353 で割ったあまりを求めてください。

Score : 600 points

Problem Statement

Let us write a positive integer on each face of a cube. How many ways are there to do this so that the sum of the six numbers written is S?

Here, two ways to write numbers are not distinguished when they only differ by rotation. (Numbers have no direction.)

The count can be enormous, so find it modulo 998244353.

Constraints

  • 6 \leq S \leq 10^{18}
  • S is an integer.

Input

Input is given from Standard Input in the following format:

S

Output

Print the count modulo 998244353.

Sample Input 1

8

Sample Output 1

3

We have one way to write 1,1,1,1,1,3 on the cube and two ways to write 1,1,1,1,2,2 (one where we write 2 on adjacent faces and another where we write 2 on opposite faces), for a total of three ways.

Sample Input 2

9

Sample Output 2

5

Sample Input 3

50

Sample Output 3

80132

Sample Input 4

10000000000

Sample Output 4

2239716

Find the count modulo 998244353.