Masala #0191

Xotira 16 MB Vaqt 1000 ms
14

Yo’llar soni

Xaritada shaharlarning bog’lashini keltirilgan, unga ko’ra 0 – shahardan 1-shaharga bo’lgan yo’llar soni a0 ta, 1 – shahardan 2 – shaharga bo’lgan yo’llar soni a1 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.


Kiruvchi ma'lumotlar:

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, ai(0 < ai ≤ 1000) shaharlar orasidagi yo’llar soni kiritiladi.


Chiquvchi ma'lumotlar:

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.


Misollar
# input.txt output.txt
1
2
3
1 3
4
2 2 2
3
8