两次 NOI 金牌选手小 H 想去世界各国旅行。世界上有 \(n\) 个国家，这些国家被 \(n-1\) 条边连在一起。小 H 定义了一个旅行计划：他将他的旅行分为了若干天，每天都会游玩 \(n\) 个国家中的一个非空子集，并且每个国家只会恰好被游玩一次。假设小 H 某天旅游了国家 \(\{a_1, \cdots, a_k\}\)，那么当天他需要经过包含这些国家的最小连通块中的所有国家。但注意经过并不是游玩，只经过但没有游玩的国家在其他天中仍然可以被游玩一次。
这些国家拥有着不同的语言，具体的，第 \(i\) 个国家的语言为 \(c_i\)。小 H 如果某天经过的所有国家中有 \(t\) 种不同的语言，那么小 H 这一天的疲劳度为 \(2^t\)。
小 H 想要知道，所有不同的旅游计划的疲劳度之和是多少？两个旅游计划不同当且仅当某天游玩的国家不同。答案对 \(10^9+7\) 取模。
\(0\le n\le5000,1\le c_i\le10\)
我们考虑先枚举点集，然后考虑怎么求出贡献的次数。
既然是这个点集的贡献，那么就是求所有方案中包含这个点集的方案数。
设点集大小为 \(k\)，接着我们枚举总共旅游了 \(i+1\) 次，那么总的方案数就是
（记住这个 \(h(k)\)，待会要用）
从组合意义上来说就是先把剩下的 \(n-k\) 个放进 \(i\) 次里，然后因为旅游有顺序，所以再乘以 \((i+1)!\)，得到的就是总方案数。
接下来我们看怎么求出疲劳度。
正着求不好求，我们考虑反过来，钦定这次旅游中用到的语言集合 \(S\)，求出能选中钦定的方案的选点的方案数 \(F(S)\)。
但是这样好像还是不好做，我们继续放宽限制，不求刚刚好是 \(S\)，而是求语言集合为 \(S'\subseteq S\) 的方案数 \(G(S)\)。
这样就十分简单了，我们把不属于 \(S\) 的点全部 “删去”，树被分裂为多个联通块。
此时只要我们选的点全部属于同一个联通块，那么构成的语言集合 \(S'\) 必然包含于 \(S\)。
那么假设所有联通块的大小分别为 \(s_1,s_2,\cdots,s_m\)，总的方案数就是：
接下来就是最后一步，因为我们求的是语言集合为 \(S'\subseteq S\) 的方案数 \(G\)，接下来我们求出 \(F\)。
因为有
根据子集反演，
因此我们通过枚举子集就能求出 \(F\)。
求出 \(F\) 之后，我们乘上 \(2^{|S|}\) 的疲劳值，然后累加，我们就得到了最终的答案！
时间复杂度 \(\mathcal O(n^2+n2^t+3^t)\)，\(t=\max c_i\)。