Кубики
Петрик П'яточкин, несмотря на то, что уже ходит в школу, все еще любит играть с кубиками. Он строит ступеньки вдоль стены, используя одинаковые кубики. Для этого он складывает столбики кубиков следующим образом:
первый столбик располагается вплотную к стене;
второй столбик ставится вплотную к стене и к первому столбику справа от него;
третий столбик размещается вплотную к стене и ко второму столбику справа от него, и так далее...
Высоты столбиков не увеличиваются, если смотреть на ступеньки слева направо. То есть, если h_i — это высота i-го столбика, то выполняется условие h_1 ≥ h_2 ≥ h_3 ≥ ... .
Петрик устанавливает кубики в определенной последовательности, соблюдая следующие правила:
Кубик, который не находится на полу, можно поставить только после того, как будет установлен кубик, на котором он должен стоять. То есть нельзя подсовывать кубики под уже установленные.
Кубик, который не находится в первом столбике, можно поставить только после установки кубика, расположенного слева от него.
Требуется определить количество различных способов последовательной установки кубиков, в результате которых образуются ступеньки с заданными высотами столбиков h_1, h_2, ..., h_k. Учитываются только те способы, которые соответствуют условиям (1) и (2).
Входные данные
Первая строка входного файла содержит натуральное число k — количество столбиков (1 ≤ k ≤ 6).
Вторая строка входного файла содержит k натуральных чисел h_1, h_2, ..., h_k — количество кубиков в первом, втором, …, k-м столбике ступенек (6 ≥ h_1 ≥ h_2 ≥ ... ≥ h_k ≥ 1).
Выходные данные
Единственная строка выходного файла должна содержать количество различных способов расположения кубиков в заданную конфигурацию согласно указанным правилам (1) и (2) при данных высотах столбиков.
Для примера укажите допустимые последовательности расположения кубиков. Номер каждого кубика указывает, каким по счету его ставят.