C. Panelni domino bilan qoplash
Vaqt limiti: 2000 ms Xotira limiti: 256 mb
Kengligi \(2\) va uzunligi \(n\) bo'lgan to'g'ri to'rtburchak panel berilgan (ya'ni \(2 \times n\) o'lchamli katakcha panel). Panelni to'liq, bo'sh joy qoldirmasdan va bir-birining ustiga chiqmasdan, \(1 \times 2\) o'lchamli domino bo'laklari bilan qoplamoqchisiz (har bir domino gorizontal yoki vertikal joylashishi mumkin).
\(q\) ta so'rov beriladi, har birida \(n\) soni beriladi. Har bir so'rov uchun panelni qoplashning nechta xil usuli borligini \(10^9+7\) ga bo'lgandagi qolig'ini toping.
Eslatma: agar \(n=0\) bo'lsa, panel bo'sh hisoblanadi va uni qoplashning yagona (hech narsa qo'ymaslik) usuli bor deb hisoblang.
Kiruvchi ma'lumotlar
Birinchi qatorda \(q\) (\(1 \le q \le 10^5\)) soni beriladi. Ikkinchi qatorda \(q\) ta butun son \(n_1, \dots, n_q\) (\(0 \le n_i \le 10^{18}\)) beriladi.
Chiquvchi ma'lumotlar
\(q\) qatorda — har bir so'rov uchun javobni chiqaring (har birini alohida qatorda).
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
5 0 1 2 3 4 |
1 1 2 3 5 |
2 |
3 5 10 20 |
8 89 10946 |
Izoh
\(2 \times 2\) panelni domino bilan qoplashning \(2\) xil usuli VV va HH.
\(2 \times 4\) panelni domino bilan qoplashning \(5\) xil usuli VVVV, VVHH, VHHV, HHVV va HHHH.
