题号：NC50325
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
「Madoka，不要相信QB！」伴随着Homura的失望地喊叫，Madoka与QB签订了契约。
这是Modoka的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次Madoka不再与QB签订契约，Homura决定在刚到学校的第一天就解决QB。然而，QB也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的Homura是不会放弃的——她决定消灭所有可能是QB的东西。现在，她已感受到附近的状态，并且把它转化为一个长度为n的字符串交给了学OI的你。
现在你从她的话中知道，所有形似于A+B+A的字串都是QB或它的替身，且
（位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），然后你必须尽快告诉Homura这个答案——QB以及它的替身的数量。
注：对于一个字符串S，|S|表示S的长度。
这是Modoka的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次Madoka不再与QB签订契约，Homura决定在刚到学校的第一天就解决QB。然而，QB也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的Homura是不会放弃的——她决定消灭所有可能是QB的东西。现在，她已感受到附近的状态，并且把它转化为一个长度为n的字符串交给了学OI的你。
现在你从她的话中知道，所有形似于A+B+A的字串都是QB或它的替身，且
注：对于一个字符串S，|S|表示S的长度。
输入描述:
第一行一个字符串S，第二行一个数k。
输出描述:
仅一行一个数，表示QB以及它的替身的数量。
备注:
对于全部数据，，且字符集为所有小写字母。