시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 27 | 9 | 6 | 37.500% |
수열 A = a1, a2, ..., an에 연산 P를 적용하면 수열 B = b1, b2, ..., bn이 된다. 이때, bi = a1 | a2 | ... | ai 이며, |는 비트 OR 연산이다.
1보다 크거나 같고, 2k보다 작은 정수로 이루어진 길이가 n인 모든 수열에 연산 P를 적용시키려고 한다. 이때, 연산을 적용한 결과가 오름차순(b1 < b2 < ... < bn)이 되는 수열의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 n과 k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 30,000)이 주어진다.
첫째 줄에 수열의 개수를 109+7로 나눈 나머지를 출력한다.
1 2
3
2 3
30
3 3
48