In 2010, the World Expo was held in Shanghai, China, attracting tens of millions of domestic and international visitors. During the summer vacation, Xiao Z also visited the Shanghai World Expo Park. Having heard about the crowds at the Expo and being well-prepared for the fact that some pavilions might require hours of queuing, Xiao Z decided to plan a detailed travel route before her visit to make her Expo journey smoother and more enjoyable.

Xiao Z collected a map of the Expo Park and discovered that, overall, the park is a very long and narrow area, with each pavilion occupying a square of almost the same size. Therefore, the entire park can be viewed as an $n \times m$ matrix ($n \le 3$), where each cell is a themed pavilion.

Due to varying levels of interest, the queuing times for different pavilions differ. Based on statistical information, Xiao Z marked each pavilion $(x, y)$ with $T_{x,y} = 0$ or $1$. If $T_{x,y} = 1$, it means the pavilion is very popular and requires a long wait; if $T_{x,y} = 0$, it means the pavilion is relatively ordinary and requires almost no queuing. Xiao Z hopes to create a reasonable route that allows her to alternate between popular and ordinary pavilions, avoiding both the long queues of visiting only popular pavilions and the monotony of visiting only ordinary ones. At the same time, Xiao Z is very efficient and wants to visit all the pavilions without taking unnecessary paths that waste energy. Therefore, she wants the travel route to satisfy the following constraints:

1. After visiting the pavilion at $(x, y)$, the next pavilion visited must be an adjacent, unvisited pavilion $(x', y')$, i.e., $|x-x'| + |y-y'| = 1$;
2. The starting point of the route must be on the boundary of the entire matrix, i.e., $x = 1$ or $x = n$ or $y = 1$ or $y = m$;

She has defined a $01$ sequence $L$ of length $n \times m$, and she wants the $i$-th pavilion $(x, y)$ visited to satisfy $T_{x,y} = L_i$.

Xiao Z wants to know how many different travel routes satisfy her requirements. Since the final result may be very large, she only wants to know the total number of feasible travel routes modulo $11192869$.

Input

The first line contains two positive integers $n, m$. The next $n$ lines each contain $m$ integers ($0$ or $1$), where the $j$-th number in the $i$-th line represents $T_{i,j}$. The $(n+2)$-th line contains $n \times m$ integers ($0$ or $1$), where the $i$-th number represents the value of $L_i$.

Output

Output a single integer representing the total number of feasible travel routes modulo $11192869$.

Examples

Input 1

2 2
10
01
1010

Output 1

4

Note

The four feasible travel 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 data: $n=1$; For $30\%$ of the data: $n=2$; For $60\%$ of the data: $n=3$, where $20\%$ of the data has $T_{i,j}$ all equal to $0$; For $100\%$ of the data: $m \le 50$, $L_i, T_{i,j} \in \{0, 1\}$.