Digital Tree

Input

The first line contains two integers $n$ and $M$ (2 \leq n \leq 100\,000, 1 \leq M \leq 10^9, \gcd(M, 10) = 1) — the number of vertices and Max's favorite number.

The next n - 1 lines each contain three integers u_i, v_i, and w_i, indicating an edge between vertices u_i and v_i with the digit w_i (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 9) written on it.

Output

Output a single integer — the number of special pairs.

Examples

\begin{example}\exmp{6 71 2 11 3 42 4 22 5 33 6 7}{7}%\exmp{5 111 2 32 3 33 4 34 5 3}{8}%\end{example}

Note

In the first example, the special pairs are $(1,5)$, $(2,3)$, $(2,6)$, $(4,3)$, $(3,6)$, $(6,3)$, $(4,6)$.

The numbers formed by these paths are $14$, $21$, $217$, $91$, $7$, $7$, and $917$, respectively, all divisible by $7$. Note that $(3,6)$ and $(6,3)$ are considered different pairs.

In the second example, the special pairs are $(5,1)$, $(1,5)$, $(4,3)$, $(3,4)$, $(1,2)$, $(2,1)$, $(5,2)$, and $(2,5)$. For these, $6$ pairs correspond to the number $33$ and $2$ pairs to the number $3333$, all divisible by $11$.