Function

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 $\displaystyle f(i) = b_{f(a_i)}$ 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 $10^9 + 7$.

Input

The input contains multiple test cases. For each case: The first line contains two numbers $n,$ $m$. $(1 \leq n \leq 100000, 1 \leq m \leq 100000)$ The second line contains $n$ numbers, ranged from $0$ to $n - 1$, the $i$-th number of which represents $a_{i - 1}$. The third line contains $m$ numbers, ranged from $0$ to $m - 1$, the $i$-th number of which represents $b_{i - 1}$. It is guaranteed that $\sum{n} \leq 10^6,$ $\sum{m} \leq 10^6$.

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

Source

2017 Multi-University Training Contest - Team 1