8382번 - Subsets 다국어

We are going to consider subsets P of a given set {1, ..., n}. We are interested in subsets such that for a given natural number x > 1 and for any natural number y at least one of the numbers y, x · y doesn't belong to P. We would like to calculate the number of such subsets, that have exactly k 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 m.

Write a program which:

• reads from the standard input four integers: n, m, k and x,
• calculates the remainder of the division by m of the number of k-element subsets of set {1, ..., n}, 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 n, m, k and x (1 ≤ n ≤ 10¹⁸, 2 ≤ m ≤ 1 000 000, 0 ≤ k ≤ 1 000, 2 ≤ x ≤ 10), separated by single spaces.

The first and only line should contain one integer - the reminder of the division by m of the number of k-element subsets of set {1, ..., n} that fulfill the specified requirements.

Considered subsets are: {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 5}, {2, 5, 6}, {3, 4, 5} and {4, 5, 6}.