鄱阳湖之战

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 话说天下大势,分久必和,合久必分。。。

又到了兵慌马乱的年代,至正十七年(1357年)九月,陈友谅袭杀倪文俊,自称宣慰使,以邹普胜为太师,张必先为丞相,起兵攻下江西诸路。迎徐寿辉迁都江州(治今江西九江)。陈友谅挟持徐寿辉,自称汉王,建都江州,国号汉,年号大义。至正二十年(1360年),陈友谅东伐朱元璋,并在途中杀徐寿辉,自立为大汉皇帝。陈冲破朱元璋长江太平防线,兵临集庆(今南京)城下。陈朱双方在集庆城西北的龙湾展开恶战,不巧江水落潮,百艘巨舰搁浅,陈友谅大败,逃走江州(九江)。至正二十三年(1363年)四月,陈友谅再出兵进围攻江西洪都(今南昌),水陆两军号称60万人,陈友谅还动用水陆两栖作战,水船使用高大但是迟缓的楼船,却围攻洪都不下(守将是朱元璋侄儿朱文正将军),朱元璋在七月亲率20万人救洪都,出身原元军水师叛军的陈友谅于是撤围,在中国最大淡水湖鄱阳湖选择所擅长水战迎战朱元璋。

此次大战朱元璋可谓九死一生,虽然最后侥幸取胜,但也让人看得惊心动魄,心有余悸。且不管战况如何,今日我们谈谈这一代枭雄陈友谅的排兵布船之法。鄱阳湖之战初期,陈友谅为了布兵费劲心机。陈友谅欲将船摆成n*m的方阵,对朱元璋的的船队进行冲击。由于水中有一些地方不能布船(有暗礁或水草,会把船困住)所以他决定这些位置不再布置船只。当然,我们知道,如果两条船相邻的话,当船加速行进时,两边的压力会把船挤到中间,两船就会撞毁。所以陈友谅要求不能出现两条船紧挨着的情况。现在陈友谅请你去帮他布兵,聪明的ACMer,你怎么解决这个问题呢?

 

 

Input

 输入n和m,接下来是n*m的方阵(0 < n , m <= 11),1表示可以放船,0表示不能放船。

Output

 输出有多少种布船方法,结果模100,000,000;

Sample Input

2 3
1 1 1
0 1 0

Sample Output

9

Hint

1 2 3
4
你可以(1,2,3或4)上只放一只船,或者(13, 14, 34)上放船,再或者(134),当然也可以1234都不放(虽然陈友谅会哭的^^),这样共有4 + 3 + 1 + 1 = 9种。

Source

von