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 Ai-th wire in system B. The A1,A2,...An 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 Ai.
It is guaranteed that  A1,A2,...An is a permutation of n.

Output an integer which denotes the answer.

2
1 2

1

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.

3
2 3 1

4