Given an integer ~N~, determine the number of ways to roll ~N~ six-sided die such that the product of the numbers rolled is divisible by the sum of the numbers rolled. Rolls are ordered (e.g. rolling a ~1~ and then a ~2~ would be distinct from rolling a ~2~ and then a ~1~). Since the answer may be huge, output its value modulo ~998244353~.

Constraints

~1 \le N \le 10^5~

Subtask 1 [10%]

~1 \le N \le 6~

Subtask 2 [20%]

~1 \le N \le 20~

Subtask 3 [30%]

~1 \le N \le 100~

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains one integer, ~N~.

Output Specification

Output one line containing one integer, the number of ordered ways to roll ~N~ six-sided die such that the product of the numbers rolled is divisible by the sum of the numbers rolled, modulo ~998244353~.

Sample Input 1

2

Sample Output 1

5

Explanation for Sample 1

The ~5~ valid rolls of ~2~ six-sided die are ~(2,2)~, ~(3,6)~, ~(4,4)~, ~(6,3)~, and ~(6,6)~. It can be shown that these are the only ways to roll ~2~ six-sided die so that the product of the numbers rolled is divisible by the sum of the numbers rolled.

Sample Input 2

66666

Sample Output 2

537825222

Explanation for Sample 2

Remember to output the answer modulo ~998244353~.