#include <bits/stdc++.h>
using namespace std;
void desperate_optimization(int precision) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.setf(ios::showpoint);
  cout.precision(precision);
}
const int N = 1e5;
vector<pair<int, long long> > vec[N + 5];
int iscen[N + 5];
int subtree[N + 5];
long long MOD;
map<long long, long long> ml;
long long ans = 0;
long long totient = 0;
long long fast(long long A, long long B) {
  long long ans = 1;
  while (B) {
    if (B & 1) ans = ans * A % MOD;
    A = A * A % MOD;
    B /= 2;
  }
  return ans;
}
void traverse(int idx, int prev, long long val, long long mul, int add) {
  ml[val] += add;
  for (int i = 0; i < vec[idx].size(); i++) {
    int nx = vec[idx][i].first;
    long long num = vec[idx][i].second % MOD;
    if (nx == prev || iscen[nx] == 1) continue;
    traverse(nx, idx, (val + mul * num % MOD) % MOD, mul * 10 % MOD, add);
  }
}
void reverseTraverse(int idx, int prev, long long val, long long mul) {
  long long target = (MOD - val) * fast(mul, totient - 1) % MOD;
  ans += ml[target];
  for (int i = 0; i < vec[idx].size(); i++) {
    int nx = vec[idx][i].first;
    long long num = vec[idx][i].second % MOD;
    if (nx == prev || iscen[nx] == 1) continue;
    reverseTraverse(nx, idx, (val * 10 % MOD + num) % MOD, mul * 10 % MOD);
  }
}
void dfs(int idx, int prev) {
  subtree[idx] = 1;
  for (int i = 0; i < vec[idx].size(); i++) {
    int nx = vec[idx][i].first;
    if (nx == prev || iscen[nx]) continue;
    dfs(nx, idx);
    subtree[idx] += subtree[nx];
  }
}
int getCentroid(int idx, int prev, int sz) {
  int center = idx;
  for (int i = 0; i < vec[idx].size(); i++) {
    if (center != idx) break;
    int nx = vec[idx][i].first;
    if (iscen[nx] == 1 || nx == prev) continue;
    if (sz < 2 * subtree[nx]) center = nx;
  }
  if (center != idx) return getCentroid(center, idx, sz);
  return center;
}
int find(int idx) {
  dfs(idx, idx);
  return getCentroid(idx, idx, subtree[idx]);
}
int construct(int idx) {
  int center = find(idx);
  traverse(center, center, 0, 1 % MOD, 1);
  ans += ml[0];
  for (int i = 0; i < vec[center].size(); i++) {
    int nx = vec[center][i].first;
    long long num = vec[center][i].second % MOD;
    if (iscen[nx] == 1) continue;
    traverse(nx, center, num % MOD, 10 % MOD, -1);
    reverseTraverse(nx, center, num % MOD, 10 % MOD);
    traverse(nx, center, num % MOD, 10 % MOD, 1);
  }
  traverse(center, center, 0, 1 % MOD, -1);
  iscen[center] = 1;
  for (int i = 0; i < vec[center].size(); i++) {
    int nx = vec[center][i].first;
    if (iscen[nx] == 1) continue;
    int res = construct(nx);
  }
  return center;
}
int main() {
  desperate_optimization(10);
  int n;
  cin >> n >> MOD;
  totient = MOD;
  long long num = MOD;
  for (int i = 2; i * i <= n; i++) {
    if (num % i == 0) {
      totient = totient / i * (i - 1);
      while (num % i == 0) num /= i;
    }
  }
  if (num != 1) totient = totient / num * (num - 1);
  for (int i = 1; i < n; i++) {
    int u, v;
    long long c;
    cin >> u >> v >> c;
    vec[u].push_back(make_pair(v, c));
    vec[v].push_back(make_pair(u, c));
  }
  int root = construct(0);
  cout << ans - n << '\n';
  return 0;
}
