+ محدودیت زمان: 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 ```