• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

عرفان و دوستانش که مجموعاً $3n$ نفر می‌شوند به سینما رفتند و روی $3n$ صندلی متوالی در یک رديف نشستند. آن‌ها با خود $n + 1$ بسته پاپ كورن به سینما بردند. قرار شد $n + 1$ پاپ کورن بین افراد تقسیم شود به نحوی که به هر نفر حداکثر یک بسته پاپ کورن برسد. در صورتی یک نفر از فیلم لذت می‌برد که یا خود یا یکی از ۲ نفر بغل دستی‌اش (۲ نفر کناری هر کدام ۱ بغل دستی دارند) پاپ کورن داشته باشد. حال برای عرفان سوال شده است که به چند طريق می‌توان پاپ کورن‌ها را بین افراد تقسیم کرد که همه از فیلم لذت ببرند.

ورودی

در سطر اول عدد $T$ آمده است که تعداد تست کیس‌ها است. در هر یک $T$ خط بعد یک عدد آمده است که نشان دهنده‌ی $n$ است.

$$1 \leq T \leq 100 , 000$$

$$1 \leq n \leq 10^9$$

خروجی

بـه ازای هـر تسـت تعداد حالات افراز $n + 1$ پـاپ کورن بین $3n$ نفر به طوری که همه از فیلم لذت ببرند را به پیمانه‌ی $10^9 + 7$ چاپ کنید.

مثال

ورودی نمونه ۱

3
1
2
3

خروجی نمونه ۱

3
10
22

حالات مطلوب برای $n = 1$ (عدد $1$ پاپ کورن دارد $0$ ندارد) :

$$101 \mid 110 \mid 011$$

حالات مطلوب برای $n = 2$ (عدد $1$ پاپ کورن دارد $0$ ندارد) :

$$110010 \mid 101010 \mid 011010 \mid 100110 \mid 010110$$

$$101001 \mid 011001 \mid 100101 \mid 010101 \mid 010011$$