题目描述

学校为编号从 $1$ 到 $N$ 的学生制作数字徽章。

若一个编号的十进制表示中至少出现一次数字 $D$，并且它的各位数字之和能被 $K$ 整除，则称该编号为“合格编号”。

请统计 $1$ 到 $N$ 中共有多少个合格编号。

输入格式

输入一行三个整数 $N$、$K$、$D$，相邻整数之间用一个空格分隔。

输出格式

输出一个整数，表示合格编号的数量。

样例

30 3 2

4

20 1 0

2

样例解释

样例 $1$ 中，满足条件的编号为 $12$、$21$、$24$、$27$，共 $4$ 个。

样例 $2$ 中，$K=1$，因此数位和条件恒成立；$1$ 到 $20$ 中含有数字 $0$ 的编号为 $10$ 和 $20$。

数据范围

$1 \le N \le 100000$。

$1 \le K \le 9$。

$0 \le D \le 9$。