Function

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$.

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$.

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.

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

Case #1: 4
Case #2: 4

2017 Multi-University Training Contest - Team 1