世界树

题目描述

世界树是一棵有 $n$ 个枢纽的树，每个枢纽闪烁着某种颜色，颜色用 $1$ 到 $m$ 之间的数字表示。

这 $m$ 种颜色可归为三种类型：

• $a$ 种颜色为 A 类型
• $b$ 种颜色为 B 类型
• $c$ 种颜色为 C 类型 其中 $a + b + c = m$，每种颜色只属于 A、B、C 中的一种。

题目给出以下相邻约束：

• A 类型枢纽的相邻枢纽不能是 C 类型
• B 类型枢纽的相邻枢纽不能是 B 类型
• C 类型枢纽的相邻枢纽不能是 A 类型

此外，A、C 类型枢纽之间必须隔一个 B 类型枢纽（即 A 和 C 不能直接相邻）。B 类型枢纽被称为过渡类型，会消耗大量能量，因此其数量不能超过 $k$。

在给定树形结构不变的情况下，求满足上述条件的枢纽颜色分布方案数。两种颜色分布不同，当且仅当存在枢纽在两种分布中的颜色不同。

答案对 $10^9+7$ 取模。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

1. 第一行五个整数 $n, k, a, b, c$。
2. 接下来 $n-1$ 行，每行两个正整数 $u, v$，表示树中的一条边，枢纽编号从 $1$ 到 $n$。

输出格式

每组测试数据输出一行一个整数，表示答案，对 $10^9+7$ 取模。

样例

输入

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

输出

48
96
10

数据范围与约定

• 对于 10% 的数据：保证 $k=1$。
• 对于 30% 的数据：保证 $1 \le k \le 10$。
• 对于 60% 的数据：保证 $1 \le n, k \le 500$。
• 对于 100% 的数据：保证 $1 \le T \le 5,\ 1 \le n, k \le 5 \times 10^3,\ 1 \le u, v \le n,\ 1 \le a, b, c \le 10^9$。