题目描述

蒟蒻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