### 问题描述 某高校准备绘制一条长度为 $L$ 的长廊（可以视为 $x$ 坐标轴，其中坐标区间为 $[0,L]$）。目前已经制作了 $N$ 张不同的海报（编号为 $1,2,...,N$），每张海报的长度为 $l_i$。现在请你来帮忙张贴海报。规则如下： 规则一：海报必须根据编号从小到大，从左到右依次将 $N$ 张海报全部贴到长廊上。 规则二：张贴海报必须从整数坐标开始，例如，一张长度为 $2$ 的海报可以从 $x=0$、 $x = L-2$ 处开始张贴（贴完后分别覆盖区间 $[0,2)$ 和 $[L-2,L)$），但不能从长度 $x = 0.5$ 处开始张贴。 规则三：两张海报禁止出现重叠、覆盖或越界（即海报结束位置超出长度 $L$ ）。 为了纪念前辈们的丰功伟绩，在某些海报之间需要预留至少长度为 $1$ 的空间给他们。为了简化问题，我们用一个只包含 $0$ 和 $1$ 的数字串来表示：若第 $i$ 个数字为 $1$，则第 $i$ 张海报和第 $i+1$ 张海报之间需要预留至少长度为 $1$ 的空间；若为 $0$ 则表示不需要预留空间。 问题来了，有多少种不同的合法的张贴方案数？由于答案可能过大，你只需要输出答案对 $998244353$ 取模后的值。 ### 输入格式 第一行两个以空格隔开的正整数 $L$，$N$。 第二行一个长度为 $N-1$ 的只包含数字 $0$ 和 $1$ 的数字串（不包含空格），含义如上所述。 第三行 $N$ 个以空格隔开的正整数 $l_i$，表示编号为 $i$ 的海报的长度。 ### 输出格式 输出仅一行，包含一个整数，表示答案对 $998244353$ 取模后的值。 ### 样例输入 ```text 5 2 1 1 2 ``` ### 样例输出 ```text 3 ``` ### 说明 在样例中，共有如下 $3$ 种合法张贴方案： `(1,0,2,2,0)`, `(1,0,0,2,2)`, `(0,1,0,2,2)` 其中 $0$ 表示预留的空间，$1$ 表示该位置张贴第一张海报，$2$ 表示该位置张贴第 $2$ 张海报。因此，第一种方案表示 $1$ 号海报贴在了区间 $[0,1)$，$2$ 号海报贴在了区间 $[2,4)$，剩下的都是预留空间。 ### 评测数据规模 对于 $50$% 的评测数据，$1 \leq L \leq 10^{3}$，$2 \leq N \leq 10^{3}$。 对于 $100$% 的评测数据，$1 \leq L \leq 10^{6}$，$2 \leq N \leq 10^{5}$，$1 \leq l_i \leq L$。