Oriented Tree

AtCoder

IDmujin_pc_2017_d

Time2000ms

Memory256MB

Difficulty—

There is a tree $T$ with $N$ vertices, numbered $1$ through $N$. For each $1 ≤ i ≤ N - 1$, the $i$\-th edge connects vertices $a_i$ and $b_i$. Snuke is constructing a directed graph $T'$ by arbitrarily assigning direction to each edge in $T$. (There are $2^{N - 1}$ different ways to construct $T'$.) For a fixed $T'$, we will define $d(s,\ t)$ for each $1 ≤ s,\ t ≤ N$, as follows: * $d(s,\ t) = $ (The number of edges that must be traversed against the assigned direction when traveling from vertex $s$ to vertex $t$) In particular, $d(s,\ s) = 0$ for each $1 ≤ s ≤ N$. Also note that, in general, $d(s,\ t) ≠ d(t,\ s)$. We will further define $D$ as the following: ![image](https://atcoder.jp/img/mujin/3d2f3f88e8fa23f065c04cd175c14ebf.png) Snuke is constructing $T'$ so that $D$ will be the minimum possible value. How many different ways are there to construct $T'$ so that $D$ will be the minimum possible value, modulo $10^9 + 7$? ## Constraints * $2 ≤ N ≤ 1000$ * $1 ≤ a_i,\ b_i ≤ N$ * The given graph is a tree. ## Input The input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_{N - 1}$ $b_{N - 1}$ [samples]

Samples

Input #1

Output #1

2

The minimum possible value for $D$ is $1$. There are two ways to construct $T'$ to achieve this value, as shown in the following figure:
![image](https://atcoder.jp/img/mujin/de49901ddf69d8565fde5b6870afb595.png)

Input #2

Output #2

6

The minimum possible value for $D$ is $2$. There are six ways to construct $T'$ to achieve this value, as shown in the following figure:
![image](https://atcoder.jp/img/mujin/dcb377e8c7fe15d6dd0cb815dc57c41a.png)

Input #3

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Oriented Tree",
    "description": {
      "content": "There is a tree $T$ with $N$ vertices, numbered $1$ through $N$. For each $1 ≤ i ≤ N - 1$, the $i$\\-th edge connects vertices $a_i$ and $b_i$. Snuke is constructing a directed graph $T'$ by arbitraril",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "mujin_pc_2017_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a tree $T$ with $N$ vertices, numbered $1$ through $N$. For each $1 ≤ i ≤ N - 1$, the $i$\\-th edge connects vertices $a_i$ and $b_i$.\nSnuke is constructing a directed graph $T'$ by arbitraril...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments