题目描述

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

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

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

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

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

输入格式

第一行有三个整数：$n,s_1,s_2$。

第二行有 $n$ 个整数：第 $i$ 个数是 $a_i$。

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

输出格式

输出一个整数：答案。

对 $1000000007$ 取模。

3 1 2
1 2 2
1 2
1 3

3

总共有 $3$ 种方案：$\{1,2\},\{1,3\},\{1,2,3\}$。

数据范围与提示

子任务 $1$（$5$ 分）：$n\leq 20,s_2\leq {10}^3$。

子任务 $2$（$5$ 分）：$n\leq 1000,s_2=1$。

子任务 $3$（$10$ 分）：$n\leq 1000,s_2\leq {10}^3$。

子任务 $4$（$10$ 分）：$n\leq 1000,s_2\leq {10}^5$。

子任务 $5$（$10$ 分）：$n\leq 1000,s_2\leq {10}^7$。

子任务 $6$（$20$ 分）：$n\leq 1000,s_2\leq {10}^{10}$。

子任务 $7$（$40$ 分）：$n\leq 1000,s_2\leq {10}^{18}$。

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

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