luogu#P4982. 规划
规划
题目背景
经过长期的艰苦奋斗,终于成功进入了理想的学校。
题目描述
作为吃货的,入学的第一件事不是去报到,而是去食堂调查菜品。但是由于各种原因,本学期食堂的菜品很少,而且食堂制定了几天的菜谱,那么这个学期里,以后每天提供的菜品都会按照菜谱轮流循环进行。听到这件事,的内心当然是崩溃的,但是他还是希望每天能吃的不那么重复,于是决定只要和前一天吃的菜不重复就行了,但是身为吃货的当然也不想饿肚子,所以每天至少都要吃一道菜。
想要知道他有多少种合法的规划方案,但是他发现这实在是太多了,于是他来求助你,希望你能编写一个程序帮他计算。
输入格式
第一行三个正整数,分别表示这个学期有天,总共有种菜品,学校制定了天的菜谱(所有菜品从到编号,保证)。
接下来行,每行第一个数表示这一天学校准备了道菜,紧接着有个数,表示这一天的道菜分别是哪几道(保证不会超过,且这个数都是不重复的)。
输出格式
输出合法方案的数量,由于答案可能过大,你只需要输出答案对取模后的值。
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
提示
样例解释:
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品;
方案:第一天吃号菜品,第二天吃号菜品,第三天吃号菜品。
数据范围:
-
对于的数据,;
-
对于的数据,;
-
另有的数据,;
-
对于的数据,;
-
对于的数据,。