Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Преподаватели кафедры «Вычислительная техника» готовят комплект билетов для выпускного государственного экзамена.
В экзаменационную программу входят N дисциплин; по i-й дисциплине преподаватели составили Ki заданий. В каждом билете должно быть три задания, причём из разных дисциплин. Порядок заданий в билете не имеет значения.
Преподаватели не хотят, чтобы билеты в комплекте повторялись. Помогите им определить, сколько различных экзаменационных билетов можно составить из имеющихся заданий. Так как это число может оказаться очень большим, выведите остаток от его деления на 1000000007 (10^9 + 7).
Входные данные
Первая строка содержит целое число N (1 <= N <= 1000) — количество дисциплин.
Вторая содержит N целых чисел Ki (0 <= Ki <= 1000) — количества заданий по каждой из дисциплин.
Выходные данные
Выведите одно целое число — ответ на задачу.
Примеры
| Входные данные | Выходные данные |
3
1 2 3 | 6 |
5
1 2 2 1 1 | 25 |
Для отправки решений необходимо выполнить вход.
|