시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 79 | 24 | 18 | 33.962% |
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.
abba 7
20
a 42
42
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
.