서로 다른 부분 문자열

Diana는 이상한 웹사이트에서 Long Random String Generator를 하나 샀다. 길이 $n$의 긴 문자열 $s$를 생성한 뒤, 그 연속 부분 문자열을 다른 이상한 웹사이트의 비밀번호로 쓰려고 했다.

그런데 곧 길이 $n$의 생성된 문자열 $s$가 전혀 무작위가 아니라, 길이 $k$의 문자열 $p$를 여러 번 반복한 뒤 길이 $n$에서 자른 것이라는 사실을 알게 되었다. 즉, $0 \le i \le n-1$인 모든 $i$에 대해 $s[i] = p[i \bmod k]$이다.

Diana는 생성된 문자열에서 서로 다른 비밀번호를 몇 개나 얻을 수 있는지 궁금해한다. 문자열 $s$에 있는 서로 다른 비어 있지 않은 부분 문자열의 개수를 구하자.

첫 번째 줄에는 $k$개의 소문자 영어 알파벳으로 이루어진 문자열 $p$가 주어진다. ($1 \le k \le 1000$)

두 번째 줄에는 정수 $n$이 주어진다. ($k \le n \le 10^9$)

$s$에 있는 서로 다른 비어 있지 않은 부분 문자열의 개수를 출력한다.

첫 번째 예제에서 생성된 문자열은 abbaabb이다. 여기에는 서로 다른 비어 있지 않은 부분 문자열이 20개 있다. a, b, aa, ab, ba, bb, aab, abb, baa, bba, aabb, abba, baab, bbaa, abbaa, baabb, bbaab, abbaab, bbaabb, abbaabb.