{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003eへやわり!\u003c/h3\u003e\n\n\u003cp\u003e\u003ci\u003eN+1\u003c/i\u003e 部屋が1列に並んだ新築の建物がある.各部屋はすべて1人用の住居であり,現在どの部屋も空室だが,来月から新たに \u003ci\u003eN\u003c/i\u003e 人がここに住む予定である.したがって彼らが暮らし始めると1室は空き部屋になる.\n\u003c/p\u003e\n\n\u003cp\u003eあなたは大家として,彼らの嗜好に合わせた部屋割りを多く提案したいと考えている.ここで部屋割りとは,それぞれの人がどの部屋に住むのかを与える表である.例えば \u003ci\u003eN \u003d 3\u003c/i\u003e のとき,「1人目は4号室,2人目は1号室,3人目は2号室」がありうる一つの部屋割りである.\n\u003c/p\u003e\n\n\u003cp\u003eもちろん,ありうるすべての部屋割りを提案すれば話は早いが,それでは提案の意味がないため,大家の手間と住人の嗜好を考慮していくつか制約を設ける.\n\u003c/p\u003e\n\n\u003cp\u003eまず,提案された部屋割りの一つに彼らが住み始めてから,「別の提案された部屋割りの方に変更したい」と言われるかもしれない.この建物は新築であり,彼らはまだ誰も入居していない新しい部屋が好みであることがわかっているので,単純に誰か1人が空き部屋へ引っ越しをするだけで提案された別の部屋割りに変更できるときに限りこれが起こりうる.しかし大家として,そういう面倒ごとは避けたいため,このような変更が許されないよう,提案する部屋割りをうまく調整したい.\nつまり,提案する部屋割りの集合は次を満たさなければならない.\n「任意の二つの異なる提案された部屋割り \u003ci\u003eA, B\u003c/i\u003e に対して,部屋割り \u003ci\u003eA\u003c/i\u003e の空き部屋に誰か1人を移しても部屋割り \u003ci\u003eB\u003c/i\u003e にならない」\n\u003c/p\u003e\n\n\u003cp\u003e次に,これから住む \u003ci\u003eN\u003c/i\u003e 人にはそれぞれちょうど1人好ましい人がいることがわかっている.したがって,提案するすべての部屋割りは,すべての人に対して好ましい人が隣に住むような部屋割りにする.\n\u003c/p\u003e\n\n\u003cp\u003eこれらの条件を満たす部屋割りの集合で,最大の集合の大きさはいくらだろうか?\u003ci\u003e1,000,000,007\u003c/i\u003e で割った余りを求めてほしい.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e入力は複数のデータセットからなる.\n各データセットは次の形式で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003eN\u003c/i\u003e\u003cbr\u003e\u003ci\u003ea\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ea\u003csub\u003e2\u003c/sub\u003e ... a\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\u003cp\u003eデータセットの 1 行目には,来月建物に住む人数を表す整数 \u003ci\u003eN\u003c/i\u003e が与えられる.これは \u003ci\u003e2 ≤ N ≤ 100,000\u003c/i\u003e を満たす.\n2行目には \u003ci\u003ei\u003c/i\u003e 番目の人にとって隣の部屋に住んでくれると好ましい人の番号 \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e の情報が与えられる.これについては \u003ci\u003e1 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ N\u003c/i\u003e かつ \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e ≠ i\u003c/i\u003e を満たす.\nまた,データセットの数は 50 を超えない.\n入力の終わりは,1個のゼロだけからなる行で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e各データセットに対して,問題文にあるような,同時に提案できる部屋割りの数の最大値を,\u003ci\u003e1,000,000,007\u003c/i\u003e で割った余りを1行で出力せよ.\n\u003c/p\u003e\n\n\n\u003ch3\u003eSample Input\u003c/h3\u003e\n\n\u003cpre\u003e2\n2 1\n3\n3 1 2\n10\n2 1 1 1 1 1 1 1 1 1\n8\n2 1 4 3 3 7 6 6\n25\n2 3 2 5 4 5 8 7 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24\n10\n2 1 4 3 6 5 8 7 10 9\n0\n\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for Sample Input\u003c/h3\u003e\n\n\u003cpre\u003e2\n0\n0\n144\n633544712\n11520\u003c/pre\u003e"}}]}