1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define mod 1000000007 6 using namespace std; 7 const int maxn=100005; 8 int f[maxn<<1],t[maxn<<2]; 9 bool vis[maxn<<1];10 int T;11 long long n,c;12 long long Pow(long long x,long long n){13     if(!n)return 1;14     long long res=Pow(x,n/2);15     res=res*res%mod;16     if(n&1)res=res*x%mod;17     return res;18 }19 long long gcd(long long a,long long b){20     return b==0?a:gcd(b,a%b);21 }22 void exgcd(long long a,long long b,long long &d,long long &x,long long &y){23     if(!b){d=a;x=1;y=0;}24     else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}25 }26 long long inv(long long a,long long n){27     long long d,x,y;28     exgcd(a,n,d,x,y);29     return d==1?(x+n)%n:-1;30 }31 void getfail(int *p){32     f[0]=f[1]=0;33     for(int i=1;i<2*n;i++){34         int j=f[i];35         while(j&&p[i]!=p[j])j=f[j];36         f[i+1]=p[i]==p[j]?j+1:0;37     }38 }39 void find(int *t){40     getfail(t);41     int j=0;42     for(int i=0;i<n*4-2;i++){43         while(j&&t[j]!=t[i])j=f[j];44         if(t[j]==t[i])j++;45         if(j==2*n){46             vis[i-(2*n-1)]=1;47             j=f[j];48         }49     }50 }51 int main(){52 //    freopen("in","r",stdin);53     scanf("%d",&T);54     while(T--){55         scanf("%I64d%I64d",&n,&c);56         for(int i=0;i<n;i++)scanf("%d",&t[2*i]);57         for(int i=0;i<n;i++)scanf("%d",&t[2*i+1]);58         for(int i=0;i<2*n;i++)t[i+2*n]=t[i];59         memset(vis,0,sizeof(bool)*(n*2+2));60         find(t);61         long long ans=0,cnt=0;62         for(int i=0;i<n;i++){63             if(vis[i<<1])ans=(ans+Pow(c,gcd(i,n)))%mod,cnt++;64         }65         ans=ans*inv(cnt,mod)%mod;66         cout<<ans<<endl;67     }68     return 0;69 }