You are given a $2 \times n$ grid graph. Some nodes have known colors, while the remaining nodes are uncolored. A valid coloring scheme does not allow any two adjacent nodes to have the same color.

There are $c$ different colors available, labeled from $1$ to $c$. How many valid coloring schemes are there for the uncolored nodes?

Input

The first line contains two integers $n$ and $c$, representing the size of the grid and the total number of colors, respectively.

The next two lines each contain $n$ integers. If an integer is $0$, it means the corresponding node is uncolored; otherwise, it is an integer from $1$ to $c$, representing the color already assigned to that node.

Output

Output a single integer representing the total number of valid coloring schemes modulo $10^9 + 9$.

Examples

Input 1

3 5
1 0 1
0 0 0

Output 1

172

Input 2

5 7
1 0 0 0 2
0 0 3 0 0

Output 2

116370

Input 3

10 13
0 2 0 0 1 0 2 0 0 3
0 1 0 1 0 0 0 0 4 0

Output 3

770175525

Subtasks

• Subtask 1 (44 points): $1 \le n \le 10000$ and $5 \le c \le 10000$; no column has 2 colored nodes; all colored nodes are in the first row; the first and last columns both have at least one colored node.
• Subtask 2 (32 points): $1 \le n \le 10000$ and $5 \le c \le 10000$; no column has 2 colored nodes; the first and last columns both have at least one colored node.
• Subtask 3 (12 points): $1 \le n \le 10000$ and $5 \le c \le 10000$; the first and last columns both have at least one colored node.
• Subtask 4 (8 points): $1 \le n \le 10000$ and $5 \le c \le 10000$.
• Subtask 5 (4 points): $1 \le n \le 100000$ and $5 \le c \le 100000$.