题目描述

「Madoka，不要相信QB！」伴随着Homura的失望地喊叫，Madoka与QB签订了契约。 这是Modoka的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次Madoka不再与QB签订契约，Homura决定在刚到学校的第一天就解决QB。然而，QB也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的Homura是不会放弃的——她决定消灭所有可能是QB的东西。现在，她已感受到附近的状态，并且把它转化为一个长度为n的字符串交给了学OI的你。 现在你从她的话中知道，所有形似于A+B+A的字串都是QB或它的替身，且$|A| \ge k,|B| \ge 1$（位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），然后你必须尽快告诉Homura这个答案——QB以及它的替身的数量。 注：对于一个字符串S，|S|表示S的长度。

输入描述

第一行一个字符串S，第二行一个数k。

输出描述

仅一行一个数$\text{ans}$，表示QB以及它的替身的数量。

示例1

输入

aaaaa
1

输出

6

示例2

输入

abcabcabc
2

输出

8

备注

对于全部数据，$1 \le |S| \le 1.5 \times 10^4,1 \le k \le 100$，且字符集为所有小写字母。