Sequence Transformation

Time limit10sMemory limit512 MB

Summary

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.

Level: Hard8 of 10
Topics: Combinatorics, Bit manipulation, Math, Dynamic programming
Solved: No attempts yet

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.

Examples3

Example 1
Input
```
1 2
```
Expected output
```
3
```
Example 2
Input
```
2 3
```
Expected output
```
30
```
Example 3
Input
```
3 3
```
Expected output
```
48
```