「dWoi R2」Arcade hall / 街机厅

众所周知，才囚学院地下有一个街机厅，~~百田被星龙马打败了 114514 次~~。 百田不服气，于是他打开了一个单人游戏 —— 先辈的城市。 --- 114514 年，火星，幺舅幺舅巴以灵国。 因为有小可爱提出题面过于冗长，所以下方有 **简要题面**。

幺舅幺舅巴以灵国一共有 $n$ 个城市，他们之间用一种神奇的通讯工具 —— 先辈符，第 $i$ 个城市的先辈符上刻有一个正整数 $w_i$。这 $n$ 个城市之前有 $n-1$ 条道路，第 $j$ 条道路连接第 $u_j$ 个城市和第 $v_j$ 个城市，有一个属性 $t_j$，这一条道路就表示为 $(u_j,v_j,t_j)$，其中 $t_j \in \{0,1,2\}$，意为： - $t_j=0$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是敌对关系； - $t_j=1$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是平等关系； - $t_j=2$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是友好关系。 每一条道路都是双向的，并且保证任意两个城市 $u,v$ 之间都是可以互相到达的。 最近火星发生了 MARS-514 病毒疫情，先辈符系统的修建要加快脚步。我们规定： - $w_i \in [1,R]$，且是一个正整数； - 对于一条道路 $(p,q,r)$，有如下要求： - 当 $r=0$ 时，即第 $p$ 个城市与第 $q$ 个城市处于敌对关系时，需要保证 $w_p \ne w_q$； - 当 $r=2$ 时，即第 $p$ 个城市与第 $q$ 个城市处于友好关系时，需要保证 $w_p=w_q$； - 当 $r=1$ 时，即第 $p$ 个城市与第 $q$ 个城市处于平等关系时，不需要保证 $w_p$ 与 $w_q$ 的大小关系。 求这样分配 $w_i$ 后，将 $w_i$ 作为一个序列，会形成多少个本质不同的序列 $w_i$。 额外地，幺舅幺舅巴以灵国的统治者浩二结节在建造先辈符发现 $w_i$ 越大，用墨就会越多，建造起来也会越困难，所以浩二结节想知道 $w_i$ 的和的最小值是多少。 注意，本题的序列 $A_i$ 与 $B_i$ 本质相同当且仅当对于所有 $i$ 都有 $A_i=B_i$。 本质不同即为不满足本质相同的两个序列。 --- **简要题面**： - 有一棵 $n$ 个点的树，第 $i$ 个点有点权 $w_i$，第 $j$ 条边有边权 $t_j$； - 每一条边 $(u_j,v_j,t_j)$ 两边点的点权有如下要求： - $t_j=0$，$w_{u_j} \ne w_{v_j}$； - $t_j=1$，没有要求； - $t_j=2$，$w_{u_j}=w_{v_j}$； - 对任意点权都要有 $w_i \in [1,R]$； - 求当 $w_i$ 作为序列时，一共有多少种本质不同的序列 $w_i$ 以及 $w_i$ 的和的最小值。

第一行两个整数 $n,R$ 代表城市数与值域。 接下来 $n-1$ 行每行三个整数 $u_j,v_j,t_j$ 描述一条道路。

一行两个整数分别代表满足要求的本质不同的序列 $w_i$ 的个数和 $w_i$ 的和的最小值。 如果不存在本质不同的序列（即第一问答案为 $0$），第二问也请输出一个 $0$。 **只有第一问答案对 $10^9+7$ 取模。**

3 3
1 2 0
1 3 0

12 4

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

648 12

#### 样例 1 解释 样例中的道路分布如下：  一共有 $12$ 种赋值方式： 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\}$，这是最优情况； 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\}$。 #### 样例 2 解释 样例中的道路分布如下：  对于第二问，其中一种最优的赋值方式是：$w_i=\{2,1,1,1,1,1,2,1,2\}$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$t_j=1$ 或 $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）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le R \le 100$。 对于 Subtask 1 ~ 5，$R \le 40$。 上面描述 Subtask 时 $t_j=P$ 即为对于所有 $j \in [1,n)$ 都有 $t_j=P$。 其中对于 Subtask 1，“或” 意为 Subtask 1 的一部分测试点满足 $t_j=1$，另一部分测试点满足 $t_j=2$。