Это простая версия задачи. Различие состоит в том, что в этой версии нет вершин с уже зафиксированными цветами.
Теофанис ужасно проголодался и хочет, наконец, отведать своего любимого блюда, шефталью. Но сначала ему нужно закончить с домашней работой. Поможете ли вы ему в решении данной задачи?
Вам задано идеальное двоичное дерево из \(2^k - 1\) вершин — двоичное дерево, в котором у всех вершин \(i\) от \(1\) по \(2^{k - 1} - 1\) есть ровно два сына: вершины \(2i\) и \(2i + 1\). У вершин с \(2^{k - 1}\) по \(2^k - 1\) нет детей. Вы хотите покрасить его вершины в \(6\) цветов кубика Рубика (белый, зеленый, красный, синий, оранжевый и желтый).
Назовем раскраску хорошей, если все ребра дерева соединяют вершины, цвета которых являются соседними цветами кубика Рубика.
Изображение кубика Рубика и его развертка. Формально говоря:
- соседними к белой вершине не могут быть белые и желтые вершины;
- соседними к желтой вершине не могут быть белые и желтые вершины;
- соседними к зеленой вершине не могут быть зеленые и синие вершины;
- соседними к синей вершине не могут быть зеленые и синие вершины;
- соседними к красной вершине не могут быть красные и оранжевые вершины;
- соседними к оранжевой вершине не могут быть красные и оранжевые вершины.
Вам нужно посчитать количество хороших раскрасок двоичного дерева. Две раскраски считаются различными, если существует вершина, цвет которой в них различается.
Так как ответ может быть слишком большим, выведите его по модулю \(10^9+7\).