eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Парад скобок

Парад скобок

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Посчитайте количество различных правильных скобочных последовательностей, состоящих из k[1] пар скобок первого типа, k[2] пар скобок второго типа, ..., k[m] пар скобок m-го типа. Последовательность скобок считается правильной в следующих случаях:

  • Пустая последовательность – правильная;

  • Если A и B правильны, то AB тоже правильная

  • Если A правильная, то (A) правильная, где ( и ) – открывающая и закрывающая скобка одного типа.

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

Первая строка содержит количество тестов n (0 < n1000). Каждая из следующих n строк задает один тест. Каждая строка начинается с числа m (0 < m100) – количества различных типов скобок. Затем m положительных чисел k[1], k[2], ..., k[m] следуют одно за другим через пробел. Число k[i] – это количество пар скобок i-го типа. Общее количество пар скобок – не больше 1000.

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

Для каждого теста выведите строку, содержащую одно целое число – ответ задачи по модулю 1000000007.

Пример

Входные данные #1
3
1 4
2 2 2
3 1 2 3
Выходные данные #1
14
84
7920