puts gets.to_i.to_s(2).count('1') % 1004535809