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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
dp[0] = 1 if 0 not in a else 0
dp[1] = 1 if 1 not in a else 0
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in [int(input()) for _ in range(m)]:
    dp[i] = -1
for i in range(n + 1):
    if i < 2:
        if dp[i] == -1:
            dp[i] = 0
    else:
        if dp[i] == -1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())

dists = [[[0, 0] for j in range(W)] for i in range(H)]

tile = [0 for i in range(H)]

for i in range(H):
    tile[i] = readline().decode().strip()

for i in range(H):
    count = 0
    start = 0
    for j in range(W):
        if tile[i][j] == '#':
            for x in range(start, j):
                dists[i][x][0] = count
            count = 0
            start = j + 1
        else:
            count += 1 
    for x in range(start, W):
        dists[i][x][0] = count

for j in range(W):
    count = 0
    start = 0
    for i in range(H):
        if tile[i][j] == '#':
            for y in range(start, i):
                dists[y][j][1] = count
            count = 0
            start = i + 1
        else:
            count += 1 
    for y in range(start, H):
        dists[y][j][1] = count


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(dists[i][j][0] + dists[i][j][1] - 1, ans)
print(ans)



### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())

tile = [0 for i in range(H)]
cnt = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    tile[i] = readline().decode().strip()

for i in range(H):
    done = [False for _ in range(W)]
    for j in range(W):
        if tile[i][j] == '#':
            continue
        if done[j]:
            continue
        l = 0
        while (j + l < W):
            if tile[i][j + l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j + k] += l
            done[j + k] = True

for j in range(W):
    done = [False for _ in range(H)]
    for i in range(H):
        if tile[i][j] == '#':
            continue
        if done[i]:
            continue
        l = 0
        while (i + l < H):
            if tile[i + l][j] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i + k][j] += l
            done[i + k] = True

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(cnt[i][j] - 1, ans)
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
ns = [[] for _ in range(n+2)]
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(range(n+2), range(n+2)):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        ns[i].append((d,j))
        ns[j].append((d,i))
def dijkstra(start):
    import heapq
    vals = [float("inf")] * (n+2)
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        if u==t:
            break
        for d, v in ns[u]:
            if vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(s)
ans = vals[t]
print(ans)


### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
# ns = [[] for _ in range(n+2)]
data = []
rs = []
cs = []
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(range(n+2), range(n+2)):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        data.append(d)
        rs.append(i)
        cs.append(j)
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n+2, n+2))
ans = scipy.sparse.csgraph.dijkstra(m, indices=t, directed=False)
print(ans[s])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
canB=[0]*N
canC=[0]*N
p1=0
p2=0
total=0
for j in range(N):
    c=C[j]
    while p2<N and B[p2]<c:
        while p1<N and A[p1]<B[p2]:
            canB[p2]+=1
            p1+=1
        p2+=1
        if p2<N:
            canB[p2]=canB[p2-1]
    canC[j]=sum(canB[:p2])
print(sum(canC))

### FIXED CODE ###

import bisect
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
total=0
for j in range(N):
    b=B[j]
    p_a=bisect.bisect_left(A,b)
    p_b=bisect.bisect_right(C,b)
    total+=p_a*(N-p_b)
print(total)
### BUGGY CODE ###

n=int(input())
prime=[True]*(n+1)
prime[0]=False
prime[1]=False
for i in range(2,n+1):
  if prime[i]:
    for j in range(i*2,int(n**0.5),i):
      prime[j]=False
s=[i for i in range(n+1) if prime[i]]

cnt=[[] for _ in range(n)]
for i in range(2,n):
  c=[]
  j=0
  i2=i
  while i>1 and s[j]<=i2**0.5:
    while i%s[j]==0:
      i=i//s[j]
      c.append(s[j])
    j+=1
  if i>i2**0.5:
    c.append(i)
  cnt[i2]=c

ans=0
from collections import Counter
for c in cnt:
  cc=Counter(c)
  cv=cc.values()
  a=1
  for ccc in cv:
    a*=(ccc+1)
  if a!=1:
    ans+=a
print(ans+1)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n):
  ans+=int((n-1)/i)
print(ans)
### BUGGY CODE ###

import numpy as np


def main(n, a, x):
    SUM_MAX = max(a, max(x)) * n + 1
    dp = np.zeros(shape=(n + 1, n + 1, SUM_MAX), dtype=int)

    dp[0][0][0] = 1
    for j in range(1, n + 1):
        for k in range(j + 1):
            for s in range(SUM_MAX):
                if s < x[j - 1]:
                    dp[j][k][s] = dp[j - 1][k][s]
                elif k >= 1:
                    dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]

    patterns = 0
    for k in range(1, n + 1):
        ka = k * a
        patterns += dp[n][k][ka]
    return patterns


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))


### FIXED CODE ###

import numpy as np


def main(n, a, x):
    SUM_MAX = max(a, max(x)) * n + 1
    dp = np.zeros(shape=(n + 1, n + 1, SUM_MAX), dtype=int)

    dp[0][0][0] = 1
    for j in range(1, n + 1):
        for k in range(j + 1):
            dp[j][k][0:x[j - 1]] = dp[j - 1][k][0:x[j - 1]]
            if k >= 1:
                dp[j][k][x[j - 1]:] = dp[j - 1][k][x[j - 1]:] + dp[j - 1][k - 1][:SUM_MAX - x[j - 1]]

    patterns = 0
    for k in range(1, n + 1):
        ka = k * a
        patterns += dp[n][k][ka]
    return patterns


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().rstrip().split()))
for i in a:
    a.remove(i)
    d = 0
    for t in range(0,len(a)):
        for j in range(t+1,len(a)):
            if a[t] == a[j]:
                d += 1
    print(d)
    a.insert(0,i)
    

### FIXED CODE ###

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

n, k = map(int, input().split())
pl = list(map(int, input().split()))

tmp = []
for p in pl:
    ii = 0
    for i in range(1, p+1):
        ii += i
    tmp.append(ii/p)

ans = 0
for i in range(n-k+1):
    if sum(tmp[i:i+k]) > ans:
        ans = sum(tmp[i:i+k])

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
pl = list(map(int, input().split()))

dp = [0] * (n + 1)

for i in range(n):
    dp[i+1] = dp[i] + (pl[i] + 1)/2

ans = 0
for i in range(k, n+1):
    ans = max(ans, dp[i] - dp[i-k])

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

x = int(input())
rx = int(x**(1/2)) + 1
P = [2] + [2*i+1 for i in range(1, rx//2)]
while True:
    flag = True
    for i in P:
        if x % i == 0:
            flag = False
            break
    if flag:
        print(x)
        break 
    if P[-1] != int(x**(1/2)):
        P.append(int(x**(1/2)))
    x += 1

### FIXED CODE ###

x = int(input())
rx = int(x**(1/2)) + 1
P = [2] + [2*i+1 for i in range(1, rx//2)]
while True:
    flag = True
    for i in P:
        if x % i == 0:
            flag = False
            break
    if flag or x == 2:
        print(x)
        break
    P.append(int(x**(1/2)+1))
    x += 1
### BUGGY CODE ###

import copy

N = int(input())
A = list(int(i) for i in input().split())
A.insert(0, 0)
A.append(0)
B = copy.deepcopy(A)
Q = 0

for i in range(N):
    A.pop(i+1)
    for j in range(N):            
        Q += abs(A[j] - A[j+1])
    print("%d" % (Q))
    Q = 0
    A = copy.deepcopy(B)

### FIXED CODE ###

N = int(input())
A = list(int(i) for i in input().split())
A.insert(0, 0)
A.append(0)

Sum = 0
Ans = 0

for i in range(len(A) - 1):
    Sum += abs(A[i+1] - A[i])

for i in range(N):
    Ans = Sum
    Ans = Ans - abs(A[i+1] - A[i]) - abs(A[i+2] - A[i+1]) + abs(A[i+2] - A[i])
    print("%d" % (Ans))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = str(input())
for i in range(Q):
    l,r = map(int,input().split())
    ans = S.count('AC',l-1,r)
    print(ans)


### FIXED CODE ###

N,Q = map(int,input().split())
S = str(input())
cumulative_sum = [0,0]
cont = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        cont += 1
    cumulative_sum.append(cont)
for i in range(Q):
    l,r = map(int,input().split())
    print(cumulative_sum[r]-cumulative_sum[l])
### BUGGY CODE ###

N = int(input())
P = [int(c)-1 for c in input().split()]
Mat = [[min(y, N-1-y, x, N-1-x) for y in range(N)] for x in range(N)]
Removed = [[0]*N for x in range(N)]
# for m in Mat:
#     print(m)
# print()
Dy, Dx = [1,0,-1,0], [0,1,0,-1]
ans = 0
closed = [[False]*N for _ in range(N)]
for p in P:
    y, x = divmod(p, N)
    ans += Mat[y][x]
    #print(p, Mat[y][x])
    Removed[y][x] = True
    #Mat[y][x] -= 1
    st = [(y, x)]
    clsd = [(y, x)]
    closed[y][x] = True
    while st:
        vy, vx = st.pop()
        vr = Removed[vy][vx]
        val = Mat[vy][vx]
        for dy, dx in zip(Dy, Dx):
            uy = vy + dy
            ux = vx + dx
            if not (0<=uy<N and 0<=ux<N):
                continue
            if closed[uy][ux]:
                continue
            ur = Removed[uy][ux]
            if vr:
                if Mat[uy][ux] >= val+1:
                    Mat[uy][ux] = val
                    st.append((uy, ux))
                    closed[uy][ux] = True
                    clsd.append((uy, ux))
            else:
                if Mat[uy][ux] >= val+2:
                    Mat[uy][ux] = val+1
                    st.append((uy, ux))
                    closed[uy][ux] = True
                    clsd.append((uy, ux))
    for y, x in clsd:
        closed[y][x] = False
# for m in Mat:
#     print(m)
print(ans)


### FIXED CODE ###

import numba
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])

#from random import shuffle
#N = 500
#P = list(range(N*N))
#shuffle(P)
#P = np.array(P)

@numba.njit("void(i8,i8[:])")
def proc(N, P):
    ans = 0
    Removed = np.zeros((500, 500), dtype=np.int8)
    Mat = np.zeros((500, 500), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y,x]
        Removed[y,x] = 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy,vx]
            val = Mat[vy,vx]
            #for dy, dx in zip(Dy, Dx):
            for j in range(4):
                dy = Dy[j]
                dx = Dx[j]
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy,ux]
                if vr:
                    if Mat[uy,ux] >= val+1:
                        Mat[uy,ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy,ux] >= val+2:
                        Mat[uy,ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)
### BUGGY CODE ###

def com(n,r,mod):
    k=min(r,n-r)
    C=1
    for i in range(1,k+1):
        C=(C*(n+1-i)*pow(i,mod-2,mod))%mod
    return C

n, m, k = map(int,input().split())
mod = 998244353

cnt = 0
for i in range(k + 1):
    cnt = (cnt + com(n - 1, i, mod) * m * pow(m - 1, n - 1 - i, mod))%mod
print(cnt)

### FIXED CODE ###

def pre_c(n, mod):
    f = [0] * (n + 1)
    g = [0] * (n + 1)
    for i in range(n + 1):
        if i == 0:
            f[i] = 1
            g[i] = 1
        else:
            f[i] = (f[i - 1] * i) % mod
            g[i] = pow(f[i], mod - 2, mod)

    return f, g
n, m, k = map(int,input().split())
mod = 998244353
F, G = pre_c(n - 1, mod)
cnt = 0
for i in range(k + 1):
    temp = F[n - 1] * G[i] * G[n - 1 - i] * m * pow(m - 1, n - 1 - i, mod)
    cnt = (cnt + temp) % mod
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = [[False] * w for _ in range(h)]
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[y][x] = True
        
    kouho_h = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    kouho_w = []
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    flag = False
    for i in kouho_h:
        for j in kouho_w:
            if bomb[i][j] == False:
                flag = True
                break
    if flag:
        print(max_h + max_w)
    else:
        print(max_h + max_w - 1)



if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = defaultdict(lambda : 0)
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[(y, x)] = 1
        
    kouho_h = []
    kouho_w = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    for i in kouho_h:
        for j in kouho_w:
            if bomb[(i, j)] == False:
                print(max_h + max_w)
                exit()
    print(max_h + max_w - 1)



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

import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    e = {i:[] for i in range(1, N+1)}

    for _ in range(N+M-1):
        A, B = map(int, input().split())
        d[A].append(B)
        e[B].append(A)

    root = [k for k,v in e.items() if not v][0]
    dist = [0] * (N+1)

    q = [(root, 0, 0)]
    parents = [0] * (N+1)

    while q:
        s, r, x = q.pop()
        if x>dist[s]:
            dist[s] = x
            parents[s] = r
        for t in d[s]:
            q.append((t, s, x+1))

    for i in range(1, N+1):
        print(parents[i])


if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys
from collections import deque
input=sys.stdin.readline

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

l = []
h = [0] * (N+1)

for _ in range(N+M-1):
    A, B = map(int, input().split())
    d[A].append(B)
    e[B].append(A)
    h[B] += 1

st = set()
for i in range(1, N+1):
    if h[i]==0:
        st.add(i)

l = []
while st:
    i = st.pop()
    l.append(i)
    for j in d[i]:
        h[j] -= 1
        if h[j] == 0:
            st.add(j)

tp = {j:i for i,j in enumerate(l, start=1)}
ans = [0] * (N+1)
for i in range(1, N+1):
    s, t = 0, 0
    for j in e[i]:
        if s < tp[j]:
            s = tp[j]
            t = j
    print(t)
### BUGGY CODE ###

import sys
from math import factorial

input = sys.stdin.readline

Mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k)) % Mod


n, m, k = list(map(int, input().split()))

ans = 0

for i in range(1, n + 1):
    ans += i * (n - i) * m**2 % Mod

for i in range(1, m + 1):
    ans += i * (m - i) * n**2 % Mod

ans *= Cmb(n * m - 2, k - 2)
ans %= Mod

print(ans)


### FIXED CODE ###

import sys
from math import factorial

input = sys.stdin.readline

Mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k)) % Mod


n, m, k = list(map(int, input().split()))

ans = 0

for i in range(1, n + 1):
    ans += i * (n - i) * m**2 % Mod

for i in range(1, m + 1):
    ans += i * (m - i) * n**2 % Mod

ans *= Cmb(n * m - 2, k - 2)
ans %= Mod

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

n = int(input())
li = list(map(int,input().split()))

count = 0
for j in range(1, n + 1):
    for i in li:
        if i == j:
            count += 1
    print(count)
    count = 0

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))

ans = [0] * n
for i in li:
    j = i - 1
    ans[j]  = ans[j] + 1
    
for i in ans:
    print(i)
### BUGGY CODE ###

S = input().replace("BC", "D")
in_ABC = S.count("AD")
count = 0
while in_ABC != 0:
  S = S.replace("AD", "DA", 1)
  count += 1
  in_ABC = S.count("AD")
print(count)  

### FIXED CODE ###

S = input().replace("BC", "D")
acc = 0
ans = 0
for s in S:
  if s == "B" or s == "C":
    acc = 0
    continue
  if s == "A":
    acc += 1
  if s == "D":
    ans += acc
print(ans)
### BUGGY CODE ###

import collections

H, W, M = map(int, input().split())

h, w = [0]*M, [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

ans = 0
for i in mode_h:
    for j in mode_w:
        if ans == H + W - 1 or ans == M:
            print(ans)
            exit()
        if ans < h.count(i) + w.count(j):
            ans = h.count(i) + w.count(j)
            for k in range(M):
                if h[k] == i and w[k] == j:
                    ans -= 1

print(ans)

### FIXED CODE ###

import collections
H, W, M = map(int, input().split())

h, w = [0]*M, [0]*M
dic = set()
for i in range(M):
    h[i], w[i] = map(int, input().split())
    dic.add((h[i],w[i]))

counter = collections.Counter(h)
h_max = max(counter.values())
mode_h = [key for key , value in counter.items() if value == h_max]
counter = collections.Counter(w)
w_max = max(counter.values())
mode_w = [key for key , value in counter.items() if value == w_max]

for i in mode_h:
    for j in mode_w:
        if (i,j) not in dic:
            print(h_max+w_max)
            exit()

print(h_max+w_max-1)
### BUGGY CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l * a[i] // fractions.gcd(l, a[i])
print(sum([l // a[i] % 1000000007 for i in range(n)]) % 1000000007)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
s = 0
for i in range(n): s += l // a[i]
print(s % 1000000007)
### BUGGY CODE ###

#import math
import fractions as math

N = int(input())
A = list(map(int, input().split()))
memo = {}
x = A[1]
for a in A[2:]:
    n = math.gcd(x, a)
    memo[(x, a)] = n
    x = n
max_gcd = x

for i in range(N):
    x = A[0]
    for j in range(N):
        if i == j:
            pass
        else:
            if (x, A[j]) in memo:
                x = memo[(x, A[j])]
            else:
                n = math.gcd(x, A[j])
                memo[(x, A[j])] = n
                x = n
    max_gcd = max(max_gcd, x)
print(max_gcd)

### FIXED CODE ###

#import math
import fractions as math

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

gcd_l, gcd_r = [0], [0]

for l, r in [(A[i], A[N-i-1]) for i in range(N)]:
    gcd_l.append(math.gcd(gcd_l[-1], l))
    gcd_r.append(math.gcd(gcd_r[-1], r))
gcd_r.reverse()

gcd_nums = [gcd_l[-1]] + [math.gcd(gcd_l[i], gcd_r[i+1]) for i in range(N)]
print(max(gcd_nums))
### BUGGY CODE ###

from sys import stdin
from collections import OrderedDict

def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    mod_arr = OrderedDict()
    for i in range(2019):
        mod_arr[i] = 0
    mod_arr[0] += 1
    for i in range(0,len_S+1):
        _ = int(S[len_S-i-1:])
        if i>0: mod = (mod+int(S[len_S-i-1])*10**i)%2019
        else:   mod = _%2019
        mod_arr[mod]+=1
    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)