У Назiка є велике дерево. Його можна представити як неорiєнтовний зв’язний граф з n вершин,пронумерованих вiд 1 до n, i n−1 ребер мiж ними. На кожному ребрi записана одна ненульова цифра.
Макса, друга Назiка, також зацiкавило це дерево. Але ще бiльше його цiкавлять особливi шляхи в цьому деревi. Улюблене число Макса — M , що являється взаємно простим з 10, тобто 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рно наступне:
Нехай a1=u,a2,...,ak=v — послiдовнiсть вершин на найкоротшому шляху вiд u до v впорядку їх зустрiчi;
Нехай d i (1≤i<k) — цифра, записана на ребрi мiж вершинами ai та ai+1;
Цiле число (d1d2...dk−1) = (i=1∑k−1di10k−1−1) дiлиться на M .
Допоможiть хлопцям знайти кiлькiсть особливих пар.
Перший рядок мiстить два цiлi числа n i M (2≤n≤100000, 1≤M≤109 , gcd(M,10)=1) —кiлькiсть вершин i улюблене число Макса.
Наступнi n − 1 рядкiв мiстять по три цiлi числа. i-а з них мiстить ui , vi i wi , що означають ребро мiж вершинами ui та vi, на якому записана цифра wi (1≤ui , vi≤n, 1≤wi≤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.