SRM652 div1 250

問題

整数Nが与えられる。
1〜Nまでを並び替えて得られる任意の順列pについて、i回目の数値をf(i)とすると、
・f(1)=p[1]
・f(m)=p[f(m-1)] (m>=2)
で定義される操作をx回行った値が1になるようしたい(すなわちf(x)=1)。
このようなxのうち、最小となるxをmod 10^9+7で返す。

考え方

N=3のケースで考えると、
123→1,1,1,...→周期1
132→1,1,1,...→周期1
213→2,1,2,1,...→周期2
231→2,3,1,2,3,1,...→周期3
312→3,2,1,3,2,1,...→周期3
321→3,1,3,1,...→周期2
のように1になるタイミングが周期的になっていることがわかる。

最初が1の場合は周期が1、そうでない場合は、周期がNまであり得るので、それらの最小公倍数がf(x)=1となる最小のxとなる。