Birthday Numbers II

Time limit1sMemory limit256 MB

Summary

Add up the products of every neighboring pair among the integers between x and y that use only the digits 3, 5 and 8, and report the total modulo 19980305.

Level: Hard8 of 10
Topics: Math, Recursion, Combinatorics, String
Solved: No attempts yet

Problem

Seunghyun was born on March 5, 1998, so he is very fond of the digits 3, 5 and 8 that appear in his birth date. He decided to call a positive integer a birthday number when its decimal representation consists of the digits 3, 5 and 8 only. For example, 3, 533 and 858553 are birthday numbers, while 3518, 1642 and 88808 are not.

You are given two birthday numbers $x$ and $y$ ( $x < y$ ). List every birthday number that is at least $x$ and at most $y$ in increasing order as $a_1, a_2, \dots, a_k$ , and write a program that computes $a_1 \times a_2 + a_2 \times a_3 + \cdots + a_{k-1} \times a_k$ . Handling huge numbers is always a bother, so print the value modulo $19980305$ , which is Seunghyun's birth date.

Input

The first line contains $x$ and the second line contains $y$ . Neither line contains any character other than '3', '5' and '8'. ( $x < y \le 10^{200000}$ )

Output

Print $a_1 \times a_2 + a_2 \times a_3 + \cdots + a_{k-1} \times a_k$ modulo $19980305$ on the first line.

Examples2

Example 1
Input
```
3
8
```
Expected output
```
55
```
Example 2
Input
```
33
8353
```
Expected output
```
3179909
```