Pelissä on n planeettaa, jotka on numeroitu 1,2,\dots,n. Jokaiselle planeetalle rakennetaan tasan yksi teleportti. Teleportin kautta pääsee jollekin planeetalle, ja teleportti voi osoittaa myös planeettaan itseensä.

Kaksi planeettaa kuuluu samaan komponenttiin, jos on jokin planeetta, johon pääsee molemmilta planeetoilta teleporttien avulla.

Esimerkiksi seuraavassa kuvassa n=9 ja planeetat muodostavat 2 komponenttia:

Laske jokaiselle komponenttien määrälle 1 \dots n, monellako eri tavalla teleporttien kohteet voidaan asettaa niin, että tuloksena on kyseinen määrä komponentteja.

Syöte

Syötteen ainoalla rivillä on luku n: planeettojen määrä.

Tuloste

Tulosta n riviä: tapojen määrät, kun komponentteja on 1 \dots n. Koska määrät voivat olla suuria, tulosta ne modulo 10^9+7.

Esimerkki

Syöte:

3

Tuloste:

17
9
1

Osatehtävä 1 (24 pistettä)

• 1 \le n \le 10

Osatehtävä 2 (25 pistettä)

• 1 \le n \le 100

Osatehtävä 3 (51 pistettä)

• 1 \le n \le 5000