問題文

高橋君的公司有一个秘密金库。这个金库被设置了密码，但是高橋君忘记了密码。幸运的是，他手头上有一个密码提示，写着以下内容：

• 密码是字符串 $s$ 的长度为 $k$ 的子串（※）之一。

高橋君很高兴地想到，只要尝试所有可能的密码，就可以打开金库！然而，字符串 $s$ 可能非常长，并且字符串 $s$ 中可能存在多个相同的子串。显然，重复尝试相同的密码是没有必要的。因此，他决定在手动尝试所有密码之前，先计算需要尝试的不同密码的数量。

你的任务是给出字符串 $s$ 的内容，并告诉高橋君需要尝试的不同密码的数量。

（※）字符串 $s$ 的「子串」是指从字符串 $s$ 中取出的某个区间的子字符串。例如，abc 的子串可以是 a、b、c、ab、bc、abc 等。请注意，ac 或 ba 不是子串。

入力

输入以以下格式从标准输入给出。

$s$ $k$

• 第 1 行包含密码提示纸上的字符串 $s (1≦|s|≦300)$。其中 $s$ 由小写英文字母（a-z）组成。$|s|$ 表示字符串 $s$ 的长度。
• 第 2 行包含可能的密码长度 $k (1≦k≦300)$。 $k$ 可能大于 $|s|$。

出力

输出结果以以下格式发送到标准输出。

在第 1 行输出可作为密码的字符串数量。不要忘记输出换行符。

入力例1

abcabc
2

出力例1

3

作为密码可能的子串集合是：{ab,bc,ca}。

入力例2

aaaaa
1

出力例2

1

作为密码可能的子串只有 a。

入力例3

hello
10

出力例3

0