eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 3.5 seconds
Memory limit 64 MiB

У Наз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рно наступне:

  • Нехай 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сть особливих пар.

Input data

Перший рядок м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).

Output data

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

Examples

Input example #1
6 7
1 2 2
5 3 4
3 1 1
4 1 9
3 6 7
Output example #1
7