Se le da una cadena formada por ~n~ caracteres entre a y z. En cada turno, puede eliminar dos caracteres adyacentes iguales. Su objetivo es construir una cadena vacía eliminando todos los caracteres.

¿De cuántas formas puede hacerlo?

Entrada

La única línea de entrada tiene una cadena de longitud ~n~.

Salida

Imprime un entero: el número de formas módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 500~

Ejemplo de Entrada

aabccb

Ejemplo de Salida

3