Maximum Flipped Substring Sum

We call a string composed only of the characters 0, 1, 5, 8 and 9 a normal digit string (leading zeros are allowed). In addition to the digits themselves, we imagine two extra symbols: 5^R and 9^R, which represent the "flipped" state of 5 and 9 respectively. A flip operation is defined as follows: select two adjacent digits X and Y (which may be in a flipped state) and replace the pair XY with Y^R X^R. Here the operation ^R means that we toggle the flipped state. In particular, the symmetric digits satisfy \[ 0^R=0,\quad 1^R=1,\quad 8^R=8,\] and for the pair 5 and 9 we have \[ 5^R\neq5,\quad 9^R\neq9,\quad 5^{RR}=5,\quad 9^{RR}=9. \] A digit string is said to be normal if it does not contain the symbols 5^R or 9^R – that is, every digit is in its original state.

Starting with a normal digit string S, we are allowed to perform any number of flip operations (even if intermediate strings are not normal) as long as eventually the resulting string is normal. Define the weight of a normal digit string to be the decimal number represented by the lexicographically (numerically) maximum normal string that can be obtained this way.

A key observation is that any flip operation acts on two adjacent positions by swapping them while toggling their flipped state. In order for a digit originally equal to 5 or 9 to appear in the final (normal) string it must be flipped an even number of times. (The symmetric digits 0, 1, and 8 are unchanged by flipping.) It turns out that these operations allow you to reorder the string but with the following constraint: if you re‐index the substring (starting at 1) then the digits that appear in the odd positions come only from positions with even offset (relative to the start of the substring) if originally they belonged to digits which require an even number of flips. More precisely, one may show that in any final normal string obtained from a normal starting string, each digit originally equal to 5 or 9 must remain in the same parity position (when positions are re–numbered from 1). On the other hand, the symmetric digits can be re–arranged arbitrarily. Hence, if you take any substring T of S and re–index it from 1 to its length L, the maximum normal string obtainable from T is given by:

• Separating the substring into two groups: the characters in odd positions and those in even positions.
• Reordering each group in descending order (since the digits are 0, 1, 5, 8, 9 and note 9 > 8 > 5 > 1 > 0).
• Interleaving the two sorted groups so that the odd positions of the final string come from the sorted odd–group and the even positions come from the sorted even–group.

The weight of T is then defined as the decimal integer represented by this final string (possibly with leading zeros). The problem asks you to compute the sum of the weights of all substrings of S modulo 998244353.

Input: A single normal digit string S (each character is one of 0, 1, 5, 8, 9).

Output: Output one integer – the sum of weights of all substrings of S modulo 998244353.

Note: You can assume that the input is generated randomly and each digit appears with equal probability. Moreover, it can be shown that the optimal reordering for a substring T is obtained by sorting the digits at odd positions (i.e. positions 1, 3, 5, … in T) in descending order and sorting the digits at even positions (positions 2, 4, 6, …) in descending order, then interleaving them (placing the odd group digits in odd positions and the even group digits in even positions).

inputFormat

The input consists of a single line containing the normal digit string S.

outputFormat

Output a single integer – the sum of the weights of all substrings of S, taken modulo 998244353.

sample

159

1040