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

s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for j, i in enumerate(s):
  S[j+1]=(S[j]+(10**(j)*int(i)))%p
  ans[S[j+1]]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)


### FIXED CODE ###

s=input()[::-1]
p=2019
ans=[0]*p

x10, S=1, 0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10
  x10%=p
  ans[S]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    A[i+1] = (A[i] | (A[i] << min(K, V[i]))) & MASK
B[N] = 1
for i in range(N-1, -1, -1):
    B[i] = (B[i+1] | (B[i+1] << min(K, V[i]))) & MASK

ans = N
for i in range(N):
    a = A[i]; b = B[i+1]
    t = K
    r = 0
    for s in range(K+1):
        if a & (1 << s) == 0:
            continue
        while t > -1 and (s + t >= K or b & (1 << t) == 0):
            t -= 1
        if t == -1:
            break
        r = max(r, s + t)
    if K-V[i] <= r < K:
        ans -= 1
print(ans)


### FIXED CODE ###

import random
N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    VM = 2**(V[i]+1)-2
    l = 1
    while a and b and l:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = max((a & -a).bit_length()-1, (b & -b).bit_length()-V[i]-1)
        a >>= l; b >>= l
print(ans)
### BUGGY CODE ###

n=int(input())
a,b,c=[list(map(int,input().split())) for _ in [0]*3]
from itertools import accumulate
a.sort()
b.sort()
c.sort()
a+=[10**20]
b+=[10**20]

p,q=0,0
cnt=0
ans=[0]*n
for i in range(n):
	for j in range(p,n+1):
		if b[i]>a[j]:
			pass
		else:
			break
	ans[i]=j
	p=j
ans=[0]+list(accumulate(ans))

for i in range(n):
	for j in range(q,n+1):
		if c[i]>b[j]:
			pass
		else:
			break
	cnt+=ans[j]
print(cnt)

### FIXED CODE ###

n=int(input())
a,b,c=[list(map(int,input().split())) for _ in [0]*3]
from itertools import accumulate
a.sort()
b.sort()
c.sort()
a+=[10**20]
b+=[10**20]
 
p,q=0,0
cnt=0
ans=[0]*n
for i in range(n):
    for j in range(p,n+1):
        if b[i]>a[j]:
            pass
        else:
            break
    ans[i]=j
    p=j
ans=[0]+list(accumulate(ans))

for i in range(n):
    for j in range(q,n+1):
        if c[i]>b[j]:
            pass
        else:
            break
    q=j
    cnt+=ans[j]
print(cnt)
### BUGGY CODE ###

from collections import Counter
S = input()
N = len(S)
result = 0
work = [0] * (N + 1)
temp = 0
for i in range(N):
    temp += int(S[N - i - 1]) * 10**i
    work[i] = temp % 2019
for v in Counter(work).values(): result += v*(v-1)//2
print(result)

### FIXED CODE ###

def main():
    S = input()
    work, temp = [0] * 2019, 0
    work[0] = 1
    a = 1
    for s in S[::-1]:
        temp += int(s) * a
        work[temp%2019] += 1
        a *= 10
        a %= 2019
    print(sum([w*(w-1)//2 for w in work]))
main()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = {}
for i in range(N) :
    if A[i] not in D :
        D[A[i]] = 1
    else :
        D[A[i]] += 1
L = D.values()
L = sorted(L)
ans = 0
for i in range(len(L)) :
    if len(L) > K :
        ans += L[0]
        L.pop(0)
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D :
        D[i] += 1
    else :
        D[i] = 1
D = sorted(D.items(),key=lambda x:x[1])
counter = 0
answer = 0
for j in range(len(D)) :
    if len(D) - counter > K :
        counter += 1
        answer += D[j][1]
    else :
        print(answer)
        break
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())

G = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

count = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1] += x

def dfs(v, p):
    if p != -1:
        count[v] += count[p]
    for next_v in G[v]:
        if next_v == p: continue
        dfs(next_v, v)

dfs(0, -1)
print(" ".join(map(str, count)))

### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())

ab = [[int(i) for i in input().split()] for j in range(N-1)]
G = [[] for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

q = [[int(i) for i in input().split()] for j in range(Q)]
count = [0 for i in range(N)]
for i in range(Q):
    p, x = q[i]
    count[p-1] += x

ls = deque([0])
seen = [0 for i in range(N)]
while len(ls) > 0:
    root = ls.popleft()
    seen[root] = 1

    for next_v in G[root]:
        if not seen[next_v]:
            count[next_v] += count[root]
            ls.append(next_v)

for i in range(N):
    print(count[i], end=" ")
### BUGGY CODE ###

from collections import deque
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    h,w,k=MI()
    x1,y1,x2,y2=MI1()
    aa=[[0 if c=="@" else inf for c in SI()] for _ in range(h)]
    #p2D(aa)

    aa[x1][y1]=0
    q=deque()
    q.append((x1,y1,0))
    while q:
        x,y,d=q.popleft()
        for nx in range(x+1,min(x+k+1,h)):
            if aa[nx][y]<d+1:break
            aa[nx][y]=d+1
            q.append((nx,y,d+1))
        for nx in range(x-1,max(x-k-1,-1),-1):
            if aa[nx][y]<d+1:break
            aa[nx][y]=d+1
            q.append((nx,y,d+1))
        for ny in range(y+1,min(y+k+1,w)):
            if aa[x][ny]<d+1:break
            aa[x][ny]=d+1
            q.append((x,ny,d+1))
        for ny in range(y-1,max(y-k-1,-1),-1):
            if aa[x][ny]<d+1:break
            aa[x][ny]=d+1
            q.append((x,ny,d+1))
        #p2D(aa)
        #print()

    ans=aa[x2][y2]
    if ans==inf:print(-1)
    else:print(ans)

main()

### FIXED CODE ###

from collections import deque
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    h,w,k=MI()
    x1,y1,x2,y2=MI1()
    aa=[[0 if c=="@" else inf for c in SI()] for _ in range(h)]
    #p2D(aa)

    aa[x1][y1]=0
    q=deque()
    q.append((x1,y1,0))
    while q:
        x,y,d=q.popleft()
        for nx in range(x+1,min(x+k+1,h)):
            if aa[nx][y] == d + 1:continue
            if aa[nx][y]<d+1:break
            aa[nx][y]=d+1
            q.append((nx,y,d+1))
        for nx in range(x-1,max(x-k-1,-1),-1):
            if aa[nx][y] == d + 1:continue
            if aa[nx][y]<d+1:break
            aa[nx][y]=d+1
            q.append((nx,y,d+1))
        for ny in range(y+1,min(y+k+1,w)):
            if aa[x][ny] == d + 1:continue
            if aa[x][ny]<d+1:break
            aa[x][ny]=d+1
            q.append((x,ny,d+1))
        for ny in range(y-1,max(y-k-1,-1),-1):
            if aa[x][ny] == d + 1:continue
            if aa[x][ny]<d+1:break
            aa[x][ny]=d+1
            q.append((x,ny,d+1))
        #p2D(aa)
        #print()

    ans=aa[x2][y2]
    if ans==inf:print(-1)
    else:print(ans)

main()
### BUGGY CODE ###

X,Y,Z,K=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
D=[]
for i in A:
  for j in B:
    D.append(i+j)
D=sorted(D)[::-1]
if X*Y>K:
  D=D[:K]
E=[]
for i in D:
  for j in C:
    E.append(i+j)
E=sorted(E)[::-1]
E=E[:K]
for i in E:
  print(i)

### FIXED CODE ###

X,Y,Z,K=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
D=[]
for i in A:
  for j in B:
    D.append(i+j)
D=sorted(D)[::-1]
if X*Y>K:
  D=D[:K]
E=[]
for i in D:
  for j in C:
    E.append(i+j)
E=sorted(E)[::-1]
E=E[:K]
for i in E:
  print(i)
### BUGGY CODE ###


n = int(input())
a = list(map(int,input().split()))
ans = 0

for i in range(n):
    for j in range(i+1,n+1):
        t = a.copy()
        tmp = t[i:j]
 #       print(tmp)
        if sum(tmp) == 0:
            ans += 1

print(ans)




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in range(n):
  b.append(b[-1]+a[i])
#print(b)
ans = 0
b.sort()
for i in range(n+1):
  if i == 0:
    x=b[0]
    m=1
  else:
    if x==b[i]:
      m+=1
      if i==n:
        ans += m*(m-1)//2
    else:
      if m!=1:
        ans += m*(m-1)//2
        m=1
      x=b[i]
print(ans)
### BUGGY CODE ###

from copy import copy
from itertools import product
h, w = map(int, input().split())
maze = []
max_d = 0
for i in range(h):
    maze.append(input())
for i, j in product(range(h), range(w)):
    if maze[i][j] == '#':
        continue
    s = (i, j)
    for k, l in product(range(h), range(w)):
        if maze[k][l] == '#':
            continue
        g = (k, l)
        pathes = [[s]]
        while pathes:
            path = pathes.pop(0)
            a, b = path[-1]
            for point in [(0, 1), (1, 0), (0, -1),(-1, 0)]:
                di, dj = point
                if a + di >= 0 and a + di < h and b + dj >= 0 and b + dj < w and (a+di, b+dj) not in path and maze[a+di][b+dj]=='.':
                    copy_path = copy(path)
                    copy_path.append((a + di, b + dj))
                    pathes.append(copy_path)
                if (a + di, b + dj) == g:
                    max_d = max(max_d, len(copy_path)-1)
                    pathes = None
                    break
print(max_d)
                



### FIXED CODE ###

from copy import copy
from itertools import product
h, w = map(int, input().split())
maze = []
max_d = 0
for i in range(h):
    maze.append(input())
for i, j in product(range(h), range(w)):
    if maze[i][j] == '#':
        continue
    s = (i, j)
    pathes = [[s]]
    seen = {s}
    while pathes:
        path = pathes.pop(0)
        a, b = path[-1]
        for point in [(0, 1), (1, 0), (0, -1),(-1, 0)]:
            di, dj = point
            if a + di >= 0 and a + di < h and b + dj >= 0 and b + dj < w and (a+di, b+dj) not in seen and maze[a+di][b+dj]=='.':
                copy_path = copy(path)
                copy_path.append((a + di, b + dj))
                seen.add((a+di, b+dj))
                pathes.append(copy_path)
                max_d = max(max_d, len(copy_path)-1)
print(max_d)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
list=[0]*(N-1)
list1=[0]*N
for i in range(1,N):
    list[i-1]=A[i-1]

for j in range(N):
    list1[j]=list.count(j+1)
for l in range(N):
    print(list1[l])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
list=[0]*(N-1)
list1=[0]*N
for i in range(1,N):
    list[i-1]=A[i-1]
    list1[A[i-1]-1]+=1
list1.append(0)
for j in range(N):
    print(list1[j])
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()

        m = {}
        def _f(a):
            l = len(a)
            if l < 2:
                return 0
            k = tuple(a)
            if k in m:
                return m[k]
            r = 0
            for i in range(len(a)-1):
                if abs(a[i]-a[i+1]) >= 2:
                    continue
                t = _f(a[:i] + a[i+2:]) + 2
                if r < t:
                    r = t
            m[k] = r
            return r

        return _f(a)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))



print(main())



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()
        l = len(a)
        s = set()
        r = 0
        for i in range(l-1):
            if abs(a[i] - a[i+1]) < 2:
                s.add((i,i+1))
        for i in range(4, l+1):
            for j in range(l-i+1):
                k = j + i - 1
                if (j+1, k-1) in s and abs(a[j] - a[k]) < 2:
                    s.add((j,k))
                    continue
                for m in range(j+2,k,2):
                    if (j,m-1) in s and (m,k) in s:
                        s.add((j,k))
                        break

        m = {}
        m[l] = 0
        def _f(i):
            if i in m:
                return m[i]
            r = 0
            for j in range(i,l+1):
                t = _f(j+1)
                if (i,j) in s:
                    t += j - i + 1
                if r < t:
                    r = t
            m[i] = r
            return r
        return _f(0)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))



print(main())
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
c = list(map(int, input().split()))
c.sort()

if n > 1:
    ans = 0
    for i in range(n):
        m = (1 << (n - 1)) + (1 << (n - 2)) * (n - 1 - i)
        ans += c[i] * m
        ans %= MOD

    for i in range(n):
        ans *= 2
        ans %= MOD
else:
    ans = c[0] * 2
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
c = list(map(int, input().split()))
c.sort()

if n > 1:
    ans = 0
    x = (1 << (n - 1)) % MOD
    y = (1 << (n - 2)) % MOD
    for i in range(n):
        m = x + (y * (n - 1 - i)) % MOD
        m %= MOD
        ans += c[i] * m
        ans %= MOD

    for i in range(n):
        ans *= 2
        ans %= MOD
else:
    ans = c[0] * 2
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    n = int(input())
    s = [int(input()) for _ in range(n)]
    for i in range(2**n):
        tmp = 0
        for j in range(n):
            if i>>j&1:
                tmp += s[j]
        if tmp%10 != 0:
            ans = max(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    n = int(input())
    s = []   
    for i in range(n):
        t = int(input())
        ans += t
        s.append(t)
    s.sort()
    
    if ans%10 == 0:
        for i in range(n):
            if s[i]%10 != 0:
                ans -= s[i]
                break
    if ans%10 == 0:
      ans = 0
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

MOD=10**9+7

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=2**(2*n-1)
d=x//2
for i in range(n):
    ans=(ans+(x+i*d)*c[i])%MOD
print(ans)

### FIXED CODE ###

MOD=10**9+7
MAXN=4*(10**5)

two_power=[1 for _ in range(MAXN+10)]
for i in range(1, MAXN+10):
    two_power[i]=(two_power[i-1]*2)%MOD

n=int(input())
c=list(map(int, input().split()))
c.sort(reverse=True)
ans=0
x=two_power[2*n-1]
d=two_power[2*n-2]
for i in range(n):
    ans+=(x+i*d)*c[i]
print(ans%MOD)
### BUGGY CODE ###

import bisect
n = int(input())
S = input()
r = []
g = []
b = []
for i, s in enumerate(S):
    if s == "R":
        r.append(i)
    elif s == "G":
        g.append(i)
    else:
        b.append(i)

# print(s, r, g, b)
ans = 0
for i, j in enumerate(r):
    for k, l in enumerate(g):
        for m, n in enumerate(b):
            I = min(j, l, n)
            K = max(j, l, n)
            J = j + l + n - I - K
            if K - J != J - I:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
S = input()
r = []
g = []
b = []
for i, s in enumerate(S):
    if s == "R":
        r.append(i)
    elif s == "G":
        g.append(i)
    else:
        b.append(i)

# print(s, r, g, b)
ans = len(r) * len(g) * len(b)
i = 0
j = 1
while i + 2 * j < n:
    while i + 2 * j < n:
        if S[i] != S[i + j] != S[i + 2 * j] != S[i]:
            ans -= 1
        i += 1
    j += 1
    i = 0

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

a,b,x = map(int, input().split())

k = 0
for i in range(a,b+1):
  if i % x == 0:
    k += 1

print(k)

### FIXED CODE ###

# -*- coding : utf-8 -*-

a,b,x = map(int, input().split())

A = a // x
B = b // x
if a % x != 0:
  print(B-A)
else:
  print( B-A + 1)
### BUGGY CODE ###

S = input()
N = len(S)
 
for i in range(N):
    fn = len(S)
    S = S.replace('01', '').replace('10', '').replace('01', '').replace('10', '').replace('01', '').replace('10', '')
    if fn == len(S):
        break
 
print(N - len(S))

### FIXED CODE ###

S = input()
N = len(S)
A = 0

for i in range(N):
    if S[i] == '1':
        A = A + 1

print(min(N - A, A)*2)
### BUGGY CODE ###

l = [list(map(int, input().split())) for _ in range(3)]

for a1 in range(101):
    for a2 in range(101):
        for a3 in range(101):
            b1 = l[0][0] - a1
            b2 = l[0][1] - a1
            b3 = l[0][2] - a1

            a = [a1, a2, a3]
            b = [b1, b2, b3]

            cnt = 0
            for i in range(3):
                for j in range(3):
                    if l[i][j] == a[i] + b[j]:
                        cnt += 1
            if cnt == 9:
                print("Yes")
                exit()
print("No")

### FIXED CODE ###

l = [list(map(int, input().split())) for _ in range(3)]

for a1 in range(101):
    for a2 in range(101):
        for a3 in range(101):
            b1 = l[0][0] - a1
            b2 = l[0][1] - a1
            b3 = l[0][2] - a1

            a = [a1, a2, a3]
            b = [b1, b2, b3]

            cnt = 0
            for i in range(3):
                for j in range(3):
                    if l[i][j] == a[i] + b[j]:
                        cnt += 1
            if cnt == 9:
                print("Yes")
                exit()
print("No")
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a_array = sorted([int(x) for x in input().split()], reverse=True)
b_array = sorted([int(x) for x in input().split()], reverse=True)
c_array = sorted([int(x) for x in input().split()], reverse=True)


def solver1():
    ab_array = [x + y for x in a_array for y in b_array]
    abc_array = sorted([ab + c for ab in ab_array for c in c_array], reverse=True)
    for abc in abc_array[:k]:
        print(abc)


solver1()


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a_array = sorted([int(x) for x in input().split()], reverse=True)
b_array = sorted([int(x) for x in input().split()], reverse=True)
c_array = sorted([int(x) for x in input().split()], reverse=True)


def solver1():
    ab_array = sorted([x + y for x in a_array for y in b_array], reverse=True)[:3000]
    abc_array = sorted([ab + c for ab in ab_array for c in c_array], reverse=True)
    for abc in abc_array[:k]:
        print(abc)


solver1()
### BUGGY CODE ###

def solve(ls, n, w):
	dp = [0] * (w + 1)
	for item in range(n):
		for weight in range(w, ls[item][0] - 1, -1):
			dp[weight] = max(dp[weight], dp[weight - ls[item][0]] + ls[item][1])
	return dp[w]


n, w = map(int, input().split())
ls = []
for i in range(n):
	ls.append(list(map(int, input().split())))

print(solve(ls, n, w))


### FIXED CODE ###

n, w = map(int, input().split())
dp = [0] * (w + 1)
for j in range(n):
	w1, v1 = map(int, input().split())
	i = w
	while i >= 0 and i - w1 >= 0:
		dp[i] = max(dp[i - w1] + v1, dp[i])
		i -= 1
print(max(dp))
### BUGGY CODE ###

dp=[[[] for i in range(3000)] for j in range(3000)]
n=int(input())
A=list(int(i) for i in input().split())
#dp=[[[] for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i<=j:
            if i==j:
                dp[i][j].append(A[i])
                dp[i][j].append(-A[i])
            else:
                dp[i][j].append(max(A[i]+dp[i+1][j][1],A[j]+dp[i][j-1][1]))
                dp[i][j].append(min(-A[i]+dp[i+1][j][0],-A[j]+dp[i][j-1][0]))
print(dp[0][n-1][0])


### FIXED CODE ###

#dp=[[ for i in range(3000)] for j in range(3000)]
n=int(input())
A=list(int(i) for i in input().split())
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i==j:
            dp[i][j]=A[i]
        else:
            dp[i][j]=max(A[i]-dp[i+1][j],A[j]-dp[i][j-1])
print(dp[0][-1])
### BUGGY CODE ###

INF = float('inf')
MOD = 1000000000 + 7

def solve():
    power = 1
    for i in range(1, int(input()) + 1):
        power *= i

    print(power % MOD)


solve()

### FIXED CODE ###

import math
MOD = 10**9 + 7

N = int(input())
print(math.factorial(N) % MOD)
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

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

k = int(input())
ans = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      t = len({a,b,c})
      if t == 3:
        ans += gcd(a,b,c) * 6
      elif t == 2:
        ans += gcd(a,b,c) * 3
      else:
        ans += gcd(a,b,c)
        
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
  B = A[:]
  B.remove(B[i])
  ans = max(ans, gcd_list(B))
print(ans)


### FIXED CODE ###

from fractions import gcd

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

L = [0 for _ in range(N)]
R = [0 for _ in range(N)]
L[0] = A[0]
R[-1] = A[-1]
for i in range(N-1):
  L[i+1] = gcd(L[i],A[i+1])
  R[N-2-i] = gcd(R[N-1-i],A[N-2-i])
#print(L)
#print(R)

ans = 0
for i in range(N):
  if i == 0:
    ans = max(ans,R[1])
  elif i == N-1:
    ans = max(ans,L[N-2])
  else:
    ans = max(ans,gcd(L[i-1],R[i+1]))
print(ans)