Problem Statement

A house is going to hold a party lasting $K$ days, and $N$ people have been invited. Initially, the $N$ people stand in a horizontal row inside the house, and the $i$-th person from the left $(1\le i\le N)$ is called person $i$.

Over the $K$ days of parties, the party on day $d$ $(1\le d\le K)$ is going to proceed as follows.

• Each person remaining in the house as of day $d$ independently chooses either "leave" or "not leave".
• Among the people who chose "leave", those who satisfy at least one of the following conditions exit the house. All the others stay in the house.
  • There is no person to their right who chose "not leave".
  • There is no person to their left who chose "not leave".
• At this point, all the people remaining in the house hold the party of day $d$.

Note that at no point during the parties does the relative order of the people in the house change.

Now, it would be very sad if a participant were left all alone partway through, or if everyone went home partway through despite preparations having been made for $K$ days. Therefore, the success level of the whole series of parties over the $K$ days is defined as follows.

• If the parties on all $K$ days were held with two or more people
  • Let $D_i$ be the number of days out of the $K$ days on which person $i$ participated in the party. The success level is $\displaystyle\sum_{i=1}^{N}A_i^{D_i}$.
• If on one or more of the $K$ days the number of participants in the party became one or fewer
  • The success level is $0$.

The way the parties over the $K$ days are held is determined by how the people choose "leave" or "not leave" on each day. For all possible ways of choosing, compute the success level of the resulting $K$ days of parties, and find the sum of these values modulo $998244353$.

Two ways of choosing are considered different if there exist integers $i$ and $d$ such that the choice made by person $i$ on day $d$ differs.

Note here that a person who has exited the house makes no further choices.

Input

$N\ \ K$
$A_1\ \ A_2\ \cdots \ A_N$

• $2\le N\le 10^5$
• $1\le K\le 14$
• $1\le A_i\lt 998244353$
• All inputs are integers.

Output

Output the answer modulo $\bmod{998244353}$.

Sample

3 1
1 2 4

25

2 14
2997 92458

660248434

5 7
662 60 70 15 1034

156455438