Tree Transformation

A tree is a connected graph with $n$ vertices and $n-1$ edges. Suchan is absorbed in growing trees and watching them. Watching them one day as usual, he happened to notice that a tree whose vertex count is a power of $2$, that is $2^0, 2^1, 2^2, \dots$, never reacts to any other tree and never moves. Suchan defined such a tree to be in a stable state.

A tree with 6 vertices is not in a stable state, and a tree with 4 vertices is in a stable state.

Suchan shared this with his fellow scientist Jihak. After reading Suchan's research notes, Jihak said, "Doesn't every tree change toward a stable state?" Suchan thought Jihak had a point, and several experiments confirmed the guess. The property he found is this. A tree that is not in a stable state cuts its own edges, splits itself suitably into several trees so that the vertex count of each tree is a power of $2$, and thereby puts itself into a stable state. Suchan shared the property with Jihak. Jihak, analyzing the experimental data, learned that cutting an edge takes energy, and found one more property: the tree splits in the way that minimizes the number of edges cut while it turns stable.

One example of a tree with 6 vertices turning stable.

The two of them decide to count the number of different ways a tree splits while obeying both properties, so that they can see exactly how a tree splits. Two ways of splitting are different when the sets of cut edges are different. The order in which the edges are cut does not matter.

Given a tree with $n$ vertices, write a program that computes the number of different ways it splits while obeying both properties.

The first line contains the number of vertices $n$ of the tree ($2 \le n \le 4095$). Each vertex carries one number from $1$ to $n$.

Each of the next $n-1$ lines describes one edge of the tree. A line contains the two vertex numbers $u$ and $v$ that the edge joins, separated by a space ($1 \le u, v \le n$, $u \ne v$).

The given graph is always a tree.

Print the number of ways the tree splits while obeying both properties, modulo $10^9 + 7$.

The tree of the first example is drawn below.

Cutting two edges splits it into a tree with $4 = 2^2$ vertices, a tree with $2 = 2^1$ vertices and a tree with $1 = 2^0$ vertex, and there are the six ways below. A solid line is an edge that stays, a dotted line is an edge that is cut.

The tree of the second example is drawn below.

Here three cut edges make the tree stable. The results fall into two groups by the vertex counts of the parts.

• Splitting into two trees with $4 = 2^2$ vertices, one tree with $2 = 2^1$ vertices and one tree with $1 = 2^0$ vertex:

  • In every possible way, the edge joining vertex 6 and vertex 9 and the edge joining vertex 6 and vertex 3 are cut. That fixes one tree with 4 vertices and one tree with 2 vertices.
  • Cutting one of the edges that join vertex 3 to vertices 2, 5, 7 and 11 fixes one more tree with 4 vertices and one more tree with 1 vertex.
  • So this group has 4 cases.

An example of splitting into four trees with 4, 4, 2 and 1 vertices

• Splitting into one tree with $8 = 2^3$ vertices and three trees with $1 = 2^0$ vertex:

  • Pick three leaves (vertices joined by exactly one edge) and cut the three edges attached to them.
  • There are 8 leaves, so this group has $\binom{8}{3} = 56$ cases.

An example of splitting into four trees with 8, 1, 1 and 1 vertices

The total number of ways is therefore 60.