Description

A set of lottery tickets is issued in a certain place. Each ticket displays the $M$ natural numbers from $1$ to $M$. A player may circle any $N$ distinct numbers among these $M$ numbers. Each player can buy only one ticket, and different players choose different sets.

Each draw picks two natural numbers $X$ and $Y$. If, on someone's ticket, the sum of the reciprocals of the $N$ selected natural numbers is exactly equal to $\dfrac{X}{Y}$, then they will receive a souvenir.

Given the draw result $X$ and $Y$, determine how many souvenirs must be prepared to ensure all winners can be awarded.

Input Format

The input contains exactly one line with four integers $N$, $M$, $X$, $Y$ separated by spaces.

Output Format

Output one line with the required number of souvenirs.

2 4 3 4

1

Hint

$1 \leq X, Y \leq 100$, $1 \leq N \leq 10$, $1 \leq M \leq 50$.

The input guarantees the output does not exceed $10^5$.

Translated by ChatGPT 5