{"raw_statement":[{"iden":"statement","content":"_As you noticed, there are lovely girls in Arpa’s land._\n\nPeople 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.\n\nSomeday Arpa shouted _Owf_ loudly from the top of the palace and a funny game started in Arpa's land. The rules are as follows.\n\nThe 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.\n\nMehrdad 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.\n\nSome strange fact in Arpa's land is that someone can be himself's crush (i.e. crushi = i).\n\nThe first line of input contains integer n (1 ≤ n ≤ 5·106) — the number of people in Arpa's land.\n\nThe second line contains n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.\n\nIf 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.\n\nIn the first sample suppose t = 3. \n\nIf the first person starts some round:\n\nThe 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.\n\nThe process is similar for the second and the third person.\n\nIf the fourth person starts some round:\n\nThe 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.\n\nIn the last example if the first person starts a round, then the second person becomes the Joon-Joon, and vice versa.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input42 3 1 4Output3Input44 4 4 4Output-1Input42 1 4 3Output1"},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ n \\leq 5 \\cdot 10^6 $.  \nLet $ f: \\{1, 2, \\dots, n\\} \\to \\{1, 2, \\dots, n\\} $ be a function where $ f(i) $ is the crush of person $ i $.  \n\nFor $ t \\in \\mathbb{Z}^+ $, define $ f^t(i) $ as the $ t $-fold composition of $ f $, i.e., the person reached after $ t $ steps starting from $ i $.  \nThe Joon-Joon of a round starting at $ x $ with parameter $ t $ is $ f^t(x) $.  \n\n**Constraint**  \nFor all $ x \\in \\{1, \\dots, n\\} $, if $ y = f^t(x) $, then $ f^t(y) = x $.  \n\n**Objective**  \nFind the smallest $ t \\geq 1 $ such that:  \n$$\n\\forall x \\in \\{1, \\dots, n\\}, \\quad f^t(f^t(x)) = x\n$$  \nIf no such $ t $ exists, output $ -1 $.  \nOtherwise, output $ t \\mod (10^9 + 7) $.","simple_statement":"Find the smallest t ≥ 1 such that:  \nIf person x starts a round with t \"w\"s, the Joon-Joon is y.  \nThen, if y starts a round with the same t, the Joon-Joon must be x.  \nIf no such t exists, output -1.  \nOtherwise, output t mod (10^9 + 7).  \n\nEach person has exactly one crush (including possibly themselves).  \nThe call chain follows crush links for t steps, and the last person is the Joon-Joon.","has_page_source":false}