#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <queue>
#define fail(x) x?(puts("0"), exit(0)):void()
using namespace std;
typedef long long i64;
inline int read(int f = 1, int x = 0, char ch = ' ') {
    while (!isdigit(ch = getchar()))
        if (ch == '-')
            f = -1;

    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();

    return f * x;
}
const int P = 1e9 + 9, N = 1e5 + 5;
i64 qpow(i64 a, int b) {
    i64 c = 1;

    for (; b; b >>= 1, a = a * a % P)
        if (b & 1)
            c = c * a % P;

    return c;
}
int n, c, m, p[N], a[N], b[N];
i64 g[5][N], ans;
struct T {
    int old, now, t[N];
    i64 f[N], S, K, B;
    i64 G(i64 x) {
        return (K * x + B) % P;
    }
    void add(i64 v) {
        ++now, (S += v * c) %= P, (B += v) %= P;
    }
    void set(i64 v) {
        ++now, S = v * c % P, K = 1, B = 0, f[0] = v, old = now;
    }
    void mul(i64 v) {
        if (v)
            ++now, S = S * v % P, K = K * v % P, B = B * v % P;
        else
            set(0);
    }
    void set(int p, i64 v) {
        ++now, (S += P - G(t[p] > old ? f[p] : f[0])) %= P, t[p] = now, (S += v) %= P, f[p] = (v + P - B) * qpow(K,
                P - 2) % P;
    }
    i64 ask(int p) {
        return G(t[p] > old ? f[p] : f[0]);
    }
    i64 ask() {
        return S;
    }
} t;
int main() {
    n = read(), c = read(), t.set(0);

    for (int i = 1; i <= n; ++i)
        a[i] = read();

    for (int i = 1; i <= n; ++i)
        b[i] = read();

    for (int i = 1; i <= n; ++i)
        if (a[i] || b[i])
            p[++m] = i, fail(a[i] && a[i] == b[i]), fail(a[i] && a[i] == a[i + 1]), fail(b[i] && b[i] == b[i + 1]);

    if (!m)
        return printf("%lld\n", c * (c - 1ll) % P * qpow(((c - 1ll) * (c - 2) + 1) % P, n - 1) % P), 0;

    g[1][1] = g[3][1] = g[4][1] = 1;

    for (int i = 1; i < n; ++i)
        g[0][i + 1] = (g[1][i] + 2ll * (c - 2) * g[3][i] + (c - 2ll) * (c - 3) % P * g[4][i]) % P,
                      g[1][i + 1] = (g[0][i] + 2ll * (c - 2) * g[2][i] + (c - 2ll) * (c - 3) % P * g[4][i]) % P,
                                    g[2][i + 1] = (g[1][i] + (c - 2ll) * g[2][i] + (2 * c - 5ll) * g[3][i] % P + (c - 3ll) *
                                            (c - 3) % P * g[4][i]) % P,
                                            g[3][i + 1] = (g[0][i] + (2 * c - 5ll) * g[2][i] + (c - 2ll) * g[3][i] % P + (c - 3ll) *
                                                    (c - 3) % P * g[4][i]) % P,
                                                    g[4][i + 1] = (g[0][i] + g[1][i] + 2 * (c - 3ll) * g[2][i] + 2 * (c - 3ll) * g[3][i] + ((c - 3ll) *
                                                            (c - 4) + 1) % P * g[4][i]) % P;

    if (p[1] == 1)
        if (a[1] && b[1])
            t.set(b[1], 1);
        else if (a[1])
            t.set(1), t.set(a[1], 0);
        else
            t.set(1), t.set(b[1], 0);
    else {
        int u = p[1], w = (g[0][u - 1] + g[1][u - 1] + 2ll * (c - 2) * (g[2][u - 1] + g[3][u - 1]) + (c - 2ll) *
                           (c - 3) % P * g[4][u - 1]) % P;

        if (a[u] && b[u])
            t.set(b[u], w);
        else if (a[u])
            t.set(w), t.set(a[u], 0);
        else
            t.set(w), t.set(b[u], 0);
    }

    for (int i = 2; i <= m; ++i) {
        i64 s = t.ask(), fu;
        int w = p[i] - p[i - 1], u, v;

        if (a[p[i]]) {
            u = a[p[i]], fu = t.ask(u);

            if (a[p[i - 1]]) {
                v = a[p[i - 1]];

                if (!b[p[i]]) {
                    if (u == v)
                        t.mul((g[0][w] - g[2][w] + P) % P), t.add(s * g[2][w] % P);
                    else
                        t.mul((g[2][w] - g[4][w] + P) % P), t.add((fu * g[3][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                                (fu * g[1][w] + (s - fu + P)*g[3][w]) % P);
                } else {
                    int j = b[p[i]];
                    i64 fj = t.ask(j);
                    t.set(0);

                    if (u == v)
                        t.set(j, (fj * g[0][w] + (s - fj + P)*g[2][w]) % P);
                    else if (j == v)
                        t.set(j, (fu * g[1][w] + (s - fu + P)*g[3][w]) % P);
                    else
                        t.set(j, (fj * g[2][w] + fu * g[3][w] + (s - fj - fu + 2 * P)*g[4][w] % P) % P);
                }
            } else {
                v = b[p[i - 1]];

                if (!b[p[i]]) {
                    if (u == v)
                        t.mul((g[1][w] - g[3][w] + P) % P), t.add(s * g[3][w] % P);
                    else
                        t.mul((g[3][w] - g[4][w] + P) % P), t.add((fu * g[2][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                                (fu * g[0][w] + (s - fu + P)*g[2][w]) % P);
                } else {
                    int j = b[p[i]];
                    i64 fj = t.ask(j);
                    t.set(0);

                    if (u == v)
                        t.set(j, (fj * g[1][w] + (s - fj + P)*g[3][w]) % P);
                    else if (j == v)
                        t.set(j, (fu * g[0][w] + (s - fu + P)*g[2][w]) % P);
                    else
                        t.set(j, (fu * g[2][w] + fj * g[3][w] + (s - fj - fu + 2 * P)*g[4][w] % P) % P);
                }
            }
        } else {
            u = b[p[i]], fu = t.ask(u);

            if (a[p[i - 1]]) {
                v = a[p[i - 1]];

                if (u == v)
                    t.mul((g[1][w] - g[3][w] + P) % P), t.add(s * g[3][w] % P);
                else
                    t.mul((g[3][w] - g[4][w] + P) % P), t.add((fu * g[2][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                            (fu * g[0][w] + (s - fu + P)*g[2][w]) % P);
            } else {
                v = b[p[i - 1]];

                if (u == v)
                    t.mul((g[0][w] - g[2][w] + P) % P), t.add(s * g[2][w] % P);
                else
                    t.mul((g[2][w] - g[4][w] + P) % P), t.add((fu * g[3][w] + (s - fu + P)*g[4][w]) % P), t.set(v,
                            (fu * g[1][w] + (s - fu + P)*g[3][w]) % P);
            }
        }

        t.set(u, 0);
    }

    if (p[m] == n)
        ans = t.ask();
    else {
        int u = n - p[m], w = (g[0][u] + g[1][u] + 2ll * (c - 2) * (g[2][u] + g[3][u]) + (c - 2ll) *
                               (c - 3) % P * g[4][u]) % P;
        ans = t.ask() * w % P;
    }

    printf("%lld\n", ans);
    return 0;
}