Rəqəmsal ağac

Nazikin böyük bir ağacı var. Bu ağacı istiqamətsiz əlaqəli qraf kimi təsvir etmək olar, burada $n$ zirvə var, $1$-dən $n$-ə qədər nömrələnmişdir və onların arasında $n-1$ kənar mövcuddur. Hər bir kənarın üzərində sıfırdan fərqli bir rəqəm yazılmışdır.

Nazikin dostu Maks da bu ağaca maraq göstərir. Lakin onu daha çox bu ağacdakı xüsusi yollar maraqlandırır. Maksın sevimli rəqəmi $M$-dir və bu rəqəm $10$ ilə qarşılıqlı sadədir, yəni $gcd(M,10)=1$.

Maks və Nazik fərqli zirvələrin $(u,v)$ sıralı cütünü xüsusi hesab edirlər, əgər $u$ zirvəsindən $v$ zirvəsinə qədər ən qısa yolu keçdikdə, yol boyunca qarşılaşdıqları rəqəmləri eyni ardıcıllıqla yazdıqda, bu rəqəmlərdən ibarət onluq yazılış tam $M$-ə bölünər.

Rəsmi olaraq, oğlanlar fərqli zirvələrin $(u,v)$ sıralı cütünü xüsusi hesab edirlər, əgər aşağıdakı şərtlər doğrudursa:

• Qoy $a_1=u,a_2,\dots ,a_k=v$ — $u$-dan $v$-yə qədər olan ən qısa yolda zirvələrin ardıcıllığı olsun;

• Qoy $d_i$ ($1\le i<k$) — $a_i$ və $a_{i+1}$ zirvələri arasındakı kənarda yazılmış rəqəm olsun;

• Tam ədəd $\left(d_1{d}_2\dots d_{k-1}\right)$ = $\left(\sum _{i=1}^{k-1}{d}_{i}10^{k-1-i}\right)$ $M$-ə tam bölünür.

Oğlanlara xüsusi cütlərin sayını tapmaqda kömək edin.

Giriş formatı

Birinci sətir $n$ və $M$ ($2\le n\le 100000$, $1\le M\le 10^9$, $gcd(M,10)=1$) tam ədədlərini ehtiva edir — zirvələrin sayı və Maksın sevimli rəqəmi.

Sonrakı $n-1$ sətir hər biri üç tam ədəd ehtiva edir. $i$-ci sətir $u_i$, $v_i$ və $w_i$ ədədlərini ehtiva edir, bu da $u_i$ və $v_i$ zirvələri arasında olan kənarı və bu kənarda yazılmış $w_i$ rəqəmini göstərir ($1\le u_i,v_i\le n$, $1\le w_i\le 9$).

Çıxış formatı

Bir tam ədəd çıxarın — xüsusi cütlərin sayı.

Qeyd

Birinci nümunədə xüsusi cütlər (1, 5), (2, 3), (2, 6), (4, 3), (3, 6), (6, 3), (4, 6) cütləridir.

Bu cütlərdən yaranan ədədlər müvafiq olaraq 14, 21, 217, 91, 7, 7, 917-dir və hamısı 7-ə bölünür. Qeyd edək ki, (3, 6) və (6, 3) fərqli cütlər hesab olunur.

İkinci nümunədə xüsusi cütlər (5, 1), (1, 5), (4, 3), (3, 4), (1, 2), (2, 1), (5, 2), (2, 5) cütləridir və bu cütlərdən 6-sı 33, 2-si isə 3333 ədədlərini yaradır və hamısı 11-ə bölünür.

Nümunələr