시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 1 1 100.000%

문제

We call the k-binary number a natural number which has in its binary representation exactly k digits of 1. For example, the 23 is a 4-binary number because the binary representation is 10111 and contains 4 digits of 1.

Given the N and k values, calculate the sum S of all k-binary numbers which are strictly lower than N. Because the sum is very large, you have to calculate modulo 1234567.

입력

The standard input contains the values N and k separated by a single space.

출력

The standard output will contain the number S modulo 1234567.

제한

  • 2 ≤ N ≤ 1015
  • 0 ≤ K ≤ 50

예제 입력 1

15 3

예제 출력 1

45

힌트

  • 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

출처

Olympiad > Junior Balkan Olympiad in Informatics > JBOI 2018 1번