🏡 index : github.com/captn3m0/codechef.git

---
category_name: hard
problem_code: CHNBGMT
problem_name: 'Chef and Big Matrix'
languages_supported:
    - 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
max_timelimit: '2 - 10'
source_sizelimit: '50000'
problem_author: antoniuk1
problem_tester: xcwgf666
date_added: 8-02-2016
tags:
    - antoniuk1
    - april16
    - binomial
    - chinese
    - hard
    - modular
editorial_url: 'http://discuss.codechef.com/problems/CHNBGMT'
time:
    view_start_date: 1460374200
    submit_start_date: 1460374200
    visible_start_date: 1460374200
    end_date: 1735669800
    current: 1493556655
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/APRIL16/mandarin/CHNBGMT.pdf), [Russian](http://www.codechef.com/download/translated/APRIL16/russian/CHNBGMT.pdf) and [Vietnamese](http://www.codechef.com/download/translated/APRIL16/vietnamese/CHNBGMT.pdf) 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 **xth** row and **yth** 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 space-separated 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 space-separated integers **xi** and **yi** 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** ≤ **105**
- 0 ≤ **D** ≤ **C** ≤ **min{200, N \* M - 2}**
- **1** ≤ **xi** ≤ **N**
- **1** ≤ **yi** ≤ **M**
- **1** ≤ **MOD** ≤ **109**
- 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

<pre><b>Input:</b>
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

<b>Output:</b>
1
0
1
0
</pre>### 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.