Problem Description
QXJ has N robots on the plane, the i-th is at (xi,yi), 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.
Input
The first line is the number of test cases T(T≤10).
The first line of each case contains three integer N(1≤N≤200),M(1≤M≤20),K(1≤K≤500), indicating the number of robots ,the number of color and the number of steps robots can move.
The second line,contains M integer mi, 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 xi,yi, indicating the postion of i-th robots..
(0≤|xi,yi|≤250).
Output
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 109+7).
Sample Input
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
Sample Output
Case #1: 49
Case #2: 256
