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$$$.

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$$$).

Output

Output a single integer, denoting the computed result modulo $$$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$$$.