Spectacular Activity Selection

All submissions for this problem are available.
###Read problems statements in [Russian](http://www.codechef.com/download/translated/S19PETST/russian/SPECTAC.pdf), [Vietnamese](http://www.codechef.com/download/translated/S19PETST/vietnamese/SPECTAC.pdf), [Hindi](http://www.codechef.com/download/translated/S19PETST/hindi/SPECTAC.pdf), [Mandarin chinese](http://www.codechef.com/download/translated/S19PETST/mandarin/SPECTAC.pdf) and [Bengali](http://www.codechef.com/download/translated/S19PETST/bengali/SPECTAC.pdf) as well. In between cooking lunch and dinner, Chef has decided to take some time off to read about the [Activity Selection Problem] (https://en.wikipedia.org/wiki/Activity_selection_problem). In that problem, there are $M$ time intervals $[l_1, r_1], [l_2, r_2], \ldots, [l_M, r_M]$. A solution to the problem is a maximum subset of these intervals such that no two intervals from this subset have a common point (sharing an endpoint is also forbidden), i.e. a set containing the maximum possible number of such intervals. Since solving this problem proved to be too easy, Chef is now wondering: in how many ways could he pick a set of $M$ distinct intervals such that all of their endpoints belong to the set $\{1, 2, \ldots, N\}$ and the number of intervals in the solution to the Activity Selection Problem for this set is exactly $K$? Since the result may be very large, compute it modulo $MOD$. ### Input The first and only line of the input contains four spaceseparated integers $N$, $M$, $K$ and $MOD$. ### Output Print a single line containing one integer — the number of sets of intervals which satisfy all constraints, modulo $MOD$. ### Constraints  $1 \le K \le N \le 50$  $1 \le M \le \mathrm{min}(50, N(N + 1)/2)$  $100 \le MOD \le 10^9 + 7$  $MOD$ is a prime ### Example Input ``` 2 2 1 997 ``` ### Example Output ``` 2 ``` ### Explanation There are exactly two possible ways to pick the intervals:  $[1, 1]$ and $[1, 2]$  $[2, 2]$ and $[1, 2]$ ### Example Input ``` 2 2 2 997 ``` ### Example Output ``` 1 ``` ### Explanation We must pick intervals $[1, 1]$ and $[2, 2]$. ### Example Input ``` 30 25 20 997 ``` ### Example Output ``` 687 ```Author:  andrei1998 
Editorial  https://discuss.codechef.com/problems/SPECTAC 
Tags  activityselection, andrei1998, combinatorics, dynamicprogramming, greedy, medium, snckpe19, taran_1407 
Date Added:  2112018 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 