수열 변환

시간 제한10초메모리 제한512 MB

요약

항목이 [1, 2^k)에 속하는 길이 n 정수 수열 중 접두사 비트 OR 값이 순증가하는 수열의 개수를 구한다. n은 1e18, k는 30000까지이다.

난이도: 어려움10점 중 8점
유형: 조합론, 비트 연산, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

수열 $A = a_1, a_2, \dots, a_n$ 에 연산 $P$ 를 적용하면 수열 $B = b_1, b_2, \dots, b_n$ 이 된다. 이때 $b_i = a_1 \mathbin{|} a_2 \mathbin{|} \cdots \mathbin{|} a_i$ 이고, $|$ 는 비트 OR 연산이다.

$1$ 이상 $2^k$ 미만의 정수로 이루어진 길이 $n$ 의 수열 전체에 연산 $P$ 를 적용한다. 결과가 오름차순, 즉 $b_1 < b_2 < \cdots < b_n$ 이 되는 수열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $n$ 과 $k$ 가 공백으로 구분되어 주어진다. ( $1 \le n \le 10^{18}$ , $1 \le k \le 30000$ )

출력

첫째 줄에 조건을 만족하는 수열의 개수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
1 2
```
예상 출력
```
3
```
예제 2
입력
```
2 3
```
예상 출력
```
30
```
예제 3
입력
```
3 3
```
예상 출력
```
48
```