#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int N = 1e5 + 10, mod = 1e9 + 9;
int n, m, w[N][3];
int f[N][10];//不等，1个交叉，1行，2个交叉，2行 
vector<int> pos;
struct tree
{
	int l, r;
	int sum;
	int mul = 1, add;
}a[N * 4];

LL ksm(LL x, LL y)
{
	LL res = 1;
	x %= mod;
	while(y)
	{
		if(y & 1) res = res * x % mod;
		y >>= 1;
		x = x * x % mod;
	}
	return res;
}

void init()
{
	f[0][1] = f[0][2] = f[0][4] = 1;
	for(int i = 1; i <= n; i++)
	{
		f[i][1] = ((1ll * m * m + 1ll * (mod - 7) * m + 13) % mod * f[i - 1][1]
				+  (2ll * m + mod - 6) % mod * f[i - 1][2]
				+  (2ll * m + mod - 6) % mod * f[i - 1][3]
				+  f[i - 1][4]
				+  f[i - 1][5]) % mod;
		f[i][2] = ((1ll * m * m + 1ll * (mod - 6) * m + 9) % mod * f[i - 1][1]
				+  (m + mod - 2) % mod * f[i - 1][2]
				+  (2ll * m + mod - 5) % mod * f[i - 1][3]
				+  f[i - 1][5]) % mod;
		f[i][3] = ((1ll * m * m + 1ll * (mod - 6) * m + 9) % mod * f[i - 1][1]
				+  (2ll * m + mod - 5) % mod * f[i - 1][2]
				+  (m + mod - 2) % mod * f[i - 1][3]
				+  f[i - 1][4]) % mod;
		f[i][4] = ((1ll * m * m + 1ll * (mod - 5) * m + 6) % mod * f[i - 1][1]
				+  (2ll * m + mod - 4) % mod * f[i - 1][3]
				+  f[i - 1][5]) % mod;
		f[i][5] = ((1ll * m * m + 1ll * (mod - 5) * m + 6) % mod * f[i - 1][1]
				+  (2ll * m + mod - 4) % mod * f[i - 1][2]
				+  f[i - 1][4]) % mod;
	}
}

inline void pushup(int p)
{
	a[p].sum = (a[p << 1].sum + a[p << 1 | 1].sum) % mod;
}
inline void pushdown(tree &a, tree &x, tree &y)
{
	if(a.mul != 1)
	{
		x.sum = 1ll * x.sum * a.mul % mod, y.sum = 1ll * y.sum * a.mul % mod;
		x.mul = 1ll * x.mul * a.mul % mod, y.mul = 1ll * y.mul * a.mul % mod;
		x.add = 1ll * x.add * a.mul % mod, y.add = 1ll * y.add * a.mul % mod;
		a.mul = 1;
	}
	if(a.add)
	{
		x.sum = (x.sum + 1ll * (x.r - x.l + 1) * a.add) % mod,
		y.sum = (y.sum + 1ll * (y.r - y.l + 1) * a.add) % mod;
		x.add = (x.add + a.add) % mod, y.add = (y.add + a.add) % mod, a.add = 0;
	}
}
inline void pushdown(int p)
{
	pushdown(a[p], a[p << 1], a[p << 1 | 1]);
}

void maketree(int p, int l, int r)
{
	a[p].l = l, a[p].r = r;
	if(l != r)
	{
		int mid = l + r >> 1;
		maketree(p << 1, l, mid);
		maketree(p << 1 | 1, mid + 1, r);
	}
}

void modify(int p, int l, int r, int mul, int add)
{
	if(l > r) return;
	if(l <= a[p].l && a[p].r <= r)
	{
		a[p].sum = (1ll * a[p].sum * mul + 1ll * (a[p].r - a[p].l + 1) * add) % mod,
		a[p].mul = 1ll * a[p].mul * mul % mod, a[p].add = (1ll * a[p].add * mul + add) % mod;
		return;
	}
	
	pushdown(p);
	int mid = a[p].l + a[p].r >> 1;
	if(l <= mid) modify(p << 1, l, r, mul, add);
	if(r > mid) modify(p << 1 | 1, l, r, mul, add);
	pushup(p);
}

int getsum(int p, int x)
{
	if(a[p].l == a[p].r)
		return a[p].sum;
	
	pushdown(p);
	int mid = a[p].l + a[p].r >> 1;
	if(x <= mid) return getsum(p << 1, x);
	else return getsum(p << 1 | 1, x);
}

void work1(int x, int y, int g[])//交叉
{
	if(x == y)
		modify(1, 1, m, (g[4] - g[2] + mod) % mod, 1ll * a[1].sum * g[2] % mod);
	else
	{
		int t = (a[1].sum * g[3] + 1ll * getsum(1, y) * (g[5] - g[3] + mod)) % mod;
		modify(1, 1, m, (g[2] - g[1] + mod) % mod, (1ll * a[1].sum * g[1] + 1ll * getsum(1, y) * (g[3] - g[1] + mod)) % mod);
		modify(1, x, x, 0, t);
	}
}

void work2(int x, int y, int g[])//同行 
{
	if(x == y)
		modify(1, 1, m, (g[5] - g[3] + mod) % mod, 1ll * a[1].sum * g[3] % mod);
	else
	{
		int t = (a[1].sum * g[2] + 1ll * getsum(1, y) * (g[4] - g[2] + mod)) % mod;
		modify(1, 1, m, (g[3] - g[1] + mod) % mod, (1ll * a[1].sum * g[1] + 1ll * getsum(1, y) * (g[2] - g[1] + mod)) % mod);
		modify(1, x, x, 0, t);
	}
}

int main()
{
	cin >> n >> m;
	init();
	
	for(int j = 1; j <= 2; j++)
		for(int i = 1; i <= n; i++)
			scanf("%d", &w[i][j]);
	for(int i = 1; i <= n; i++)
		if(w[i][1] || w[i][2])
		{
			if(w[i][1] == w[i][2]) return puts("0"), 0;
			pos.push_back(i);
		}
	if(pos.empty())
	{
		cout << ksm(1ll * m * m + 1ll * (mod - 3) * m + 3, n - 1) * m % mod * (m - 1) % mod << endl;
		return 0;
	}
	
	maketree(1, 1, m);
	if(w[pos[0]][1])
	{
		if(w[pos[0]][2])
			modify(1, w[pos[0]][2], w[pos[0]][2], 1, 1);
		else
			modify(1, 1, w[pos[0]][1] - 1, 1, 1), modify(1, w[pos[0]][1] + 1, m, 1, 1);
	}
	else
		modify(1, 1, w[pos[0]][2] - 1, 1, 1), modify(1, w[pos[0]][2] + 1, m, 1, 1);
	
	for(int i = 1; i < pos.size(); i++)
	{
		int p = pos[i - 1], x = pos[i], *g = f[x - p - 1];
		if(w[x][1])
		{
			if(w[p][1]) work2(w[p][1], w[x][1], g);
			else work1(w[p][2], w[x][1], g);
			modify(1, w[x][1], w[x][1], 0, 0);
			if(w[x][2]) modify(1, 1, w[x][2] - 1, 0, 0), modify(1, w[x][2] + 1, m, 0, 0);
		}
		else
		{
			if(w[p][1]) work1(w[p][1], w[x][2], g);
			else work2(w[p][2], w[x][2], g);
			modify(1, w[x][2], w[x][2], 0, 0);
		}
	}
	
	cout << a[1].sum * ksm(1ll * m * m + 1ll * (mod - 3) * m + 3, pos[0] - 1 + n - pos.back()) % mod << endl;
	return 0;
}