Problem Description
The irRegularGame of Life(http://www.bilibili.tv/video/av94917/) is an interesting game, it’s based on the same cell rules as Conway's original, with the addition of limitations on initial conditions, and goals for completing levels.
The Conway’s original game of life rules is a "2-Dimensional cellular automaton". It was invented by British mathematician John Conway in 1970.It is not a game in the video game sense, but consists of a 2-D grid of cells. The game of life shouldn't to be confused with Milton Bradley's Board game of the same name.
Cells in the grid follow a few simple mathematical rules that determine whether they will live, die or multiply in the next generation.
Specifically, each cell interacts with its 8 horizontal, vertical, and diagonal neighbours, according to these 4 simple rules below:
1. Any live cell with fewer than 2 live neighbours dies through loneliness.
2. Any live cell with more than 3 live neighbours dies through overcrowding.
3. Any live cell with 2 or 3 live neighbours lives to the next generation.
4. Any dead cell with exactly 3 live neighbours comes to live.
Despite having such simple rules, the patterns that evolve are remarkable and can vary greatly from only small differences in initial conditions.
The game of life has fascinated mathematicians, computer scientists and nerdy types for decades.
This picture shows the rule of The irRegularGame of Life.
Sakuya thought this game is too simple, so he added some rules.
1.We have K (1<=K<=10) independent boxes in every level, and each box contains 4*4 grids.
2.The goal to pass a level is the sum of live cells in all boxes are exactly N (0<=N<=20) after T (0<=T<=200000) generations.
3.For those boxes, we can add at most M (0<=M<=20) cells.
Sakuya want know how many ways to pass one level?
As an example, initially we have one box as below.
The goal is to have exactly 5 live cells after 10 generations, and we can add at most one cell into the box.
There are 9 different ways to pass this level.
Input
First an integer L (L <= 50), indicates there are L different levels.
For every level, the first line contains 4 integers, they are K, M, T and N which mentioned above.
Then, there are K 4*4 01-matrices follow, indicating the initial state of each box, 0 stands for an empty cell and 1 stands for an alive cell.
Output
For each level, you should output "Case #C: " first, where C indicates the level number and counts from 1. Then output the answer. There may be a great deal of ways, just mod 1000000009
Sample Input
2
1 1 10 5
0 0 0 0
0 1 0 0
1 0 1 0
0 1 0 0
2 3 0 3
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Sample Output
Case #1: 9
Case #2: 4960
