Problem Description

Given a grid graph of size $2 \times n$. Some nodes have known colors, while others are uncolored.

A valid coloring scheme does not allow adjacent nodes to have the same color.

There are $c$ different colors, labeled from $1$ to $c$.

How many valid coloring schemes are there for the uncolored nodes?

Input Format

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

The next two lines each contain $n$ integers: if it is $0$, it indicates that the corresponding node is uncolored; otherwise, it is an integer between $1$ and $c$, indicating that the corresponding node has been colored.

Output Format

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

Sample Input and Output

Sample Input #1

3 5
1 0 1
0 0 0

Sample Output #1

172

Sample Input #2

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

Sample Output #2

116370

Sample Input #3

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

Sample Output #3

770175525

Notes

Subtask $1$: (44 points) $1 \le n \le 10000$ and $5 \le c \le 10000$; no column has two colored nodes; all colored nodes are in the first row; both the first and last columns have colored nodes.

Subtask $2$: (32 points) $1 \le n \le 10000$ and $5 \le c \le 10000$; no column has two colored nodes; both the first and last columns have colored nodes.

Subtask $3$: (12 points) $1 \le n \le 10000$ and $5 \le c \le 10000$; both the first and last columns have colored nodes.

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$.

见题面 Input 部分

见题面 Output 部分