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

s=input()[-1::-1]
n=len(s)
dp=[[0,0,0,0] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(4):
        dp[i+1][j]=dp[i][j]%1000000007
    if s[i]=="?":
        dp[i+1][0]+=2*dp[i][0]
        for j in range(1,4):
            dp[i+1][j]+=2*dp[i][j]+dp[i][j-1]
    else:
        index=" CBA".find(s[i])
        dp[i+1][index]+=dp[i][index-1]
print(dp[n][3]%1000000007)

### FIXED CODE ###

s=input()
n=len(s)
c=[0 for i in range(n)]
d=[0 for i in range(n)]
bc=[0 for i in range(n)]
bd=[0 for i in range(n)]
dc=[0 for i in range(n)]
dd=[0 for i in range(n)]
if s[-1]=="C":
    c[-1]=1
if s[-1]=="?":
    d[-1]=1
for i in range(-2,-n-1,-1):
    c[i]=c[i+1]
    d[i]=d[i+1]
    bc[i]=bc[i+1]
    bd[i]=bd[i+1]
    dc[i]=dc[i+1]
    dd[i]=dd[i+1]
    if s[i]=="B":
        bc[i]+=c[i+1]
        bd[i]+=d[i+1]
    if s[i]=="C":
        c[i]+=1
    if s[i]=="?":
        d[i]+=1
        dc[i]+=c[i+1]
        dd[i]+=d[i+1]
mul=[1,1,1,1]
for i in range(d[0]):
    mul[3]*=3
    mul[3]%=1000000007
for i in range(2,-1,-1):
    if mul[i+1]%3==0:
        mul[i]=mul[i+1]//3
    elif mul[i+1]%3==1:
        mul[i]=(mul[i+1]+1000000007)//3
    else:
        mul[i]=(mul[i+1]+2000000014)//3
res=0
for i in range(n-2):
    if s[i]=="A":
        res+=bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i]=="?":
        res+=bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res%=1000000007
print(res)
### BUGGY CODE ###

N = int(input().strip())
A = list(map(int,input().strip().split(' ')))
B = list(map(int,input().strip().split(' ')))
C = list(map(int,input().strip().split(' ')))
A.sort()
B.sort()
C.sort()
bstart = 0
cstart = 0
ans = 0
for ai in range(N):
    a = A[ai]
    cstart = 0
    for bi in range(bstart,N):
        b = B[bi]
        if a >= b:
            bstart = bi + 1
        else:    
            for ci in range(cstart,N):
                c = C[ci]
                if b >= c:
                    cstart = ci + 1
                else:
                    ans = ans + (N-ci)
                    break
                    
print(ans)

### FIXED CODE ###

import bisect as bi

N = int(input().strip())
A = list(map(int,input().strip().split(' ')))
B = list(map(int,input().strip().split(' ')))
C = list(map(int,input().strip().split(' ')))

A.sort()
B.sort()
C.sort()
ans = 0

for b in B:
    i = bi.bisect_left(A, b) # A[0],...,A[i - 1] < b
    k = bi.bisect_right(C, b) # b < C[k],...C[N-1]
    ans += i * (N - k)

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

#!/usr/bin/python3

import sys
import resource
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


n = int(input())
a = tuple(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

import itertools
import bisect

def main():
    N = int(input())
    S = input()
    d = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    #answer = set()
    cnt = 0
    for xx, yy, zz in itertools.permutations(('R', 'G', 'B'), 3):
        x, y, z = d[xx], d[yy], d[zz]
        for i in x:
            y_start = bisect.bisect_left(y, i)
            for jj in range(y_start, len(y)):
                j = y[jj]
                assert i < j
                z_start = bisect.bisect_left(z, j)
                # z_point = bisect.bisect_left(z, 2*j-i)
                # #print(z_point, z)
                # if (len(z) <= z_point) or (z[z_point] - j != j - i):
                #     cnt += len(z)
                # else:
                #     cnt += len(z) - 1
                for kk in range(z_start, len(z)):
                    k = z[kk]
                    assert j < k
                    if k-j > j-i:
                        #超えたのでもうチェックしなくていい
                        cnt += len(z) - kk
                        break
                    elif k-j == j-i:
                        cnt += len(z) - kk - 1
                        break
                    else:
                        #assert k > j > i
                        #answer.add((i+1, j+1, k+1))
                        cnt += 1
    print(cnt)
    #assert len(answer) == cnt
    #print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import itertools
import bisect

def main():
    N = int(input())
    S = input()
    d = {'R': [], 'G': [], 'B': []}
    for i, c in enumerate(S):
        d[c].append(i)
    #print(d)
    #answer = set()
    cnt = 0
    for xx, yy, zz in itertools.permutations(('R', 'G', 'B'), 3):
        x, y, z = d[xx], d[yy], d[zz]
        for i in x:
            y_start = bisect.bisect_left(y, i)
            for jj in range(y_start, len(y)):
                j = y[jj]
                assert i < j
                z_start = bisect.bisect_left(z, j)
                z_point = bisect.bisect_left(z, 2*j-i)
                #print(z_point, z)
                if (len(z) <= z_point) or (z[z_point] - j != j - i):
                    cnt += len(z) - z_start
                else:
                    cnt += len(z) - z_start - 1
                # for kk in range(z_start, len(z)):
                #     k = z[kk]
                #     assert j < k
                #     if k-j > j-i:
                #         #超えたのでもうチェックしなくていい
                #         cnt += len(z) - kk
                #         break
                #     elif k-j == j-i:
                #         cnt += len(z) - kk - 1
                #         break
                #     else:
                #         #assert k > j > i
                #         #answer.add((i+1, j+1, k+1))
                #         cnt += 1
    print(cnt)
    #assert len(answer) == cnt
    #print(answer)

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

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

P = [0]*(1000001)
for i in a: P[i] += 1


def check(N,P):
    if N == 1:
        if P[1]==1: return True
        else: return False

    if P[1] >= 1: return False
    if P[N] >= 2: return False
    i = 1
    
    for i in range(2,N):
        if i*i >= N: break
        if N%i == 0:
            #print(i,N)
            if P[i]>=1: return False
            if P[N//i]>=1: return False
    if i*i == N:
        if P[i]>=1: return False

    return True    

ans = 0
for N in a:
    if check(N,P): ans += 1

print(ans)



### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

d = {}
for i in a:
    if i in d: d[i] += 1
    else: d[i] = 1

M = 10**6+1
sieve = [0]*(M)
for k,v in d.items():
    for i in range(k,M,k):
        sieve[i] += v


ans = 0
for ai in a:
    if sieve[ai] == 1:
        ans += 1

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

def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    ret = []
    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


def main():
    N, M = map(int, input().split())
    E_in = [[] for _ in range(N)]
    E_from = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E_from[a].append(b)
        E_in[b].append(a)

    top_sort = topological_sort(N, E_in, E_from)

    # こっからを改善
    parent = [0]*N
    for i in range(N):
        current = top_sort[i]
        for j in reversed(top_sort[:i]):
            if current in E_from[j]:
                parent[current] = j+1
                break

    ans = '\n'.join(map(str, parent))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def topological_sort(V, E_in, E_from):
    '''
    V:N(node)
    E_from:
    E_in:
    '''

    # count num of pointed nodes for each nodes
    parent = [0]*V
    cnt = [0]*V
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            Q.append(v)

    while Q:
        del_node = Q.pop()
        for j in E_from[del_node]:
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)
                parent[j] = del_node+1

    return parent


def main():
    N, M = map(int, input().split())
    E_in = [[] for _ in range(N)]
    E_from = [[] for _ in range(N)]
    for _ in range(N+M-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E_from[a].append(b)
        E_in[b].append(a)

    ans = topological_sort(N, E_in, E_from)
    for s in ans:
        print(s)


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

n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(1,n):
    d[i]=min(d[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
print(d[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
d=[float('inf')]*n
d[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        d[i+j]=min(d[i+j],d[i]+abs(h[i+j]-h[i]))
print(d[-1])
### BUGGY CODE ###

n = int(input())
s = list(input())

r = [i for i, x in enumerate(s) if x == 'R']
g = [i for i, x in enumerate(s) if x == 'G']
b = [i for i, x in enumerate(s) if x == 'B']
ans = 0

for x in r:
    n = [i for i in g if i>x]
    for y in n:
        m = [i for i in b if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1
    n = [i for i in b if i>x]
    for y in n:
        m = [i for i in g if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1

for x in b:
    n = [i for i in r if i>x]
    for y in n:
        m = [i for i in g if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1
    n = [i for i in g if i>x]
    for y in n:
        m = [i for i in r if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1           
                
for x in g:
    n = [i for i in r if i>x]
    for y in n:
        m = [i for i in b if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1              
    n = [i for i in b if i>x]
    for y in n:
        m = [i for i in r if i>y]
        for z in m:
            if y-x != z-y:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
r = 0
g = 0
b = 0

for c in s:
    if c == "R":
        r += 1
    if c == "G":
        g += 1
    if c == "B":
        b += 1
ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = 2*j - i
        if k > n-1:
            continue
        x = s[i]
        y = s[j]
        z = s[k]
        if x!= y and y != z and z != x:
            ans -= 1

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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素であることが前提）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans


p = I()
a = III()

beki = [[0]*p for _ in range(p)]
for i in range(p):
    for j in range(p):
        beki[i][j] = pow(-i, j, p)

fact_inv = [0]*p
for i in range(p):
    fact_inv[i] = mod_inv(fact(i,p),p)

pfact = fact(p-1,p)

ans = [0]*p
for j in range(p):
    if a[j]==0:
        continue
    else:
        ans[0] += 1
        for i in range(p):
            ans[i] -= pfact*fact_inv[i]*fact_inv[p-1-i]*beki[j][p-1-i]
            ans[i] %= p

print(*ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素であることが前提）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans


p = I()
a = III()

beki = [[1]*p for _ in range(p)]
for i in range(p):
    for j in range(1,p):
        beki[i][j] = beki[i][j-1]*(-i)
        beki[i][j] = beki[i][j]%p

fact_inv = [0]*p
for i in range(p):
    fact_inv[i] = mod_inv(fact(i,p),p)

pfact = fact(p-1,p)

ans = [0]*p
for j in range(p):
    if a[j]==0:
        continue
    else:
        ans[0] += 1
        for i in range(p):
            ans[i] -= pfact*fact_inv[i]*fact_inv[p-1-i]*beki[j][p-1-i]
            ans[i] %= p

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K, S = MAP()

cnt = 0

A = [1]*(S+2)
for i in range(S+1):
	for j in range(1, S+2-i):
		if sum(A[:i]) <= K and sum(A[i+1:i+j]) <= K and sum(A[i+j+1:]) <= K:
			cnt += 1

print(cnt)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

K, S = MAP()

cnt = 0

for X in range(K+1):
	for Y in range(K+1):
		Z = S - X - Y
		if 0 <= Z <= K:
			cnt += 1
print(cnt)
### BUGGY CODE ###

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


Memo = []
def solve(data):
    global Memo
    for d in data:
        if d in Memo:
            Memo.remove(d)
        else:
            Memo.append(d)
    return len(Memo)


def main():
    N = int(input())
    data = [int(input()) for _ in range(N)]
    result = solve(data)
    print(result)


if __name__ == '__main__':
    main()
    


### FIXED CODE ###

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


Memo = []
def solve(data):
    global Memo
    for d in data:
        if d in Memo:
            Memo.remove(d)
        else:
            Memo.append(d)
    return len(Memo)


def solve2(data):
    from collections import Counter
    c = Counter(data).most_common()
    remaining = [x for x in c if x[1]%2==1]
    return len(remaining)


def main():
    N = int(input())
    data = [int(input()) for _ in range(N)]
    result = solve2(data)
    print(result)


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

n=int(input())
member = [0]*(10**5+1)

li = list(map(int,input().split()))
for i in range(n):
  member[li[i]] +=1

q = int(input())
for j in range(q):
  x,y = input().split()
  x=int(x)
  y=int(y)
  member[y]+=member[x]
  member[x]=0
  total = 0
  for k in range(10**5+1):
    total += k*member[k]
  print(total)

### FIXED CODE ###

n=int(input())
member = [0]*(10**5+1)
 
li = list(map(int,input().split()))
total = sum(li)
for i in range(n):
  member[li[i]] +=1
 
q = int(input())
for j in range(q):
  x,y = input().split()
  x=int(x)
  y=int(y)
  total += (y-x)*member[x]
  print(total)
  member[y]+=member[x]
  member[x]=0
### BUGGY CODE ###

N, K, Q = (int(x) for x in input().split())
A = [int(input()) for i in range(Q)]
ans = [K for i in range(N)]

for a in A:
    ans = list(map(lambda x: x-1, ans))
    ans[a-1] += 1

for b in ans:
    if b > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = (int(x) for x in input().split())
A = [int(input()) for i in range(Q)]
ans = [K-Q for i in range(N)]

for a in A:
    ans[a-1] += 1

for b in ans:
    if b > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  
  def count(l, r, a, x):
    mid = (l+r)//2
    if a > 0:
      if r - l <=1:
        return r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(mid, r, a, x)
      else:
        return count(l, mid, a, x)
    else:
      if r - l <=1:
        return n - r - (1 if a**2 <= x else 0)
      if a * As[mid] <= x:
        return count(l, mid, a, x)
      else:
        return count(mid, r, a, x)
      
  def bs(l, r):
    mid = (l+r) // 2
    if r - l <= 1:
      return r
    tot = 0
    for A in As:
      tot += count(-1, n, A, mid)
    tot //= 2
    if tot < k:
      return bs(mid, r)
    else:
      return bs(l, mid)
  print(bs(MIN-1, MAX+1))
    
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while  r >= 0 and xs[l] * ys[r] > ub:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      
      tot = 0      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

cnt = len(hs)*len(ws)
for h, w in HW:
    if h-1 in hs and w-1 in ws:
        cnt -= 1
print(max(h_count)+max(w_count) - (cnt==0))



### FIXED CODE ###

import sys

input = sys.stdin.readline
H, W, M = map(int, input().split())
h_count = [0]*H
w_count = [0]*W
HW = [tuple(map(int, input().split())) for _ in range(M)]
for h, w in HW:
    h_count[h-1] += 1
    w_count[w-1] += 1
h_max, w_max = 0, 0
hs, ws = [], []
for i in range(H):
    if h_max < h_count[i]:
        h_max = h_count[i]
        hs = [i]
    elif h_max == h_count[i]:
        hs.append(i)
for i in range(W):
    if w_max < w_count[i]:
        w_max = w_count[i]
        ws = [i]
    elif w_max == w_count[i]:
        ws.append(i)

HW = set(HW)
for h in hs:
    for w in ws:
        if (h+1, w+1) not in HW:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
hito=[]
points=[]
for _ in range(Q):
    hito.append(int(input()))
for _ in range(N):
    points.append(K)
for i in hito:
    for j in list(range(0,i-1))+list(range(i,N)):
        points[j]-=1
for point in points:
    if point>0:
        print("Yes")
    else:
        print("No")
    

### FIXED CODE ###

N,K,Q=map(int,input().split())
hito=[]
points=[]
for _ in range(Q):
    hito.append(int(input()))
for _ in range(N):
    points.append(K-Q)
for i in hito:
    points[i-1]+=1
for j in points:
    if j>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from fractions import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)

### FIXED CODE ###

from math import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)