Problem : 209 - 買醬油III 之污漬問題

Problem Statistics

Solved Member: 23　　Submission: 215　　User Tried: 27

Statement:

梓喵又回來買醬油了！！
自從上一次，梓喵去買醬油之後，你已經在路上被她撞到而得到幸福了。(如果你已經AC過這題的話...)

梓喵買了很多種醬油瓶，每一種醬油瓶可以用一個3x3的方塊表示。

方塊中的1代表污漬，0代表乾淨。

每一種醬油瓶，梓喵都買了無限多個，她想要挑出若干個醬油瓶，串成一個M瓶醬油瓶的橫向序列。

規定只有一個，排成的醬油瓶序列當中，不能有任何污漬上下左右相鄰。

梓喵現在想要問你，她有幾種相異擺法。

Input:Output:

第一行有兩個數字N和M，其中用一個空格隔開，分別代表醬油瓶種類數量以及醬油瓶序列目標長度。(1 ≤ N ≤ 10, 1 ≤ M ≤ 10000000)
接下來有3xN行，每一行有3個字元，每3行代表一個醬油瓶，其中1代表污漬，0代表乾淨。

題目中所給的醬油瓶種類都是獨立的，也就是說，若有兩種醬油瓶污漬排列一模一樣，只要分開定義，就視為不同種。並且，任何醬油瓶都不可以旋轉。

輸出只有一行，包含一個數字，代表種類數量，請將此答案 % 1000000007 之後再輸出。

Sample Input:Sample Output:

3 5
101
010
101
000
000
000
010
000
100

HINT:

對於範例測資，這是一種合理接法：

101 000 010 101 000
010 000 000 010 000
101 000 100 101 000

以下第二種範例，因為在第四、第五兩個醬油瓶之間存在一組汙漬相鄰因此就不合了：

101 000 010 101 010
010 000 000 010 000
101 000 100 101 100

醬油瓶是方形的O_O

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	3000ms	65536kb	10
9	3000ms	65536kb	10
10-1	3000ms	65536kb	10
10-2	3000ms	65536kb

Problem : 209 - 買醬油III 之 污漬問題

Problem : 209 - 買醬油III 之污漬問題