#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
using namespace std;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
const int M = 1e9 + 7;
const int N = 2e5 + 7;
int n, m, k, x, y, w, sz[N], V, Kek, pp[N];
vector<pair<int, int> > g[N];
bool used[N];
long long ans;
int pw(int x, int n) {
  if (n < 0) return 0;
  if (n == 0) return 1ll;
  if (n % 2ll) return (1ll * x * pw(x, n - 1)) % m;
  return pw((1ll * x * x) % m, n / 2ll);
}
int rev(int x) {
  if (m == 1) return 0;
  return pw(x, Kek - 1);
}
void calc(int v, int p) {
  sz[v] = 1;
  for (auto to : g[v]) {
    if (used[to.first] || to.first == p) continue;
    calc(to.first, v);
    sz[v] += sz[to.first];
  }
  return;
}
int Find(int v, int p) {
  for (auto to : g[v]) {
    if (used[to.first] || to.first == p) continue;
    if (sz[to.first] >= k) return Find(to.first, v);
  }
  return v;
}
void solve(int v, int p, int h, int kek, int lol, unordered_map<int, int> &kol,
           map<pair<int, int>, int> &KOL) {
  int a = m - h;
  if (a >= m) a -= m;
  int b = pp[kek];
  int c = (1ll * a * b) % m;
  ans += kol[c] - KOL[{lol, c}];
  for (auto to : g[v]) {
    if (used[to.first] || to.first == p) continue;
    solve(to.first, v, (h * 10ll + to.second) % m, kek + 1, lol, kol, KOL);
  }
  return;
}
void upd(int v, int p, int h, int kek, int lol, unordered_map<int, int> &kol,
         map<pair<int, int>, int> &KOL) {
  kol[h]++;
  KOL[{lol, h}]++;
  for (auto to : g[v]) {
    if (used[to.first] || to.first == p) continue;
    upd(to.first, v, (h + 1ll * kek * to.second) % m, (kek * 10ll) % m, lol,
        kol, KOL);
  }
  return;
}
void go(int v) {
  unordered_map<int, int> kol;
  map<pair<int, int>, int> KOL;
  kol[0] = 1;
  sz[v] = 0;
  calc(v, v);
  k = sz[v] / 2;
  V = Find(v, v);
  int K = 0;
  for (auto to : g[V]) {
    if (used[to.first]) continue;
    upd(to.first, V, to.second % m, 10 % m, K++, kol, KOL);
  }
  K = 0;
  for (auto to : g[V]) {
    if (used[to.first]) continue;
    solve(to.first, V, to.second % m, 1 % m, K++, kol, KOL);
  }
  ans += kol[0] - 1;
  used[V] = 1;
  for (auto to : g[V])
    if (!used[to.first]) go(to.first);
  return;
}
int phi(int n) {
  int result = n;
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  if (n > 1) result -= result / n;
  return result;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  Kek = phi(m) - 1;
  Kek = pw(10, Kek);
  pp[1] = Kek;
  for (int i = 2; i < N / 2; i++) pp[i] = (1ll * pp[i - 1] * Kek) % m;
  for (int i = 0; i < n - 1; i++) {
    cin >> x >> y >> w;
    w %= m;
    g[x].push_back({y, w});
    g[y].push_back({x, w});
  }
  go(0);
  cout << ans;
  return 0;
}
