آقای $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$ آمده است که تعداد کارمندان شرکت در این سناریو را نشان می‌دهد.

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

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

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le q \le 2000$
• $1 \le n \le 10^{18}$

شرح ورودی و خروجی نمونه

در حالت 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}$

• سوال قبل