V

Zvonko는 또 숫자를 가지고 놀고 있다. 수학을 너무 많이 하니 밖에 나가 친구들과 놀라고 엄마가 잔소리를 했는데도 말이다.

최근의 놀이에서 Zvonko는 특정 숫자들로만 이루어진, 정수 \(D\)의 배수를 찾는다. \(D\)의 배수란 \(D\)로 나누어떨어지는 수를 말한다.

Zvonko의 재미를 망치기 위해, 엄마는 이 문제를 푸는 프로그램을 구하기로 했다. \(A\) 이상 \(B\) 이하의 \(D\)의 배수 중에서, 십진법으로 썼을 때 허용된 특정 숫자들만 포함하는 수가 몇 개인지 계산하는 프로그램을 작성하시오.

입력의 첫째 줄에 세 정수 \(D\), \(A\), \(B\) (\(1 \le D \le 10\,000\), \(1 \le A \le B \le 10^{10}\))가 주어진다. 둘째 줄에 허용된 숫자들이 주어진다. 숫자들은 공백 없이, 오름차순으로, 중복 없이 주어진다.

Zvonko가 만들 수 있는 배수의 개수를 한 줄에 출력한다.

riseoj 작성

출처 COCI 2006/2007 Contest 6