EOJ Monthly 2020.7 Sponsored by TuSimple

D. 前缀排序

单点时限: 2.0 sec

内存限制: 256 MB

Cuber QQ 正在研究方氏数论。方氏数论主要探讨的课题是正整数拼接时产生的奇妙反应。今天,他遇到了一个难题。

Cuber QQ 得到了一个长度为 $n$ 正整数,接着,Cuber QQ 会取出它的 $n$ 个长度不同的非空前缀,分别组成 $n$ 个不同的正整数。例如,四位数 $1234$ 中能提取出四个前缀,分别为 $1$、$12$、$123$ 和 $1234$。

Cuber QQ 想知道,这 $n$ 个前缀经过自由调换顺序并首尾拼接可以获得的最大正整数是多少,例如,四位数 $1234$ 的四个前缀能拼成的最大正整数为 $1234123121$。由于答案会很大,你需要输出答案对 $998244353$ 取模的结果。

输入格式

一行,一个 $n$ 位正整数($1\le n \le 10^5$)。

输出格式

一行,一个正整数,表示答案对 $998244353$ 取模的结果。

样例

Input
12345
Output
351476317
Input
114514
Output
266269731

提示

$114514$ 共有六个非空前缀,分别为 $114514$、$11451$、$1145$、$114$、$11$ 和 $1$,他们排列拼接可以获得的最大正整数为 $114514~1145~11451~114~11~1$,对 $998244353$ 取模的结果为 $266269731$。