给一个无向简单图 $G$，请问有多少边集的子集，使得保留这一子集后，每个点的度数 $\geq 2$？

你需要对 $G$ 的若干个导出子图都回答这一问题，答案对 $998244353$ 取模。

输入格式

第一行输入两个正整数 $n,m$。表示图的点数和边数。

接下来 $m$ 行每行输入两个正整数 $u,v$ 表示一条边。

接下来一行输入一个正整数 $q$，表示询问数。

接下来 $q$ 行每行输入一个长为 $n$ 的 01 串，其中第 $i$ 个数为 $1$ 表示 $i\in S$，否则 $i\notin S$，询问 $S$ 这个集合的导出子图。保证 $S$ 非空。

输出格式

输出 $q$ 行每行一个数，表示答案。

样例数据

样例输入

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5
3
11111
01111
11110

样例输出

29
2
1

子任务

对于 $100\%$ 的数据，保证 $1\leq n\leq 19$，$1\leq m\leq \frac{n(n-1)}{2}$，$1\leq q\leq 10^5$。