eolymp
Задачі

Парад дужок

Парад дужок

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

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

Вхідні дані

Перший рядок містить кількість тестів n (0 < n1000). Кажен з наступних n рядків описує тест. Кажен рядок починається з числа m (0 < m100) - кількості різних типів дужок. Потім m додатніх чисел k1, k2, ..., km, що йдуть одне за одним через пропуск. Число ki – це кількість пар дужок i-го типу. Загальна кількість пар дужок не більша 1000.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 4
2 2 2
3 1 2 3
Вихідні дані #1
14
84
7920