K = int(eval(input()))

def gcd(x, y):

  a, b = x, y

  while b != 0:

    a, b = b, a % b

  return a

gcds = [[0 for j in range(K)] for i in range(K)]

for i in range(K):

  for j in range(K):

    gcds[i][j] = gcd(i+1, j+1)

S = 0

for i in range(K):

  for j in range(K):

    for k in range(K):

      S += gcds[gcds[j][k]-1][i]

print(S)
K = int(eval(input()))

mod = int(1e9) + 7

X = [0 for _ in range(K)]

def doubling(n, m):

  y = 1

  base = n

  while m != 0:

    if m % 2 == 1:

      y *= base

      y %= mod

    base *= base

    base %= mod

    m //= 2

  return y

SS = 0

for i in range(K, 0, -1):

  d = K // i

  S = doubling(d, 3)

  if d > 1:

    for j in range(2, d+1):

      S -= X[j*i-1]

      S %= mod

  X[i-1] = S

  SS += i * S

  SS %= mod

print(SS)
K = int(eval(input()))


def gcd(x, y):
    a, b = x, y
    while b != 0:
        a, b = b, a % b
    return a


gcds = [[0 for j in range(K)] for i in range(K)]
for i in range(K):
    for j in range(K):
        gcds[i][j] = gcd(i + 1, j + 1)
S = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            S += gcds[gcds[j][k] - 1][i]
print(S)

K = int(eval(input()))
mod = int(1e9) + 7
X = [0 for _ in range(K)]


def doubling(n, m):
    y = 1
    base = n
    while m != 0:
        if m % 2 == 1:
            y *= base
            y %= mod
        base *= base
        base %= mod
        m //= 2
    return y


SS = 0
for i in range(K, 0, -1):
    d = K // i
    S = doubling(d, 3)
    if d > 1:
        for j in range(2, d + 1):
            S -= X[j * i - 1]
            S %= mod
    X[i - 1] = S
    SS += i * S
    SS %= mod
print(SS)

+mod = int(1e9) + 7 +X = [0 for _ in range(K)] -def gcd(x, y): -    a, b = x, y -    while b != 0: -        a, b = b, a % b -    return a +def doubling(n, m): +    y = 1 +    base = n +    while m != 0: +        if m % 2 == 1: +            y *= base +            y %= mod +        base *= base +        base %= mod +        m //= 2 +    return y -gcds = [[0 for j in range(K)] for i in range(K)] -for i in range(K): -    for j in range(K): -        gcds[i][j] = gcd(i + 1, j + 1) -S = 0 -for i in range(K): -    for j in range(K): -        for k in range(K): -            S += gcds[gcds[j][k] - 1][i] -print(S) +SS = 0 +for i in range(K, 0, -1): +    d = K // i +    S = doubling(d, 3) +    if d > 1: +        for j in range(2, d + 1): +            S -= X[j * i - 1] +            S %= mod +    X[i - 1] = S +    SS += i * S +    SS %= mod +print(SS)