반복도

길이가 $n$인 문자열은 문자들의 어떤 부분집합을 지워서 얻는 $2^n$개의 부분 수열(subsequence)을 가진다. 하지만 이 부분 수열들이 모두 서로 다른 것은 아니다. 예를 들어 문자열 "zoo"가 가지는 서로 다른 부분 수열은 6개뿐이다.

• "z", "oo", "zoo"는 각각 한 번씩만 나타나고,
• 빈 부분 수열도 한 번만 나타나며,
• "o"와 "zo"는 각각 두 번씩 나타난다.

문자열 $S$에 서로 다른 부분 수열이 $k$개 있고, 그중 $i$번째 부분 수열이 $f_i$번 나타난다고 하자. 이때 $S$의 반복도(repetitivity) 를 $\sum_{i=1}^{k} f_i^2$로 정의한다. 예를 들어 "zoo"의 반복도는

$$1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12$$

이다.

첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 최대 $10000$이다. 둘째 줄에 정수 $M$이 주어지며 $2 \le M \le 10^9$을 만족한다. $S$는 ASCII 코드가 $33$ 이상 $126$ 이하인 문자만 포함한다(모두 출력 가능하고 공백이 아닌 문자이다).

$S$의 반복도를 $M$으로 나눈 나머지를 첫째 줄에 출력한다.