You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

克露丝卡尔酱喜欢车万！

鬼人正邪（きじん せいじゃ）是东方 Project 系列中的角色，首次登场于《东方辉针城 ～ Double Dealing Character.》（第 14 作）。她是来自妖怪之山的天邪鬼，种族特性为天生喜欢与人作对、颠覆常理的「反逆者」，拥有「颠覆事物性质程度的能力」（如让弹幕反转、规则倒错）。在《辉针城》中，她策划了「下克上异变」，赋予道具自主意识反抗主人，意图颠覆妖怪世界的等级制度。其能力可令弹幕方向/判定反转，战斗中需要玩家逆向操作。

一天，正邪在 USTC 1958 咖啡馆引发了异变。咖啡馆内排列着一串以数字 $1$、$9$、$5$、$8$、$0$ 为形状的装饰气球，原本它们是降序排列的，即 $99\dots988\dots855\dots511\dots100\dots0$。但是在异变的影响下，它们的顺序完全被打乱了(即数据随机生成)，并且你只能以翻转相邻两个气球的形式将气球进行重排。由于 $5$、$9$ 的不对称性，显然将气球完全恢复到初始状态是不大可能的。你想要尽量将气球恢复有序，即找到一个可以通过原串操作得到的最大的数字串，并且没有气球是颠倒的(即 $5$、$9$ 在最终状态没有被翻转奇数次)。更进一步地，你想要对原数字串的每个子串都求出这一答案。

题目描述

形式化地，定义一个数字串为 $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$。保证数据随机生成且生成各数字的概率相等。

输入格式

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

输出格式

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

样例

#1 输入

1958

#1 输出

10695

解释

$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$。

#2 输入

0595588119519515955880115851881598599518850811185891881850801018159809101088511509958819091819010858

#2 输出

784814030

友情提示

本题时限已开至 std 两倍，不卡常；本题五个数据点串长分别为 $20,100,300,10000,50000$，选手可以利用前四个测试点验证一些想法的正确性。