题目背景

夜空に咲く花を摘んで 摘下夜空中盛放的花

瞬く星を束ねて / 君にあげる 将闪烁繁星合成一束 / 送给你

ねぇ / どうして君は泣いているの 呐 / 你为什么在哭呢

...

揺らめく明かりを見ていた / どれも綺麗だけど 摇曳闪烁的烟火光芒 / 纵然每一朵都美丽绝伦

君の涙は止められないなぁ 却依旧止不住你的眼泪

—— 霞む夏の灯 - 猫村いろは / *Luna

题目描述

夏天就要结束了。

烟火大会马上就要开始了，烟火大会的负责人小 L 采购了 $n$ 种烟花。现在有一个残缺的演出顺序表 $k_i$。如果 $k_i \ne -1$，则代表第 $i$ 场演出应该表演第 $k_i$ 种烟花。你可以任意排列剩下烟花的演出顺序，但是要求每种烟花都必须演出恰好一次。

定义第 $i$ 种烟花的精彩度为，如果其在第 $j$ 个演出，它的精彩度为 $c_{\min(|i-j|,m)}$。烟花大会的精彩度定义为所有烟花精彩度的乘积。小 L 希望知道，对于所有可能的烟花的排列顺序，烟火大会的精彩度之和。这里定义两个排列 $\pi_1$ 和 $\pi_2$ 不同当且仅当存在 $i$ 使得 $\pi_1(i)\ne \pi_2(i)$。由于这个数会很大，你只需要输出对 $998244353$ 取模的结果即可。

形式化题意：给定 $n,m$ 和长为 $m+1$ 的序列 $c_i$，以及长为 $n$ 的序列 $k_i$，你需要求出 $\displaystyle\sum_{\pi}\prod_{i=1}^n c_{\min(|i-\pi(i)|,m)}\times[k_i=-1 \vee k_i=\pi(i)]$ 对 $998244353$ 取模的值。

输入格式

第一行两个正整数 $n,m$。

第二行 $m+1$ 个正整数，代表 $c_i$。

第三行 $n$ 个正整数，代表 $k_i$。

输出格式

你只需要输出一个数，代表答案。

3 2
2 3 1
-1 -1 -1

64

9 4
11 45 14 1919 810
-1 -1 -1 -1 -1 -1 -1 -1 -1

452171515

10 1
3 5
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

244007436

10 1
3 5
2 -1 -1 5 -1 -1 -1 1 -1 -1

951753292

4 2
4 2 3
3 -1 -1 2

117

10 3
114 514 191 9810
9 -1 2 -1 -1 -1 6 -1 -1 5

544409251

提示

本题采用捆绑测试：

• Subtask 1（1 pts）：$1 \le n \le 10$。
• Subtask 2（2 pts）：$1 \le n \le 16$。
• Subtask 3（1 pts）：$k_i=-1,m=1,c_1=0$。
• Subtask 4（3 pts）：$k_i=-1,m=1,c_0=0$。
• Subtask 5（5 pts）：$k_i=-1,m=1$。
• Subtask 6（5 pts）：$m=1$。
• Subtask 7（13 pts）：$m=2$。
• Subtask 8（15 pts）：$k_i = -1, m \le 5$。
• Subtask 9（15 pts）：$k_i = -1$。
• Subtask 10（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 100, 1 \le m \le 6,-1 \le k_i \le n, k_i \ne 0,0 \le c_i < 998244353$。

题目保证对于任意一对 $(i,j)(i \ne j,k_i \ne -1, k_j \ne -1)$，都有 $k_i \ne k_j$。

---

待在她身旁，像这样闲聊些无聊的话题，甚至让我感到舒坦。所以我才会想继续和她在一起的。

「以前啊。我还曾想说要成为魔法使的呢。既可爱又帅气。嘛、知道了那是无法成为的后，就只能以自己的方式生活下去了」

悠然地走着时，烟火的光芒映入眼帘。差不多要进入高潮了，射向空中的烟火比刚才增加不少。

「如果是魔法使的话，是不是就能让所有人都展露笑容了呢」