{"problem":{"name":"Next or Nextnext","description":{"content":"You are given an integer sequence $a$ of length $N$. How many permutations $p$ of the integers $1$ through $N$ satisfy the following condition? *   For each $1 ≤ i ≤ N$, at least one of the following","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc008_e"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence $a$ of length $N$. How many permutations $p$ of the integers $1$ through $N$ satisfy the following condition?\n\n*   For each $1 ≤ i ≤ N$, at least one of the following holds: $p_i = a_i$ and $p_{p_i} = a_i$.\n\nFind the count modulo $10^9 + 7$.\n\n## Constraints\n\n*   $1 ≤ N ≤ 10^5$\n*   $a_i$ is an integer.\n*   $1 ≤ a_i ≤ N$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc008_e","tags":[],"sample_group":[["3\n1 2 3","4\n\nThe following four permutations satisfy the condition:\n\n*   $(1, 2, 3)$\n*   $(1, 3, 2)$\n*   $(3, 2, 1)$\n*   $(2, 1, 3)$\n\nFor example, $(1, 3, 2)$ satisfies the condition because $p_1 = 1$, $p_{p_2} = 2$ and $p_{p_3} = 3$."],["2\n1 1","1\n\nThe following one permutation satisfies the condition:\n\n*   $(2, 1)$"],["3\n2 1 1","2\n\nThe following two permutations satisfy the condition:\n\n*   $(2, 3, 1)$\n*   $(3, 1, 2)$"],["3\n1 1 1","0"],["13\n2 1 4 3 6 7 5 9 10 8 8 9 11","6"]],"created_at":"2026-03-03 11:01:14"}}