{"problem":{"name":"Ribbons on Tree","description":{"content":"Let $N$ be an even number. There is a tree with $N$ vertices. The vertices are numbered $1, 2, ..., N$. For each $i$ ($1 \\leq i \\leq N - 1$), the $i$\\-th edge connects Vertex $x_i$ and $y_i$. Snuke wo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc101_c"},"statements":[{"statement_type":"Markdown","content":"Let $N$ be an even number.\nThere is a tree with $N$ vertices. The vertices are numbered $1, 2, ..., N$. For each $i$ ($1 \\leq i \\leq N - 1$), the $i$\\-th edge connects Vertex $x_i$ and $y_i$.\nSnuke would like to decorate the tree with ribbons, as follows.\nFirst, he will divide the $N$ vertices into $N / 2$ pairs. Here, each vertex must belong to exactly one pair. Then, for each pair $(u, v)$, put a ribbon through all the edges contained in the shortest path between $u$ and $v$.\nSnuke is trying to divide the vertices into pairs so that the following condition is satisfied: \"for every edge, there is at least one ribbon going through it.\" How many ways are there to divide the vertices into pairs, satisfying this condition? Find the count modulo $10^9 + 7$. Here, two ways to divide the vertices into pairs are considered different when there is a pair that is contained in one of the two ways but not in the other.\n\n## Constraints\n\n*   $N$ is an even number.\n*   $2 \\leq N \\leq 5000$\n*   $1 \\leq x_i, y_i \\leq N$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$:$\n$x_{N - 1}$ $y_{N - 1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc101_c","tags":[],"sample_group":[["4\n1 2\n2 3\n3 4","2\n\nThere are three possible ways to divide the vertices into pairs, as shown below, and two satisfy the condition: the middle one and the right one.\n![image](https://img.atcoder.jp/arc101/2d7584d2e0736f746aa9d54e1bf31e28.png)"],["4\n1 2\n1 3\n1 4","3\n\nThere are three possible ways to divide the vertices into pairs, as shown below, and all of them satisfy the condition.\n![image](https://img.atcoder.jp/arc101/2de530ed2e64d0161ee6b989d1946261.png)"],["6\n1 2\n1 3\n3 4\n1 5\n5 6","10"],["10\n8 5\n10 8\n6 5\n1 5\n4 8\n2 10\n3 6\n9 2\n1 7","672"]],"created_at":"2026-03-03 11:01:13"}}