C. 数码管
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

有一组坏掉的、只能显示 0, 2, 5, 6, 8, 9 的 n 位十进制数码管，记这组数码管从左到右读出的十进制数为 A（允许有前导零）。

由于失误，这组数码管被整体旋转了 180 度，记现在选转过来的数码管从左到右读出的十进制数为 B（允许有前导零）。

比如，原先 A = 025689，现在 B = 689520；原先 A = 66559，现在 B = 65599；原先 A = 02500，现在 B = 00520。

A = 025689，B = 689520

现在希望你帮忙计算一下，有多少种方案，使得数码管旋转前和旋转后的读数相同，即 A = B。由于答案很大，请你给出答案模 998, 244, 353 的值。

Input

一行，一个正整数 n (1 ≤ n < 10105)。

Output

一个非负整数，为答案模 998, 244, 353 的值。

Examples
Input
1
Output
4
Input
2
Output
6
Input
3
Output
24
Input
101
Output
23811823
Input
99999999999999999999999999999999
Output
648334277
Note

第一个样例中，数码管读出的数可能为 {0, 2, 5, 8}。

第二个样例中，数码管读出的数可能为 {00, 22, 55, 69, 88, 96}。