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$.