#!/usr/bin/env python3
import math
N = int(input())
sum = 0
max = 2 * N
while N > 0:
    sum += N
    N = N // 2
print((max - sum) % 1004535809)