369 Game Count

Time limit1sMemory limit256 MB

Summary

Count numbers from A to B that are multiples of 3 or contain the digit 3, 6, or 9, and output the count modulo 20150523.

Level: Medium7 of 10
Topics: Dynamic programming, String, Math
Solved: No attempts yet

Problem

여러 사람이 둘러 앉아 즐기는 369 게임은 다음과 같은 규칙을 가지고 있다. 규칙: 양의 정수 A에서 시작하여 차례로 사람들 이 돌아가면서 숫자를 하나씩 증가하면서 불러 나간다. 단, 부르는 숫자가 3의 배수이거나 그 숫자에 3, 6, 9중 하나라도 들어 있는 경우에 숫자는 부르지 않고 박수를 친다.

예를 들어, 369 게임을 17부터 시작하는 경우를 생각해보자. 박수를 X로 표현하면, 이 게임의 진행은 17-X-X-20-X-22-X-X-25–X–X-28-X-X …과 같을 것이다.

시작하는 양의 정수 A와 끝나는 양의 정수 B가 주어졌을 때, 박수를 치는 총 횟수를 구하는 프로그램을 작성하시오.

Input

한 줄에 시작하는 양의 정수 A와 끝나는 양의 정수 B가 순서대로 주어진다. 두 수의 범위는 1≤ A ≤ B ≤ 10100,000이다.

Output

박수치는 총 횟수를 20,150,523으로 나눈 나머지를 출력한다.

Examples4

Example 1
Input
```
1 12
```
Expected output
```
4
```
Example 2
Input
```
29 39
```
Expected output
```
11
```
Example 3
Input
```
12345 123456789
```
Expected output
```
17517670
```
Example 4
Input
```
17 39
```
Expected output
```
18
```