P7846 “dWoi R2” Arcade hall / Arcade Hall.

As everyone knows, there is an arcade hall under Caiqiu Academy, ~~and Baitian was defeated by Xinglongma 114514 times~~. Baitian was not convinced, so he opened a single-player game — City of the Senpai. --- In the year 114514, on Mars, in the country of Yaoyao-Yaoyao-Ba-Yiling. Since someone said the statement is too long, a **brief statement** is provided below.

The country of Yaoyao-Yaoyao-Ba-Yiling has $n$ cities. They are connected by a magical communication tool — the “Senpai Talisman”. The Senpai Talisman of the $i$-th city is engraved with a positive integer $w_i$. There are $n-1$ roads among these $n$ cities. The $j$-th road connects city $u_j$ and city $v_j$, and has an attribute $t_j$. This road is denoted as $(u_j,v_j,t_j)$, where $t_j \in \{0,1,2\}$, meaning: - When $t_j=0$, city $u_j$ and city $v_j$ are in an antagonistic relationship. - When $t_j=1$, city $u_j$ and city $v_j$ are in an equal relationship. - When $t_j=2$, city $u_j$ and city $v_j$ are in a friendly relationship. Each road is bidirectional, and it is guaranteed that any two cities $u,v$ are mutually reachable. Recently, Mars has suffered from the MARS-514 virus outbreak, so the construction of the Senpai Talisman system must be accelerated. We define: - $w_i \in [1,R]$, and $w_i$ is a positive integer. - For a road $(p,q,r)$, the following requirements must be satisfied: - When $r=0$, i.e., city $p$ and city $q$ are antagonistic, it must hold that $w_p \ne w_q$. - When $r=2$, i.e., city $p$ and city $q$ are friendly, it must hold that $w_p=w_q$. - When $r=1$, i.e., city $p$ and city $q$ are equal, there is no requirement on the relationship between $w_p$ and $w_q$. After assigning values to $w_i$, treat $w_i$ as a sequence. Determine how many essentially different sequences $w_i$ can be formed. In addition, the ruler of Yaoyao-Yaoyao-Ba-Yiling, Haoer Jiejie, found that the larger $w_i$ is, the more ink is needed, and the harder it is to build. Therefore, Haoer Jiejie wants to know the minimum possible value of the sum of $w_i$. Note that, in this problem, sequences $A_i$ and $B_i$ are essentially the same if and only if for all $i$, $A_i=B_i$. “Essentially different” means two sequences that are not essentially the same. --- **Brief statement**: - There is a tree with $n$ nodes. Node $i$ has a node weight $w_i$, and edge $j$ has an edge weight $t_j$. - For each edge $(u_j,v_j,t_j)$, the endpoint node weights must satisfy: - $t_j=0$, $w_{u_j} \ne w_{v_j}$. - $t_j=1$, no requirement. - $t_j=2$, $w_{u_j}=w_{v_j}$. - For any node weight, $w_i \in [1,R]$. - When $w_i$ is treated as a sequence, find (1) the number of essentially different sequences $w_i$, and (2) the minimum possible sum of $w_i$.

The first line contains two integers $n,R$, representing the number of cities and the value range. The next $n-1$ lines each contain three integers $u_j,v_j,t_j$, describing a road.

Output one line with two integers: the number of essentially different sequences $w_i$ that satisfy the requirements, and the minimum possible sum of $w_i$. If there is no essentially different sequence (i.e., the answer to the first question is $0$), then output $0$ for the second question as well. **Only the first answer is taken modulo $10^9+7$.**

#### Explanation for Sample 1 The roads in the sample are distributed as follows:  There are $12$ assignment methods in total: 1. $w_i=\{1,2,2\}$. 2. $w_i=\{1,2,3\}$. 3. $w_i=\{1,3,2\}$. 4. $w_i=\{1,3,3\}$. 5. $w_i= \bf \{2,1,1\}$, this is the optimal case. 6. $w_i=\{2,1,3\}$. 7. $w_i=\{2,3,1\}$. 8. $w_i=\{2,3,3\}$. 9. $w_i=\{3,1,1\}$. 10. $w_i=\{3,1,2\}$. 11. $w_i=\{3,2,1\}$. 12. $w_i=\{3,2,2\}$. #### Explanation for Sample 2 The roads in the sample are distributed as follows:  For the second question, one optimal assignment is: $w_i=\{2,1,1,1,1,1,2,1,2\}$. #### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (5 pts): $t_j=1$ or $t_j=2$. - Subtask 2 (5 pts): $R=1$. - Subtask 3 (10 pts): $u_j=j$, $v_j=j+1$. - Subtask 4 (20 pts): $t_j=0$. - Subtask 5 (10 pts): $n \le 10$, $R \le 5$. - Subtask 6 (50 pts): no special constraints. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le R \le 100$. For Subtask 1 ~ 5, $R \le 40$. In the subtask descriptions above, $t_j=P$ means that for all $j \in [1,n)$, $t_j=P$. For Subtask 1, “or” means that part of the test points in Subtask 1 satisfy $t_j=1$, and the other part satisfy $t_j=2$. Translated by ChatGPT 5