Rəqəmsal ağac#10163

Rəqəmsal ağac

3,5 saniyə

64 meqabayt

Asan

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$ 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 $g c d (M, 10) = 1$ 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$ a_1 = u, a_2, \ldots, 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}$ d_i ( $1 \leq i < k$ 1 \leq i < k) — $a_{i}$ a_i və $a_{i + 1}$ a_{i+1} zirvələri arasındakı kənarda yazılmış rəqəm olsun;
Tam ədəd $(d_{1} d_{2} \dots d_{k - 1})$ \displaystyle\left( d_1 d_2 \ldots d_{k-1} \right) = $(i = 1 \sum k - 1 d_{i} 1 0^{k - 1 - i})$ \displaystyle\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 \leq n \leq 100000$ 2 \leq n \leq 100 000, $1 \leq M \leq 1 0^{9}$ 1 \leq M \leq 10^9, $g c d (M, 10) = 1$ gcd(M, 10) = 1) tam ədədlərini ehtiva edir — zirvələrin sayı və Maksın sevimli rəqəmi.

Sonrakı $n - 1$ n - 1 sətir hər biri üç tam ədəd ehtiva edir. $i$ -ci sətir $u_{i}$ u_i, $v_{i}$ v_i və $w_{i}$ w_i ədədlərini ehtiva edir, bu da $u_{i}$ u_i və $v_{i}$ v_i zirvələri arasında olan kənarı və bu kənarda yazılmış $w_{i}$ w_i rəqəmini göstərir ( $1 \leq u_{i}, v_{i} \leq n$ 1 \leq u_i, v_i \leq n, $1 \leq w_{i} \leq 9$ 1 \leq w_i \leq 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

Nümunə 1