비트 세기

값 $k$와 비트 수 $b$가 주어진다. $0$ 이상 $2^b-1$ 이하의 $k$의 배수 각각을 이진수로 나타냈을 때, 등장하는 1 비트의 총 개수를 구하시오.

각 입력은 하나의 테스트 케이스로 이루어진다. 프로그램은 서로 다른 입력에 대해 여러 번 실행될 수 있다.

각 테스트 케이스는 한 줄로 이루어지며, 공백으로 구분된 두 정수 $k$ ($1 \le k \le 1{,}000$)와 $b$ ($1 \le b \le 128$)가 주어진다. $k$와 $b$의 의미는 위에서 설명한 것과 같다.

$0$ 이상 $2^b-1$ 이하의 $k$의 배수 각각을 이진수로 나타냈을 때 등장하는 1 비트의 총 개수를 한 정수로 출력한다. 이 값은 매우 클 수 있으므로 $10^9+9$로 나눈 나머지를 출력한다.

두 번째 예제를 보자. $k=10$, $b=5$이다.

$2^5-1 = 31$이다. $0$ 이상 $31$ 이하의 $10$의 배수는 $10$, $20$, $30$이다.

• $10 = 01010_2$ (1 비트 2개)
• $20 = 10100_2$ (1 비트 2개)
• $30 = 11110_2$ (1 비트 4개)

따라서 1 비트는 모두 $2+2+4=8$개이다.