28846번 - Декодирование сообщения 다국어

문제

Во время последней секретной операции Капитану Марвел удалось выкрасть закодированное секретное сообщение скруллов --- строку $s$. Однако, в закодированном виде никакой полезной информации оно из себя не представляет, поэтому его непременно нужно раскодировать.

Несмотря на развитость скруллов, их система кодирования сообщений проста и общеизвестна:

• Перед кодированием сообщения выбирается цифра $d$ (0ドル \le d \le 9$)
• Символы сообщения рассматриваются слева направо
• У каждого символа сообщения вычисляется его ASCII-код (например, у <<a>> он равен 97ドル,ドル у <<b>> --- 98ドル,ドル у <<z>> --- 122ドル$)
• Если код трехзначный, он дописывается к текущей закодированной строке как есть, если же код двузначный, к нему в случайное место добавляется цифра $d$ и полученный результат дописывается к текущей закодированной строке (например, если $d = 3,ドル а текущая буква --- <<a>>, к текущей закодированной строке могут дописатсья числа 397ドル,ドル 937ドル$ или 973ドル$)
• После обработки всех букв, результатом считается полученная закодированная строка

Число $d$ обычно передается вместе с сообщением, но Капитану Марвел не удалось его найти. Однако, она точно знает, что исходное сообщение состояло только из строчных и заглавных латинских букв. Она понимает, что без числа $d$ раскодировать сообщение однозначно может не получиться, поэтому для начала хочет посчитать, сколько существует различных строк $t,ドル состоящих из строчных и заглавных латинских букв, таких, что, закодировав их, получится строка $s$. Так как наша героиня не может быть полностью уверена, что сообщение было перехвачено полностью, вполне возможно, что его невозможно декодировать ни одним способом.

Помогите нашей героине --- найдите количество этих строк по модулю 10ドル^9 + 7$.

입력

В единственной строке содержится закодированная строка $s,ドル выкраденная Капитаном Марвел (3ドル \le |s| \le 10^5$). Гарантируется, что строка $s$ состоит только из цифр, а также что ее длина кратна 3ドル$.

출력

В единственной строке выведите одно число --- количество различных строк, состоящих из строчных и заглавных латинских букв, которые кодируются в строку $s,ドル по модулю 10ドル^9 + 7$.

제한

노트

В первом примере закодированную строку можно получить из <<b>>, если $d = 8,ドル а также из <<X>>, если $d = 9$.

Во втором примере закодированную строку можно получить только из <<dZ>> при $d = 5$.