問題文

$N$ 個の区別可能なボールを $M$ 人の人に配ります。ただし、誰にも配られないボールがあってもいいです。

ここで、条件 $X_i$ を「配られたボールの個数が $i$ の倍数であること」と定義します。

$M$ 人の人はわがままなので、$i$ 番目の人は $X_{A_{i,1}},X_{A_{i,2}},...,X_{A_{i,k_i}}$ の条件の内少なくとも $1$ 個を満たさないと怒ってしまいます。また、条件を $1$ 個以上満たせば怒ることはありません。

誰も怒らないようなボールの配り方を $\mathbf{90001}($素数$)$ で割ったあまりを求めてください。

制約

• 入力は全て整数である。
• $1\le N\le {10}^{200000}$
• $1\le M\le 10$
• $1\le k_i\le 6$
• $1\le A_{i,j}\le 6$

入力

$NM$
$k_1{A}_{1,1}{A}_{1,2}\dots A_{1,k_1}$
$k_2{A}_{2,1}{A}_{2,2}\dots A_{2,k_2}$
$⋮$
$k_M{A}_{M,1}{A}_{M,2}\dots A_{M,k_M}$

出力

答えを $1$ 行に出力してください。

サンプル

4 2
1 2
1 1

41

10 3
1 2
1 3
2 2 3

36952

2021 6
1 1
2 2 3
3 4 5 6
1 6
2 4 5
3 1 2 3

83960