У Наз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ле число $\displaystyle\left( d_1 d_2 ... d_{k−1} \right)$ = $\displaystyle\left( \sum_{i=1}^{k-1} d_i 10^{k-1-1} \right)$ дiлиться на M .

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

Формат вхiдних даних

Перший рядок мiстить два цiлi числа n i M ($2 ≤ n ≤ 100 000$, $1 ≤ M ≤ 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 ≤ u_i$ , $v_i ≤ n$, $1 ≤ w_i ≤ 9$).

Формат вихiдних даних

Вивед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.