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

a,b=map(int,input().split())
z=[]
for i in range(min(a,b)):
    if a%(i+1)==0 and b%(i+1)==0:
        z+=[i+1]
print(max(z))

### FIXED CODE ###

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

a,b=list(map(int,input().split()))
print(gcd(a,b))
### BUGGY CODE ###

N = int(input())
s = [int(input()) for _ in range(N)]
ans = 0
for i in range(2**N):
    correct = []
    su = 0
    for j in range(N):
        if ((i >> j) & 1):
            su += s[j]
    if su % 10 == 0:
      su = 0
    ans = max(ans,su)
print(ans)
            


### FIXED CODE ###

N = int(input())
s = [int(input()) for _ in range(N)]
s.sort()
ans = sum(s)

if ans % 10 != 0:
  print(ans)
else:
  for i in range(N):
    if s[i] % 10 != 0:
      print(ans - s[i])
      exit()
  print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

INF = 10**19
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)
pos.sort()
neg.sort()
p, n = len(pos), len(neg)
if K <= p * n:
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = 0, 0
        while s < p:
            while t < n and pos[s] * neg[t] <= mid:
                t += 1
            cnt += t
            s += 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)
else:
    K -= p * n
    neg = neg[::-1]
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = p-1, 0
        while s >= 0:
            while t < s and pos[s] * pos[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        s, t = n-1, 0
        while s >= 0:
            while t < s and neg[s] * neg[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = 10**19
N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(a)
pos.sort()
neg.sort()
p, n = len(pos), len(neg)
if K <= p * n:
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = 0, 0
        while s < p:
            while t < n and pos[s] * neg[t] <= mid:
                t += 1
            cnt += t
            s += 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)
else:
    K -= p * n
    neg = neg[::-1]
    lb, ub = -INF, INF
    while ub - lb > 1:
        mid = (lb + ub) // 2
        cnt = 0

        s, t = p-1, 0
        while s >= 0:
            while t < s and pos[s] * pos[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        s, t = n-1, 0
        while s >= 0:
            while t < s and neg[s] * neg[t] <= mid:
                t += 1
            cnt += min(s, t)
            s -= 1

        if cnt < K:
            lb = mid
        else:
            ub = mid
    print(ub)
### BUGGY CODE ###

L, R = map(int, input().split())

if L - R + 1 >= 2019:
     print(0)
else:
    ans = float('Inf')
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
    print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

if R - L + 1 >= 2019:
    print(0)
else:
    res = 2018
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            res = min(res, (i * j) % 2019)
    print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

sum = sum(A)

for i in range(Q):
    B[i], C[i] = map(int, input().split())
    
    time = 0
    for k in range(N):
        if A[k] == B[i]:
            A[k] = C[i]
            time += 1
        
    sum += (C[i]-B[i])*time

    print(sum)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

num = [0]*100000

for i in range(N):
    num[A[i]-1] += 1

sum = sum(A)

for i in range(Q):
    B[i], C[i] = map(int, input().split())
    
    sum += (C[i]-B[i])*num[B[i]-1]
    num[C[i]-1] += num[B[i]-1] 
    num[B[i]-1] = 0

    print(sum)
### BUGGY CODE ###

n, m = map(int, input().rstrip().split())
h = list(map(int, input().rstrip().split()))
a_b = [list(map(int, input().rstrip().split())) for i in range(m)]
for i in range(m):
    a_b[i][0] = a_b[i][0] - 1
    a_b[i][1] = a_b[i][1] - 1
count = 0

for i in range(n):
    temp = set()
    for j in range(m):
        if a_b[j][0] == i:
            temp.add(a_b[j][1])
        if a_b[j][1] == i:
            temp.add(a_b[j][0])
    high = h[i]
    num = 0
    for k in temp:
        if high == h[k]:
            num += 1
        high = max(high, h[k])
    if (h[i] == high and num != len(temp)) or len(temp)==0:
        count += 1

print(count)

### FIXED CODE ###

n, m = map(int, input().rstrip().split())
h = list(map(int, input().rstrip().split()))
l = []
high = [0] * n
count = 0

for i in range(m):
    a, b = map(int, input().rstrip().split())
    l.append([a, b])

for i in l:
    if h[i[0]-1] < h[i[1]-1]:
        high[i[0]-1] += 1
    elif h[i[0]-1] == h[i[1]-1]:
        high[i[0]-1] += 1
        high[i[1]-1] += 1
    else:
        high[i[1]-1] += 1

for hi in high:
    if hi == 0:
        count += 1
print(count)
### BUGGY CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(str(input()))
orange = []
for i in apple:
    if i not in orange:
        orange.append(i)
    else:
        orange.remove(i)
print(len(orange))

### FIXED CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
apple = sorted(apple)
apple.append(0)
count = 0
ans = 1
for i in range(n):
    if apple[i] == apple[i + 1]:
        ans += 1
    else:
        if ans%2 == 0:
            ans = 1
        else:
            count += 1
print(count)
### BUGGY CODE ###

X = [int(e) for e in input().split()]
ans = 0
for i in range(0,X[0]+1):
    for k in range(0,X[0]+1):
        for j in range(0,X[0]+1):
            if(i + k + j)==X[1]:
                ans += 1
                break
print(ans)


### FIXED CODE ###

X = [int(e) for e in input().split()]
ans = 0
for i in range(0,X[0]+1):
    for k in range(0,X[0]+1):
        if(X[1] - (i+k))<=X[0] and X[1] - i - k >= 0:
            ans += 1
print(ans)
### BUGGY CODE ###

while 1:
    n = int(raw_input())
    if n==0: break
    s = {i*i % n for i in xrange(1, n)}
    c = (n-1)/2
    m = [0] * (c+1)
    for a in s:
        for b in s:
            if a==b: continue
            t = a-b
            if t<0: t += n
            if t > c: t = n - t
            m[t] += 1
    print "\n".join(map(str, m[1:]))

### FIXED CODE ###

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    if N == 1:
        return True
    *S, = set(i**2 % N for i in range(1, N))
    S.sort()
    L = len(S)
    C = [0]*N
    D = [0]*((N-1)//2)
    for i in range(L):
        a = S[i]
        for b in S[:i]:
            C[a - b] += 2
    for i in range(1, N):
        D[min(i, N-i)-1] += C[i]
    write("\n".join(map(str, D)))
    write("\n")
    return True
while solve():
    ...
### BUGGY CODE ###

n,k=map(int,input().split())
s=list(input())
s.reverse()
if k>=n:
    print(min(s)*n)
else:
    for i in range(min(k,5000)):
        t=list(reversed(s))
        u=t+s
        uu=[]
        for j in range(n+1):
            uu.append(u[j:j+n])
        uu.sort()
        s=uu[0]
    print("".join(s))


### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
import sys
input=sys.stdin.readline
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n):
    for j in range(i):
        for k in range(j):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j-i != k-j:
                ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    d = 1
    while i + 2*d < n:
        if s[i] != s[i+d] and s[i] != s[i+2*d] and s[i+d] != s[i+2*d]:
            ans -= 1
        d += 1
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if i >= j: break
        if S[i] == S[j]:
            dp[i][j] = min(1 + dp[i + 1][j + 1], j - i)
            if dp[i][j] > ans:
                ans = dp[i][j]
print(ans)


### FIXED CODE ###

N = int(input())
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if i >= j: break
        if S[i] == S[j]:
            dp[i][j] = min(1 + dp[i + 1][j + 1], j - i)
            if dp[i][j] > ans:
                ans = dp[i][j]
print(ans)
### BUGGY CODE ###

import numpy as np

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr

n = int(input())

buf = []
cnt = []

for i in range(n):
    buf2 = input()
    if buf2 not in buf:
        buf.append(buf2)
        cnt.append(0)
    cnt[buf.index(buf2)] += 1

aaa = max(cnt)
ans2 = np.array(buf)[np.array(cnt) == aaa]
ans2.sort()

for i in ans2:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### BUGGY CODE ###

import math
N = int(input())
def gcdtriple(a,b,c):
    return math.gcd(a, math.gcd(b,c))
ans = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            ans += gcdtriple(a,b,c)
print(ans)

### FIXED CODE ###

import math
N = int(input())
def gcdtriple(a,b,c):
    return math.gcd(a, math.gcd(b,c))
ans = 0
for a in range(1, N+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a == b and b == c:
                ans += gcdtriple(a,b,c)
            elif a == b or b == c or c == a:
                ans += gcdtriple(a,b,c) * 3
            else:
                ans += gcdtriple(a,b,c) * 6
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    left = 0
    right = N
    print(left,flush=True)
    ls = int(input())
    if ls == "Vacant":
        exit()
        
    while right-left > 1:
        mid = (right+left)//2
        print(mid,flush=True)
        nls = input()
        if get == "Vacant":
            exit()
        if nls == ls:
            if (mid-left)%2 == 0:
                left = mid
            else:
                right = mid
        else:
            if (mid-left)%2 == 1:
                left = mid
                ls = nls
            else:
                right = mid

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    left = 0
    right = N
    print(left,flush=True)
    ls = input()
    if ls == "Vacant":
        exit()
        
    while right-left > 1:
        mid = (right+left)//2
        print(mid,flush=True)
        nls = input()
        if nls == "Vacant":
            exit()
        if nls == ls:
            if (mid-left)%2 == 0:
                left = mid
            else:
                right = mid
        else:
            if (mid-left)%2 == 1:
                left = mid
                ls = nls
            else:
                right = mid

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

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

    INF = float('inf')

    dp = [INF for _ in range(N)]

    for i in range(N):
        if i == 0:
            dp[i] = 0
        else:
            for dist in range(1, min(K, i) + 1):
                c = dp[i - dist] + abs(H[i] - H[i - dist])
                if c < dp[i]:
                    dp[i] = c

    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = np.array(list(map(int, input().split())))

    INF = float('inf')

    dp = np.array([INF for _ in range(N)])
    dp[0] = 0

    for i in range(1, N):
        max_dist = min(K, i)
        dp[i] = np.min(dp[i - max_dist:i] + np.abs(H[i] - H[i - max_dist:i]))

    print(int(dp[-1]))


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

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
hrz = [[0] * w for _ in range(h)]
vrt = [[0] * w for _ in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w + 1):
        if j < w and s[i][j] == '.':
            if cnt == 0:
                start = j
            cnt += 1
        elif cnt > 0:
            for k in range(start, j):
                hrz[i][k] = cnt
            cnt = 0
for j in range(w):
    cnt = 0
    for i in range(h + 1):
        if i < h and s[i][j] == '.':
            if cnt == 0:
                start = i
            cnt += 1
        elif cnt > 0:
            for k in range(start, i):
                vrt[k][j] = cnt
            cnt = 0
ans = max(hrz[i][j] + vrt[i][j] - 1 for i in range(h) for j in range(w))
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
hrz = [[0] * w for _ in range(h)]
vrt = [[0] * w for _ in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w + 1):
        if j < w and s[i][j] == '.':
            if cnt == 0:
                start = j
            cnt += 1
        elif cnt > 0:
            for k in range(start, j):
                hrz[i][k] = cnt
            cnt = 0
for j in range(w):
    cnt = 0
    for i in range(h + 1):
        if i < h and s[i][j] == '.':
            if cnt == 0:
                start = i
            cnt += 1
        elif cnt > 0:
            for k in range(start, i):
                vrt[k][j] = cnt
            cnt = 0
ans = max(hrz[i][j] + vrt[i][j] - 1 for i in range(h) for j in range(w))
print(ans)
### BUGGY CODE ###

import numpy as np
import math

N , M = map(int, input().split())
A = list(map(int , input().split()))
np_list = np.array(A)
#print(A)
for _ in range(M):
    #print(np_list)
    max_index = np_list.argmax()
    #print(max_index)
    np_list[max_index] = np_list[max_index] / 2
A = list(map( lambda x : math.floor(x) , A ))
print(sum(np_list))

### FIXED CODE ###

import math
import heapq
N , M = map(int, input().split())
A = list(map(int , input().split()))
A = list(map( lambda x : x * (-1) , A ))
heapq.heapify(A)
for _ in range(M):
    tmp = heapq.heappop(A) * (-1) / 2
    heapq.heappush(A,tmp * (-1))
A = list(map( lambda x : x * (-1) , A ))
A = list(map( lambda x : math.floor(x) , A ))
print(sum(A))
### BUGGY CODE ###

N, M = map(int, input().split())
x = sorted([int(x) for x in input().split()])

diff = sorted([i - j for i, j in zip(x[1:], x[:-1])], reverse=True)
diff = diff[:N-1]

if N >= M:
    print(0)
elif N == 1:
    print(max(x)-min(x))
else:
    j = 0
    ans = 0
    for i in range(M-1):
        a = x[i+1] - x[i]
        if a in diff:
            if i - j >= 1:
                ans += x[i] - x[j]
            diff.remove(a)
            j = i+1
            if len(diff) == 0:
                ans += x[-1] - x[i+1]
                break
    print(ans)
    



### FIXED CODE ###

import sys

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

if N >= M:
    print(0)
    sys.exit()
diff = [0]*(M-1)
for i in range(M-1):
    diff[i] = x[i+1] - x[i]
diff.sort()
ans = sum(diff[:M-N])
print(ans)
### BUGGY CODE ###

N = int(input())
Ls = list(map(int, input().split()))
Ls.sort()
count = 0
for i in range(N-2):
    a = Ls[i]
    for k in range(i+1,N-1):
        ab = a + Ls[k]
        count += len(list(filter(lambda c: c<ab, Ls[k+1:N])))
print(count)

### FIXED CODE ###

import bisect
n = int(input())
lis = sorted(list(map(int,input().split())))
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        index = bisect.bisect_left(lis,lis[i]+lis[j])
        count += index-1-j
print(count)
### BUGGY CODE ###

import itertools
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff =[V[n] - C[n] for n in range(N)]
XY = 0

for v in itertools.permutations([0, 1] * N, N):
  xy = 0
  for n in range(N):
    xy += diff[n] * v[n]
    if xy > XY:
      XY = xy
print(XY)
    

### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff = [0]
for n in range(N):
  if V[n] - C[n] > 0:
    diff.append(V[n] - C[n])

print(sum(diff))
### BUGGY CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [(b[i], i) for i in range(N) if a[i] != b[i]]
h = []
push = lambda x,i: hpu(h, (-x,i))
for t in sb: push(t[0], t[1])
res = 0
while len(h):
  v, i = hpo(h)
  v = -v
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  push(b[i], i)
print(res)


### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9+7

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

"""
・既に強連結成分として確定している町の個数
・訪問済だけれど強連結成分には入っていない町の個数
に対する場合の数を持ってdp
"""

dp = np.zeros((N+1,N+1),np.int64)
dp[1,0] = 1

rng = np.arange(N+1,dtype=np.int64)

for _ in range(M):
    prev = dp
    dp = np.zeros_like(prev)
    # 強連結成分から出発する場合。
    dp[:,0] += prev[:,0] * rng
    dp[:,1] += prev[:,0] * rng[::-1]
    # 未確定部分から
    for m in range(1,N):
        # 強連結成分に戻る
        dp[m:,0] += prev[:-m,m] * rng[:-m]
        # 未確定部分のまま
        dp[:,m] += prev[:,m] * m
        # 未確定部分を広げる
        dp[:,m+1] += prev[:,m] * (N-m-rng)
    dp %= MOD

answer = dp[N,0]
print(answer)



### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9+7

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

"""
・合計の訪問済の町の個数
・訪問済だけれど強連結成分には入っていない町の個数
に対する場合の数を持ってdp
"""

dp = np.zeros((N+1,N+1),np.int64)
dp[1,0] = 1
for _ in range(M):
    prev = dp
    dp = np.zeros_like(prev)
    # 強連結成分にもどる
    dp[:,0] += (prev[:,:] * (np.arange(N+1)[:,None] - np.arange(N+1)[None,:])).sum(axis=1)
    # 未確定部分内で
    dp[:,:] += prev[:,:] * np.arange(N+1)[None,:]
    # 未確定部分の拡張
    dp[1:,1:]+= prev[:-1,:-1] * np.arange(N,0,-1)[:,None]
    dp %= MOD

answer = dp[N,0]
print(answer)
### BUGGY CODE ###

N,K=list(map(int,input().split()))
dp_list=[None]*N
h=list(map(int,input().split()))
dp_list[0]=0
for i in range(N):
    for j in range(1,K+1):
        j=i+j
        if j<N:
            if dp_list[j] is None:dp_list[j]=abs(h[j]-h[i])+dp_list[i]
            else:dp_list[j]=min(dp_list[j],abs(h[j]-h[i])+dp_list[i])
print(dp_list[-1])



### FIXED CODE ###

import numpy as np
N,K=list(map(int,input().split()))
dp_list=np.full(N,10**10,dtype=int)
h=list(map(int,input().split()))
h=np.array(h)
dp_list[0]=0
for i in range(1,N):
        dp_list[i:i+K] = np.fmin(dp_list[i:i+K], dp_list[i-1] + np.abs(h[i:i+K] - h[i-1]))
print(dp_list[-1])
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k < n and s[i] != s[k] and s[j] != s[k]:
            cnt += 1
print(s.count('R') * s.count('G') * s.count('B') - cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k < n and s[i] != s[k] and s[j] != s[k]:
            cnt += 1
print(s.count('R') * s.count('G') * s.count('B') - cnt)