Digital Tree
Nazik has a large tree, which can be represented as an undirected connected graph with vertices, numbered from to , and edges. Each edge has a non-zero digit written on it.
Max, Nazik's friend, is particularly interested in special paths within this tree. Max's favorite number is , which is coprime with , meaning .
Max and Nazik define an ordered pair of different vertices as special if, when traversing the shortest path from vertex to vertex , the sequence of digits encountered forms a decimal number divisible by .
Formally, an ordered pair of different vertices is special if:
Let be the sequence of vertices on the shortest path from to ;
Let () be the digit on the edge between vertices and ;
The integer , which equals , is divisible by .
Your task is to help them find the number of special pairs.
Input Format
The first line contains two integers and (, , ) — the number of vertices and Max's favorite number.
The next lines each contain three integers. The -th line contains , , and , indicating an edge between vertices and , with the digit (, ) written on it.
Output Format
Output a single integer — the number of special pairs.
Examples
Note
In the first example, the special pairs are (1, 5), (2, 3), (2, 6), (4, 3), (3, 6), (6, 3), (4, 6).
The numbers formed by these pairs are 14, 21, 217, 91, 7, 7, 917 respectively, all divisible by 7. Note that (3, 6) and (6, 3) are considered different pairs.
In the second example, the special pairs are (5, 1), (1, 5), (4, 3), (3, 4), (1, 2), (2, 1), (5, 2), (2, 5), with 6 pairs yielding the number 33 and 2 pairs yielding the number 3333, all divisible by 11.