p gets.to_i.to_s(2).count(?1)%1004535809