"Get Out! I Need To Go To My Mind Palace!" - Sherlock

Problem 8

A tree is a connected graph that doesn't contain any cycles. This tree is a special one with N nodes and each of the $N-1$ edges has some weight associated with it.

Distance between two vertices of the tree is the product of edge weights on the shortest path between the two vertices. Since this product might get too large, we will compute distance modulo $MOD$.

Given an integer P , you needs to find the number of unordered $(u,v)$ pairs such that distance between u and v modulo $MOD$ is equal to P.

Input:

First line of input contains 2 integer N and $MOD$, denoting the number of nodes in the tree and the modulo with which we are computing distances. Each of the next $N-1$ lines contains 3 integers X, Y and Z, meaning that there is an edge between node X and node Y of weight Z. Next line contains an integer P.

Output:

Print the answer as described in problem statement. If you count $(u,v)$ in the answer, do not count $(v,u)$.

Constraints:

$1 \le N \le 2\cdot 10^5$

$3 \le MOD \le 10^9+7$

$MOD$ is prime.

$0 \le P \le MOD-1$

$1 \le X, Y \le N$

$1 \le Z \le MOD-1$

Note:

This problem has binary scoring. You will get $100$ points if you pass all test cases.