Kbin
시간 제한1초메모리 제한512 MB
이진수로 나타냈을 때 1이 정확히 k개인 수 가운데 N보다 작은 모든 수의 합을 구해 1234567로 나눈 나머지를 출력한다.
문제
어떤 자연수의 이진수 표현에 1이 정확히 k개 있으면 그 수를 k-이진수라고 부른다. 예를 들어 23은 이진수로 10111이고 1이 4개이므로 4-이진수이다.
N과 k가 주어질 때, N보다 작은 모든 k-이진수의 합 S를 구하시오. 합이 매우 클 수 있으므로 1234567로 나눈 나머지를 구한다.
입력
표준 입력에 N과 k가 공백 하나를 사이에 두고 주어진다.
출력
표준 출력에 S를 1234567로 나눈 나머지를 출력한다.
제한
- 2 ≤ N ≤ 10^15
- 0 ≤ K ≤ 50
힌트
- 1 – 1
- 2 – 10
- 3 – 11
- 4 – 100
- 5 – 101
- 6 – 110
- 7 – 111
- 8 – 1000
- 9 – 1001
- 10 – 1010
- 11 – 1011
- 12 – 1100
- 13 – 1101
- 14 – 1110
S=7+11+13+14=45