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

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

def cmb(n, r, p):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = 1
    for i in range(n, n - r, -1):
        over = over * i % p
    under = 1
    for i in range(1, r + 1):
        under = under * i % p
    inv = pow(under, p - 2, p)
    return over * inv % p

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

minus = 0
plus = 0

d = defaultdict(int)
for i in range(N):
    d[i] = cmb(i, K-1, MOD)

for i, a in enu(A):
    mval = d[N-i-1]
    pval = d[i]
    if i<=K-2:
        pval = 0
    if N-K+1<=i:
        mval = 0
#    print(mval, pval)
    minus -= a*mval
    plus += a*pval


print((plus+minus)%MOD)



### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))


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

fact = [1]
for i in range(1, N+10):
    fact.append(fact[-1] * i % MOD)
def rev(x):
    return pow(x, MOD-2, MOD)
def cmb(i, k):
    if(i < k): return 0
    return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

minus = 0
plus = 0

for i, a in enu(A):
    mval = cmb(N-i-1, K-1)
    pval = cmb(i, K-1)
    if i<=K-2:
        pval = 0
    if N-K+1<=i:
        mval = 0
#    print(mval, pval)
    minus -= a*mval
    plus += a*pval

print((plus+minus)%MOD)
### BUGGY CODE ###

n=int(input())
a=[]
m=[]
b=[]
for i in range(n):
  a.append(input())
kaisu=1
for i in range(n):
  b.append(a.count(a[i]))
for i in range(n):
  if kaisu==b[i]:
    m.append(a[i])
  elif kaisu<b[i]:
    m=[a[i]]
    kaisu=b[i]
m=sorted(list(set(m)))
n=len(m)
for i in range(n):
  print(m[i])

### FIXED CODE ###

n=int(input())
s=[input() for i in range(n)]
s=sorted(s)
poll=[s[0]]
counta=[1]
kind=0
for i in range(1,n):
  if s[i]==s[i-1]:
    counta[kind]+=1
  else:
    kind+=1
    poll.append(s[i])
    counta.append(1)
m=max(counta)
for i in range(kind+1):
  if counta[i]==m:
    print(poll[i])
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = []
for i in range(Q):
        lr.append(list(map(int,input().split())))

for i in range(Q):
        cnt = 0
        l,r = lr[i][0],lr[i][1]
        x = S[l-1:r]
        x = x.replace('G','').replace('T','')
        for k in range(len(x)):
                if k - 1 >= 0:
                    if x[(k - 1):(k + 1)] == 'AC':
                            cnt += 1
        print(cnt)
                

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
cnt = [0] * (N + 1)
lrs = []
for i in range(Q):
        lrs.append(list(map(int,input().split())))

for i in range(N):
        cnt[i+1] = cnt[i] + (1 if S[i:i+2] == "AC" else 0)
for lr in lrs:
        print(cnt[lr[1] - 1] - cnt[lr[0] - 1])
### BUGGY CODE ###

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

### TESTCASE
test = ""
#test = \
"""
9 3
8 3
4 2
2 1
ans 4
"""

"""
5 2
4 4
2 3
ans 7
"""

"""
100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100
"""

"""
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN
        
h, n = map(int, input2().split())    
ab = [tuple(map(int, input2().split())) for _ in range(n)]

dp = [0] * (h + 1)

for i in range(1, h+1):
    kouho = 10**15
    for c in ab:     
        kouho = min(kouho, dp[max(i-c[0], 0)] + c[1])
    
    dp[i] = kouho
    #print(i, kouho)
        
print(dp[-1])
    
    








### FIXED CODE ###

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

"""

9 3
8 3
4 2
2 1
ans 4

7 2
4 4
2 3
ans 8

100 6
1 1
2 3
3 9
4 27
5 81
6 243
ans 100

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461
ans 139815
"""; test = """
"""
import builtins
test = list(reversed(test.strip().splitlines()))
input = test.pop if test else builtins.input


import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])


dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
    ### dp[i] = min(dp[max(i-c[0], 0)] + c[1] for c in ab) ###
print(dp[-1])
### BUGGY CODE ###

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

lst = []
for i in range(1, N+1):
    lst.append(A.index(str(i))+1)

print(*lst)

### FIXED CODE ###

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

l = []
for i, a in enumerate(A):
    l.append((a, i+1))
    
l.sort()

print(*[t[1] for t in l])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import Counter
S = input()
n = len(S)
mod = 2019
s = [0]*(n+1)
for i in range(n):
    s[i+1] = (s[i]+int(S[n-i-1])*10**i)%mod
c = Counter(s)
ans = 0
for x in c.values():
    ans += x-1
print(ans)

### FIXED CODE ###

from collections import Counter
S = input()
n = len(S)
mod = 2019
s = [0]*(n+1)
X = [1]*n
for i in range(n-1):
    X[i+1] = X[i]*10%mod
for i in range(n):
    s[i+1] = (s[i]+int(S[n-i-1])*X[i])%mod
c = Counter(s)
ans = 0
for x in c.values():
    ans += (x-1)*x//2
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
h = 1
t = set()
while h * h <= N:
  t.add(N // h)
  t.add(h)
  h += 1
t = sorted(t)
#print(t)
tt = []
for x in t:
  tt.append(N // x)

dp = [[0] * len(t) for _ in range(K + 1)]
dp[0][0] = 1
for i in range(K):
  for j in range(len(t)):
    k = bl(t, tt[j])
    dp[i + 1][k] += dp[i][j]
    dp[i + 1][k] %= mod
  #print(dp)
  for k in range(len(t) - 1, 0, -1):
    dp[i + 1][k - 1] += dp[i + 1][k]
    dp[i + 1][k - 1] %= mod
  for k in range(1, len(t)):
    rng = t[k] - t[k - 1]
    dp[i + 1][k] *= rng
    dp[i + 1][k] %= mod
  #print(dp)
res = 0
#print(dp)
for j in range(len(t)):
  res += dp[-1][j]
  res %= mod
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
h = 1
t = set()
while h * h <= N:
  t.add(N // h)
  t.add(h)
  h += 1
t = sorted(t)
#print(len(t))
tt = []
for x in t:
  tt.append(N // x)

dp = [[0] * len(t) for _ in range(K + 1)]
dp[0][0] = 1
for i in range(K):
  for j in range(len(t)):
    k = len(t) - j - 1
    dp[i + 1][k] += dp[i][j]
    dp[i + 1][k] %= mod
  #print(dp)
  for k in range(len(t) - 1, 0, -1):
    dp[i + 1][k - 1] += dp[i + 1][k]
    dp[i + 1][k - 1] %= mod
    rng = (t[k] - t[k - 1]) % mod
    dp[i + 1][k] *= rng
    dp[i + 1][k] %= mod

  #print(dp)
res = 0
#print(dp)
for j in range(len(t)):
  res += dp[-1][j]
  res %= mod
print(res)
### BUGGY CODE ###

N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            if k==i or k==j:continue
            if dist[i][k]+dist[j][k]==dist[i][j]:
                ans-=dist[i][j]
            elif dist[i][k]+dist[j][k]<dist[i][j]:
                ans=-1*float('inf')
if ans<0:ans=-1
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
for i in range(N):
    dist[i][i]=float('inf')
ans//=2
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(map(sum,zip(dist[i],dist[j])))
            if Min<dist[i][j]:
                return -1
            if Min==dist[i][j]:
                ans-=dist[i][j] 
    return ans
print(main(ans))
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append((i,j))
      lis[i][j]=0


while q:
  cur=q.popleft()
  i,j=cur[0],cur[1]

  if 0<=i+1<=h-1 and 0<=j<=w-1:
    if lis[i+1][j]==-1:
      lis[i+1][j]=lis[i][j]+1
      q.append((i+1,j))
  
  if 0<=i-1<=h-1 and 0<=j<=w-1:
    if lis[i-1][j]==-1:
      lis[i-1][j]=lis[i][j]+1
      q.append((i-1,j))

  
  if 0<=i<=h-1 and 0<=j+1<=w-1:
    if lis[i][j+1]==-1:
      lis[i][j+1]=lis[i][j]+1
      q.append((i,j+1))
      
  if 0<=i<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[i][j-1]==-1:
      lis[i][j-1]=lis[i][j]+1
      q.append((i,j-1))      
  
print(max(max(l) for l in lis))



### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append((i,j))
      lis[i][j]=0


while q:
  cur=q.popleft()
  i,j=cur[0],cur[1]

  if 0<=i+1<=h-1 and 0<=j<=w-1:
    if lis[i+1][j]==-1:
      lis[i+1][j]=lis[i][j]+1
      q.append((i+1,j))
  
  if 0<=i-1<=h-1 and 0<=j<=w-1:
    if lis[i-1][j]==-1:
      lis[i-1][j]=lis[i][j]+1
      q.append((i-1,j))

  
  if 0<=i<=h-1 and 0<=j+1<=w-1:
    if lis[i][j+1]==-1:
      lis[i][j+1]=lis[i][j]+1
      q.append((i,j+1))
      
  if 0<=i<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[i][j-1]==-1:
      lis[i][j-1]=lis[i][j]+1
      q.append((i,j-1))      
  
print(max(max(l) for l in lis))
### BUGGY CODE ###

from collections import defaultdict
import numpy as np

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

PYlist = []
PYmap = defaultdict(list)

for _ in range(M):
    P, Y = map(int, input().split())
    PYlist.append((P, Y))
    PYmap[P].append(Y)
for P in PYmap.keys():
    PYmap[P] = list(np.argsort(np.argsort(PYmap[P])) + 1)

for P, Y in PYlist:
    print(format(P, '06') + format(PYmap[P].pop(0), '06'))

### FIXED CODE ###

from collections import defaultdict

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

city = []

for i in range(M):
    P, Y = map(int, input().split())
    city.append([i, P, Y])
city.sort(key=lambda x: x[2])

count = defaultdict(lambda: 0)
for c in city:
    count[c[1]] += 1
    c.append(count[c[1]])
city.sort(key=lambda x: x[0])

for _, P, _, n in city:
    print(format(P, '06') + format(n, '06'))
### BUGGY CODE ###

N,W = map(int,input().split())
w = []
v = []
for i in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(N+1)]

for i in range(N):# 2 1 0
    for j in range(W+1):# 0 1 2 3 4 5 6 7 8
        """
        for k in dp:
            print(k)
        print(i,j)
        print("-------------------")
        """
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
"""
for k in dp:
    print(k)
print("-------------------")
"""
print(dp[N][W])

### FIXED CODE ###

n,W = map(int,input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])
### BUGGY CODE ###

K=int(input())

if K%2==0:
    print(-1)
    exit()


now=0
count=0
N=0
flag=False
while True:
    now+=(7*pow(10,count, K))%K
    now%=K
    #print(N)
    if not flag:
        N+=7*10**(count)
    if N>=K:
        flag=True
    #print(now, count)
    if now==0 and flag:
        print(count+1)
        exit()
    count+=1
    if count>=10**7:
        break


print(-1)

### FIXED CODE ###

K=int(input())

if K%2==0:
    print(-1)
    exit()


now=0
count=0
N=0
flag=False
while True:
    now+=(7*pow(10,count, K))%K
    now%=K
    #print(N)
    if not flag:
        N+=7*10**(count)
    if N>=K:
        flag=True
    #print(now, count)
    if now==0 and flag:
        print(count+1)
        exit()
    count+=1
    if count>10**6:
        break


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

N = int(input())
S = [input() for _ in range(N)]

count = dict()
for x in S:
    count[x] = count.get(x, 0) + 1

sorted_kv = list(sorted(count.items(), key=lambda x: (-x[1], x[0])))
max_val = sorted_kv[0][1]

res = []
for k, v in sorted_kv:
    if v == max_val:
        print(k)
    else:
        break


### FIXED CODE ###

N = int(input())

count = dict()
for _ in range(N):
    x = input()
    count[x] = count.get(x, 0) + 1

max_val = -float("infinity")
for k, v in sorted(count.items(), key=lambda x: (-x[1], x[0])):
    max_val = max(v, max_val)
    if v == max_val:
        print(k)
    else:
        break
### BUGGY CODE ###

def gcd(a, b):
    while b != 0 :
        t = a % b
        a = b
        b = t
    return a
        
sum = 0
N=int(input(""))
for a in range(1, N + 1):
    for b in range(1, N + 1):
        for c in range(1, N + 1):
            sum = sum + gcd(gcd(a, b), c)
print(sum)

  

### FIXED CODE ###

def gcd(a, b):
    while b != 0 :
        t = a % b
        a = b
        b = t
    return a
        
sum = 0
N=int(input(""))
for a in range(1, N + 1):
    for b in range(1, N + 1):
        x = gcd(a, b)
        if x == 1:
            sum = sum + N
        else:
            for c in range(1, N + 1):
                sum = sum + gcd(x, c)
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

k, q = map(int, input().split())
d = tuple(map(int, input().split()))


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)


### FIXED CODE ###

k, q = map(int, input().split())
d = tuple(map(int, input().split()))


def query(n, x, m):
    dd = tuple(di % m for di in d)
    ans = n - 1

    # a_j mod m = a_{j+ 1} mod m
    for i in range(k):
        if dd[i] == 0:
            ans -= ((n - 1) - (i + 1)) // k + 1

    a0 = a1 = x
    for i in range(k):
        a1 += (((n - 1) - (i + 1)) // k + 1) * dd[i]
    ans -= (a1 // m) - (a0 // m)

    return ans


for _ in range(q):
    n_i, x_i, m_i = map(int, input().split())
    ans_i = query(n_i, x_i, m_i)
    print(ans_i)
### BUGGY CODE ###

from collections import defaultdict as dd
d = dd(int)
N = int(input())
for i in [int(n) for n in input().split()]:
  d[i] = d[i]+1
times = int(input())
for i in range(times):
  a, b = [int(n) for n in input().split()]
  d[b], d[a] = d[b] + d[a], 0
  print(sum([ key*value for key, value in d.items() if value > 0]))
  

### FIXED CODE ###

from collections import defaultdict as dd
d = dd(int)
N = int(input())
for i in [int(n) for n in input().split()]:
  d[i] = d[i]+1
times = int(input())
summation = sum([ key*value for key, value in d.items() if value > 0])
for i in range(times):
  a, b = [int(n) for n in input().split()]
  summation = summation + (b-a)*d[a]
  d[b], d[a] = d[b] + d[a], 0
  print(summation)
### BUGGY CODE ###

n=int(input())
s=input()
from collections import Counter
c= Counter(s)
ans=0
vals=list(c.values())
for i in range(1,1<<len(c)):
    tmpans=1
    for j in range(len(c)):
        if ((i>>j) &1) == 1:
            tmpans*=vals[j]
    ans+=tmpans
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
s=input()
from collections import Counter
c= Counter(s)
ans=1
vals=list(c.values())
for i in range(len(c)):
    ans=ans*(1+vals[i])
print((ans-1)%(10**9+7))
### BUGGY CODE ###

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

L.sort(reverse=True)

ans = 0
for a in range(N):
    flgb = True
    for b in range(a+1,N):
        flgc = True
        for c in range(N-1,b,-1):
            if L[c]+L[a] <= L[b]:
                flgb = False
                break
            if L[a]+L[b] <= L[c]:
                flgc = False
                break
            if (L[a] < L[b] + L[c]) and (L[b] < L[a] + L[c]):
                ans += 1
        if not flgb: break
        if not flgc: break
    if not flgb: break
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
from bisect import bisect_left
for i in range(N):
    for j in range(i+1,N):
        t = bisect_left(L,L[i]+L[j])
        ans += max(0, t-(j+1))
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
count=0
queue=deque([[0,0,0]])
for i in range(h):
    for j in range(w):
        if field[i][j]=='.':
            count+=1
def bfs(x,y,k):
    if (not 0<=x<h) or (not 0<=y<w):
        return
    if field[x][y]=='#':
        return
    queue.append([x,y,k+1])
    
while True:
    if len(queue)==0:
        break
    x,y,k=queue.popleft()
#    print(queue)
#    print(field)
    if x==h-1 and y==w-1:
        print(count-k-1)
        sys.exit()
    
    field[x][y]='#'
    bfs(x+1,y,k)
    bfs(x-1,y,k)
    bfs(x,y-1,k)
    bfs(x,y+1,k)
print(-1)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
cost=[[float('inf')]*w for _ in range(h)]
cost[0][0]=1
queue=deque([[0,0]])
count=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='.':
            count+=1
def bfs():
    while queue:
        x,y=queue.popleft()
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=x+dx<h and 0<=y+dy<w:
                if field[x+dx][y+dy]=='.' and cost[x+dx][y+dy]==float('inf'):
                    cost[x+dx][y+dy]=cost[x][y]+1
                    queue.append([x+dx,y+dy])
bfs()
#print(cost)
if cost[-1][-1]<float('inf'):
    print(count-cost[-1][-1])
else:
    print(-1)
### BUGGY CODE ###

N=int(input())

count=0
for i in range(1,N+1):
    head=int(str(i)[0])
    hip=i%10
    jstart=head-hip
    if jstart<0:
        jstart+=10
    for j in range(jstart,N+1-i,10):
        if str(i+j)[0]==str(i)[-1]:
            count+=2
            if j==0:
                count-=1
            else:
            	pass
        else:
            j=(int(str(i+j)[0])+1)*10**(len(str(i+j))-1)+jstart

print(count)


### FIXED CODE ###

N = int(input())

c = [[0]*10 for _ in range(10)]

for k in range(1,N+1):
    c[int(str(k)[0])][int(str(k)[-1])]+=1

ans = 0

for k in range(81):
    i = k // 9 + 1
    j = k % 9 + 1
    ans += c[i][j] * c[j][i]

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

n = int(input())
A = [int(input()) for i in range(n)]


mm = max(A)+2
B=[0 for i in range(mm)]
for i in range(n):
    if A[i]<=mm:
        B[A[i]]+=1
        mm=A[i]
    else:
        t=A[i]
        while B[t]==0:
            t-=1
        B[t]-=1
        B[A[i]]+=1
        #print(B)
        if mm==t and B[t]==0:
            while B[mm]==0:
                mm+=1
print(sum(B))

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] >= A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    # print(Q[:10])

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

n = int(input())
nums = [int(input()) for i in range(n)]
ans = -10000000000

for i in range(1, n):
    temp_max = nums[i:n+1]
    temp_min = nums[0:i]
    ans = max(ans, max(temp_max) - min(temp_min))
print(ans)	

### FIXED CODE ###

N = int(input())
R0 = int(input())
R1 = int(input())
max_profit = R1 - R0
min_R = min(R0, R1)

for i in range(N-2):
    R = int(input())
    max_profit = max(max_profit, R - min_R)
    min_R = min(min_R, R)

print(max_profit)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N = ii()
    A = list(mi())

    A.sort()
    if A[0] == 1:
        print(1)
        exit()
    
    ini = A[0]
    while len(A) > 1:
        x = A[0]
        B = set([x])
        for a in A:
            b = a%x
            if b > 0:
                B.add(b)

        A = list(B)
        #print(A)

    if len(A) > 0:
        print(A[0])
    else:
        print(ini)
            

            
        



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N = ii()
    A = list(mi())

    A.sort()
    if A[0] == 1:
        print(1)
        exit()
    
    ini = A[0]
    while len(A) > 1:
        x = A[0]
        B = set([x])
        for a in A:
            b = a%x
            if b > 0:
                B.add(b)

        A = list(B)
        A.sort()

    if len(A) > 0:
        print(A[0])
    else:
        print(ini)
            

            
        



if __name__ == "__main__":
    main()