Кубики
Незважаючи на те, що Петрик П’яточкін ходить до школи, він все ще продовжує гратися з кубиками. З однакових кубиків він викладає сходинки вздовж стіни. Для цього складає стовпчики з кубиків таким чином:
перший стовпчик стоїть впритул до стіни;
другий стовпчик стоїть впритул до стіни і впритул до першого стовпчика праворуч від нього;
третій стовпчик стоїть впритул до стіни і впритул до другого стовпчика праворуч від нього і так далі...
Висоти стовпчиків не зростають при розгляданні сходинок зліва направо. Інакше кажучи, якщо 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) при даних висотах стовпчиків.
Для цього прикладу вкажемо допустимі послідовності розташування кубиків. Номер кожного кубика вказує, яким за рахунком його ставлять.