+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از اینکه پوریا بازی‌اش تمام شد به حیاط رفت و مطمئن بود دیگر قرار نیست امروز با مسئله ریاضی دست و پنجه نرم کند؛ اما زهی خیال باطل! وقتی وارد حیاط شد $N$ مورچه را دید که هر کدام روی یک راس از یک $N$ ضلعی منتظم قرار دارند (روی هر راس تنها یک مورچه نشسته است). هر چند وقت **همه** مورچه‌ها باهم تصمیم میگیرند که به راس‌های همسایه خود بروند (یک راس را همسایه گوییم اگر با یک یال به راس مذکور وصل باشد). می‌دانیم که مورچه‌های حیاط پوریا غذا گیرشان نیامده و اعصاب ندارند و اگر یکدیگر را بر روی یک راس ببینند همدیگر را آنقدر می‌زنند تا هر دو بمیرند! (حالتی که دو مورچه به یک راس بروند باعث دعوا می‌شود) پوریا که دلش نمی‌خواست هیچ مورچه‌ای بمیرد برایش سوالی پیش آمد که چقدر احتمال دارد که بعد از هر حرکت همه مورچه ها زنده بمانند؟ او تا به خودش آمد دید باری دیگر مسئله‌ای ریاضی جلویش قرار دارد! شما که زحمت دو سوال قبل را برای پوریا کشیدید، لطفا این سوال را هم برای او حل کنید :) # مثال # ورودی در خط اول عدد $T$ داده می‌شود که نشان دهنده تعداد ورودی‌های هر تست نمونه است. $$T \le 1000$$ در $T$ خط بعد یک عدد $N$ داده می‌شود که نشان دهنده تعداد مورچه هاست. $$3 \le N \le 10^{11}$$ # خروجی فرض کنید جواب مسئله برابر کسر $P / Q$ باشد. برای هر ورودی حاصل $(10^9 + 7)$ % $(P * Q^{-1})$ را چاپ کنید + علامت **%** نشان دهنده باقی مانده است. ## ورودی نمونه ۱ ``` 1 3 ``` ## خروجی نمونه ۱ ``` 250000002 ```