本题是《序列染色》的加强版

题目描述

小明有一个长度为$n$的序列，一开始这个序列都是白色。

小明想执行$m$次染色操作，第$i$次操作，小明将选择一段区间（可能是空区间），然后把这一段区间染色成颜色$s_i$（$s_i$必然是红或者蓝之一），如果一个位置之前已经有颜色了，则这次染色会覆盖之前的颜色。

问：经过这$m$次操作后，小明的序列有多少种不同的可能。

输入格式

第一行输入$n,m$。

第二行输入字符串$s$，保证每个位置是b,r中的一种。

输出格式

输出一个数字表示答案。

样例输入 #1

2 2
br

样例输出 #1

9

样例解释 #1

一共有如下$9$种可能：[..],[.b],[.r],[b.],[bb],[br],[r.],[rb],[rr]。

样例输入 #2

4 2
br

样例输出 #2

56

样例解释 #2

[....],[...b],[...r],[..b.],[..bb],[..br],[..r.],[..rb],[..rr],[.b..],[.b.r],[.bb.],[.bbb],[.bbr],[.br.],[.brb],[.brr],[.r..],[.r.b],[.rb.],[.rbb],[.rr.],[.rrb],[.rrr],[b...],[b..r],[b.r.],[b.rr],[bb..],[bb.r],[bbb.],[bbbb],[bbbr],[bbr.],[bbrb],[bbrr],[br..],[brb.],[brbb],[brr.],[brrb],[brrr],[r...],[r..b],[r.b.],[r.bb],[rb..],[rbb.],[rbbb],[rr..],[rr.b],[rrb.],[rrbb],[rrr.],[rrrb],[rrrr]。

样例输入 #3

8 8
bbbbrbrr

样例输出 #3

6544

样例输入 #4

10 10
bbrbbrbbrr

样例输出 #4

59028

样例输入 #5

12 12
bbbrbbbrbbbr

样例输出 #5

496109

数据范围

对于所有数据：$1\leq n\leq 20,1\leq m\leq 10^5$。