We are going to consider subsets of a given set .
We are interested in subsets such that for a given natural number and for
any natural number at least one of the numbers , doesn't belong to .
We would like to calculate the number of such subsets, that have exactly elements.
It is possible that the number of such subsets is huge - therefore it is sufficient to calculate the remainder of the division
of the result by .
Write a program which:
reads from the standard input four integers: , , and ,
calculates the remainder of the division by of the number of -element subsets of set , that fulfill
the requirements described above,
writes result to the standard output.
In the first and only line of the standard input there are four integers , , and (,
), separated by single spaces.
The first and only line should contain one integer - the reminder of the division by of the number of -element subsets
of set that fulfill the specified requirements.