自然数nに以下の操作を行い、p(n)を計算する。

(1)((n!)^(n!))-1と(2n)!の最大公約数dを求める。

(2)d^dとd!の最大公約数sを求め、t=(d^d)/sを求める。

(3)d^aがtを割り切るような最大の整数aを求め、t/(d^a)とdの最大公約数uを求める。

この時、p(n)=d/u


例えば
n=2の時は(2!)^(2!)-1=3,4!=24よりd=3で、3^3=27,3!=6よりs=3。
(3^3)/3=9よりt=9。
よってa=2だからu=9/(3^2)=1となり、

p(2)=3/1=3

になる。


問題
p(2009)を求めよ。