CSES - Putka Open 2020 – 2/5 - Planeetat
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Pelissä on nn planeettaa, jotka on numeroitu 1,2,,n1,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=9n=9 ja planeetat muodostavat 22 komponenttia:

Laske jokaiselle komponenttien määrälle 1n1 \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 nn: planeettojen määrä.

Tuloste

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

Esimerkki

Syöte:

3

Tuloste:

17
9
1

Osatehtävä 1 (24 pistettä)

  • 1n101 \le n \le 10

Osatehtävä 2 (25 pistettä)

  • 1n1001 \le n \le 100

Osatehtävä 3 (51 pistettä)

  • 1n50001 \le n \le 5000