The Shining Tower

A full binary tree named the Shining Tower has nodes numbered from \(1\) to \(2^n-1\) with node \(1\) as its root, and it has \(n\) levels. For every non‐leaf node \(i\), its left and right children have numbers \(2 \times i\) and \(2 \times i+1\) respectively.

Dorothy wants to assign a weight to every node. The weight of each node is an integer in the range \([1,2^n-1]\) and all weights must be distinct.

For a node \(u\) with weight \(val_u\) and children set \(S(u)\), define its energy value \(f(u)\) as \[ f(u)= val_u + \sum_{v\in S(u)}f(v) \,, \] which means that \(f(u)\) is the sum of weights in the subtree rooted at \(u\). The total energy of the tree is \(\sum_{i=1}^{2^n-1} f(i)\).

The total energy is maximized if we assign larger weights to nodes that appear many times in these sums (i.e. nodes with larger depth). In fact, note that the total energy can be written as \[ \sum_{u=1}^{2^n-1} f(u)=\sum_{v=1}^{2^n-1}(d(v)\cdot val_v)\,, \] where \(d(v)\) is the depth of node \(v\) (with the root having depth \(1\)). Hence, to maximize the total energy, one must assign the largest weights to the nodes with the greatest depth. However, when several nodes have the same depth, the assignment within that level can be chosen arbitrarily without changing the total energy.

Under an assignment that maximizes the total energy, Dorothy wonders: What is the maximum possible value of \(f(p)\) for a given node \(p\)? Since the answer might be huge, print it modulo \(10^9+7\).

Note on optimal assignment: For each depth \(L\) (where \(1\le L\le n\)), the nodes at that level must be assigned exactly the integers from \(2^{L-1}\) to \(2^L-1\) (in some order). To maximize \(f(p)\) (the sum of weights in the subtree rooted at \(p\)), for each level \(L\) in the subtree of \(p\) (i.e. for \(L\ge d(p)\)) the nodes belonging to the subtree should receive the largest available numbers among all nodes at level \(L\).

Hint: If \(d\) is the depth of node \(p\), then its subtree spans levels \(d, d+1, \ldots, n\). At level \(L\), the total set of numbers is \(\{2^{L-1},2^{L-1}+1,\ldots,2^L-1\}\), and there are \(2^{L-d}\) nodes in \(p\u2019s subtree at that level. Thus, the maximum contribution from level \(L\) is the sum of the largest \(2^{L-d}\) numbers in that set. This sum for level \(L\) is:

\[ \text{term}_L = 2^{L-d} \times (2^L-1) - \frac{(2^{L-d}-1)\times 2^{L-d}}{2} \,, \]

and \(f(p)\) equals the sum of \(\text{term}_L\) for \(L=d, d+1, \ldots, n\).

inputFormat

The input consists of two space-separated integers \(n\) and \(p\) where \(n\) is the number of levels in the full binary tree and \(p\) is the node number for which you need to compute \(f(p)\) under the optimal assignment. \(1 \le p \le 2^n-1\).

outputFormat

Output a single integer representing the maximum possible value of \(f(p)\) modulo \(10^9+7\).

sample

3 2

16