Distinct Substrings

길이 k인 패턴을 길이 n까지 반복해 만든 문자열에서 서로 다른 비어 있지 않은 부분 문자열의 개수를 센다. n은 10억까지 커질 수 있다.

어려움9문자열문자열 매칭수학조합론아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제 설명

예제2

문제

Diana bought a Long Random String Generator on some weird website. She planned to generate a long string s of length n and then use its contiguous substrings as passwords for other weird websites.

Soon she discovered that the generated string s of length n was not random at all, but rather a string p of length k repeated many times and then cut to length n. Thus, s[i] = p[i mod k] for all i from 0 to n − 1.

Diana wonders how many different passwords she can get from the generated string. Help her find the number of distinct non-empty substrings in string s.

입력

The first line of the input contains a string p consisting of k lowercase English letters (1 ≤ k ≤ 1000).

The second line contains an integer n (k ≤ n ≤ 109).

출력

Output the number of distinct non-empty substrings in s.

힌트

In the first example, the generated string is abbaabb. It contains 20 distinct non-empty substrings: a, b, aa, ab, ba, bb, aab, abb, baa, bba, aabb, abba, baab, bbaa, abbaa, baabb, bbaab, abbaab, bbaabb, abbaabb.