2020 South Central USA Regional Contest

Start

2021-03-06 10:00 AKST

2020 South Central USA Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -103 days 18:58:28

Time elapsed

5:00:00

Time remaining

0:00:00

Problem L
Rainbow Numbers

Define a rainbow number as an integer that, when represented in base $10$ with no leading zeros, has no two adjacent digits the same.

Given lower and upper bounds, count the number of rainbow numbers between them (inclusive).

Input

The first line of input contains a single integer $L$ ($1 \le L < 10^{10^5}$), which is the lower bound.

The second line of input contains a single integer $U$ ($1 \le U < 10^{10^5}$), which is the upper bound.

It is guaranteed that $L \le U$. Note that the limits are not a misprint; $L$ and $U$ can be up to $10^5$ digits long.

Output

Output a single integer, which is the number of rainbow numbers between $L$ and $U$ (inclusive). Because this number may be very large, output it modulo $998\, 244\, 353$.

Sample Input 1 Sample Output 1
1
10
10
Sample Input 2 Sample Output 2
12345
65432
35882