Şah əsər#9106
Dünya şöhrətli rəssam Teodor Kadman Spenser, "Bənövşəyi Kvadrat" və "Fuşyə Dairəsi" əsərlərindən sonra yeni bir şah əsəri üzərində çalışır. Bu əsər tək bir həndəsi forma ilə təsvir edilə bilməz və bu, Teodorun sənətində yeni bir mərhələdir.
Rəssam n x n ölçüsündə bir kətan seçib, bu kətan 1 x 1 kvadratlara bölünmüşdür. Əvvəlcə tamamilə ağ olan kətanda, Teodor tünd-bordo kvadratlar çəkməyə başlayır.
Teodor fırçasını kətanın sol üst küncündən (birinci sıra və birinci sütun) başlayaraq sağ alt küncə doğru hərəkət etdirir. Hər zaman ya bir kvadrat sağa, ya da bir kvadrat aşağı hərəkət edir. Fırçanın toxunduğu bütün kvadratlar dərhal bordo rəngə çevrilir. Sağ alt küncə çatdıqdan sonra, rəssam sola və ya yuxarı hərəkət edərək geri qayıdır və başladığı kvadratda bitirir. Rəssamın yolu seçməkdə sərbəstdir və iki dəfə rənglənən sahələr dəyişmir.
Siz Spenserin işlərinin böyük bir pərəstişkarısınız və onun kompüterinə daxil olaraq əsərin planlarını yükləməyə çalışdınız. Lakin faylın böyük ölçüsü buna mane oldu, buna görə də onu sıxılmış formada saxladınız. Hər bir n sıranın tünd-bordo kvadratlarının sayını və hər bir n sütunun tünd-bordo kvadratlarının sayını hesabladınız. Bu dəyərləri serverinizdə saxladınız.
İndi isə, bu məlumatlara uyğun gələn fırça yollarının sayını bilmək istəyirsiniz. İki yol fərqli sayılır, əgər bir anda rəssam başqa bir istiqamət seçirsə. Qeyd edək ki, iki fərqli yol eyni rəsmə gətirib çıxara bilər, amma siz prosesi fərqli hesab edirsiniz.
Cavab böyük ola biləcəyi üçün onu 10^9 + 7 modulunda çıxarın.
Birinci sətir testlərin sayı z (1 ≤ z ≤ 30) ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər bir testin birinci sətiri kətanın ölçüsünü n (1 ≤ n ≤ 100 000) ehtiva edir. İkinci sətir hər bir sıradakı tünd-bordo kvadratların sayını r[i] (0 ≤ r[i] ≤ n) ehtiva edir. Növbəti sətir sütunların təsvirlərini eyni formatda ehtiva edir.
Hər bir test üçün bir tam ədəd çıxarın: verilən məlumatlara uyğun rəsm çəkməyə gətirib çıxaran yolların sayını 10^9 + 7 modulunda.
Nümunə 1