Robots

QXJ has $N$ robots on the plane, the i-th is at $(x_i, y_i)$, numbereded 1 to $N$. Every robot is painted by one kind of color, numbered 1 to $M$.

Each robots can move $K$ times. In one move,a robot at $(x,y)$ can move to $(x-1,y),(x,y+1),(x+1,y),(x,y-1)$.

After exactly $K$ moves, she wants robots with same color to gather at the same postion and the robot on the i-th color gather at different postion with robots on (i-1)-th or (i+1)-th color.

Now she wants to know how many ways of moving these robots following to rules above.

Two ways are different if one of final postions of certain robot is different or there is at least one robot whose moving path is different.

The first line is the number of test cases $T (T \leq 10)$.

The first line of each case contains three integer $N(1 \leq N \leq 200), M(1 \leq M \leq 20), K(1 \leq K \leq 500)$, indicating the number of robots ,the number of color and the number of steps robots can move.

The second line,contains $M$ integer $m_i$, indicating the number of robots with the i-th color.

The robots numbered $[1,m1]$ are on the 1st color.The robots numbered $[m1+1,m1+m2]$ are one the 2nd color, ans so on.

The next $N$ line,each contains two integers $x_i, y_i$, indicating the postion of i-th robots..

$(0\leq |x_i, y_i| \leq 250)$.

For each test case, output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer(module $10^9 + 7$).

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

Case #1: 49
Case #2: 256

UESTC

2016中国大学生程序设计竞赛 - 网络选拔赛