Вася очень любит рисовать верблюдов: одногорбых, двугорбых, трехгорбых и так далее. Верблюда он рисует соединяя точки на координатной плоскости. Сейчас он рисует t-горбых верблюдов, изображая их ломанными на плоскости. Каждая ломанная состоит из n вершин с координатами (x₁, y₁), (x₂, y₂), ..., (x_n, y_n). Первая вершина имеет координату x₁ = 1, вторая x₂ = 2 и т.д. Координаты y_i могут быть любыми, но должны удовлетворять следующим условиям:

• должно существовать ровно t горбов, то есть таких индексов j (2 ≤ j ≤ n - 1), что y_j - 1 < y_j > y_j + 1,
• должно существовать ровно t - 1 таких индексов j (2 ≤ j ≤ n - 1), что y_j - 1 > y_j < y_j + 1,
• никакой отрезок ломанной не должен быть параллелен оси Ox,
• все y_i — целые числа от 1 до 4.

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