Problems
Innovative hanger
Innovative hanger
The innovative hanger consists of $n$ levels of interconnected rods. Level $i$ (with $i = [0, n-1]$ ) consists of $2^i$ horizontal rods.
The middle of the rod at $0$ is attached to the wall. At all other levels, the middle of the $j$-th (for $j= [1, 2^i]$) rod is attached to the left side of the $j/2$-th rod (rounded up when dividing by $2$) of the previous level for odd $j$, or to the right side of the same rod if $j$ is even. There are coat hooks at both ends of each rod on the last level. The hooks are numbered from left to right with numbers from $1$ to $2^n$.
For example, the hanger for $n$ = $3$ looks like this:
\includegraphics{https://static.e-olymp.com/content/59/59dc0f4b834bc8da66981e273e8938017ee59d8e.png}
Masha wants to hang all her jackets on her new hanger. The weight of each jacket is equal to one. To avoid breaking the fragile structure, she must hang the jackets in such an order that the difference between the total weight at the left end of any rod and the total weight at the right end of the same rod after adding another jacket is either $0$ or $1$. (According to the laws of physics, the difference can be equal to $-1$, but Masha considers the skew to the right to be terrible.) The rods are so thin that their weight can be neglected. Masha has heard a lot about your professionalism and asks for your help. Write a program that, given $n$ and $k$, finds the number of the hook modulo $10^9+7$ on which Masha must hang her jacket at the $k$-th step.
\InputFile
The only line contains two integers $n$ and $k$ .
\OutputFile
Print one integer — the number of the hook on which Masha should hang her jacket at the $k$-th step modulo $10^9+7$.
\subsection{Limitations}
\begin{itemize}
\item $n$ $[1, 10^6]$
\item $k$ $[1, min(2^n, 10^18)]$
\end{itemize}
\Note
In the first example, the hooks should be used in the following order: $1$, $5$, $3$, $7$, $2$, $6$, $4$, $8$.
In the second step, Masha must hang her jacket on hook number $5$.
In the second example, the order of hooks is: $1$, $17$, $9$, $25$, $5$, $21$, $13$, $29$, $3$, $19$, etc.
Input example #1
3 2
Output example #1
5
Input example #2
5 10
Output example #2
19