UT Invitational Programming Contest 2019


2019-05-04 10:00 AKDT

UT Invitational Programming Contest 2019


2019-05-04 15:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 16:12:28

Time elapsed


Time remaining


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$.


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 a single integer, the number of lucky serial numbers between $L$ and $R$, modulo $998\, 244\, 353$.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2