function Main(INPUT){
  const input=INPUT.split("\n");
  let N=BigInt(input[0]);
  const max=N*2n;
  let normal=0n;
  while(N>0n){
    normal+=N;
    N/=2n;
  }
  console.log(((max-normal)%1004535809n).toString());
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));