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

from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math

sys.setrecursionlimit(10 ** 8)
# mem = {}

M = 10 ** 9 + 7


def f(rs, gs, bs):
    res = 0
    for ir in range(0, len(rs)):
        for ig in range(0, len(gs)):
            for ib in range(0, len(bs)):
                i = rs[ir]
                j = gs[ig]
                k = bs[ib]
                if i < j and j < k and (j - i) != k - j:
                    res += 1
    return res
    # ir,ig,ib=(0,0,0)
    # while True:
    #     i= rs[ir]
    #     j= gs[ig]
    #     k= bs[ib]
    #     if i<j and j<k and (j-i)!=k-j:
    #         res+=1
    #


def main():
    N = int(input())
    S = input()

    rs = []
    gs = []
    bs = []

    for i, c in enumerate(S):
        if c == 'R':
            rs.append(i)
        elif c == 'G':
            gs.append(i)
        else:
            bs.append(i)
    print(f(rs, gs, bs) + f(rs, bs, gs) + f(gs, rs, bs) + f(gs, bs, rs) + f(bs, rs, gs) + f(bs, gs, rs))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)
# mem = {}

M = 10 ** 9 + 7


def f(rs, gs, bs):
    res = 0
    lgs = len(gs)
    lbs = len(bs)
    for i in rs:
        j = bisect.bisect_left(gs, i)
        k = bisect.bisect_left(bs, i)
        res += (lgs - j) * (lbs - k)

        for jj in range(j, lgs):
            d = (gs[jj] - i)
            index = bisect.bisect_left(bs, i + 2 * d)
            if index != lbs:
                if bs[index] == i + 2 * d:
                    res -= 1

        for kk in range(k, lbs):
            d = (bs[kk] - i)
            index = bisect.bisect_left(gs, i + 2 * d)
            if index != lgs:
                if gs[index] == i + 2 * d:
                    res -= 1


        # for j in reversed(gs):
        #     if not (i < j):
        #         break
        #     for k in reversed(bs):
        #         if not (i < k):
        #             break
        #         if j < k:
        #             if (j - i) != k - j:
        #                 res += 1
        #         else:
        #             if (k - i) != j - k:
        #                 res += 1

    return res


def main():
    N = int(input())
    S = input()

    rs = []
    gs = []
    bs = []

    for i, c in enumerate(S):
        if c == 'R':
            rs.append(i)
        elif c == 'G':
            gs.append(i)
        else:
            bs.append(i)
    print(f(rs, gs, bs) + f(gs, rs, bs) + f(bs, rs, gs))


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

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    ab = 0  # ABの選び方
    count = 0

    for _s in s:
        if _s == "?":
            # ある?(== C)を末尾とするABCの選び方は
            # 「ABの選び方+?」
            count *= 3
            count += ab
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            ab += alpha[0] * (3**ques)
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            ques += 1
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            ab += alpha[0] * (3**ques)
            if ques > 0:
                ab += ques * 3 ** (ques-1)
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ques %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


# print(func("A??C") == 8)
# print(func("ABCBC") == 3)
# print(func("????C?????B??????A???????") == 979596887)
print(func(input()))


### FIXED CODE ###

def func(s):
    alpha = [0, 0, 0]
    ques = 0
    nowQues = 1
    ab = 0  # ABの選び方
    count = 0
    for _s in s:
        if _s == "?":
            count *= 3  # 既にabcとなっている場合の数
            count += ab  # 「? == c」とする場合
            ab *= 3
            # ある?(== B)を末尾とするABの選び方は「A+?」か「?+?」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            # ？の中からaを選ぶ場合
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            ques += 1
            if ques > 1:
                nowQues *= 3
        elif _s == "A":
            alpha[0] += 1
        elif _s == "B":
            # あるBを末尾とするABの選び方は「A + B」か「? + B」
            if ques > 0:
                ab += alpha[0] * nowQues*3  # (3 ** ques)
            else:
                ab += alpha[0]
            if ques > 0:
                ab += ques * nowQues  # (3 ** (ques - 1))
            alpha[1] += 1
        elif _s == "C":
            # あるCを末尾とするABCの選び方は「bSelect通り」
            count += ab
            alpha[2] += 1
        count %= 10 ** 9 + 7
        ab %= 10 ** 9 + 7
        nowQues %= 10 ** 9 + 7
        # print("{} -> alpha:{} ab:{} count:{}".format(_s, alpha, ab, count))
    return count % (10 ** 9 + 7)


"""
print(func("A??C") == 8)
print(func("ABCBC") == 3)
print(func("????C?????B??????A???????") == 979596887)
def listToString(_list, split=""):
    maped_list = map(str, _list)  # mapで要素すべてを文字列に
    mojiretu = split.join(maped_list)
    return mojiretu
print(func(listToString(["?" for _ in range(10 ** 5)])))
print("finish")
"""
print(func(input()))
### BUGGY CODE ###

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
goto=[[] for i in range(N+1)]
for i in range(M):
    goto[AB[i][0]].append(AB[i][1])
    goto[AB[i][1]].append(AB[i][0])
#print(goto)

from collections import deque
from sys import exit
AB=deque(AB)
rank=[[1]]
flag=1

while len(AB)>0:
    l=len(AB)
    rank.append([])
    for i in range(l):
        ab=AB.popleft()
        if ab[0] in rank[-2] and ab[1] not in rank[-2]:
            rank[-1].append(ab[1])
        elif ab[1] in rank[-2] and ab[0] not in rank[-2]:
            rank[-1].append(ab[0])
        elif ab[0] not in rank[-2] and ab[1] not in rank[-2]:
            AB.append(ab)
    if l==len(AB):
        print('No')
        exit()

#print(rank)
print('Yes')
rank2=[-1 for i in range(N+1)]
rank2[1]=0
for i in range(1,len(rank)):
    for j in range(len(rank[i])):
        rank2[rank[i][j]]=i

#print(rank2)

for i in range(2,N+1):
    s=set(goto[i])&set(rank[rank2[i]-1])
    print(list(s)[0])

### FIXED CODE ###

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
goto=[[] for i in range(N+1)]
for i in range(M):
    goto[AB[i][0]].append(AB[i][1])
    goto[AB[i][1]].append(AB[i][0])
#print(goto)

parent=[0 for i in range(N+1)]
done=[0 for i in range(N+1)]
done[1]=1

from collections import deque
q=deque([1])

while q:
    r=q.popleft()
    for t in goto[r]:
        if done[t]:
            continue
        parent[t]=r
        done[t]=1
        q.append(t)

#print(parent)

print('Yes')
for i in range(2,N+1):
    print(parent[i])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
A=[list(map(int,input().split())) for i in range(Q)]
X=[0]*(N+1)
for i in range(N-1):
  if S[i]=='A':
    if S[i+1]=='C':
      X[i+1]=1
for i in range(Q):
  a=A[i][0]
  b=A[i][1]
  print(sum(X[a:b]))

### FIXED CODE ###

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

X=[0]*(N)
cnt=0
for i in range(N-1): 
  if S[i]=='A' and S[i+1]=='C':
    cnt+=1
    X[i+1]=cnt
  else:
    X[i+1]=cnt
    
for i in range(Q):
  a=A[i][0]-1
  b=A[i][1]-1
  print(X[b]-X[a])
### BUGGY CODE ###

Q = int(input())
for i in range(Q):
    a = list(map(int,input().split()))
    a.sort()
    A = a[0]
    B = a[1]
    n = 0
    if A==B:
        n = 2*A-2
    elif B == A+1:
        n = 2*A-2
    else:
        j = 0
        while True:
            j+=1
            if j*j >= A*B:
                C = j-1
                break
        if C*(C+1)>=A*B:
            n = 2*C-2
        else:
            n = 2*C-1
    print(n)

### FIXED CODE ###

import math
Q = int(input())
for i in range(Q):
    a = list(map(int,input().split()))
    a.sort()
    A = a[0]
    B = a[1]
    n = 0
    if A==B:
        n = 2*A-2
    elif B == A+1:
        n = 2*A-2
    else:
        C = math.ceil(math.sqrt(A*B)-1)
        if C*(C+1)>=A*B:
            n = 2*C-2
        else:
            n = 2*C-1
    print(n)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
S = input()
remainder = ["" for _ in range(2019)]
for i in range(len(S)):
  s = int(S[len(S)-1-i:])
  remainder[s % 2019] += "1"
ans = 0
for i in range(2019):
  if i == 0:
    ans += len(remainder[i])
  else:
    # 累積和
    ans += len(list(itertools.combinations(remainder[i], 2)))
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
S = input()[::-1]
remainder = [0] * 2019

# 2つ選ぶ組み合わせにおいて余り0の場合は1つしか選ばなくて良いので
# 2つ目に0を選んだ場合として便宜的に設定
remainder[0] = 1

num = 0
d = 1
for s in S:
  num += int(s) * d
  remainder[num % 2019] += 1
  d *= 10
  
  # numが大きくなりすぎると計算量が膨大になってしまうのを防ぐ
  # num%2019を計算するので、先に%2019で計算しても結果は変わらない
  d %= 2019
ans = 0
for i in range(2019):
  ans += remainder[i] * (remainder[i]-1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
array = list(map(int,input().split()))
ans = []
for i in range(N-1):
  product = []
  for j in range(1,N-i):
    product.append(array[i]*array[i+j])
  ans.append(sum(product))
print( sum(ans)%(10**9+7) )
  

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
ans = 0
kuso = sum(array)
for i in range(N-1):
  kuso -= array[i]
  ans += array[i]*kuso  
print( ans%(10**9+7) )
### BUGGY CODE ###

N = int(input())
list_A = []

for i in range(N):
  list_A.append(input())

i = 0

while i< len(list_A):
  a = list_A[i]
  b = list_A.count(a)
  if(b > 1 and b % 2 == 0):
    for j in range(b):
      list_A.remove(a)
  elif(b > 1):
    for k in range(b- 1):
      list_A.remove(a)
  else:
    i+= 1

ans = len(list_A)

print(ans)

### FIXED CODE ###

N = int(input())
A = []
B = []
for i in range(N):
  A.append(int(input()))
  
A.sort()
B.append(1)

for i in range(1, N):
  if(A[i]!= A[i- 1]):
    B.append(1)
  else:
    B[-1]+= 1
  i+= 1
  
ans = list(filter(lambda x: x % 2 == 1, B))

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

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

mul=1
for i in range(K):
    mul*=A[i]

for i in range(K,N):
    ki=mul
    mul=(mul/A[i-K])*A[i]
    if mul>ki :
        print("Yes")
    else:
        print("No")






### FIXED CODE ###

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

text=""
for i in range(K,N):
    if A[i]>A[i-K] :
        text+="Yes\n"
    else:
       text+="No\n"
print("{}".format(text))
### BUGGY CODE ###

from collections import defaultdict
def solve():
  ans = 0
  mod = 10**9+7
  s = defaultdict(lambda: -1)
  t = defaultdict(lambda: -1)
  N, M = map(int, input().split())
  S = list(map(int, input().split()))
  T = list(map(int, input().split()))
  for i in range(N):
    s[S[i]] = i
  for j in range(M):
    t[T[j]] = j
  dp = [[0]*(M+1) for _ in range(N+1)]
  for j in range(M+1):
    dp[0][j] = 1
  for i in range(1,N+1):
    dp[i][0] = 1
  for i in range(1,N+1):
    for j in range(1,M+1):
      if S[i-1]==T[j-1]:
        dp[i][j] += dp[i-1][j]+dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
  ans = dp[-1][-1]%mod
  return ans
print(solve())

### FIXED CODE ###

from collections import defaultdict
def solve():
  ans = 0
  mod = 10**9+7
  s = defaultdict(lambda: -1)
  t = defaultdict(lambda: -1)
  N, M = map(int, input().split())
  S = list(map(int, input().split()))
  T = list(map(int, input().split()))
  dp = [[0]*(M+1) for _ in range(N+1)]
  for j in range(M+1):
    dp[0][j] = 1
  for i in range(1,N+1):
    dp[i][0] = 1
  for i in range(1,N+1):
    for j in range(1,M+1):
      if S[i-1]==T[j-1]:
        dp[i][j] += dp[i-1][j]+dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
      dp[i][j]%= mod
  ans = dp[-1][-1]%mod
  return ans
print(solve())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1
 
l = 6500
m = 0
 
M = [[[0] * l for i in range(w)] for j in range(h)]
N = [[0 for i in range(w)] for j in range(h)]
N[0][0] = C[0][0]
 
s = 0
Q = [[0, 0]]
 
M[0][0][C[0][0]] = 1
# M[0][0][m-C[0][0]] = 1
 
while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1
        V[i+1][j] -= 1
        # print(N[i+1][j], N[i][j] + C[i+1][j])
        N[i+1][j] = max(N[i+1][j], N[i][j] + C[i+1][j])
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 1
        V[i][j+1] -= 1
        N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1
 
# print(M[-1][-1])
 
ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
M = [[0] * w for i in range(h)]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

m = 80
M[0][0] = (1 << m + C[0][0]) | (1 << m - C[0][0])

for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        M[i+1][j] |= (M[i][j] << m + C[i+1][j]) | (M[i][j] << m - C[i+1][j])
    if j+1 < w:
        M[i][j+1] |= (M[i][j] << m + C[i][j+1]) | (M[i][j] << m - C[i][j+1])

        # N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
b = bin(M[-1][-1])
ans = float("inf")
for i in range(len(b)):
    if b[-1-i] == "1":
        ans = min(ans, abs(i - m*(h+w-1)))
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())
    
    l = np.zeros((n, n))
    for i in range(m):
        a, b, c =map(int, input().split())
        c = p-c
        if c == 0:
            c = 10**(-7.9)
        if l[a-1][b-1] == 0:
            l[a-1][b-1] = c
        else:
            l[a-1][b-1] = min(l[a-1][b-1], c)
    x = l[-1, 0]
    l[-1][0] = 10**(-7.9)
    n, labels = connected_components(l, connection="strong")
    l = l[labels == labels[0]][:, labels == labels[0]]
    l[-1, 0] = x
    
    try:
        print(max(0, int(bellman_ford(l)[0][-1])*(-1)))
    except:
        print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import bellman_ford, connected_components
input = sys.stdin.readline


def main():
    n, m, p = map(int, input().split())
    
    l = np.zeros((n, n))
    for i in range(m):
        a, b, c =map(int, input().split())
        c = p-c
        if c == 0:
            c = 10**(-7.9)
        if l[a-1][b-1] == 0:
            l[a-1][b-1] = c
        else:
            l[a-1][b-1] = min(l[a-1][b-1], c)
    x = l[-1, 0]
    l[-1][0] = 10**(-7.9)
    n, labels = connected_components(l, connection="strong")
    l = l[labels == labels[0]][:, labels == labels[0]]
    l[-1, 0] = x
    
    try:
        print(max(0, int(round(bellman_ford(l, indices=0)[-1]))*(-1)))
    except:
        print(-1)


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

import sys

def main():
    N,*S = map(int, open(0).read().split())
    S = sorted(S)

    g = [S.pop(-1)]

    for _ in range(N):
        g.sort(reverse=True)
        c = []
        for p in g:
            for si, s in enumerate(S[::-1]):
                if p > s:
                    c.append(s)
                    S.pop(-(si+1))
                    break
            else:
                print('No')
                sys.exit()
        g.extend(c)
    print('Yes')

if __name__=='__main__':
    main()

### FIXED CODE ###

## 他の方と処理内容がほぼ同じなのに何でTLEになるか分からないので、他の方のコードでテスト
N = int(input())
a = list(map(int,input().split(' ')))
a.sort()
    

fathers = [a.pop()]
for _ in range(N):
    sons = list()
    b = list()
    
    for father in fathers:
        while a:
            x = a.pop()
            if father > x:
                sons.append(x)
                break
            else:
                b.append(x)
                
    a = a + b[::-1]
    fathers.extend(sons)
    fathers.sort(reverse = True)
    
    
    
if len(fathers) == 2**N:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  for j in range(i+1, n):
    if abs(i- j) == a[i] + a[j]:
      ans += 1
    
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l = [i + a[i] for i in range(n)]
r = [i - a[i] for i in range(n)]
countl = Counter(l)
countr = Counter(r)
ans = sum([countl[i]*countr[i] for i in countl.keys()])
print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    ans = []
    for i in range(N):
        a, b = map(int, input().split())
        for i in range(b):
            ans.append(a)
    sort_ans = sorted(ans)
    print(sort_ans[K-1])
    
main()

    

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    ans = [0] * (10 ** 5 + 1) 
    for i in range(N):
        a, b = map(int, input().split())
        ans[a] += b
    for i in range(10 ** 5 + 1):
        if K <= ans[i]:
            print(i)
            exit()
        else:
            K -= ans[i]
    
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [0] * n

for i in range(1, n):
    min_cost = 1e19
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            min_cost = min(cost, min_cost)
    dp[i] = min_cost

print(dp[n - 1])


### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
    costs = []
    for j in range(1, k + 1):
        if i - j >= 0:
            cost = dp[i - j] + abs(hs[i] - hs[i - j])
            costs.append(cost)
    dp[i] = min(costs)

print(dp[n - 1])
### BUGGY CODE ###

import sys

N=int(input())
A=list(map(int,input().split()))
for i in range(N):
  for j in range(N):
    if(i!=j and A[i]==A[j]):
      print("NO")
      sys.exit()
print("YES")

### FIXED CODE ###

import sys

N=int(input())
A=list(map(int,input().split()))
A.sort()
for i in range(N-1):
  if(A[i]==A[i+1]):
    print("NO")
    sys.exit()
print("YES")
### BUGGY CODE ###

N=int(input())
count=0
for i in range(N):
    n=int(input())
    s=2
    for j in range(n):
        if (n==2):
            count+=1
            break
        tmp=n%s
        if (tmp!=0):
            s+=1
            if (s==n):
                count+=1
                break
        else:
            break
print(count)

### FIXED CODE ###

import math
def prime(n):
    if (n==2):
        return True
    if(n<2 or n%2==0):
        return False
    i=3
    while(i<=math.sqrt(n)):
        if (n%i==0):
            return False
        i=i+2
    return True

N=int(input())
count=0
for i in range(N):
    n=int(input())
    if(prime(n)):
        count+=1
print(count)
### BUGGY CODE ###

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

ans = 1
INF = 1000000000000000000

for a in A:
    ans *= a
    
if ans > INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
INF = 1000000000000000000

if 0 in A:
    print(0)
    exit()

for a in A:
    ans *= a
    if ans > INF:
        print(-1)
        exit()

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

import fractions
 
k = int(input())
ans = 0
 
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = fractions.gcd(a, b)
        for c in range(1, k+1):
            ans += fractions.gcd(tmp, c)
 
print(ans)

### FIXED CODE ###

import math
 
k = int(input())
ans = 0
 
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = math.gcd(a,b)
        for c in range(1, k+1):
            ans += math.gcd(tmp, c)
 
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
for i in range(len(a)):
    for j in range(i, len(a)):
        if i != j:
          t += a[i]*a[j]

ans = t%(10**9+7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
r = 0
mod = 10**9+7
for i in range(n-1, 0, -1):
    r += a[i]
    t += a[i-1]*r
print(t%mod)
### BUGGY CODE ###

from sys import stdin
N,K=map(int,input().split())
h=[int(i) for i in stdin.readline().split()][:N]
dp=[float('inf')]*N
dp[0]=0
for i in range(max(N,N-K+1)):
    for j in range(i+1,i+K+1):
        if j<N:
            dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]))
    #print(dp)
print(dp[-1])

### FIXED CODE ###

from sys import stdin
N,K=map(int,stdin.readline().split())
h=[int(i) for i in stdin.readline().split()][:N]
dp=[float('inf') for i in range(N)]
dp[0]=0
for i in range(N):
    for j in range(i+1,i+K+1):
        if j<N:
            dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]))
    #print(dp)
print(dp[-1])
### BUGGY CODE ###

a = int(input())

s = input().split()
d = len(s)

for i in range(d-1):
  for f in range(i+1, d):
    if s[i] == s[f]:
      print("NO")
      break
  else:
    continue
  break
else:
  print("YES")

### FIXED CODE ###

a = int(input())

s = input().split()

e = set(s)
if len(s) == len(e):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

N,P = map(int,input().split())
S = input()

ans = 0
if P == 2 or P == 5:
  for i in range(N):
    if int(S[i])%P == 0:
      ans += i+1
else:
  r = [0] * (N+1)
  for i in range(N):
    r[N-1-i] = int(S[N-1-i:])%P
  # for i in range(N):
  #   for j in range(i,N):
  #     if (r[i]-r[j+1])%P == 0:
  #       ans += 1
  d = {}
  for x in r:
    if x in d:
      d[x] += 1
    else:
      d[x] = 1
  for k,v in d.items():
    ans += v*(v-1)//2
  
print(ans)      

### FIXED CODE ###

def main():
  N,P = map(int,input().split())
  S = input()

  ans = 0
  if P == 2 or P == 5:
    for i in range(N):
      if int(S[i])%P == 0:
        ans += i+1
  else:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    r = 0
    for i in range(N):
      r = (r+int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

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

a, b = map(int, input().split())
c = 1
for i in range(a, b+1):
    c *= i
if c>0:
    print("Positive")
elif c<0:
    print("Negative")
else:
    print("Zero")

### FIXED CODE ###

a, b = map(int, input().split())
if a>0 and b>0:
    print("Positive")
elif a==0 or b==0:
    print("Zero")
elif (a>0 and b<0) or (a<0 and b>0):
    print("Zero")
elif ((a+b)+1)%2==0:
    print("Positive")
else:
    print("Negative")