406061: GYM102253 F Function

You are given a permutation $$$a$$$ obtained from $$$0$$$ to $$$(n - 1)$$$, and a permutation $$$b$$$ obtained from $$$0$$$ to $$$(m - 1)$$$.

Let's define a function $$$f$$$, which maps each integer between $$$0$$$ and $$$(n - 1)$$$, to an integer between $$$0$$$ and $$$(m - 1)$$$.

Please calculate the number of different functions $$$f$$$ satisfying that $$$f(i) = b_{f(a_i)}$$$ for each $$$i$$$.

Two functions are considered different if and only if there exists at least one integer mapped to different integers in these functions.

The answer can be a bit large, so you should output it modulo $$$(10^9 + 7)$$$ instead.

The input contains multiple test cases.

For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$).

The second line contains $$$n$$$ integers, the $$$i$$$-th number of which is $$$a_{i - 1}$$$ ($$$0 \leq a_{i - 1} \leq n - 1$$$).

The third line contains $$$m$$$ integers, the $$$i$$$-th number of which is $$$b_{i - 1}$$$ ($$$0 \leq b_{i - 1} \leq m - 1$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ in all test cases are no more than $$$10^6$$$ respectively.

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 to the corresponding case.

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

Case #1: 4
Case #2: 4