У Сени есть шоколадка, составленная из нескольких прилегающих друг к другу плиточек в форме правильных треугольников. Его брат Женя нашел эту шоколадку и решил сделать ее треугольной, съев все лишнее (ведь треугольные шоколадки намного вкуснее). Сколькими способами он может это сделать?
Например, из такой шоколадки:
можно сделать треугольную шоколадку со стороной 1 шестью способами или шоколадку со стороной 2 двумя способами. Итого восемь способов.
Входные данные
Форма шоколадки задается ее границей в порядке обхода по часовой стрелке. Первая строка входного файла INPUT.TXT содержит число n - количество отрезков на границе (1 ≤ n ≤ 5000). Далее n чисел от 1 до 6, задающих направление движения по границе (см. рисунок).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - количество способов.
|
Можете помочь с данной задачей? Скорее всего, есть сугубо математическое решение, так как лучшее решение данной задачи в 121 символ на C++.