题面描述

给你一棵由 $n$ 个节点的树和一个数 $x$，其中每个节点都有一个值。有多少条简单路径的值的 $\text{lcm}$ 为 $x$？

一条简单路径的 $\text{lcm}$ 的定义为路径上所有节点的值的 $\text{lcm}$。

输入

第一行输入两个数 $n$（$1 \leq n \leq 10^5$），$x$（$2 \leq x \leq 10^7$），表示节点的个数和目标值 $x$。 接下来 $n - 1$ 行，每行两个数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 之间存在一条边。 接下来一行 $n$ 个数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq 10^9$），每个节点的值。

输出

输出一个数，满足条件的路径的数量。

样例输入：

样例1：
3 2
1 2
2 3
2 2 2
样例2：
6 6
1 2
1 3
2 4
2 5
3 6
6 1 4 2 3 5

样例输出：

样例1：
6
样例2：
5

注：

对于前 $30\%$ 的数据有： $1\leq n \leq 10^3$