C. Arpa's loud Owf and Mehrdad's evil plan(Hard)

_As you noticed, there are lovely girls in Arpa’s land._ People in Arpa's land are numbered from 1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi. Someday Arpa shouted _Owf_ loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows. The game consists of rounds. Assume person x wants to start a round, he calls crushx and says: "_Oww...wwf_" (the letter _w_ is repeated t times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "_Oww...wwf_" (the letter _w_ is repeated t - 1 times) and cuts off the phone immediately. The round continues until some person receives an "_Owf_" (t = 1). This person is called the _Joon-Joon_ of the round. There can't be two rounds at the same time. Mehrdad has an evil plan to make the game more funny, he wants to find smallest t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y , x would become the Joon-Joon of the round. Find such t for Mehrdad if it's possible. Some strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i). The first line of input contains integer n (1 ≤ n ≤ 5·106) — the number of people in Arpa's land. The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush. If there is no t satisfying the condition, print _-1_. Otherwise print such smallest t. As answer can become too large, print it modulo 109 + 7. In the first sample suppose t = 3. If the first person starts some round: The first person calls the second person and says "_Owwwf_", then the second person calls the third person and says "_Owwf_", then the third person calls the first person and says "_Owf_", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1. The process is similar for the second and the third person. If the fourth person starts some round: The fourth person calls himself and says "_Owwwf_", then he calls himself again and says "_Owwf_", then he calls himself for another time and says "_Owf_", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4. In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa. ## Input The first line of input contains integer n (1 ≤ n ≤ 5·106) — the number of people in Arpa's land.The second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush. ## Output If there is no t satisfying the condition, print _-1_. Otherwise print such smallest t. As answer can become too large, print it modulo 109 + 7. [samples] ## Note In the first sample suppose t = 3. If the first person starts some round:The first person calls the second person and says "_Owwwf_", then the second person calls the third person and says "_Owwf_", then the third person calls the first person and says "_Owf_", so the first person becomes Joon-Joon of the round. So the condition is satisfied if x is 1.The process is similar for the second and the third person.If the fourth person starts some round:The fourth person calls himself and says "_Owwwf_", then he calls himself again and says "_Owwf_", then he calls himself for another time and says "_Owf_", so the fourth person becomes Joon-Joon of the round. So the condition is satisfied when x is 4.In the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.