프로그램 명: ccc_rep(open)
제한시간: 5 초

어떤 문자열이든 길이가 n이면 2^n개의 부분 문자열을 가지고 있습니다. 부분 문자열은 기존 문자열이서 임의의 문자를 지워 만든 문자열입니다. 그런데 어떤 부분 문자열은 여러번 나올 수도 있습니다. 예를들어 문자열 "zoo"는 6개의 다른 부분 문자열을 가지고 있습니다

부분 문자열 "z", "oo", "zoo"는 한 번만 나타납니다. 텅 빈 부분 문자열도 한 번만 나타납니다. 부분 문자열 "o", "zo"는 두 번씩 나타납니다.

문자열 S가 k개의 다른 부분 문자열을 가지고 있고, i번째 부분 문자열이 fi번 나타난다고 가정합시다. 그럼 이 문자열 S의 반복성을 다음과 같은 식으로 나타낼 수 있습니다.

문자열 "zoo"의 반복성은

이 됩니다.

입력

각 테스트 케이스는 문자열 S (길이 10000 이하의 문자열)와 정수 M (2 ≤ M ≤ 1 000 000 000)으로 이루어져있습니다. 문자열 S는 아스키 값 33과 126 사이의 문자들로 이루어져있습니다. (이 문자들은 전부 공백이 없는 출력 가능한 문자들입니다)

출력

첫 줄에 문자열 S의 반복성을 M으로 나눈 나머지를 출력하세요.

입출력 예

입력

zoo
10

출력

2

입력

@#$%
1000000

출력

16
※공식들은 Daum Equation Editor를 이용했습니다. 
출처:CEMC (CCC 2013 Stage 2)
번역:ladown21
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]