ΣΣΠΠΣΠΣΠ . . .

在博丽神社的后院，灵梦发现了一块刻满奇怪符号的古老石板。即使是熟知幻想乡历史的稗田阿求，也被这些神秘的铭文难住了。

经过仔细检查，八云紫断定这可能是来自古代月之文明的遗物，其中包含了某种强大咒术能量的公式。

石板上的符号主要由两种运算组成：

• $\Sigma$（求和符号）：表示一系列数值的和。例如： $$\sum_{x=0}^{n-1} f(x) = f(0) + f(1) + \dots + f(n - 1)$$

• $\Pi$（求积符号）：表示一系列数值的积。例如： $$\prod_{x=0}^{n-1} f(x) = f(0) \times f(1) \times \dots \times f(n - 1)$$

经过分析，石板上的咒术公式可以表示为： $$\text{power} = [\text{op}_1]_{x_1=0}^{n-1} [\text{op}_2]_{x_2=0}^{n-1} \dots [\text{op}_k]_{x_k=0}^{n-1} a_{(x_1+x_2+\dots+x_k) \bmod n}$$ 其中 $\text{op}_i \in {\Sigma, \Pi}$，$a$ 是一个长度为 $n$ 的能量系数数组。

八云紫对这个咒术的最终能量值很感兴趣，但即使以她非凡的计算能力，要在合理的时间内完成计算也过于庞大。因此，她向拥有 21 世纪机械式神（计算机）的你寻求帮助。

由于结果可能大到无法在整个幻想乡写下，她只需要你提供结果对 $998\,244\,353$ 取模后的值。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n, k \le 10$)。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < 998\,244\,353$)。

第三行包含一个长度为 $k$ 的字符串 $op$，其中每个字符要么是 's'（求和，代表 $\Sigma$），要么是 'p'（求积，代表 $\Pi$）。

输出格式

输出一个整数，表示计算结果对 $998\,244\,353$ 取模后的值。

样例

样例输入 1

2 3
1 2
sps

样例输出 1

18

说明

考虑以下数学表达式： $$\text{power} = \sum_{x_1=0}^{1} \prod_{x_2=0}^{1} \sum_{x_3=0}^{1} a_{(x_1+x_2+x_3) \bmod 2}$$

计算过程如下：

1. 当 $x_1 = 0$ 时： (a) 当 $x_2 = 0$ 时：

    i. 当 $x_3 = 0$ 时，结果为 $a_{(0+0+0) \bmod 2} = a_0 = 1$；
    ii. 当 $x_3 = 1$ 时，结果为 $a_{(0+0+1) \bmod 2} = a_1 = 2$；
    iii. 因此内层求和为 $1 + 2 = 3$。

   (b) 当 $x_2 = 1$ 时：

    i. 当 $x_3 = 0$ 时，结果为 $a_{(0+1+0) \bmod 2} = a_1 = 2$；
    ii. 当 $x_3 = 1$ 时，结果为 $a_{(0+1+1) \bmod 2} = a_0 = 1$；
    iii. 因此内层求和为 $1 + 2 = 3$。

   (c) 因此中间的求积为 $3 \times 3 = 9$。

2. 当 $x_1 = 1$ 时： (a) 当 $x_2 = 0$ 时：

    i. 当 $x_3 = 0$ 时，结果为 $a_{(1+0+0) \bmod 2} = a_1 = 2$；
    ii. 当 $x_3 = 1$ 时，结果为 $a_{(1+0+1) \bmod 2} = a_0 = 1$；
    iii. 因此内层求和为 $1 + 2 = 3$。

   (b) 当 $x_2 = 1$ 时：

    i. 当 $x_3 = 0$ 时，结果为 $a_{(1+1+0) \bmod 2} = a_0 = 1$；
    ii. 当 $x_3 = 1$ 时，结果为 $a_{(1+1+1) \bmod 2} = a_1 = 2$；
    iii. 因此内层求和为 $1 + 2 = 3$。

   (c) 因此中间的求积为 $3 \times 3 = 9$。

3. 因此外层求和为 $9 + 9 = 18$。