You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

题目描述

高桥君的公司里有一个秘密的金库。由于这个金库需要密码才能进入，而高桥君已经忘记了这个密码。但是幸运的是，他的手边有这个密码的提示，提示是以下这样写的。

• 密码为这张纸上写着的字符串s的长为k的某个子串。

高桥君只需试完所有可能的密码就能打开金库，他因此很高兴~但是，字符串s非常长因此密码的可能情况有很多种。很明显，重复的密码没有必要再试一遍。所有在亲自将所有密码试一遍之前，需要数出有多少种不同的密码。

你的任务就是将给定的字符串s中需要试的相异密码的个数告诉高桥君。

字符串s的“子串”指，字符串s里所含的一段区间的字符取出所得字符串。例如：$abc$的子串有：$a$,$b$,$c$,$ab$,$bc$,$abc$。而请注意，像$ac$或$ba$这样的字符串并非$abc$的子串。

输入输出格式

输入格式

输入遵从以下形式：

$s$ $k$

• 第一行给定的是纸上写有的字符串s，也就是密码的提示。$(1≤length(s)≤300)$s中只含a-z小写英文字母。
• 第二行给定的是密码的长度k$(1≤k≤300)$。k可能比s的长度更大。

输出格式

输出按照以下格式。

在第一行输出可能的密码总数。别忘了在最后换行。

输入输出样例

输入样例#1：

abcabc
2

输出样例#1：

3

输入样例#2：

aaaaa
1

输出样例#2：

1

输入样例#3：

hello
10

输出样例#3：

题目描述

高橋君の会社には、秘密の金庫があります。この金庫にはパスワードをかけているのですが、高橋君はそのパスワードを忘れてしまいました。 しかし、幸運なことに、手元にはパスワードのヒントが以下のように書かれていました。

• パスワードは、この紙に書かれている文字列 $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

样例输入 #1

abcabc
2

样例输出 #1

3

样例 #2

样例输入 #2

aaaaa
1

样例输出 #2

1

样例 #3

样例输入 #3

hello
10

样例输出 #3

0

提示

Sample Explanation 1

パスワードとしてありうる部分文字列の集合は、{ab,bc,ca} です。

Sample Explanation 2

パスワードとしてありえる部分文字列は、a のみです。