{"raw_statement":[{"iden":"problem statement","content":"Given are permutations of $(1, \\dots, N)$: $p = (p_1, \\dots, p_N)$ and $q = (q_1, \\dots, q_N)$.\nFind 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)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 3000$\n*   $1 \\leq p_i, q_i \\leq N$\n*   $p_i \\neq p_j \\, (i \\neq j)$\n*   $q_i \\neq q_j \\, (i \\neq j)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$p_1$ $\\ldots$ $p_N$\n$q_1$ $\\ldots$ $q_N$"},{"iden":"sample input 1","content":"4\n1 2 3 4\n2 1 4 3"},{"iden":"sample output 1","content":"4\n\nThere are four valid permutations: $(3, 4, 1, 2)$, $(3, 4, 2, 1)$, $(4, 3, 1, 2)$, and $(4, 3, 2, 1)$."},{"iden":"sample input 2","content":"3\n1 2 3\n2 1 3"},{"iden":"sample output 2","content":"0\n\nThe answer may be $0$."},{"iden":"sample input 3","content":"20\n2 3 15 19 10 7 5 6 14 13 20 4 18 9 17 8 12 11 16 1\n8 12 4 13 19 3 10 16 11 9 1 2 17 6 5 18 7 14 20 15"},{"iden":"sample output 3","content":"803776944\n\nBe sure to print the count modulo $(10^9 + 7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}