#include <iostream>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 1e5 + 10, mod = 1e9 + 9;

int n, a[MAXN][2];
ll c;

ll g[MAXN][5];
inline void CalcG()
{
    g[1][0] = 0, g[1][1] = 0, g[1][2] = 1, g[1][3] = 1, g[1][4] = 1;
    for (int i = 2; i <= n; i++)
    {
        g[i][0] = (g[i - 1][2] + g[i - 1][3] * (2 * c - 4) + g[i - 1][4] * (c * c % mod - 5 * c + 6)) % mod;
        g[i][1] = (g[i - 1][1] * (c - 2) + g[i - 1][2] + g[i - 1][3] * (2 * c - 5) + g[i - 1][4] * (c * c % mod - 6 * c + 9)) % mod;
        g[i][2] = (g[i - 1][0] + g[i - 1][1] * (2 * c - 4) + g[i - 1][4] * (c * c % mod - 5 * c + 6)) % mod;
        g[i][3] = (g[i - 1][0] + g[i - 1][1] * (2 * c - 5) + g[i - 1][3] * (c - 2) + g[i - 1][4] * (c * c % mod - 6 * c + 9)) % mod;
        g[i][4] = (g[i - 1][0] + g[i - 1][1] * (2 * c - 6) + g[i - 1][2] + g[i - 1][3] * (2 * c - 6) + g[i - 1][4] * (c * c % mod - 7 * c + 13)) % mod;
    }
}

int id[MAXN], tot;
inline ll TYPE(int u, int v)
{
    if (a[u][0] == a[v][0] && a[u][1] == a[v][1]) return g[u - v][0];
    if (a[u][0] == a[v][0] || a[u][1] == a[v][1]) return g[u - v][1];
    if (a[u][0] == a[v][1] && a[u][1] == a[v][0]) return g[u - v][2];
    if (a[u][0] == a[v][1] || a[u][1] == a[v][0]) return g[u - v][3];
    return g[u - v][4];
}

inline ll Qpow(ll x, int y = mod - 2) {ll res = 1; while (y) (y & 1) && (res = res * x % mod), x = x * x % mod, y >>= 1; return res;}

namespace Structure
{
    ll Sum = 0;
    ll mdf = 0, mul = 1, add = 0, pmdf[MAXN];
    int gt = 0, pt[MAXN], cur = 0;
    inline void ModifyAll(ll k)
    {
        mdf = k, mul = 1, add = 0, gt = ++cur;
        Sum = k * c % mod;
    }
    inline void AddAll(ll k)
    {
        add = (add + k) % mod;
        Sum = (Sum + k * c) % mod;
    }
    inline void MulAll(ll k)
    {
        k %= mod;
        if (k == 0) return ModifyAll(0), void();
        mul = mul * k % mod, add = add * k % mod;
        Sum = Sum * k % mod;
    }
    inline void ModifyPoint(int x, ll k)
    {
        Sum = (Sum - (pt[x] < gt ? mdf : pmdf[x]) * mul - add) % mod;
        pmdf[x] = (k - add) * Qpow(mul) % mod, pt[x] = ++cur;
        Sum = (Sum + k) % mod;
    }
    inline ll QuerySum()
    {
        return Sum;
    }
    inline ll QueryPoint(int x)
    {
        return ((pt[x] < gt ? mdf : pmdf[x]) * mul + add) % mod;
    }
}
using namespace Structure;


int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n), Read(c);
    for (int i = 1; i <= n; i++) Read(a[i][0]);
    for (int i = 1; i <= n; i++) Read(a[i][1]);

    for (int i = 1; i <= n; i++)
        if (a[i][0] || a[i][1])
        {
            id[++tot] = i;
            if (a[i][0] == a[i][1]) return cout << "0\n", 0;
        }
    CalcG();
    
    if (!tot) return cout << (c * (c - 1) % mod * Qpow(c * c % mod - 3 * c + 3, n - 1) % mod + mod) % mod << '\n', 0;
    bool REV = 0;
    if (a[id[1]][0] && a[id[1]][1]) ModifyPoint(a[id[1]][1], 1);
    else
    {
        if (a[id[1]][1]) swap(a[id[1]][0], a[id[1]][1]), REV = 1;
        ModifyAll(1), ModifyPoint(a[id[1]][0], 0);
    }
    for (int i = 2; i <= tot; i++)
    {
        int u = id[i], v = id[i - 1];
        if (REV) swap(a[u][0], a[u][1]);
        if (a[u][0] && a[u][1])
        {
            if (a[v][0] && a[v][1])
            {
                ll val = QueryPoint(a[v][1]) * TYPE(u, v) % mod;
                ModifyPoint(a[v][1], 0), ModifyPoint(a[u][1], val);
            }
            else if (a[v][0] == a[u][0])
            {
                ll val = QueryPoint(a[u][1]), sum = QuerySum() - val;
                ModifyAll(0), ModifyPoint(a[u][1], (val * g[u - v][0] + sum * g[u - v][1]) % mod);
            }
            else if (a[v][0] == a[u][1])
            {
                ll val = QueryPoint(a[u][0]), sum = QuerySum() - val;
                ModifyAll(0), ModifyPoint(a[u][1], (val * g[u - v][2] + sum * g[u - v][3]) % mod);
            }
            else
            {
                ll val1 = QueryPoint(a[u][0]), val2 = QueryPoint(a[u][1]), sum = QuerySum() - val1 - val2;
                ModifyAll(0), ModifyPoint(a[u][1], (val1 * g[u - v][3] + val2 * g[u - v][1] + sum * g[u - v][4]) % mod);
            }
        }
        else if (a[u][0])
        {
            if (a[v][0] && a[v][1])
            {
                ll val = QueryPoint(a[v][1]);
                if (a[u][0] == a[v][0]) ModifyAll(val * g[u - v][1] % mod), ModifyPoint(a[v][1], val * g[u - v][0] % mod);
                else if (a[u][0] == a[v][1]) ModifyAll(val * g[u - v][3] % mod), ModifyPoint(a[v][0], val * g[u - v][2] % mod);
                else ModifyAll(val * g[u - v][4] % mod), ModifyPoint(a[v][0], val * g[u - v][3] % mod), ModifyPoint(a[v][1], val * g[u - v][1] % mod);
            }
            else if (a[v][0] == a[u][0])
            {
                ll sum = QuerySum();
                MulAll(g[u - v][0] - g[u - v][1]), AddAll(sum * g[u - v][1] % mod);
            }
            else
            {
                ll val = QueryPoint(a[u][0]), sum = QuerySum();
                MulAll(g[u - v][1] - g[u - v][4]), AddAll((sum * g[u - v][4] + val * (g[u - v][3] - g[u - v][4])) % mod);
                ModifyPoint(a[v][0], (val * g[u - v][2] + (sum - val) * g[u - v][3]) % mod);
            }
            ModifyPoint(a[u][0], 0);
        }
        else
        {
            if (a[v][0] && a[v][1])
            {
                ll val = QueryPoint(a[v][1]);
                if (a[u][1] == a[v][1]) ModifyAll(val * g[u - v][1] % mod), ModifyPoint(a[v][0], val * g[u - v][0] % mod);
                else if (a[u][1] == a[v][0]) ModifyAll(val * g[u - v][3] % mod), ModifyPoint(a[v][1], val * g[u - v][2] % mod);
                else ModifyAll(val * g[u - v][4] % mod), ModifyPoint(a[v][1], val * g[u - v][3] % mod), ModifyPoint(a[v][0], val * g[u - v][1] % mod);
            }
            else if (a[v][0] == a[u][1])
            {
                ll sum = QuerySum();
                MulAll(g[u - v][2] - g[u - v][3]), AddAll(sum * g[u - v][3] % mod);
            }
            else
            {
                ll val = QueryPoint(a[u][1]), sum = QuerySum();
                MulAll(g[u - v][3] - g[u - v][4]), AddAll((sum * g[u - v][4] + val * (g[u - v][1] - g[u - v][4])) % mod);
                ModifyPoint(a[v][0], (val * g[u - v][0] + (sum - val) * g[u - v][1]) % mod);
            }
            ModifyPoint(a[u][1], 0);
            REV ^= 1, swap(a[u][0], a[u][1]);
        }
    }
    ll ans = QuerySum() * Qpow(c * c % mod - 3 * c + 3, id[1] - 1 + n - id[tot]) % mod;
    cout << (ans + mod) % mod << "\n";
    return 0;
}