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 \bmod 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\le k\le 1000$$$).
The second line contains an integer $$$n$$$ ($$$k\le n\le 10^9$$$).
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.
