该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

大内密探，负责秘密保护皇上，还有保护皇宫内外一切产业。——大内密探零零七

描述

在古老的皇宫中，有N个房间以及N-1条双向通道，每条通道连接着两个不同的房间，所有的房间都能互相到达。皇宫中有许多的宝物，所以需要若干个大内密探来守护。一个房间被守护当切仅当该房间内有一名大内密探或者与该房间直接相邻的房间内有大内密探。

现在身为大内密探零零七的你想知道要把整个皇宫守护好至少需要多少名大内密探以及有多少种安排密探的方案。两种方案不同当且仅当某个房间在一种方案有密探而在另一个方案内没有密探。

格式

输入格式

第一行一个正整数N.(1<=N<=100000)
后面N-1行，每行两个正整数a和b,表示房间a和房间b之间有一条无向通道。

房间的编号从1到N

输出格式

第一行输出正整数K，表示最少安排的大内密探。

第二行输出整数S,表示有多少种方案安排最少的密探，由于结果可能较大，请输出方案数mod 1000000007的余数。

样例1

样例输入1

7
2 1
3 1
4 2
5 1
6 2
7 6

样例输出1

3
4

限制

每个测试点1s

提示

30%保证:n <= 10
70%保证:n <= 1000
100%保证:n <= 100000