Description

One day,lmh did a problem in HDU.But he doubted this problem is wrong.At last,he found the reason is he get the wrong meaning of the title.

He spent a lot of time to solve it,so he did not convince himself.And then,he decide to change this title to satisfy his vanity.

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

Please calculate the quantity of different functions f satisfying that f(i)=bf(ai) for each i.(You just need to consider the value of f 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 $1e9+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,the i-th number of which represents ai−1.

The third line contains m numbers,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