import java.math.BigInteger;

public class Euler817 {

    static final long kP = 1000000007L;

    static long modPow(long base, long exp, long mod) {
        long res = 1 % mod;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1L) == 1L) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1L;
        }
        return res;
    }

    static BigInteger ceilIsqrt(BigInteger n) {
        if (n.signum() == 0) {
            return BigInteger.ZERO;
        }

        // Initial approximation
        int bitLength = n.bitLength();
        BigInteger r = BigInteger.ONE.shiftLeft((bitLength + 1) / 2);

        while (true) {
            BigInteger nextR = r.add(n.divide(r)).shiftRight(1);
            if (nextR.compareTo(r) >= 0) {
                break;
            }
            r = nextR;
        }

        while (r.multiply(r).compareTo(n) < 0) {
            r = r.add(BigInteger.ONE);
        }
        while (r.signum() > 0 && r.subtract(BigInteger.ONE).multiply(r.subtract(BigInteger.ONE)).compareTo(n) >= 0) {
            r = r.subtract(BigInteger.ONE);
        }

        return r;
    }

    static long MForTargetDigit(long d, long expLeg, long expSqrt, BigInteger p2) {
        long a = kP - d;
        long leg = modPow(a, expLeg, kP);

        if (leg == 1) {
            long r = modPow(a, expSqrt, kP);
            return Math.min(r, kP - r);
        }

        BigInteger L = p2.subtract(BigInteger.valueOf(d).multiply(BigInteger.valueOf(kP)));
        BigInteger width = BigInteger.valueOf(kP);

        while (true) {
            BigInteger m = ceilIsqrt(L);
            BigInteger sq = m.multiply(m);
            if (sq.compareTo(L.add(width).subtract(BigInteger.ONE)) <= 0) {
                return m.longValue();
            }
            L = L.add(p2);
        }
    }

    public static String solve() {
        long expLeg = (kP - 1) / 2;
        long expSqrt = (kP + 1) / 4;
        BigInteger p2 = BigInteger.valueOf(kP).multiply(BigInteger.valueOf(kP));

        BigInteger total = BigInteger.ZERO;
        for (long d = 1; d <= 100000; ++d) {
            long res = MForTargetDigit(d, expLeg, expSqrt, p2);
            total = total.add(BigInteger.valueOf(res));
        }

        return total.toString();
    }

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