#P9328. [COCI2006-2007#6] 整除X

[COCI2006-2007#6] 整除X

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

2 1 20
0123456789

样例输出 #1

10

样例 #2

样例输入 #2

6 100 9294
23689

样例输出 #2

111

样例 #3

样例输入 #3

5 4395 9999999999
12346789

样例输出 #3

0

提示

数据规模与约定

  • 对于 100%100\% 的数据,保证 1X<10111\le X\lt 10^{11}1AB<10111\le A\le B\lt 10^{11}

说明

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