Sum of Weighted Node Values in a Tree

You are given a tree with n nodes (numbered from 1 to n) and a prime modulus m. The tree is rooted at node 1. Each node i is assigned a pair of integers \( (v_i, c_i) \).

For each node, we define its weight \( f_u \) as follows:

• If u is the root (i.e. node 1), then \[ f_1 = \prod_{i=1}^{n} c_i. \]
• If u is not the root, let \(\operatorname{subtree}(u)\) be the set of nodes in the subtree of u (including u itself). Then, \[ f_u = \left(\prod_{w \in \operatorname{subtree}(u)} c_w\right) \times \left(\prod_{w \notin \operatorname{subtree}(u)} v_w\right). \]

Your task is to compute the sum of the weights of all nodes in the tree modulo m.

Note: All products and the final answer are to be calculated modulo \(m\), and it is guaranteed that \(m\) is a prime number.

inputFormat

The input is given as follows:

1. The first line contains two integers n and m, where n (\(1 \le n \le 10^5\) or so) is the number of nodes and m is a prime modulus.
2. The second line contains n integers: \(v_1, v_2, \dots, v_n\).
3. The third line contains n integers: \(c_1, c_2, \dots, c_n\).
4. The following n-1 lines each contain two integers u and v indicating that there is an undirected edge between nodes u and v. The given tree is guaranteed to be connected and rooted at node 1.

outputFormat

Output a single integer: the sum of the weights of all nodes in the tree modulo m.

sample

3 7
1 2 3
4 5 6
1 2
1 3

0