Counting the ways of Making Friends is Fun

と番号付けられた 人の人がいます。最初， 人のうちどの二人組も直接友人ではありません。

あなたは今から，以下の操作をちょうど 回行います。

• 人のうちから二人選んで，その二人を直接友人にさせる。

また， 回の操作終了後，以下の条件を満たす必要があります。

条件： 回の操作が終了した後，全ての で，人 について，人 の直接の友人，またその友人の直接の友人… というように，直接の友人を辿っていくことで，人 以外の全ての人に行きつく。

ありえる 人の友人関係は何通りあるでしょう？

回の操作を終えた後の 人の友人関係 と， 人の友人関係 について，ある二人組 で、「 では直接の友人であるが、 では直接の友人ではないような組」または 「 では直接の友人ではないが、 では直接の友人であるような組」 である場合，友人関係 と は区別することにします。

ありえる 人の友人関係の場合の数を （この値は素数です。）で割った余りで出力してください。

ありえる 人の友人関係の場合の数を で割った余りで一行に出力してください。改行を忘れないこと。

2

1

人を人 と 人 と書くことにし，人 間の友人関係を で表すことにします。
最終的な友人関係は の 通りのみです。 は と同一視されることに注意してください。
よって， を で割った余りである を出力すればよいです。

3

3

最終的な友人関係は , , の 通りです。
よって， を で割った余りである を出力すればよいです。