Transforming Sequence

7000ms

262144K

Description:

Let's define the transformation P of a sequence of integers a₁, a₂, ..., a_n as b₁, b₂, ..., b_n, where b_i = a₁ | a₂ | ... | 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⁹ + 7.

Input:

The only line of the input contains two integers n and k (1 ≤ n ≤ 10¹⁸, 1 ≤ k ≤ 30 000).

Output:

Print a single integer — the answer to the problem modulo 10⁹ + 7.

Sample Input:

1 2

Sample Output:

Sample Input:

2 3

Sample Output:

Sample Input:

3 3

Sample Output:

Informação

Provedor Codeforces

Código CF623E