Subsets [A]
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
.
Task
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.
Input
In the first and only line of the standard input there are four integers
,
,
and
(
,
,
,
), separated by single spaces.
Output
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.
Example
For the input data:
6 1234 3 2
the correct result is:
9
Considered subsets are:
,
,
,
,
,
,
,
and
.
Task author: Jakub Radoszewski.