题意

给定一个 $n$ 行 $m$ 列的影院座位布局，其中 0 表示空座，1 表示已被订出。你和朋友想一起观影，且组内人员可区分。每次希望选定连续的 $k$ 个空座，中间不允许被占，且在垂直方向（上下）和水平方向（左右）相邻的位置都不能有已订座位，满足条件的方案数乘以 $k!$ 即为答案，对 $998244353$ 取模。

输入包括多次询问，每次给出一个 $k$，需要输出对应的方案数。

题解思路

枚举每行安全区间

1. 定义 safe[i][j]：仅当座位 $(i,j)$ 为空且其上下位置要么越界要么也是空时，safe[i][j]=1，否则为0。
2. 对于每一行，用前缀和 pref[j] 快速判断任意区间内是否全是 safe=1。

题目内容

电影院共有 $n$ 行、$m$ 列座位。部分座位已被陌生人的购买，剩余座位为空闲。你和你的 $k$ 位朋友希望一起观影，选座时有以下要求：

只能选择空闲座位；

全部 $k$ 个人的选座需要位于同一行，且保持连续；

对于选中的每一个位置，其上下左右相邻的位置要么不存在，要么为空闲，要么同样为被你们选中的位置。

现在，给出电影院的座位示意图，以及多次询问，每次询问给出 $k$ 个整教，表示你们希望一起观影的人数，请计算对于每次询问，有多少种不同的选座方案满足上述要求。两个方案不同当且仅当至少有一个人与之前的位置不同。若不存在任何合法方案，输出 $0$ 。由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

输入描述

第一行输入三个整数 $n,m,q(1≦n,m,q≦ 100)$ ，表示电影院座位的行数、列数、询问次数。

此后 $n$ 行，第 $i$ 行输入 $m$ 个整数 $a_{i,1},a_{i,2},...,a_{i,m}(0≦a_{i,j}≦1)$，其中 $a_{i,j}$ ，表示电影院第 $i$ 行第 $j$ 列的座位状态。$a_{i,j}=0$ 表示空用，$a_{i,j}=1$ 表示已被购买。

第 $n+2$ 行输入 $q$ 个整数 $k_1,k_2,...,k_q(1≦k_i≦n×m)$，表示每次询问中，你们希望一起观影的人数。

输出描述

对于每次询问，在一行上连续的输出一个整数，表示不同的选座方案数，由于答案可能很大，请将答案对 $998$ $244$ $353$ 取模后输出。

样例1

输入

1 3 4
0 0 0
0 1 2 3

输出

0 3 4 6

说明

对于第三次询问，有以下几种选座方案：

选择第 $1$ 行，第一个朋友坐第 $1$ 列，第二个朋友坐第 $2$ 列；

选择第 $1$ 行，第一个朋友坐第 $2$ 列，第二个朋友坐第 $1$ 列；

选择第 $1$ 行，第一个朋友坐第 $2$ 列，第二个朋友坐第 $3$ 列；

选择第 $1$ 行，第一个朋友坐第 $3$ 列，第二个朋友坐第 $2$ 列。

样例2

输入

2 4 3
1 1 0 1
0 0 0 0
1 3 8

输出

1 0 0

样例3

输入

4 4 2
1 0 0 0
0 0 0 0
0 0 0 1
1 1 0 1
1 2

输出

4 4