{"trustable":false,"sections":[{"title":"statement","value":{"format":"HTML","content":"Given an integer k and a number of bits b (1 ≤ b ≤ 128), calculate the total number of 1 bits in the\nbinary representations of multiples of k between 0 and 2\u003csup\u003eb\u003c/sup\u003e − 1 (inclusive), modulo 1,000,000,009."}},{"title":"Input","value":{"format":"HTML","content":"The input will consist of two integers k and b on a single line, with (1 ≤ k ≤ 1000) and (1 ≤ b ≤ 128)."}},{"title":"Output","value":{"format":"HTML","content":"Write your result as an integer on a single line"}},{"title":"sample input 1:","value":{"format":"HTML","content":"1 4"}},{"title":"sample output 1:","value":{"format":"HTML","content":"32"}},{"title":"sample input 2:","value":{"format":"HTML","content":"10 5"}},{"title":"sample output 2:","value":{"format":"HTML","content":"8"}},{"title":"sample input 3:","value":{"format":"HTML","content":"3 28"}},{"title":"sample output 3:","value":{"format":"HTML","content":"252698795"}}]}