Alternate Path in Expo

In 2010, the Expo in Shanghai attracted millions of visitors from around the world. Little Z planned her visit by first designing a detailed itinerary through the expo park. The expo park can be represented as an n × m grid (with n ≤ 3), where each cell denotes an exhibition hall. Each hall (x, y) is marked with a binary value \(T_{x,y}\) such that

[ T_{x,y} \in {0, 1} ]

If \(T_{x,y} = 1\), then the hall is very popular and often involves a long queue; if \(T_{x,y} = 0\), the hall is less popular with almost no waiting time. Meanwhile, Little Z has prepared a binary sequence \(L = L_1L_2\cdots L_{n\times m}\) (with each \(L_i\) being 0 or 1) representing the type of hall she wants to visit at the \(i\textsuperscript{th}\) step; that is, the \(i\textsuperscript{th}\) visited hall \((x,y)\) must satisfy

[ T_{x,y} = L_i ]

There are two additional constraints on her travel route:

1. After visiting a hall at \((x,y)\), the next hall \((x', y')\) must be adjacent (sharing an edge), i.e. \(|x-x'|+|y-y'|=1\), and it must not have been visited before.
2. The starting hall must lie on the boundary of the grid, i.e. it satisfies \(x=1\) or \(x=n\) or \(y=1\) or \(y=m\).

Your task is to count the total number of valid traveling routes that visit every hall exactly once while matching the given binary sequence. Since the answer can be huge, output it modulo \(11192869\).

inputFormat

The input consists of:

1. The first line contains two integers n and m (n ≤ 3).
2. The second line contains a binary string L of length n*m.
3. The next n lines each contain m integers (each either 0 or 1) representing the values of \(T_{x,y}\) for each exhibition hall.

outputFormat

Output a single integer: the number of valid traveling routes modulo \(11192869\).

sample

2 2
1010
1 0
1 0

0