luogu#P4982. 规划

规划

题目背景

经过长期的艰苦奋斗,TimeTraveller {\rm TimeTraveller\ }终于成功进入了理想的学校。

题目描述

作为吃货的 TimeTraveller{\rm \ TimeTraveller},入学的第一件事不是去报到,而是去食堂调查菜品。但是由于各种原因,本学期食堂的菜品很少,而且食堂制定了几天的菜谱,那么这个学期里,以后每天提供的菜品都会按照菜谱轮流循环进行。听到这件事,TimeTraveller {\rm TimeTraveller\ }的内心当然是崩溃的,但是他还是希望每天能吃的不那么重复,于是 TimeTraveller {\rm \ TimeTraveller\ }决定只要和前一天吃的菜不重复就行了,但是身为吃货的 TimeTraveller {\rm \ TimeTraveller\ }当然也不想饿肚子,所以每天至少都要吃一道菜

TimeTraveller {\rm TimeTraveller\ }想要知道他有多少种合法的规划方案,但是他发现这实在是太多了,于是他来求助你,希望你能编写一个程序帮他计算。

输入格式

第一行三个正整数n,m,kn,m,k,分别表示这个学期有nn天,总共有mm种菜品,学校制定了kk天的菜谱(所有菜品从11mm编号,保证nkn ≥ k)。

接下来kk行,每行第一个数pp表示这一天学校准备了pp道菜,紧接着有pp个数,表示这一天的pp道菜分别是哪几道(保证pp不会超过mm,且这pp个数都是不重复的)。

输出格式

输出合法方案的数量,由于答案可能过大,你只需要输出答案对1e9+71e9+7取模后的值。

3 3 2
2 1 3
2 2 3

11
10 7 3
5 1 2 3 4 5
3 1 3 7
4 1 2 6 7

730285459

提示

样例11解释:

方案11:第一天吃1,31,3号菜品,第二天吃22号菜品,第三天吃1,31,3号菜品;

方案22:第一天吃1,31,3号菜品,第二天吃22号菜品,第三天吃33号菜品;

方案33:第一天吃1,31,3号菜品,第二天吃22号菜品,第三天吃11号菜品;

方案44:第一天吃33号菜品,第二天吃22号菜品,第三天吃1,31,3号菜品;

方案55:第一天吃33号菜品,第二天吃22号菜品,第三天吃33号菜品;

方案66:第一天吃33号菜品,第二天吃22号菜品,第三天吃11号菜品;

方案77:第一天吃11号菜品,第二天吃2,32,3号菜品,第三天吃11号菜品;

方案88:第一天吃11号菜品,第二天吃33号菜品,第三天吃11号菜品;

方案99:第一天吃11号菜品,第二天吃22号菜品,第三天吃1,31,3号菜品;

方案1010:第一天吃11号菜品,第二天吃22号菜品,第三天吃33号菜品;

方案1111:第一天吃11号菜品,第二天吃22号菜品,第三天吃11号菜品。

数据范围:

  • 对于20%20\%的数据,n5,m7,k5n≤ 5,m≤ 7,k≤ 5

  • 对于45%45\%的数据,n50000,m7,k7n≤ 50000,m≤ 7,k≤ 7

  • 另有10%10\%的数据,n107,m2,k=1n≤ 10^7,m≤ 2,k= 1

  • 对于70%70\%的数据,n107,m7,k7n≤ 10^7,m≤ 7,k≤ 7

  • 对于100%100\%的数据,n107,m7,k300n≤ 10^7,m≤ 7,k≤ 300