C0098 [WC2016-B]论战捆竹竿

这是一个美好的下午，小 W 和小 C 在竹林里切磋捆竹竿的技艺。

竹林里有无数根完全一样的短竹子，每一根竹子由 $𝑛$ 节组成。这些竹子比较特别，每一节都被染上了颜色。可能的颜色一共 26 种，分别用小写英文字母 a 到 z 表示。也就是说，如果把竹子的底端到顶端的颜色按顺序写出来可以排成一个由小写英文字母组成的字符串。

小 W 和小 C 都是捆竹竿的高手，他们知道怎样才能把零散的短竹子捆成一整根长竹竿。初始时你拿着一根短竹子作为当前的竹竿。每次你可以选择一根短竹子，短竹子底端若干节（可以是 0 节）与竹竿的最上面若干节对应地一节一节捆起来，而短竹子前面剩下的节伸出去，这样就得到了一根更长的竹竿。注意，竹子的底端是靠近根部的那一端，不可以颠倒。

小 W 对竹竿的审美要求很高，他捆竹竿时有一个癖好：如果两根竹子的某两节被捆在了一起，那么它们的颜色必须相同。

我们假设一根短竹子从底端到顶端每节的颜色为 aba。

那么两根竹子可以首尾捆在一起，可以得到一根颜色为 abaaba 的竹竿；也可以将第一根顶端的一节 a 与第二根底端的一节 a 捆在一起，得到一根颜色为 ababa 的竹竿；还可以直接将每一节都对应起来，捆成一根颜色为 aba 的竹竿。

假设我们在颜色为 ababa 的竹竿顶端再捆一根竹子，则可以捆成 ababaaba， abababa 和 ababa 三种不同的情况。

但是小 C 在这个问题上有不同的看法，他认为小 W 捆不出很多种长度不同的竹竿。小 W 非常不服，于是他找到了你——现在请你求出在竹竿长度不超过 $𝑤$ 的情况下，小W可以捆出多少种长度不同的竹竿。其中，竹竿的长度指从底端到顶端的竹子的节的个数。

注意：如果 $𝑤 < 𝑛$，则没有合法的长度，此时答案为 0。

样例输入 1

1
4 11
bbab

样例输出 1

5

样例输入 2

2
44 1000
baaaaaabaabbaaabbbbabbbaaabbbababaaabaaabaaa
41 1000
abaabbabaaabaabbbbbbbbbbbababbbbaaabaabbb

样例输出 2

195
24