Дано корневое дерево из $$$2^n - 1$$$ вершин. У каждой вершины дерева либо $$$0$$$ сыновей, либо $$$2$$$. Все листья дерева расположены на одинаковой глубине, а у каждой внутренней вершины один из сыновей является левым, а другой — правым. Формально, вам задано совершенное бинарное дерево.

Вершины дерева пронумерованы следующим образом:

• номер корня — $$$1$$$;
• если номер внутренней вершины — $$$x$$$, то номер ее левого сына — $$$2x$$$, а номер правого сына — $$$2x+1$$$.

На каждой вершине дерева записана буква A или буква B. Пусть буква на вершине $$$x$$$ — это $$$s_x$$$.

Назовем строкой прямого обхода вершины $$$x$$$ строку, которая строится по следующим правилам:

• если вершина $$$x$$$ — лист, то строка прямого обхода $$$x$$$ состоит из одного символа $$$s_x$$$;
• в противном случае строка прямого обхода $$$x$$$ равна $$$s_x + f(l_x) + f(r_x)$$$, где $$$+$$$ обозначает конкатенацию строк, $$$f(l_x)$$$ — строка прямого обхода левого сына $$$x$$$, а $$$f(r_x)$$$ — строка прямого обхода правого сына $$$x$$$.

Строка прямого обхода всего дерева — это строка прямого обхода его корня.

А теперь — сама задача.

Вы должны посчитать количество различных строк, которые могут быть получены как строка прямого обхода заданного дерева, если до построения строки прямого обхода можно применить следующую операцию любое количество раз:

• выбрать любую вершину $$$x$$$, не являющуюся листом, и поменять местами ее детей (то есть левый сын становится правым, и наоборот).