{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $1 ≤ N ≤ 10^5$\n*   $a_i$ is an integer.\n*   $1 ≤ a_i ≤ N$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_N$"},{"iden":"sample input 1","content":"3\n1 2 3"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"2\n1 1"},{"iden":"sample output 2","content":"1\n\nThe following one permutation satisfies the condition:\n\n*   $(2, 1)$"},{"iden":"sample input 3","content":"3\n2 1 1"},{"iden":"sample output 3","content":"2\n\nThe following two permutations satisfy the condition:\n\n*   $(2, 3, 1)$\n*   $(3, 1, 2)$"},{"iden":"sample input 4","content":"3\n1 1 1"},{"iden":"sample output 4","content":"0"},{"iden":"sample input 5","content":"13\n2 1 4 3 6 7 5 9 10 8 8 9 11"},{"iden":"sample output 5","content":"6"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}