问题 E: 构造回文串

问题 E: 构造回文串

时间限制: 1 Sec  内存限制: 128 MB
提交: 143  解决: 56
[提交][状态][讨论版][命题人:]

题目描述

使用a,b,c三个字母构造长度恰好为n的字串,每个字母在一个串中最多可以出现k次。求可以构造的不同的回文串的数量。

回文串是指字符串中心对称,或者说正序遍历和倒序遍历得到的字串完全相同。例如abcba,12233221等。


输入

输入仅一行,包含两个整数n,k,分别为目标字串的长度和每个字母在同一串中可以出现的最多次数。

输出

输出仅一行,包含一个整数,即所求得的方案数。

样例输入

3 2

样例输出

6

提示


对于样例,可以构造的六种回文串是:



aba aca bab bcb cac cbc



保证3 * k >= n,(n<=30)即可用的字母一定能构造出长度为n的字串。

[提交][状态]