Problem Description

Let $\text{cyc}_\pi$ be the number of cycles when treating a permutation $\pi$ of length $n$ as a permutation mapping. Given two integers $n, k$ and a degree-$(k-1)$ polynomial, compute:

where $\pi$ ranges over all permutations of length $n$ such that there is no position $i$ with $\pi_i = i$.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $k$ integers, giving the coefficients of the polynomial from low degree to high degree.

Output Format

Output one integer, the answer modulo $998244353$.

3 2
0 1

2

6 4
11 43 27 7

53070

6 4
9 72 22 7

60990

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, k \le 10^5$.

Translated by ChatGPT 5