func_code_string: #include <bits/stdc++.h>   using namespace std;   const long long maxN = 1e5 + 13;   long long root, sz[maxN], h[maxN], ans, val[maxN], m, n, pw[maxN], pre[maxN];   map<long long, long long> mp;   vector<long long> vec;   vector<pair<long long, long long>> adj[maxN];   bool mark[maxN], fl;   void dfs(long long v, long long p) {     sz[v] = 1;     for (auto a : adj[v]) {       long long u = a.first, w = a.second;       if (u != p && !mark[u]) {         dfs(u, v);         sz[v] += sz[u];       }     }   }   long long getpw(long long a, long long b) {     long long ret = 1;     for (; b; b >>= 1, a = 1ll * a * a % m)       if (b & 1) ret = 1ll * ret * a % m;     return ret;   }   void precomp() {     pw[0] = 1;     for (long long i = 1; i < n + 5; i++) pw[i] = pw[i - 1] * 10 % m;     long long tmp = m, tot = m;     for (long long p = 2; p * p <= tmp; p++)       if (tmp % p == 0) {         tot = tot / p * (p - 1);         while (tmp % p == 0) tmp /= p;       }     if (tmp > 1) tot = tot / tmp * (tmp - 1);     pre[0] = 1;     pre[1] = getpw(10, tot - 1);     for (long long i = 2; i < n + 5; i++) pre[i] = 1ll * pre[i - 1] * pre[1] % m;   }   void du(long long v, long long p) {     for (auto a : adj[v]) {       long long u = a.first, w = a.second;       if (u != p && !mark[u]) {         h[u] = h[v] + 1;         val[u] = ((val[v]) + w * pw[h[v]]) % m;         if (val[u] == 0) ans++;         du(u, v);       }     }   }   void dd(long long v, long long p, long long cur) {     if (v != root) vec.push_back(v);     reverse(adj[v].begin(), adj[v].end());     for (auto a : adj[v]) {       long long u = a.first, w = a.second;       if (u != p && !mark[u]) {         long long nwcur = (cur * 10 + w) % m;         long long wnt = ((1ll * pre[h[u]] * ((-nwcur) % m + m)) + m) % m;         ans += mp[wnt];         dd(u, v, nwcur);         if (nwcur == 0 && fl) ans++;         if (v == root) {           while (vec.size()) {             long long u = vec.back();             vec.pop_back();             mp[val[u]]++;           }         }       }     }   }   void calc(long long v) {     long long tmp = ans;     h[v] = 0;     val[v] = 0;     du(v, -1);     mp.clear();     fl = 0;     dd(v, -1, 0);     mp.clear();     fl = 1;     dd(v, -1, 0);   }   void solve(long long v) {     dfs(v, -1);     root = v;     long long p = -1;     bool fl = true;     while (fl) {       fl = false;       for (auto a : adj[v]) {         long long u = a.first;         if (!mark[u] && u != p && sz[u] > sz[root] / 2) {           p = v;           v = u;           fl = true;           break;         }       }     }     mark[v] = true;     root = v;     calc(v);     for (auto a : adj[v]) {       long long u = a.first;       if (!mark[u]) solve(u);     }   }   int32_t main() {     ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> m;     precomp();     for (long long i = 0; i < n - 1; i++) {       long long a, b, w;       cin >> a >> b >> w;       a++;       b++;       w %= m;       adj[a].push_back({b, w});       adj[b].push_back({a, w});     }     solve(1);     cout << ans << endl;   }   