Function

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

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

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码