Rainbow Numbers

Time limit1sMemory limit512 MB

Summary

Count integers between two huge bounds (up to 100000 digits) whose decimal digits never repeat consecutively, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

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

Given a lower bound and an upper bound, count the rainbow numbers between them, inclusive.

Input

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

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

It is guaranteed that $L \le U$ . The bounds are not a misprint; $L$ and $U$ can have up to $10^5$ digits.

Output

Print a single integer, the number of rainbow numbers between $L$ and $U$ inclusive. This number can be very large, so print it modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
1
10
```
Expected output
```
10
```
Example 2
Input
```
12345
65432
```
Expected output
```
35882
```