Năm nay, ông già Noel lại bay đến thị trấn JOI. Mọi ngôi nhà trong thị trấn đều có trẻ em, nên ông phải đi phát quà đến tất cả các nhà. Tuy nhiên, chú tuần lộc đi cùng ông năm nay hơi kém định hướng và chỉ có thể hạ xuống trên các công trình, nên ông cần khéo léo lựa chọn đường đi để phát quà cho mọi nhà.

Thị trấn JOI được chia thành các ô theo các hướng đông, tây, nam, bắc. Mỗi ô là một ngôi nhà, một nhà thờ hoặc một khu đất trống. Trong thị trấn có đúng một nhà thờ. Ông già Noel và tuần lộc xuất phát từ nhà thờ, phát quà cho mỗi ngôi nhà đúng một lần rồi trở về nhà thờ, theo các quy tắc sau:

• Vì hơi kém định hướng, chú tuần lộc năm nay chỉ có thể bay thẳng theo một trong bốn hướng đông, tây, nam, bắc và không thể đổi hướng trên không.
• Có thể tự do bay qua phía trên những ngôi nhà chưa được phát quà và có thể hạ xuống những ngôi nhà ấy. Mỗi khi hạ xuống một ngôi nhà, ông già Noel bắt buộc phải phát quà, rồi bay đi theo một trong bốn hướng đông, tây, nam, bắc.
• Vào đêm Giáng sinh, các nhà trong thị trấn JOI không đốt lò sưởi cho đến khi ông già Noel đến, và chỉ đốt lò sau khi ông bay đi. Khi lò sưởi được đốt, khói sẽ thoát ra từ ống khói, nên không thể bay qua phía trên một ngôi nhà đã được phát quà.
• Có thể tự do bay qua phía trên nhà thờ. Tuy nhiên, vì nhà thờ đang có buổi lễ, không được hạ xuống nhà thờ cho đến khi phát hết quà.
• Có thể tự do bay qua phía trên các khu đất trống, nhưng không được hạ xuống đó.

Yêu cầu

Cho cấu trúc của thị trấn. Hãy viết chương trình tính số đường đi mà ông già Noel và tuần lộc có thể sử dụng để phát quà.

Dữ liệu vào

Dữ liệu vào gồm \(n+1\) dòng.

• Dòng đầu tiên chứa hai số nguyên \(m,n\), cách nhau bởi một dấu cách.
• Mỗi dòng từ \(2\) đến \(n+1\) chứa \(m\) số, cách nhau bởi dấu cách; mỗi số là \(0\), \(1\) hoặc \(2\) và biểu diễn trạng thái của một ô.

Ký hiệu \((i,j)\) là ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây (\(1\le i\le n\), \(1\le j\le m\)). Giá trị thứ \(j\) trên dòng \(i+1\) mô tả ô \((i,j)\):

• \(0\) nếu đó là khu đất trống.
• \(1\) nếu đó là ngôi nhà.
• \(2\) nếu đó là nhà thờ.

Dữ liệu ra

In ra một dòng chỉ chứa một số nguyên là số đường đi để phát quà.

Ràng buộc

• \(1\le m\le 10\).
• \(1\le n\le 10\).
• Có đúng \(1\) nhà thờ.
• Số ngôi nhà từ \(1\) đến \(23\).
• Trong các bộ dữ liệu chấm, số đường đi để phát quà không vượt quá \(2\,000\,000\).

Ví dụ

3 2
1 0 1
1 0 2

2

3 3
1 1 1
1 0 1
1 1 2

6