Республиканская олимпиада по математике 2015 года за 9 класс | Казахстанские олимпиады

Дано дерево полного пирамидального вида, которое состоит из ${n+1}$ уровней, и из каждой вершины исходит два ребра вниз и входит одно ребро сверху (при этом в самую верхнюю вершину уровня 1 не входит ни одно ребро, а из вершин последнего $(n+1)$-го уровня не исходят рёбра). На рисунке ниже пример показан для $n = 3$.
Сколько существует способов раскрасить ребра данного дерева в заданные $2^n$ цветов (каждое ребро покрашено в один цвет) так, чтобы для каждого цвета все рёбра, покрашенные в этот цвет, составляли путь из некоторой вершины в вершину последнего уровня? (Путь — это последовательность вершин, где каждая следующая вершина соединена ребром с предыдущей и находится уровнем ниже. )