생일수 II Batch Compilation commands

승현이는 1998년 3월 5일에 태어났습니다. 그래서 승현이는 자신의 생년월일에 있는 수들 중에서 3, 5, 8을 굉장히 좋아합니다. 이에 승현이는 10진수로 표현했을 때 3, 5, 8로만 구성되어 있는 자연수를 '생일수'로 부르기로 했습니다. 예로 들어 3, 533, 858553은 생일수이지만, 3518, 1642, 88808은 생일수가 아닙니다.

여러분에게 두 생일수 $x$와 $y$ ($x < y$)가 주어졌습니다. $x$ 이상 $y$ 이하의 서로 다른 모든 생일수들을 오름차순으로 나열한 수열을 $a_{1}, a_{2}, \cdots , a_{k}$로 둘 때, $a_{1} \times a_{2} + a_{2} \times a_{3} + \cdots + a_{k-1} \times a_{k}$의 값을 구하는 프로그램을 작성하세요. 큰 수를 처리하기는 언제나 귀찮으므로, 승현이의 생일인 $19980305$로 나눈 나머지를 출력하도록 합시다.

입력 형식

첫 번째 줄에 $x$, 두 번째 줄에 $y$가 주어집니다. 각 줄에는 '3', '5', '8' 이외의 다른 문자는 주어지지 않습니다.

출력 형식

첫 번째 줄에 $a_{1} \times a_{2} + a_{2} \times a_{3} + \cdots + a_{k-1} \times a_{k}$의 값을 $19980305$로 나눈 나머지를 출력합니다.

서브태스크

서브태스크 1 (10점)

• $x, y \le 10^5.$

서브태스크 2 (15점)

• $x, y \le 10^{10}.$

서브태스크 3 (20점)

• $x, y \le 10^{1000}.$
• $k \le 500.$

서브태스크 4 (25점)

• $x, y \le 10^{200000}.$
• $x$와 $y$를 10진법으로 표현했을 때의 자리수가 서로 같습니다. (즉 $x = 35, y = 888$과 같은 경우는 주어지지 않습니다.)

서브태스크 5 (30점)

• $x, y \le 10^{200000}.$

입력과 출력의 예

예제 1

입력

3
8

출력

55

예제 2

입력

33
8353

출력

3179909