func_code_string: #include <bits/stdc++.h>   #pragma comment(linker,  /STACK:102400000,102400000 )   using namespace std;   const int mo = 1000000007;   const int inf = 0x3f3f3f3f;   const int INF = 2000000000;   int n, m, phi;   int lt[100008], size[100008], f[100008], vis[100008], a[100008], b[100008], sum,       tot, root, pre1[100008], pre2[100008];   long long ans, Alltmp;   map<int, int> mp;   struct edge {     int u, v, w, nt;   } eg[100008 * 2];   void add(int u, int v, int w) {     eg[++sum] = (edge){u, v, w, lt[u]};     lt[u] = sum;   }   long long quick(long long x, long long y) {     long long res = 1;     while (y) {       if (y & 1) res = res * x % m;       x = x * x % m;       y >>= 1;     }     return res;   }   void init() {     int mm = m;     phi = m;     for (int i = 2; i * i <= m; i++) {       if (mm % i == 0) {         while (mm % i == 0) mm /= i;         phi = phi / i * (i - 1);       }     }     if (mm > 1) phi = phi / mm * (mm - 1);     memset(lt, 0, sizeof(lt));     ;     sum = 1;     memset(f, 0, sizeof(f));     ;     f[0] = INF;     memset(vis, 0, sizeof(vis));     ;     ans = 0;     pre1[0] = 1;     pre2[0] = 1;     for (int i = 1; i <= 100000; i++) {       pre1[i] = 1ll * pre1[i - 1] * 10 % m;       pre2[i] = quick(pre1[i], phi - 1);     }   }   void getRoot(int u, int fa) {     size[u] = 1;     f[u] = 0;     for (int i = lt[u]; i; i = eg[i].nt) {       int v = eg[i].v;       if (vis[v] || v == fa) continue;       getRoot(v, u);       size[u] += size[v];       f[u] = max(f[u], size[v]);     }     f[u] = max(f[u], tot - size[u]);     if (f[u] < f[root]) root = u;   }   void getA(int u, int fa, int len) {     for (int i = lt[u]; i; i = eg[i].nt) {       int v = eg[i].v;       if (vis[v] || v == fa) continue;       a[v] = (1ll * eg[i].w * pre1[len] + a[u]) % m;       getA(v, u, len + 1);     }     Alltmp += mp[a[u]];     int tp = (m - b[u]) % m;     tp = 1ll * tp * pre2[len] % m;     if (a[u] == tp) Alltmp--;   }   void getB(int u, int fa, int len) {     int tp = (m - b[u]) % m;     tp = 1ll * tp * pre2[len] % m;     mp[tp]++;     for (int i = lt[u]; i; i = eg[i].nt) {       int v = eg[i].v;       if (vis[v] || v == fa) continue;       b[v] = (1ll * b[u] * 10 + eg[i].w) % m;       getB(v, u, len + 1);     }   }   long long calc(int u, int key) {     key %= m;     Alltmp = 0;     mp.clear();     a[u] = b[u] = key;     getB(u, 0, key == 0 ? 0 : 1);     getA(u, 0, key == 0 ? 0 : 1);     return Alltmp;   }   void solve(int u) {     ans += calc(u, 0);     vis[u] = 1;     for (int i = lt[u]; i; i = eg[i].nt) {       int v = eg[i].v;       if (vis[v]) continue;       ans -= calc(v, eg[i].w);       root = 0;       tot = size[v];       getRoot(v, u);       solve(root);     }   }   int main() {     scanf( %d%d , &n, &m);     init();     for (int i = 1; i <= n - 1; i++) {       int u, v, w;       scanf( %d%d%d , &u, &v, &w);       add(u + 1, v + 1, w);       add(v + 1, u + 1, w);     }     root = 0;     tot = n;     getRoot(1, 0);     solve(root);     cout << ans << endl;   }   