{"raw_statement":[{"iden":"background","content":"题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。"},{"iden":"statement","content":"给出一个长度为 $n$，由 $\\tt B,W,X$ 三种字符组成的字符串 $S$，你需要把每一个 $\\tt X$ 染成 $\\tt B$ 或 $\\tt W$ 中的一个。\n\n对于给出的 $k$，问由多少种染色方式，使得存在整数 $a,b,c,d$ 满足：\n- $1\\leq a\\leq b<c\\leq d\\leq n$；\n- $b=a+k-1$，$d=c+k-1$;\n- $S_a=S_{a+1}=\\dots=S_b=\\tt B$；\n- $S_c=S_{c+1}=\\dots=S_d=\\tt W$；\n\n由于方法可能很多，你只需输出最后的答案对 $10^9+7$ 取模的结果。"},{"iden":"input","content":"第一行输入两个正整数 $n,k$；\n\n第二行输出一个长度为 $n$ 的字符串 $S$。"},{"iden":"output","content":"输出一行，包含一个整数，表示答案。"},{"iden":"note","content":"对于 $20\\%$ 的数据，$1\\leq n\\leq 20$；\n\n对于 $50\\%$ 的数据，$1\\leq n\\leq 2000$；\n\n对于 $100\\%$ 的数据，$1\\leq n,k\\leq 10^6$。"}],"translated_statement":null,"sample_group":[["5 2\nXXXXX","4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}