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