题目描述

给定 $k$ 以及系数序列 $w_0 \sim w_{2^{k-1}-1}$。定义一个 $n \ge k$ 阶排列 $p$ 的权值 $$\text{val}(p) = \prod_{i=1}^{n-k+1} w_{f(p_i, p_{i+1}, \dots, p_{i+k-1})}$$ 其中 $$f(a_1, a_2, \dots, a_k) = \sum_{i=1}^{k-1} 2^{i-1} [a_i < a_{i+1}]$$ 给定 $n$，计算所有 $n$ 阶排列的权值和 $\bmod \, 998244353$。

输入格式

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

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

输出格式

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

样例

样例 #1

样例输入 #1

3 2
1 2

样例输出 #1

13

样例 #2

样例输入 #2

5 3
1 2 3 4

样例输出 #2

1875

样例 #3

样例输入 #3

6 4
1 2 3 4 5 6 7 8

样例输出 #3

68850

数据范围

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

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