题目描述

有一片由 $N$ 个据点组成的区域，据点之间通过道路相连，并且这些道路恰好构成一棵树。所有据点从 $1$ 到 $N$ 编号。

现在要给每个据点分配一种标记颜色。共有 $M$ 种颜色，颜色编号为 $1,2,\cdots,M$。不过，每个据点并不一定能使用所有颜色，第 $i$ 个据点只能从给定的可用颜色集合中选择一种颜色。

为了避免相邻据点之间产生冲突，任意一条道路连接的两个据点必须染成不同的颜色。

请你计算一共有多少种合法染色方案。由于答案可能很大，只需要输出方案数对 $10^9 + 7$ 取模后的结果。

输入格式

第 $1$ 行包含两个整数 $N,M$，分别表示据点数量和颜色数量。

接下来 $N$ 行，第 $i$ 行描述编号为 $i$ 的据点可以使用的颜色。该行第 $1$ 个整数为 $k_i$，表示该据点可选颜色的数量；接下来有 $k_i$ 个整数，表示这些可选颜色的编号。

最后 $N - 1$ 行，每行包含两个整数 $A_i,B_i$，表示据点 $A_i$ 与据点 $B_i$ 之间有一条道路。

输出格式

输出一行一个整数，表示合法染色方案数对 $10^9 + 7$ 取模后的结果。

样例

2 2
1 1
2 1 2
1 2

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$。