J. Dangerous Driving
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The recent rain and low temperatures have caused many trees to fall over on the streets of Austin, turning many two-way streets into one-way streets. In fact, so many trees have fallen over that you can only leave an intersection via one street, as all the other streets have been blocked by fallen trees. Additionally, the roads have become very icy, and the traffic lights are no longer operating due to a power outage, leading to very dangerous driving conditions.

Thankfully, most people are smart enough to not be driving in these conditions. However, two idiots have decided to try driving around in these treacherous conditions. They each start at separate intersections and take one minute to drive from one intersection to the next, taking the only available road at each intersection. If they enter the same intersection at the same time, they will crash into each other, being unable to brake under the icy conditions.

Your job is to find out how many unique pairs of starting intersections will not result in a crash between the two drivers.

Input

The first line contains $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$), which is the number of intersections. The following $$$n$$$ lines each contain an integer $$$y$$$ ($$$1 \leq y \leq n$$$), meaning that the $$$x$$$th line (after the first) represents a one-way street from intersection $$$x$$$ to intersection $$$y$$$. Note that $$$x \neq y$$$, as an intersection can't have a street to itself.

Output

Print out how the number of unique pairs of starting intersections that will not result in a crash between the two drivers. Because this number can be very large, please mod your final answer by $$$10^9 + 7$$$. Note that the order of the intersections does not matter. $$$(1,2)$$$ is the same as $$$(2,1)$$$.

Examples
Input
3
2
1
1
Output
2
Input
6
2
1
1
5
4
4
Output
13