Mingi, having solved too many tree problems, has grown tired of standard ones. Therefore, he wants to transform the shape of a tree in a unique way and play a game with Minchan using it. The graph Mingi creates is a Pi-Tree, which is formed by adding a semicircle or a circle to every edge of a standard tree. That is, every edge will have one of the shapes shown in the figures below. The center of the semicircle or circle is the midpoint of the edge, and the position of the semicircle (above or below the edge) does not matter.

In the initial state, a piece is placed on the root node of the tree. Mingi and Minchan take turns moving this piece to an adjacent node. The game starts with Mingi, an edge cannot be traversed more than once, and the player who cannot move the piece on their turn loses. Mingi wants to prepare a Pi-Tree where he wins the game. In this process, the intersection points between the circle or semicircle and the original tree edge are also treated as nodes. The diameters of the semicircles and circles drawn by Mingi are shorter than the length of the edges, and they do not overlap with semicircles or circles drawn on other edges. Help Mingi by calculating the number of Pi-Trees out of the total $2^{(N-1)}$ possible configurations such that Mingi always wins the game, assuming both Mingi and Minchan play optimally. Output the count modulo $1,000,000,007$ $(=10^9+7)$.

Input

The first line contains the number of nodes $N$ and the index of the root node, separated by a space. From the second line to the $N$-th line, the indices of the two nodes $a_i$ and $b_i$ connected by each edge are given. $(1 \le i < N)$ $1 \le N \le 100,000$

Output

Output the number of Pi-Trees where Mingi wins the game, modulo $1,000,000,007$.

Examples

Input 1

4 1
1 2
2 3
2 4

Output 1

4

Input 2

16 1
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12
7 13
7 14
8 15
8 16

Output 2

18688