Problem Statement

The Fibonacci sequence $\{F_i\}$ is the sequence defined by $F_0 = F_1 = 1, \ F_{i+2} = F_{i+1} + F_i \ (i \geq 0)$. A number contained in the Fibonacci sequence is called a Fibonacci number.

Find the number, modulo $10^9+7$, of positive integers $M$ satisfying all of the following. Here, the number of digits and so on are all considered in base 10.

• The number of digits of $M$ is at most $N$.
• When $M$ is viewed as a string, none of its contiguous substrings, taken as a number, is a Fibonacci number between $L$ and $R$, inclusive.

For example, $M=1305$ contains the Fibonacci numbers $1,3,5,05,13$ as contiguous substrings. ($05$ is equivalent to $5$.)

Input

$N\ L\ R$

• All inputs are integers.
• $1 \leq N \leq 5000$
• $1 \leq L \leq R \leq 10^{18}$

Output

Output the number of $M$ satisfying the conditions, modulo $10^9+7$.

Sample

1 1 9

4

2 2 2

80

100 123 456789101112

629926418