In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

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:

9

Considered subsets are: , , , , , , , and .

*Task author: Jakub Radoszewski.*