A. Кёя и цветные мячи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кёи Оотори есть сумка с n цветными мячиками, раскрашенными k различными цветами. Цвета пронумерованы от 1 до k. Мячики одного цвета неотличимы друг от друга. Юноша вынимает мячики из сумки один за другим, пока сумка не опустеет. Он заметил, что для всех i от 1 до k - 1 он вынул последний мяч цвета i до того, как он вынул последний мяч цвета i + 1. Теперь ему интересно, сколько существует различных последовательностей цветов вынутых мячей, удовлетворяющих данному условию.

Входные данные

В первой строке ввода находить целое число k (1 ≤ k ≤ 1000) — количество цветов.

Затем следуют k строк. В i-й строке находится число ci, количество мячей i-го цвета (1 ≤ ci ≤ 1000).

Суммарное количество мячей не превосходит 1000.

Выходные данные

Выведите единственное целое число — остаток от деления на 1 000 000 007 количества различных последовательностей цветов мячей, удовлетворяющих условию.

Примеры
Входные данные
3
2
2
1
Выходные данные
3
Входные данные
4
1
2
3
4
Выходные данные
1680
Примечание

В первом примере у нас есть два мяча цвета 1, два мяча цвета 2, и один мяч цвета 3. Три возможных способа таковы: 


1 2 1 2 3
1 1 2 2 3
2 1 1 2 3