import java.util.HashMap;
import java.util.Map;

public class Euler463 {
    private static final long MOD = 1000000000L;
    private final Map<Long, Long> sumCache = new HashMap<>();
    private final Map<Long, Long> oddCache = new HashMap<>();

    public Euler463() {
        sumCache.put(0L, 0L);
        sumCache.put(1L, 1L);
        oddCache.put(0L, 0L);
        oddCache.put(1L, 1L);
    }

    private long fMod(long n) {
        long x = n;
        while ((x & 1) == 0) {
            x >>= 1;
        }
        long rev = 0;
        while (x > 0) {
            rev = (rev << 1) | (x & 1);
            x >>= 1;
        }
        return rev % MOD;
    }

    private long sumMod(long n) {
        if (sumCache.containsKey(n)) {
            return sumCache.get(n);
        }
        long val;
        if ((n & 1) == 0) {
            long half = n >> 1;
            val = (sumMod(half) + oddSumMod(half)) % MOD;
        } else {
            val = (sumMod(n - 1) + fMod(n)) % MOD;
        }
        if (val < 0)
            val += MOD;
        sumCache.put(n, val);
        return val;
    }

    private long oddSumMod(long n) {
        if (oddCache.containsKey(n)) {
            return oddCache.get(n);
        }
        long val;
        if ((n & 1) == 0) {
            long half = n >> 1;
            val = (-1 + 5 * oddSumMod(half) - 3 * sumMod(half - 1)) % MOD;
        } else {
            long half = n >> 1;
            val = (oddSumMod(n - 1) + 2 * fMod(n) - fMod(half)) % MOD;
        }
        if (val < 0)
            val += MOD;
        oddCache.put(n, val);
        return val;
    }

    public static String solve() {
        long n = 1L;
        for (int i = 0; i < 37; i++) {
            n *= 3;
        }
        Euler463 solver = new Euler463();
        return Long.toString(solver.sumMod(n));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}