Configurations

Well,inthisproblemyouaregivenanR×Cgrid(1≤R≤109 and1≤C≤10). TherewillbeB 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.
2. You cannot move a token outside of the grid.
3. You cannot move two or more tokens to the same cell.
4. 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≤10and0≤M≤Crespectively. Thesecondlinecontains0≤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.

2/2 Sample Input 3 1000000000 10 0 0 1000000000 10 2 0 10202 10 2 4 10 3 11 2 20 3 20 5 Sample Output Case 1: 1 Case 2: 4973 Case 3: 3205