题目描述

枫丹境内有 $n$ 座城市，这 $n$ 座城市之间由 $n-1$ 条双向道路连接，使得任意两座城市之间都能互相到达。枫丹人民共使用 $k$ 种能源，其中第 $i$ 座城市中的居民一共使用 $l_i$ 种能源，分别为 $a_{i,1},a_{i,2},\cdots,a_{i,l_i}$。

现在最高审判官想将所有 $n$ 座城市划分为若干个经济区，其中第 $i$ 个经济区由一些城市 $c_{i,1},c_{i,2},\cdots$ 组成。为了克服能源不同而产生的障碍，每个经济区会花费一定的摩拉来建立能源转化装置。对第 $i$ 个经济区，其中的能源转化装置需要支持转化所有经济区中城市的能源，同时由于货运只能通过这 $n-1$ 条道路进行，该能源转化装置也需要支持转化所有处于经济区中某两个城市 $c_{i,p},c_{i,q}$ 间的简单路径上的城市的能源。如果确定需要支持转化的能源共有 $t$ 种，则建立能源转化装置所需的摩拉为 $w_{t}$。

在确定完经济区的划分之后，这种划分的代价定义为各经济区建立能源转化装置的摩拉数之和。现在请你求出所有本质不同的划分的代价之和。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模之后的结果即可。

定义两种划分本质不同，当且仅当存在两个不同的城市 $i,j$，满足 $i,j$ 在一种划分方式中处于同一个经济区内，而在另一种划分方式中不处于同一个经济区内。

输入格式

从文件 water.in 中读入数据。

第一行包含两个正整数 $n,k$。

第二行包含 $k$ 个正整数 $w_{1\cdots k}$。

接下来 $n$ 行，每行第一个正整数 $l_i$，后面包含 $l_i$ 个两两不同的正整数 $a_{i,1},a_{i,2},\cdots ,a_{i,l_i}$，表示第 $i$ 座城市中居民使用的能源。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示一条双向道路的两个端点。

输出格式

输出到文件 water.out 中。

输出一行一个整数，表示答案。

样例1输入

3 3
1 2 4
1 1
1 2
1 3
1 2
2 3

样例1输出

18

样例1解释

共有以下 $5$ 种划分方式，$t_i$ 表示每个经济区能源转化装置需要支持转化的能源种类数：

• $\{1,2,3\},t_1=3$：共需 $w_3=4$ 的摩拉
• $\{1,2\},t_1=2;\{3\},t_2=1$：共需 $w_2+w_1=3$ 的摩拉
• $\{1,3\},t_1=3;\{2\},t_2=1$：共需 $w_3+w_1=5$ 的摩拉
• $\{1\},t_1=1;\{2,3\},t_2=2$：共需 $w_1+w_2=3$ 的摩拉
• $\{1\},t_1=1;\{2\},t_2=1;\{3\},t_3=1$：共需 $w_1+w_1+w_1=3$ 的摩拉

总和为 $4+3+5+3+3=18$ 摩拉。

样例2输入

7 5
12 34 56 78 90
1 2
2 1 2
2 2 3
3 1 3 4
1 4
2 1 5
2 3 5
1 2
1 3
2 4
2 5
3 6
3 7

样例2输出

183666

样例3

见题目目录下的 3.in 与 3.ans。

样例3解释

这个数据满足 Subtask 1 的限制。

样例4

见题目目录下的 4.in 与 4.ans。

样例4解释

这个数据满足 Subtask 3 的限制。

子任务

本题存在子任务捆绑

对所有数据，保证 $1\le n\le 5000,1\le l_i\le k\le 10,1\le a_{i,j}\le k,1\le u,v\le n,1\le w_i<10^9+7$。

​