배너

Äčm 의장의 즉위 기념 행진을 하루 앞두고, 배너 공장에 급한 주문이 들어왔다. 매우 중요한 주문이다. 이 배너가 제때 완성되지 않으면 아이들이 고아원에서 자라게 될지도 모른다. (아마 그냥 지나친 걱정일 수도 있다. Äčm 의장이 유명하게 말했듯이 "우리 나라는 큰 숫자와 놀라운 우연의 축복을 받았다.") 공장에는 26대의 기계가 있고, 각 기계는 서로 다른 대문자 하나를 천에 빠르게 박음질하도록 특화되어 있다. 배너는 대문자로 이루어진 문자열이다. 하루의 시작에 26대의 기계를 일렬로 세운다. 이 줄의 비어 있지 않은 연속 부분 문자열은 무엇이든 배너에 박음질할 수 있다. 비어 있지 않은 부분 문자열은 $26 \times 27 / 2 = 351$개이다. 그다음 작업자가 배너를 만든다. 작업자는 매시간 아직 박음질하지 않은 가장 왼쪽 글자에서 시작해, 그 위치에서 시작하는 가장 긴 부분 문자열을 박음질한다. 부분 문자열 하나를 박음질하는 데는 정확히 1시간이 걸리며, 한 번에 하나의 부분 문자열만 박음질할 수 있다. 그림 B.1: 입력 예 2에 대한 최적 순열 중 하나. 예를 들어 그림 B.1의 순열에서 박음질할 문자열이 HURRAHPATRIOT이면, 배너는 6시간에 완성된다. 1시간째에 HUR, 2시간째에 R, 3시간째에 AH, 4시간째에 PA, 5시간째에 T, 6시간째에 RIOT를 박음질한다. 어떤 기계 순열도 배너를 더 적은 시간에 완성할 수 없으면 그 순열은 최적이다. 최적인 순열은 몇 개인가?

입력은 배너에 박음질할 문자열이 적힌 한 줄이다. 문자열은 대문자로만 이루어지며, 길이는 1 이상 35 이하이다.

Äčm 의장이 좋아하는 네 소수 1000000007, 1000000009, 1000000021, 1000000033 각각으로 나눈 나머지를 최적 순열의 개수에 대해 구하여 출력한다.