#include <bits/stdc++.h>   using namespace std;   int n, Mod, p[100010], a[200010], nxt[200010], w[200010], tot, root,       size[100010], son[100010], cnt;   bool vis[100010];   long long ans, mul[100010];   struct record {     int dep, step;     record(int D = 0, int S = 0) {       dep = D;       step = S;     }   } pre[100010], suf[100010];   int comp(record a, record b) { return a.dep < b.dep; }   void add(int x, int y, int val) {     tot++;     a[tot] = y;     nxt[tot] = p[x];     w[tot] = val;     p[x] = tot;   }   void getroot(int u, int fa, int N) {     size[u] = 1;     son[u] = 0;     for (int i = p[u]; i != 0; i = nxt[i])       if (a[i] != fa && vis[a[i]] == false) {         getroot(a[i], u, N);         size[u] += size[a[i]];         son[u] = max(son[u], size[a[i]]);       }     son[u] = max(son[u], N - size[u]);     if (son[u] < son[root]) root = u;   }   void getdeep(int u, int fa, long long pred, int step, long long sufd) {     pre[++cnt] = record(pred, step);     suf[cnt] = record(sufd, step);     for (int i = p[u]; i != 0; i = nxt[i])       if (a[i] != fa && vis[a[i]] == false)         getdeep(a[i], u, (pred * 10 + w[i]) % Mod, step + 1,                 (sufd + w[i] * mul[step] % Mod) % Mod);   }   int findL(int l, int r, int x, record *v) {     int mid;     while (l != r) {       mid = (l + r) >> 1;       if (v[mid].dep >= x)         r = mid;       else         l = mid + 1;     }     if (v[l].dep != x) return 1000000000;     return l;   }   int findR(int l, int r, int x, record *v) {     int mid, ans = 0;     while (l <= r) {       mid = (l + r) >> 1;       if (v[mid].dep <= x) {         ans = max(ans, mid);         l = mid + 1;       } else         r = mid - 1;     }     if (v[ans].dep != x) return 0;     return ans;   }   long long getnum(int l, int r, int now, record *v) {     int L, R;     if (l > r) return 0;     L = findL(l, r, now, v);     R = findR(l, r, now, v);     if (L <= R) return R - L + 1;     return 0;   }   void exgcd(int a, int b, long long &x, long long &y) {     if (b == 0) {       x = 1;       y = 0;       return;     }     long long t;     exgcd(b, a % b, x, y);     t = x;     x = y;     y = t - (a / b) * y;   }   int getinv(long long A, long long B) {     long long x, y;     exgcd(A, Mod, x, y);     x = (x % Mod + Mod) % Mod;     x = (x * B) % Mod;     return x;   }   long long calc(int u, int pre0, int s0, int suf0) {     long long sum = 0;     cnt = 0;     getdeep(u, 0, pre0, s0, suf0);     sort(pre + 1, pre + cnt + 1, comp);     sort(suf + 1, suf + cnt + 1, comp);     for (int i = 1; i <= cnt; i++) {       int now = getinv(mul[pre[i].step], Mod - pre[i].dep);       sum += getnum(1, cnt, now, suf);       if (now == 0) --sum;     }     return sum;   }   void work(int u) {     ans += calc(u, 0, 0, 0);     vis[u] = true;     for (int i = p[u]; i != 0; i = nxt[i])       if (vis[a[i]] == false) {         ans -= calc(a[i], w[i] % Mod, 1, w[i] % Mod);         root = 0;         getroot(a[i], 0, size[a[i]]);         work(root);       }   }   int main() {     scanf( %d%d , &n, &Mod);     for (int i = 1; i < n; i++) {       int x, y, v;       scanf( %d%d%d , &x, &y, &v);       ++x;       ++y;       add(x, y, v);       add(y, x, v);     }     son[0] = 1000000000;     root = 0;     mul[0] = 1;     for (int i = 1; i <= n; i++) mul[i] = mul[i - 1] * 10 % Mod;     getroot(1, 0, n);     work(root);     printf( %I64d n , ans);     return 0;   }   