Luogu侧点这里

题目背景

2022-08-01，@tiger2008被拉去集训了（悲 以下 tiger2008 用 tiger代替

屑tiger的机房比较神奇，他准备挑选一个好位置

因为屑tiger有一颗想摸鱼的心，所以他不想被别人看见(看见就死啦)

他想让你帮忙统计一下这个机房的视野情况(?)

题目描述

$$\kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt}\kern{-11pt} \rule[66pt]{11pt}{2pt}\kern{-11pt} \rule[77pt]{11pt}{2pt}\kern{-11pt} \rule[88pt]{11pt}{2pt}\kern{-11pt} \rule[99pt]{11pt}{2pt} \kern{-1.5pt} \rule{2pt}{101pt}\quad \rule{2pt}{101pt}\quad \kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt}\kern{-11pt} \rule[66pt]{11pt}{2pt}\kern{-11pt} \rule[77pt]{11pt}{2pt}\kern{-11pt} \rule[88pt]{11pt}{2pt}\kern{-11pt} \rule[99pt]{11pt}{2pt}\kern{-25.5pt} \raisebox{-10px}{l}\kern{15pt} \raisebox{-10px}{r}\kern{-17.5pt} \raisebox{-20px}{图1}\kern{51pt} \kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt}\kern{-11pt} \rule[66pt]{11pt}{2pt}\kern{-11pt} \rule[77pt]{11pt}{2pt}\kern{-11pt} \rule[88pt]{11pt}{2pt}\kern{-11pt} \rule[99pt]{11pt}{2pt} \kern{-1.5pt} \kern{-10pt} \rule{2pt}{101pt}\quad \kern{20pt} \rule{2pt}{101pt}\quad \kern{-12pt} \kern{-10pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt}\kern{-11pt} \rule[66pt]{11pt}{2pt}\kern{-11pt} \rule[77pt]{11pt}{2pt}\kern{-11pt} \rule[88pt]{11pt}{2pt}\kern{-11pt} \rule[99pt]{11pt}{2pt}\kern{-25.5pt} \raisebox{-10px}{r}\kern{15pt} \raisebox{-10px}{l}\kern{-17.5pt} \raisebox{-20px}{图2} $$

这是两种长为9的电脑组$l$和$r$(如图1)，上面每个空都可以坐$1$个人

当两个人能互相看到，当且仅当他们中间没有挡板 也就是说，只有$r$和$l$并在一起时，两组的人能互相看到(如图2)

tiger会告诉你机房电脑组数$n$和每组电脑数$m$，和每组的类型($l$,$r$)，他想问你，有几对人可以互相看到？ 最神牛的你一定能在$500ms$内算出来吧（？

输入格式

第一行输入$2$个整数$n,m$，意思如题目描述所述

第二行输入一个长度为$n$的字符串(仅包含$l$和$r$)，代表电脑组的类型

输出格式

输出$1$个整数，代表有几对人可以互相看见

tiger觉得人多了数据不好处理，所以请输出答案$\mod 10^9+7$的值

样例 #1

样例输入 #1

5 5
lrlrl

样例输出 #1

50

提示

$$\kern{-60pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt} \kern{-1.5pt} \rule{2pt}{57pt}\quad \kern{10pt} \rule{2pt}{57pt}\quad \kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt} \kern{-1.5pt} \kern{30pt} \kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt} \kern{-1.5pt} \rule{2pt}{57pt}\quad \kern{10pt} \rule{2pt}{57pt}\quad \kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt} \kern{-1.5pt} \kern{30pt} \kern{-12pt} \rule[0pt]{11pt}{2pt}\kern{-11pt} \rule[11pt]{11pt}{2pt}\kern{-11pt} \rule[22pt]{11pt}{2pt}\kern{-11pt} \rule[33pt]{11pt}{2pt}\kern{-11pt} \rule[44pt]{11pt}{2pt}\kern{-11pt} \rule[55pt]{11pt}{2pt} \kern{-1.5pt} \rule{2pt}{57pt}\quad \kern{-95pt} \raisebox{-20px}{样例解释} $$

样例中有$2$组可以互相看见，所以结果为$5^2\times2=50$

数据范围

对于$20\%$的数据，$n,m\leq10$

对于$40\%$的数据，$n,m\leq10^3$

对于$70\%$的数据，$n.m\leq10^5$

对于$100\%$的数据，$n,m\leq10^7$

不是这机房有这么大吗