#6400. yww 与连通块计数

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yww

题目描述

蒟蒻yww发现了一棵 n 个点的树。树上的每个点都有一个权值 a_i

yww想选出一个连通块,这个连通块不能是空的。

这个连通块必须满足某种条件。具体来说,连通块内的点必须满足所有点的点权的 \gcd=s1 且所有点的点权的 \operatorname{lcm}=s2

yww想计算有多少种合法的方案,于是就来向你求助。

由于方案数很多,所以你只需要输出方案数 1000000007 的值。

输入格式

第一行有三个整数: n,s1,s2

第二行有 n 个整数:第 i 个数是 a_i

接下来 n−1 行每行有两个整数: x,y ,表示第 x 个点和第 y 个点之间有一条边。

输出格式

输出一个整数:答案。

1000000007 取模。

样例

样例一

input

3 1 2
1 2 2
1 2
1 3

output

3

explanation

总共有 3 种方案: \{1,2\},\{1,3\},\{1,2,3\}

数据范围与提示

子任务 1 5 分): n\leq 20,s2\leq {10}^3

子任务 2 5 分): n\leq 1000,s2=1

子任务 3 10 分): n\leq 1000,s2\leq {10}^3

子任务 4 10 分): n\leq 1000,s2\leq {10}^5

子任务 5 10 分): n\leq 1000,s2\leq {10}^7

子任务 6 20 分): n\leq 1000,s2\leq {10}^{10}

子任务 7 40 分): n\leq 1000,s2\leq {10}^{18}

对于 100\% 的数据, 1\leq n\leq 1000,1\leq a_i,s1,s2\leq {10}^{18},s1∣a_i,a_i∣s2 ,保证 s2 的所有质因子都不大于 50 \nexists i>1 满足 i^2\mid s2 (就是 s2 没有平方因子的意思)。

题目来源:全是水题的GDOI模拟赛 by yww