#include <bits/stdc++.h>   #pragma GCC optimize( O3 )   using namespace std;   using ll = long long;   using pii = pair<ll, int>;   const int INF = 1e9 + 1e2;   void fin() {}   const bool flag = 0;   const int N = 1e5 + 10;   int MOD;   int mult(ll a, ll b) { return a * 1ll * b % MOD; }   ll binpow(ll a, int b) {     ll res = 1;     while (b) {       if (b & 1) {         res = mult(res, a);       }       a = mult(a, a);       b >>= 1;     }     return res;   }   vector<pii> adj[N];   int sz[N], po[N];   bool cent[N];   void calc_sz(int first, int p = -1) {     sz[first] = 1;     for (pii to : adj[first]) {       if (to.first != p && !cent[to.first]) {         calc_sz(to.first, first);         sz[first] += sz[to.first];       }     }   }   int c_sz;   int fnd(int first, int p = -1) {     for (pii to : adj[first]) {       if (to.first != p && !cent[to.first] && sz[to.first] > c_sz / 2) {         return fnd(to.first, first);       }     }     return first;   }   ll ans;   int add(ll a, int b) { return (a + b + MOD) % MOD; }   map<int, ll> cnt;   void dfsadd(int first, int d, int r, int p = -1) {     cnt[r]++;     for (pii to : adj[first]) {       if (to.first != p && !cent[to.first]) {         dfsadd(to.first, d + 1, add(r, mult(po[d], to.second)), first);       }     }   }   void dfscalc(int first, int d, int r1, int r2, int p = -1) {     ans += (r1 == 0) + (r2 == 0);     for (pii to : adj[first]) {       if (to.first != p && !cent[to.first]) {         dfscalc(to.first, d + 1, add(mult(r1, 10), to.second),                 add(r2, mult(po[d], to.second)), first);       }     }   }   int phi;   void dfsget(int first, int d, int r, int p = -1) {     int inv = mult(MOD - r, binpow(po[d], phi - 1));     ans += cnt[inv];     for (pii to : adj[first]) {       if (to.first != p && !cent[to.first]) {         dfsget(to.first, d + 1, add(mult(r, 10), to.second), first);       }     }   }   void solve(int first = 0) {     calc_sz(first);     c_sz = sz[first];     first = fnd(first);     cent[first] = 1;     for (pii to : adj[first]) {       if (!cent[to.first]) {         dfsget(to.first, 1, to.second);         dfsadd(to.first, 1, to.second);         dfscalc(to.first, 1, to.second, to.second);       }     }     cnt.clear();     reverse((adj[first]).begin(), (adj[first]).end());     for (pii to : adj[first]) {       if (!cent[to.first]) {         dfsget(to.first, 1, to.second);         dfsadd(to.first, 1, to.second);       }     }     cnt.clear();     for (pii to : adj[first]) {       if (!cent[to.first]) {         solve(to.first);       }     }   }   void ma1n() {     int n;     cin >> n >> MOD;     for (int i = 1; i < n; ++i) {       int u, v, w;       cin >> u >> v >> w;       w %= MOD;       adj[u].push_back({v, w});       adj[v].push_back({u, w});     }     int first = MOD;     phi = MOD;     for (int i = 2; i <= sqrt(first); ++i) {       if (first % i == 0) {         while (first % i == 0) {           first /= i;         }         phi -= phi / i;       }     }     if (first > 1) {       phi -= phi / first;     }     po[0] = 1;     for (int i = 1; i < N; ++i) {       po[i] = mult(po[i - 1], 10);     }     solve();     cout << ans;   }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(nullptr), fin();     int ts = 1;     if (flag) {       cin >> ts;     }     while (ts--) {       ma1n();     }     return 0;   }   