题目描述

有一块由 $n$ 行 $m$ 列组成的展示板。每个位置要么可用，要么被挡住不可用。

现在要在若干可用位置上放置徽章。为了保证展示效果，任意两个徽章不能共享一条边，也就是说不能出现在上下相邻或左右相邻的位置。

请统计有多少种放置方案满足要求。一个徽章也不放也算作一种合法方案。

输入格式

输入包含多组数据，直到文件结束。

每组数据第一行输入两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个整数。其中 $1$ 表示该位置可用，$0$ 表示该位置不可用。

输出格式

对每组数据输出一行一个整数，表示合法方案数对 $100000000$ 取模后的结果。

样例

2 2
1 1
1 1

7

样例说明

在 $2\times2$ 的全可用展示板上，可以不放、放任意一个位置，或放一组对角位置，共 $1+4+2=7$ 种方案。

数据范围

$1\le n,m\le 12$，每个格子状态为 $0$ 或 $1$。输入可能包含多组数据。