Uolevin lempipeli on nimeltään "Merkkijonon tyhjennys".

Pelin alussa on merkkijono, joka muodostuu merkeistä A–Z. Jokaisella siirrolla Uolevin täytyy poistaa merkkijonosta kaksi vierekkäistä merkkiä, jotka ovat samat. Uolevi voittaa pelin, jos hän onnistuu poistamaan kaikki merkit merkkijonosta.

Tehtäväsi on laskea, monellako tavalla Uolevi voi voittaa pelin annetusta alkutilanteesta. Kaksi tapaa ovat erilaiset, jos Uolevi poistaa jossain vaiheessa eri kohdassa olevat merkit.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä väliltä A–Z.

Tuloste

Ohjelmasi tulee tulostaa, monellako tavalla Uolevi voi voittaa pelin. Vastaus voi olla suuri, joten tulosta se modulo 10^9+7.

Rajat

• 1 \le n \le 100

Esimerkki

Syöte:

ABBAACCA

Tuloste:

12