Цифровое дерево

У Назика есть большое дерево, которое можно представить как неориентированный связный граф с $n$ вершинами, пронумерованными от $1$ до $n$, и $n-1$ ребрами. На каждом ребре записана одна ненулевая цифра.

Макса, друга Назика, тоже заинтересовало это дерево. Однако его больше интересуют особые пути в этом дереве. Любимое число Макса — $M$, которое взаимно просто с $10$, то есть $gcd(M,10)=1$.

Макс и Назик считают упорядоченную пару различных вершин $(u,v)$ особенной, если, пройдя по кратчайшему пути от вершины $u$ до вершины $v$ и записав цифры, встречающиеся на пути, в том же порядке, они получат десятичную запись целого числа, которое делится нацело на $M$.

Формально, пара $(u,v)$ считается особенной, если выполняется следующее:

• Пусть $a_1=u,a_2,...,a_k=v$ — последовательность вершин на кратчайшем пути от $u$ до $v$ в порядке их следования;

• Пусть $d_i$ ($1$ ≤ $i$ < $k$) — цифра, записанная на ребре между вершинами $a_i$ и $a_{i+1}$;

• Целое число $\left(d_1{d}_2...d_{k-1}\right)$ = $\left(\sum _{i=1}^{k-1}{d}_{i}10^{k-1-i}\right)$ делится на $M$.

Помогите ребятам найти количество особенных пар.

Формат входных данных

Первая строка содержит два целых числа $n$ и $M$ ($2\le n\le 100000$, $1\le M\le 10^9$, $gcd(M,10)=1$) — количество вершин и любимое число Макса.

Следующие $n-1$ строк содержат по три целых числа. $i$-я из них содержит $u_i$, $v_i$ и $w_i$, которые обозначают ребро между вершинами $u_i$ и $v_i$, на котором записана цифра $w_i$ ($1\le u_i$, $v_i\le n$, $1\le w_i\le 9$).

Формат выходных данных

Выведите одно целое число — количество особенных пар.

Примеры

Примечание

В первом примере из условия особенными являются пары (1, 5), (2, 3), (2, 6), (4, 3), (3, 6), (6, 3), (4, 6).

Числа, которые создаются этими парами — 14, 21, 217, 91, 7, 7, 917 соответственно, все они кратны 7. Обратите внимание, что (3, 6) и (6, 3) считаются разными парами.

Во втором примере из условия особенными являются пары (5, 1), (1, 5), (4, 3), (3, 4), (1, 2), (2, 1), (5, 2), (2, 5), и 6 из этих пар дают число 33, а 2 из них дают число 3333, и все они кратны 11.