Посчитайте количество различных правильных скобочных последовательностей, состоящих из k1 пар скобок первого типа, k2 пар скобок второго типа, ..., km пар скобок m-го типа. Последовательность скобок считается правильной в следующих случаях:

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

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

Первая строка содержит количество тестов n (0 < n ≤ 1000). Каждая из следующих n строк задает один тест. Каждая строка начинается с числа m (0 < m ≤ 100) – количества различных типов скобок. Затем m положительных чисел k1, k2, ..., km следуют одно за другим через пробел. Число ki – это количество пар скобок i-го типа. Общее количество пар скобок – не больше 1000.

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

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