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

N = int(input())
A = input().split()

px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nz+1) for y in range(ny+1)] for x in range(nx+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[x-1][y][z]*x/s
        if y > 0:
          t += dp[x+1][y-1][z]*y/s
        if z > 0:
          t += dp[x][y+1][z-1]*z/s
        
        dp[x][y][z] += t


print(dp[px][py][pz])

### FIXED CODE ###

N = int(input())
A = input().split()
px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nx+1) for y in range(ny+1)] for z in range(nz+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[z][y][x-1]*x/s
        if y > 0:
          t += dp[z][y-1][x+1]*y/s
        if z > 0:
          t += dp[z-1][y+1][x]*z/s
        
        dp[z][y][x] += t


print(dp[pz][py][px])
### BUGGY CODE ###

class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res
      
    def get_lcp(self, l1, r1, l2, r2):
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok
        
n = int(input())
s = input()

rh = RollingHash(s)

ans = 0
for l1 in range(n):
    for l2 in range(l1+1, n):
        if l2 - l1 < ans or n - l2 < ans:
            continue
        tmp = rh.get_lcp(l1, l2, l2, n)
        ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

def LRS(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = ""
    res_length = 0
  
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
n = int(input())
s = input()

print(len(LRS(s)))
### BUGGY CODE ###

n,x,y=map(int, input().split())
x -= 1
y -= 1
queue = []
zumi = []
result = [[0]* n for i in range(n)]
next_point = []

for i in range(n):
    queue.append(i)
    zumi = []
    result[i][i] = 0
    
    while queue:
        next_point = []
        now = queue.pop(0)
        zumi.append(now)
        
        #次に行ける場所
        if now - 1 >= 0:
            next_point.append(now - 1)
        if now + 1 < n :
            next_point.append(now +1)
        if now == x:
            next_point.append(y)
        if now == y:
            next_point.append(x)
            
        for a in next_point:
            if a in zumi :
                pass
            elif result[i][a] == 0:
                result[i][a] = result[i][now] + 1
                queue.append(a)
                
for i in range(1,n):
    count = 0
    for j in result:
        count += j.count(i)
    print(int(count/2))

### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0]*n #個数を数えるのにバケットを用意する
for i in range(1,n+1): #i<jなるすべての頂点の組について最短距離を求める
    for j in range(i+1,n+1):
        dist1=j-i
        dist2=abs(x-i)+abs(y-j)+1
        dist3=abs(y-i)+abs(x-j)+1
        d=min(dist1,dist2,dist3) #最短距離は上式により求められる
        ans[d]+=1 #最短距離がdとなる組の個数を1増やす
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

import bisect

x,y,z,k = map(int, input().split())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
cc = list(map(int, input().split()))

ab = sorted(a+b for a in aa for b in bb)[:-k-1:-1]
abc = sorted(s+c for s in ab for c in cc)[:-k-1:-1]
print(*abc, sep='\n')


### FIXED CODE ###

x,y,z,k = map(int, input().split())
aa = sorted(list(map(int, input().split())))
bb = sorted(list(map(int, input().split())))
cc = sorted(list(map(int, input().split())))

ab = sorted(a+b for a in aa for b in bb)[:-k-1:-1]
abc = sorted(s+c for s in ab[:k] for c in cc)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

import itertools
from functools import reduce
from operator import mul

def make_divisor_list(n):
    if n < 1:
        return []
    elif n == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, n // 2 + 1):
            if n % i == 0:
                divisor_list.append(i)
        divisor_list.append(n)

        return divisor_list

n, m = map(int, input().split())
d = []
for i in make_divisor_list(m):
    d += [i] * n
count = 0
ans = []
for v in itertools.permutations(d, n):
    if reduce(mul, v) == m:
        if not v in ans:
            ans.append(v)
            count += 1
print(count)

### FIXED CODE ###

mod = 1000000007

# aのp乗を求めるアルゴリズム
# p=62のとき、pの変化は、62->31->30->15->14->7->6->3->2->1->0
# と、半分半分になっていく
# よって、計算量はO(logp)になる
def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        # pが偶数のとき
        halfP = p // 2
        half = modpow(a, halfP)

        # a^(p/2) をhalfとして、half*halfを計算
        return half * half % mod
    else:
        # pが奇数のときは、
        # pを偶数にするために1減らす
        return a * modpow(a, p - 1) % mod


# (10*9*8) / (3*2*1)
# 10*9*8 -> ansMul
# 3*2*1 -> ansDiv
def calcComb(a, b):
    if b > a - b:
        return calcComb(a, a - b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= (a - i)
        ansDiv *= (i + 1)
        ansMul %= mod
        ansDiv %= mod
    # ansMul / ansDivをやりたい
    # ansDivの逆元を使って求める
    ans = ansMul * modpow(ansDiv, mod - 2) % mod
    return ans


n, m = map(int, input().split())
MNkori = m
ans = 1
i = 2
while i * i <= MNkori:
    cnt = 0
    while MNkori % i == 0:
        cnt += 1
        MNkori //= i
    # cntが2^Xとか3^XのXの部分
    ans *= calcComb(n + cnt - 1, n - 1) # N-1はcntと同じ
    ans %= mod
    i += 1
if MNkori != 1:
    # 最後に素数が残ってる分を処理する
    ans *= calcComb(n, n - 1)  # N-1はcntと同じ
    ans %= mod
print(ans)
### BUGGY CODE ###

import copy
A,B,C,k = map(float,input().split())
for _ in range(int(k)):
    a = copy.copy(A)
    b = copy.copy(B)
    c = copy.copy(C)
    A = b + c
    B = c + a
    C = a + b
print(int(A-B))


### FIXED CODE ###

A,B,C,k = map(int,input().split())
s1 = A-B
s2 = B-A
if k%2 == 0:
    print(s1)
elif k%2 == 1:
    print(s2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
temp=a[0]
for i in range(n - 1):
    if temp > 0:
        temp+=a[i+1]
        if temp < 0:
            pass
        else:
            while temp >= 0:
                temp -= 1
                ans += 1
    else:
        temp+=a[i+1]
        if temp > 0:
            pass
        else:
            while temp <= 0:
                temp += 1
                ans += 1
print(ans)


### FIXED CODE ###

import functools
n = int(input())
a = list(map(int, input().split()))

@functools.lru_cache()
def memo(n):
    ans1 = 0
    ans2 = 0
    now = 0

    for i in range(n):
        now += a[i]
        if i % 2 == 0:
            if now <= 0:
                ans1 += 1 - now
                now = 1
        else:
            if now >= 0:
                ans1 += now + 1
                now = -1

    now = 0

    for i in range(n):
        now += a[i]
        if i % 2 == 1:
            if now <= 0:
                ans2 += 1 - now
                now = 1
        else:
            if now >= 0:
                ans2 += now + 1
                now = -1
    
    return min([ans1,ans2])

print(memo(n))
### BUGGY CODE ###

import bisect

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
a=[que[1]]
min=0
l,r=0,0
j=1
tmp=que[1]
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        a.insert(  bisect.bisect_left(a,que[1]), que[1] )
        if j%2==0: r+=1
        else: l+=1
        
        if a[l]!=a[r]: min+=abs(tmp-que[1])
        else: min+=abs(tmp-que[1])-abs(a[l]-tmp)
        tmp=a[l]

    elif que[0]==2:
        print(tmp,min+b)

### FIXED CODE ###

import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<-l[0]:
                heapq.heappush(l,-q1)
                heapq.heappush(r,-l[0])
            else:
                heapq.heappush(r,q1)
                heapq.heappush(l,-r[0])
        

        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,a+b)
### BUGGY CODE ###

from collections import deque

S = input().rstrip('\r\n')
S_list = deque(S)


Q = int(input())
for _ in range(Q):
    query = input().rstrip('\r\n')
    t, f, c = '', '', ''
    if len(query) == 1:
        t = query
    else:
        t, f, c = query.split(' ')
    if t == '1':
        S_list.reverse()
    else:
        if f == '1':
            S_list.appendleft(c)
        else:
            S_list.append(c)
print(''.join(S_list))

### FIXED CODE ###

from collections import deque

S = input().rstrip('\r\n')
S_list = deque(S)
is_reverse = False

Q = int(input())
for _ in range(Q):
    query = input().rstrip('\r\n')
    t, f, c = '', '', ''
    if len(query) == 1:
        t = query
    else:
        t, f, c = query.split(' ')
    if t == '1':
        is_reverse = not is_reverse
    else:
        if f == '1':
            if is_reverse:
                S_list.append(c)
            else:
                S_list.appendleft(c)
        else:
            if is_reverse:
                S_list.appendleft(c)
            else:
                S_list.append(c)
if is_reverse:
    S_list.reverse()
print(''.join(S_list))
### BUGGY CODE ###

def c_marks():
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    score = 1
    for a in A[:K]:
        score *= a

    ans = ['Yes' if A[i + K] > A[i] else 'No' for i in range(N - K)]
    return ' '.join(ans)

print(c_marks())

### FIXED CODE ###

def c_marks():
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    ans = ['Yes' if A[i + K] > A[i] else 'No' for i in range(N - K)]
    return '\n'.join(ans)

print(c_marks())
### BUGGY CODE ###

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

a.sort()
tn = 1
cnt = 0
suffix = 0
for i in range(n):
    
    for j in range(suffix, n-1):
        if a[j] == tn:
            cnt += 1
            suffix = j
    print(cnt)
    cnt = 0
    tn += 1

### FIXED CODE ###

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

a.sort()
tn = 1
cnt = 0
suffix = 0
for i in range(n):
    for j in range(suffix, n-1):
        if a[j] == tn:
            cnt += 1
            suffix = j+1
        else:
            break
    print(cnt)
    cnt = 0
    tn += 1
### BUGGY CODE ###

import bisect

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

ans = 0
larger_indexes = [-1, -1, N, N]
for i, p in P:
  idx = bisect.bisect_left(larger_indexes, i)
  ir1, ir2 = larger_indexes[idx], larger_indexes[idx+1]
  il1, il2 = larger_indexes[idx-1], larger_indexes[idx-2]
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  bisect.insort(larger_indexes, i)

print(ans)

### FIXED CODE ###

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


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

K=int(input())
number=[]
for i in range(3234566668):
    k=str(i)
    if all([abs(int(k[j])-int(k[j-1]))<=1 for j in range(1,len(k))]):
        number.append(k)
print(number[K])

### FIXED CODE ###

from collections import deque
K=int(input())
queue=deque([1,2,3,4,5,6,7,8,9])
for i in range(K):
    k=queue.popleft()
    if k%10!=0:
        queue.append(10*k+(k%10)-1)
    queue.append(10*k+(k%10))
    if k%10!=9:
        queue.append(10*k+(k%10)+1)
print(k)
### BUGGY CODE ###

n = int(input())
s = list(input())

def main():
    if(n<4):
        return 0
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            nk = j-i
            for k in range(j+1,n):
                
                if((k-j)==nk):
                    continue
                if(s[i]==s[j] or s[j]==s[k] or s[i]==s[k]):
                    continue
                ans += 1
    return ans
print(main())

### FIXED CODE ###

n = int(input())
s = list(input())
def main():
    ans = s.count('R') * s.count('G') * s.count('B')

    if(n<4):
        return 0
    
    for i in range(n):
        for j in range(i+1,n):
            k= 2*j-i
            if k>=n:
                continue
            if(s[i]==s[j] or s[i]== s[k] or s[j]==s[k]):
                continue
            ans -= 1
    return ans
print(main())
### BUGGY CODE ###

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

if abs(N - M) > 1:
	print(0)

elif N == M:
	answer = 2
	for i in range(1, N+1):
		answer = answer * i * i

	answer = answer % (1000000000 + 7)
	print (answer)

elif N > M:
	answer = 1
	j = 1
	for i in range(2, N+1):
		answer = answer * i * j
		j = i

	answer = answer % (1000000000 + 7)
	print(answer)

else:
	answer = 1
	j = 1
	for i in range(2, M+1):
		answer = answer * i * j
		j = i

	answer = answer % (1000000000 + 7)
	print(answer)

### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
mod = 10**9+7

if N < M:
    N, M = M, N

if N == M:
	answer = 2
	for i in range(2, N+1):
		answer = answer * i * i
		answer = answer % mod
	print (answer)

elif N == M+1:
	answer = 1
	for i in range(2, N):
		answer = answer * i * i
		answer = answer % mod
	answer = answer * N % mod
	print(answer)

else:
	print(0)
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1,n+1):
  p = p*i
ap = p%1000000007
print(ap)


### FIXED CODE ###

n = int(input())
import math
p = math.factorial(n)
ap = p%1000000007
print(ap)
### BUGGY CODE ###

#pragma GCC optimize("Ofast")

a=int(input())

d=list(map(int,input().split()))

sum=0

for i in range(a-1):
  for j in range(i+1,a):
    sum=sum+d[i]*d[j]

mod = pow(10,9)+7
print(pow(sum,1,mod))

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

total=sum(alst)
sum=0

# for i in range(n-1):
#   for j in range(i+1,n):
#     sum=pow(sum+alst[i]*alst[j],1,MOD)

# print(sum)

for a in alst:
  sum = sum+a * (total - a)
  sum %= MOD

sum *= pow(2, MOD - 2, MOD)
sum %= MOD
print(sum)
### BUGGY CODE ###


n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]



for b, c in bc:
    a.sort()
    for i in range(b):
        if a[i]>=c:
            idx = i
            break
    else:
        idx = b
    a[0:idx] = [c] * idx

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
*a, = map(int, input().split())
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(key=lambda x:-x[1])
i = 0

for b,c in bc:
    for j in range(i, min(n, i+b)):
        if a[j]<c:
            a[j] = c
    i = i+b
print(sum(a))
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

tmp = [10 ** 12 for _ in range(N)]
tmp[0] = 0
tmp[1] = abs(H[1] - H[0])

for i in range(2, N):
    for k in range(1, K+1):
        if i - k >= 0:
            tmp[i] = min(tmp[i], tmp[i - k] + abs(H[i] - H[i - k]))
        else:
            break
print(tmp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

tmp = [10 ** 12 for _ in range(N)]
tmp[0] = 0
tmp[1] = abs(H[1] - H[0])

for i in range(2, N):
    for k in range(1, K+1):
        if i - k >= 0:
            tmp[i] = min(tmp[i], tmp[i - k] + abs(H[i] - H[i - k]))
        else:
            break
print(tmp[N-1])
### BUGGY CODE ###

N,M,Q=map(int,input().split())
Town=[[0,0] for i in range(M)]
for i in range(M):
  Town[i][0],Town[i][1]=map(int,input().split())
Town.sort(key=lambda x:x[0])

def BS_left(x,L):
  L_copy=L[:]
  l=len(L_copy)
  left=0
  if L[l-1]<x:
    return l-1
  else:
    while l>2:
      if L_copy[l//2]<x:
        L_copy=L_copy[l//2:l]
        left+=l//2
      else:
        L_copy=L_copy[0:l//2+1]
      l=len(L_copy)
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L):
  L_copy=L[:]
  l=len(L_copy)
  right=l-1
  if L[0]>x:
    return 0
  else:
    while l>2:
      if L_copy[l//2]<=x:
        L_copy=L_copy[l//2:l]
      else:
        L_copy=L_copy[0:l//2+1]
        right+=-l//2+1
      l=len(L_copy)
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  TownL=list(zip(*Town))[0]
  newTown=Town[BS_left(p,TownL)+1:BS_right(q,TownL)]
  if len(newTown)==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    TownR=list(zip(*newTown))[1]
    if BS_right(q,TownR)==1 and TownR[0]>q:
      print(0)
    else:
      print(BS_right(q,TownR))

### FIXED CODE ###

N,M,Q=map(int,input().split())
Train=[[int(i) for i in input().split()] for i in range(M)]
Map=[[0]*(N+1) for i in range(N+1)]
for i in Train:
  x,y=i[0],i[1]
  Map[y][x]+=1
for a in range(1,N+1):
  for b in range(1,N+1):
    if b<=N-1:
      Map[a][b+1]=Map[a][b]+Map[a][b+1]
    if a>=2:
      Map[a][b]=Map[a-1][b]+Map[a][b]
for i in range(Q):
  p,q=map(int,input().split())
  print(Map[q][q]-Map[q][p-1]-Map[p-1][q]+Map[p-1][p-1])
### BUGGY CODE ###

import queue
import copy

H,W = map(int,input().split())
c =[]
c.append(['#' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
for _ in range(H):
    tmp = list('#'+input()+'#')
    ans_tmp = []
    for i in range(W+2):
        if tmp[i] == '#':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['#' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])
q = queue.Queue()

def bfs(x,y):
    global q
    global c
    global ans
    q.put([x,y])

    while not q.empty():
        x,y = q.get()
        """
        if [x,y] == [gx,gy]:
            return ans[gy][gx]
        """
        if c[y][x-1] == '.':
            q.put([x-1,y])
            ans[y][x-1] = min(ans[y][x] + 1,ans[y][x-1])
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.put([x+1,y])
            ans[y][x+1] = min(ans[y][x] + 1,ans[y][x+1])
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.put([x,y-1])
            ans[y-1][x] = min(ans[y][x] + 1,ans[y-1][x])
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.put([x,y+1])
            ans[y+1][x] = min(ans[y][x] + 1,ans[y+1][x])
            c[y+1][x] = '#'

c_copy = copy.deepcopy(c)

for i in range(1,H+1):
    for j in range(1,W+1):
        if c[i][j] == '#':
            c = copy.deepcopy(c_copy)
            bfs(i,j)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)
"""))
### BUGGY CODE ###

s = input()
dp = [0]*2019
dp[0] = 1
total = int(s)
k=1

for n in list(map(int, list(s))):
  dp[total%2019]+=1
  total -= n*(10**(len(s)-k))
  k+=1
  

count=0
for i in range(2019):
  m=dp[i]
  count += m*(m-1)/2
 
print(int(count))

### FIXED CODE ###

s = input()[::-1]

dp = [0]*2019
dp[0]=1
total = 0
a = 1

for i in list(s):
  total += int(i)*a
  total %= 2019
  dp[total] += 1
  a *= 10
  a %= 2019
count=0
  
for i in range(2019):
    count += dp[i]*(dp[i]-1)//2
 
print(count)
### BUGGY CODE ###

def euclid(a, b):
    if a < b:
        a, b = (b, a)

    while True:
        r = a % b
        if r == 0:
            break
        a, b = (b, r)

    return b


if __name__ == '__main__':
    n, x = tuple(map(int, input().split()))
    points = [int(x) for x in input().split()]
    if not x in points:
        points.append(x)

    buf = [abs(points[i + 1] - points[i]) for i in range(len(points) - 1)]
    while len(buf) > 1:
        buf = [euclid(buf[i + 1], buf[i]) for i in range(len(buf) - 1)]

    print(buf[0])

### FIXED CODE ###

from functools import reduce

def euclid(a, b):
    if a < b:
        a, b = (b, a)

    while True:
        r = a % b
        if r == 0:
            break
        a, b = (b, r)

    return b


if __name__ == '__main__':
    n, x = tuple(map(int, input().split()))
    points = [int(x) for x in input().split()]

    buf = [abs(p - x) for p in points]
    print(reduce(lambda a,b: euclid(a, b), buf))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
b = c = 0

for i in range(n):
    s.append(s[i] + a[i])

for i in set(s):
    b = s.count(i)
    if b > 1:
        c += int(b*(b-1)/2)
print(c)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
b = 1
c = 0

for i in range(n):
    s.append(s[i] + a[i])
s.sort()
s.append('\0')

for i in range(1, len(s)):
    if s[i] == s[i-1]:
        b += 1
        continue
    c += int(b*(b-1)/2)
    b = 1
print(c)