無向単純グラフ $G$ が与えられます。このグラフの辺集合のサブセットのうち、そのサブセットを残したときに各頂点の次数が $2$ 以上となるようなものの個数を求めてください。

$G$ のいくつかの誘導部分グラフについてこの問いに答える必要があります。答えは $998244353$ で割った余りを出力してください。

入力

1行目に2つの正整数 $n, m$ が与えられます。これらはグラフの頂点数と辺数を表します。

続く $m$ 行には、各辺を表す2つの正整数 $u, v$ が与えられます。

続く1行に、クエリ数 $q$ が与えられます。

続く $q$ 行には、長さ $n$ の 01 文字列が与えられます。$i$ 番目の文字が $1$ ならば $i \in S$、そうでなければ $i \notin S$ であることを表し、集合 $S$ による誘導部分グラフに対するクエリとなります。$S$ は空ではないことが保証されます。

出力

$q$ 行にわたって、各クエリに対する答えを出力してください。

入出力例

入力 1

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

出力 1

29
2
1

子タスク

すべてのデータにおいて、$1 \leq n \leq 19$、$1 \leq m \leq \frac{n(n-1)}{2}$、$1 \leq q \leq 10^5$ を満たします。