Zadanie

Igorova Introvertná postupnosť

Počet bodov: 50, časový limit: 1000ms

Introvert Igor nerád navštevuje neznáme lokality. Vyskytujú sa tam neznámi ľudia, ktorí sa s ním chcú zoznámiť.

Igorovi však v živote niekto chýba. Niekto, kto by ho doplnil – šikovný stredoškolský programátor.

Igor teda musí prekonať svoj strach, a navštíviť aj nejaké nové lokality v jeho okolí.

Keďže programátora chce nájsť čo najskôr, každý deň sa niekam vydá. Aby to však s tým stretávaním nových ľudí neprehnal, chcel by vždy navštíviť také miesto, že predtým bol na nejakom podobnom mieste. Bude sa mu tak ľahšie nadhazdovať konverzácia.

Chcel si zhotoviť plán, kam sa vydá, pre každý z ďalších \(n\) dní. No dajako sa nevedel rozhodnúť, keďže rôznych plánov bolo strašne veľa.

Nič to, hodí si každé ráno kockou. A v tom ho napadol spôsob, ako o novozoznámenom stredoškolskom programátorovi zistiť, či je šikovný…

Úloha

V Igorovom okolí je \(10\) lokalít, ktorým priradíme čísla od \(0\) po \(9\). V prvý deň Igor prekoná svoj strach, a vyberie sa do niektorej z lokalít, inej ako \(0\). V každý ďalší deň môže navštíviť buď lokalitu \(0\), ktorou je Igorova škola, alebo lokalitu číslo \(x\) vtedy, keď v niektorom z predošlých dní navštívil lokalitu s číslom, ktoré delí \(x\) bezozvyšku (číslo \(1\) za tykýto deliteľ považovať nebudeme). Tieto lokality sú totiž podobné.

Každá postupnosť číslic, ktorá predstavuje platný plán navštívených lokalít pre Igora, sa nazýva Igorova Introvertná postupnosť.

Vypíšte počet Igorových Introvertných Postupností dĺžky \(n\).

Vstup a výstup

V jedinom riadku vstupu je kladné číslo \(n\).

Vypíšte počet introvertných postupností dĺžky \(n\). Keďže toto číslo môže byť priveľké, vypíšte len jeho zvyšok po delení číslom \(10^9+7\).

Sú štyri sady vstupov. Platí v nich postupne \(n \leq 4, 9, 1000, 10^5\).

Príklad

Input:

2

Output:

23

Niektoré platné postupnosti sú napríklad [5,0] a [4,8].