UT Invitational Programming Contest 2019

Start

2019-05-04 18:00 UTC

UT Invitational Programming Contest 2019

End

2019-05-04 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -192 days 0:23:49

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Serious Business

As the proprietor of a Serious Business, you deal with 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 use lucky serial numbers on your products. A serial number is said to be 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 has asked how many gadgets, gizmos, and thingamajigs you manufactured last year, but you can’t remember! All you know is that all the serial numbers you used were between $L$ and $R$ inclusive (when 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 its remainder 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$.

Sample Input 1 Sample Output 1
1
9
4
Sample Input 2 Sample Output 2
1
99
94