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

N=int(input())
vertexes=[[] for i in range(N)]
edges=[[int(s) for s in input().split()] for i in range(N-1)]
#頂点ごとに、頂点から伸びる辺のデータを記録
for e in edges:
  vertexes[e[0]-1].append([e[1]-1,e[2]])
  vertexes[e[1]-1].append([e[0]-1,e[2]])

#幅優先探索の開始（v_possibleに入った順に頂点を訪れる）
answer=[-1 for i in range(N)]  #到達していない頂点は-1
answer[0]=0
v_possible=[] #到達可能な頂点と、辺の情報
v=0 #現在の位置
for i in range(N-1):
  for e in vertexes[v]: #行き先の更新
    v_possible.append([e[0],v,e[1]]) #[行き先,つながる頂点,距離]
  for j in v_possible:
    if answer[j[0]]==-1: #まだ訪れていないなら移動
      answer[j[0]]=(answer[j[1]]+j[2])%2
      v=j[0]
      break

#答を出力
for i in range(N):
  print(answer[i])


### FIXED CODE ###

N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1): #辺の情報と距離を記録
  u, v, w = map(int, input().split())
  edge[u-1].add((v-1, w))
  edge[v-1].add((u-1, w))

#幅優先検索
dist = [0] * N #距離
stack = [0]
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to, w in edge[vrt].copy():
    stack.append(to)
    dist[to] = dist[vrt] + w
    edge[vrt].discard((to, w))
    edge[to].discard((vrt, w))
    
for i in range(N):
  print(dist[i]%2)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a*b // gcd(a,b)

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

A, B = map(int,input().split())

g = divisor(gcd(A,B))
#g.sort()

cnt = 0
for i in g:
    if len(divisor(i)) <= 2:
        cnt += 1

print(cnt)


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a*b // gcd(a,b)

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

A, B = map(int,input().split())

g = divisor(gcd(A,B))
#g.sort()

cnt = 0
for i in g:
    if len(divisor(i)) <= 2:
        cnt += 1

print(cnt)
### BUGGY CODE ###

import math

input_num = int(input())
input_numline = list(map(int,input().split(' ')))
q = int(input())

op_list = []
for i in range(q):
    op_list.append(list(map(int,input().split(' '))))

maxnum = 100000

num_list = [0 for m in range(maxnum+1)]

for n in input_numline:
    num_list[n] += 1

for o in op_list:
    num_list[o[1]] += num_list[o[0]]
    num_list[o[0]] = 0

    ans = 0
    for j in range(maxnum+1):
        ans += j*num_list[j]
    print(ans)


### FIXED CODE ###

import math

input_num = int(input())
input_numline = list(map(int,input().split(' ')))
q = int(input())

op_list = []
for i in range(q):
    op_list.append(list(map(int,input().split(' '))))

maxnum = 100000

num_list = [0 for m in range(maxnum+1)]

for n in input_numline:
    num_list[n] += 1

ans = 0

for j in range(maxnum+1):
    ans += j*num_list[j]

for o in op_list:
    ans -= o[0]*num_list[o[0]]
    ans += o[1]*num_list[o[0]]
    num_list[o[1]] += num_list[o[0]]
    num_list[o[0]] = 0

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

ans=1
n=int(input())
for i in range(1,n+1):
    ans*=i
print(ans%(10**9+7))

### FIXED CODE ###

ans=1
n=int(input())
for i in range(1,n+1):
    ans*=i
    ans=ans%(10**9+7)
print(ans)
### BUGGY CODE ###

def prime(max):
  num = [True] * (max + 1)
  n = 2
  while n ** 2 <= max:
    if num[n]:
      m = n + n
      while m <= max:
        num[m] = False
        m += n
    n += 1
  return [i for i in range(2, max + 1) if num[i]]

Q = int(input())
LR = []
max = 0
for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < int(_input[1]):
    max = int(_input[1])

prime = prime(max)

for i in range(Q):
  sum = 0
  for num in range(LR[i][0], LR[i][1]+1):
    if (num in prime) and ((num+1) / 2 in prime):
      sum = sum + 1
  print(sum)

### FIXED CODE ###

num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

for i in range(3, 100001):
  c[i] = c[i] + c[i-1]

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])
### BUGGY CODE ###

import sys
n = int(input())
a = [int(a) for a in input().split()]

for i in range(n):
  if a.count(a[i]) > 1:
    print('NO')
    sys.exit()

print('YES')

### FIXED CODE ###

import sys
n = int(input())
a = [int(a) for a in input().split()]

done = {}
flag = 0
for i in range(n):
  try:
    if done[a[i]] > 0:
      flag = 1
    done[a[i]] = 1
  except:
    done[a[i]] = 1

if flag:
  print('NO')
else:
  print('YES')
### BUGGY CODE ###

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

X = []
for i in range(n):
    X.append([x[i],i])

X.sort(reverse=True)
ans = []
for i in range(n):
    sub = X.pop(i)
    ans.append([X[(n // 2) - 1][0],sub[1]])
    X.insert(i, sub)

ans.sort(key = lambda x: x[1])

for i in range(n):
    print(ans[i][0])

### FIXED CODE ###

import bisect
n = int(input())
x = list(map(int, input().split()))

cp = sorted(x, reverse=False)
for i in range(n):
    s = bisect.bisect_left(cp, x[i])
    if s + 1 <= n // 2:
        print(cp[n // 2])
    else:
        print(cp[(n // 2) - 1])
### BUGGY CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      for j in range(n):
        y = l[j]+p[j][w]
        if y>K:
          t_a+=1
          l = [0]*n
          for z,b in enumerate(p):
            l[z] = b[w]
          break
        else:
          l[j]=y
    ans = min(ans,t_a)

  print(ans)
  
main()

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [-1]*200010
now = 0
l[0] = 0
ans = -100

for i in range(n):
    a[i] -= 1

for i in range(n*4):
    k -= 1
    now = a[now] #転送された場所
    l[now] += 1
    if l[now] == 2: #3ループ目の頭
        loop = l.count(1) + 1
        k %= loop
    if k == 0:
        ans = now + 1
        break

print(max(ans, -1))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()
### BUGGY CODE ###

n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
 
        return divisor_list
 
minpos= min(pos2)
divs=make_divisor_list(minpos)[::-1]
for j in divs:
    if all(x%j==0 for x in pos2):
        ans=j
        break
print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
 
        return divisor_list

if n==1: ans=pos2[0]
else:
    minpos= min(pos2)
    divs=make_divisor_list(minpos)[::-1]
    if divs[0]==1:ans=1
    else:
        for j in divs:
            if all(x%j==0 for x in pos2):
                ans=j
                break
print(ans)
### BUGGY CODE ###

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

# 数値Aの頻度
ndic = {}
for i in A:
    if i in ndic:
        ndic[i] += 1
    else:
        ndic[i] = 1

# 2つの同じ数値Aの選び方
cdic = {}
for j in ndic:
    cdic[j] = int((ndic[j] * (ndic[j] -1)) / 2)


for i in A:
    cmb = 0
    for j in cdic:
        if i == j and cdic[j] > 0:
            cmb += cdic[j] - (ndic[j] - 1)
        else:
            cmb += cdic[j]
    print(cmb)

### FIXED CODE ###

import collections

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

# 数値Aの頻度
ndic = collections.Counter(A)

mem = {}
tcmb = 0
for j in ndic:
    if ndic[j] == 1:
        continue
    
    if ndic[j] in mem:
        tcmb += mem[ndic[j]]
    else:
        mem[ndic[j]] = int((ndic[j] * (ndic[j] -1)) / 2)
        tcmb += mem[ndic[j]]
        
for i in A:
    cmb  = tcmb - (ndic[i] - 1)
    print(cmb)
### BUGGY CODE ###

n=int(input())
ans = 1
for i in range(2,n+1):
  ans *= i
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
ans = 1
for i in range(2,n+1):
  ans = ans*i%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    if d[v]<p[0]:
      continue
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
for i in reversed(range(n)):
  print(ans_list[i])


### FIXED CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

inf = float("inf")
cost = [inf]*N

cost[0] = 0
m = min
for i in range(N):
  for step in range(1, K+1):
    if i + step < N:
      cost[i+step] = m(cost[i+step], cost[i] + abs(h[i] - h[i+step]))

print(cost[-1])

### FIXED CODE ###

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

  inf = float("inf")
  cost = [inf]*N


  cost[0] = 0
  for i in range(1, N):
    cost[i] = min([cost[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
  print(cost[-1])

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

import math
import itertools
from numba import njit

@njit
def culc_gcd_of_3(l_p):
    answer = 0
    for x in l_p:
        temp = math.gcd(x[0], x[1])
        answer += math.gcd(x[2], temp)
    
    return answer


K = int(input())
l_p = list(itertools.product(range(1, K+1), range(1, K+1), range(1, K+1)))

culc_gcd_of_3(l_p)

### FIXED CODE ###

N = int(input())

N_str = str(N)
flag = 0
for x in N_str:
    if x == '7':
        print('Yes')
        flag = 1
        break

if not flag:
    print('No')
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N + 1):
	if i < N:
		ans += i % (i + 1)
print(ans)

### FIXED CODE ###

N = int(input())
ans = (N * (N - 1)) // 2
print(int(ans))
### BUGGY CODE ###

from collections import defaultdict

MOD = 998244353
N,S = map(int,input().split())
A = map(int,input().split())

dp = defaultdict(int)
dp[(0,0)] = 1
for a in A:
    for (size,total),cnt in tuple(dp.items()):
        if total+a <= S:
            dp[(size+1,total+a)] += cnt
            dp[(size+1,total+a)] %= MOD

res = 0
c = 1
for size in reversed(range(1,N+1)):
    res += c*dp[(size,S)]
    res %= MOD
    c *= 2
    c %= MOD
print(res)

### FIXED CODE ###

from collections import defaultdict

MOD = 998244353
N,S = map(int,input().split())
A = map(int,input().split())

dp = [0]*(S+1)
dp[0] = 1
for a in A:
    ndp = [0]*(S+1)
    for total,cnt in enumerate(dp):
        ndp[total] += (dp[total]*2)%MOD
        if total+a <= S:
            ndp[total+a] += dp[total]
            ndp[total+a] %= MOD
    dp = ndp

print(dp[-1]%MOD)
### BUGGY CODE ###

N,K = list(map(int,input().split(" ")))
hs = list(map(int,input().split(" ")))
dp = [9999999999999] * N

dp[0] = 0
for i in range(1,N):

    stepLim = min(K,i)
    temp = 9999999999999999999
    for j in range(1,stepLim + 1):
        ind = i-j
        c = dp[ind]+abs(hs[i]-hs[ind])
        if temp >c:
                temp = c
    dp[i] = temp
print(dp[-1])

### FIXED CODE ###

N,K = list(map(int,input().split(" ")))
hs = list(map(int,input().split(" ")))
dp = [9999999999999] * N

dp[0] = 0
for i in range(1,N):
#ind → i-1 ~ i-stepLim -1   [i-stepLim -1:i]
    stepLim = min(K,i)
    temp = 9999999999999999999
    dp[i] = min([d+abs(hs[i]-h) for d,h in zip(dp[i-stepLim:i],hs[i-stepLim:i])])
print(dp[-1])
### BUGGY CODE ###

# -*- coding utf-8 -*-

k,s=map(int,input().split())

ans=0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s-x==y+z:
                ans+=1
    
print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-

k,s=map(int,input().split())

ans=0

for x in range(k+1):
    for y in range(k+1):
        if 0<=s-x-y<=k:
            ans+=1
    
print(ans)
### BUGGY CODE ###

n=int(input())
from math import sqrt
m=int(sqrt(n))
for i in range(m,n+1):
  if n%i==0:
    print(len(str(i)))
    exit()

### FIXED CODE ###

from numpy import sqrt
n=int(input())
r=int(sqrt(n))
for i in range(r):
  if n % (r-i) == 0:
    m = n // (r-i)
    print(len(str(m)))
    exit()
### BUGGY CODE ###

N, K = map(int, input().split())
p = input().split()
ex = [0 for i in range(N)]
E=0
def expectation(n):
    return (n+1)/2


for i in range(N):
    p[i] = int(p[i])
    ex[i] = expectation(p[i])


for i in range(N-K+1):
    newE = 0
    for j in range(K):
        newE += ex[i+j]

    if newE > E:
        E = newE

    

print(E)



    


### FIXED CODE ###

N, K = map(int, input().split())
p = input().split()
bubun = [0 for i in range(N)]
sums= [0 for i in range(N+K)]
E=0
S=0

for i in range(N):
    p[i] = int(p[i])
    


sums[0] = p[0]
for i in range(N-1):
    sums[i+1] = sums[i] + p[i+1]

for i in range(N):
    if i == 0:
        bubun[i] = sums[K-1]
    else:
        bubun[i] = sums[i+K-1]-sums[i-1]

for i in range(N):

    if bubun[i] > S:
        S = bubun[i]


E=(S+K)/2

print(E)
### BUGGY CODE ###

times, jump = [int(i) for i in input().split()]
line = input()
list1 = []
if times <= 1:
  print("%s" % 0)
else: 
  for i in line.split():
    if i:
      list1.append(int(i))
  mem = [0] * times
  mem[-2] = abs(list1[-1] - list1[-2])
  for i in range(len(list1)-3, -1, -1):
    ans = float("inf")
    end = min(len(list1), i+jump+1)
    for k in range(i+1, end):
      ans = min(ans, abs(list1[i] - list1[k]) + mem[k])
    mem[i] = ans
  print("%s" % mem[0])


### FIXED CODE ###

times, jump = [int(i) for i in input().split()]
line = input()
list1 = []
if times <= 1:
  print("%s" % 0)
else: 
  for i in line.split():
    if i:
      list1.append(int(i))
  mem = [0] * times
  mem[-2] = abs(list1[-1] - list1[-2])
  for i in range(len(list1)-3, -1, -1):
    ans = float("inf")
    end = min(len(list1), i+jump+1)
    for k in range(i+1, end):
      ans = min(ans, abs(list1[i] - list1[k]) + mem[k])
    mem[i] = ans
  print("%s" % mem[0])
### BUGGY CODE ###

from collections import deque
h,w = map(int, input().split())
al = [input() for _ in range(h)]

inf = 10**9
f = [[inf]*w for _ in range(h)]
q = deque()
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            f[hi][wi] = 0
            q.append((hi,wi))

while len(q)>0:
    hi,wi = q.pop()
    c = f[hi][wi]

    for dh,dw in [[0,1],[1,0],[0,-1],[-1,0]]:
        nh = hi+dh
        nw = wi+dw
        if h>nh>=0 and w>nw>=0:
            if f[nh][nw]>c+1:
                f[nh][nw] = c+1
                q.append((nh,nw))

res = 0
for hi in range(h):
    for wi in range(w):
        res = max(res,f[hi][wi])
print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
h,w = map(int, input().split())
al = [list(input()) for _ in range(h)]
cnt = 0

q = []
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            q.append((hi,wi))

while len(q)>0:
    nq = []
    cnt += 1
    for hi,wi in q:
        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            if h>hi+d[0]>=0 and w>wi+d[1]>=0:
                if al[hi+d[0]][wi+d[1]]==".":
                    al[hi+d[0]][wi+d[1]] = "#"
                    nq.append((hi+d[0], wi+d[1]))
    q = nq

print(cnt-1)
### BUGGY CODE ###

import collections
import sys
import numpy as np

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})
C1, C2, C3 = ac[1], ac[2], ac[3]
K = C1 + C2 + C3
dp = np.zeros((K + 3, C2 + C3 + 2, C3 + 1), dtype=np.float64)


def solve(c1, c2, c3):
    for i3 in range(c3 + 1):
        for i2 in range(c2 + c3 + 1):
            for i1 in range(N - i2 - i3 + 1):
                isum = i1 + i2 + i3
                if isum == 0:
                    continue
                i0 = N - i1 - i2 - i3
                if i0 < 0:
                    continue
                e = i0
                if i1 > 0:
                    e += i1 * (1.0 + dp[i1 - 1, i2, i3])
                if i2 > 0 and i1 <= K:
                    e += i2 * (1.0 + dp[i1 + 1, i2 - 1, i3])
                if i3 > 0 and i2 + 1 <= c2 + c3:
                    e += i3 * (1.0 + dp[i1, i2 + 1, i3 - 1])
                dp[i1, i2, i3] = e / isum
    return dp[c1, c2, c3]


if __name__ == "__main__":
    print(solve(C1, C2, C3))


### FIXED CODE ###

import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})


def solve(c1, c2, c3):
    K = c1 + c2 + c3
    L = K + 1
    L2 = L ** 2
    dp = [0.0] * L ** 3
    for i3 in range(c3 + 1):
        for i2 in range(c2 + c3 + 1):
            for i1 in range(N - i2 - i3 + 1):
                isum = i1 + i2 + i3
                if isum == 0:
                    continue
                i0 = N - i1 - i2 - i3
                if i0 < 0:
                    continue
                e = i0
                if i1 > 0:
                    e += i1 * (1.0 + dp[(i1 - 1) * L2 + i2 * L + i3])
                if i2 > 0 and i1 <= K:
                    e += i2 * (1.0 + dp[(i1 + 1) * L2 + (i2 - 1) * L + i3])
                if i3 > 0 and i2 + 1 <= c2 + c3:
                    e += i3 * (1.0 + dp[i1 * L2 + (i2 + 1) * L + i3 - 1])
                dp[i1 * L2 + i2 * L + i3] = e / isum
    return dp[c1 * L2 + c2 * L + c3]


if __name__ == "__main__":
    print(solve(ac[1], ac[2], ac[3]))
### BUGGY CODE ###


N = int(input())
A = list(map(int,input().split()))
value = 0
plus = 0
ans = 0

for i in range(N-1):
    for j in range(N-i-1):
        plus = A[i]*A[i+j+1] % (1*10**9 + 7)
        value = (value + plus) % (1*10**9 + 7)
        

print(value)


### FIXED CODE ###

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

A_sum = sum(A)

value = 0
ans = 0

for i in range(N-1):
    A_sum -= A[i]
    value += A[i]*A_sum

ans = value % (1*10**9+7)

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

def m():
    N, X, Y = map(int, input().split())
    ans = [0] * (N+1)
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            p = min(abs(j - i), abs(X - i) + 1 + abs(Y - j), abs(Y - i) + 1 + abs(X - j))
            ans[p] += 1
    for a in range(1, N):
        print(ans[a]//2)

m()


### FIXED CODE ###

def m():
    N, X, Y = map(int, input().split())
    ans = [0] * (N+1)
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            p = min(abs(j - i), abs(X - i) + 1 + abs(Y - j), abs(Y - i) + 1 + abs(X - j))
            ans[p] += 1
    for a in range(1, N):
        print(ans[a]//2)

m()