Description

给定正整数 $k,l,r$，求区间 $[l,r]$ 中数位积为 $k$ 的倍数（注意 $0$ 是任何数的倍数）的数的个数对 $10^9+7$ 取模。

注：数位积指的是一个数所有位置上的数的乘积，例如 $114514$ 的数位积为 $80$。

Input Format

一行三个正整数 $k,l,r$。

Output Format

一个整数，表示答案。

5 1 20

4

5 50 100

19

15 11 19

0

Hint

数据范围

$1\le k\le 10^{17}$，$1\le l\le r\le 10^{20}$。