ZS the Coder có một cây lớn và được biểu diễn dưới dạng đồ thị vô hướng liên thông của ~n~ đỉnh được đánh số từ ~0~ đến ~n - 1~ và ~n - 1~ cạnh nối giữa chúng. Trên mỗi cạnh có một chữ số khác không.

Một ngày nọ, ZS the Coder cảm thấy chán chường và quyết định điều tra một số tính chất của cây. Anh ấy chọn một số nguyên dương ~M~, sao cho ~M~ là số nguyên tố cùng nhau với ~10~, tức là ~GCD(M, 10) = 1~.

ZS xem một cặp đỉnh có thứ tự (~u, v~) là thú vị khi nếu anh ấy đi theo đường đi ngắn nhất từ đỉnh ~u~ đến đỉnh ~v~ và viết tất cả các chữ số mà anh ấy gặp trên con đường của mình theo thứ tự, anh ấy sẽ được một biểu diễn thập phân của một số nguyên chia hết cho ~M~.

Cụ thể, ZS xem một cặp đỉnh có thứ tự (~u, v~) là thú vị nếu các điều kiện sau đúng:

• Gọi ~a_1 = u, a_2, ..., a_k = v~ là chuỗi các đỉnh trên đường đi ngắn nhất theo thứ tự từ ~u~ đến ~v~;

• Gọi ~d_i~ (~1 \leq i < k~) là chữ số được viết trên cạnh giữa các đỉnh ~a_i~ và ~a_{i + 1}~;

• Số nguyên dương ~\overline{d_1 d_2 d_3 ... d_{k-1}} = \sum_{i=1}^{k-1}d_i \cdot 10^{k-1-i}~ chia hết cho ~M~.

Hãy giúp ZS the Coder tìm số lượng cặp đỉnh thú vị!

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~M~ (~2 \leq n \leq 100000, 1 \leq M \leq 10^9, gcd(M, 10) = 1~) — số đỉnh và số mà ZS đã chọn.

Trong ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên ~u_i, v_i, w_i~ biểu diễn một cạnh nối đỉnh ~u_i~ và ~v_i~ với chữ số ~w_i~ viết trên đó(~0 \leq u_i, v_i \leq n, 1 \leq w_i \leq 9~).

Output

Ghi ra một số nguyên duy nhất là số lượng cặp đỉnh thú vị.

Scoring

Sample Input 1

6 7
0 1 2
4 2 4
2 0 1
3 0 9
2 5 7

Sample Output 1

7

Sample Input 2

5 11
1 2 3
2 0 3
3 0 3
4 3 3

Sample Output 2

8