Counting DFS Traversal Orders with an Extra Edge

In this problem, you are given a tree with (n) nodes and (n-1) edges. The tree is rooted at node 1. We define the DFS (depth‐first search) Euler tour of the tree by the following pseudocode:

[ \begin{array}{l} DFS\text{-}TREE(u):\ \quad p \gets p+1\ \quad t_p \gets u\ \quad vis_u \gets 1\ \quad \textbf{for each edge }(u,v)\in E \quad \textbf{(in an arbitrary order)}\ \qquad \textbf{if } vis_v = 0 \textbf{ then} \ \qquad\quad DFS\text{-}TREE(v)\ \quad p \gets p+1\ \quad t_p \gets u \end{array} ]

Initially, all variables and arrays are zero. The array (t) obtained from calling (DFS\text{-}TREE(1)) is called the traversal order of the tree. Notice that since the order in which the edges are iterated is arbitrary, the DFS traversal order is not unique. In fact, if for every node we may choose an arbitrary permutation of the edges leading to first‐time visits (i.e. the effective children), then the number of different DFS orders for a tree is

[ F_{T} = \prod_{u=1}^{n} (c(u))! \quad, \quad \text{where } c(u) = \begin{cases} \deg(u) & u=1\ \deg(u)-1 & u\neq 1 \end{cases} ]

Now, consider the twist: after the tree is given, an extra edge connecting two distinct vertices (a) and (b) (which is not already present in the tree) is added. The DFS procedure remains the same. However, now the extra edge might be used to initiate a DFS call from one endpoint if it appears before the corresponding tree edge in the arbitrary ordering. More precisely, if among (a) and (b), the vertex that is visited earlier (say (s)) in the DFS of the tree (using a fixed tie–breaking rule such as increasing order of labels) has a tree child (r) on the (unique) path towards the other endpoint, then in the DFS on the new graph the effective neighbor list at (s) becomes enlarged by one (the extra edge to (t), with (t) being the other endpoint). Hence, the number of different DFS traversal orders becomes:

[ F = F_{T} \times (c(s)+1) \mod (10^9+7), ]

where (s) is the endpoint (either (a) or (b)) with the smaller discovery time according to the DFS of the tree (performed by, say, sorting the neighbors in increasing order of their labels), and (c(s)) is the number of effective children of node (s) in the tree (i.e. (\deg(s)) if (s=1) or (\deg(s)-1) if (s \neq 1)).

Your task is to compute the number of different DFS traversal orders (i.e. Euler tours) that can be generated by the DFS procedure on the graph (tree plus extra edge), modulo (10^9+7).

Input Description:

• The first line contains an integer \(n\) (\(n \ge 2\)) denoting the number of nodes.
• Then follow \(n-1\) lines, each containing two integers \(u\) and \(v\) representing an edge of the tree.
• The last line contains two integers \(a\) and \(b\) representing the extra edge added to the tree.

Output Description:

• Output a single integer representing the number of different DFS traversal orders modulo \(10^9+7\).

Note: The tree is undirected and is rooted at node 1. When determining the discovery times in the DFS of the tree, assume that at each node the neighbors are processed in increasing order of their labels.

inputFormat

The first line contains an integer (n) ((n \ge 2)). Each of the next (n-1) lines contains two integers (u) and (v), denoting an edge of the tree. The last line contains two integers (a) and (b) representing the extra edge added to the tree.

outputFormat

Output a single integer: the number of different DFS traversal orders modulo (10^9+7).

sample

3
1 2
2 3
1 3

2