#!/usr/bin/env python3

from fractions import gcd
from time import sleep

"""
Use the frickin' binomial expansion. Problem solved.
"""

def get_cyclic_group(seed, modifier):
    current=seed+modifier
    cyclic_group=[1, current]
    mod=seed**2
    counter=2
    while True:
        if counter%2==0:
            next_element=(cyclic_group[-2]+2*current)%mod
        else:
            next_element=(cyclic_group[-2]-2*current)%mod
        if next_element in (cyclic_group[0], cyclic_group[1]):
            return cyclic_group
        cyclic_group.append(next_element)
        counter+=1

def lcm(a,b):
    if a%b==0:
        return a
    elif b%a==0:
        return b
    else:
        return (a*b)//gcd(a,b)

def combine_groups(group_a, group_b, mod):
    a=len(group_a)
    b=len(group_b)
    n=lcm(a, b)
    combined_group=[]
    for i in range(n):
        combined_group.append((group_a[i%a]+group_b[i%b])%mod)
    return combined_group

def get_r_max(n):
    mod=n**2
    a=get_cyclic_group(n-1, -1)
    b=get_cyclic_group(n+1, 1)
    return max(combine_groups(a,b,mod))

def main(lower=3, upper=1000):
    return sum(get_r_max(i) for i in range(lower, upper+1))
