Lottery Reciprocal Sum

A lottery is issued with numbers written from \(1\) to \(M\). Each lottery ticket has \(M\) natural numbers, and a player can select any \(N\) distinct numbers among them and circle those numbers. Each lottery ticket is unique so that no two players choose the same combination.

During each draw, two natural numbers \(X\) and \(Y\) are drawn. A player wins a souvenir if the sum of the reciprocals of the \(N\) numbers he selected exactly equals \(\frac{X}{Y}\) (in \(\LaTeX\) format).

Given the lottery parameters and the drawn fraction \(\frac{X}{Y}\), your task is to determine how many souvenirs must be prepared so that every winning ticket can be rewarded.

Note: You are given four positive integers: \(M\), \(N\), \(X\), and \(Y\). You need to count the number of ways to choose \(N\) distinct numbers from \(\{1,2,\dots,M\}\) such that:

\[ \frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_N} = \frac{X}{Y} \]

inputFormat

The input consists of a single line with four positive integers \(M\), \(N\), \(X\), and \(Y\) separated by spaces. Here, \(M\) is the maximum number on the ticket, \(N\) is the number of numbers chosen by each player, and \(\frac{X}{Y}\) is the fraction drawn.

outputFormat

Output a single integer that represents the number of winning tickets, i.e. the count of \(N\)-element subsets from \(\{1,2,\dots,M\}\) whose reciprocal sum is exactly \(\frac{X}{Y}\).

sample

10 2 3 2

1

</p>