Однажды здесь была великая легенда, но один тролль взломал Codeforces и удалил его. Очень плохо для наc, но в сообществе троллей он заработал уважение и титул овер-супер-мега тролля. Пожалуй для них это что-то хорошее. А для нас, наверное, ещё лучше будет формальное условие.
Вам дано дерево \(T\), содержащее \(n\) вершин, пронумерованных от \(1\) до \(n\). Для каждого непустого \(X\), являющемся подмножеством вершин \(T\), определим \(f(X)\) как количество рёбер в минимальном по размеру поддереве \(T\), содержащем все вершины из \(X\).
Вам также дано целое число \(k\). Вам нужно вычислить сумму \((f(X))^k\) по всем непустым подмножествам вершин, то есть:
\(\) \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k. \(\)
Так как эта величина может быть очень большой, выведите её по модулю \(10^9 + 7\).
Примечание
В первых двух примерах значения \(f\) выглядят следующим образом:
\(f(\{1\}) = 0\)
\(f(\{2\}) = 0\)
\(f(\{1, 2\}) = 1\)
\(f(\{3\}) = 0\)
\(f(\{1, 3\}) = 2\)
\(f(\{2, 3\}) = 1\)
\(f(\{1, 2, 3\}) = 2\)
\(f(\{4\}) = 0\)
\(f(\{1, 4\}) = 2\)
\(f(\{2, 4\}) = 1\)
\(f(\{1, 2, 4\}) = 2\)
\(f(\{3, 4\}) = 2\)
\(f(\{1, 3, 4\}) = 3\)
\(f(\{2, 3, 4\}) = 2\)
\(f(\{1, 2, 3, 4\}) = 3\)