为了方便客户，旅游代理商“42 best journeys”选择了 $N$ 个城市，这些城市由 $N-1$ 条直飞航线连接，且任意两个城市之间都可以通过航空（直飞或经停）到达。为了推广其服务，代理商选择了情境广告。为了避免令人厌烦的重复广告，提供商只向客户展示独特的旅游路线。旅游路线包含访问 $K$ ($K \le N$) 个城市，这些城市由 $K-1$ 条直飞航线连接，且任意两个城市之间都可以通过航空到达。如果两个旅游路线中一个包含某个特定城市而另一个不包含，则认为这两个旅游路线是独特的。

代理商负责人制定了广告策略并开始考虑其费用。情境广告提供商对每条广告收取 1 美元，并对旅游路线中包含的每个城市收取 1 白俄罗斯卢布。会计团队现在需要计算最终需要支付的金额。在此次活动中，所有可能的独特旅游路线（广告）都已向客户展示过恰好一次。

输入格式

第一行包含一个整数 $N$ —— 所选城市的数量。接下来的 $N-1$ 行，每行包含两个整数 $U_i$ 和 $V_i$ —— 由直飞航线连接的城市索引。

$1 \le N \le 10^5$ $1 \le U_i, V_i \le N$

输出格式

单行输出两个整数 —— 代理商需要支付的美元金额和白俄罗斯卢布金额。作为其折扣政策的一部分，情境广告提供商按模 $10^9 + 7$ 计算代理商的账单金额。

样例

输入 1

5
4 2
2 5
3 2
5 1

输出 1

17 42