题目描述

某地的车牌号由一串纯数字组成。小 Y 认为一个正整数是"幸运车牌号"，当且仅当它同时满足：

1. 它的十进制表示中不出现数字 $d$；
2. 它各位数字之和是 $m$ 的倍数。

给定 $L,R,m,d$，请你统计区间 $[L,R]$ 内幸运车牌号的个数。

输入格式

一行四个整数 $L,R,m,d$。

输出格式

一行一个整数，表示幸运车牌号的个数。

输入输出样例 #1

输入 #1

1 20 3 4

输出 #1

6

说明

【样例解释】

$[1,20]$ 中不含数字 $4$、且各位数字之和是 $3$ 的倍数的数有 $3,6,9,12,15,18$，共 $6$ 个。

【数据范围】

数据范围

• 对于 $100\%$ 的数据，$1\le L\le R\le 10^{18}$，$2\le m\le 20$，$0\le d\le 9$。