题目背景

搬运自 Code+ #8 决赛。

题目描述

小 r 和小 z 厌倦了传统的报数游戏——几个人轮流报数，规定凡是 $7$ 的倍数以及数字中含有 $7$ 的数都不能报。“这也太容易了吧！谁还不会算个 $7$ 的倍数啊。”

于是他们打算把游戏加强。一个比较广为人知的加强是“不能报出所有含有 $7$ 的数的倍数”，不过这次他们打算玩点更有意思的。

小 z 说，可以把 $7$ 改成任意正整数 $a$ ，要求报出的数 $x$ 不能是 $a$ 的倍数，同时不能包含 $a$ （即如果把 $x$ 和 $a$ 都将其不含前导 $0$ 的十进制形式写成字符串，则 $x$ 不能以 $a$ 为子串，下文中“前缀”“后缀”的表述也是类似的含义）。

小 r 说，“不能是 $a$ 的倍数”还是太弱，不妨我们改成 $x$ 的每个非空前缀都不能是 $a$ 的倍数吧。

小 z 紧接着说，既然都考虑前缀了，那为什么不顺便考虑后缀？

小 r 最后说，这几个条件用到的都是同一个 $a$ ，还是不够有意思，不如换成 $3$ 个数 $a,b,c$ 吧。

于是他们最终制定好了规则：一个数 $x$ 能被报出当且仅当：$x$ 当中不包含 $a$ ，并且 $x$ 的任意一个非空前缀都不是 $b$ 的倍数，并且 $x$ 的任意一个非空后缀都不是 $c$ 的倍数。

最后，他们打算看一下这个规则到底好不好玩——于是他们叫上了全程吃瓜的你。给定正整数 $l,r,a,b,c$，你需要计算 $[l,r]$ 范围内的正整数有多少个是按照上述规则能被报出来的。

输入格式

输入共一行，$5$ 个正整数 $l,r,a,b,c$。

输出格式

输出共一行，一个非负整数表示答案。

20 31 5 3 7

4

12345 999999 121 66 233

815118

提示

【样例 #1 解释】

$[20,31]$ 中，不包含 $5$、非空前缀不含 $3$ 的倍数、非空后缀不含 $7$ 的倍数的共有以下 $4$ 个：$22、23、26、29$。其他的数均不符合条件，例如 $0$ 是 $20$ 的非空后缀且为 $7$ 的倍数。

【数据范围】

对于所有的数据，满足 $1 \leq l \leq r \leq 10^{18}, 1 \leq a \leq 10^9, 2 \leq b,c \leq 300$ 。

子任务 $1$ （$15$ 分）：$r \leq 10^6$。

子任务 $2$ （$10$ 分）：$a, b, c \leq 9$。

子任务 $3$ （$15$ 分）：$c \leq 15$。

子任务 $4$ （$15$ 分）：$b,c \leq 50$。

子任务 $5$ （$15$ 分）：$b=c$。

子任务 $6$ （$10$ 分）：$c$ 与 $10$ 互质。

子任务 $7$ （$20$ 分）：无特殊性质。