Description

形式化地，定义一个数字串为 $0$、$1$、$5$、$8$、$9$、$5^R$、$9^R$ 组成的字符串(允许含有前导零)。数字串的一次翻转操作为：将相邻两个数字 $XY$ 变为 $Y^RX^R$，$^R$ 表示左右颠倒状态。特别地，$0$、$1$、$8$ 由于对称有 $0=0^R$，$1=1^R$，$8=8^R$，$5$、$9$ 翻转两次得到本身，即 $5=5^{RR}\neq 5^R$，$9=9^{RR}\neq 9^R$。不含 $5^R$、$9^R$ 的数字串称为正常数字串。一个正常数字串的权值定义为它通过任意次翻转(中间状态可以不正常)最终得到的最大正常数字串对应的十进制整数。请求出给定正常数字串 $S$ 的所有子串的权值和，答案模 $998244353$。保证数据随机生成且生成各数字的概率相等。

Input Format

一行，代表这个串 $S$。$|S|\leq50000$。

Output Format

一行一个整数，代表答案。

1958

10695

0595588119519515955880115851881598599518850811185891881850801018159809101088511509958819091819010858

784814030

Hint

对于样例 $1$：

$1$、$9$、$5$、$8$、$19$、$95$、$58$、$958$ 权值为其本身。

$195 \rightarrow 15^R9^R \rightarrow 519^R \rightarrow 591$，权值为 $591$。

$1958 \rightarrow 1985^R \rightarrow 189^R5^R \rightarrow 819^R5^R \rightarrow 8915^R \rightarrow 8951$，权值为 $8951$。