Problem E

Configurations
Input: Standard Input

Output: Standard Output

 

Well, in this problem you are given an RxC  grid (1≤R≤109 and 1≤C≤10). There will be B blocks (1≤B≤100) in the grid. Each block will be placed in a cell of the grid. There can be more than one blocks in a cell.

Now you are given M identical tokens and you can place them in the first row as you like. A cell cannot contain more than one token and you also cannot place a token in a cell occupied by blocks. Now you can move a token but you have to follow following rules:              
        1. If there is a token in a cell (r,c) then you can move it to either (r+1,c-1) or (r+1,c+1).
        2. You cannot move a token to a cell occupied by blocks.
        3. You cannot move a token outside of the grid.
        4. You cannot move two or more tokens to the same cell.    
        5. All the tokens should be moved to i-th row before any token can be moved (i + 1)-th row.            

Now let S = {(1,c1),(1,c2),...,(1,cM)) be the set of cells of where you placed M identical tokens and W(S) = number of ways you can move these tokens to last row. You have to find the sum of W for every possible S.

For R = 2, C = 2, M = 1 and B = 0 the answer is 2.

Input

           First line contains number of test cases 1≤T≤500.   For each test case, the first line contains 1≤R≤109 , 1≤C≤10 and  0≤M≤C respectively. The second line contains 0≤B≤100, followed by B lines and each of those B lines contains two integers r and c, (1≤r≤R and 1≤c≤C) indicating the cell position of each block.

Output
             For each test cases you have to output the answer in a single line as shown in the sample output. As the answer can be very large you have to mod the output with 12345.

 

 

Sample Input

Output for Sample Input

3
1000000000 10 0
0
1000000000 10 2
0
10202 10 2
4
10 3
11 2
20 3
20 5

 

Case 1: 1
Case 2: 4973
Case 3: 3205

Problemsetter: Kazi Rakibul Hossain

Special Thanks: Md. Arifuzzaman Arif, Jane Alam Jan