import java.util.ArrayList;

public class Euler806 {

    static final long MOD = 1000000007L;

    static long addmod(long a, long b) {
        long r = a + b;
        if (r >= MOD)
            r -= MOD;
        return r;
    }

    static long submod(long a, long b) {
        return a >= b ? a - b : a + MOD - b;
    }

    static long mulmod(long a, long b) {
        return (a * b) % MOD;
    }

    static long modpow(long a, long e) {
        long r = 1L;
        a %= MOD;
        while (e > 0) {
            if ((e & 1L) == 1L)
                r = mulmod(r, a);
            a = mulmod(a, a);
            e >>= 1L;
        }
        return r;
    }

    static class Comb {
        int maxI;
        long[] fact, invfact, pow2, inv;

        Comb(int maxI_) {
            maxI = Math.max(0, maxI_);
            fact = new long[maxI + 1];
            invfact = new long[maxI + 1];
            pow2 = new long[maxI + 1];
            inv = new long[maxI + 1];

            fact[0] = 1;
            pow2[0] = 1;
            invfact[0] = 1;

            for (int i = 1; i <= maxI; i++) {
                fact[i] = mulmod(fact[i - 1], i);
                pow2[i] = addmod(pow2[i - 1], pow2[i - 1]);
            }
            invfact[maxI] = modpow(fact[maxI], MOD - 2);
            for (int i = maxI; i >= 1; i--) {
                invfact[i - 1] = mulmod(invfact[i], i);
            }
            if (maxI >= 1) {
                inv[1] = 1;
                for (int i = 2; i <= maxI; i++) {
                    inv[i] = MOD - mulmod(MOD / i, inv[(int) (MOD % i)]);
                }
            }
        }
    }

    static long H(Comb C, int u, int v, int w) {
        if (u < 0 || v < 0 || w < 0)
            return 0;
        int n = u + v + w;
        if (((u ^ n) & 1) != 0 || ((v ^ n) & 1) != 0 || ((w ^ n) & 1) != 0)
            return 0;

        int A = (v + w) / 2;
        int B = (u + w) / 2;
        int Cc = (u + v) / 2;

        int lo = (n + 2) / 3;
        if (A > lo)
            lo = A;
        if (B > lo)
            lo = B;
        if (Cc > lo)
            lo = Cc;

        int hi = n / 2;
        if (lo > hi)
            return 0;

        int i0 = lo;
        int k0 = n - 2 * i0;
        int p0 = i0 - A;
        int q0 = i0 - B;
        int r0 = i0 - Cc;

        long coef = C.fact[i0];
        coef = mulmod(coef, C.invfact[k0]);
        coef = mulmod(coef, C.invfact[p0]);
        coef = mulmod(coef, C.invfact[q0]);
        coef = mulmod(coef, C.invfact[r0]);
        coef = mulmod(coef, C.pow2[k0]);

        long s = coef;
        long inv4 = C.inv[4];
        int k = k0;

        for (int i = i0; i < hi; i++) {
            long num = mulmod(i + 1, mulmod(k, k - 1));
            long den = mulmod(C.inv[i + 1 - A], mulmod(C.inv[i + 1 - B], C.inv[i + 1 - Cc]));
            coef = mulmod(coef, num);
            coef = mulmod(coef, den);
            coef = mulmod(coef, inv4);
            s = addmod(s, coef);
            k -= 2;
        }

        return s;
    }

    static long gCoeff(Comb C, int a, int b, int c) {
        long res = 0;
        res = addmod(res, H(C, a, b, c));
        res = addmod(res, H(C, a - 1, b, c));
        res = addmod(res, H(C, a, b, c - 1));
        res = addmod(res, H(C, a - 1, b - 1, c));
        res = addmod(res, H(C, a, b - 1, c - 1));
        res = submod(res, H(C, a, b - 2, c));
        return res;
    }

    static class Triple {
        int a, b, c;

        Triple(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    static ArrayList<Triple> enumerateXorTriples(int n) {
        ArrayList<Triple> cur = new ArrayList<>();
        cur.add(new Triple(0, 0, 0));
        if ((n & 1) == 1)
            return new ArrayList<>();

        for (int bit = 1; (1 << bit) <= n * 2 || bit <= 20; bit++) {
            if (((n >> bit) & 1) == 1) {
                int v = 1 << (bit - 1);
                ArrayList<Triple> nxt = new ArrayList<>();
                for (Triple t : cur) {
                    nxt.add(new Triple(t.a, t.b + v, t.c + v));
                    nxt.add(new Triple(t.a + v, t.b, t.c + v));
                    nxt.add(new Triple(t.a + v, t.b + v, t.c));
                }
                cur = nxt;
            }
            if ((1 << bit) > n && bit > 20)
                break;
        }

        ArrayList<Triple> out = new ArrayList<>();
        for (Triple t : cur) {
            if (t.a + t.b + t.c == n && ((t.a ^ t.b ^ t.c) == 0)) {
                out.add(t);
            }
        }
        return out;
    }

    static long solveFast(Comb C, int n) {
        if (n < 0)
            return 0;
        if ((n & 1) == 1)
            return 0;
        ArrayList<Triple> triples = enumerateXorTriples(n);

        long K = 0;
        for (Triple t : triples) {
            K = addmod(K, gCoeff(C, t.a, t.b, t.c));
        }

        long inv2 = (MOD + 1) / 2;
        long pow2n = modpow(2, n);
        long ans = mulmod(K, submod((int) pow2n, 1));
        ans = mulmod(ans, (int) inv2);
        return ans;
    }

    public static String solve() {
        int n = 100000;
        int maxI = Math.max(n, 10) / 2 + 5;
        Comb C = new Comb(maxI);
        return Long.toString(solveFast(C, n));
    }

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