시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 39 | 30 | 28 | 84.848% |
Given a value k and a number of bits b, calculate the total number of 1-bits in the binary representations of all multiples of k that are between 0 and 2b-1 (inclusive).
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.
Each test case will consist of a single line containing two space-separated integers k (1 ≤ k ≤ 1,000) and b (1 ≤ b ≤ 128), where k and b are as described above.
Output a single integer, which is the total number of 1-bits in the binary representations of all multiples of k that are between 0 and 2b-1 (inclusive). Since this number may be very large, output it modulo 109+9.
1 4
32
10 5
8
100 7
3
3 28
252698795
11 128
856188165
1 26
872415232
876 128
530649653
Consider the second sample: k=10 and b=5.
25-1 = 31. All the multiples of 10 between 0 and 31 are: 10, 20 and 30.
That’s a total of 2+2+4=8 1-bits.