へやわり！

N+1 部屋が1列に並んだ新築の建物がある．各部屋はすべて1人用の住居であり，現在どの部屋も空室だが，来月から新たに N 人がここに住む予定である．したがって彼らが暮らし始めると1室は空き部屋になる．

あなたは大家として，彼らの嗜好に合わせた部屋割りを多く提案したいと考えている．ここで部屋割りとは，それぞれの人がどの部屋に住むのかを与える表である．例えば N = 3 のとき，「1人目は4号室，2人目は1号室，3人目は2号室」がありうる一つの部屋割りである．

もちろん，ありうるすべての部屋割りを提案すれば話は早いが，それでは提案の意味がないため，大家の手間と住人の嗜好を考慮していくつか制約を設ける．

まず，提案された部屋割りの一つに彼らが住み始めてから，「別の提案された部屋割りの方に変更したい」と言われるかもしれない．この建物は新築であり，彼らはまだ誰も入居していない新しい部屋が好みであることがわかっているので，単純に誰か1人が空き部屋へ引っ越しをするだけで提案された別の部屋割りに変更できるときに限りこれが起こりうる．しかし大家として，そういう面倒ごとは避けたいため，このような変更が許されないよう，提案する部屋割りをうまく調整したい． つまり，提案する部屋割りの集合は次を満たさなければならない． 「任意の二つの異なる提案された部屋割り A, B に対して，部屋割り A の空き部屋に誰か1人を移しても部屋割り B にならない」

次に，これから住む N 人にはそれぞれちょうど1人好ましい人がいることがわかっている．したがって，提案するすべての部屋割りは，すべての人に対して好ましい人が隣に住むような部屋割りにする．

これらの条件を満たす部屋割りの集合で，最大の集合の大きさはいくらだろうか？1,000,000,007 で割った余りを求めてほしい．

Input

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

N
a₁ a₂ ... a_N

データセットの 1 行目には，来月建物に住む人数を表す整数 N が与えられる．これは 2 ≤ N ≤ 100,000 を満たす． 2行目には i 番目の人にとって隣の部屋に住んでくれると好ましい人の番号 a_i の情報が与えられる．これについては 1 ≤ a_i ≤ N かつ a_i ≠ i を満たす． また，データセットの数は 50 を超えない． 入力の終わりは，1個のゼロだけからなる行で表される．

Output

各データセットに対して，問題文にあるような，同時に提案できる部屋割りの数の最大値を，1,000,000,007 で割った余りを1行で出力せよ．

Sample Input

2
2 1
3
3 1 2
10
2 1 1 1 1 1 1 1 1 1
8
2 1 4 3 3 7 6 6
25
2 3 2 5 4 5 8 7 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24
10
2 1 4 3 6 5 8 7 10 9
0

Output for Sample Input

2
0
0
144
633544712
11520

---