Во время последней секретной операции Капитану Марвел удалось выкрасть закодированное
секретное сообщение скруллов — строку s. Однако, в закодированном виде никакой полезной информации оно из себя не представляет, поэтому его непременно нужно раскодировать.
Несмотря на развитость скруллов, их система кодирования сообщений проста и общеизвестна:
• Перед кодированием сообщения выбирается цифра d (0 <= d <= 9)
• Символы сообщения рассматриваются слева направо
• У каждого символа сообщения вычисляется его ASCII-код (например, у «a» он равен 97, у
«b» — 98, у «z» — 122)
• Если код трехзначный, он дописывается к текущей закодированной строке как есть, если же
код двузначный, к нему в случайное место добавляется цифра d и полученный результат
дописывается к текущей закодированной строке (например, если d = 3, а текущая буква —
«a», к текущей закодированной строке могут дописатсья числа 397, 937 или 973)
• После обработки всех букв, результатом считается полученная закодированная строка
Число d обычно передается вместе с сообщением, но Капитану Марвел не удалось его найти. Однако, она точно знает, что исходное сообщение состояло только из строчных и заглавных латинских
букв. Она понимает, что без числа d раскодировать сообщение однозначно может не получиться, поэтому для начала хочет посчитать, сколько существует различных строк t, состоящих из строчных
и заглавных латинских букв, таких, что, закодировав их, получится строка s. Так как наша героиня
не может быть полностью уверена, что сообщение было перехвачено полностью, вполне возможно,
что его невозможно декодировать ни одним способом.
Помогите нашей героине — найдите количество этих строк по модулю 109 + 7.
Формат входных данных
В единственной строке содержится закодированная строка s, выкраденная Капитаном Марвел
(3 <= |s| <= 105). Гарантируется, что строка s состоит только из цифр, а также что ее длина кратна 3.
Формат выходных данных
В единственной строке выведите одно число — количество различных строк, состоящих из строчных и заглавных латинских букв, которые кодируются в строку s, по модулю 109 + 7.
| Ввод |
Вывод |
| 988 |
2 |
| 100905 |
1 |
| 600 |
0 |
Замечание
В первом примере закодированную строку можно получить из «b», если d = 8, а также из «X», если d = 9.
Во втором примере закодированную строку можно получить только из «dZ» при d = 5.