Mazes in higher dimensions are quite different than mazes in lower dimensions such as two and three. Generally, mazes in lower dimensions have a lot of barriers or walls to confuse the peoples who enter it. But when the dimensions of maze is greater than 3, mere mortals struggle simply to find their directions so intense barriers are not required. In this problem we will try to study some N-dimensional grid mazes and find possible ways of going from one place to another. Our grid maze in three dimension looks like the following: This three dimensional maze has dimension of (5 × 4 × 3) which is made of 60 3D-blocks. The rules of the maze are: a) In an n dimensional maze one can go towards maximum 2n different directions from one place if there is no barrier. b) The movements are only possible parallel to the axis. c) The direction of movements should be such that it does not increase distance with the destination. By distance I mean the Cartesian distance. d) There may be some opaque hyper-blocks in the maze. These blocks do not allow anyone to go through. e) Total number of hyper-blocks in the maze is not more than 3000000. f) The maximum dimension length on any axis direction of the maze is 50. g) The maximum possible dimension of the maze is 7. h) In an n dimensional maze let the length along n-axes be l1, l2, l3, ..., ln respectively. Then the starting block is always (0,0,...,0) and the destination is always (l1 −1,l2 −1,l3 −1,...,ln −1). This n-Dimensional maze is made of (l1 × l2 × l3 × . . . × ln) n-dimensional hyper-blocks. In the 3-dimensional maze shown above the starting block is D (0,0,0) and the destination block is F (4, 3, 2). The figure above shows two possible ways of going from block D (0, 0, 0) to block F (4, 3, 2).
2/2 i) When the maze makers place opaque hyper-blocks in the maze they make sure that the number of ways to reach the destination is reduced to less than 263. Given the description of a maze your job is to determine the number of ways you can go from its lowest block to the highest block as it is said in point h. You must know that in a n-dimensional Cartesian coordinate system the coordinate of a point P can be written in the form (p1, p2, p3, . . . , pn) and the coordinate of another point Q can be written as (q1, q2, q3, . . . , qn). And the distance between these two points is: √ (p1 −q1)2 +(p2 −q2)2 +(p3 −q3)2 +...+(pn −qn)2 This distance is also known as the Cartesian distance of two points in n-dimension. Input The input file contains several sets of inputs. The description of each set is given below: First line of each set contains two integers DIM (0 < DIM < 8) and R (0 <≤ R < 30000). Here DIM is the dimension of the maze, R is the number of opaque blocks. Next line contain DIM integers (p1, p2, p3, . . . , pDIM ) which is the coordinate of the destination hyper-block. Each of the next R lines contains DIM integers which are the coordinates of R opaque blocks. Note that blocks are not point objects. So by coordinate of a block we refer to the point of the block that is nearest to the origin. Thats why in the picture above the coordinate of block D is (0, 0, 0). There is a blank line after each set of input. Input is terminated by a case where both DIM and R are zero. This case should not be processed. Output For each set of input produce one line of output. This line should contain the serial of the output as shown in the sample output. Then it should contain an integer N which indicates in how many ways we can reach the destination. It is guaranteed that this number will be less than 263. Sample Input 30 555 31 987 111 00 Sample Output Case 1: 756756 Case 2: 6318655200