#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=100005,mod=1000000009;
int n,m,c[3][N];
int dp[N][5];
inline ll quickPower(ll x,ll y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
namespace seg
{
	int tr[N<<2],tag[N<<2],tad[N<<2];
	void ptag(int k,int x)
	{
		if (x==1) return;
		tr[k]=tr[k]*x%mod;
		tad[k]=tad[k]*x%mod;
		tag[k]=tag[k]*x%mod;
	}
	void padd(int k,int l,int r,int x)
	{
		tr[k]=(tr[k]+x*(r-l+1)%mod)%mod;
		tad[k]=(tad[k]+x)%mod;
	}
	void pushdown(int k,int l,int r)
	{
		ptag(k<<1,tag[k]);
		ptag(k<<1|1,tag[k]);
		int mid=l+(r-l)/2;
		padd(k<<1,l,mid,tad[k]);
		padd(k<<1|1,mid+1,r,tad[k]);
		tag[k]=1;
		tad[k]=0;
	}
	void pushup(int k)
	{
		tr[k]=(tr[k<<1]+tr[k<<1|1])%mod;
	}
	void build(int k,int l,int r)
	{
		tag[k]=1;
		tad[k]=0;
		tr[k]=0;
		if (l==r) return;
		int mid=l+(r-l)/2;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
	}
	void add(int k,int l,int r,int L,int R,int x)
	{
		if (L<=l&&r<=R) 
		{
			padd(k,l,r,x);
			return;
		}
		int mid=l+(r-l)/2;
		pushdown(k,l,r);
		if (L<=mid) add(k<<1,l,mid,L,R,x);
		if (R>mid) add(k<<1|1,mid+1,r,L,R,x);
		pushup(k);
		// cout<<"fuck "<<l<<" "<<r<<" "<<tr[k]<<endl;.
	}
	void add(int k,int l,int r,int L,int x)
	{
		if (l==r)
		{
			padd(k,l,r,x);
			return;
		}
		int mid=l+(r-l)/2;
		pushdown(k,l,r);
		if (L<=mid) add(k<<1,l,mid,L,x);
		else add(k<<1|1,mid+1,r,L,x);
		pushup(k);
	}
	void mul(int k,int l,int r,int L,int R,int x)
	{
		if (L<=l&&r<=R)
		{
			ptag(k,x);
			return;
		}
		int mid=l+(r-l)/2;
		pushdown(k,l,r);
		if (L<=mid) mul(k<<1,l,mid,L,R,x);
		if (R>mid) mul(k<<1|1,mid+1,r,L,R,x);
		pushup(k);
	}
	void mul(int k,int l,int r,int L,int x)
	{
		if (l==r)
		{
			ptag(k,x);
			return;
		}
		int mid=l+(r-l)/2;
		pushdown(k,l,r);
		if (L<=mid) mul(k<<1,l,mid,L,x);
		else mul(k<<1|1,mid+1,r,L,x);
		pushup(k);
	}
	int query(int k,int l,int r,int L)
	{
		if (l==r) return tr[k];
		int mid=l+(r-l)/2;
		pushdown(k,l,r);
		if (L<=mid) return query(k<<1,l,mid,L);
		return query(k<<1|1,mid+1,r,L);
	}
}
void BellaKira()
{
	cin>>n>>m;
	for (int i=1;i<=2;i++)
		for (int j=n;j>=1;j--)
			cin>>c[i][j];
	//0 ab cd
	//1 ab ad
	//2 ab ab
	//3 ab ca
	//4 ab ba
	dp[1][2]=1;
	for (int i=2;i<=n;i++)
	{
		dp[i][0]=(
			dp[i-1][0]*((m-4)*(m-5)%mod+2*(m-4)%mod+1)%mod+
			dp[i-1][1]*(m-3)%mod*(m-3)%mod*2%mod+
			dp[i-1][2]*(m-2)%mod*(m-3)%mod+
			dp[i-1][3]*(m-3)%mod*(m-3)%mod*2%mod+
			dp[i-1][4]*(m-2)%mod*(m-3)%mod)%mod;
		dp[i][1]=(
			dp[i-1][0]*(m-3)%mod+
			dp[i-1][1]*(m-2)%mod+
			dp[i-1][3]*(m-2)%mod+
			dp[i-1][3]*(m-3)%mod+
			dp[i-1][4]*(m-2)%mod)%mod;
		dp[i][2]=(
			dp[i-1][0]+
			dp[i-1][3]*2%mod+
			dp[i-1][4])%mod;
		dp[i][3]=(
			dp[i-1][0]*(m-3)%mod+
			dp[i-1][1]*(m-2)%mod+
			dp[i-1][1]*(m-3)%mod+
			dp[i-1][2]*(m-2)%mod+
			dp[i-1][3]*(m-2)%mod)%mod;
		dp[i][4]=(
			dp[i-1][0]+
			dp[i-1][1]*2%mod+
			dp[i-1][2])%mod;
	}
	int rt=0,lst=-1;
	seg::build(1,1,m);
	for (int j=1;j<=n;j++)
	{
		if (c[1][j]==0&&c[2][j]==0)
		{
			continue;
		}
		if(lst==-1)
		{
			rt++;
			lst=j;
			if (c[1][j])
			{
				if (!c[2][j]) 
				{
					for (int i=1;i<=m;i++)
						if (i!=c[1][j]) seg::add(1,1,m,i,1);
				} else 
				{
					for (int i=c[2][j];i<=c[2][j];i++)
						if (i!=c[1][j]) seg::add(1,1,m,i,1);
				}
			} else
			{
				for (int i=1;i<=m;i++)
					if (i!=c[2][j]) seg::add(1,1,m,i,1);
			}
			continue;
		}
		//0 ab cd
		//1 ab ad
		//2 ab ab
		//3 ab ca
		//4 ab ba
		int x=(c[1][lst]>0);
		int y=(c[1][j]>0);
		if (x==y)
		{
			int o=1;
			if (c[o][lst]==0) o++;
			if (c[o][lst]==c[o][j])
			{
				int mul=(dp[j-lst+1][2]-dp[j-lst+1][1]*quickPower(m-2,mod-2)%mod+mod)%mod;
				int s=seg::tr[1];
				seg::mul(1,1,m,1,m,mul);
				seg::add(1,1,m,1,m,s*dp[j-lst+1][1]%mod*quickPower(m-2,mod-2)%mod);
				seg::mul(1,1,m,c[o][j],0);
			} else
			{
				int x=c[o][lst],y=c[o][j];
				int s=seg::tr[1],ss=seg::query(1,1,m,y);
				s=(s-ss+mod)%mod;
				//ab cd && ab cb
				{
					int mul=(dp[j-lst+1][1]*quickPower(m-2,mod-2)%mod
						-dp[j-lst+1][0]*quickPower(m-2,mod-2)%mod*quickPower(m-3,mod-2)%mod+mod)%mod;
					int coef=s*dp[j-lst+1][0]%mod*quickPower(m-2,mod-2)%mod*quickPower(m-3,mod-2)%mod;
					seg::mul(1,1,m,1,m,mul);
					seg::add(1,1,m,1,m,coef);
					seg::mul(1,1,m,y,0);
					seg::mul(1,1,m,x,0);
				}
				//ab ca
				{
					int coef=s*dp[j-lst+1][3]%mod*quickPower(m-2,mod-2)%mod;
					seg::add(1,1,m,x,coef);
				}
				//ac cd
				{
					int coef=ss*dp[j-lst+1][3]%mod*quickPower(m-2,mod-2)%mod;
					seg::add(1,1,m,1,m,coef);
					seg::add(1,1,m,y,mod-coef);
					seg::add(1,1,m,x,mod-coef);
				}
				//ac ca
				{
					int coef=ss*dp[j-lst+1][4]%mod;
					seg::add(1,1,m,x,coef);
				}
			}
			if (o==1&&c[2][j])
			{
				int p=c[2][j];
				int s=seg::query(1,1,m,p);
				seg::mul(1,1,m,1,m,0);
				seg::add(1,1,m,p,p,s);
			}
		} else
		{
			int o=1;
			if (c[o][lst]==0) o++;
			if (c[o][lst]==c[3-o][j])
			{
				int mul=(dp[j-lst+1][4]-dp[j-lst+1][3]*quickPower(m-2,mod-2)%mod+mod)%mod;
				int s=seg::tr[1];
				seg::mul(1,1,m,1,m,mul);
				seg::add(1,1,m,1,m,s*dp[j-lst+1][3]%mod*quickPower(m-2,mod-2)%mod);
				seg::mul(1,1,m,y,0);
			} else
			{
				int x=c[o][lst],y=c[3-o][j];
				int s=seg::tr[1],ss=seg::query(1,1,m,y);
				s=(s-ss+mod)%mod;
				//ab cd && ab bd
				{
					int mul=(dp[j-lst+1][3]*quickPower(m-2,mod-2)%mod
						-dp[j-lst+1][0]*quickPower(m-2,mod-2)%mod*quickPower(m-3,mod-2)%mod+mod)%mod;
					int coef=s*dp[j-lst+1][0]%mod*quickPower(m-2,mod-2)%mod*quickPower(m-3,mod-2)%mod;
					seg::mul(1,1,m,1,m,mul);
					seg::add(1,1,m,1,m,coef);
					seg::mul(1,1,m,x,0);
					seg::mul(1,1,m,y,0);
				}
				//ab ad
				{
					seg::add(1,1,m,x,s*dp[j-lst+1][1]%mod*quickPower(m-2,mod-2)%mod);
				}
				//ad cd
				{
					int coef=ss*dp[j-lst+1][1]%mod*quickPower(m-2,mod-2)%mod;
					seg::add(1,1,m,1,m,coef);
					seg::add(1,1,m,x,mod-coef);
					seg::add(1,1,m,y,mod-coef);
				}
				//ad ad
				{
					int coef=ss*dp[j-lst+1][2]%mod;
					seg::add(1,1,m,x,coef);
				}
			}
			if (o==2&&c[2][j])
			{
				int p=c[2][j];
				int s=seg::query(1,1,m,p);
				seg::mul(1,1,m,1,m,0);
				seg::add(1,1,m,p,p,s);
			}
		}
		rt+=j-lst;
		lst=j;
	}
	int op=0;
	for (int i=0;i<5;i++) op=(op+dp[n-rt][i])%mod;
	for (int i=1;i<2;i++) op=(op+dp[n-rt][i])%mod;
	for (int i=3;i<4;i++) op=(op+dp[n-rt][i])%mod;
	if (rt==0) cout<<op*m%mod*(m-1)%mod<<'\n';
	else
	{
		op=0;
		for (int i=0;i<5;i++) op=(op+dp[n-rt+1][i])%mod;
		for (int i=1;i<2;i++) op=(op+dp[n-rt+1][i])%mod;
		for (int i=3;i<4;i++) op=(op+dp[n-rt+1][i])%mod;
		cout<<seg::tr[1]*op%mod<<'\n';
	}
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
/*
a
b
*/