{"problem":{"name":"Three Permutations","description":{"content":"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 th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc214_g"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$p_1$ $\\ldots$ $p_N$\n$q_1$ $\\ldots$ $q_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc214_g","tags":[],"sample_group":[["4\n1 2 3 4\n2 1 4 3","4\n\nThere are four valid permutations: $(3, 4, 1, 2)$, $(3, 4, 2, 1)$, $(4, 3, 1, 2)$, and $(4, 3, 2, 1)$."],["3\n1 2 3\n2 1 3","0\n\nThe answer may be $0$."],["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","803776944\n\nBe sure to print the count modulo $(10^9 + 7)$."]],"created_at":"2026-03-03 11:01:13"}}