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 翻译