To improve his IQ, ZJY went on a trip to a new world. However, after the trip, ZJY sadly discovered that to open the door back to his original world, he must solve a puzzle drawn on the door. The puzzle is as follows: there is a chessboard with $n$ rows and $m$ columns, on which many special chess pieces can be placed. The attack range of each piece is 3 rows and $p$ columns. The input data provides a $3 \times p$ matrix representing the attack range template. A piece is assumed to be at the 1st row and $k$-th column of the template. Positions that the piece can attack are marked as 1, and positions it cannot attack are marked as 0. We have $1 \le p \le m$ and $0 \le k < p$, and the input guarantees that the position at the 1st row and $k$-th column is 1. The password to open the door is the number of ways to place the pieces such that no two pieces attack each other. Note that placing no pieces at all is also considered a valid configuration. Since the number of ways can be very large, and the password is a 32-bit binary code, ZJY only needs to know the result of the number of ways modulo $2^{32}$.

Input

The first line of the input contains two integers $n$ and $m$, representing the size of the chessboard. The second line contains two integers $p$ and $k$, representing the size of the attack range template and the position of the piece within the template. The next three lines each contain $p$ numbers, representing the attack range template. Each number is followed by a space.

Output

The output contains a single integer, representing the number of valid configurations modulo $2^{32}$.

Constraints

• For 10% of the data: $1 \le n \le 5$, $1 \le m \le 5$
• For 50% of the data: $1 \le n \le 1000$, $1 \le m \le 6$
• For 100% of the data: $1 \le n \le 1000000$, $1 \le m \le 6$

Examples

Input 1

2 2
3 1
0 1 0
1 1 1
0 1 0

Output 1

7