Chọn Ô Không Chung Cạnh

Cho một bảng $N\times M$. Mỗi ô có giá trị $1$ nếu được phép chọn và $0$ nếu không được phép chọn.

Hãy đếm số cách chọn một tập các ô được phép sao cho không có hai ô được chọn nào chung cạnh. Tập rỗng cũng được tính là một cách.

Input

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• Mỗi trong $N$ dòng tiếp theo chứa $M$ số nguyên, mỗi số là $0$ hoặc $1$, mô tả một hàng của bảng.

Output

• In số cách chọn, lấy phần dư theo $10^8$.

Constraints

• $1\le N,M\le 12$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 6$ và $M\le 6$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

1 3
1 1 1

5