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