染色计数
题目描述
有一颗$N$个节点的树,节点用$1,2,\cdots,N$编号。你要给它染色,使得相邻节点的颜色不同。有$M$种颜色,用$1,2,\cdots,M$编号。每个节点可以染$M$种颜色中的若干种,求不同染色方案的数量除以($10^9 + 7$)的余数。
输入输出格式
输入格式
第1 行,2 个整数$N,M$。
接下来$N$行,第$i$行表示节点$i$可以染的颜色。第1个整数$k_i$,表示可以染的颜色数量。接下来$k_i$个整数,表示可以染的颜色编号。
最后$N - 1$行,每行2个整数$A_i,B_i$,表示边$(A_i,B_i)$。
输出格式
1 个整数,表示所有的数。
输入输出样例
输入样例 #1
2 2
1 1
2 1 2
1 2
输出样例 #1
1
说明
• 对于30% 的数据,$1 \le N \le 10; 1 \le M \le 4$;
• 对于60% 的数据,$1 \le N \le 200; 1 \le M \le 200$;
• 对于100% 的数据,$1 \le N \le 5000; 1 \le M \le 5000$。