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
-
3 3 3 0 1 2 2 2 1 2 0 2 0 0
- sample output
-
2
- hint
- source
- Hust Monthly 09.08.21/rocket323