Annettuna on merkkijono, jonka jokainen merkki on numero väliltä 1–9 tai operaattori + (yhteenlasku) tai * (kertolasku). Merkkijonossa ei ole peräkkäin kahta operaattoria.

Merkkijonon osajonon arvo lasketaan tavallisten laskusääntöjen mukaisesti. Esimerkiksi merkkijonon 1337+42*666 osana on osajono 7+42*66, jonka arvo on 2779. Jos osajonon ensimmäinen tai viimeinen merkki on operaattori, osajonon arvo on 0.

Tehtäväsi on laskea summa merkkijonon kaikkien osajonojen arvoista.

Syöte

Syötteen ainoalla rivillä on merkkijono, jonka pituus on n.

Tuloste

Tulosta yksi kokonaisluku: vastaus modulo 10^9+7.

Esimerkki 1

Syöte:

1+23

Tuloste:

56

Selitys: Vastaus saadaan laskemalla yhteen osajonojen 1, 2, 3, 23, 1+2 ja 1+23 arvot.

Esimerkki 2

Syöte:

1337+42*666

Tuloste:

167998

Osatehtävä 1 (5 pistettä)

• 1 \le n \le 100

Osatehtävä 2 (25 pistettä)

• 1 \le n \le 5000

Osatehtävä 3 (10 pistettä)

• 1 \le n \le 10^6
• Jokainen merkki on numeromerkki

Osatehtävä 4 (10 pistettä)

• 1 \le n \le 10^6
• Jokainen merkki on numeromerkki tai +-merkki

Osatehtävä 5 (10 pistettä)

• 1 \le n \le 10^6
• Jokainen merkki on numeromerkki tai *-merkki

Osatehtävä 6 (40 pistettä)

• 1 \le n \le 10^6