Problem Description

Let $\text{cyc}_\pi$ denote the number of cycles into which the permutation $\pi$ of length $n$ can be decomposed when treated as a permutation. Given two integers $n$ and $k$, and a polynomial of degree $k-1$, compute:

$$ \sum\limits_{\pi}F(\text{cyc}_{\pi}) $$

where $\pi$ is a permutation of length $n$ such that there is no position $i$ where $\pi_i = i$.

Input Format

The first line contains two integers, representing $n$ and $k$ respectively.

The second line contains $k$ integers, listing the coefficients of the polynomial from lowest to highest degree.

Output Format

A single integer on one line, representing the answer modulo $998244353$.

Sample Input and Output

Sample Input #1

3 2
0 1

Sample Output #1

2

Sample Input #2

6 4
11 43 27 7

Sample Output #2

53070

Sample Input #3

6 4
9 72 22 7

Sample Output #3

60990

Notes

Data Range

For $100\%$ of the data, $1 \leq n, k \leq 10^5$.

见题面 Input 部分

见题面 Output 部分