6547 - 似乎在梦中见过的样子

“Madoka，不要相信QB！”伴随着Homura失望的喊叫，Madoka与QB签订了契约。

这是Madoka的一个噩梦，也同时是上个是轮回中发生的事。为了使这一次Madoka不再与QB签订契约，Homura决定刚到学校的第一天就解决QB。然而，QB也是由许多替身的（但在第八回中的剧情显示它也有可能是无限重生的），不过一直坚定地Homura是不会放弃的——她决定，消灭所有可能是QB的东西。现在，她已经感受到附近的状态，并且把它转化为一个长度为n的字符串交给了学OI的你。

现在你从她的话中知道，所有形似于A+B+A的字符串都是QB或它的替身，且len（A）≥k，len（B）≥1（位置不同，其他性质相同的子串算不同子串，位置相同单拆分不同的子串算同一子串），然后你必须尽快告诉Homura这个答案——QB以及它的替身的数量。

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

仅一行一个数ans，表示QB以及它的替身的数量。

一本通