Problem Description
You are given a permutation a from 0 to n−1 and a permutation b from 0 to m−1.

Define that the domain of function f is the set of integers from 0 to n−1, and the range of it is the set of integers from 0 to m−1.

Please calculate the quantity of different functions f satisfying that f(i)=bf(ai) for each i from 0 to n−1.

Two functions are different if and only if there exists at least one integer from 0 to n−1 mapped into different integers in these two functions.

The answer may be too large, so please output it in modulo 109+7.

Input
The input contains multiple test cases.

For each case:

The first line contains two numbers n, m. (1≤n≤100000,1≤m≤100000)

The second line contains n numbers, ranged from 0 to n−1, the i-th number of which represents ai−1.

The third line contains m numbers, ranged from 0 to m−1, the i-th number of which represents bi−1.

It is guaranteed that ∑n≤106, ∑m≤106.

Output
For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

Sample Input

3 2
1 0 2
0 1
3 4
2 0 1
0 2 3 1

Sample Output

Case #1: 4
Case #2: 4

题意：给你一个a序列，代表0到n-1的排列；一个b序列代表0到m-1的排列。问你可以找出多少种函数关系，满足f(i)=b[f(a[i])]

解法：

看一下第二组样例：

对于这个样例，假如我们确定了f(0)在b中的值，那么根据第二个式子，就可以得到f(1)，同理通过f(1)可以得到f(2)，最后根据f(2)反推回来就可以判断f(0)是不是正确。也就是说，对于a中的一个循环节只要确定其中一个数映射的值，那么这个循环节其他的数就确定了。

所以我们需要先计算a,b的循环节和每个循环节节的个数，然后根据循环节的约数关系就可以判断是否成立。
如何求答案呢？当b中的循环节的长度是a的循环节长度的约数的时候，a循环节可以指定数字的个数是b的循环节长度。这里有一个规律就是：0~n 的排列，是一定存在循环节的，而且多个循环节是不会有交叉的，所以最后的结果应该相乘。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 1e5+6;
int n, m, a[maxn], b[maxn], loop_a[maxn], loop_b[maxn], vis[maxn];
LL qsm(int a, int n)
{
    int ret = 1;
    while(n){
        if(n&1) ret=1LL*ret*a%mod;
        a=1LL*a*a%mod;
        n>>=1;
    }
    return ret;
}
int main()
{
    int ks = 0;
    while(~scanf("%d %d", &n,&m)){
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        for(int i=0; i<m; i++) scanf("%d", &b[i]);
        memset(vis, 0, sizeof(vis));
        memset(loop_a, 0, sizeof(loop_a));
        memset(loop_b, 0, sizeof(loop_b));
        for(int i=0; i<n; i++){
            if(!vis[i]){
                int x = a[i];
                int cnt = 0;
                while(!vis[x]){
                    cnt++;
                    vis[x]=1;
                    x=a[x];
                }
                loop_a[cnt]++;
            }
        }
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<m; i++){
            if(!vis[i]){
                int x = b[i];
                int cnt = 0;
                while(!vis[x]){
                    cnt++;
                    vis[x]=1;
                    x=b[x];
                }
                loop_b[cnt]++;
            }
        }
        LL ans=1;
        for(int i=1; i<=n; i++){
            LL ret = 0;
            for(int j=1; j*j<=i; j++){
                if(i%j==0){
                    int k = j;
                    ret += 1LL * loop_b[j] * j;
                    if(j*j != i){
                        k = i / j;
                        ret += 1LL * loop_b[k] * k;
                    }
                }
            }
            int x = loop_a[i];
            ans = 1LL * ans * qsm(ret, x)%mod;
        }
        printf("Case #%d: %lld\n", ++ks, ans);
    }
    return 0;
}