問題

あるゲームを考える. N (< 50) マスからなる盤があり, 始めに任意の 0 個以上のマスに印を置くことができる.

配列 a が与えられ, 1 ターンで p 番目のマスにある印が a[p-1] 番目のマスに移動する.

K (< 1,000,000,000) ターンの間に, 同じマスに複数の印が存在する状態が一度も発生しないようにしたい.

このような印の初期配置は何通りあるか.

パターン数を 1,000,000,007 で割った余りを出力せよ.

解法

一度でも同じマスになった印は, それ以降ずっと同じマスを移動する. よって, K ターン目時点での印の配置のみ考えれば良い.

マスの数は N であり, 印が移動する周期は最大 N である. よって, K > N の場合, K ターン目時点での印のダブり方と N ターン目時点でのそれは一致する.

よって, K = min(K, N) として考える.

マス i_1, i_2, …, i_n に置いた印が K ターン目に同じマスにいた場合, i_1, i_2, …, i_n のどれか 1 マスにのみ印を置くことができる. すなわち, i_1, i_2, …, i_n についての初期配置の選び方は n 通りある.

マス 1..N について, K ターン目時点での移動先を求めて, 選び方を乗算すれば良い.