p gets.to_i.to_s(2).chars.inject(0){|s,e|s+(e=="1" ? 1 : 0)}%10045358091004535809