合约数

题号：NC15569
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

在埃森哲，员工培训是最看重的内容，最近一年，我们投入了 9.41 亿美元用于员工培训和职业发展。截至 2018 财年末，我们会在全球范围内设立 100 所互联课堂，将互动科技与创新内容有机结合起来。按岗培训，按需定制，随时随地，本土化，区域化，虚拟化的培训会让你快速取得成长。小埃希望能通过培训学习更多ACM 相关的知识，他在培训中碰到了这样一个问题，

给定一棵n个节点的树，并且根节点的编号为p，第i个节点有属性值val_i, 定义F(i): 在以i为根的子树中，属性值是val_i的合约数的节点个数。y 是 x 的合约数是指 y 是合数且 y 是 x 的约数。小埃想知道 $\sum_{i=1}^{n}{i \cdot F\left( i \right)}$ 对1000000007取模后的结果.

输入描述:

输入测试组数T，每组数据，输入n+1行整数，第一行为n和p，1<=n<=20000, 1<=p<=n, 接下来n-1行，每行两个整数u和v,表示u和v之间有一条边。第n+1行输入n个整数val₁, val₂,…, val_n,其中1<=val_i<=10000，1<=i<=n.

输出描述:

对于每组数据，输出一行，包含1个整数，表示 $\sum_{i=1}^{n}{i \cdot F\left( i \right)}$ 对1000000007取模后的结果

示例1

输入

复制

2
5 4
5 3
2 5
4 2
1 3
10 4 3 10 5
3 3
1 3
2 1
1 10 1

输出

复制

11
2

备注:

n>=10000的有20组测试数据