题目描述

给定 $k$ 以及系数序列 $w_0 \sim w_{2^{k-1}-1}$。

定义一个 $n \ge k$ 阶排列 $p$ 的权值 $val(p)=\prod\limits_{i=1}^{n-k+1} w_{f(p_i,p_{i+1}...p_{i+k-1})}$，其中 $f(a_1,a_2...a_k)=\sum\limits_{i=1}^{k-1}2^{i-1}[a_i<a_{i+1}]$。

给定 $n$，计算所有 $n$ 阶排列的权值和，答案对 $998244353$ 取模。

输入格式

第一行两个整数 $n,k$。

第二行 $2^{k-1}$ 个整数，第 $i$ 个整数表示 $w_{i-1}$。

输出格式

一行一个整数，表示答案 $\bmod\ 998244353$。

3 2
1 2

13

5 3
1 2 3 4

1875

6 4
1 2 3 4 5 6 7 8

68850

提示

本题使用捆绑测试，你只有通过一个子任务的所有测试点，才能获得这个子任务的分数。

对于所有数据：$2 \le k \le 4$，$k \le n \le 10^5$，$0 \le w_i < 998244353$。