{"raw_statement":[{"iden":"background","content":"小 L 很喜欢树，很喜欢 $ \\operatorname{LCA} $，很喜欢有序元组，于是有了这样一道题。"},{"iden":"statement","content":"对于一棵 $ n $ 点有根树（根为 $ 1 $），定义有序 $ p $ 元组 $ (a_1,a_2,......,a_p) $ 为 $ k $ 级 $ \\operatorname{LCA} $ $ p $ 元组当且仅当：\n\n* $ 1 \\le a_1<a_2<......<a_p \\le n $\n\n* 存在 $ x $ 使得对于任意有序严格递增 $ k $ 元组 $ b \\subseteq a $ 均满足 $ \\operatorname{LCA}_{i=1}^{k}\\{b_i\\} = x $。\n\n注意，$ \\operatorname{LCA}(x,y) $ 指树上 $ x $ 点和 $ y $ 点的最近公共祖先，且 $ \\operatorname{LCA}_{i=1}^{k}\\{b_i\\} $ 指的是所有的 $ b_i $ 的 $ \\operatorname{LCA} $。\n\n求出 $ k $ 级 $ \\operatorname{LCA} $ $ p $ 元组的个数，对 $ 10^9+7 $ 取模。"},{"iden":"input","content":"第一行一个整数 $ n,p,k $。\n\n接下来 $ n-1 $ 行，每行两个整数代表一条边的两个端点的编号。"},{"iden":"output","content":"输出一个整数代表要求的答案。"},{"iden":"note","content":"**【样例 1 解释】**\n\n对于样例 $ 1 $，我们发现符合要求的 $ 4 $ 元组只有 $ (3,4,5,6) $。\n\n**【数据规模与约定】**\n\n对于 $ 100\\% $ 的数据，$ 2 \\le n \\le 5000 $，$ 2 \\le k \\le p \\le n $。\n\n**提示：本题开启捆绑测试。**\n\n* Subtask 1（10 pts）：$ n \\le 10 $。\n* Subtask 2（20 pts）：$ n \\le 20 $。\n* Subtask 3（30 pts）：$ n \\le 500 $。\n* Subtask 4（10 pts）：$ 1 $ 和所有点存在直接连边。\n* Subtask 5（30 pts）：无特殊限制。\n\n**【贡献名单】**\n\ndata&check：EstasTonne。（主题库里这个题下一个题号的出题人）"}],"translated_statement":null,"sample_group":[["6 4 3\n1 2\n2 3\n3 4\n3 5\n3 6","1"],["6 3 2\n1 2\n1 3\n1 4\n1 5\n1 6","20"],["6 4 2\n1 2\n1 3\n2 4\n2 5\n3 6","0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}