問題文

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

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

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

誰も怒らないようなボールの配り方を $\boldsymbol{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$

入力

$N\ M$
$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}$
$\vdots$
$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