ZS the Coder has a large tree. It can be represented as an undirected connected graph of n vertices numbered from 0 to n-1 and n-1 edges between them. There is a single nonzero digit written on each edge.

One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer M, which is coprime to 10, i.e. .

ZS consider an ordered pair of distinct vertices (u,v) interesting when if he would follow the shortest path from vertex u to vertex v and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by M.

Formally, ZS consider an ordered pair of distinct vertices (u,v) interesting if the following states true:

• Let a₁=u,a₂,...,a_k=v be the sequence of vertices on the shortest path from u to v in the order of encountering them;
• Let d_i (1≤i<k) be the digit written on the edge between vertices a_i and a_i+1;
• The integer is divisible by M.

Help ZS the Coder find the number of interesting pairs!

The first line of the input contains two integers, n and M (2≤n≤100000,1≤M≤10⁹, )− the number of vertices and the number ZS has chosen respectively.

The next n-1 lines contain three integers each. i-th of them contains u_i,v_i and w_i, denoting an edge between vertices u_i and v_i with digit w_i written on it (0≤u_i,v_i<n,1≤w_i≤9).

Print a single integer− the number of interesting (by ZS the Coder's consideration) pairs.