National Olympiad in Informatics, China, 2010

The 2010 World Expo will be hosted in Shanghai, China, attracting millions of tourists from within and outside of China. Little Z has also arrived at Expo 2010 during her summer vacation. She has known about the infamous crowdedness of the world's fair. She is already very prepared to wait many hours in line at certain pavilions, but to make her trip at the Expo even smoother, little Z decided to plan a detailed route.

Little Z has gotten her hands on a map of the Expo, and she noticed that the site of the whole event is very narrow and long. Within it, each pavilion occupies a square region which are all roughly the same size. Thus, we can view the entire Expo as an ~n \times m~ grid ~(n \le 3)~, where each grid cell represents a theme pavilion.

Since the attention received by different pavilions differ, the length of time spent waiting in their lines will also vary. Through statistical data, Little Z has labeled each pavilion ~(x, y)~ with a number ~T_{x, y}~ equaling either ~0~ or ~1~. If ~T_{x, y} = 1~, then this pavilion is really popular and will demand a very long wait. If ~T_{x, y} = 0~, then this pavilion is relatively average, and will require virtually no waiting at all to enter. Little Z wishes to design a route with a fixed order of popular and average pavilions: this way she won't have to wait in line for too long due to always visiting popular pavilions, but also won't be bored due to always visiting average pavilions. She has formulated a ~01~-sequence ~L~ of length ~n \times m~, wishing for her ~i~-th visited pavilion ~(x, y)~ to satisfy ~T_{x, y} = L_i~.

At the same time, little Z really values efficiency; she wishes to avoid unnecessary walking when visiting all the pavilions. Thus she wishes for her route to satisfy the following conditions:

1. After visiting the pavilion at location ~(x, y)~, the next pavilion she visits must be a neighboring pavilion ~(x', y')~ that has not already been visited, where ~|x-x'|+|y-y'| = 1~.
2. The route's starting position must be on the border of the entire grid, where either ~x = 1~, or ~x = n~, or ~y = 1~, or ~y = m~.

Little Z wishes to know how many possible routes can satisfy these requirements. Since the final answer can be really large, little Z would only like to know the number of possible routes modulo ~11\,192\,869~.

Input Specification

• The first line contains two positive integers ~n~ and ~m~.
• For lines ~2~ to ~n+1~, each line contains ~m~ space separated integers, where the ~j~-th number on line ~i+1~ represents ~T_{i, j}~.
• Line ~n+2~ contains a ~n \times m~ space separated ~0/1~ integers: the ~i~-th integer is the value of ~L_i~.

Output Specification

The output should contain a single integer, representing the number of valid routes that satisfy the requirements, modulo ~11\,192\,869~.

Sample Input

2 2
1 0
0 1
1 0 1 0

Sample Output

4

Explanation

The four valid routes are:

• ~(1, 1) \to (1, 2) \to (2, 2) \to (2, 1)~
• ~(1, 1) \to (2, 1) \to (2, 2) \to (1, 2)~
• ~(2, 2) \to (1, 2) \to (1, 1) \to (2, 1)~
• ~(2, 2) \to (2, 1) \to (1, 1) \to (1, 2)~

Constraints

For ~10\%~ of the test cases: ~n = 1~.
For ~30\%~ of the test cases: ~n = 2~.
For ~60\%~ of the test cases: ~n = 3~, and ~20\%~ of the test cases have ~T_{i, j}~ all equal to ~0~.
For ~100\%~ of the test cases: ~m \le 50~, and ~L_i, T_{i, j} = 0~ or ~1~.

Problem translated to English by Alex, fixed by rpeng.