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

public class Euler408 {
    private static final int MOD = 1000000007;

    private static int modPow(int base, long exp) {
        long result = 1;
        long cur = base % MOD;
        long e = exp;
        while (e > 0) {
            if ((e & 1L) != 0) {
                result = (result * cur) % MOD;
            }
            cur = (cur * cur) % MOD;
            e >>= 1L;
        }
        return (int) result;
    }

    private static class Point implements Comparable<Point> {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) {
            if (this.x != o.x)
                return Integer.compare(this.x, o.x);
            return Integer.compare(this.y, o.y);
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Point))
                return false;
            Point o = (Point) obj;
            return this.x == o.x && this.y == o.y;
        }
    }

    public static String solve() {
        int n = 10000000;
        int lim = (int) Math.sqrt(n);
        int lim2 = (int) Math.sqrt(2L * n);

        boolean[] isSquare = new boolean[2 * n + 1];
        for (int c = 1; c <= lim2; ++c) {
            isSquare[c * c] = true;
        }

        List<Point> pts = new ArrayList<>();
        for (int a = 1; a <= lim; ++a) {
            int a2 = a * a;
            for (int b = 1; b <= lim; ++b) {
                int b2 = b * b;
                if (isSquare[a2 + b2]) {
                    pts.add(new Point(a2, b2));
                }
            }
        }

        Collections.sort(pts);
        List<Point> uniquePts = new ArrayList<>();
        for (Point p : pts) {
            if (uniquePts.isEmpty() || !uniquePts.get(uniquePts.size() - 1).equals(p)) {
                uniquePts.add(p);
            }
        }
        pts = uniquePts;

        int maxv = 2 * n;
        int[] fact = new int[maxv + 1];
        fact[0] = 1;
        for (int i = 1; i <= maxv; ++i) {
            fact[i] = (int) ((1L * fact[i - 1] * i) % MOD);
        }

        int[] invFact = new int[maxv + 1];
        invFact[maxv] = modPow(fact[maxv], MOD - 2);
        for (int i = maxv; i >= 1; --i) {
            invFact[i - 1] = (int) ((1L * invFact[i] * i) % MOD);
        }

        int m = pts.size();
        int[] ways = new int[m];

        for (int i = 0; i < m; ++i) {
            int xi = pts.get(i).x;
            int yi = pts.get(i).y;
            long w = nCr(xi + yi, xi, fact, invFact);

            for (int j = 0; j < i; ++j) {
                int xj = pts.get(j).x;
                int yj = pts.get(j).y;
                if (xj <= xi && yj <= yi) {
                    long paths = nCr((xi - xj) + (yi - yj), xi - xj, fact, invFact);
                    w = (w - 1L * ways[j] * paths) % MOD;
                    if (w < 0)
                        w += MOD;
                }
            }
            ways[i] = (int) w;
        }

        long ans = nCr(2 * n, n, fact, invFact);
        for (int i = 0; i < m; ++i) {
            int x = pts.get(i).x;
            int y = pts.get(i).y;
            long tailPaths = nCr((n - x) + (n - y), n - x, fact, invFact);
            ans = (ans - 1L * ways[i] * tailPaths) % MOD;
            if (ans < 0)
                ans += MOD;
        }

        return String.valueOf(ans);
    }

    private static long nCr(int nn, int rr, int[] fact, int[] invFact) {
        if (rr < 0 || rr > nn)
            return 0;
        return 1L * fact[nn] * invFact[rr] % MOD * invFact[nn - rr] % MOD;
    }

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