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

## 문제

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.