問題文

フィボナッチ数列 $\{F_i\}$ は、 $F_0 = F_1 = 1, \ F_{i+2} = F_{i+1} + F_i \ (i \geq 0)$ で定義される数列です。 フィボナッチ数列に含まれる数をフィボナッチ数と言います。

次を全て満たす正の整数 $M$ の個数を $10^9+7$ で割った余りを求めてください。ただし桁数等は全て10進法で考えます。

• $M$ の桁数は $N$ 以下である。
• $M$ を文字列として見たときの連続する部分文字列で、数として $L$ 以上 $R$ 以下の フィボナッチ数となるものが存在しない。

例えば $M=1305$ は連続部分文字列としてフィボナッチ数 $1,3,5,05,13$ を含みます。（$05$ は $5$ と等価です）

入力

$N\ L\ R$

• 入力は全て整数
• $1 \leq N \leq 5000$
• $1 \leq L \leq R \leq 10^{18}$

出力

条件を満たす $M$ の個数を $10^9+7$ で割った余りを出力してください。

サンプル

1 1 9

4

2 2 2

80

100 123 456789101112

629926418