考虑一个长度为 $N$、由 11 个字符组成的字符串 $S$：‘1’、‘2’、‘3’、‘4’、‘5’、‘6’、‘7’、‘8’、‘9’、‘+’、‘*’。 如果字符串 $S$ 满足以下条件，我们称其为数学字符串：

• $S$ 的第一个和最后一个字符既不是 ‘+’ 也不是 ‘*’。
• 在 $S$ 中任意两个相邻的字符中，至少有一个字符不是 ‘+’ 或 ‘*’。

每个数学字符串都可以被视为一个使用十进制整数和普通算术运算的算术表达式，其中乘法的优先级高于加法。对于每一个这样的表达式，都可以计算出它的值：例如，数学字符串 “35+2*6” 的值为 47。请计算给定长度 $N$ 的所有数学字符串的值之和，结果对 998 244 353 取模。

输入格式

输入包含一个整数 $N$ ($1 \le N \le 10^{18}$)。

输出格式

输出一个整数：问题的答案。

样例

样例输入 1

1

样例输出 1

45

样例输入 2

3

样例输出 2

407430

样例输入 3

1000000000000000000

样例输出 3

493565653

说明

在样例 1 中，只有 9 个不同的单位数数学字符串：从 ‘1’ 到 ‘9’ 的数字。这些数字作为算术表达式的值之和等于 45。