import java.util.stream.IntStream;

public class Euler973 {
    static final long MOD = 1000000007;

    static long power(long b, long e) {
        long r = 1;
        b %= MOD;
        while (e > 0) {
            if ((e & 1) != 0)
                r = (r * b) % MOD;
            b = (b * b) % MOD;
            e >>= 1;
        }
        return r;
    }

    static long getStable(int k, int n) {
        long s = 1L << k;
        if (n == s)
            return 1;
        long t1 = (n - s + 2) % MOD;
        long exp = n - s - 1;
        return (t1 * power(2, exp)) % MOD;
    }

    static long solveBit(int k, int n) {
        long s = 1L << k;
        if (n < s)
            return 0;
        long es = 1L << (k + 1);
        if (n < es)
            return getStable(k, n);

        long[] dp = new long[n + 1];
        for (int i = (int) s; i < (int) es; ++i) {
            dp[i] = getStable(k, i);
        }

        long cSum = 0;
        long ub = 1L << k;
        if (ub > 2) {
            for (int i = (int) es - 2; i >= (int) (es - ub + 1); --i) {
                cSum = (cSum + dp[i]) % MOD;
            }
        }

        for (int i = (int) es; i <= n; ++i) {
            long t1 = (3 * dp[i - 1]) % MOD;
            long t3 = (4 * dp[i - (int) ub]) % MOD;
            long t4 = (4 * dp[i - (int) ub - 1]) % MOD;
            long val = (t1 - cSum - t3 + t4) % MOD;
            dp[i] = (val + 2 * MOD) % MOD;

            if (ub > 2) {
                cSum = (cSum + dp[i - 1]) % MOD;
                cSum = (cSum - dp[i - (int) ub + 1] + MOD) % MOD;
            }
        }

        return dp[n];
    }

    static long solveX(int n) {
        long tot = 0;
        if (n % 2 != 0) {
            tot = (power(2, n - 1) - 1 + MOD) % MOD;
        }

        int maxK = 0;
        for (int k = 1; k < 20; ++k) {
            if ((1L << k) > n)
                break;
            maxK = k;
        }

        long sumP = IntStream.rangeClosed(1, maxK)
                .parallel()
                .mapToLong(k -> {
                    long val = solveBit(k, n);
                    return (val * power(2, k)) % MOD;
                })
                .sum() % MOD;

        return (tot + sumP) % MOD;
    }

    public static String solve() {
        return Long.toString(solveX(10000));
    }

    public static void main(String[] args) {
        if (solveX(2) != 2) {
            System.out.println("Validation failed");
            return;
        }
        if (solveX(4) != 14) {
            System.out.println("Validation failed");
            return;
        }
        if (solveX(10) != 1418) {
            System.out.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}