Uolevilla on kokonaisluku, jossa on $n$ numeroa välillä $1 \ldots 9$.

Uolevi päättää kääntää ympäri jonkin välin luvussa. Tämä tarkoittaa, että Uolevi valitsee luvut $a$ ja $b$ ($1 \le a \le b \le n$) ja kääntää ympäri luvun numerot välillä $a \ldots b$.

Tehtäväsi on laskea yhteen kaikista mahdollisista käännöistä syntyvät luvut. Koska tulos voi olla hyvin suuri, ilmoita se modulo $10^9+7$.

Syöte

Syötteen ainoalla rivillä on kokonaisluku, jossa on $n$ numeroa välillä $1 \ldots 9$.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: käännöistä syntyvien lukujen summa modulo $10^9+7$.

Esimerkki 1

Syöte:

123

Tuloste:

1035

Selitys: Luvut ovat 123, 123, 123, 213, 132 ja 321.

Esimerkki 2

Syöte:

43799276198569422312

Tuloste:

563613522

Osatehtävä 1 (15 pistettä)

• $1 \le n \le 100$

Osatehtävä 2 (41 pistettä)

• $1 \le n \le 5000$

Osatehtävä 3 (44 pistettä)

• $1 \le n \le 10^5$