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

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

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

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

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

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

• Нехай $d$ i ($1$ ≤ $i$ < $k$) — цифра, записана на ребрi мiж вершинами $a_i$ та $a_{i+1}$;

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

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

Вхідні дані

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

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

Вихідні дані

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

####Примiтка

В першому прикладi з умови особливими є пари (1, 5), (2, 3), (2, 6), (4, 3), (3, 6), (6, 3), (4, 6).

Числа, що створюються цими парами — 14, 21, 217, 91, 7, 7, 917 вiдповiдно, всi вони кратнi 7. Звернiть увагу, що (3, 6) i (6, 3) вважаються рiзними парами.

В другому прикладi з умови особливими є пари (5, 1), (1, 5), (4, 3), (3, 4), (1, 2), (2, 1), (5, 2), (2, 5), i 6 з цих пар дають число 33, а 2 з них дають число 3333, i всi вони кратнi 11.

Приклади