AIM Tech Round (Div. 1) |
---|

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

dp

fft

math

*3300

No tag edit access

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

×
E. Transforming Sequence

time limit per test

7 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet's define the transformation *P* of a sequence of integers *a*_{1}, *a*_{2}, ..., *a*_{n} as *b*_{1}, *b*_{2}, ..., *b*_{n}, where *b*_{i} = *a*_{1} | *a*_{2} | ... | *a*_{i} for all *i* = 1, 2, ..., *n*, where | is the bitwise OR operation.

Vasya consequently applies the transformation *P* to all sequences of length *n* consisting of integers from 1 to 2^{k} - 1 inclusive. He wants to know how many of these sequences have such property that their transformation is a strictly increasing sequence. Help him to calculate this number modulo 10^{9} + 7.

Input

The only line of the input contains two integers *n* and *k* (1 ≤ *n* ≤ 10^{18}, 1 ≤ *k* ≤ 30 000).

Output

Print a single integer — the answer to the problem modulo 10^{9} + 7.

Examples

Input

1 2

Output

3

Input

2 3

Output

30

Input

3 3

Output

48

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 19:13:58 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|