题目描述

无聊的 \(\text{Smart}\) 对把树分块这个操作感到十分好奇。他想，假如能把一棵树分成几块，使得每个块中的点数都相同该有多优美啊！\(\text{Smart}\) 很想知道，能有几种分割方法使得一棵树变得优美。

\(\text{Smart}\) 每次会画出一棵树，但由于手速太快，有时候他画出来的树会异常地庞大，令他感到十分的苦恼。但是 \(\text{Smart}\) 实在是太想知道答案了，于是他找到了你，一个天才的程序员，来帮助他完成这件事。

格式

输入格式

第一行一个正整数\(N\)，表示这棵树的结点总数。

接下来 \(N-1\) 行，每行两个数字 \(x,y\)，表示编号为 \(x\) 的结点与编号为 \(y\) 的结点相连。结点编号的范围为 \(1 \sim N\) 且编号两两不同。

输出格式

一行一个整数 \(Ans\)，表示所求的方案数。

样例1

样例输入1

6
1 2
2 3
2 4
4 5
5 6

样例输出1

3

样例解释

有三种方案：

1. 分成 \(1\) 个块，块中节点个数为 \(6\)；
2. 分成 \(2\) 个块，块中节点个数为 \(3\)，分别为块 \(1,2,3\) 和块 \(4,5,6\)；
3. 分成 \(6\) 个块，每个块中有 \(1\) 个节点。

限制

\(30\%\)的数据：\(N≤100\)。

\(100\%\)的数据：\(N≤10^6\)。

提示

输入数据较大，尽量使用下面的快速读入。

inline int read(int &x)//快速读入
{char ch=getchar();
int f=1;x=0;
while (ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}