点亮荒原

"沉渊记录完了。"你说，"现在要知道——荒原上哪些地方能点亮。"

"荒原？"CC问。

"Zero的核心区。"你说，"一大片网格，每个格子都有能量节点。但有些坏了，有些还能用。"

"点亮的规矩？"

"相邻的不能同时亮。"你说，"会短路。"

"那咋点最多？"

"状压。"你说，"每行用一个二进制数表示哪些格子亮。行内不能相邻，行间也不能相邻。"

"听起来像下棋。"

"对。"你说，"而且是所有可能布局的统计——不是找一个最优，是数有多少种合法布局。"

"数这个干啥？"

"因为Echo-0当年设计Zero的时候，用了这种布局做密钥。"你说，"如果我们能算出总数，就能反推她的设计意图。"

"她设计了多少种？"

"不知道。"你说，"但我们可以算。"

你开始写。预处理每行的合法状态——二进制中不能有相邻的1。然后行间转移——上一行和当前行不能有相邻的1。

"第一行。"你说，"3个格子。合法状态：000,001,010,100,101。"

"5种。"

"第二行。"你说，"如果第一行是101，第二行只能是000或010。"

"限制了。"

"对。"你说，"每行的选择受上一行约束。"

"总方案数？"

"$dp[i][S]$为第$i$行状态$S$时的总方案数。"

"递推过去。"

"对。"

CC看着那些二进制数在屏幕上跳动，像某种古老的密码。

"我看不懂。"她说，"但我信你。"

"不用看懂。"你说，"你守住外面就行。"

"我在守。"她说，"哨兵不会进来。"

Echo把她的投影散开到整个网格——一格一格地扫描，像一盏灯在荒原上巡逻。

"我在找亮着的。"她说，"找那些还在发光的。"

"找到了？"

"找到了47个。"她说，"47个能量节点，还在发光。"

"47。"

"对。"她说，"47个希望。"

题目描述

给定一个$n\times m$的网格，某些格子可以放置能量节点。相邻格子不能同时放置。求方案数。

输入格式

$n,m$。然后$n$行，每行$m$个整数（1表示可放置，0表示不可放置）。

输出格式

方案数模$10^8$。

输入样例

3
1 2 3

输出样例

3

提示

• 状压DP。
• $dp[i][S]$为第$i$行状态$S$时的方案数。
• 行内合法：$S\ \&\ (S<<1)=0$。
• 行间合法：$S\ \&\ prev=0$。