Парад дужок
Порахуйте кількість різних правильних послідовностей дужок, що складаються з 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.