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

---

آقای \(B\) می‌خواهد با دعوت تعدادی از کارمندهای شرکتش یک دوره مهمانی مخفیانه برگزار کند.

اگر این شرکت \(n\) کارمند داشته باشد، این کارمندها با شماره‌های \(1\) تا \(n\) مشخص می‌شوند و فرد شماره \(i\) با افراد با شماره‌های \(2i\)، \(2i+1\) و \(\lfloor \frac{i}{2} \rfloor\) در صورت وجود دوست است.

در دوره مهمانی‌های آقای \(B\)، هر شب یک مهمانی برگزار می‌شود. در این دوره مهمانی‌ها، هر کس در هر مهمانی حضور پیدا کند، در تمام مهمانی‌های شب‌های بعدی نیز حضور پیدا می‌کند. آقا \(B\) تصمیم گرفته برای شب اول تعدادی از کارمندها را مستقیما دعوت کند تا در مهمانی حضور داشته باشند، و بعد از آن در هر شب، هر فردی که در مهمانی شب قبلی حضور داشته دوستانش را برای مهمانی بعدی دعوت می‌کند و آن‌ها نیز در مهمانی شب بعد حضور پیدا می‌کنند. همچنین هر کس به اندازه تعداد مهمانی‌هایی که از دست داده، ناراحت می‌شود. ناراحتی کلی افراد نیز برابر با مجموع ناراحتی کارمندها است.

حال آقای \(B\) می‌خواهد تعدادی از کارمندهایش را به مهمانی دعوت کند، او برای انتخاب افراد در شب اول یکی از مجموعه‌های ناتهی کارمندان را به صورت تصادفی و با احتمال برابر انتخاب و دعوت می‌کند. (یعنی هر کدام از \(2^n-1\) حالت ممکن به احتمال برابر انتخاب می‌شوند)

آقای \(B\) از شما خواسته تا امیدریاضی ناراحتی کلی افراد را برای او محاسبه کنید ولی چون یادش نیست که شرکتش چند کارمند دارد \(q\) حدس مختلفی که برای \(n\) دارد را به شما می‌گوید تا جواب را در همه حالات به دست آورید. همچنین چون او اعداد اعشاری را دوست ندارد، از شما خواسته که اگر امید ریاضی خواسته شده به صورت \(\frac{P}{Q}\) نوشته شود که \(P\) و \(Q\) اعداد صحیح نسبت به هم اول هستند، با توجه به این که \(Q\) بر \(10^9+7\) بخش‌پذیر نیست، مقدار \(PQ^{-1}\) به پیمانه \(10^9+7\) را به عنوان جواب گزارش کنید.

ورودی

در سطر اول ورودی عدد \(q\) آمده‌است.

در هر یک از \(q\) سطر بعدی یک مقدار \(n\) آمده است که تعداد کارمندان شرکت در این سناریو را نشان می‌دهد. \[ 1 \le q \le 2000 \] \[ 1 \le n \le 10^{18} \]

خروجی

در هر یک از \(q\) خط خروجی, مقدار خواسته شده را برای \(n\) مربوطه خروجی دهید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۷	\( n \le 200 \)
۲	۲۳	هر عدد \(n\) به شکل \(2^k - 1\) است.
۳	۳۳	\( q \le 200 \)
۴	۳۷	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

5
1
2
3
4
5

خروجی نمونه ۱

0
666666672
571428577
733333341
548387104

در حالت \(n = 1\) امید ریاضی ناراحتی کلی افراد برابر \(0\) است. برای \(n=2\) امید ریاضی برابر \(\frac{2}{3}\) است که به پیمانه \(10^9+7\) برابر با \(666666672\) است.

امید ریاضی ناراحتی کلی افراد در مثال‌های داده شده به صورت زیر است:

\[ \frac{0}{1} \frac{2}{3} \frac{11}{7} \frac{38}{15} \frac{105}{31} \]

ورودی نمونه ۲

5
438683104447824131
461983238699791439
483227912528828095
352592111888489755
432980889538354445

خروجی نمونه ۲

597802608
929243282
897893632
550955255
88788769