Contest Duration: - (local time) (100 minutes) Back to Home
F - Cube /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

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

制約

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

入力

S


入力例 1

8


出力例 1

3


入力例 2

9


出力例 2

5


入力例 3

50


出力例 3

80132


入力例 4

10000000000


出力例 4

2239716


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.