Background

A phoenix that is not beautiful at all.

Those sharp claws are stained with the innocent blood.

Problem Description

You are given a pair sequence $\{(v_i,c_i)\}$ and a rooted tree with root $1$. The weight of node $i$ is $(v_i,c_i)$.

• Define the value of a non-root node as the product of all $c$ in its subtree times the product of all $v$ outside its subtree.
• Define the value of the root node as the product of all $c$ in its subtree.

Formally, if $u$ is not the root, then the value $f_u$ of $u$ is:

$$f_u=\prod\limits_{v\in \operatorname{substree}(u)} c_v\times \prod\limits_{v\notin \operatorname{substree}(u)} v_v$$

Otherwise, its value $f_u$ is:

$$f_u=\prod\limits_{v=1}^n c_v$$

Find the sum of the values of all nodes in the whole tree, and output the answer modulo $m$. Note: it is guaranteed that $\bm m$ is a prime.

Input Format

The first line contains two positive integers $n,m$.

The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between $u$ and $v$.

The next line contains $n$ integers, representing $c_{1, 2, \dots, n}$.

The next line contains $n$ integers, representing $v_{1, 2, \dots, n}$.

Output Format

Output one integer, representing the result of the answer modulo $m$.

3 998244853
1 2
1 3
2 1 2
1 2 2

10

5 998244353
1 2
1 3
1 4
4 5
5 5 5 2 3
6 6 1 5 3

4656

Hint

Sample Explanation

(The image is incorrect. The weights $v,c$ should be swapped.)

Constraints and Notes

For $100\%$ of the testdata, $1\le n\leq 3\times 10^5$, $1\leq v_i,c_i,m\leq 10^9$.

Translated by ChatGPT 5