Секоја вечер, малиот Ламбе и праќа на малата Елена тајни пораки преку електронска пошта (е-маил). Знаејќи дека електронските пораки на Ламбе патуваат незаштитени преку мрежата на својот пат до електронското сандаче на Елена, Ламбе решил да ги криптира своите пораки на следниов начин:

Електронските пораки на Ламбе се состојат од неколку знаци од латиничната азбука. Енкрипцијата на пораките се состои од едноставно доделување на вредност на секој знак (на буквата 'A' и доделуваме вредност 1, на 'B' вредност 2, итн. се до 'Z', на која и доделуваме вредност 26). На пример, зборот, "AVION" ќе има вредност 12291514 ('A' e 1, 'V' e 22, 'I' e 9, 'O' e 15', и 'N' e 14).

Но, приметете дека кога Елена ќе добие нова порака, таа не може секогаш еднозначно да ја декодира. На пример, пораката 25114 може да се декодира на 6 начини ("BEAN", "BEAAD", "YAAD", "YAN", "YKD" и "BEKD"), а пораката 12291514 може да се декодира на 12 начини ("AVION", "ABBIAEAD", ...).

Ваша задача е да напишете програма која ќе пресмета на колку различни начини може да се декодира една порака, кодирана на горенаведениот начин.

Влез

Првиот и единствен ред содржи валидна кодираната порака, со не повеќе од 250 цифри (ниту еден код нема да започнува со 0).

Излез

Излезот се состои од еден ред во кој треба да го отпечатите бројот на можни декодирања на влезниот код. Решенијата на сите тест случаи ќе бидат помали од 2^31.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
25114

излез
6