Xu1024 is a boy who is responsible for fixing the bug of HOJ.

Because the Hunan university ACM freshman competition is coming, Xu1024 find that HOJ still has a lot of
functions not realized. To solve this problem, Xu1024 had to work a 996 schedule.

Unfortunately, Xu1024 was carried into the ambulance because of exhaustion. More unfortunate thing happened, There is something wrong with the ambulance's electrical system. The electrical system of the ambulance is very special. There are $N$ wires in system $A$ and $N$ wires in system $B$, and the ambulance can restart when any $i$-th wire in system $A$ is connected to line the $A_i$-th wire in system $B$. The $A_1,A_2,...A_n$ is a premutation of $n$.

In order to save the child, you decide to reconnect the electric wire so that every wire in system $B$ will be connected with a unique line in system $A$. How many ways can the ambulance restart? Due to the answer will be very large, you only need to output the answer mod $1,000,000,007$.

The first line contains one integer $N(N ≤100000)$, the number of the system’s wire(s).
The next line contains $N$ integers, the $i$-th number is $A_i$.
It is guaranteed that $A_1,A_2,...A_n$ is a permutation of $n$.

Output an integer which denotes the answer.

In the first case:
There two ways to connect the electric wire.
One is choose the $1st\ A$ wire to connect the $1st\ B$ wire and choose the $2nd\ A$ wire to
connect the $2nd\ B$ wire.
Another is choose the $2nd\ A$ wire to connect the $1st\ B$ wire and choose the $1st\ A$ wire to
connect the $2nd\ B$ wire.
Only the first way can restart the ambulance.