Sinulle annetaan merkkijono, joka muodostuu merkeistä "8" ja ")".

Tehtäväsi on laskea, monellako tavalla voit valita merkkijonosta kaksi merkkiä niin, että niistä muodostuu kasihymiö eli merkkijono "8)". Valinnassasi vasemman merkin tulee olla "8" ja oikean merkin tulee olla ")".

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä.

Tuloste

Tulosta yksi kokonaisluku: tapojen määrä.

Esimerkki

Syöte:

8)88)

Tuloste:

4

Osatehtävä 1 (23 pistettä)

• 1 \le n \le 1000

Osatehtävä 2 (77 pistettä)

• 1 \le n \le 10^6