Serious Business

Time limit3sMemory limit1024 MB

Summary

Count the integers in [L, R] whose number of even-digit-sum contiguous substrings is odd, modulo 998244353, with R up to 100000 digits.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum, String, Math
Solved: No attempts yet

Problem

As the proprietor of a Serious Business, you handle a lot of serial numbers. Each gadget, gizmo, and thingamajig you manufacture has a unique serial number. Each serial number is a sequence of decimal digits with no leading zeros.

You are extremely superstitious, however, and you only put lucky serial numbers on your products. A serial number is lucky if it has an odd number of scary contiguous substrings. A contiguous substring is scary if the sum of its digits is even.

An auditor asked how many gadgets, gizmos, and thingamajigs you manufactured last year, but you cannot remember. You only know that every serial number you used was between $L$ and $R$ inclusive (interpreted as decimal numbers), and that you used every lucky serial number in that range. How many such serial numbers are there? Since the answer may be very large, output it modulo the prime $998\,244\,353$ .

Input

There are two lines of input. The first contains $L$ and the second contains $R$ , which are integers with no leading zeros. It is guaranteed that $1 \leq L \leq R < 10^{100\,000}$ .

Output

Output a single integer, the number of lucky serial numbers between $L$ and $R$ , modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
1
9
```
Expected output
```
4
```
Example 2
Input
```
1
99
```
Expected output
```
94
```