Problem1047--积木玩具

1047: 积木玩具

[Creator : ]
Time Limit : 15.000 sec  Memory Limit : 256 MB

Submit

Description


你想在一个长方形棋盘上放一些等大的正方体积木块,搭成一个玩具。玩具的形状可以用一个 “高度矩阵”来描述。比如下面的矩阵表示棋盘中心格子的上方的高度为 4,而其他位置的高 度为 1。 

你有足够多的 1*1 和 1*2 积木块,所以可以搭出很多种不同的玩具。比如下图展示了一种可能 的方案,其中字母表示单位正方体,相同字母代表同一个木块。 
 
如果至少用了一个 1*1木块,这个积木成为普通玩具,否则称为高级玩具。 
输入一个高度矩阵,你的任务是统计出有多少种不同的普通玩具和高级玩具。 


Input

输入包含不超过 20组数据。每组数据第一行为两个正整数 R, C (1<=R*C<=16),即棋盘的行数 和列数。以下 R行每行 C个整数,表示各个格子的高度 h(i,j). (0<=h(i,j)<=20) 

Output

对于每组数据,输出测试点编号,普通玩具的个数和高级玩具的个数。因为答案可能很大,只 需输出这两个值除以 109+7的余数。 

Sample Input Copy

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

Sample Output Copy

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