配点 : $600$ 点

問題文

キャベツ農家の高橋君は、品種 $1$ から品種 $N$ までの $N$ 種類のキャベツを育てました。高橋君は品種 $i$ $(1 \leq i \leq N)$ のキャベツを $A_i$ 個持っています。ここで、 すべてのキャベツは区別できます。 キャベツの卸先として会社 $1$ から会社 $M$ までの $M$ 個の会社があり、会社 $j$ $(1 \leq j \leq M)$ からは $B_j$ 個のキャベツの注文を受けています。 出荷できるキャベツの品種は会社ごとに異なっており、すべての $i, j$ の組 $(1 \leq i \leq N, 1 \leq j \leq M)$ について

• $c_{i, j} = 1$ のとき、品種 $i$ のキャベツを会社 $j$ に出荷できます。
• $c_{i, j} = 0$ のとき、品種 $i$ のキャベツを会社 $j$ に出荷できません。

高橋君は、すべてのキャベツの出荷先を適切に決めることで、すべての会社 $j$ $(1 \leq j \leq M)$ にキャベツを $B_j$ 個以上出荷することができれば「キャベツ名人」の称号を得ることができます。

すぬけ君は、高橋君がどのようにキャベツの出荷先を決めても「キャベツ名人」の称号を得られないように $0$ 個以上のキャベツを選んで食べることにしました。キャベツが苦手なすぬけ君は、前述の条件のもとで食べるキャベツの個数が 最少 となるように食べるキャベツの組み合わせを選択します。

すぬけ君が食べるキャベツの個数、およびすぬけ君が食べるキャベツの選び方が何通りあるかを $998244353$ で割ったあまりの $2$ つを出力してください。 ただし、 キャベツの選び方が異なるとは、一方の選び方で食べられたがもう一方の選び方で食べられていないようなキャベツが存在することをいいます。ここで、異なる $2$ つのキャベツは 品種が同じでも区別される ことに注意してください。

制約

• $1 \leq N \leq 20$
• $1 \leq M \leq 10^4$
• $1 \leq A_i \leq 10^5$
• $1 \leq B_j \leq 10^5$
• $c_{i, j} \in \lbrace 0, 1 \rbrace$
• 任意の $1 \leq j \leq M$ に対して、ある $1 \leq i \leq N$ が存在して $c_{i, j} = 1$ が成り立つ
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_1$ $A_2$ $\ldots$ $A_N$

$B_1$ $B_2$ $\ldots$ $B_M$

$c_{1, 1}$ $c_{1, 2}$ $\ldots$ $c_{1, M}$

$c_{2, 1}$ $c_{2, 2}$ $\ldots$ $c_{2, M}$

$\vdots$

$c_{N, 1}$ $c_{N, 2}$ $\ldots$ $c_{N, M}$

出力

すぬけ君が食べるキャベツの個数 $X$ と、すぬけ君が食べるキャベツの選び方が何通りあるかを $998244353$ で割ったあまり $Y$ を、この順番に空白区切りで出力せよ。

$X$ $Y$

3 2
2 2 5
3 4
1 0
1 1
0 1

2 6

高橋君がキャベツ名人になれないようにするために、すぬけ君が食べるキャベツの個数は $2$ 個です。 また、便宜上 「品種 $i$ の $j$ 番目のキャベツ」を $(i,j)$ のように表したとき、すぬけ君が食べるキャベツの組み合わせとして考えられるものは以下の $6$ 通りです。

• $(1, 1), (1, 2)$
• $(1, 1), (2, 1)$
• $(1, 1), (2, 2)$
• $(1, 2), (2, 1)$
• $(1, 2), (2, 2)$
• $(2, 1), (2, 2)$

1 1
3
4
1

0 1

すぬけ君がキャベツを $1$ 個も食べなくても、高橋君がキャベツ名人になることができない場合もあります。 このとき、すぬけ君が食べるキャベツの個数は $0$ 個であり、すぬけ君が食べるキャベツの組み合わせとして考えられるのは、「どのキャベツも食べない」という $1$ 通りのみです。

1 3
100
30 30 30
1 1 1

11 892328666

すぬけ君が食べるキャベツの選び方が何通りあるかについては、 $998244353$ で割ったあまりを出力することに注意してください。