{"raw_statement":[{"iden":"statement","content":"Rikka has a tree $T$ with $n$ vertices numbered from $1$ to $n$.\n\nMeanwhile, Rikka has marked $m$ simple paths in $T$, the $i$-th of which is between the vertices $x_i$ and $y_i$, where some of them could be the same path.\n\nNow, Rikka wants to know in how many different strategies she can select $k$ paths from the marked paths such that those selected paths share at least one common vertex.\n\nThe input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 200$), the number of test cases.\n\nFor each test case, the first line contains three integers $n$ ($1 <= n <= 3 times 10^5$), the size of the tree $T$, $m$ ($2 <= m <= 3 times 10^5$), the number of marked paths, and $k$ ($2 <= k <= m$).\n\nThe following $(n -1)$ lines describe the tree $T$. Each of them contains two integers $u$ and $v$ ($1 <= u, v <= n$, $u != v$), representing an edge between the vertices $u$ and $v$.\n\nThe following $m$ lines describe all marked simple paths in the tree. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 <= x_i, y_i <= n$).\n\nThe input guarantees that the sum of $n$ and the sum of $m$ in all test cases are at most $2 times 10^6$ respectively.\n\nFor each test case, output a single line with a single integer, the number of different strategies meeting the requirement modulo $(10^9 + 7)$.\n\n"},{"iden":"input","content":"The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 200$), the number of test cases.For each test case, the first line contains three integers $n$ ($1 <= n <= 3 times 10^5$), the size of the tree $T$, $m$ ($2 <= m <= 3 times 10^5$), the number of marked paths, and $k$ ($2 <= k <= m$).The following $(n -1)$ lines describe the tree $T$. Each of them contains two integers $u$ and $v$ ($1 <= u, v <= n$, $u != v$), representing an edge between the vertices $u$ and $v$.The following $m$ lines describe all marked simple paths in the tree. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 <= x_i, y_i <= n$).The input guarantees that the sum of $n$ and the sum of $m$ in all test cases are at most $2 times 10^6$ respectively."},{"iden":"output","content":"For each test case, output a single line with a single integer, the number of different strategies meeting the requirement modulo $(10^9 + 7)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.  \nLet $ \\mathcal{P} = \\{P_1, P_2, \\dots, P_m\\} $ be a multiset of simple paths in $ T $, where each $ P_i $ connects vertices $ x_i $ and $ y_i $.  \nLet $ k \\in \\mathbb{Z} $, $ 2 \\leq k \\leq m $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 200 $ (number of test cases).  \n2. For each test case:  \n   - $ 1 \\leq n \\leq 3 \\times 10^5 $, $ 2 \\leq m \\leq 3 \\times 10^5 $, $ 2 \\leq k \\leq m $.  \n   - The sum of all $ n $ across test cases $ \\leq 2 \\times 10^6 $.  \n   - The sum of all $ m $ across test cases $ \\leq 2 \\times 10^6 $.  \n\n**Objective**  \nCompute the number of $ k $-subsets $ \\mathcal{S} \\subseteq \\mathcal{P} $, $ |\\mathcal{S}| = k $, such that $ \\bigcap_{P \\in \\mathcal{S}} P \\neq \\emptyset $, i.e., all paths in $ \\mathcal{S} $ share at least one common vertex.  \nOutput the result modulo $ 10^9 + 7 $.","simple_statement":"Given a tree with n nodes and m marked paths, count how many ways to choose k paths such that they all share at least one common vertex.","has_page_source":false}