406733: GYM102512 B Confession

B. Confessiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$N$$$ students from a certain high school and each of them has a crush. Student $$$i$$$ has a crush on student $$$p_{i}$$$. Obviously, $$$p_{i} \neq i$$$ as a person cannot have a crush on themselves. For the purposes of this problem, the gender of the students doesn't matter, i.e. it is possible for a guy to have a crush on a guy and a girl to have a crush on a girl.

Consider the following process. Firstly, choose a random permutation $$$(a_1, a_2, ..., a_{N})$$$ of $$$1$$$ to $$$N$$$ (each with equal probability). On the $$$i$$$-th day, student $$$a_i$$$ (if they are not already taken) will confess to their crush, say X = student $$$p_{a_{i}}$$$.

• If X has a crush on student $$$a_{i}$$$ as well (meaning they have a crush on each other), then X and student $$$a_{i}$$$ become a couple (and thus both become taken).
• Otherwise, if X is taken or X hasn't confessed to their crush (regardless of whether their crush is taken), then student $$$a_i$$$ will be rejected as X's residual feelings toward their crush prevents them from accepting the confession.
• Otherwise, student $$$a_i$$$ and X become a couple (and both become taken).

What is the expected number of couples after the process ends? The answer can be written as an irreducible fraction $$$\frac{P}{Q}$$$. It can be proven that there exists a unique integer $$$0 \le R < 10^{9} + 7$$$ such that $$$QR \equiv P \pmod{10^{9}+7}$$$. Output the integer $$$R$$$.

Input

The first line of input contains a single integer $$$N$$$ ($$$2 \le N \le 100$$$), denoting the number of students in the school.

The next line of input contains $$$N$$$ space-separated integers, the $$$i$$$-th of which denotes $$$p_{i}$$$ ($$$1 \le p_{i} \le N, p_{i} \neq i$$$).

Output

Output a single integer, the value of $$$R$$$.

Scoring

Subtask 1 (7 points): $$$N \le 9$$$

Subtask 2 (11 points): The graph with edges $$$i \rightarrow p_{i}$$$ form a directed cycle.

Subtask 3 (33 points): $$$N \le 40$$$

Subtask 4 (49 points): No additional constraints

ExamplesInput

3
2 3 1

Output

1

Input

4
2 3 1 1

Output

166666669

Input

2
2 1

Output

1

Input

9
4 9 4 9 4 9 4 9 4

Output

1

Input

10
6 3 7 3 8 3 9 3 10 3

Output

362830693

Note

For the first sample, there are $$$6$$$ possible permutations.

Suppose $$$a = (1, 2, 3)$$$. Then, student $$$1$$$'s confession will fail as student $$$2$$$ hasn't confessed. Student $$$2$$$'s confession will fail because student $$$3$$$ hasn't confessed. Student $$$3$$$'s confession will succeed and student $$$3$$$ and $$$1$$$ will form a couple.

You can check that any other permutation $$$a$$$ will give exactly $$$1$$$ couple.

Thus, the expected number of couples is $$$1$$$.

For the second sample, the expected number of couples is $$$\frac{7}{6}$$$, and $$$6 \times 166666669 \equiv 7 \pmod{10^{9} + 7}$$$. Thus, $$$R = 166666669$$$.

For example, consider $$$a = (3, 1, 2, 4)$$$. Then, student $$$3$$$'s confession will fail as student $$$1$$$ hasn't confessed. Student $$$1$$$'s confession will fail as student $$$2$$$ hasn't confessed. Student $$$2$$$'s confession will succeed and student $$$2$$$ and $$$3$$$ will form a couple. Student $$$4$$$'s confession will succeed and student $$$1$$$ and $$$4$$$ will form a couple. The number of couples in this case is $$$2$$$.

On the other hand, consider $$$a = (3, 2, 4, 1)$$$. Then, student $$$3$$$'s confession will fail as student $$$1$$$ hasn't confessed. Student $$$2$$$'s confession will succeed and student $$$2$$$ and $$$3$$$ will form a couple. Student $$$4$$$'s confession will fail as student $$$1$$$ hasn't confessed. Note that it doesn't matter here that student $$$1$$$'s crush, student $$$2$$$, is already taken at this point. Finally, student $$$1$$$'s confession will fail as student $$$2$$$ is already taken. The number of couples in this case is $$$1$$$.

For the third sample, both permutations $$$a = (1, 2), (2, 1)$$$ will leave students $$$1$$$ and $$$2$$$ as a couple. Thus, the expected number of couples is $$$1$$$.