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

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())

sum = 0
for i in range(1, N+1):
  for j in range(1, N+1):
    for k in range(1, N+1):
      hoge = gcd(i, j, k)
      sum+=hoge

print(sum)


### FIXED CODE ###

from math import gcd

N = int(input())

sum = 0
for i in range(1, N+1):
  for j in range(1, N + 1):
    x=gcd(i,j)
    for k in range(1, N + 1):
      hoge = gcd(x,k)
      sum+=hoge

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

import heapq
x, y, a, b, c = map(int,input().split())

p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
p = p[:x]
q = q[:y]

p = [-i for i in p]
q = [-i for i in q]
r = [-i for i in r]


result = [0]
for i in range(min(x+y+1, c+1)):
    hq = p+q+r[:i]
    heapq.heapify(hq)
    for j in range(x+y):
        result[-1] -= heapq.heappop(hq)
    result.append(0)
print(max(result))

### FIXED CODE ###

x, y, a, b, c = map(int,input().split())

p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
rr = [0]
for i in r:
    rr.append(rr[-1]+i)
p = p[:x]
q = q[:y]
pq = sorted(p+q)
ppqq = [sum(pq)]
for i in pq:
    ppqq.append(ppqq[-1]-i)
result = []
for i in range(min(x+y, c+1)):
    result.append(ppqq[i]+rr[i])
print(max(result))
### BUGGY CODE ###

import sys
from bisect import bisect_right

N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
#%%
b0 = []
ab1 = []
for a,b in ab:
    if a==0:
        b0.append(b+1)
    else:
        ab1.append([a/(b+1), a, b+1])

N0 = len(b0)
N1 = len(ab1)

b0.sort()
if N0>0:
    b_ruiseki = [0]*N0
    b_ruiseki[0] = b0[0]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

ab1.sort(reverse = True)

INF = T + 100

dp = [[INF]*31 for _ in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    # dp[i+1][j] : 0~i番目までの店を見て，j個選ぶときの最小時間
    
    for j in range(31):
        if j>i+1:break
        if j==0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-1] + (dp[i][j-1]+1)*ab1[i][1]+ab1[i][2])

for j in range(31):
    if dp[N1][j]>T:break    
    # a>0をj店舗めぐった後にa=0を何店舗めぐれるか
    num0 = bisect_right(b_ruiseki, T - dp[N1][j])
    ans = max(ans, j + num0)
        
    
print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_right

N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
#%%
b0 = []
ab1 = []
for a,b in ab:
    if a==0:
        b0.append(b+1)
    else:
        ab1.append([(b+1)/a, a, b])

N0 = len(b0)
N1 = len(ab1)

b0.sort()
if N0>0:
    b_ruiseki = [0]*N0
    b_ruiseki[0] = b0[0]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

ab1.sort()

INF = T + 100

dp = [[INF]*31 for _ in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    # dp[i+1][j] : 0~i番目までの店を見て，j個選ぶときの最小時間
    
    for j in range(31):
        if j>i+1:break
        if j==0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], (dp[i][j-1]+1)*(ab1[i][1]+1)+ab1[i][2])

for j in range(31):
    if dp[N1][j]>T:break    
    # a>0をj店舗めぐった後にa=0を何店舗めぐれるか
    num0 = bisect_right(b_ruiseki, T - dp[N1][j])
    ans = max(ans, j + num0)
        
    
print(ans)
### BUGGY CODE ###

S = str(input())
Q = int(input())


re_flag = 0
for i in range(Q):
    que = str(input())

    if len(que) == 1:
        #S = S[::-1]
        if re_flag == 0:
            re_flag = 1
        else:
            re_flag = 0

    else:
        if que[2] == '1':
            if re_flag == 0:
                S = que[4:] + S
            else:
                S =  S + que[-1:3:-1]
        if que[2] == '2':
            if re_flag == 0:
                S = S + que[4:]
            else:
                S = que[-1:3:-1] + S

if re_flag == 1:
    S = S[::-1]

print(S)

### FIXED CODE ###

from  collections import deque

S = str(input())
Q = int(input())

#Que = [list(map(str, input().split())) for _ in range(Q)]

deque_S = deque(S)
re_flag = 1
for i in range(Q):
    que = str(input())

    if len(que) == 1:
        #S = S[::-1]
        re_flag *= -1

    else:
        if que[2] == '1':
            if re_flag == 1:
                #S = que[4:] + S
                deque_S.appendleft(que[4:])
            else:
                #S =  S + que[-1:3:-1]
                deque_S.append(que[-1:3:-1])
        if que[2] == '2':
            if re_flag == 1:
                #S = S + que[4:]
                deque_S.append(que[4:])
            else:
                #S = que[-1:3:-1] + S
                deque_S.appendleft(que[-1:3:-1])

ans = ''
if re_flag == 1:
    ans = ''.join(deque_S)
else:
    ans = ''.join(deque_S)[::-1]
#print(deque_S)

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

s = input()
q = int(input())

for i in range(q):
  qi = input()
  if qi[0] == "1":
    s = s[::-1]
  else:
    t, f, c = qi.split() 
    if f == "1":
      s = c + s
    else:
      s = s + c
print(s)

### FIXED CODE ###

s = input()
q = int(input())
zengo = True
mae = []
usiro = []
for i in range(q):
  qi = input()
  if qi[0] == "1":
    if zengo:
      zengo = False
    else:
      zengo = True
  else:
    t, f, c = qi.split() 
    if zengo:
      if f == "1":
        mae.append(c)
      else:
        usiro.append(c)
    else:
      if f == "1":
        usiro.append(c)
      else:
        mae.append(c)
mae = mae[::-1]
s = ''.join(mae) + s + ''.join(usiro)
if zengo:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

dp = [0 for _ in range(100000)]

def main():
    N, M = map(int, input().split())
    A_B = [list(map(int, input().split()))[::-1] for _ in range(N)]
    logging.info("Hello!")

    sorted_A_B = sorted(A_B, reverse=True)
    logging.info(sorted_A_B)


    total = 0
    for i in range(N):
        if i >= M:
            break
        
        if sorted_A_B[i][1] + i <= M and sorted_A_B[i][0] != -1:
            total += sorted_A_B[i][0]
            sorted_A_B[i][0] = -1

        else:
            for k in range(i, N):
                if sorted_A_B[k][1] + i <= M and sorted_A_B[k][0] != -1:
                    total += sorted_A_B[k][0]
                    sorted_A_B[k][0] = -1


    print(total)
    
if __name__ == "__main__":
    main()



### FIXED CODE ###

import logging
import heapq

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)


def main():
    N, M = map(int, input().split())
    A_B = [list(map(int, input().split())) for _ in range(N)]
    logging.info("Hello!")

    A_B.sort()
    logging.info(A_B)


    heap_Q = []
    curr = 0
    total = 0
    for i in range(1, M + 1):
        while curr < N and  A_B[curr][0] <= i:
            heapq.heappush(heap_Q, A_B[curr][1] * (-1))
            curr += 1

        if heap_Q:
            total += (-1) * heapq.heappop(heap_Q)

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

N=int(input())
L=list(map(int,input().split()))
D=[{}for i in range(N)]
D[0][(0,0)]=L[0]
D[0][(1,1)]=0

for i in range(1,N):
    for k,v in D[i-1].items():
        #print(k)
        if k[0]==0:
            if k[1]+1<=(N-N//2):
                if (1,k[1]+1) in D[i]:
                    D[i][(1,k[1]+1)]=max(D[i][(1,k[1]+1)],v)
                else:
                    D[i][(1,k[1]+1)]=v
        else:
            if (0,k[1]) in D[i]:
                D[i][(0,k[1])]=max(D[i][(0,k[1])],v+L[i])
            else:
                D[i][(0,k[1])]=v+L[i]
            if k[1]+1<=(N-N//2):
                if (1,k[1]+1) in D[i]:
                    D[i][(1,k[1]+1)]=max(D[i][(1,k[1]+1)],v)
                else:
                    D[i][(1,k[1]+1)]=v
ans=-(10**9+7)
for i in D[-1].values():
    if ans<i:
        ans=i
print(ans)
                


### FIXED CODE ###

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

DP=[[-10**16 for i in range(N)]for j in range(3)]

DP[1][0]=0
DP[2][0]=0
DP[2][1]=0
DP[0][0]=A[0]
DP[1][1]=A[1]
if N>=3:
    DP[2][2]=A[2]

for i in range(2,N):
    DP[0][i]=DP[0][i-2]+A[i]
    DP[1][i]=DP[1][i-2]+A[i]
    DP[2][i]=DP[2][i-2]+A[i]
    if i-3>=0:
        DP[1][i]=max(DP[1][i],DP[0][i-3]+A[i])
        DP[2][i]=max(DP[2][i],DP[1][i-3]+A[i])
    if i-4>=0:
        DP[2][i]=max(DP[2][i],DP[0][i-4]+A[i])

if N%2==0:
    print(max(DP[0][-2],DP[1][-1]))
else:
    print(max(DP[0][-3],DP[1][-2],DP[2][-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019

    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * (times % mod)
        times = times * 10

    # 累積和
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    # print(R)
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        # print(r)
        ans = ans + cnt.get(r, 0)
        # cnt.setdefault(r, 0)
        # ans = ans + cnt[r]
        cnt[r] = cnt.get(r, 0) + 1
    # print(cnt)
    print(ans)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

S = input()
Q = int(input())
Query = []

for _ in range(Q):
    Query += [input()]

reversed = False
for i, q in enumerate(Query):
    if q == "1":
        reversed = not reversed
        # S = S[::-1]
    else:
        Ti, Fi, Ci = list(q.split())
        # print(f"Fi:{Fi} S:{S} reversed:{reversed} Ci:{Ci}")
        if Fi == "1":
            if not reversed:
                S = Ci + S
            else:
                S = S + Ci
        elif Fi == "2":
            # print(f"S:{S} reversed:{reversed} Ci:{Ci}")
            if not reversed:
                S = S + Ci
            else:
                S = Ci + S
    # print(f"i:{i} S:{S}")

if reversed:
    print(S[::-1])
else:
    print(S)


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
Query = []

S = deque([S])

for _ in range(Q):
    Query += [input()]

reversed = False
for i, q in enumerate(Query):
    if q == "1":
        reversed = not reversed
        # S = S[::-1]
    else:
        Ti, Fi, Ci = list(q.split())
        # print(f"Fi:{Fi} S:{S} reversed:{reversed} Ci:{Ci}")
        if Fi == "1":
            if not reversed:
                S.appendleft(Ci)
                # S = Ci + S
            else:
                S.append(Ci)
                # S = S + Ci
        elif Fi == "2":
            # print(f"S:{S} reversed:{reversed} Ci:{Ci}")
            if not reversed:
                S.append(Ci)
                # S = S + Ci
            else:
                S.appendleft(Ci)
                # S = Ci + S
    # print(f"i:{i} S:{S}")

s = "".join(S)

if reversed:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
RLC=sorted([[r,l,c] for l,r,c in LRC])
stack=[[0,1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(bisect_left(RLC,[a,0,0]),M):
            r,l,c=RLC[i]
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,r])
else:
    print(-1)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
x=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(x,M):
            l,r,c=LRC[i]
            x=i
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)
### BUGGY CODE ###

import heapq
n,a,b= map(int,input().split())
h =[int(input()) for i in range(n)]
h.sort()
p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**17
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)

### FIXED CODE ###

import heapq
n,a,b= map(int,input().split())
h =[int(input()) for i in range(n)]

p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**9
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)
### BUGGY CODE ###

for _ in[0]*int(input()):
 X,Y=' '+input(),' '+input();m,n=len(X),len(Y);c=[[0]*n for _ in[0]*m]
 for i in range(1,m):
  for j in range(1,n):c[i][j]=(max(c[i-1][j],c[i][j-1]),1+c[i-1][j-1])[X[i]==Y[j]]
 print(c[m-1][n-1])


### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

from fractions import gcd
n = int(input())
g = 0
for i in range (1, n+1):
  for j in range (1, n+1):
    for k in range (1, n+1):
      g  += gcd(gcd(i,j),k)
print(g)



### FIXED CODE ###

from math import gcd
N = int(input())
ans = 0
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(1,N+1):
      ans += gcd(gcd(i,j),k)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if j-i != k-j:
                if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                    count += 1
print(count)


### FIXED CODE ###

N = int(input())
S = "A"
S += input()
r = 0
g = 0
b = 0
k = 0
for i in range(1, N+1):
    if S[i] == "R":
        r += 1
    elif S[i] == "G":
        g += 1
    else:
        b += 1

sum = r * g * b
for i in range(1, N-1):
    for j in range(i+1,N):
        k = 2*j - i
        if k <= N:
            if S[j] != S[i] and S[k] != S[j] and S[i] != S[k]:
                sum -= 1

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

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

mod = 998244353
f = [1]
for i in range(1,N+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = 0

for i in range(K+1):
    k = ((M * pow((M-1), N-1-i, mod)) % mod) * comb(N-1,i)
    k %= mod
    ans += k
    ans %= mod
    
print(ans)
    
    
    


### FIXED CODE ###

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

mod = 998244353
f = [1]
for i in range(1,N+1):
    f.append((f[-1] * i) % mod)
def comb(n,r):
    return f[n] * (pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod) % mod

ans = 0

for i in range(K+1):
    k = ((M * pow((M-1), N-1-i, mod)) % mod) * comb(N-1,i)
    k %= mod
    ans += k
    ans %= mod
    
print(ans)
### BUGGY CODE ###

prims = list()

prims.append(2)

base = int(input())

def _is_prim(n):
  global prims
  for p in prims:
    if n == p:
      return True
    elif n % p == 0:
      return False
  
  return True

# 入力値までの素数を作る
for n in range(base):
  if n < 2:
    continue
  elif n % 2 == 0:
    continue
  elif _is_prim(n):
    prims.append(n)

# 作った素数値で。。。
while not _is_prim(base):
  base += 1

print(base)    


### FIXED CODE ###

import math

prims = list()

prims.append(2)

base = int(input())

def _is_prim(n):
  global prims
  for p in prims:
    if n == p:
      return True
    elif n % p == 0:
      return False
  
  return True

# 入力値の平方根までの素数を作る
rt = int(math.sqrt(base))
for n in range(rt):
  if n < 2:
    continue
  elif n % 2 == 0:
    continue
  elif _is_prim(n):
    prims.append(n)

# 作った素数値で。。。
while not _is_prim(base):
  base += 1

print(base)
### BUGGY CODE ###

N,K=list(map(int, input().split()))
A=list(map(int, input().split()))
A.sort()
S=set(A)
B=[]
for i in S:
  j=0
  while A[j]==A[0]:
    j+=1
    if j==len(A):
      break
  B.append(j)
  A=A[j:]
B.sort()
# print(B)
C=B[:len(S)-K]
print(sum(C))


### FIXED CODE ###

from collections import Counter

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

dic = dict(Counter(A))
ls = list(dic.items())
ls.sort(key=lambda x: x[1])

i=0
ans=0
res=len(ls)
while 1:
  if res <= K or i >= N:
    break
  ans += ls[i][1]
  i+=1
  res-=1
print(ans)
### BUGGY CODE ###

def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

    dp = [0] * (N+1)
    dp[0] = 1

    for i in range(N):
        if i+1 in A:
            dp[i+1] = 0
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    # print(dp)
    return dp[N]


if __name__ == "__main__":
    M = 0

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

    ans = typical_stairs(N, M, A)
    print(ans)


### FIXED CODE ###

import bisect


def typical_stairs(N: int, M: int, A: list)->int:
    MOD = 10**9 + 7

    A.sort()
    A.append(float('inf'))

    dp = [0] * (N+1)
    dp[0] = 1

    for i in range(N):
        if A[bisect.bisect_left(A, i+1)] == i+1:
            dp[i+1] = 0
        else:
            dp[i+1] = dp[i]
            if i > 0:
                dp[i+1] += dp[i-1]
                dp[i+1] %= MOD

    # print(dp)
    return dp[N]


if __name__ == "__main__":
    M = 0

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

    ans = typical_stairs(N, M, A)
    print(ans)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = str(input())
for i in range(Q):
    l, r = map(int,input().split())
    S_tmp = S[l-1:r]
    tmp = []
    for j in range(0,len(S_tmp),1):
        tmp.append(S_tmp[j:j+2])
    print(tmp.count("AC"))


### FIXED CODE ###

N, Q = map(int,input().split())
S = str(input())
count = 0
li = [0]
for i in range(N-1):
    if S[i:i+2] == "AC":
        count += 1
    li.append(count)
for i in range(Q):
    l,r = map(int,input().split())
    print(li[r-1]-li[l-1])
### BUGGY CODE ###

N = int(input())
S = input()
s = list(S)

def check(a,b,c):
    if abs(a-b) == abs (a-c) or abs(b-a) == abs (b-c) or abs(c-a) == abs (c-b):
        return True
    else:
        return False

R=[]
G=[]
B=[]
for i in range(N):
    if s[i] == "R":
        R.append(i+1)
    elif s[i] == "G":
        G.append(i+1)
    else:
        B.append(i+1)
count = 0
for i in range(len(R)):
    for j in range(len(G)):
        for k in range(len(B)):
            if check(R[i],G[j],B[k]):
                count +=1
print(len(R)*len(G)*len(B)-count)

### FIXED CODE ###

N = int(input())
S = input()
s = list(S)

R=[]
G=[]
B=[]
for i in range(N):
    if s[i] == "R":
        R.append(i+1)
    elif s[i] == "G":
        G.append(i+1)
    else:
        B.append(i+1)

count = len(R)*len(G)*len(B)
for i in range(1,N-1):
    f = s[i-1::-1]
    b = s[i+1:]
    for j in range(min(len(f),len(b))):
        if f[j]!=s[i] and f[j] != b[j] and s[i] != b[j]:
            count -=1
print(count)
### BUGGY CODE ###

def com(n,r):
    if n-r<r:
        r=n-r
    re=1
    for i in range(n,n-r,-1):
        re*=i
    for i in range(1,r+1):
        re//=i
    return re

md=10**9+7
n,m,k=map(int,input().split())
ans=0
for d in range(1,m):
    ans+=d*(m-d)*n*n
for d in range(1,n):
    ans+=d*(n-d)*m*m
ans=ans*com(n*m-2,k-2)
print(ans%md)


### FIXED CODE ###

def com(n,r):
    re=fct[n]*pow(fct[r],md-2,md)*pow(fct[n-r],md-2,md)
    re%=md
    return re

n,m,k=map(int,input().split())
md=10**9+7
ans=0
fct=[1]*(n*m-1)
f=1
for i in range(1,n*m-1):
    f=f*i%md
    fct[i]=f
for d in range(1,m):
    ans=(ans+d*(m-d)*n*n)%md
for d in range(1,n):
    ans=(ans+d*(n-d)*m*m)%md
ans=(ans*com(n*m-2,k-2))%md
print(ans)