Masala #0191

Xaritada shaharlarning bog’lashini keltirilgan, unga ko’ra 0 – shahardan 1-shaharga bo’lgan yo’llar soni a₀ ta, 1 – shahardan 2 – shaharga bo’lgan yo’llar soni a₁ ta, va hokazo, shunday tartibda faqatgi yonma-yon shaharlar orasida yo’llar bor.

Megamix 0 – shahardan oxirgi shaharga borishning necha xil usuli mavjudligini bilmoqchi, unga yordam bering.

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 1000) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun alohida ikki qatorning birinchi satrida N (2 < N ≤ 100) shaharlar soni, ikkinchi satrda N-1 ta butun son, a_i(0 < a_i ≤ 1000) shaharlar orasidagi yo’llar soni kiritiladi.

Har bir test uchun alohida qatorda Megamix bilmoqchi bo’lgan sonni chop eting, bu son juda katta bo’lishi mumkin, shuning uchun siz natijaviy sonning 1234567 ga bo’lgandagi qoldig’ini chop eting.