У вас есть корневое дерево, состоящее из n вершин. Пронумеруем вершины дерева целыми числами от 1 до n включительно. Корень дерева находится в вершине 1. Для каждого i > 1 непосредственным предком вершины i является вершина p_i. Назовём вершину i ребёнком вершины p_i.

Изначально вы покрасили все вершины в красный цвет. Кроме этого, вы любите перекрашивать некоторые вершины дерева. Для этого вы используете функцию paint, которую вы вызываете от корня дерева. Ниже приведен псевдокод этой функции:

count = 0 // глобальная целочисленная переменная 

rnd() { // эта функция используется в коде paint
    вернуть 0 или 1 с равной вероятностью 50%
}

paint(s) {
    if (count четное) then покрасить вершину s в белый цвет
    else покрасить вершину s в черный цвет

    count = count + 1
    
    if rnd() = 1 then children = [массив из детей вершины s в порядке возрастания номеров]
    else children = [массив из детей вершины s в порядке убывания номеров]

    for child in chilren { // проходим по элементам массива child
        if rnd() = 1 then paint(child) // выполняем рекурсивный вызов функции paint
    }
}

В результате выполнения этой функции некоторые вершины могут изменить свой цвет на белый или чёрный, а некоторые — остаться красными.

Ваша задача — определить количество различных возможных раскрасок вершин дерева. Будем считать раскраску возможной, если существует ненулевая вероятность получить эту раскраску с помощью одного вызова функции paint(1). Будем считать раскраски различными, если существует пара вершин, которые покрашены в различные цвета в этих раскрасках. Поскольку искомое количество может быть очень большим, найдите остаток от деления этого количества на 1000000007 (10⁹ + 7).