Problem Statement

Given is a string S consisting of digits from 1 through 9.
From this string S, let us make a formula T by the following operations.

• Initially, let T=S.
• Choose a (possibly empty) set A of different integers where each element is between 1 and |S|-1 (inclusive).
• For each element x in descending order, do the following.
• Insert a + between the x-th and (x+1)-th characters of T.

For example, when S= 1234 and $A= \lbrace 2,3 \rbrace$, we will have T= 12+3+4.
Consider evaluating all possible formulae T obtained by these operations. Find the sum, modulo 998244353, of the evaluations.

Input

Input is given from Standard Input in the following format:
S

Output

Print the answer.

Constraints

• $1 \le |S| \le 2 \times 10^5$
• S consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

1234

Sample Output 1

1736

There are eight formulae that can be obtained as T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is 1736.

Sample Input 2

1

Sample Output 2

1

S may have a length of 1, in which case the only possible choice for A is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo 998244353.

见题面 Input 部分

见题面 Output 部分