Count the Bits

Interview

Time limit2sMemory limit512 MB

Summary

Given k and b, count the total number of 1-bits in all multiples of k from 0 to 2^b-1, and print the sum modulo 10^9+9.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Math
Solved: No attempts yet

Problem

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 $2^b-1$ (inclusive).

Input

Each input consists of a single test case. Your program may be run multiple times on different inputs.

Each test case consists of a single line containing two space-separated integers $k$ ( $1 \le k \le 1{,}000$ ) and $b$ ( $1 \le b \le 128$ ), where $k$ and $b$ are as described above.

Output

Output a single integer, the total number of 1-bits in the binary representations of all multiples of $k$ that are between $0$ and $2^b-1$ (inclusive). Since this number may be very large, output it modulo $10^9+9$ .

Hint

Consider the second sample: $k=10$ and $b=5$ .

$2^5-1 = 31$ . All the multiples of $10$ between $0$ and $31$ are $10$ , $20$ and $30$ .

$10 = 01010_2$ (2 1-bits)
$20 = 10100_2$ (2 1-bits)
$30 = 11110_2$ (4 1-bits)

That is a total of $2+2+4=8$ 1-bits.

Examples5

Example 1
Input
```
1 4
```
Expected output
```
32
```
Example 2
Input
```
10 5
```
Expected output
```
8
```
Example 3
Input
```
100 7
```
Expected output
```
3
```
Example 4
Input
```
3 28
```
Expected output
```
252698795
```
Example 5
Input
```
11 128
```
Expected output
```
856188165
```