题目描述

给定一个长度为 $n$ 的序列 $a$ 和一个仅包含字符 L 和 R 的长度为 $k$ 的字符串 $S$，你需要对这个序列执行 $k$ 次操作，对于第 $i$ 次操作：

• 若序列长度为 $1$，不需要执行任何操作。
• 否则，设当前序列长度为 $m$，均匀随机地在 $[1,m-1]$ 中选择一个整数 $x$，将当前 $a$ 切割为 $a[1,x]$ 和 $a[x+1,m]$。接下来，如果 $S_i$ 等于 L，令 $a\gets a[1,x]$，否则令 $a\gets a[x+1,m]$。

求执行 $k$ 次操作后 $a$ 数组的期望元素和。答案对 $10^9+7$ 取模。

其中 $a[l,r]$ 表示子数组 $[a_l,a_{l+1},\dots,a_r]$，数组下标从 $1$ 开始编号。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_{1\sim n}$。

第三行一个长度为 $k$ 的字符串 $S$。

输出格式

对于每组数据，输出一行一个整数表示答案。

2
5 1
1 2 3 4 5
L
5 2
1 2 3 4 5
LR

5
416666673

数据范围

对于 $30\%$ 的数据，$\sum n,\sum k\leq 10$。

对于 $60\%$ 的数据，$\sum n,\sum k\leq 100$。

对于 $100\%$ 的数据，$1\leq T\leq 500$，$1\leq n,k,\sum n,\sum k\leq 500$，$1\leq a_i\leq 10^9$，$S$ 中仅包含 LR 两种字符。