In Byteland there are N cities, numbered 1 through N. Some pairs of cities are connected by bi-directional roads in such a way that starting from any one city you can visit all other cities either directly or indirectly.

Chef is currently at city A and wants to visit all other cities in Byteland. Chef can only move according to following rule. 

If Chef is at city A then he continues to move from city A to city B, city B to city C (provided A is directly connected to B, B is directly connected to C) and so on unless there are no more cities leading from current city.

If so he jumps back to previous city and repeat the same tour with other cities leading from it which are not visited. Chef repeat this step unless all cities are not visited.

Help Chef to count number of ways in which he can visit all other cities . As this number can be large print it modulo 109+7

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of cities in Byteland.
-  Next N-1 lines contain two space-separated integers u and v denoting there is bi-directional road between city numbered u and v. 
-  Next line contains a single integer A denoting the city number where Chef is present.

-----Output-----
- For each test case, output a single line containing number of ways in which Chef can visit all cities modulo 109+7.

-----Constraints-----
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 105
- 1 ≤ A ≤ N

-----Subtasks-----
Subtask #1 : (10 points) 
- 1 ≤ N ≤ 5
Subtask #2 : (30 points) 
- 1 ≤ N ≤ 100
Subtask #3 : (60 points) 
- 1 ≤ N ≤ 105

-----Example-----
Input:
2
3
1 2
1 3
1
5
1 2
1 3
2 4
2 5
1

Output:
2
4

-----Explanation-----
Example case 1. Chef can visit cities in two ways according to the problem: 1-2-3 and 1-3-2
Example case 1. Chef can visit cities in four ways according to the problem:

1-2-4-5-3
1-2-5-4-3
1-3-2-4-5
1-3-2-5-4

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nsys.setrecursionlimit(10**8)\n\nMOD = 10**9+7\n\nfac = [0]*(10**5+1)\ndef pre() :\n fac[0] = 1\n for i in range(1,10**5+1) :\n  fac[i] = fac[i-1]*i\n  fac[i] = fac[i]%MOD\n\ndef dfs(gp , vertex , visited , deg , ans) :\n visited[vertex] = 1\n stack = []\n stack.append(vertex)\n while len(stack)>0 :\n  vertex = stack.pop()\n  ans = ans%MOD * fac[deg[vertex]]%MOD\n  ans %= MOD\n  for i in gp[vertex] :\n   if not visited[i] :\n    visited[i] = 1\n    if vertex in gp[i] :\n     deg[i] -= 1\n    stack.append(i)\n return ans%MOD\n\npre()\nfor __ in range(eval(input())) :\n n = eval(input())\n deg = [0]*(n+1)\n st = [[] for __ in range(n+1)]\n for _ in range(n-1) :\n  a , b = list(map(int,sys.stdin.readline().split()))\n  st[a].append(b)\n  st[b].append(a)\n  deg[a] += 1\n  deg[b] += 1\n k = eval(input())\n visited = [0]*(n+1)\n print(dfs(st ,k,visited,deg , 1)%MOD)\n  \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 4019753