ZS the Coder has a large tree. It can be represented as an undirected connected graph of _n_ vertices numbered from 0 to _n_ - 1 and _n_ - 1 edges between them. There is a single **nonzero** digit written on each edge.
One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer _M_, which is **coprime** to 10, i.e. .
ZS consider an **ordered pair** of distinct vertices (_u_, _v_) _interesting_ when if he would follow the shortest path from vertex _u_ to vertex _v_ and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by _M_.
Formally, ZS consider an ordered pair of distinct vertices (_u_, _v_) interesting if the following states true:
* Let _a_1 = _u_, _a_2, ..., _a__k_ = _v_ be the sequence of vertices on the shortest path from _u_ to _v_ in the order of encountering them;
* Let _d__i_ (1 ≤ _i_ < _k_) be the digit written on the edge between vertices _a__i_ and _a__i_ + 1;
* The integer is divisible by _M_.
Help ZS the Coder find the number of interesting pairs!
## Input
The first line of the input contains two integers, _n_ and _M_ (2 ≤ _n_ ≤ 100 000, 1 ≤ _M_ ≤ 109, ) — the number of vertices and the number ZS has chosen respectively.
The next _n_ - 1 lines contain three integers each. _i_\-th of them contains _u__i_, _v__i_ and _w__i_, denoting an edge between vertices _u__i_ and _v__i_ with digit _w__i_ written on it (0 ≤ _u__i_, _v__i_ < _n_, 1 ≤ _w__i_ ≤ 9).
## Output
Print a single integer — the number of interesting (by ZS the Coder's consideration) pairs.
[samples]
## Note
In the first sample case, the interesting pairs are (0, 4), (1, 2), (1, 5), (3, 2), (2, 5), (5, 2), (3, 5). The numbers that are formed by these pairs are 14, 21, 217, 91, 7, 7, 917 respectively, which are all multiples of 7. Note that (2, 5) and (5, 2) are considered different.
<center></center>In the second sample case, the interesting pairs are (4, 0), (0, 4), (3, 2), (2, 3), (0, 1), (1, 0), (4, 1), (1, 4), and 6 of these pairs give the number 33 while 2 of them give the number 3333, which are all multiples of 11.
<center></center>
[{"iden":"statement","content":"ZS the Coder 有一棵大树。它可以表示为一个包含 #cf_span[n] 个顶点（编号从 #cf_span[0] 到 #cf_span[n - 1]）和 #cf_span[n - 1] 条边的无向连通图。每条边上都写有一个 *非零* 数字。\n\n有一天，ZS the Coder 感到无聊，决定研究这棵树的一些性质。他选择了一个正整数 #cf_span[M]，该数与 #cf_span[10] 互质，即 。\n\nZS 认为一个 *有序对* 的不同顶点 #cf_span[(u, v)] 是 *有趣的*，当且仅当他沿着从顶点 #cf_span[u] 到顶点 #cf_span[v] 的最短路径行走，并按顺序写下路径上遇到的所有数字时，所得到的十进制表示的整数能被 #cf_span[M] 整除。\n\n形式化地说，ZS 认为一个有序对的不同顶点 #cf_span[(u, v)] 是有趣的，当且仅当以下条件成立：\n\n帮助 ZS the Coder 找出有趣的有序对的数量！\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[M]（#cf_span[2 ≤ n ≤ 100 000]，#cf_span[ 1 ≤ M ≤ 10^9]）——分别是顶点数和 ZS 选择的数。\n\n接下来的 #cf_span[n - 1] 行每行包含三个整数。第 #cf_span[i] 行包含 #cf_span[ui, vi] 和 #cf_span[wi]，表示顶点 #cf_span[ui] 和 #cf_span[vi] 之间有一条边，边上写有数字 #cf_span[wi]（#cf_span[0 ≤ ui, vi < n]，#cf_span[1 ≤ wi ≤ 9]）。\n\n请输出一个整数——满足 ZS the Coder 定义的有趣对的数量。\n\n在第一个样例中，有趣的对是 #cf_span[(0, 4), (1, 2), (1, 5), (3, 2), (2, 5), (5, 2), (3, 5)]。这些对形成的数字分别是 #cf_span[14, 21, 217, 91, 7, 7, 917]，它们都是 #cf_span[7] 的倍数。注意 #cf_span[(2, 5)] 和 #cf_span[(5, 2)] 被视为不同的对。\n\n在第二个样例中，有趣的对是 #cf_span[(4, 0), (0, 4), (3, 2), (2, 3), (0, 1), (1, 0), (4, 1), (1, 4)]，其中 #cf_span[6] 对形成数字 #cf_span[33]，#cf_span[2] 对形成数字 #cf_span[3333]，它们都是 #cf_span[11] 的倍数。"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[M]（#cf_span[2 ≤ n ≤ 100 000]，#cf_span[ 1 ≤ M ≤ 10^9]）——分别是顶点数和 ZS 选择的数。接下来的 #cf_span[n - 1] 行每行包含三个整数。第 #cf_span[i] 行包含 #cf_span[ui, vi] 和 #cf_span[wi]，表示顶点 #cf_span[ui] 和 #cf_span[vi] 之间有一条边，边上写有数字 #cf_span[wi]（#cf_span[0 ≤ ui, vi < n]，#cf_span[1 ≤ wi ≤ 9]）。"},{"iden":"output","content":"请输出一个整数——满足 ZS the Coder 定义的有趣对的数量。"},{"iden":"examples","content":"输入：\n6 7\n0 1 2\n4 2 4\n2 0 1\n3 0 9\n2 5 7\n输出：\n7\n\n输入：\n5 11\n1 2 3\n2 0 3\n3 0 3\n4 3 3\n输出：\n8"},{"iden":"note","content":"在第一个样例中，有趣的对是 #cf_span[(0, 4), (1, 2), (1, 5), (3, 2), (2, 5), (5, 2), (3, 5)]。这些对形成的数字分别是 #cf_span[14, 21, 217, 91, 7, 7, 917]，它们都是 #cf_span[7] 的倍数。注意 #cf_span[(2, 5)] 和 #cf_span[(5, 2)] 被视为不同的对。 在第二个样例中，有趣的对是 #cf_span[(4, 0), (0, 4), (3, 2), (2, 3), (0, 1), (1, 0), (4, 1), (1, 4)]，其中 #cf_span[6] 对形成数字 #cf_span[33]，#cf_span[2] 对形成数字 #cf_span[3333]，它们都是 #cf_span[11] 的倍数。 "}]"
Let $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $, where each edge $ e \in E $ is labeled with a digit $ w_e \in \{1, 2, \dots, 9\} $.
For any ordered pair of distinct vertices $ (u, v) $, let $ P(u, v) $ denote the unique simple path from $ u $ to $ v $ in $ T $, and let $ d(u, v) $ denote the integer formed by concatenating the digits on the edges of $ P(u, v) $ in order from $ u $ to $ v $.
Define the set of **interesting pairs** as:
$$
\mathcal{I} = \left\{ (u, v) \in V \times V \mid u \ne v,\ d(u, v) \equiv 0 \pmod{M} \right\}
$$
Given: $ \gcd(M, 10) = 1 $
**Objective:** Compute $ |\mathcal{I}| $.
---
**Input Constraints:**
- $ 2 \leq n \leq 100{,}000 $
- $ 1 \leq M \leq 10^9 $
- $ \gcd(M, 10) = 1 $
- Each edge weight $ w \in \{1, 2, \dots, 9\} $
**Output:** $ |\mathcal{I}| $