题目描述

使用给定的数字，组成一些在 $[A,B]$ 之间的数使得这些数每个都能被 $X$ 整除。

输入格式

输入第一行包含三个整数 $X,A,B$。

第二行为一个数字串，表示可以使用的数字。一个数字可以使用多次，数字不会重复出现。

输出格式

输出一行一个整数，表示在 $[A,B]$ 这个区间用这些给定的数字能组成多少个被 $X$ 整除的数字。

2 1 20
0123456789

10

6 100 9294
23689

111

5 4395 9999999999
12346789

0

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1\le X\lt 10^{11}$，$1\le A\le B\lt 10^{11}$。

说明

题目译自 COCI2006-2007 CONTEST #6 T5 V。