题目背景

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

题目描述

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

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

输入格式

第一行三个正整数$n,m,k$，分别表示这个学期有$n$天，总共有$m$种菜品，学校制定了$k$天的菜谱（所有菜品从$1$到$m$编号，保证$n ≥ k$）。

接下来$k$行，每行第一个数$p$表示这一天学校准备了$p$道菜，紧接着有$p$个数，表示这一天的$p$道菜分别是哪几道（保证$p$不会超过$m$，且这$p$个数都是不重复的）。

输出格式

输出合法方案的数量，由于答案可能过大，你只需要输出答案对$1e9+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

提示

样例$1$解释：

方案$1$：第一天吃$1,3$号菜品，第二天吃$2$号菜品，第三天吃$1,3$号菜品；

方案$2$：第一天吃$1,3$号菜品，第二天吃$2$号菜品，第三天吃$3$号菜品；

方案$3$：第一天吃$1,3$号菜品，第二天吃$2$号菜品，第三天吃$1$号菜品；

方案$4$：第一天吃$3$号菜品，第二天吃$2$号菜品，第三天吃$1,3$号菜品；

方案$5$：第一天吃$3$号菜品，第二天吃$2$号菜品，第三天吃$3$号菜品；

方案$6$：第一天吃$3$号菜品，第二天吃$2$号菜品，第三天吃$1$号菜品；

方案$7$：第一天吃$1$号菜品，第二天吃$2,3$号菜品，第三天吃$1$号菜品；

方案$8$：第一天吃$1$号菜品，第二天吃$3$号菜品，第三天吃$1$号菜品；

方案$9$：第一天吃$1$号菜品，第二天吃$2$号菜品，第三天吃$1,3$号菜品；

方案$10$：第一天吃$1$号菜品，第二天吃$2$号菜品，第三天吃$3$号菜品；

方案$11$：第一天吃$1$号菜品，第二天吃$2$号菜品，第三天吃$1$号菜品。

数据范围：

• 对于$20\%$的数据，$n≤ 5,m≤ 7,k≤ 5$；

• 对于$45\%$的数据，$n≤ 50000,m≤ 7,k≤ 7$；

• 另有$10\%$的数据，$n≤ 10^7,m≤ 2,k= 1$；

• 对于$70\%$的数据，$n≤ 10^7,m≤ 7,k≤ 7$；

• 对于$100\%$的数据，$n≤ 10^7,m≤ 7,k≤ 300$。