시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB39302884.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

1 4

예제 출력 1

32

예제 입력 2

10 5

예제 출력 2

8

예제 입력 3

100 7

예제 출력 3

3

예제 입력 4

3 28

예제 출력 4

252698795

예제 입력 5

11 128

예제 출력 5

856188165

예제 입력 6

1 26

예제 출력 6

872415232

예제 입력 7

876 128

예제 출력 7

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.