시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 6 6 85.714%

문제

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.

• 10 = 01010b (2 1-bits)
• 20 = 10100b (2 1-bits)
• 30 = 11110b (4 1-bits)

That’s a total of 2+2+4=8 1-bits.