E. Reliable Piglet
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To verify whether the piglet is a reliable intermediate-level competitive programmer, Little L gives him the following problem.

Every positive integer $$$x$$$ can be uniquely written as $$$\overline{d_md_{m-1}\cdots d_0}$$$, satisfying all of the following conditions:

  • $$$x=\sum\limits_{i=0}^m10^id_i$$$.
  • $$$1\le d_m\le9$$$.
  • For all $$$i\in\{0,1,\cdots,m-1\}$$$, $$$0\le d_i\le9$$$.
We say that the positive integer $$$x$$$ is good if and only if it satisfies the following two conditions:
  • None of $$$2,3,5,7$$$ is a divisor of $$$x$$$.
  • For all $$$i\in\{0,1,\cdots,m-3\}$$$, at least one of the following holds: $$$d_{i+3}\ne2$$$, $$$d_{i+2}\ne0$$$, $$$d_{i+1}\ne2$$$, $$$d_i\ne5$$$.
Let $$$f(x)$$$ be a function defined on positive integers. If $$$x$$$ is good, then $$$f(x)=2025^x$$$; otherwise, $$$f(x)=0$$$.

Given positive integers $$$L$$$ and $$$R$$$ ($$$L\le R$$$), compute $$$\left(\sum\limits_{i=L}^Rf(i)\right)\bmod(10^9+7)$$$.

Input

The input consists of a single line containing two integers $$$L,R$$$ ($$$1\le L\le R\le10^{202512}$$$).

Output

Output a single integer, the value of $$$\left(\sum\limits_{i=L}^Rf(i)\right)\bmod(10^9+7)$$$.

Examples
Input
20249 20257
Output
935315683
Input
1 20252025202520252025
Output
423849977
Note

In the first example, only $$$20249$$$ is good, and $$$2025^{20249}\bmod(10^9+7)=935315683$$$.