{"problem":{"name":"Twin Binary Trees","description":{"content":"Inspired by the tv series _Stranger Things_, bear Limak is going for a walk between two mirror worlds. There are two perfect binary trees of height $H$, each with the standard numeration of vertices f","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc047_d"},"statements":[{"statement_type":"Markdown","content":"Inspired by the tv series _Stranger Things_, bear Limak is going for a walk between two mirror worlds.\nThere are two perfect binary trees of height $H$, each with the standard numeration of vertices from $1$ to $2^H-1$. The root is $1$ and the children of $x$ are $2 \\cdot x$ and $2 \\cdot x + 1$.\nLet $L$ denote the number of leaves in a single tree, $L = 2^{H-1}$.\nYou are given a permutation $P_1, P_2, \\ldots, P_L$ of numbers $1$ through $L$. It describes $L$ _special_ edges that connect leaves of the two trees. There is a special edge between vertex $L+i-1$ in the first tree and vertex $L+P_i-1$ in the second tree.\n![image](https://img.atcoder.jp/agc047/nice_wide_example.png)\n_drawing for the first sample test, permutation $P = (2, 3, 1, 4)$, special edges in green_\nLet's define _product_ of a cycle as the product of numbers in its vertices. Compute the sum of products of all simple cycles that have **exactly two special edges**, modulo $(10^9+7)$.\nA simple cycle is a cycle of length at least 3, without repeated vertices or edges.\n\n## Constraints\n\n*   $2 \\leq H \\leq 18$\n*   $1 \\leq P_i \\leq L$ where $L = 2^{H-1}$\n*   $P_i \\neq P_j$ (so this is a permutation)\n\n## Input\n\nInput is given from Standard Input in the following format (where $L = 2^{H-1}$).\n\n$H$\n$P_1$ $P_2$ $\\cdots$ $P_L$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc047_d","tags":[],"sample_group":[["3\n2 3 1 4","121788\n\nThe following drawings show two valid cycles (but there are more!) with products $2 \\cdot 5 \\cdot 6 \\cdot 3 \\cdot 1 \\cdot 2 \\cdot 5 \\cdot 4 = 7200$ and $1 \\cdot 3 \\cdot 7 \\cdot 7 \\cdot 3 \\cdot 1 \\cdot 2 \\cdot 5 \\cdot 4 \\cdot 2 = 35280$. The third cycle is invalid because it doesn't have exactly two special edges.\n![image](https://img.atcoder.jp/agc047/3_trees_font.png)"],["2\n1 2","36\n\nThe only simple cycle in the graph indeed has two special edges, and the product of vertices is $1 \\cdot 3 \\cdot 3 \\cdot 1 \\cdot 2 \\cdot 2 = 36$."],["5\n6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1","10199246"]],"created_at":"2026-03-03 11:01:14"}}