Вам дано дерево \(G\) из \(n\) вершин, а также целое число \(k\). Вершины дерева пронумерованы от \(1\) до \(n\).
Для некоторой вершины \(r\) и подмножества \(S\) вершин дерева \(G\) такого, что \(|S| = k\), определим \(f(r, S)\) как размер наименьшего корневого поддерева, содержащего все вершины \(S\) при условии, что корнем дерева является вершина \(r\). Множество вершин \(T\) называется корневым поддеревом, если все вершины в \(T\) связны и для любой вершины в \(T\) все ее потомки тоже принадлежат \(T\).
Вам нужно вычислить сумму \(f(r, S)\) по всем различным комбинациям вершины \(r\) и подмножества \(S\), где \(|S| = k\). Формально, вычислите следующее: \(\)\sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S),\(\) где \(V\) — множество вершин дерева \(G\).
Выведите ответ по модулю \(10^9 + 7\).
Примечание
Дерево во втором примере показано ниже:
Всего в этом дереве \(21\) подмножество вершин размера \(2\). А именно, \(\)S \in \left\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{1, 6\}, \{1, 7\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{2, 6\}, \{2, 7\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}.\(\) Так как в дереве \(7\) вершин, \(1 \le r \le 7\). Нужно найти сумму \(f(r, S)\) по всем парам \(r\) и \(S\).
Ниже перечислены значения \(f(r, S)\) для некоторых комбинаций \(r\) и \(S\).
- \(r = 1\), \(S = \{3, 7\}\). Значение \(f(r, S)\) равно \(5\), а соответствующее поддерево равно \(\{2, 3, 4, 6, 7\}\).
- \(r = 1\), \(S = \{5, 4\}\). Значение \(f(r, S)\) равно \(7\), а соответствующее поддерево равно \(\{1, 2, 3, 4, 5, 6, 7\}\).
- \(r = 1\), \(S = \{4, 6\}\). Значение \(f(r, S)\) равно \(3\), а соответствующее поддерево равно \(\{4, 6, 7\}\).