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

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
for i in range(len(s)):
    num_int = pow(10, i) * int(s[-i-1]) + num_int
    res = num_int % mod
    mod_dict[res] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

print(ans)

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
s = s[::-1]
t = 1
for i in range(len(s)):
    num_int += t * int(s[i])
    num_int %= mod
    t *= 10
    t %= mod
    mod_dict[num_int] += 1

for i in mod_dict:
    ans += ((mod_dict[i] - 1) * mod_dict[i]) // 2

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

N,M = (int(i) for i in input().split())
A = sorted([int(i) for i in input().split()])
e = []
for k, v in sorted([[int(i) for i in input().split()] for i in range(M)], key=lambda x: -x[1]):
    e.append((k,v))
for B,C in e:
    for j in range(B):
        if min(A) < C:
            A[A.index(min(A))] = C
        else:
            print(sum(A))
            exit()
print(sum(A))


### FIXED CODE ###

N,M = (int(i) for i in input().split())
A = sorted([int(i) for i in input().split()])
e,p = [(0,0)],0
for k, v in sorted([[int(i) for i in input().split()] for i in range(M)], key=lambda x: -x[1]):
    e.append((e[p][0]+k,v))
    p+=1

p = 1
for i in range(min(e[-1][0],len(A))):
    B,C = e[p]
    if A[i]<C:
        A[i]=C
    else:
        break
    if i == B-1:
        p+=1
print(sum(A))
### BUGGY CODE ###

import copy

n = int(input())
arr = []
for i in range(n):
    a = int(input())
    arr.append(a)
for i in range(n):
    brr = copy.copy(arr)
    brr.pop(i)
    print(max(brr))

### FIXED CODE ###

import copy

n = int(input())
arr = [int(input()) for i in range(n)]
brr = sorted(arr, reverse=True)
ind = arr.index(max(arr))
# for i in range(n):
#     brr = copy.copy(arr)
#     brr.pop(i)
#     print(max(brr))
for i in range(n):
    if i == ind:
        print(brr[1])
    else:
        print(brr[0])
### BUGGY CODE ###

import sys


class mydeque:
    class cell:
        def __init__(self,x,y = None,z = None):
            self.data = x
            self.next = y
            self.prev = z

    def __init__(self):
        head = mydeque.cell(None)
        head.next = head
        head.prev = head
        self.size = 0
        self.head = head

    def push_front(self,x):
        h = self.head
        q = h.next
        p = mydeque.cell(x,q,h)
        h.next = p
        q.prev = p
        self.size += 1

    def push_back(self,x):
        h = self.head
        p = h.prev
        q = mydeque.cell(x,h,p)
        h.prev = q
        p.next = q
        self.size += 1

    def delete_top(self):
        h = self.head
        top = h.next
        nexttop = top.next
        h.next = nexttop
        nexttop.prev = h
        self.size -= 1

    def delete_last(self):
        h = self.head
        last = h.prev
        prevlast = last.prev
        h.prev = prevlast
        prevlast.next = h
        self.size -= 1

    def delete_find(self,target):
        h = self.head
        now_data = h.next
        while now_data != self.head:
            if now_data.data == target:
                next_now = now_data.next
                prev_now = now_data.prev
                next_now.prev = prev_now
                prev_now.next = next_now
                self.size -= 1
                break
            now_data = now_data.next

    def allprint(self):
        h = self.head.next
        for i in range(self.size):
            if i == self.size - 1:
                print(h.data)
            else:
                print(h.data, end=" ")
                h = h.next

# with open("input.txt","r") as f:
queue = int(input())
length = 0
myd = mydeque()
for q in range(queue):
    command = [n for n in input().strip("\n").split(' ')]
    if command[0] == "insert":
        myd.push_front(command[1])
    elif command[0] == "delete":
        myd.delete_find(command[1])
    elif command[0] == "deleteFirst":
        myd.delete_top()
    else:
        myd.delete_last()
myd.allprint()

### FIXED CODE ###

from collections import deque
query = int(input())
l = deque()
for _ in range(query):
    command = input().strip()
    if command == "deleteFirst":
        try:
            l.popleft()
        except:
            pass
    elif command == "deleteLast":
        try:
            l.pop()
        except:
            pass
    else:
        command, value = command.split(" ")
        if command == "insert":
            l.appendleft(int(value))
        elif command == "delete":
            try:
                l.remove(int(value))
            except:
                pass
print(*l)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def find(x):#xの親を見つける
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):#要素xとｙを併合させる
  x,y=find(x),find(y)#xとyの親の検索
  if x!=y:#親が異なる場合併合させる
    if x>y:
        x,y=y,x#小さい方をxとする. これにより要素の値が小さいものを優先して木の根とする. 
    par[x]+=par[y] #値を無向木の要素数の和にする.
    par[y]=x #枝側は根の位置を格納

def same(x, y):#要素xと要素yが同じ無向木に所属しているかを判定する
  return find(x) == find(y)#同じ値を持つか否か

def size(x):#要素xが所属する無向木の大きさを返す
  return-par[find(x)]

n, m = map(int, input().split()) #要素の数
par = [-1] * n #
import numpy as np
path = []
par = np.array(par)
for i in range(m):
  a, b = map(int, input().split())
  path.append([a-1, b-1])
ans_l = [n*(n-1)//2]
for i in range(m-1, 0, -1):
  if same(path[i][0], path[i][1]):
    ans_l.append(ans_l[-1])
    unite(path[i][0], path[i][1])
  else:
    ans_l.append(ans_l[-1] - size(path[i][0])*size(path[i][1]))
    unite(path[i][0], path[i][1])
for i in range(m-1, -1, -1):
  print(ans_l[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def find(x):#xの親を見つける
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):#要素xとｙを併合させる
  x,y=find(x),find(y)#xとyの親の検索
  if x!=y:#親が異なる場合併合させる
    if x>y:
        x,y=y,x#小さい方をxとする. これにより要素の値が小さいものを優先して木の根とする. 
    par[x]+=par[y] #値を無向木の要素数の和にする.
    par[y]=x #枝側は根の位置を格納

def same(x, y):#要素xと要素yが同じ無向木に所属しているかを判定する
  return find(x) == find(y)#同じ値を持つか否か

def size(x):#要素xが所属する無向木の大きさを返す
  return-par[find(x)]

n, m = map(int, input().split()) #要素の数
par = [-1] * n #
path = []
for i in range(m):
  a, b = map(int, input().split())
  path.append([a-1, b-1])
ans_l = [n*(n-1)//2]
for i in range(m-1, 0, -1):
  if same(path[i][0], path[i][1]):
    ans_l.append(ans_l[-1])
    unite(path[i][0], path[i][1])
  else:
    ans_l.append(ans_l[-1] - size(path[i][0])*size(path[i][1]))
    unite(path[i][0], path[i][1])
for i in range(m-1, -1, -1):
  print(ans_l[i])
### BUGGY CODE ###


from collections import Counter

n = int(input())
s = [input() for i in range(n)]
c = Counter(s)
a = c.most_common()[0][1]
ans = []
for i in range(len(c)):
  if c.most_common()[i][1] == a:
    ans.append(c.most_common()[i][0])

ans.sort()
print(*ans,sep="\n")

### FIXED CODE ###

import collections
n = int(input())
s = [input() for _ in range(n)]
c = collections.Counter(s)
C = c.most_common()
most_count = C[0][1]
answer = []

for i in range(len(C)):
  if most_count == C[i][1]:
    answer.append(C[i][0])

answer.sort()
for i in answer:
    print(i)
### BUGGY CODE ###

def slv(A):

    count = 0

    for i in range(len(A)):
        for j in range(i + 1, len(A) + 1):
            # print(A[i:j], i, j)
            if sum(A[i:j]) == 0:
                count += 1
                # print(A[i:j], i, j)
    return count


def main():
    N = int(input())
    A = list(map(int, input().split()))
    # print(A)
    print(slv(A))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter


def slv(A):
    S = 0
    C = Counter()
    C[0] += 1
    for a in A:
        S += a
        C[S] += 1

    c = 0
    for v in C.values():
        if v > 1:
            c += (v * (v - 1)) // 2

    return c


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

    # import random
    # N = 2 * 100000
    # A = [random.randint(-1000000000, 1000000000) for _ in range(N)]

    print(slv(A))


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

import bisect

n, q = map(int, input().split())
s = input()
index = []
for i in range(n):
    if s[i:i + 2] == "AC":
        index.append(i)
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 2
    bl = bisect.bisect_left(index, l)
    br = bisect.bisect_left(index, r)
    if r in index:
        print(br - bl + 1)
    else:
        print(br - bl)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac = []
last = False
for i in range(n):
    if last and s[i] == "C":
        last = False
        ac.append(1)
    else:
        if s[i] == "A":
            last = True
        else:
            last = False
        ac.append(0)
ac_t = [0]
for i in range(n):
    ac_t.append(ac[i] + ac_t[i])
for i in range(q):
    l, r = map(int, input().split())
    print(ac_t[r] - ac_t[l])
### BUGGY CODE ###

from collections import deque
 
H, W = [int(x) for x in input().split()]

Ch,Cw = map(int,input().split())

Ch,Cw = Ch-1,Cw-1

Dh,Dw = map(int,input().split())

Dh,Dw = Dh-1,Dw-1

cell = [list(input()) for i in range(H)]

dp = [[-1]*W for _ in range(H)]

stack = deque()
stack.append([Ch,Cw])

dp[Ch][Cw] = 0

while len(stack) > 0:
    h,w = stack.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dy
        nw = w + dx
        if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
            if cell[nh][nw] == '.':
                dp[nh][nw] = dp[h][w]
                stack.append([nh,nw])
            else:
                for ddy in range(-2,3):
                    for ddx in range(-2,3):
                        if ddy==ddx==0:
                            continue
                        nnh = h + ddy
                        nnw = w + ddx
                        if 0 <= nnh < H and 0 <= nnw < W:
                            if cell[nnh][nnw] == '.' and (dp[nnh][nnw] == -1 or dp[nnh][nnw] > dp[h][w]+1):
                                dp[nnh][nnw] = dp[h][w] + 1
                                stack.append([nnh,nnw])
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)


### FIXED CODE ###

import copy

from collections import deque
 
H, W = [int(x) for x in input().split()]

Ch,Cw = map(int,input().split())

Ch,Cw = Ch-1,Cw-1

Dh,Dw = map(int,input().split())

Dh,Dw = Dh-1,Dw-1

cell = [list(input()) for i in range(H)]

dp = [[-1]*W for _ in range(H)]

copy_stack = []
copy_stack.append([Ch,Cw])

nstack = []

dp[Ch][Cw] = 0

def search(stack):
    while len(stack) > 0:
        h,w = stack.pop()
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
                if cell[nh][nw] == '.':
                    dp[nh][nw] = dp[h][w]
                    stack.append([nh,nw])
                    copy_stack.append([nh,nw])
                   
while True:
    if len(copy_stack):
        nstack = copy.copy(copy_stack)
    else:
        copy_stack = copy.copy(nstack)
    search(nstack)
    #print(dp)
    if dp[Dh][Dw] == -1:
        while len(copy_stack)>0:
            h,w = copy_stack.pop()
            for ddy in range(-2,3):
                for ddx in range(-2,3):
                    if ddy==ddx==0:
                        continue
                    nnh = h + ddy
                    nnw = w + ddx
                    if 0 <= nnh < H and 0 <= nnw < W:
                        if cell[nnh][nnw] == '.' and dp[nnh][nnw] == -1:
                            dp[nnh][nnw] = dp[h][w] + 1
                            nstack.append([nnh,nnw])
        if len(nstack) == 0:
            break
    else:
        break
                        
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)
### BUGGY CODE ###

from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input()
for i in range(Q):
    d=deque()
    v=points[i][0]-1
    d.append(v)
    while len(d)!=0:
        v=d.popleft()
        score[v]=score[v]+points[i][1]
        for j in dirtree[v]:
            d.append(j)
        #input()
print(*score,sep=" ")


### FIXED CODE ###

from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")
### BUGGY CODE ###

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)] #木構造を入れておく
long = [0] * (N+1) #Kから任意のノードまでの距離

for i in range(N-1):
  x, y, z = map(int, input().split())
  graph[x].append([y, z])
  graph[y].append([x, z])
  
Q, K = map(int, input().split())
x = [0] * Q
y = [0] * Q

for i in range(Q):
  x_i, y_i = map(int, input().split())
  x[i] = x_i
  y[i] = y_i
  
for i in range(1,N+1): #Kから任意のノードまでの距離を求める
  q = deque([K])
  while q:
    t = q.popleft()
    tlen = len(graph[t])
    for i in range(tlen):
      next_t = graph[t][i][0]
      if(long[next_t] > 0):
        continue
      q.append(next_t)
      long[next_t] = long[t] + graph[t][i][1]
        

for i in range(Q):
  print(long[x[i]] + long[y[i]])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
### BUGGY CODE ###

H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if abs(x+A[i][j+1]) not in L[i][j+1]:
                L[i][j+1][abs(x+A[i][j+1])]=1
            if abs(x-A[i][j+1]) not in L[i][j+1]:
                L[i][j+1][abs(x-A[i][j+1])]=1
            if abs(x+A[i+1][j]) not in L[i+1][j]:
                L[i+1][j][abs(x+A[i+1][j])]=1
            if abs(x-A[i+1][j]) not in L[i+1][j]:
                L[i+1][j][abs(x-A[i+1][j])]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
A=[]
A.append([0 for i in range(W+1)])
for i in range(H):
    a=[0]+list(map(int,input().split()))
    A.append(a)
B=[]
B.append([0 for i in range(W+1)])
for i in range(H):
    b=[0]+list(map(int,input().split()))
    B.append(b)
C=[[0 for i in range(W+1)]for j in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j]=abs(A[i][j]-B[i][j])
        
ST=1<<80*160+1

dp=[[0 for i in range(W+1)]for j in range(H+1)]
dp[0][1]=ST
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] |= (dp[i-1][j]<<C[i][j]) |(dp[i-1][j]>>C[i][j])
        dp[i][j] |= (dp[i][j-1]<<C[i][j]) |(dp[i][j-1]>>C[i][j])
#print(bin(dp[-1][-1]>>7))
ANS=list(bin(dp[-1][-1]>>80*160+1))[::-1]
#print(ANS)
for i in range(len(ANS)):
    if ANS[i]=="1":
        print(i)
        exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
sum = 0
for i in range(N):
    sum += i
print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
N = int(input())-1
M = 0
x = int(math.ceil((N)/2))
if N%2 == 0:
    M = x*(N+1)
else:
    M = (x-1)*(N+1)+x
print(M)
### BUGGY CODE ###

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

sm=1
sm_lst=[]
for i in range(n):
    sm*=a[i]
    if i>=k:
        sm//=a[i-k]
        if sm > sm_lst[i-1]:
            print("Yes")
        else:
            print("No")
    sm_lst.append(sm)


### FIXED CODE ###

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

for i in range(k,n):
        if a[i] > a[i-k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for _ in range(n)]
    for _ in range(m):
        s,t = map(int, ipt().split())
        way[s].append(t)

    cos = [0]*(n+1)
    cos[n] = 0 * n
    for i in range(n-1,0,-1):
        nm = 0
        sm = 0
        for j in way[i]:
            nm += 1
            sm += 1+cos[j]
        cos[i] = sm/nm

    gm = cos[1]
    for i in range(1,n-1):
        nm = 0
        ma = 0
        sm = 0
        for j in way[i]:
            nm += 1
            sm += 1+cos[j]
            if ma < 1+cos[j]:
                ma = 1+cos[j]
        if nm == 1:
            continue
        else:
            cos[i] = (sm-ma)/(nm-1)
        for j in range(i-1,0,-1):
            nm = 0
            sm = 0
            for k in way[j]:
                nm += 1
                sm += 1+cos[k]
            cos[j] = sm/nm
#        print(cos)
        if cos[1] < gm:
            gm = cos[1]

    print(gm)


    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    way = [[] for _ in range(n)]
    for _ in range(m):
        s,t = map(int, ipt().split())
        way[s].append(t)

    cos = [0]*(n+1)
    cos[n] = 0 * n
    for i in range(n-1,0,-1):
        nm = 0
        sm = 0
        for j in way[i]:
            nm += 1
            sm += 1+cos[j]
        cos[i] = sm/nm

    gm = cos[1]
    for i in range(1,n-1):
        nm = 0
        ma = 0
        sm = 0
        for j in way[i]:
            nm += 1
            sm += 1+cos[j]
            if ma < 1+cos[j]:
                ma = 1+cos[j]
        if nm == 1:
            continue
        else:
            cos[i] = (sm-ma)/(nm-1)
        for j in range(i-1,0,-1):
            nm = 0
            sm = 0
            for k in way[j]:
                nm += 1
                sm += 1+cos[k]
            cos[j] = sm/nm
#        print(cos)
        if cos[1] < gm:
            gm = cos[1]

    print(gm)


    return

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

from fractions import*
from functools import*
lcm=lambda x,y:x*y//gcd(x,y)
n,*a=map(int,open(0).read().split())
t=reduce(lcm,a)
c=0
M=10**9+7
for i in a:
    c+=t//i
    c%=M
print(c)

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###


N, M = map(int, input().split())
Vs = [ list(map(int, input().split())) for _ in range(M)]

d = dict()

for v in Vs:
    if v[0] in d:
        d[v[0]].append(v[1])
    else:
        d[v[0]] = [v[1]]

for k, v in d.items():
    s = sorted(v)
    d[k] = s

for v in Vs:
    ind = d[v[0]].index(v[1])
    print(str(v[0]).zfill(6) + str(ind+1).zfill(6))

### FIXED CODE ###


N, M = map(int, input().split())
Vs = [ list(map(int, input().split())) for _ in range(M)]

d = dict()

for v in Vs:
    if v[0] in d:
        d[v[0]].append(v[1])
    else:
        d[v[0]] = [v[1]]

for k, v in d.items():
    s = sorted(v)
    d[k] = s


ans = dict()
for k, v in d.items():
    for i in range(len(v)):
        a = v[i]
        ans[(str(k)+'-'+str(a))]  = i+1

for v in Vs:
    a = ans[(str(v[0])+'-'+str(v[1]))]
    print(str(v[0]).zfill(6) + str(a).zfill(6))
### BUGGY CODE ###

def gcd(a,b):
	if b ==0:
		return(a)
	else:
		return gcd(b,a%b)

k = int(input())
ans = 0
for i in range(1,k+1):
	for p in range(1,k+1):
		for q in range(1,k+1):
			ans+=gcd(q,gcd(i,p))

print(ans)

### FIXED CODE ###


from math import gcd
k = int(input())
ans = 0
for i in range(1,k+1):
	for p in range(1,k+1):
		for q in range(1,k+1):
			ans+=gcd(q,gcd(i,p))

print(ans)