Funny Bits

Funny Bits

Problem Statement

Let $a$ be the average (rounded down) of all positive integers up to $k$-bits with $n$ bits set.

(A bit is "set" if it equals one. For example, in the binary number 1101, there is a total of 3 bits set.)

Given $k$ and $a$, find $n$.

Input

Your only line of input will contain two space-separated integers, $k$ and $a$.

Output

One line, containing only the number $n$.

Constraints

For all test cases:

• $1 \le k \le 30$
• $1 \le a \le 10^{10}$
• There will always be a unique valid $n$ for the given $k$ and $a$.

Sample Test Cases

Example 1

4 7

2

Explanation

If we let $n = 2$, then there are a total of $6$ integers (3, 5, 6, 9, 10, 12) that can be represented with at most $k = 4$ bits with exactly $n = 2$ bits set:

3 = 0011
5 = 0101
6 = 0110
9 = 1001
10 = 1010
12 = 1100

The average of these numbers is $7.5$, which rounds down to $7$. Thus, $n = 2$.

Example 2

3 2

1

Explanation

If we let $n = 1$, then there are a total of $3$ integers (1, 2, 4) that can be represented with at most $k = 3$ bits with exactly $n = 1$ bit set:

1 = 001
2 = 010
4 = 100

The average of these numbers is $2.33$, which rounds down to $2$. Thus, $n = 2$.

Example 3

7 90

5

Explanation

If we let $n = 5$, then there are a total of $21$ integers that can be represented with at most $k = 7$ bits with exactly $n = 5$ bits set. These numbers sum to $1905$ and averages to $90.71$, which rounds down to $90$. Thus, $n = 5$.