P12047 [USTCPC 2025] 翻转数字

考虑到评测机性能差异，改为 2.5s 时限。USTCPC 时限为 3s。 克露丝卡尔酱喜欢车万！ 鬼人正邪（きじん せいじゃ）是东方 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$： $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$。