No tag edit access

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-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/28/2017 08:32:59 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|