블랙 펄의 저주

이미 알려진 사실이지만 배 '블랙 펄'은 실제로 존재한다. 오랫동안 유명한 선장 잭 스패로우가 이 배를 지휘했다. 배는 선장과 함께 온갖 시련을 겪었다. 학자들은 '블랙 펄'이 세상에서 가장 빠른 배라고 확인했다. 이 배는 '라지야시이'호와 '하늘을 나는 네덜란드인'호보다도 빠르다. 소문에 따르면 하늘을 나는 네덜란드인호는 바람보다 빠르게 달린다고 한다.

이슬라 데 무에르테의 보물창고를 턴 뒤 블랙 펄의 선원들과 배 자체에 저주가 내렸다. 돛이 찢어졌고 배 주위에는 으스스한 안개가 끼기 시작했다. 저주를 완전히 풀기는 어려워서 아무도 시도하지 않았다.

선창 가장 안쪽 벽의 가장 썩은 널빤지에 수수께끼가 적혀 있다. 이 수수께끼가 저주를 푸는 열쇠다. 널빤지가 매우 낡아서 일부 글자가 지워졌다. 전설에 따르면 수수께끼에는 공백이 없었고, 하나의 단어처럼 보였다. 수수께끼를 복원할 수는 없으므로 저주를 완전히 풀 수는 없다. 그래도 저주를 누그러뜨릴 수는 있다.

현자의 말에 따르면 저주를 누그러뜨리려면 금화가 든 큰 자루를 바다에 던져야 한다. 수수께끼 단어의 부분 문자열 중에서, 빈칸에 글자를 어떻게 채워 넣더라도 모든 글자가 같아질 수 있는 부분 문자열마다 동전 하나를 자루에 넣어야 한다.

수수께끼 단어가 주어질 때, 저주를 누그러뜨리기 위해 바다에 던져야 할 동전의 개수를 구하라.

입력 파일에는 길이가 $10^6$을 넘지 않는 문자열이 한 줄 주어진다. 문자열은 영소문자와 지워진 글자(빈칸)를 나타내는 물음표로 이루어져 있다.

답을 나타내는 정수 하나를 출력한다.

조건을 만족하는 부분 문자열은 첫 번째 예제의 수수께끼 단어에서 정확히 여섯 개다:

• 글자 하나로 이루어진 부분 문자열 네 개: 'a', 'b', 'c', 그리고 빈칸 '?'를 임의의 글자로 채운 경우
• 'b?' 부분 문자열, 빈칸을 'b'로 채운 경우
• '?c' 부분 문자열, 빈칸을 'c'로 채운 경우