문제
준혁이는 장난감 공장의 공장장이다.
이번에 새로 나온 장난감을 설계하기 위해 준혁이는 총 M개의 부품을 주문하려 한다.
부품이 남도록 부품을 더 주문하는 것은 상관없다. 하지만 부품이 없어서 못만드는 경우는 없게 하려 한다.
그러나 부품 공장에서는 단순히 부품을 하나씩 팔지는 않는다. 구체적으로 총 N개의 팩이 있어, i번째 팩에서는 총 si종류의 부품(p1,p2,...번)을 팔며, 오직 팩 단위로만 물건을 내놓는다.
준혁이는 부자다. 그렇기에 각 팩의 가격은 궁금하지도 않다. 그러나 수학에 관심이 많은 준혁이는 모든 종류의 부품이 적어도 하나씩 있을 팩 조합의 개수는 궁금하다.
모든 부품이 적어도 하나씩 있을 팩 조합의 개수를 준혁이에게 대신 구해서 알려주자. 그러면 준혁이는 감동해 여러분에게 용돈을 줄지도 모른다.
입력
첫 줄에 팩의 종류 N(1<=N<=1000000)과 장난감 부품의 종류 M(1<=M<=20)이 주어진다.
그 다음 줄부터 팩에 있는 부품의 종류의 개수 Ki에 이어, 부품의 종류 Ki개 pi1, pi2, ...가 순서대로 주어진다. (0<=Ki<=M)
출력
모든 부품이 적어도 하나씩 있을 팩 조합의 개수를 출력한다. 답이 클 수도 있으므로 10^9+7로 나눈 나머지를 대신 출력한다.
예제1
입력
33
3123
3123
3123
출력
7
예제2
입력
33
11
12
13
출력
1
예제3
입력
45
223
212
41235
41245
출력
6
출처
COCI 2011/2012