题目描述

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

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

这个连通块必须满足某种条件。具体来说，连通块内的点必须满足所有点的点权的 gcd=s_1 且所有点的点权的 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≤20,s_2≤10^3。

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

子任务 3（10 分）：n≤1000,s_2≤10^3。

子任务 4（10 分）：n≤1000,s_2≤10^5。

子任务 5（10 分）：n≤1000,s_2≤10^7。

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

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

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

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