The incoming Protoss army just finished its +1 ground attack upgrade and zealot speed upgrade, and is bearing down on the Zerg natural with a nasty timing attack.

The Zerg army has a bunch of creep colonies already built, and will convert some of them into sunken colonies in an attempt at holding the attack. Due to the nature of the timing attack and limited resources, the Zerg will refuse to convert creep colonies that are directly adjacent to each other.

The Zerg base is modeled as an $R\times C$ rectangle, and some of the locations in the base already have creep colonies ready to be converted. Two locations are considered adjacent if they share a side.

How many different subsets of creep colonies can the Zerg convert to sunken colonies? Note that the Zerg can choose not to convert any sunken colonies, which may be a viable strategy as creep colonies have more health than sunken colonies.

Constraints

$1\le R,C\le 12$

Input Specification

The first line will contain two integers, $R$ and $C$.

Each of the next $R$ lines will contain $C$ integers. If the $i$th integer is $1$, there is a creep colony in the $i$th column that can be converted there. Otherwise, the $i$th integer will be $0$ and there will not be a creep colony there.

Output Specification

Output the number of different configurations the Zerg can convert, modulo ${10}^8$.

Sample Input

2 3
1 1 1
0 1 0

Sample Output

9