21712_BoardColoring

HH is painting a board of size 4 × N. You can assume the color of square (X, Y) on the board is A_{x, y} which is an integer between 0 and 255. For the beauty of the board, HH decide to paint the board following the rules :

1. A_{x, y} ≥ A_{x, y-1}.

2. For some given pairs of (X₁, Y₁) (X₂, Y₂), A_{x1, y1} = A_{x2, y2}

Your task is to calculate how many ways there are to paint the board.

There are multiple test cases, the first line of input contains a single integer denoting the number of test cases.

For each test case, the first line contains an integer N and M, denoting the length of the board and the number of additional rules. (1 ≤ N ≤ 15, 0 ≤ M ≤ 100)

For next M lines, each line contains four integers X₁, Y₁, X₂, Y₂ denoting one additional rule for the painting. (1 ≤ X₁, X₂ ≤ 4, 1 ≤ Y₁, Y₂ ≤ N)

For each test cases, you are to output the number of ways of painting. Because there may be too many ways, you are only to output the last five digits. See sample output for further details.

3
1 0
1 3
1 1 2 1
1 1 3 1
4 1 3 1
2 6
1 1 2 1
1 1 3 1
1 1 4 1
1 2 2 2
1 2 3 2
1 2 4 2

Case 1: 67296
Case 2: 00256
Case 3: 32896