Mathematics Curriculum solution codeforces

Mathematics Curriculum solution codeforces

Let c1,c2,,cnc1,c2,…,cn be a permutation of integers 1,2,,n1,2,…,n. Consider all subsegments of this permutation containing an integer xx. Given an integer mm, we call the integer xx good if there are exactly mm different values of maximum on these subsegments.

Cirno is studying mathematics, and the teacher asks her to count the number of permutations of length nn with exactly kk good numbers.

Mathematics Curriculum solution codeforces

Unfortunately, Cirno isn’t good at mathematics, and she can’t answer this question. Therefore, she asks you for help.

Since the answer may be very big, you only need to tell her the number of permutations modulo pp.

A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

Mathematics Curriculum solution codeforces

A sequence aa is a subsegment of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains four integers n,m,k,pn,m,k,p (1n100,1mn,1kn,1p1091≤n≤100,1≤m≤n,1≤k≤n,1≤p≤109).

Output

Output the number of permutations modulo pp.

Examples
input

Copy Mathematics Curriculum solution codeforces

4 3 2 10007
output

Copy Mathematics Curriculum solution codeforces

4
input

Copy Mathematics Curriculum solution codeforces

6 4 1 769626776 
output

Copy Mathematics Curriculum solution codeforces

472
input

Copy Mathematics Curriculum solution codeforces

66 11 9 786747482
output

Copy Mathematics Curriculum solution codeforces

206331312
input

Copy Mathematics Curriculum solution codeforces

99 30 18 650457567 
output

Copy Mathematics Curriculum solution codeforces

77365367

Note Mathematics Curriculum solution codeforces

In the first test case, there are four permutations: [1,3,2,4][1,3,2,4][2,3,1,4][2,3,1,4][4,1,3,2][4,1,3,2]  and [4,2,3,1][4,2,3,1].

Take permutation [1,3,2,4][1,3,2,4] as an example:

For number 11, all subsegments containing it are: [1][1][1,3][1,3][1,3,2][1,3,2] and [1,3,2,4][1,3,2,4], and there’re three different maxima 1133 and 44.

Similarly, for number 33, there’re two different maxima 33 and 44. For number 22, there’re three different maxima 2233 and 44. And for number 44, there’re only one, that is 44 itself.

Leave a Reply

Your email address will not be published. Required fields are marked *

*