题目描述

高桥君的公司里有一个秘密的保险箱。这个保险箱需要密码才能打开，但是高桥君忘记了密码。幸运的是，他手头有一张写有密码提示的纸：

密码是写在这张纸上的字符串 $s$ 的一个长度为 $k$ 的连续子串（※）。

高桥君很高兴，他觉得只要把所有可能的密码都试一遍就能打开保险箱！但是，字符串 $s$ 可能很长，并且同一个子串在 $s$ 中可能会出现多次。显然，没有必要重复尝试相同的密码。因此，在手动尝试所有密码之前，他想先数一数一共需要尝试多少种不同的密码。

你的任务是，根据给定的字符串 $s$ 和整数 $k$，帮助高桥君计算出他需要尝试的不同密码的数量。

字符串 $s$ 的“子串”是指从字符串 $s$ 中截取出的一段连续的字符序列。例如，abc 的子串包括 a、b、c、ab、bc、abc 等。请注意，ac 或 ba 等不是它的连续子串。

输入格式

第一行包含一个字符串 $s$ —— 表示提示纸上写的字符串。

第二行包含一个整数 $k$ —— 表示可能的密码长度。

输出格式

输出一行，一个整数，表示可能的不同密码的数量。

样例输入 1

abcabc
2

样例输出 1

3

样例输入 2

aaaaa
1

样例输出 2

1

样例输入 3

hello
10

样例输出 3

0

说明

样例解释

• 在第一个样例中，长度为 $2$ 的子串有 ab、bc、ca、ab、bc。去重后可能的密码集合为 {"ab", "bc", "ca"}，共有 $3$ 种。
• 在第二个样例中，可能的密码集合只有 {"a"}，共有 $1$ 种。
• 在第三个样例中，字符串的长度为 $5$，不存在长度为 $10$ 的子串，因此共有 $0$ 种可能的密码。

数据范围

• 对于所有测试点，保证 $1 \le |s| \le 300$，其中 $|s|$ 表示字符串 $s$ 的长度。
• 保证 $s$ 仅由小写英文字母（$a \sim z$）组成。
• 对于所有测试点，保证 $1 \le k \le 300$。注意 $k$ 的值可能大于 $|s|$。