Given are permutations of $(1, \dots, N)$: $p = (p_1, \dots, p_N)$ and $q = (q_1, \dots, q_N)$. Find the number, modulo $(10^9 + 7)$, of permutations $r = (r_1, \dots, r_N)$ of $(1, \dots, N)$ such that $r_i \neq p_i$ and $r_i \neq q_i$ for every $i$ $(1 \leq i \leq N)$.

Input is given from Standard Input in the following format: >$N$\ >$p_1$ $\ldots$ $p_N$\ >$q_1$ $\ldots$ $q_N$ #### Constraints - $1 \leq N \leq 3000$ - $1 \leq p_i, q_i \leq N$ - $p_i \neq p_j \, (i \neq j)$ - $q_i \neq q_j \, (i \neq j)$ - All values in input are integers.

Print the answer.

***For Sample #1:*** There are four valid permutations: $(3, 4, 1, 2)$, $(3, 4, 2, 1)$, $(4, 3, 1, 2)$, and $(4, 3, 2, 1)$. ***For Sample #2:*** The answer may be $0$. ***For Sample #3:*** Be sure to print the count modulo $(10^9 + 7)$.

AtCoder [ABC214G]