| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Всем известно, что корабль <<Черная жемчужина>> на самом деле существует. Долгое время им командовал всем извеcтный капитан Джек Воробей. И этот корабль, вместе со своим капитаном прошел огонь, воду и медные трубы. Так же учеными установлено, что <<Черная жемчужина>> является самым быстроходным кораблем в мире. Она даже быстрее, чем <<Разящий>> и <<Летучий голландец>>, про который говорят, что он ходит быстрее ветра.
После ограбления сокровищницы на Исла де Муэрте на команду <<Чёрной Жемчужины>> легло проклятие, которое повлияло и на сам корабль: паруса корабля порвались, а само судно стал окружать жутковатый туман. Снять проклятие было достаточно сложно, и поэтому никто не стал этого делать.
В трюме корабля, на самой гнилой доске самой дальней стены, написана загадка, которая является ключом к снятию проклятия. Доска очень старая, и из-за этого некоторые буквы на ней стерлись. Согласно легендам, в загадке не было пробелов, то есть она выглядела как одно слово. Поскольку загадку восстановить уже нельзя, снять проклятие не представляется возможным. Однако, его можно попробовать смягчить.
Если верить Мудрецу, для смягчения проклятия нужно выбросить за борт большой мешок с золотом. За каждую подстроку слова-загадки, в которой, при каком-нибудь заполнении пропусков буквами, все буквы могли оказаться одинаковыми, в мешок необходимо положить одну монету.
Вам дана загадка, определите, сколько монет нужно выбросить за борт для смягчения проклятия.
Во входном файле дана строка, длина которой не превышает 10ドル^6$. Строка состоит из строчных латинских букв и знаков вопроса, обозначающих стертую букву (пропуск).
Выведите одно число --- ответ на задачу.
ab?c
6
aa??b?c
19
Описанным в условии требованиям отвечают ровно шесть подстрок слова-загадки из первого примера: