单点时限: 1.0 sec
内存限制: 512 MB
Cuber QQ 闲来无事就自己定义了一类有趣的数。
如果一个正整数满足在 $B_1$ 进制下的位数是 $D_1$ ，而且在 $B_2$ 进制下的位数是 $D_2$ ，Cuber QQ 就认为他是一个有趣的数。
现在 Cuber QQ 想知道满足要求的数一共有多少个。
Cuber QQ 为了不为难你，他只需要你考虑所有不超过 $10^{18}$ 的数是不是有趣的。换句话说，Cuber QQ 认为所有大于 $10^{18}$ 的数都是不有趣的。
输入数据包含一行，四个整数，分别是 $B_1,D_1,B_2,D_2$ ($2\le B_1,B_2\le 100,1\le D_1,D_2\le 20$) ，意义如题面所述。
输出一行包含一个整数，表示答案。
3 1 5 1
2
10 2 2 4
6