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

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

3,5 секунди

64 мегабайти

Легка

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

Макса, друга Назіка, також зацікавило це дерево. Але ще більше його цікавлять особливі шляхи в цьому дереві. Улюблене число Макса — $M$ , що є взаємно простим з $10$ , тобто $g c d (M, 10) = 1$ gcd(M, 10) = 1.

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

Формально, хлопці вважають впорядковану пару різних вершин $(u, v)$ особливою, якщо виконується наступне:

Нехай $a_{1} = u$ a_1 = u, $a_{2}, ..., a_{k} = v$ a_2, ..., a_k = v — послідовність вершин на найкоротшому шляху від $u$ до $v$ у порядку їх проходження;
Нехай $d_{i}$ d_i ( $1 \leq i < k$ 1 \le i < k) — цифра, записана на ребрі між вершинами $a_{i}$ a_i та $a_{i + 1}$ a_{i+1};
Ціле число $d_{1} d_{2} ... d_{k - 1} = \sum_{i = 1}^{k - 1} d_{i} 1 0^{k - 1 - i}$ d_1 d_2 ... d_{k-1} = \sum_{i=1}^{k-1} d_i 10^{k-1-i} ділиться на $M$ .

Допоможіть хлопцям знайти кількість особливих пар.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $M$ ( $2 \leq n \leq 100000$ 2 \le n \le 100\,000, $1 \leq M \leq 1 0^{9}$ 1 \le M \le 10^9, $g c d (M, 10) = 1$ gcd(M, 10) = 1) — кількість вершин і улюблене число Макса.

Наступні $n - 1$ n - 1 рядків містять по три цілі числа. $i$ -й з них містить $u_{i}$ u_i, $v_{i}$ v_i і $w_{i}$ w_i, що означають ребро між вершинами $u_{i}$ u_i та $v_{i}$ v_i, на якому записана цифра $w_{i}$ w_i ( $1 \leq u_{i}, v_{i} \leq n$ 1 \le u_i, v_i \le n, $1 \leq w_{i} \leq 9$ 1 \le w_i \le 9).

Вихідні дані

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

Приклади

\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}

Приклад 1

Примітка

У першому прикладі з умови особливими є пари $(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$ .