You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在北辰学校鲜花大道的尽头, 有几个小花园, 各个花园之间有一些小路连通, 小北打算游览全部花园, 并带去她的歌声.

题目描述

一共有 $n$ 个小花园, 这些花园的连通性可以看作是一棵树,

小北打算选中一所花园为起点开始游览花园, 如果某一个花园是第一次到达, 她将会唱一首歌.

她只可以从游览过的花园向与之相连的花园游览, 现在我们想知道, 她一共有多少种不同的唱歌序列方案.

结果可能很大, 对 1000000007 取模.

数据格式

输入格式

第 $1$ 行有一个整数$n$, 表示有 $n$ 座花园.

接下来 $n-1$ 行, 每行两个整数 $x_i, y_i$ , 表示 $x_i$ 与 $y_i$ 相邻.

最后一行 $1$ 个整数 $s$ , 表示小北游览的起点.

Output

一个整数, 表示不同位置唱歌序列的方案数

Samples

5
1 2
2 3
3 4
3 5
2

8

样例解释

从 $2$ 点出发, 共有 $8$ 种唱歌序列

$2 \rightarrow 1\rightarrow3\rightarrow4\rightarrow5$

$2\rightarrow1\rightarrow3\rightarrow5\rightarrow4$

$2\rightarrow3\rightarrow1\rightarrow4\rightarrow5$

$2\rightarrow3\rightarrow1\rightarrow5\rightarrow4$

$2\rightarrow3\rightarrow4\rightarrow1\rightarrow5$

$2\rightarrow3\rightarrow5\rightarrow1\rightarrow4$

$2\rightarrow3\rightarrow4\rightarrow5\rightarrow1$

$2\rightarrow3\rightarrow5\rightarrow4\rightarrow1$

数据范围

$2 <= n <= 2*10^5$

$2 <= x_i, y_i <= n$

$1<=s<=n$