+ محدودیت زمان: 3 ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
---
محمدسام به تازگی به شرکت در قرعه کشی های مختلف علاقه مند شده است. در آخرین قرعه کشی ای که او شرکت کرده است ، به او یک کد $n$ رقمی با ارقام 1 و 2 و 3 داده میشود. او یک شاخص میزان خوش یُمنی برای خود درنظر میگیرد تا بتواند با استفاده از آن ، حدس بزند که آیا ممکن است در قرعه کشی برنده شود یا خیر.
او در یک کد $x$ رقمی به نام $s$ که ارقام آن به ترتیب $s_1$ تا $s_x$ هستند، جذاب بودن آن کد را برابر با تعداد اندیس های $i$ تعریف میکند که $$ 1 \leq i \leq x-1 $$ و $$s_i < s_{i+1} \quad $$ است. و آن را با $G(s) $ نشان میدهد. ( جذاب بودن یک کد 0 رقمی ، برابر با 0 است ) به عبارتی $ G(s) $ نشان دهنده تعداد جایگاه هایی در کد $s$ است که رقم آنها از رقم بعدی خود کوچکتر است.
او میزان خوش یُمن بودن یک کد قرعه کشی $n$ رقمی $s$ را ، برابر با جمع $ G(a) ^ k $ به ازای تمامی $2^n $ زیردنباله کد $s$ در نظر میگیرد . به صورتی که $k$ یک عدد ثابت است و به ازای هر تست کیس به شما ورودی داده میشود و $a$ زیردنباله ای از $s$ است . به طور دقیقتر میزان خوش یُمنی یک کد برابر با عبارت زیر است :
$$ \sum_{m=0}^{n}
\;
\sum_{1\le i_1<i_2<\cdots<i_m\le n}
G(s_{i_1}s_{i_2}\cdots s_{i_m})^k $$
محمدسام هنوز کد قرعه کشی خود را دریافت نکرده و نمیداند قرار است چقدر این کد خوش یُمن باشد. اما میداند این کد ، یک کد $n$ رقمی با ارقام 1 و 2 و 3 است . او میداند کد قرعه کشی اش ، به صورت تصادفی و با احتمال برابر ، یکی از $3^n$ کد $n$ رقمی موجود ( با ارقام 1 و 2 و 3 ) خواهد بود . حال او از شما میخواهد با توجه به این اطلاعات ، امیدریاضی میزان خوش یُمنی کدی که محمدسام دریافت خواهد کرد را باقیمانده بر $10^9 + 7$ حساب کنید.
میتوان نشان داد جواب به صورت کسر ساده نشدنی $ \frac{p}{q} $
است که $p$ و
$ q $
اعداد صحیح هستندو
$ q \neq 0 $
و شما باید
$ p \cdot q^{-1} ( mod \ 10^9 + 7 ) $
را خروجی دهید که
$ q^{-1} $
وارون ضربی $ q $
باقیمانده بر
$ 10^9 + 7 $
است.
**توضیحات :** زیر دنباله ای از یک کد $s$ , دنباله ای است که از پاک کردن برخی اعضای $s$ ( که میتواند تمامی اعضا یا هیچکدام از آنها هم باشد ) به دست می آید . و یک کد $2^n$ زیردنباله دارد.
# ورودی
ورودی به صورت $T$ تستکیس مختلف میآید که برای هرکدام باید مسئله را جداگانه حل کنید.
در خط اول ابتدا عدد $T$ و سپس در $T$ خط بعد به ترتیب برای هر تستکیس عدد $n$ و عدد ثابت $k$ می آید که به ترتیب نشان دهنده طول کد قرعه کشی و عدد ثابت $k$ است.
$$ 1 \leq T \leq 50$$
$$ 1 \leq n \leq 10^{18} $$
$$ 1 \leq k \leq 50$$
تضمین میشود جمع مقادیر $k$ بر روی همه تستکیسها حداکثر $50$ است.
# خروجی
در یک خط، باید امیدریاضی میزان خوش یُمن بودن کد قرعه کشی محمدسام را حساب کنید ( در حالی که این کد به صورت تصادفی و با احتمال برابر برای او انتخاب خواهد شد )
# مثال
## ورودی نمونه ۱
```
3
1 1
5 2
10 10
```
## خروجی نمونه ۱
```
0
148148169
525754884
```