You want to build a toy by placing identical cubic blocks on a rectangular grid. The shape of the toy can be described by a "height matrix." For example, the matrix below indicates that the height above the center cell of the grid is 4, while the height at all other positions is 1.

You have an unlimited supply of $1 \times 1$ and $1 \times 2$ blocks, so you can build many different toys. The figure below shows one possible configuration, where letters represent unit cubes, and identical letters represent the same block.

(a) Top view (b) Front view

If at least one $1 \times 1$ block is used, the toy is called a "regular toy"; otherwise, it is called an "advanced toy."

Given a height matrix, your task is to count how many different regular toys and advanced toys can be formed.

Input

The input contains no more than 20 test cases. The first line of each test case contains two positive integers $R$ and $C$ ($1 \le R \times C \le 16$), representing the number of rows and columns of the grid. The following $R$ lines each contain $C$ integers, representing the height $h(i,j)$ of each cell ($0 \le h(i,j) \le 20$).

Output

For each test case, output the test case number, the number of regular toys, and the number of advanced toys. Since the answers can be very large, output these two values modulo $10^9+7$.

Examples

Input 1

3 3
1 1 1
1 4 1
1 1 1
1 5
1 1 1 1 1
2 2
2 3
4 5

Output 1

Case 1: 485 2
Case 2: 8 0
Case 3: 2794 12