ZS 编码器有一棵大树。它可以表示为由编号为 0 到 n - 1 的 n 个顶点以及它们之间的 n - 1 条边组成的无向连通图。每个边缘上都写有一个非零数字。
有一天,编码员 ZS 很无聊,决定调查一下这棵树的一些属性。他选择了一个与 10 互质的正整数 M,即 $$\gcd(M, 10) = 1$$。
ZS 认为一对有序的不同顶点 (u, v) 很有趣,如果他沿着从顶点 u 到顶点 v 的最短路径并以相同的顺序写下他在路径上遇到的所有数字,他将得到可被 M 整除的整数的十进制表示。
形式上,如果满足以下条件,则 ZS 认为一对有序的不同顶点 (u, v) 是有趣的:
- 设 a1 = u, a2, ..., ak = v 为从 u 到 v 的最短路径上的顶点序列(按照遇到它们的顺序);
- 令 di (1 ≤ i < k) 为写在顶点 ai 和 ai + 1 之间的边上的数字;
- 整数 $$\frac{d_1 d_2 \ldots d_{k-1}}{d_k} = \sum_{i=1}^{k-1} d_i \cdot 10^{k-1-i}$$ 可以被 M 整除。
帮助编码员 ZS 找到有趣对的数量!
输入
输入的第一行包含两个整数,n 和 M (2 ≤ n ≤ 100 000, 1 ≤ M ≤ 109, $$\gcd(M, 10) = 1$$) - 分别是顶点数和 ZS 选择的数。
接下来的 n - 1 行每行包含三个整数。其中第 i 个包含 ui、vi 和 wi,表示顶点 ui 和 vi 之间的一条边,上面写有数字 wi(0 ≤ ui,vi < n,1 ≤ wi ≤ 9)。
输出
打印一个整数——有趣的(由 ZS 编码员考虑)对的数量。
示例
输入 #1
6 7 0 1 2 4 2 4 2 0 1 3 0 9 2 5 7
输出 #1
7
输入 #2
5 11 1 2 3 2 0 3 3 0 3 4 3 3
输出 #2
8
注意
在第一个示例案例中,有趣的对是 (0, 4)、(1, 2)、(1, 5)、(3, 2)、(2, 5)、(5, 2)、(3, 5)。这些对组成的数字分别是 14、21、217、91、7、7、917,它们都是 7 的倍数。请注意,(2, 5) 和 (5, 2) 被认为是不同的。
在第二个示例案例中,有趣的对是 (4, 0)、(0, 4)、(3, 2)、(2, 3)、(0, 1)、(1, 0)、(4, 1)、(1, 4),其中 6 个对给出数字 33,其中 2 个对给出数字 3333,它们都是 11 的倍数。