求和

Problem Description

给定一个长度为 $k$ 的正整数序列 $a_1,a_2,\dots,a_k$ ，以及包含 $n$ 个正整数的多重集合 $S$（即可以包含重复元素的集合）; 另定义在整数上的函数 $f:$

$$f(n)= \left\{ \begin{aligned} &0,n\leq -1\\ &1,n=0\\ &\sum_{i=1}^k f(n-i)a_i,n\geq 1 \end{aligned} \right. $$

求 $\sum_{T\subseteq S}{f(\sum_{x\in T}x)}$ 对 $998244353$ 取模的结果。

Input

输入共 $3$ 行： 第 $1$ 行输入两个正整数 $n ~(1 \leq n \leq 10^5)$ 和 $k ~(1 \leq k \leq 50)$ ，分别表示集合大小和序列 $a$ 的长度。 第 $2$ 行包含 $k$ 个正整数，第 $i$ 个数代表 $a_i~(1 \leq a_i \leq 10^9)$ 。 第 $3$ 行包含 $n$ 个正整数，第 $i$ 个数 ($b_i$) 代表集合 $S$的第 $i$ 个元素 $~(1 \leq b_i \leq 10^9)$ 。

Output

输出共一行，含仅一个非负整数表示答案。

Sample Input

2 2
1 1
2 3

Sample Output

14

Hint

$S=\{2,3\}$ 的所有子集为：$\{\varnothing,\{2\},\{3\},\{2,3\}\}$ , $f(0)=1,f(2)=2,f(3)=3,f(5)=8$ ； $f(\sum_{x\in \varnothing} x)=f(0)=1$ , $f(\sum_{x\in\{2\}} x)=f(2)=2$，$f(\sum_{x\in\{3\}} x)=f(3)=3$，$f(\sum_{x\in\{2,3\}} x)=f(5)=8$ ，故所求的结果为 $1+2+3+8=14$ 。 注意：考虑多重集子集的时候，形式相同的子集可能需要被认为是不同的，例如统计 $S=\{1,1\}$ 的子集时，$\{1\}$ 需要计算 $2$ 次。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）