#include <bits/stdc++.h>   using namespace std;   int M;   const int MAX = 100001;   vector<int> _size, marked, _pow, _ipow;   vector<pair<int, int> > adjList[MAX + 1];   int getSize(int u, int p = -1) {     _size[u] = 1;     for (auto [v, w] : adjList[u])       if (v != p && !marked[v]) _size[u] += getSize(v, u);     return _size[u];   }   int getCentroid(int u, int p, int n) {     for (auto [v, w] : adjList[u])       if (v != p && !marked[v] && _size[v] * 2 > n) return getCentroid(v, u, n);     return u;   }   void add(unordered_map<int, int> &aux, int u, int p, int lvl, int rem) {     aux[rem]++;     for (auto [v, w] : adjList[u])       if (v != p && !marked[v])         add(aux, v, u, lvl + 1, (int(1LL * w * _pow[lvl] % M) + rem) % M);   }   void remove(unordered_map<int, int> &aux, int u, int p, int lvl, int rem) {     aux[rem]--;     for (auto [v, w] : adjList[u])       if (v != p && !marked[v])         remove(aux, v, u, lvl + 1, (int(1LL * w * _pow[lvl] % M) + rem) % M);   }   long long count(unordered_map<int, int> &aux, int u, int p, int lvl, int rem) {     int nxt = int(1LL * _ipow[lvl] * (M - rem) % M);     long long ans = aux[nxt];     for (auto [v, w] : adjList[u])       if (v != p && !marked[v])         ans += count(aux, v, u, lvl + 1, (rem * 10LL + w) % M);     return ans;   }   long long solve(int u) {     int N = getSize(u);     u = getCentroid(u, -1, N);     marked[u] = 1;     unordered_map<int, int> aux;     aux[0] = 1;     for (auto [v, w] : adjList[u])       if (!marked[v]) add(aux, v, u, 1, w % M);     long long ans = aux[0] - 1;     for (auto [v, w] : adjList[u])       if (!marked[v]) {         remove(aux, v, u, 1, w % M);         ans += count(aux, v, u, 1, w % M);         add(aux, v, u, 1, w % M);       }     aux.clear();     for (auto [v, w] : adjList[u])       if (!marked[v]) ans += solve(v);     return ans;   }   int gcd(int a, int b, int &x, int &y) {     if (b == 0) {       x = 1;       y = 0;       return a;     }     int x1, y1;     int d = gcd(b, a % b, x1, y1);     x = y1;     y = x1 - y1 * (a / b);     return d;   }   int getInv() {     int x, y;     int g = gcd(10, M, x, y);     assert(g == 1);     return (x % M + M) % M;   }   int main() {     ios_base ::sync_with_stdio(false);     cin.tie(nullptr);     int n;     cin >> n >> M;     _size = vector<int>(n), _pow = vector<int>(n + 1, 1),     _ipow = vector<int>(n + 1, 1), marked = vector<int>(n + 1);     _ipow[1] = getInv();     _pow[1] = 10;     for (int i = 2; i <= n; i++) {       _pow[i] = int(1LL * _pow[i - 1] * 10 % M);       _ipow[i] = int(1LL * _ipow[i - 1] * _ipow[1] % M);     }     for (int i = 0; i < n - 1; i++) {       int u, v, w;       cin >> u >> v >> w;       adjList[u].push_back({v, w});       adjList[v].push_back({u, w});     }     cout << solve(0) <<   n ;     return 0;   }   