题目内容

园艺师计划在一个矩形花坛中种植一批不同品种的花卉。花坛被划分为 $n$ 行 $m$ 列的方格，每个方格要么是空地（用 0 表示），要么已经摆放了石块（用 1 表示）。现在需要为同一品种的花卉选择种植位置，但由于它们需要相同的养护条件，因此必须满足：

• 所有花卉必须种植在空地上；
• 全部 $k$ 株花卉必须位于同一行，并且占据连续的 $k$ 个方格；
• 对于每一株花卉所在的方格，其上下左右四个相邻方格（如果存在的话）都不能是石块。换句话说，相邻方格只能是边界外、空地或者同样种有花卉的方格。

由于不同花卉品种彼此不同，即使选择的种植方格集合相同，但花卉的具体排列顺序不同也会被视为不同的种植方案。现在给出花坛的现状以及多次询问，每次询问给定一个整数 $k$，表示需要种植的花卉株数。请你计算每次询问对应的合法种植方案总数。如果没有任何可行方案，则答案为 0。由于答案可能很大，请将结果对 $998244353$ 取模后输出。

约束条件：行数 $n$、列数 $m$ 和询问次数 $q$ 均不超过 $100$。方格中的数字仅为 0 或 1。每次询问的 $k$ 满足 $1 \le k \le n \times m$。