A10666 | Digit Tree

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_{1}=u,a_{2},...,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^{9}$ , ) — 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.