Sequence Transformation

Count length-n integer sequences with entries in [1, 2^k) whose prefix bitwise-OR values are strictly increasing, for n up to 1e18 and k up to 30000.

Hard8CombinatoricsBit manipulationMathDynamic programmingNo attempts yetTime limit10sMemory limit512 MB

Description

Examples3

Problem

Applying operation $P$ to the sequence $A = a_1, a_2, \dots, a_n$ produces the sequence $B = b_1, b_2, \dots, b_n$ , where $b_i = a_1 \mathbin{|} a_2 \mathbin{|} \cdots \mathbin{|} a_i$ and $|$ is the bitwise OR operation.

Apply $P$ to every sequence of length $n$ whose entries are integers at least $1$ and less than $2^k$ . Write a program that counts the sequences whose result is increasing, that is, $b_1 < b_2 < \cdots < b_n$ .

Input

The first line contains $n$ and $k$ , separated by a space. ( $1 \le n \le 10^{18}$ , $1 \le k \le 30000$ )

Output

Print the number of such sequences modulo $10^9+7$ on the first line.