AT_kupc2021_m.Formula

我们考虑由 $1$、$2$、$3$、$4$、$5$、$6$、$7$、$8$、$9$、+、* 这 $11$ 种字符组成、长度为 $N$ 的字符串。

这样的字符串共有 $11^N$ 种可能，但请你求出其中所有作为合法表达式成立的字符串的计算结果之和，并对 $998244353$ 取模。

这里，字符串 $S$ 被认为是合法表达式需满足：

• $S$ 的首尾字符都不能是 + 或 *；
• 从 $S$ 中任取连续的 $2$ 个字符，至少有一个不是 + 或 *。

此外，表达式中的整数均为十进制表示，表达式的计算遵循普通的四则运算规则。例如，字符串 22+3*4 的计算结果为 $34$。

输入通过标准输入给出，格式如下：

$N$

请输出答案，结果对 $998244353$ 取模。

限制

• $1 \leq N \leq 10^{18}$
• 输入均为整数。

样例解释 1

所有可能的字符串为 1、2、3、4、5、6、7、8、9 共 $9$ 种，每个的计算结果分别为 $1,2,3,4,5,6,7,8,9$，因此答案为这些数的和 $45$。

样例解释 2

合法表达式的例子有 239、2+5、5*8 等。

由 ChatGPT 4.1 翻译