Memory limit: 32 MB
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.
For the input data:
6 1234 3 2
the correct result is:
Considered subsets are:
Task author: Jakub Radoszewski.