Aqua là một trò chơi giải đố logic được chơi trên một bảng hình chữ nhật chia thành $r$ hàng và $c$ cột. Các hàng được đánh số từ $1$ đến $r$ từ dưới lên trên, và các cột được đánh số từ $1$ đến $c$ từ trái sang phải. Ô ở hàng thứ $i$ và cột thứ $j$ được ký hiệu là $(i,j)$.

Bảng được chia thành một số vùng liên thông trực giao (gọi là lồng) bằng các đường biên dọc và ngang. Chính xác hơn, mỗi lồng là một tập con khác rỗng gồm các ô của bảng. Mỗi ô trên bảng thuộc về đúng một lồng. Tập hợp các ô của một lồng tạo thành một thành phần liên thông: Nếu hai ô thuộc cùng một lồng, luôn có thể di chuyển từ ô này sang ô kia bằng cách chỉ đi qua các ô của lồng đó, sao cho mỗi bước là một bước di chuyển giữa hai ô kề cạnh.

Hình A.1: Một bảng có 6 hàng, 7 cột và 8 lồng.

Trong mỗi lồng, người tạo câu đố rót nước từ các cạnh phía trên của lồng. Do trọng lực, nước chảy xuống các ô ở độ cao thấp hơn. Anh ấy rót nước sao cho thỏa mãn tất cả các điều kiện dưới đây:

• Mỗi ô hoặc được đổ đầy nước hoàn toàn, hoặc hoàn toàn trống rỗng.

• Một lồng có thể đầy nước, hoàn toàn trống rỗng hoặc được đổ nước một phần.

• Trong mỗi lồng, tồn tại một mức nước $\ell$ nào đó sao cho tất cả các ô nằm dưới mức này của lồng đều đầy nước, và tất cả các ô nằm trên mức này của lồng đều trống rỗng. Nói cách khác, gọi $(r_1,c_1)$ và $(r_2,c_2)$ là hai ô thuộc cùng một lồng sao cho $r_1 \le r_2$; nếu ô $(r_2,c_2)$ đầy nước thì ô $(r_1,c_1)$ cũng phải đầy nước.

• Các lồng được xử lý độc lập và tách biệt nhau. Do đó, quy tắc trên không áp dụng cho các ô thuộc các lồng khác nhau.

Dưới đây là một ví dụ về bảng hợp lệ:

Hình A.2: Một bảng hợp lệ.

Dưới đây là một số ví dụ về các bảng không hợp lệ:

Hình A.3: Một bảng không hợp lệ — các ô $(5,5)$ và $(5,7)$ lẽ ra phải cùng đầy nước hoặc cùng trống rỗng, vì chúng nằm trong cùng một lồng và trên cùng một hàng.

Hình A.4: Một bảng không hợp lệ — các ô $(4,2)$, $(4,3)$ và $(4,4)$ đang trống rỗng, nhưng chúng lại nằm trong cùng một lồng với ô $(5,2)$ đang đầy nước.

Hình A.5: Một bảng không hợp lệ — các ô không thể chỉ chứa nước một phần.

Người tạo câu đố không chỉ tuân theo các quy tắc trên mà còn chú ý đến số lượng ô đầy nước trên mỗi hàng. Ở một số hàng, anh ấy muốn số lượng ô đầy nước bằng những giá trị cố định cho trước, trong khi không đặt bất kỳ ràng buộc nào lên các hàng khác.

Nhiệm vụ của bạn là đếm số cách rót nước vào các lồng thỏa mãn tất cả các quy tắc và yêu cầu nêu trên. Hai cách được coi là khác nhau khi và chỉ khi tồn tại một ô đầy nước ở cách này nhưng lại trống rỗng ở cách kia.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $r,c$ ($1 \le r,c \le 20$). Tiếp theo là $r+1$ dòng mô tả bảng theo các quy tắc sau:

• Mỗi dòng chứa đúng $2\cdot c+1$ ký tự, mỗi ký tự là một trong các loại sau: dấu cách, dấu gạch dưới (_) và dấu gạch đứng (|).

• Tất cả các ký tự ở vị trí chỉ số chẵn trên dòng đầu tiên và dòng cuối cùng đều là dấu gạch dưới, thể hiện đường biên trên và biên dưới của bảng.

• Mỗi dấu gạch dưới trong dữ liệu vào, ngoại trừ những dấu đã nêu ở trên, biểu thị một đường biên lồng nằm ngang giữa hai ô liên tiếp trong cùng một cột.

• Ký tự đầu tiên và ký tự cuối cùng của tất cả các dòng (ngoại trừ dòng đầu tiên) đều là dấu gạch đứng, thể hiện đường biên trái và biên phải của bảng.

• Mỗi dấu gạch đứng trong dữ liệu vào, ngoại trừ những dấu đã nêu ở trên, biểu thị một đường biên lồng thẳng đứng giữa hai ô liên tiếp trong cùng một hàng.

Xem các ví dụ để hiểu rõ hơn.

Theo định nghĩa:

• Nếu không có bất kỳ đường biên lồng nằm ngang nào giữa hai ô liên tiếp trong một cột, thì hai ô này thuộc cùng một lồng.

• Nếu không có bất kỳ đường biên lồng thẳng đứng nào giữa hai ô liên tiếp trong một hàng, thì hai ô này thuộc cùng một lồng.

Dòng cuối cùng chứa $r$ số nguyên $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) mô tả các yêu cầu về số lượng ô đầy nước trong mỗi hàng. Nếu $x_i=-1$, hàng thứ $r-i+1$ có thể có số lượng ô chứa nước tùy ý. Ngược lại, số lượng ô đầy nước ở hàng này phải bằng đúng $x_i$.

Dữ liệu đảm bảo bảng có nhiều nhất 20 lồng.

Kết quả

Kết quả gồm đúng một số nguyên — số lượng bảng hợp lệ thỏa mãn các điều kiện đã cho, chia lấy dư cho $10^9+7$.

Ví dụ

Dữ liệu vào 1

6 7
 _ _ _ _ _ _ _ 
| |  _ _|  _  |
| | |_ _| |_| |
| |_ _ _|  _ _|
| |  _ _| |   |
| | |_ _| |   |
|_|_ _ _|_|_ _|
6 3 7 2 2 2

Kết quả 1

1

Giải thích

Ví dụ đầu tiên tương ứng với hình A.2 ở trên.

Dữ liệu vào 2

2 3
 _ _ _ 
|     |
|_ _ _|
-1 -1

Kết quả 2

3

Dữ liệu vào 3

3 3
 _ _ _ 
|  _  |
| | | |
|_|_|_|
-1 1 1

Kết quả 3

1