近日，ObenAI 高调宣布其最新模型 GBT-5.2 Bro 已彻底解决最大独立集问题，提出了可处理规模高达 $10^6$ 的数据范围的高效算法。

此言一出，媒体争相报道相关内容。然而经你仔细调研，GBT-5.2 Bro 生成的代码只对存在大小至少为 $n-20$ 的独立集的图才能快速计算出结果。

你觉得在这种图上运行一个经典的贪心算法大概率就能找出最大独立集，为了准确算出概率，需要解决以下问题：

给定一张 $n$ 个点的无向图 $G$，保证 $\{m+1,m+2,\cdots,n-1,n\}$ 是 $G$ 的一个独立集$^\dagger$。

均匀随机选取一个 $1\sim n$ 的排列作为 $p$，并按照如下方式生成一个独立集 $T$：

• $T$ 初始为空集。
• 对 $i = 1 \sim n$，若 $T \cup \{p_i\}$ 仍然是 $G$ 中的独立集，则将 $p_i$ 加入 $T$；否则什么都不做。

给定一个长为 $n$ 的 01 串 $s$，定义 $S$ 集合为 $\{1,2,\cdots,n\}$ 的一个子集，其中 $i\in S$ 当且仅当 $s_i=1$。

求生成的集合恰好为 $S$ 的概率，答案对 $998244353$ 取模$^\ddagger$。

---

$^\dagger$：嗯，用户现在问的是算法竞赛中“独立集”的定义，我需要给出一个既准确又通俗易懂的解释：在图 $G$ 中，若顶点集的一个子集 $S$ 满足其中任意两个顶点在原图中均没有边直接相连，则称 $S$ 为图 $G$ 的一个独立集。

$^\ddagger$：好的，用户现在问的是关于概率对 $998244353$ 取模的定义，这次也需要简洁的版本：可以证明答案 $P$ 可以以有理数 $\frac{x}{y}$（$x, y$ 均为整数，且 $y \not\equiv 0 \pmod{998244353}$）的形式表示，请输出唯一满足 $0\le z<998244353$ 的整数 $z$ 使得 $yz\equiv x\pmod{998244353}$。

输入格式

第一行两个正整数 $n,m$，含义如题目所述。

接下来一行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，描述图 $G$。

图的压缩方式如下：对于 $1\le i\le n,1\le j\le m$，设 $A_{i,j}$ 表示 $i$ 和 $j$ 之间是否有边，那么 $a_i=\sum_{j=1}^m2^{j-1}\cdot A_{i,j}$。

接下来一行一个长为 $n$ 的 01 串 $s$，表示题面中的 $S$ 集合。

输出格式

一行一个整数，表示上述算法生成的集合恰好为 $S$ 的概率，答案对 $998244353$ 取模。

5 2
0 0 1 3 2
10001

166374059

样例二 $\sim$ 八

见“附件下载”。

数据范围

对于所有数据，保证 $1\le n\le10^6,1\le m\le\min(n,20)$。保证输入解码后对于 $1\le i,j\le m$，有 $A_{i,j}=A_{j,i}$，且 $A_{i,i}=0$。不保证 $S$ 为独立集。

时间限制：$3\texttt{s}$

空间限制：$1\texttt{GB}$