Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    mod = 998244353
    DP = defaultdict(int)
    DP[(A, B)] = 1
    for cb in range(B + 1, D + 1):
        DP[(A, cb)] = (DP[(A, cb - 1)] * A) % mod

    for ca in range(A + 1, C + 1):
        DP[(ca, B)] = (DP[(ca - 1, B)] * B) % mod
        for nb in range(B + 1, D + 1):
            DP[(ca, nb)] = (DP[(ca, nb - 1)] * ca + DP[(ca - 1, nb)] * nb - DP[(ca - 1, nb - 1)] * (ca - 1) * (nb - 1)) % mod

    print(DP[(C, D)])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    mod = 998244353

    DP = [[0 for j in range(D + 1)] for i in range(C + 1)]
    DP[A][B] = 1
    for b in range(B + 1, D + 1):
        DP[A][b] = (DP[A][b-1] * A) % mod
    
    for a in range(A + 1, C + 1):
        DP[a][B] = (DP[a-1][B] * B) % mod
        for b in range(B + 1, D + 1):
            DP[a][b] = ((DP[a][b-1] * a) % mod + (DP[a-1][b] * b) % mod - (DP[a-1][b-1] * (a-1) * (b-1)) % mod) % mod
    print(DP[C][D])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import  collections 
N = int(input())
# list_a = [str(i) input() for i in range(N)]
list_a = []
for i in range (0,N):
    a = input()
    list_a.append(a)
dict_a = collections.Counter(list_a)
 
 
list_ans = []
 
list_ans.append(dict_a.most_common()[0][0])
a = dict_a.most_common()[0][1]
for i in range (1,len(dict_a)):
    if a == dict_a.most_common()[i][1]:
        list_ans.append(dict_a.most_common()[i][0])
 
list_ans.sort()
for i in range (0,len(list_ans)):
    print(list_ans[i])

### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]
dictionary = {}
for word in S:
    if word in dictionary:
        dictionary[word] += 1
    else:
        dictionary[word] = 1

maximum = max(dictionary.values())
for key, value in sorted(dictionary.items()):
    if value == maximum:
        print(key)
### BUGGY CODE ###

s=input();t=input()
ls=len(s);lt=len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while ls and lt:
  if dp[ls][lt]==dp[ls-1][lt]:
    ls-=1
  elif dp[ls][lt]==dp[ls][lt-1]:
    lt-=1
  else:
    ls-=1;lt-=1
    ans+=s[ls]
print(ans[::-1])

### FIXED CODE ###

s=input();t=input()
ls=len(s);lt=len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while ls and lt:
  if dp[ls][lt]==dp[ls-1][lt]:
    ls-=1
  elif dp[ls][lt]==dp[ls][lt-1]:
    lt-=1
  else:
    ls-=1;lt-=1
    ans+=s[ls]
print(ans[::-1])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  ones = 0
  for i in A:
    if i>>j & 1:
      ones += 1
  ans += 2**j*((n-ones)*ones)
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  ones = 0
  for i in A:
    if i>>j & 1:
      ones += 1
  ans += 2**j*((n-ones)*ones)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
res = 0
for i in range(N):
  x = a[i]
  cc = N
  for k in ks:
    z = x * k
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    if c >= 18:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc
print(res // 2)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for x in ks:
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc * d[x]
print(res // 2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1))
while q:
  px,py = q.popleft()
  d = dp[px][py]
  for j in range(1,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= d:
      break
    dp[px+j][py] = d+1
    q.append((px+j,py))
  for j in range(1,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= d:
      break
    dp[px-j][py] = d+1
    q.append((px-j,py))
  for j in range(1,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= d:
      break 
    dp[px][py+j] = d+1
    q.append((px,py+j))
  for j in range(1,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= d:
      break
    dp[px][py-j] = d+1
    q.append((px,py-j))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1))
while q:
  px,py = q.popleft()
  d = dp[px][py]
  for j in range(1,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= d:
      break
    if dp[px+j][py] == 10**6:
      dp[px+j][py] = d+1
      q.append((px+j,py))
  for j in range(1,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= d:
      break
    if dp[px-j][py] == 10**6:
      dp[px-j][py] = d+1
      q.append((px-j,py))
  for j in range(1,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= d:
      break 
    if dp[px][py+j] == 10**6:
      dp[px][py+j] = d+1
      q.append((px,py+j))
  for j in range(1,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= d:
      break
    if dp[px][py-j] == 10**6:
      dp[px][py-j] = d+1
      q.append((px,py-j))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])
### BUGGY CODE ###

Q = int(input())
Query = [input() for _ in range(Q)]

x = []
c = 0

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        x.append(a)
        c += b

    else :
        x.sort()

        min_v = float('inf')

        mid_l, mid_r = (len(x) - 1) // 2, len(x) // 2

        for mid in range(mid_l, mid_r + 1) :
            tmp = 0
            xmid = x[mid]

            for xi in x :
                tmp += abs(xi - xmid)
            
            if tmp < min_v :
                min_v = tmp
                min_k = x[mid]
        
        print(min_k, min_v + c)


### FIXED CODE ###

import heapq

Q = int(input())
Query = [input() for _ in range(Q)]

ans = 0

lq = []
rq = []

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        heapq.heappush(lq, -a)
        heapq.heappush(rq, a)

        lmax, rmin = -heapq.heappop(lq), heapq.heappop(rq)
        if lmax > rmin :
            lmax, rmin = rmin, lmax
            ans += rmin - lmax

        heapq.heappush(lq, -lmax)
        heapq.heappush(rq, rmin)

        ans += b

    else :
        print(-lq[0], ans)
### BUGGY CODE ###

n=int(input())
i=0
while(1):
    n//=2
    i+=1
    if n==1:
        break
print(2**(i+1)-1)

### FIXED CODE ###

n=int(input())
i=0
while(1):
    if n==1:
        break
    n//=2
    i+=1
i=bin(i+1)[2:]
ans=1
mkr=2
for j in i[::-1]:
    if j=="1":
        ans*=mkr
    mkr*=mkr
print(ans-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
a = [0]*(N) #1 index
b = [0]*(N) #1 index
p = [0]*(Q+1) #1 index
x = [0]*(Q+1) #1 index
counter = [0]*(N+1) #1 index
for i in range(1, N):
    a[i], b[i] = map(int, input().split())
for i in range(1, Q+1):
    p[i], x[i] = map(int, input().split())
    counter[p[i]] += x[i]

from collections import deque
graph = {i: deque() for i in range(1, N+1)}
for i in range(1, N):
    graph[a[i]].append(b[i])
    graph[b[i]].append(a[i])


def dfs(v):
    seen = [0]*(N+1)
    stack = []
    seen[v] = 1
    stack.append(v)
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            continue
        g = graph[s].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        stack.append(g)
        counter[g] += counter[s]

dfs(v=1)
print(*counter[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
a = [0]*(N) #1 index
b = [0]*(N) #1 index
p = [0]*(Q+1) #1 index
x = [0]*(Q+1) #1 index
counter = [0]*(N+1) #1 index
for i in range(1, N):
    a[i], b[i] = map(int, input().split())
for i in range(1, Q+1):
    p[i], x[i] = map(int, input().split())
    counter[p[i]] += x[i]

from collections import deque
graph = {i: deque() for i in range(1, N+1)}
for i in range(1, N):
    graph[a[i]].append(b[i])
    graph[b[i]].append(a[i])


def dfs(v):
    seen = [0]*(N+1)
    stack = []
    seen[v] = 1
    stack.append(v)
    while stack:
        s = stack[-1]
        if not graph[s]:
            stack.pop()
            continue
        g = graph[s].popleft()
        if seen[g]:
            continue
        seen[g] = 1
        stack.append(g)
        counter[g] += counter[s]

dfs(v=1)
print(*counter[1:])
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)
# BC.sort(key=lambda x:x[1])

for b,c in BC:
    for _ in range(b):
        a=heappop(A)
        if a>=c:
            heappush(A,a)
            break;
        else:
            heappush(A,c)

print(sum(A))

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)
BC.sort(key=lambda x:-x[1])

D=[]
for b,c in BC:
    D.extend([c]*b)
    if len(D)>=n:
        break
D=D[:n]


for d in D:
    a=heappop(A)
    if a>=d:
        heappush(A,a)
        break;
    else:
        heappush(A,d)

print(sum(A))
### BUGGY CODE ###

# 再帰回数の上限を引き上げる
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
a0,a1,a2,a3=0,0,0,0
for ai in a:
      if ai==0:
            a0+=1
      elif ai==1:
            a1+=1
      elif ai==2:
            a2+=1
      elif ai==3:
            a3+=1
aa=a0+a1+a2+a3
memo=[[[-1]*(aa+1) for _ in range(aa+1)] for _ in range(aa+1)]
#print(memo)
memo[1][0][0]=n
def dp(i,j,k):
      if memo[i][j][k]>0:
            return memo[i][j][k]
      else:
            m=i+j+k
            c=n
            if i>0:
                  c+=i*dp(i-1,j,k)
            if j>0:
                  c+=j*dp(i+1,j-1,k)
            if k>0:
                  c+=k*dp(i,j+1,k-1)
            memo[i][j][k]=c/m
            return c/m
print(dp(a1,a2,a3))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # 0個の皿がx0枚、1個の皿がx1枚、2個の皿がx2枚、3個の皿がx3枚
    # x0=n-x1-x2-x3
    ca={1:a.count(1),2:a.count(2),3:a.count(3)}
    memo=[[[-1]*(n+2) for _ in range(n+2)] for _ in range(n+2)]
    memo[0][0][0]=0
    for x3 in range(ca[3]+1):
        for x2 in range(ca[2]+ca[3]+1-x3):
            for x1 in range(ca[1]+ca[2]+ca[3]+1-x3-x2):
                if (x1,x2,x3)==(0,0,0):continue
                tmp=0
                if x1>0:tmp+=memo[x1-1][x2][x3]*x1
                if x2>0:tmp+=memo[x1+1][x2-1][x3]*x2
                if x3>0:tmp+=memo[x1][x2+1][x3-1]*x3
                tmp+=n
                tmp/=x1+x2+x3
                memo[x1][x2][x3]=tmp
    print(memo[ca[1]][ca[2]][ca[3]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)

### FIXED CODE ###

import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)
 
dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)
 
 
ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
 
print(ans[::-1])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1, N):
    cnt = 0
    for j in range(N-i):
        if S[j] == S[i+j]:
            cnt += 1
            if cnt == i:
                ans = max(ans, i)
                break
        else:
            ans = max(ans, cnt)
            cnt = 0
    ans = max(ans, cnt)
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1, N):
    cnt = 0
    for j in range(N-i):
        if S[j] == S[i+j]:
            cnt += 1
            if cnt == i:
                ans = max(ans, i)
                break
        else:
            ans = max(ans, cnt)
            cnt = 0
    ans = max(ans, cnt)
print(ans)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n-r*i+1):
        p=n-(r*i+g*j)
        if p>=0 and p%b==0:
            ans+=1
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans=0
for i in range(n//r+1):
    for j in range(n-r*i+1):
        p=n-(r*i+g*j)
        if p>=0 and p%b==0:
            ans+=1
print(ans)
### BUGGY CODE ###

def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.pop(0)
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited


n,x,y = map(int, input().split())

G = {}
G[0]=[1]

for i in range(n-1):
    G[i+1] = [i]
    if i==0:
        continue
    G[i].append(i+1)
G[x-1].append(y-1)
G[y-1].append(x-1)

dis_table=[]
for i in range(n):
    visited = [-1]*n
    queue = []
    visited[i]=0
    queue.append(i)
    dis_table.append(bfs(queue, visited))

ans = [0]*(n-1)
for i in range(1,n):
    for j in range(0,i):
        ans[dis_table[i][j]-1]+=1

for i in ans :
    print(i)



### FIXED CODE ###

def bfs(queue, visited):
    while len(queue) > 0:
        dest = queue.pop(0)
        for i in G[dest]:
            if visited[i] == -1:
                visited[i] = visited[dest] + 1
                queue.append(i)
    return visited


n,x,y = map(int, input().split())

G = {}
G[0]=[1]

for i in range(n-1):
    G[i+1] = [i]
    if i==0:
        continue
    G[i].append(i+1)
G[x-1].append(y-1)
G[y-1].append(x-1)

dis_table=[]
for i in range(n):
    visited = [-1]*n
    queue = []
    visited[i]=0
    queue.append(i)
    dis_table.append(bfs(queue, visited))

ans = [0]*(n-1)
for i in range(1,n):
    for j in range(0,i):
        ans[dis_table[i][j]-1]+=1

for i in ans :
    print(i)
### BUGGY CODE ###

N = int(input())
ans = 1
for i in map(int,input().split()):
    ans = ans * i

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int,input().split()))
mult = 1

if 0 in A:
    print(0)
    sys.exit()
else:
    for i in A:
        mult *= i
        if mult > 10**18:
            print('-1')
            sys.exit()

print(mult)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
a_list = list(map(int,input().split()))
same = 0
for a,b in combinations(a_list,2):
    if a == b:
        same += 1
for i in range(n):
    print(same - a_list.count(a_list[i])+1)

### FIXED CODE ###

from collections import Counter
n = int(input())
num_list = list(map(int,input().split()))
a = Counter(num_list)
count = 0
for i in a.values():
  count += (i*(i-1))//2
for j in num_list:
  print(count-(a[j]-1))
### BUGGY CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for i in range(T+1)] for j in range(S+1)]

for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

ans = ""
while S > 0 and T > 0:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1] + ans
        S -= 1
        T -= 1

print(ans)

### FIXED CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for i in range(T+1)] for j in range(S+1)]

for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

ans = ""
while S > 0 and T > 0:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1] + ans
        S -= 1
        T -= 1

print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd,numbers)

n =int(input())
c=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            c+=gcd(i,j,k)
print(c)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd,numbers)

n =int(input())
c=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            c+=gcd(i,j,k)
print(c)
### BUGGY CODE ###

k = int(input())
x = 7
for i in range(1,k+1):
    if x%k==0:
        print(i)
        break
    x=int('7'*(i+1))%k
else:
    print(-1)

### FIXED CODE ###

k = int(input())
x = 7
for i in range(1,k+1):
    if x%k==0:
        print(i)
        break
    x=(x*10+7)%k
else:
    print(-1)
### BUGGY CODE ###

import numpy as np

Input = map(int,raw_input().split(' '))
N = Input[0]
K = Input[1]
A = map(int,raw_input().split(' '))
A = sorted(A)
count = []
i = 0
while i < len(A):
	count.append(A.count(A[i]))
	i += A.count(A[i])
count = sorted(count)
count = np.array(count)
dim = count.shape[0]
rslt = 0
if dim <= K:
	print rslt
else:
	rslt += count[:dim-K].sum()
	print rslt

### FIXED CODE ###

import bisect
Input = map(int,raw_input().split(' '))
N = Input[0]
K = Input[1]
A = map(int,raw_input().split(' '))
A = sorted(A)
count = []
i = 0
while i < len(A):
	count.append(bisect.bisect_right(A,A[i]) - bisect.bisect_left(A,A[i]))
	i = bisect.bisect_right(A,A[i])
count = sorted(count)
dim = len(count)
rslt = 0
if dim <= K:
	print rslt
else:
	rslt += sum(count[:dim-K])
	print rslt
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(input())
a_lst = []
for i in range(n):
    if s[i] == 'A':
        a_lst.append(i)
for i in range(q):
    cnt = 0
    l, r = map(int, input().split())
    for i in range(l-1, r-1):
        if i in a_lst:
            if s[i+1] == 'C':
                cnt += 1
    print(cnt)

### FIXED CODE ###

N,Q=map(int,input().split()) 
S=input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

n,k,*a=map(int,open(0).read().split())
for _ in range(k):
  b=[0]*(n+1)
  for i,c in enumerate(a):
    b[max(0,i-c)]+=1
    b[min(n,c+i+1)]-=1
  for i in range(n):
    b[i+1]+=b[i]
  a=b[:-1]
  if a==[n]*n:
    print(*a)
    exit()
print(*a)

### FIXED CODE ###

n,k,*a=map(int,open(0).read().split())
for _ in range(k):
  b=[0]*(n+1)
  for i,c in enumerate(a):
    b[max(0,i-c)]+=1
    b[min(n,c+i+1)]-=1
  for i in range(n):
    b[i+1]+=b[i]
  a=b[:-1]
  if a==[n]*n:
    print(*a)
    exit()
print(*a)
### BUGGY CODE ###

N=int(input())
list = list(map(int, input().split()))
i=1
res=0

for i in range(1,N+1):
  j=list.count(i)
  res+=j
  print(j)
  if(res>N):
    break
  i+=1

### FIXED CODE ###

from collections import Counter

N=int(input())
list = list(map(int, input().split()))
i=1
counter = Counter(list)

for i in range(1,N+1):
  print(counter[i])
### BUGGY CODE ###

s = str(input())
#print(s)


#s = int(s)
#s = str(s)

flag = 1
cont = 0


while(flag):
    flag = 0
    for x in range(0, len(s)):
        if  x+1 < len(s) and s[x] == '1' and s[x+1] == '0':
            cont = cont + 2
            flag = 1
            aux = s[:x]
            aux2 = s[x+2: len(s)]
            s = aux + aux2
            break
        elif x+1 < len(s) and s[x] == '0' and s[x+1] == '1':
            cont = cont + 2
            flag = 1
            aux = s[:x]
            aux2 = s[x+2: len(s)]
            s = aux + aux2
            break

print(cont)

### FIXED CODE ###

s = input()
print(2*(min(s.count("0"), s.count("1"))))
### BUGGY CODE ###

import sys

N = int(input())
A = list(map(int, input().split()))
A = sorted([e for e in A if A.count(e) > 1], reverse = True)

c = None
for a in A:
    if A.count(a) >= 2:
        if c is not None:
            print(c * a)
            sys.exit()
    c = a
    A.remove(a)
    A.remove(a)
print(0)


### FIXED CODE ###

import sys

N = int(input())
A = sorted(list(map(int, input().split())), reverse = True)

mstack = []
stack = [0]
for a in A:
    if a == stack[-1]:
        mstack.append(a)
        stack.pop()
        if len(mstack) >= 2:
            print(mstack[-1] * mstack[-2])
            sys.exit()
    else:
        stack.append(a)
print(0)