Za rođendan ste dobili magični štapić koji djeluje nad magičnim permutacijama. Prije korištenja, u postavke magičnog štapića možete unjeti jednu permutaciju duljine \(n\). Nakon što ste to napravili, kada magičnim štapićem dotaknete neku permutaciju, permutacija će se permutirati prema permutaciji koju ste unjeli u postavke.

Preciznije, ako ste u postavke unjeli \(p_1\), \(p_2\), ..., \(p_n\), a permutacija koju ćete dotaknuti je \(a_1\), \(a_2\), ..., \(a_n\) onda će permutacija \(a\) postati \(a_{p_1}\), \(a_{p_2}\), ..., \(a_{p_n}\).

Odlučili ste prirediti predstavu u kojoj ćete na početku unjeti neku permutaciju u postavke štapića te zatim uzastopno dodirivati istu permutaciju štapićem dok se ne vrati u početno stanje.

Da bi predstava bila zanimljivija želite maksimizirati duljinu trajanja, odnosno broj dodirivanja. Odredite taj maksimalni broj dodirivanja. Budući da maksimalni broj dodirivanja može biti jako velik ispišite njegov ostatak pri dijeljenju s \(10^9+7\)

Ulazni podatci

U jedinom redu nalazi se prirodni broj \(n\) \((1 \leq n \leq 1000)\).

Izlazni podatci

U prvi red ispišite traženi maksimalni broj dodira modulo \(10^9+7\).

Ulaz primjera 1

6

Izlaz primjera 1

6

Ulaz primjera 2

4

Izlaz primjera 2

4