John's Math Problem

Time limit1sMemory limit1024 MB

Summary

Given an integer N, sum the values of every number formed by deleting zero or more digits (subsequences), counting duplicates once per way, modulo 998244353.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Farmer John, given his line of work, makes many math problems. This one is a simple math problem. You have to solve it.

You are given an integer $N$ . You may remove zero or more digits from $N$ and concatenate the remaining digits in order to form a new number. You cannot remove every digit.

For example, if $N = 121$ , the new numbers you can form are 1, 2, 11, 12, 21, and 121.

Find the sum of all new numbers you can form.

Input

An integer $N$ is given. $N$ does not begin with 0.

Output

Print the sum of all new numbers you can form, modulo $998\,244\,353(=119\cdot2^{23}+1)$ . If a number can be formed in several ways, add it once for each way, and ignore leading zeros when adding. For example, when $N = 1\,101$ , the number 11 must be added 3 times, and the value to print is $1\,581$ .

Constraints

$1 \le N < 10^{250\,000}$

Examples2

Example 1
Input
```
7
```
Expected output
```
7
```
Example 2
Input
```
31
```
Expected output
```
35
```