Problem Description

Takahashi has a secret safe in his company. The safe is protected by a password, but Takahashi has forgotten it. Fortunately, he has a hint written on a piece of paper as follows:

• The password is one of the length $ k $ substrings of the string $ s $ written on this paper.

Takahashi was delighted, thinking he could open the safe by trying all possible passwords. However, the string $ s $ could be very long, and the same substring might appear multiple times within the string $ s $. Clearly, there is no need to try the same password repeatedly. Therefore, before manually trying all passwords, he decided to count how many different passwords need to be tried.

Your task is to tell Takahashi how many different passwords need to be tried, given the content of the string $ s $.

(※) A "substring" of string $ s $ is a string that can be obtained by taking any contiguous segment from string $ s $. For example, substrings of abc include a, b, c, ab, bc, abc, etc. Note that ac or ba are not substrings.

Input Format

The input is given from the standard input in the following format:

$ s $ $ k $

• The first line contains the string $s\ (1≦|s|≦300)$, which is written on the hint paper. $ s $ consists only of lowercase English letters (a-z). $ |s| $ denotes the length of the string $ s $.
• The second line contains the integer $k\ (1≦k≦300)$, which is the length of the possible passwords. $ k $ may be greater than $ |s| $.

Output Format

Output the following to the standard output:

The first line should contain the number of different strings that can be considered as passwords. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

abcabc
2

Sample Output #1

3

Sample Input #2

aaaaa
1

Sample Output #2

1

Sample Input #3

hello
10

Sample Output #3

0

Notes/Hints

Sample Explanation 1

The set of possible password substrings is {ab, bc, ca}.

Sample Explanation 2

The only possible password substring is a.

见题面 Input 部分

见题面 Output 部分