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

def main():
    from builtins import pow

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

    fac = [0] * N
    fac[0] = 1
    for i in range(N - 1):
        fac[i + 1] = fac[i] * (i + 1) % 998244353

    def mcomb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    result *= M
    result %= 998244353
    print(result)


main()


### FIXED CODE ###

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

result = 0
n = 1
k = 1
for i in range(K + 1):
    result += n * pow(k, 998244353 - 2, 998244353) * pow(M - 1, N - 1 - i, 998244353)
    result %= 998244353
    n *= N - 1 - i
    n %= 998244353
    k *= i + 1
    k %= 998244353
result *= M
result %= 998244353
print(result)
### BUGGY CODE ###

line = int(input())
nums = []
for n in range(line):
    nums.append(int(input()))

res = nums[1] - nums[0]
for i in range(line):
    for j in range(i+1, line):
        dif = nums[j] - nums[i]
        res = dif if dif > res else res

print(res)

### FIXED CODE ###

line = int(input())
nums = []
for n in range(line):
    nums.append(int(input()))

# res = nums[1] - nums[0]
# for i in range(line):
#     for j in range(i+1, line):
#         dif = nums[j] - nums[i]
#         res = dif if dif > res else res
maxd = nums[1] - nums[0]
minv = nums[0]

for j in range(1, line):
    maxd = max(maxd, nums[j] - minv)
    minv = min(minv, nums[j])


print(maxd)
### BUGGY CODE ###

import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
import numpy as np

def main():
    n, m = MII()
    a_lst = np.array(sorted(MII()))
    for i in range(m):
        b, c = MII()
        idx = np.searchsorted(a_lst, c, side='left')
        if idx <= b:
            a_lst[:idx] = c
        else:
            a_lst[:b] = c
        a_lst.sort()
    print(np.sum(a_lst))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from heapq import heapify, heappush, heappop

def main():
    n, m = MII()
    a_lst = MII()
    a_lst.sort()
    bc = []
    for i in range(m):
        b, c= MII()
        bc.append((b,c))
    bc.sort(key=lambda x: x[1], reverse=True)
    index = 0
    cnt = 0
    for i in range(n):
        if a_lst[i] > bc[index][1]: break
        a_lst[i] = bc[index][1]
        cnt += 1
        if cnt == bc[index][0]:
            cnt = 0
            index += 1
            if index == m:
                break
    print(sum(a_lst))

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

import numpy as np

iN ,iX  = [int(x) for x in input().split()]
aX = [int(x) for x in input().split()]

aCum = [0]*(iN)
aCum[0] = aX[0]
for i in range(1,iN):
    aCum[i]=aCum[i-1]+aX[i]

aCum = np.array(aCum)

def fCeil(iT,iR):
    return -1 * iT // iR * -1

def fCalcCost(iN,iX,aCum,iK):
    iCost = 5 * aCum[-1]
    for i in range(2,fCeil(iN,iK) ):
        iCost += 2 * aCum[-1 * i * iK -1]
    iCost += (iK +iN)*iX
    return iCost

iTotalCost = fCalcCost(iN,iX,aCum,1)
for iK in range(2,fCeil(iN,2) + 1):
    iTotalCost = min(iTotalCost,fCalcCost(iN,iX,aCum,iK))
print(iTotalCost)


### FIXED CODE ###


iN ,iX  = [int(x) for x in input().split()]
aX = [int(x) for x in input().split()]

#人のをみてようやく仕組みがわかったがこれで通るんだろうか

aCum = [0]*(iN)
aCum[0] = aX[0]
for i in range(1,iN):
    aCum[i]=aCum[i-1]+aX[i]

def fCalcCost(iN,iX,aCum,iK):
    iCost = 5 * aCum[-1]
    i = 2
    while  i*iK < iN  :
        iCost += 2 * aCum[-1 * i * iK -1]
        i += 1
    iCost += (iK +iN)*iX
    return iCost

iTotalCost = fCalcCost(iN,iX,aCum,1)
for iK in range(2,iN//2 + 2):
    iTotalCost = min(iTotalCost,fCalcCost(iN,iX,aCum,iK))
print(iTotalCost)
### BUGGY CODE ###

from collections import Counter

N = int(input())
S = []
for _ in range(N):
    s = input()
    S.append(Counter(s))

ans = 0

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



### FIXED CODE ###

from collections import Counter

N = int(input())
dic = {}

for _ in range(N):
    s = sorted(input())
    s = str(s)
    if s in dic.keys():
        dic[s] += 1
    else:
        dic[s] = 1

print(sum(d * (d-1) // 2 for d in dic.values() if d > 1))
### BUGGY CODE ###

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

p = len(format(max(A), 'b'))
digit = '0' + str(p) + 'b'

r = [0] * p
for i in range(N):
  tmp = format(A[i], digit)
  #print(tmp)
  for j in range(p):
    r[j] += int(tmp[j])

#print(r)
s = 0
for j in range(p):
  s += r[j] * (N - r[j]) * (2 ** (p-1-j))

print(s % (10**9 + 7))

### FIXED CODE ###

import numpy as np 
N = int(input())
A = np.fromstring(input(), dtype = np.int64, sep = ' ')

res = 0
for bit in range(60):
  c = int((A & 1).sum())
  res += c * (N - c) * (1 << bit)
  A >>= 1

print(res % 1000000007)
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
L, R = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]
ans = 3000

for i in range(L,R+1):
        for j in range(L,R+1):
            if i<j:
                ans=min(ans,(i*j)%2019)
                
print(ans)



### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
def input(): return sys.stdin.readline().strip()
def gcd(x, y): return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y): return (x * y) // gcd(x, y)
MOD = 10 **9 + 7

# N = int(input())
# S = input()
L, R = map(int, input().split())
# 横
# L = [int(x) for x in input().split()]
# 縦
# A = [int(input()) for _ in range(N)]
# 多次元
# L = [[int(x) for x in input().split()] for _ in range(N)]
ans = 3000

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

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
i = 1
k = 0
di = []
while True:
    i = ls[i-1]
    if i in di:
        print(-1)
        sys.exit()
    di.append(i)
    k += 1
    if i == 2:
        break
print(k)

### FIXED CODE ###

import sys
n = int(input())
ls = [int(input()) for _ in range(n)]
if 2 not in ls:
    print(-1)
    sys.exit()
i = 1
k = 0
for j in range(n):
    i = ls[i-1]
    k += 1
    if i == 2:
        print(k)
        sys.exit()
print(-1)
### BUGGY CODE ###

def main():
    from collections import namedtuple
    import sys
    input = sys.stdin.readline

    Param = namedtuple('Param', 'coef const')

    inf = 1 << 30
    L = 30

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

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append(Param(coef=a, const=b))

    ps.sort(key=lambda p: p.coef / (p.const + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for p in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (p.coef + 1) + p.const
            )
            # dp[visited] + 1 + (dp[visited] + 1) * p.coef + p.const

    def accumulate(a):
        s = 0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = -1
    cur = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: continue  # le->lt
        while cur >= 0 and acc[cur] > rest:  # bisect_right->しゃくとり
            cur -= 1
        cnt = cur + 1
        ans = max(ans, visited + cnt)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/hitachi2020/submissions/10704509

def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

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

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  # namedtupleやめた,coef,const

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = {0}
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  # le->lt,continue->break,restは狭義単調減少
        while cnt > 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        ans.add(visited + cnt)
    print(max(ans))


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

N=int(input())
A=map(int,input().split())
Q=int(input())
numbers=[]
for _ in range(Q):
    B,C=map(int,input().split())
    numbers.append([B,C])
answers=[0 for _ in range(100001)]
for a in A:
    answers[a]+=a
for number in numbers:
    suuji=answers[number[0]]//number[0]
    answers[number[0]]=0
    answers[number[1]]+=suuji*number[1]
    print(sum(answers))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=map(int,input().split())
Q=int(input())
numbers=[]
for _ in range(Q):
    B,C=map(int,input().split())
    numbers.append([B,C])
answers=[0 for _ in range(100001)]
for a in A:
    answers[a]+=a
whole=sum(answers)
for number in numbers:
    suuji=answers[number[0]]//number[0]
    answers[number[0]]=0
    answers[number[1]]+=suuji*number[1]
    whole+=(number[1]-number[0])*suuji
    print(whole)
### BUGGY CODE ###

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

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

a = b = 0
visited = [0 for i in range(N)]
stack = [0]
while stack:
  fr = stack.pop()
  if not visited[fr]:
    visited[fr] = 1
    a += 1
  for to in es[fr]:
    if visited[to]: continue
    stack.append(to)

stack = [1]
while stack:
  fr = stack.pop()
  if not visited[fr]:
    visited[fr] = 1
    b += 1
  for to in es[fr]:
    if visited[to]: continue
    stack.append(to)

if a > b: a,b = b,a
unused = N-a-b
b += unused

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(lambda x:int(x)-1,input().split())
  es[a].append(b)
  es[b].append(a)

a = b = 1
visited = [1,1] + [0]*(N-2)
q = deque([0])
while q:
  fr = q.popleft()
  for to in es[fr]:
    if visited[to]: continue
    q.append(to)
    visited[to] = 1
    a += 1

q = deque([1])
while q:
  fr = q.popleft()
  for to in es[fr]:
    if visited[to]: continue
    q.append(to)
    visited[to] = 1
    b += 1

if a > b: a,b = b,a
unused = N-a-b
b += unused

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)
### BUGGY CODE ###

import numpy as np
def solve(R,C,K,item):
  dp = np.zeros((C+1,5), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,5), dtype=np.int64)
    #上からアイテムを取らずに移動
    new_dp[:,0] = dp[:,-1]
    #上からアイテムを取って移動
    new_dp[1:,1] = np.maximum(new_dp[1:,1],dp[1:,-1]+item[i-1])
    for j in range(1,C+1):
      #横からアイテムを取らずに移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #横からアイテムを取って移動
      for k in range(1,4):
        new_dp[j,k] = max(new_dp[j,k],new_dp[j-1,k-1]+item[i-1,j-1])
    for k in range(4):
      new_dp[:,-1] = np.maximum(new_dp[:,-1],new_dp[:,k])
    dp = new_dp
  ans = dp[-1,-1]
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))


### FIXED CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())
### BUGGY CODE ###

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

box = []
for i in range(N):
    a = abs(A[i-1]-A[i])
    if a>K/2:
        a = K - a
    box.append(a)
box.extend(box)
dis = []
for i in range(N):
    d = sum(box[i:i+N-1])
    dis.append(d)

print(min(dis))

### FIXED CODE ###

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

box = []
for i in range(N):
    d = abs(A[i-1]-A[i])
    if d>K/2:
        d = K - d
    box.append(d)
print(K-max(box))
### BUGGY CODE ###

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

def make_charcount(word):
    charcount = {}
    for c in word:
        if c not in charcount:
            charcount[c] = 1
        else:
            charcount[c] += 1
    return charcount

charcount_list = [make_charcount(word) for word in word_list]

result = 0
while(len(charcount_list)):
    charcount = charcount_list.pop()
    result += len([1 for c in charcount_list if charcount == c])

print(result)

### FIXED CODE ###

n = int(input())

result = 0
word_list = {}

for i in range(n):
    input_word = "".join(sorted(input()))
    flag = 1
    if input_word in word_list:
        word_list[input_word] += 1
        result += word_list[input_word]
        flag = 0
    else:
        word_list[input_word] = 0

print(result)
### BUGGY CODE ###

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


### FIXED CODE ###

x = int(raw_input())
a = 1L
for i in range(1, x+1):
 a = a * i
 a = a % 1000000007
print(a)
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(K):
  if A >= 1:
    A -= 1
  elif A < 1 and B >= 1:
    B -= 1
  else:
    pass
print(A, B)

### FIXED CODE ###

a, b, k = map(int, input().split())
d = max(0, k-a)
ans_a = max(0, a-k)
ans_b = max(0, b-d)
print(ans_a, ans_b)
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def tleft(fn, lo, hi):
    """
    fn の結果が最も小さくなるインデックスを三分探索する
    :param callable fn:
    :param int lo: 最小のインデックス
    :param int hi: 最大のインデックス + 1
    :return: lo <= ret < hi
    """
    left = lo
    right = hi
    while abs(right - left) >= 3:
        r1 = (left * 2 + right) // 3
        r2 = (left + right * 2) // 3
        if fn(r1) <= fn(r2):
            right = r2
        else:
            left = r1
    if left + 1 >= hi or fn(left) <= fn(left + 1):
        return left
    if left + 2 >= hi or fn(left + 1) <= fn(left + 2):
        return left + 1
    return left + 2


def cost(n):
    return np.abs(A - (np.arange(N) + n)).sum()


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

i = tleft(cost, int(-1e10), int(1e10))
ans = int(cost(i))
print(ans)


### FIXED CODE ###

import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)
D = A - np.arange(N)
print(int(np.abs(D - np.median(D)).sum()))
### BUGGY CODE ###

from bisect import bisect_left
from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# x以上のものがK個あるならOK
def f(x):
    cnt = 0
    for i in A:
        for j in B:
            for k in C:
                if i+j+k<x:break
                cnt += 1
                if cnt>=K:
                    return True
    return False

def get_boarder():
    l, r = 0, A[0]+B[0]+C[0]
    while r-l>1:
        m = (l+r)//2
        if f(m):
            l = m
        else:
            r = m
    return l

s = []
for i in B:
    for j in C:
        s.append(i+j)
s.sort()
A.sort()
boarder = get_boarder()
q = []

for i in A:
    if boarder-i<0:continue
    pos = bisect_left(s, boarder-i)
    for j in s[pos:]:
        heappush(q, -(i+j))

for _ in range(K):
    print(-heappop(q))

### FIXED CODE ###

from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

# x以上のものがK個あるならOK
def f(x):
    cnt = 0
    for i in A:
        for j in B:
            for k in C:
                if i+j+k<x:break
                cnt += 1
                if cnt>=K:
                    return True
    return False

def get_boarder():
    l, r = 0, A[0]+B[0]+C[0]
    while r-l>1:
        m = (l+r)//2
        if f(m):
            l = m
        else:
            r = m
    return l

boarder = get_boarder()
q = []
for i in A:
    for j in B:
        for k in C:
            if i+j+k<boarder:break
            heappush(q, -(i+j+k))

for _ in range(K):
    print(-heappop(q))
### BUGGY CODE ###

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for j in range(n):
        if i - a[j] < 0:
            break
        if dp[i-a[j]] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")

### FIXED CODE ###

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for a in A:
        if i - a < 0:
            break
        if dp[i-a] == 0:
            dp[i] = 1

if dp[k] == 1:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())

import queue
todo = queue.Queue()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.put((x, y))
            seen[y][x] = True


seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
last = 0
while not todo.empty():
    x, y = todo.get()
    #print(x, y)
    for i in range(4):
        if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
            if seen[y + dy[i]][x + dx[i]] == False:
                route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                last = route[y + dy[i]][x + dx[i]]
                seen[y + dy[i]][x + dx[i]] = True
                todo.put((x + dx[i], y + dy[i]))

#print(seen)
#print(route)
print(last)
# M = 0
# for y in range(W):
#     for x in range(H):
#         M = max(M, route[y][x])
# print(M)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

#黒いタイルの位置情報を確認
for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

#白いタイルが無くなるまで、黒いタイルを増やす
while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

from collections import deque
def bfs(start):
    global count
    d = [float('inf') for i in range(N)]
    d[start] = 0
    que = deque()
    que.append(start)
    alr = [start]
    while que:
        q = que.popleft()
        for i in path[q]:
            if i not in alr:
                que.append(i)
                alr.append(i)
                d[i] = min(d[i],d[q]+1)
    for i in range(start+1,N):
        count[d[i]-1] += 1

N,X,Y = map(int,input().split())
path = [[] for i in range(N)]
path[0] = [1]
path[N-1] = [N-2]
for i in range(1,N-1):
    path[i] = [i-1,i+1]
path[X-1].append(Y-1)
path[Y-1].append(X-1)

count = [0 for i in range(N-1)]
for i in range(N-1):
    bfs(i)
for i in range(N-1):
    print(count[i])

### FIXED CODE ###

N,X,Y = map(int,input().split())
ans = [0 for i in range(N-1)]
for i in range(1,N):
    for j in range(i+1,N+1):
        mina = min(j-i, abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(X-j))
        ans[mina-1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
S = input()
result = 0
'''
for i in range(N):
    print(result)
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j ,N):
                if k- j == j - i:
                    continue
                if S[j] != S[k] and S[i] != S[k]:
                    result +=1
print(result)
'''
r = S.count('R')
g = S.count('G')
b = S.count('B')
target = set('RGB')
result = r*g*b
for i in range(N):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            tmp = (target - set(S[i]+S[j])).pop()
            if 2*j-i < N and S[2 * j - i] == tmp:
                result -= 1
print(result)

### FIXED CODE ###

N = int(input())
S = input()
result = 0
'''
for i in range(N):
    print(result)
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j ,N):
                if k- j == j - i:
                    continue
                if S[j] != S[k] and S[i] != S[k]:
                    result +=1
print(result)
'''
r = S.count('R')
g = S.count('G')
b = S.count('B')
target = set('RGB')
result = r * g * b
for i in range(N):
    for j in range(1, min(i, (N - i - 1)) + 1):
        if target == set(S[i] + S[i-j] + S[j + i]):
            result -= 1
print(result)