Chef and Big Matrix

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a rectangular table consisting of N rows and M columns. Rows are numbered by integers from 1 to N from top to bottom and columns are numbered from 1 to M from left to right. Let (x, y) denote the cell corresponding to x^{th} row and y^{th} column.
Chef has two bunnies, both initially at the cell (1, 1). He wants them to get to the cell (N, M). Each of the bunny can move from some cell (x, y) to cell (x+1, y) or cell (x, y+1). As bunnies do not really like each other, they do not want to meet along their ways, except at the start (1,1) and end (N, M) cells.
Also, there are exactly C cells in the table containing a carrot. When a bunny goes through such a cell, he eats this carrot. As Chef also wants to eat carrots, he wants that both the bunnies cumulatively don't eat more than D carrots.
Find out number of ways in which bunnies can get from cell (1, 1) to cell (N, M) satisfying the above conditions. As answer could be large, please output your answer modulo MOD.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains five spaceseparated integers N, M, C, D and MOD denoting the sizes of table, the number of cells with a carrot, the maximum number of carrots that can be eaten by bunnies and the modulo.
 Each of next C lines contains two spaceseparated integers x_{i} and y_{i} denoting the coordinates of the cell with a carrot.
Output
 For each test case, output a single line containing the numbers of ways bunnies can get from cell (1,1) to cell (N, M) modulo MOD.
Constraints
 2 ≤ N, M ≤ 10^{5}
 0 ≤ D ≤ C ≤ min{200, N * M  2}
 1 ≤ x_{i} ≤ N
 1 ≤ y_{i} ≤ M
 1 ≤ MOD ≤ 10^{9}
 It's guaranteed that there is no carrot in cells (1, 1) and (N, M)
Subtasks
Subtask #1 (7 pts)
 1 ≤ T ≤ 100
 2 ≤ N, M ≤ 5
 TL = 2s
Subtask #2 (11 pts)
 1 ≤ T ≤ 10
 2 ≤ N, M, C ≤ 60
 TL = 2s
Subtask #3 (13 pts)
 1 ≤ T ≤ 10
 C = 0
 TL = 2s
Subtask #4 (19 pts)
 1 ≤ T ≤ 5
 0 ≤ C ≤ 100
 TL = 10s
Subtask #5 (23 pts)
 1 ≤ T ≤ 5
 0 ≤ C ≤ 100
 TL = 2s
Subtask #6 (27 pts)
 1 ≤ T ≤ 5
 TL = 2s
Example
Input: 4 2 3 0 0 10 2 3 1 0 16 2 1 3 3 1 0 7 2 2 2 2 2 1 11 1 2 2 1 Output: 1 0 1 0
Explanation
Example case 1.
***
***
In this case there is only one variant how bunnies can get from the cell (1,1) to the cell (2, 3).
First bunny  (1, 1) > (2, 1) > (2, 2) > (2. 3) and the second bunny  (1, 1) > (1, 2) > (1, 3) > (2, 3).
Example case 2.
***
x**
In this example there are no two nonintersecting ways without cells with carrot. Therefore the answer is 0.
Example case 4.
*x
x*
In this case there is only one variant how bunnies can move. First bunny  (1, 1) > (2, 1) > (2, 2) and the second bunny  (1, 1) > (1, 2) > (2, 2). But in this case, in total, bunnies will eat two carrots(when only one carrot is allowed). Therefore the answer is 0.
Author:  antoniuk1 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHNBGMT 
Tags  antoniuk1 april16 binomial chineserem hard modularinv 
Date Added:  8022016 
Time Limit:  2  10 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions