Codeforces Round 818 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

constructive algorithms

greedy

math

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Madoka and The Corruption Scheme

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMadoka decided to entrust the organization of a major computer game tournament "OSU"!

In this tournament, matches are held according to the "Olympic system". In other words, there are $$$2^n$$$ participants in the tournament, numbered with integers from $$$1$$$ to $$$2^n$$$. There are $$$n$$$ rounds in total in the tournament. In the $$$i$$$-th round there are $$$2^{n - i}$$$ matches between two players (one of whom is right, the other is left), after which the winners go further along the tournament grid, and the losing participants are eliminated from the tournament. Herewith, the relative order in the next round does not change. And the winner of the tournament — is the last remaining participant.

But the smaller the participant's number, the more he will pay Madoka if he wins, so Madoka wants the participant with the lowest number to win. To do this, she can arrange the participants in the first round as she likes, and also determine for each match who will win — the participant on the left or right.

But Madoka knows that tournament sponsors can change the winner in matches no more than $$$k$$$ times. (That is, if the participant on the left won before the change, then the participant on the right will win after the change, and if the participant on the right won, then the participant on the left will win after the change).

Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors. But since the answer can be very large, output it modulo $$$10^9 + 7$$$. Note that we need to minimize the answer, and only then take it modulo.

Input

The first and the only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5, 1 \le k \le \min(2^n - 1, 10^9)$$$) — the number of rounds in the tournament and the number of outcomes that sponsors can change.

Output

Print exactly one integer — the minimum number of the winner modulo $$$10^9 + 7$$$

Examples

Input

1 1

Output

2

Input

2 1

Output

3

Input

3 2

Output

7

Note

In the first example, there is only one match between players $$$1$$$ and $$$2$$$, so the sponsors can always make player $$$2$$$ wins.

The tournament grid from the second example is shown in the picture in the statement.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 17:54:16 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|