染色计数

题目描述

有一颗$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$。