Story

Yu-san is a researcher studying parallel worlds, but today he is taking a day off and chatting leisurely with you, his assistant.

"All right, here's a problem. Among the positive integers up to $10$ oku (one billion), how many do not contain the number I hate, that is, 404?"

You found that tedious, so you tried to have a machine compute it.

While you were writing the code, Yu-san caught you. Then he said this:

"Hey, that's not allowed.... Ah, no, actually, you may use it. But if you're using a machine, $10$ oku (one billion) is too small, right? You can surely handle about this much."

Problem Statement

Find the number of positive integers less than or equal to $N$ that satisfy the following condition.

• When its decimal representation is interpreted as a string, no substring of $3$ consecutive characters is 404

Since the answer can be very large, output it modulo $998244353$.

Also, note that the given value of $N$ can be extremely large.

Input

$N$

Constraints

• $1\leq N \leq$ $10^{1000000}$ $=$ $10^{10^6}$
• All inputs are integers

Output

Output the answer on one line, followed by a newline.

Sample

1000

999

98765432109876543210

848152577