Problem Background

After a long period of hard work, ${\rm TimeTraveller\ }$ has finally succeeded in entering his ideal school.

Problem Description

As a food lover, ${\rm TimeTraveller\ }$’s first task upon enrollment is not to register but to investigate the dishes in the cafeteria. However, due to various reasons, the dishes available this semester are few, and the cafeteria has set a menu for several days. Therefore, the dishes provided each day will cycle through the menu. Upon hearing this, ${\rm TimeTraveller\ }$ is naturally devastated, but he still hopes to avoid eating the same dish two days in a row. Thus, ${\rm TimeTraveller\ }$ decides that as long as the dish he eats today is different from the one he ate yesterday, he is satisfied. However, being a food lover, ${\rm TimeTraveller\ }$ certainly does not want to go hungry, so he must eat at least one dish every day.

${\rm TimeTraveller\ }$ wants to know how many valid planning schemes there are, but he finds that the number is too large. Therefore, he comes to seek your help, hoping you can write a program to calculate it for him.

Input Format

The first line contains three positive integers $n, m, k$, representing the number of days in the semester, the total number of dishes, and the number of days for which the school has set a menu (all dishes are numbered from 1 to $m$, and it is guaranteed that $n \geq k$).

The next $k$ lines, each starting with a number $p$ indicating the number of dishes prepared for that day, followed by $p$ numbers representing the dishes for that day (it is guaranteed that $p$ does not exceed $m$, and these $p$ numbers are unique).

Output Format

Output the number of valid schemes. Since the answer may be very large, you only need to output the value of the answer modulo $1e9+7$.

Sample Input and Output

Sample Input #1

3 3 2
2 1 3
2 2 3

Sample Output #1

11

Sample Input #2

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

Sample Output #2

730285459

Notes

Sample 1 Explanation:

Scheme 1: Day 1 eats dishes 1 and 3, Day 2 eats dish 2, Day 3 eats dishes 1 and 3;

Scheme 2: Day 1 eats dishes 1 and 3, Day 2 eats dish 2, Day 3 eats dish 3;

Scheme 3: Day 1 eats dishes 1 and 3, Day 2 eats dish 2, Day 3 eats dish 1;

Scheme 4: Day 1 eats dish 3, Day 2 eats dish 2, Day 3 eats dishes 1 and 3;

Scheme 5: Day 1 eats dish 3, Day 2 eats dish 2, Day 3 eats dish 3;

Scheme 6: Day 1 eats dish 3, Day 2 eats dish 2, Day 3 eats dish 1;

Scheme 7: Day 1 eats dish 1, Day 2 eats dishes 2 and 3, Day 3 eats dish 1;

Scheme 8: Day 1 eats dish 1, Day 2 eats dish 3, Day 3 eats dish 1;

Scheme 9: Day 1 eats dish 1, Day 2 eats dish 2, Day 3 eats dishes 1 and 3;

Scheme 10: Day 1 eats dish 1, Day 2 eats dish 2, Day 3 eats dish 3;

Scheme 11: Day 1 eats dish 1, Day 2 eats dish 2, Day 3 eats dish 1.

Data Range:

• For 20% of the data, $n \leq 5, m \leq 7, k \leq 5$;
• For 45% of the data, $n \leq 50000, m \leq 7, k \leq 7$;
• For another 10% of the data, $n \leq 10^7, m \leq 2, k = 1$;
• For 70% of the data, $n \leq 10^7, m \leq 7, k \leq 7$;
• For 100% of the data, $n \leq 10^7, m \leq 7, k \leq 300$.

见题面 Input 部分

见题面 Output 部分