جایگشت $a^{(0)}=\langle a^{(0)}_1,a^{(0)}_2,\ldots,a^{(0)}_{2^k}\rangle$ از اعداد $1$ تا $2^k$ را در نظر بگیرید. این اعداد در یک تورنمنت حذفی شرکت می‌کنند. در دور اول، عضوهای اول و دوم با هم، عضوهای سوم و چهارم با هم و به همین ترتیب بازی می‌کنند. در هر بازی عدد بزرگ‌تر برنده می‌شود و به دور بعد می‌رود. ترتیب برنده‌ها در دور بعد حفظ می‌شود و بازی‌ها تا مشخص‌شدن قهرمان ادامه پیدا می‌کنند.

به بیان دقیق‌تر، برای هر $1\leq t\leq k$، دنباله‌ی برنده‌های دور $t$ را با $a^{(t)}$ نشان می‌دهیم؛ این دنباله $2^{k-t}$ عضو دارد و $$ a^{(t)}_i=\max\bigl(a^{(t-1)}_{2i-1},a^{(t-1)}_{2i}\bigr). $$

اکنون دنباله‌ی نهایی $b$ را با نوشتن طبقه‌های درخت تورنمنت از پایین به بالا می‌سازیم: $$ b=\langle a^{(0)},a^{(1)},\ldots,a^{(k)}\rangle. $$ وارونگیِ $b$ یک جفت اندیس $(i,j)$ است که $i<j$ و $b_i>b_j$ باشد.

از بین تمام $(2^k)!$ جایگشت ممکن، یکی را به‌صورت تصادفی و با احتمال برابر انتخاب می‌کنیم و فرایند بالا را روی آن انجام می‌دهیم. امید ریاضی تعداد وارونگی‌های دنباله‌ی نهایی را با $E$ نشان می‌دهیم.

ابتدا مقدار $E$ را به پیمانه‌ی $M=10^9+7$ حساب کنید. منظور از پیمانه‌کردن یک عدد گویا مانند $\frac pq$، مقدار $p\times q^{-1}\pmod M$ است. اگر نماینده‌ی این مقدار در بازه‌ی $[0,M-1]$ برابر $R$ باشد، در هر بخش باید باقی‌مانده‌ی $R$ بر $\Delta$ را چاپ کنید.

برای مثال، اگر $k=2$ و $a^{(0)}=\langle3,1,2,4\rangle$ باشد، داریم $a^{(1)}=\langle3,4\rangle$ و $a^{(2)}=\langle4\rangle$؛ در نتیجه $b=\langle3,1,2,4,3,4,4\rangle$ است و $3$ وارونگی دارد.

تمام پاسخ‌های ارائه‌شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

بخش اول (۷ نمره): $k=2$ است.

بخش دوم (۱۹ نمره): $k=9$ است.

بخش سوم (۲۳ نمره): $k=17$ است.

بخش چهارم (۲۲ نمره): $k=1405$ است.

بخش پنجم (۲۹ نمره): $k=14051405$ است.