//可以看出f在定义域[0,n-1]中是循环的，f的每个循环节中只要有一个f的值确定了那么其他的f的值也就确定了(
//因为每相邻的两个f都相关)，所以先找出a数列的所有的循环节然后在b中找f可以对应的值(同样是循环节)，只有b
//的某个循环节是a的某个循环节的因子时这两个循环节才能匹配，统计能匹配的个数，结果相乘。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=100009;
const ll mod=1e9+7;
int n,m,a[maxn],b[maxn];
int num1[maxn],num2[maxn];//num1[i]表示a数列第i个循环节的大小，num2[i]表示b数列长度为i的循环节的个数
int main()
{
    int cas=0;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        memset(num2,0,sizeof(num2));
        memset(num1,0,sizeof(num1));

        int tot=0;
        for(int i=0;i<n;i++){
            if(a[i]==-1) continue;
            int ii=i;
            tot++;
            while(a[ii]!=-1){
                num1[tot]++;
                int t=ii;
                ii=a[ii];
                a[t]=-1;
            }
        }
        for(int i=0;i<m;i++){
            if(b[i]==-1) continue;
            int ii=i,len=0;
            while(b[ii]!=-1){
                len++;
                int t=ii;
                ii=b[ii];
                b[t]=-1;
            }
            num2[len]++;
        }
        ll sum=1;
        for(int i=1;i<=tot;i++){
            ll cnt=0;
            for(int j=1;j<=num1[i];j++){
                if(num1[i]%j==0){
                    cnt+=num2[j]*j;
                    cnt%=mod;
                }
            }
            sum*=cnt;
            sum%=mod;
        }
        printf("Case #%d: %lld\n",++cas,sum);
    }
    return 0;
}