1303 - For Fun:: HUST Online Judge

1303 - For Fun

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 84

Solved: 41

Description

Gaewah, a friend with high niubility, is asking me to set some problems for the monthly contest hosted by him.
with my hardworking, all the N problems have finally come out. However, it confuses me while I am arranging the order of this N problems.
explicitly I take the order of the N problems as a permutation of numbers 0...n-1, and for some reasons, some particular orders is not allowed
to show up in the permutation. Now can you help me figure out how many permutations that satisfy the condition mentioned above?

here come an example for explanation:
supposed N is 3, and there are M illegal orders, (here M = 3) (1)0, 1, 2 (2)2, 1 (3)0, 2
initially there are 6 permutation:
0, 1, 2 a)
0, 2, 1 b)
1, 0, 2 c)
1, 2, 0 d)
2, 0, 1 e)
2, 1, 0 f)
however, permutation a), b), c), f) is illegal because they contain some forbidden orders as subsequence(think about substring).
so there are 2 permutation which are legal.

Input

there are multi testcases, for each testcase:
the first line two integer N, M stand for numbers of the problems, and illegal suborders (0 < N <= 15, 0 <= M <= 20)
next M lines each is an illegal suborder in such format: K a1, a2, ... ak
an integer K is length of an illegal suborder, then a1, a2, .... ak stand for an order, and they differ from each other.
(0 < K <= N, 0 <= a1, a2, ... ak < N)

the last case is two zero 0 0 which should not be processed.

Output

for each testcase one single line stands for the total numbers of legal permutation module 20000009

sample input

sample output

hint

source

Hust Monthly 09.08.21/rocket323