P10593 BZOJ2958 序列染色

题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

给出一个长度为 $n$，由 $\tt B,W,X$ 三种字符组成的字符串 $S$，你需要把每一个 $\tt X$ 染成 $\tt B$ 或 $\tt W$ 中的一个。 对于给出的 $k$，问由多少种染色方式，使得存在整数 $a,b,c,d$ 满足： - $1\leq a\leq b

第一行输入两个正整数 $n,k$； 第二行输出一个长度为 $n$ 的字符串 $S$。

输出一行，包含一个整数，表示答案。

对于 $20\%$ 的数据，$1\leq n\leq 20$； 对于 $50\%$ 的数据，$1\leq n\leq 2000$； 对于 $100\%$ 的数据，$1\leq n,k\leq 10^6$。