import java.util.ArrayList;
import java.util.List;

public class Euler614 {
    static final int MOD = 1000000007;

    static int[] buildA015128(int limit) {
        int[] a = new int[limit + 1];
        a[0] = 1;

        List<Integer> squares = new ArrayList<>();
        List<Integer> signs = new ArrayList<>();

        for (int m = 1; (long) m * m <= limit; m++) {
            squares.add(m * m);
            signs.add((m & 1) != 0 ? 1 : -1);
        }

        for (int n = 1; n <= limit; n++) {
            long val = 0;
            int cnt = 0;
            for (int i = 0; i < squares.size(); i++) {
                int sq = squares.get(i);
                if (sq > n)
                    break;
                if (signs.get(i) > 0) {
                    val += a[n - sq];
                } else {
                    val -= a[n - sq];
                }
                if ((++cnt & 63) == 0)
                    val %= MOD;
            }
            val %= MOD;
            if (val < 0)
                val += MOD;
            a[n] = (int) ((2L * val) % MOD);
        }

        return a;
    }

    static int solve614(int limit) {
        int maxK = limit / 4;
        int[] a = buildA015128(maxK);

        byte[] mark = new byte[limit + 1];
        mark[0] = 1;
        for (int n = 1;; n++) {
            long h1 = (long) n * (2L * n - 1);
            if (h1 > limit)
                break;
            mark[(int) h1] = 1;
            long h2 = (long) n * (2L * n + 1);
            if (h2 <= limit)
                mark[(int) h2] = 1;
        }

        int[] pref = new int[limit + 1];
        int run = 0;
        for (int i = 0; i <= limit; i++) {
            if (mark[i] == 1)
                run++;
            pref[i] = run;
        }

        long ans = 0;
        for (int k = 0; k <= maxK; k++) {
            ans += (long) a[k] * pref[limit - 4 * k];
            ans %= MOD;
        }
        ans = (ans - 1) % MOD;
        if (ans < 0)
            ans += MOD;
        return (int) ans;
    }

    public static String solve() {
        return Integer.toString(solve614(10000000));
    }

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