Problem Statement

You distribute $N$ distinguishable balls to $M$ people. Some balls may be given to no one.

Here, define condition $X_i$ as "the number of balls given is a multiple of $i$".

The $M$ people are selfish: person $i$ gets angry unless at least $1$ of the conditions $X_{A_{i,1}},X_{A_{i,2}},...,X_{A_{i,k_i}}$ is satisfied. Also, they do not get angry if $1$ or more of the conditions are satisfied.

Find the number of ways to distribute the balls so that no one gets angry, modulo $\boldsymbol{90001}($prime$)$.

Constraints

• All inputs are integers.
• $1 \le N \le 10^{200000}$
• $1 \le M \le 10$
• $1 \le k_i \le 6$
• $1 \le A_{i,j} \le 6$

Input

$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}$

Output

Output the answer on $1$ line.

Sample

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