题目描述

小杨正在整理一批正整数编号。对于一个编号 $x$，若它的各位数字之和能够被 $k$ 整除，并且数字 $d$ 在 $x$ 的十进制表示中恰好出现一次，则称 $x$ 为合格编号。给定区间 $[L,R]$、整数 $k$ 和数字 $d$，请计算区间内合格编号的个数。

输入格式

输入一行，包含四个整数 $L$、$R$、$k$、$d$，含义如题目描述。

输出格式

输出一个整数，表示区间 $[L,R]$ 内合格编号的个数。

样例

20 40 3 3

3

98 125 5 0

2

样例解释

样例 $1$ 中，$30$、$36$、$39$ 的数位和能被 $3$ 整除，且数字 $3$ 恰好出现一次，因此答案为 $3$。

样例 $2$ 中，$104$ 与 $109$ 满足条件，因此答案为 $2$。

数据范围

$1 \le L \le R \le 1000000$，$R-L \le 100000$，$2 \le k \le 9$，$0 \le d \le 9$。

所有输入均为整数。