import fractions def solve(N): mod = 1000003 xyz = N // 4 max_m = int((xyz / 2)**0.5) while max_m * (max_m + 1) * 2 > xyz: max_m -= 1 count = 0 for m in range(2, max_m + 1): for n in range(1, min(m, xyz // (2 * m) - m + 1)): if fractions.gcd(m + n, 2*m*n) == 1: count += 1 return count % mod N = 10**7 print(solve(N))