题目背景

众所周知，才囚学院地下有一个街机厅，百田被星龙马打败了 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$。