AT_abc032_b [ABC032B] 高橋君とパスワード

[problemUrl]: https://atcoder.jp/contests/abc032/tasks/abc032_b 高橋君の会社には、秘密の金庫があります。この金庫にはパスワードをかけているのですが、高橋君はそのパスワードを忘れてしまいました。 しかし、幸運なことに、手元にはパスワードのヒントが以下のように書かれていました。 - パスワードは、この紙に書かれている文字列 $ 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 $ 行目に、パスワードとして考えられる文字列の数を出力せよ。末尾の改行を忘れないこと。

### Sample Explanation 1 パスワードとしてありうる部分文字列の集合は、{`ab`,`bc`,`ca`} です。 ### Sample Explanation 2 パスワードとしてありえる部分文字列は、`a` のみです。