문제
부분 문자열은 기존 문자열에서 0개 이상의 문자를 지워 만든 문자열입니다. 길이가 N인 문자열은 총 2^N개의 부분 문자열을 가지고 있습니다. 이 때 같은 부분 문자열이 여러번 나올 수도 있습니다. 예를 들어 문자열 "zoo"는 8개의 부분 문자열이 있지만 중복을 제외하면 6개가 됩니다.
부분 문자열 "z", "oo", "zoo"는 한 번만 나타납니다. 텅 빈 부분 문자열도 한 번만 나타납니다. 부분 문자열 "o", "zo"는 두 번씩 나타납니다.
우리는 부분 문자열의 중복을 찾기 위하여 '반복성'이라는 지표를 만들었습니다. 문자열 S가 k개의 다른 부분 문자열을 가지고 있고, i번째 부분 문자열이 fi번 나타난다고 가정합시다. 그럼 이 문자열 S의 반복성은 f1^2 + ... + fk^2 입니다.
즉, 문자열 "zoo"의 반복성은 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12 입니다.
문자열 S가 주어지면 S의 반복성을 구하는 프로그램을 작성하세요.
입력
첫 번째 줄에는 문자열 S (길이 10000 이하의 문자열)를, 두 번째 줄에는 정수 M (2 ≤ M ≤ 1 000 000 000)을 입력받습니다. 문자열 S는 아스키 값 33과 126 사이의 문자들로 이루어져있습니다. (이 문자들은 전부 공백이 없는 출력 가능한 문자들입니다.)
출력
첫 줄에 문자열 S의 반복성을 M으로 나눈 나머지를 출력하세요.
예제 #1
zoo
10
2
예제 #2
@#$%
16
16
출처
Canadian Computing Competition 2013
로그인해야 코드를 작성할 수 있어요.