Problem description

Jasio wymyślił bardzo “sprytną” (albo raczej głupią) metodę kodowania napisów. Literka a dostaje kod 1, literka b kod 2, literka z kod 26 (Jasio zna jedynie małe litery alfabetu angielskiego). Uzyskane kody Jasio skleja ze sobą i otrzymuje kodowanie całego napisu. W ten sposób słowo olimpiada otrzymuje kod 1512913169141. Oczywiście kodowanie nie jest jednoznaczne, ale o tym Jasio nie pomyślał wcześniej.

Otrzymałeś od Jasia zakodowany napis. Co on mógł oznaczać? Napisz program, który wczyta kodowanie Jasia, wyznaczy resztę z dzielenia przez 10⁹ + 7 liczby wszystkich możliwych napisów, które mogły uzyskać takie kodowanie i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się ciąg cyfr (bez żadnych odstępów) – kodowanie pewnego napisu uzyskane metodą Jasia.

Wyjście

Twój program powinien wypisać na wyjście resztę z dzielenia przez 10⁹ + 7 liczby wszystkich napisów, które prowadzą do uzyskania kodowania z wejścia.

Ograniczenia

Długość ciągu cyfr podanego na wejściu nie przekracza 100 000 znaków.

Przykład

261411495

12