据说是很套路的题
考虑显然一段连续为的答案可以预处理出来
分类讨论最左右2行分别是什么情况
发现只有5种（实际上是7种，有2种可以合并）
然后可以先出表示中间空的长度为
左右为上面第几种类型的的方案数
再设表示第列，填入的颜色为（如果有要填颜色的则为要填的颜色，否则记为第二行的那个颜色）的方案数
发现就可以直接枚举每一段大力分类讨论转移了
特别处理一下第一个前和最后一个后的空行的情况
这样可以拿到分
在观察一下每次转移的
有单点赋值、全局乘，全局加，全局覆盖，全局求和，单点求值
发现和前面没什么区别
复杂度
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>
cs int mod=1e9+9;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:0;}
inline void Dec(int &a,int b){(a-=b)<0?a+=mod:0;}
inline void Mul(int &a,int b){a=1ll*a*b%mod;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int N=100005;
int a[N],b[N],n,c,f[N][5];
int tmp[N],g[N];
int pos[N],tot;
inline void trans(int a1,int b1,int a2,int b2,int x){
int all=0;
for(int i=1;i<=c;i++)Add(all,g[i]);
if(a1&&a2&&b1&&b2){
if(a1==a2&&b1==b2)tmp[b2]=mul(g[b1],f[x][3]);
else if((a1==a2)+(b1==b2)==1)tmp[b2]=mul(g[b1],f[x][2]);
else if((a1==b2)+(a2==b1)==2)tmp[b2]=mul(g[b1],f[x][4]);
else if((a1==b2)+(a2==b1)==1)tmp[b2]=mul(g[b1],f[x][1]);
else tmp[b2]=mul(g[b1],f[x][0]);
}
if((a1&&b1)+(a2&&b2)==0){
if(!a1)swap(a1,b1),swap(a2,b2);
int now=dec(all,g[a1]);
if(!a2){
if(b2==a1){
for(int i=1;i<=c;i++)if(i!=b2)Add(tmp[i],mul(g[i],f[x][4])),Add(tmp[i],mul(dec(now,g[i]),f[x][1]));
}
else{
for(int i=1;i<=c;i++)if(i!=b2){
if(i==a1){
Add(tmp[i],mul(dec(now,g[b2]),f[x][2]));
Add(tmp[i],mul(g[b2],f[x][3]));
}
else{
Add(tmp[i],mul(dec(dec(now,g[i]),g[b2]),f[x][0]));
Add(tmp[i],mul(g[i],f[x][1]));
Add(tmp[i],mul(g[b2],f[x][2]));
}
}
}
}
if(!b2){
if(a2==a1){for(int i=1;i<=c;i++)if(i!=a2)Add(tmp[i],mul(g[i],f[x][3])),Add(tmp[i],mul(dec(now,g[i]),f[x][2]));}
else{
for(int i=1;i<=c;i++)if(i!=a2){
if(i==a1){
Add(tmp[i],mul(g[a2],f[x][4]));
Add(tmp[i],mul(dec(now,g[a2]),f[x][1]));
}
else{
Add(tmp[i],mul(dec(dec(now,g[a2]),g[i]),f[x][0]));
Add(tmp[i],mul(g[a2],f[x][1]));
Add(tmp[i],mul(g[i],f[x][2]));
}
}
}
}
}
if((a1&&b1)&&(!a2||!b2)){
int now=g[b1];
if(!a2)swap(a1,b1),swap(a2,b2);
if(a1==a2){
for(int i=1;i<=c;i++)if(i!=a2){if(i==b1)Add(tmp[i],mul(now,f[x][3]));else Add(tmp[i],mul(now,f[x][2]));}
}
else if(b1==a2){
for(int i=1;i<=c;i++)if(i!=a2){if(i==b1)Add(tmp[i],mul(now,f[x][4]));else Add(tmp[i],mul(now,f[x][1]));}
}
else for(int i=1;i<=c;i++)if(i!=a2){
if(i==a1)Add(tmp[i],mul(now,f[x][1]));
else if(i==b1)Add(tmp[i],mul(now,f[x][2]));
else Add(tmp[i],mul(now,f[x][0]));
}
}
if((!a1||!b1)&&(a2&&b2)){
int pp=b2;
if(!a1)swap(a1,b1),swap(a2,b2);
if(a1==a2){
for(int i=1;i<=c;i++)if(i==b2)Add(tmp[pp],mul(g[i],f[x][3]));else Add(tmp[pp],mul(g[i],f[x][2]));
}
else if(a1==b2){
for(int i=1;i<=c;i++)if(i==a1)Add(tmp[pp],mul(g[i],f[x][4]));else Add(tmp[pp],mul(g[i],f[x][1]));
}
else{
for(int i=1;i<=c;i++){
if(i==a2)Add(tmp[pp],mul(g[i],f[x][1]));
else if(i==b2)Add(tmp[pp],mul(g[i],f[x][2]));
else Add(tmp[pp],mul(g[i],f[x][0]));
}
}
}
memcpy(g,tmp,sizeof(tmp));memset(tmp,0,sizeof(tmp));
}
int main(){
n=read(),c=read();
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]&&(a[i]==a[i+1]||a[i]==b[i])){
puts("0");return 0;
}
for(int i=1;i<=n;i++)
if(b[i]&&b[i]==b[i+1]){
puts("0");return 0;
}
for(int i=1;i<=n;i++)
if(a[i]||b[i])pos[++tot]=i;
f[0][0]=1,f[0][1]=1,f[0][4]=1;
ll a1=add(mul(c-4,c-4),(c-3)),a2=mul(c-3,c-3),a3=mul(c-2,c-3);
for(int i=1;i<=n;i++){
f[i][0]=(a1*f[i-1][0]+2ll*(c-3)*f[i-1][1]+2ll*(c-3)*f[i-1][2]+f[i-1][3]+f[i-1][4])%mod;
f[i][1]=(a2*f[i-1][0]+1ll*(c-2)*f[i-1][1]+1ll*(2*c-5)*f[i-1][2]+f[i-1][3])%mod;
f[i][2]=(a2*f[i-1][0]+1ll*(2*c-5)*f[i-1][1]+1ll*(c-2)*f[i-1][2]+f[i-1][4])%mod;
f[i][3]=(a3*f[i-1][0]+2ll*(c-2)*f[i-1][1]+f[i-1][4])%mod;
f[i][4]=(a3*f[i-1][0]+2ll*(c-2)*f[i-1][2]+f[i-1][3])%mod;
}
if(a[1]&&b[1])g[b[1]]=1;
else if(a[1]||b[1]){
for(int i=1;i<=c;i++)if(i==a[1]||i==b[1])g[i]=0;else g[i]=1;
}
else {
int u=pos[1];
if(a[u]&&b[u]){
g[b[u]]=(a3*f[u-2][0]+2ll*(c-2)*f[u-2][1]+2ll*(c-2)*f[u-2][2]+f[u-2][3]+f[u-2][4])%mod;
}
else for(int i=1;i<=c;i++)
if(i!=a[u]&&i!=b[u])g[i]=(a3*f[u-2][0]+2ll*(c-2)*f[u-2][1]+2ll*(c-2)*f[u-2][2]+f[u-2][3]+f[u-2][4])%mod;
else g[i]=0;
}
for(int i=2;i<=tot;i++){
int u=pos[i]-pos[i-1]-1;
trans(a[pos[i-1]],b[pos[i-1]],a[pos[i]],b[pos[i]],u);
}
int ans=0;
if(pos[tot]==n)
for(int i=1;i<=c;i++)Add(ans,g[i]);
else{
int u=n-pos[tot]-1;
for(int i=1;i<=c;i++)Add(ans,mul((a3*f[u][0]+2ll*(c-2)*f[u][1]+2ll*(c-2)*f[u][2]+f[u][3]+f[u][4])%mod,g[i]));
}
cout<<ans;
}
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>
cs int mod=1e9+9;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline void Add(int &a,int b){(a+=b)>=mod?a-=mod:0;}
inline void Dec(int &a,int b){(a-=b)<0?a+=mod:0;}
inline void Mul(int &a,int b){a=1ll*a*b%mod;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int N=100005;
int a[N],b[N],n,c,f[N][5];
int tmp[N],g[N];
int pos[N],tot;
namespace cyk{
int mtag=1,atag,last,sum,f[N],stk[N],top;
inline void init(){
memset(f,-1,sizeof(f));
}
inline void clear(){
while(top)f[stk[top--]]=-1;
}
inline void update(int x,int y){
int k=mul(dec(y,atag),Inv(mtag));
if(~f[x])Dec(sum,f[x]),f[x]=k,Add(sum,k);
else Dec(sum,last),f[x]=k,Add(sum,k),stk[++top]=x;
}
inline void pushadd(int x){
Add(atag,x);
}
inline void pushmul(int x){
if(x==0)clear(),last=0,sum=0,atag=0,mtag=1;
else Mul(atag,x),Mul(mtag,x);
}
inline void pushcov(int x){
clear(),sum=mul(x,c),last=x,atag=0,mtag=1;
}
inline int ask(int x){
int res=last;
if(~f[x])res=f[x];
Mul(res,mtag),Add(res,atag);
return res;
}
inline int query(){
return add(mul(sum,mtag),mul(c,atag));
}
}
using cyk::ask;
using cyk::pushcov;
using cyk::pushmul;
using cyk::pushadd;
using cyk::update;
using cyk::clear;
using cyk::query;
using cyk::init;
inline void trans(int a1,int b1,int a2,int b2,int x){
int all=query();
if(a1&&a2&&b1&&b2){
int val=ask(b1);
if(a1==a2&&b1==b2)Mul(val,f[x][3]);
else if((a1==a2)+(b1==b2)==1)Mul(val,f[x][2]);
else if((a1==b2)+(a2==b1)==2)Mul(val,f[x][4]);
else if((a1==b2)+(a2==b1)==1)Mul(val,f[x][1]);
else Mul(val,f[x][0]);
clear(),update(b2,val);
}
if((a1&&b1)+(a2&&b2)==0){
if(!a1)swap(a1,b1),swap(a2,b2);
int now=dec(all,ask(a1));
if(!a2){
if(b2==a1){
pushmul(dec(f[x][4],f[x][1]));
pushadd(mul(now,f[x][1]));
}
else{
int val=ask(b2);
int vala1=add(mul(now,f[x][2]),mul(val,dec(f[x][3],f[x][2])));
pushmul(dec(f[x][1],f[x][0]));
pushadd(mul(val,dec(f[x][2],f[x][0])));
pushadd(mul(now,f[x][0]));
update(a1,vala1);
}
update(b2,0);
}
if(!b2){
if(a2==a1){
pushmul(dec(f[x][3],f[x][2]));
pushadd(mul(now,f[x][2]));
}
else{
int val=ask(a2);
int vala1=add(mul(now,f[x][1]),mul(val,dec(f[x][4],f[x][1])));
pushmul(dec(f[x][2],f[x][0]));
pushadd(mul(val,dec(f[x][1],f[x][0])));
pushadd(mul(now,f[x][0]));
update(a1,vala1);
}
update(a2,0);
}
}
if((a1&&b1)&&(!a2||!b2)){
int now=ask(b1);
if(!a2)swap(a1,b1),swap(a2,b2);
if(a1==a2){
int valb1=mul(now,f[x][3]);
pushcov(mul(now,f[x][2]));
update(b1,valb1);
}
else if(b1==a2){
int valb1=mul(now,f[x][4]);
pushcov(mul(now,f[x][1]));
update(b1,valb1);
}
else{
int vala1=mul(now,f[x][1]);
int valb1=mul(now,f[x][2]);
pushcov(mul(now,f[x][0]));
update(a1,vala1);
update(b1,valb1);
}
update(a2,0);
}
if((!a1||!b1)&&(a2&&b2)){
int pp=b2;
if(!a1)swap(a1,b1),swap(a2,b2);
if(a1==a2){
int tot=query();
int val=ask(b2);
clear();
update(pp,add(mul(dec(tot,val),f[x][2]),mul(val,f[x][3])));
}
else if(a1==b2){
int tot=query();
int val=ask(a1);
clear();
update(pp,add(mul(dec(tot,val),f[x][1]),mul(val,f[x][4])));
}
else{
int tot=query();
int val1=ask(a2),val2=ask(b2);
clear();
update(pp,add(add(mul(f[x][1],val1),mul(f[x][2],val2)),mul(dec(dec(tot,val1),val2),f[x][0])));
}
}
}
int main(){
n=read(),c=read(),init();
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]&&(a[i]==a[i+1]||a[i]==b[i])){
puts("0");return 0;
}
for(int i=1;i<=n;i++)
if(b[i]&&b[i]==b[i+1]){
puts("0");return 0;
}
for(int i=1;i<=n;i++)
if(a[i]||b[i])pos[++tot]=i;
f[0][0]=1,f[0][1]=1,f[0][4]=1;
ll a1=add(mul(c-4,c-4),(c-3)),a2=mul(c-3,c-3),a3=mul(c-2,c-3);
for(int i=1;i<=n;i++){
f[i][0]=(a1*f[i-1][0]+2ll*(c-3)*f[i-1][1]+2ll*(c-3)*f[i-1][2]+f[i-1][3]+f[i-1][4])%mod;
f[i][1]=(a2*f[i-1][0]+1ll*(c-2)*f[i-1][1]+1ll*(2*c-5)*f[i-1][2]+f[i-1][3])%mod;
f[i][2]=(a2*f[i-1][0]+1ll*(2*c-5)*f[i-1][1]+1ll*(c-2)*f[i-1][2]+f[i-1][4])%mod;
f[i][3]=(a3*f[i-1][0]+2ll*(c-2)*f[i-1][1]+f[i-1][4])%mod;
f[i][4]=(a3*f[i-1][0]+2ll*(c-2)*f[i-1][2]+f[i-1][3])%mod;
}
if(a[1]&&b[1])g[b[1]]=1;
else if(a[1]||b[1]){
for(int i=1;i<=c;i++)if(i==a[1]||i==b[1])g[i]=0;else g[i]=1;
}
else {
int u=pos[1];
if(a[u]&&b[u]){
g[b[u]]=(a3*f[u-2][0]+2ll*(c-2)*f[u-2][1]+2ll*(c-2)*f[u-2][2]+f[u-2][3]+f[u-2][4])%mod;
}
else for(int i=1;i<=c;i++)
if(i!=a[u]&&i!=b[u])g[i]=(a3*f[u-2][0]+2ll*(c-2)*f[u-2][1]+2ll*(c-2)*f[u-2][2]+f[u-2][3]+f[u-2][4])%mod;
else g[i]=0;
}
for(int i=1;i<=c;i++)update(i,g[i]);
for(int i=2;i<=tot;i++){
int u=pos[i]-pos[i-1]-1;
trans(a[pos[i-1]],b[pos[i-1]],a[pos[i]],b[pos[i]],u);
}
int ans=0;
if(pos[tot]==n)
ans=query();
else{
int u=n-pos[tot]-1;
for(int i=1;i<=c;i++)Add(ans,mul((a3*f[u][0]+2ll*(c-2)*f[u][1]+2ll*(c-2)*f[u][2]+f[u][3]+f[u][4])%mod,ask(i)));
}
cout<<ans;
}