题目描述

光头强闲来无事就自己定义了一类有趣的数。

如果一个正整数满足在 $B_1$ 进制下的位数是 $D_1$，而且在 $B_2$ 进制下的位数是 $D_2$，光头强就认为他是一个有趣的数。

现在光头强想知道满足要求的数一共有多少个。

光头强为了不为难你，他只需要你考虑所有不超过 $10^{18}$ 的数是不是有趣的。换句话说，光头强认为所有大于 $10^{18}$ 的数都是不有趣的。

输入格式

输入数据包含一行，四个整数，分别是 $B_1,D_1,B_2,D_2(2\leq B_1,B_2 \leq 100, 1\leq D_1,D_2 \leq 20)$，意义如题面所述。

输出格式

输出一行包含一个整数，表示答案。

测试样例

3 1 5 1

2

10 2 2 4

6