Парад скобок
Посчитайте количество различных правильных скобочных последовательностей, состоящих из k[1] пар скобок первого типа, k[2] пар скобок второго типа, ..., k[m] пар скобок m-го типа. Последовательность скобок считается правильной в следующих случаях:
Пустая последовательность – правильная;
Если A и B правильны, то AB тоже правильная
Если A правильная, то (A) правильная, где ( и ) – открывающая и закрывающая скобка одного типа.
Входные данные
Первая строка содержит количество тестов n (0 < n ≤ 1000). Каждая из следующих n строк задает один тест. Каждая строка начинается с числа m (0 < m ≤ 100) – количества различных типов скобок. Затем m положительных чисел k[1], k[2], ..., k[m] следуют одно за другим через пробел. Число k[i] – это количество пар скобок i-го типа. Общее количество пар скобок – не больше 1000.
Выходные данные
Для каждого теста выведите строку, содержащую одно целое число – ответ задачи по модулю 1000000007.