C. SSPPSPSP
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little Wavelet v.s. Legacy of Lunatic Kingdom

$$$\Sigma\Sigma\Pi\Pi\Sigma\Pi\Sigma\Pi\dots$$$

In the backyard of the Hakurei Shrine, Reimu discovered an ancient stone tablet covered in strange symbols. Even Hieda no Akyuu, who knows all of Gensokyo's history by heart, was puzzled by these mysterious inscriptions.

After careful examination, Ran Yakumo of the Yakumo family determined that this might be a relic from the ancient Lunar civilization, containing the formula for some powerful spell energy.

The symbols on the tablet consist primarily of two operations:

  • $$$\Sigma$$$ (Summation symbol): Represents the sum of a series of values. For example: $$$$$$\sum_{x=0}^{n-1} f(x) = f(0) + f(1) + \cdots + f(n-1)$$$$$$
  • $$$\Pi$$$ (Product symbol): Represents the product of a series of values. For example: $$$$$$\prod_{x=0}^{n-1} f(x) = f(0) \times f(1) \times \cdots \times f(n-1)$$$$$$

After analysis, the spell formula on the tablet can be expressed as:

$$$$$$ \def\op{\mathrm{op}} \mathrm{power} = [\op_1]_{x_1=0}^{n-1} [\op_2]_{x_2=0}^{n-1} \cdots [\op_k]_{x_k=0}^{n-1} \ a_{(x_1 + x_2 + \cdots + x_k) \bmod n} $$$$$$

Where $$$\mathrm{op}_i \in \{ \Sigma , \Pi \}$$$, and $$$a$$$ is an energy coefficient array of length $$$n$$$.

Ran Yakumo is interested in the final energy value of this spell, but even with her exceptional calculation abilities, the computation is too massive to complete in a reasonable time. Therefore, she seeks help from you who possess 21st century mechanical shikigami (computers).

Since the result might be too large to write down in all of Gensokyo, she only needs you to provide the result modulo $$$998\,244\,353$$$.

小 Wavelet 大战赶猪转

$$$\Sigma\Sigma\Pi\Pi\Sigma\Pi\Sigma\Pi\dots$$$

在博丽神社的后山，灵梦发现了一块刻满奇怪符号的古老石板。即使是熟记幻想乡历史的稗田阿求，面对这些神秘的碑文也一筹莫展。

八云家的式神八云蓝仔细观察后认为，这可能是上古月球文明遗留的碑石，上面记载着某种强大的术式能量公式。

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

  • $$$\Sigma$$$（求和符号）：表示对一系列数值进行相加。例如： $$$$$$\sum_{x=0}^{n-1} f(x) = f(0) + f(1) + \cdots + f(n-1)$$$$$$
  • $$$\Pi$$$（求积符号）：表示对一系列数值进行相乘。例如： $$$$$$\prod_{x=0}^{n-1} f(x) = f(0) \times f(1) \times \cdots \times f(n-1)$$$$$$

经过解析，石板上的术式可以表示为：

$$$$$$ \def\op{\mathrm{op}} \mathrm{power} = [\op_1]_{x_1=0}^{n-1} [\op_2]_{x_2=0}^{n-1} \cdots [\op_k]_{x_k=0}^{n-1} \ a_{(x_1 + x_2 + \cdots + x_k) \bmod n} $$$$$$

其中，$$$\mathrm{op}_i \in \{\Sigma, \Pi\}$$$，而 $$$a$$$ 是一个给定的长度为 $$$n$$$ 的能量系数数组。

八云蓝对这个术式的最终能量值感兴趣，但由于计算量过于庞大，即使是擅长计算的她也无法在合理时间内完成。因此她求助于拥有二十一世纪机械式神（计算机）的你。

由于结果可能非常大以至于整个幻想乡都写不下，因此她只需要你给出结果对 $$$998\,244\,353$$$ 取模的值。

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n, k \leq 10)$$$.

The second line contains $$$n$$$ integers $$$a_0, a_1, \ldots, a_{n-1}$$$ $$$(0 \leq a_i \lt 998\,244\,353)$$$.

The third line contains a string $$$op$$$ of length $$$k$$$, where each character is either 's' (sum, representing $$$\Sigma$$$) or 'p' (product, representing $$$\Pi$$$).

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

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

第三行包含一个长度为 $$$k$$$ 的字符串 $$$op$$$，每个字符为 's'（sum，代表 $$$\Sigma$$$）或 'p'（product，代表 $$$\Pi$$$）。

Output

Output a single integer, denoting the computed result modulo $$$998\,244\,353$$$.

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

Example
Input
2 3
1 2
sps
Output
18
Note

Consider the following mathematical expression:

$$$$$$ \mathrm{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} $$$$$$

The computation process unfolds as:

  1. When $$$x_1 = 0$$$:
    1. When $$$x_2 = 0$$$:
      1. When $$$x_3 = 0$$$, the result is $$$a_{(0+0+0)\bmod 2} = a_{0} = 1$$$;
      2. When $$$x_3 = 1$$$, the result is $$$a_{(0+0+1)\bmod 2} = a_{1} = 2$$$;
      3. Thus the inner sum is $$$1 + 2 = 3$$$.
    2. When $$$x_2 = 1$$$:
      1. When $$$x_3 = 0$$$, the result is $$$a_{(0+1+0)\bmod 2} = a_{1} = 2$$$;
      2. When $$$x_3 = 1$$$, the result is $$$a_{(0+1+1)\bmod 2} = a_{0} = 1$$$;
      3. Thus the inner sum is $$$1 + 2 = 3$$$.
    3. Therefore the middle product is $$$3\times 3 = 9$$$.
  2. When $$$x_1 = 1$$$:
    1. When $$$x_2 = 0$$$:
      1. When $$$x_3 = 0$$$, the result is $$$a_{(1+0+0)\bmod 2} = a_{1} = 2$$$;
      2. When $$$x_3 = 1$$$, the result is $$$a_{(1+0+1)\bmod 2} = a_{0} = 1$$$;
      3. Thus the inner sum is $$$1 + 2 = 3$$$.
    2. When $$$x_2 = 1$$$:
      1. When $$$x_3 = 0$$$, the result is $$$a_{(1+1+0)\bmod 2} = a_{0} = 1$$$;
      2. When $$$x_3 = 1$$$, the result is $$$a_{(1+1+1)\bmod 2} = a_{1} = 2$$$;
      3. Thus the inner sum is $$$1 + 2 = 3$$$.
    3. Therefore the middle product is $$$3\times 3 = 9$$$.
  3. Therefore the outer sum is $$$9 + 9 = 18$$$.

对应的数学表达式：

$$$$$$ \mathrm{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$$$ 时，
    1. 当 $$$x_2 = 0$$$ 时，
      1. 当 $$$x_3 = 0$$$ 时，结果为 $$$a_{(0+0+0)\bmod 2} = a_{0} = 1$$$；
      2. 当 $$$x_3 = 1$$$ 时，结果为 $$$a_{(0+0+1)\bmod 2} = a_{1} = 2$$$；
      3. 从而内层求和结果为 $$$1 + 2 = 3$$$。
    2. 当 $$$x_2 = 1$$$ 时，
      1. 当 $$$x_3 = 0$$$ 时，结果为 $$$a_{(0+1+0)\bmod 2} = a_{1} = 2$$$；
      2. 当 $$$x_3 = 1$$$ 时，结果为 $$$a_{(0+1+1)\bmod 2} = a_{0} = 1$$$；
      3. 从而内层求和结果为 $$$1 + 2 = 3$$$。
    3. 于是得到中层求积结果为 $$$3\times 3 = 9$$$。
  2. 当 $$$x_1 = 1$$$ 时，
    1. 当 $$$x_2 = 0$$$ 时，
      1. 当 $$$x_3 = 0$$$ 时，结果为 $$$a_{(1+0+0)\bmod 2} = a_{1} = 2$$$；
      2. 当 $$$x_3 = 1$$$ 时，结果为 $$$a_{(1+0+1)\bmod 2} = a_{0} = 1$$$；
      3. 从而内层求和结果为 $$$1 + 2 = 3$$$。
    2. 当 $$$x_2 = 1$$$ 时，
      1. 当 $$$x_3 = 0$$$ 时，结果为 $$$a_{(1+1+0)\bmod 2} = a_{0} = 1$$$；
      2. 当 $$$x_3 = 1$$$ 时，结果为 $$$a_{(1+1+1)\bmod 2} = a_{1} = 2$$$；
      3. 从而内层求和结果为 $$$1 + 2 = 3$$$。
    3. 于是得到中层求积结果为 $$$3\times 3 = 9$$$。
  3. 于是得到外层求和结果为 $$$9 + 9 = 18$$$。