[HNOI2002] 彩票

题目描述

某地发行一套彩票。彩票上写有 $1$ 到 $M$ 这 $M$ 个自然数。彩民可以在这 $M$ 个数中任意选取 $N$ 个不同的数打圈。每个彩民只能买一张彩票,不同的彩民的彩票上的选择不同。 每次抽奖将抽出两个自然数 $X$ 和 $Y$。如果某人拿到的彩票上,所选 $N$ 个自然数的倒数和,恰好等于 $\dfrac{X}{Y}$,则他将获得一个纪念品。 已知抽奖结果 $X$ 和 $Y$。现在的问题是,必须准备多少纪念品,才能保证支付所有获奖者的奖品。

输入输出格式

输入格式


输入文件有且仅有一行,就是用空格分开的四个整数 $N$,$M$,$X$,$Y$。

输出格式


输出文件有且仅有一行,即所需准备的纪念品数量。

输入输出样例

输入样例 #1

2 4 3 4

输出样例 #1

1

说明

$1 \leq X, Y \leq 100$,$1 \leq N \leq 10$,$1 \leq M \leq 50$。 输入数据保证输出结果不超过 $10^5$。