The innovative hanger consists of n levels of interconnected rods. Level i (with i=[0,n−1] ) consists of 2i 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,2i]) 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 2n. For example, the hanger for n = 3 looks like this:
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 109+7 on which Masha must hang her jacket at the k-th step.
The only line contains two integers n and k .
Print one integer — the number of the hook on which Masha should hang her jacket at the k-th step modulo 109+7.
n [1,106]
k [1,min(2n,1018)]
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.