This problem was featured from DMOJ's Wesley Anger Contest 4 and has been transferred to this site. The time limit has been rescaled by a factor of 3 from the official time limit. If there are any concerns regarding a specific problem's time limit, please contact the administrators. Due to these changes, some of these problems may not be doable in specific languages due to the time limit cap.

The squirrels have invented a new way to communicate with each other! The process of sending and receiving messages requires the almighty acorn, which is said to have a string of infinite length written on its surface (don't question how it works, they don't know either). Interestingly, the almighty acorn's string consists of the concatenation of all positive integers in base \(10\). The string begins as follows:

\(123456789101112131415\dots\)

Sending messages is straightforward, but the squirrels haven't set up the decoder yet! Decoding the message is simple: it is the \(1\)-based position of the message's leftmost occurrence in the string, modulo \(998\,244\,353\).

You have been tasked by the squirrels to be their decoder. Given a message \(S\), please determine and output the position.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

\(1 \le |S| \le 10\,000\)

Subtask 1 [6%]

\(1 \le |S| \le 3\)

Subtask 2 [23%]

\(1 \le |S| \le 300\)

Subtask 3 [71%]

No additional constraints.

Input Specification

The first and only line contains a string \(S\) consisting of only characters from \(0\) to \(9\).

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output an integer representing the leftmost position of the string \(S\) in the almighty acorn's string, modulo \(998\,244\,353\).

Sample Input 1

45

Sample Output 1

4

Sample Explanation 1

As denoted by the string, 45 first appears at 123[45]678..., making the position \(4\).

Sample Input 2

0111

Sample Output 2

11

Sample Explanation 2

\(S\) can have leading zeroes. In the string, it is located at 1234567891[0111]2..., making the position \(11\).