LCA-сумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево, состоящее из $$$n$$$ вершин, пронумерованных числами от $$$1$$$ до $$$n$$$. У каждой вершины $$$v$$$ кроме корневой непосредственный предок равен $$$p_v$$$, если $$$v$$$ — корень, то выполняется $$$p_v = v$$$. Вершина $$$u$$$ называется предком $$$v$$$, если $$$u$$$ содержится на простом пути от $$$v$$$ до корня дерева. В частности, сама вершина, ее непосредственный предок и корень всегда являются ее предками.

Пусть $$$S$$$ — некоторое множество вершин дерева, обозначим через $$$\textrm{LCA}(S)$$$ наименьшего общего предка множества $$$S$$$, то есть наиболее удаленную от корня вершину, которая является предком для каждой вершины из $$$S$$$.

Например, пусть дерево состоит из $$$6$$$ вершин и имеет вид как на картинке выше. Тогда:

- $$$\textrm{LCA}(\{2, 3\}) = 5$$$
- $$$\textrm{LCA}(\{6, 1\}) = 1$$$
- $$$\textrm{LCA}(\{5, 2, 3\}) = 5$$$
- $$$\textrm{LCA}(\{3\}) = 3$$$

Требуется узнать сумму значений номеров наименьших общих предков для всех непустых подмножеств вершин дерева. Так как ответ может быть слишком большим, выведите его по модулю $$$10^9 + 7$$$

Входные данные

Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество вершин в дереве.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — массив предков.

Гарантируется, что массив $$$p$$$ кодирует некоторое корневое дерево, и что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных на отдельной строке выведите единственное число — сумму значений функции $$$\textrm{LCA}$$$ по всем подмножествам вершин дерева по модулю $$$10^9 + 7$$$.

Пример

Входные данные

    364 5 5 4 4 122 251 1 1 2 3

Выходные данные

    250
    5
    44

Примечание

Первый набор входных данных соответствует дереву из условия.