+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
به تعدادی مربع واحد که شکلی همبند ایجاد کنند، (یعنی با شروع از هر مربع بتوان با تعدادی بار جابه‌جا شدن بین مربع‌های مجاور ضلعی به هر مربع دیگر رسید) یک چندمینو می‌گوییم. برای مثال تمام $6$-مینوهای ممکن را می‌توانید در شکل زیر (با در نظر گرفتن دوران‌ها) ببینید:
استاد که این بار سوال را صریح بیان می‌کند از شما می‌خواهد تعداد روش‌های پوشاندن یک جدول $2$ در $n$ با چندمینوها را پیدا کنید. از آن‌جایی که این مقدار ممکن است بزرگ باشد، کافی‌ست باقی‌مانده‌ی آن بر $10^9+7$ را پیدا کنید.
دو روش متفاوت شمرده می‌شود اگر در یک روش دوخانه توسط یک چندمینو پوشانده شود و در روش دیگر دو خانه در دو چندمینو قرار داشته باشند.
# ورودی
در خط اول ورودی عدد $t$، تعداد پرسش‌های استاد می‌آید. سپس در $t$ خط بعد در هر خط یک عدد صحیح مانند $n$، می‌آید که نشان‌دهنده تعداد ستون‌های جدول مورد پرسش استاد است.
# خروجی
برای هر یک از پرسش‌های استاد به‌ترتیب پاسخ را به پیمانه‌ی $10^9 + 7$ چاپ کنید.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت
|:------------------:|:----------:|:------------------:|
| ۱ | ۶۰ | $1 \leq t \leq 10^5 , 1\leq n \leq 10^6$ |
| ۲ | ۴۰ | $1 \leq t \leq 10^5 , 1 \leq n \leq 10^{18}$ |
# مثال
## ورودی نمونه ۱
```
4
1
2
962398
832984703297404324
```
## خروجی نمونه ۱
```
2
12
290395550
469838046
```