옥수수 밭

농부 존은 $M \times N$($1 \le M \le 12$, $1 \le N \le 12$)개의 정사각형 구획으로 이루어진 직사각형 목초지를 새로 샀습니다. 그는 이 중 몇몇 칸에 소들이 먹을 맛있는 옥수수를 심으려고 합니다. 그런데 일부 칸은 척박해서 심을 수 없습니다.

소들은 서로 가까이서 먹는 것을 싫어하므로, 존은 심을 칸을 고를 때 서로 인접한 칸(변을 공유하는 두 칸)을 동시에 고르지 않습니다.

마음이 무척 열린 존은 심을 칸을 고르는 모든 경우를 살펴보고 싶어 합니다. 한 칸도 심지 않는 것조차 유효한 선택으로 봅니다! 존이 옥수수를 심을 칸을 고르는 방법의 수를 구해 주세요.

• 첫째 줄: 공백으로 구분된 두 정수 $M$과 $N$
• 둘째 줄부터 $M+1$째 줄까지: $i+1$째 줄은 목초지의 $i$째 행을 나타내며, 각 칸이 비옥한지($1$) 척박한지($0$)를 공백으로 구분된 $N$개의 정수로 나타냅니다

• 첫째 줄: 존이 칸을 고를 수 있는 방법의 수를 100,000,000으로 나눈 나머지 하나를 출력합니다

위쪽 행 전체와 아래쪽 행의 가운데 칸만 비옥한 $2 \times 3$ 목초지를 생각해 봅시다. 비옥한 칸을 1, 2, 3(윗행 왼쪽부터)과 4(아랫행 가운데)라고 이름 붙이면, 한 칸만 심는 방법이 4가지(1, 2, 3, 4), 두 칸을 심는 방법이 3가지((1,3), (1,4), (3,4)), 세 칸을 심는 방법이 1가지((1,3,4)), 아무 칸도 심지 않는 방법이 1가지로 총 4+3+1+1 = 9가지입니다.