k1 sayda birinci tip mötərizələr cütündən, k2 sayda ikinci tip mötərizələr cütündən,..., km sayda m-ci tip mötərizələr cütündən təşkil edilmiş müxtəlif düzgün mötərizələr ardıcıllığının sayını hesablayın.

Mötərizələr ardıcıllığı aşağıdakı hallarda düzgün hesab edilir:

• Boş ardıcıllıq-düzgündür;
• Əgər A və B düzgündürsə, onda AB də düzgündür;
• Əgər A düzgündürsə, onda (A) də düzgündür. Burada ( və ) eyni tipli açılan və bağlanan mötərizələrdir.

Giriş verilənləri

Giriş faylının birinci sətrində testlərin n (0 < n ≤ 1000) sayı verilir. Sonrakı n sətrin hər birində testlər təsvir olunur. Hər bir sətir müxtəlif tip mötərizələrin sayı olan m (0 < m ≤ 100) ədədi ilə başlayır. Sonra aralarında boşluq işarəsi olmaqla m sayda bir birinin ardınca müsbət k1, k2, ..., km ədədləri gəlir. ki ədədləri i-ci tip mötərizələr cütünün sayıdır. Mötərizələr cütünün ümumi sayı 1000-dən böyük deyil.

Çıxış verilənləri

Hər bir test üçün bir tam ədəd - məsələnin cavabını mütləq qiymətcə 1000000007-dən çox olmamaqla bir sətirdə verin.