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

P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        for j in range(P):
            X[j] = (X[j] - C(j) * pow(-i, P-1-j, P)) % P
        X[0] = (X[0] + 1) % P
print(*X)


### FIXED CODE ###

P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        c = 1
        for j in range(P)[::-1]:
            X[j] = (X[j] - C(j) * c) % P
            c = -c * i % P
        X[0] = (X[0] + 1) % P
print(*X)
### BUGGY CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
ans=0
for x in a:
  ans+=lcm//x
print(ans%mod)

### FIXED CODE ###

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

import fractions
lcm = 1
prevlcm = 1
ans = 0
for i in range(n):
    ai = a[i]
    lcm = ai * lcm // fractions.gcd(ai, lcm)
    if prevlcm == lcm:
        ans = ans + (lcm // ai)
    else:
        ans = ans * (lcm // prevlcm) + (lcm // ai)
    #print(i, lcm, ans)
    prevlcm = lcm

print(ans % (10**9 + 7))
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
from functools import lru_cache

@lru_cache(maxsize=None)
def f(N, *A):
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][i] = 0
    for l in range(1, N + 1):
        for i in range(N - l + 1):
            j = i + l
            if (N - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
    print(dp[0][N])

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    f(N,*A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import lru_cache
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')

@lru_cache(maxsize=None)
def f(N, *A):
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][i] = 0
    for l in range(1, N + 1):
        for i in range(N - l + 1):
            j = i + l
            if (N - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
    print(dp[0][N])

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    f(N,*A)

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

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[0][0]<=latest:
    a,b=AB.pop(0)
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

lis=list(map(int,input().split()))
alist=[]
for i in range(lis[1]):
    alist.append(int(input()))
steps=[0]*(lis[0]+2)
steps[1]=1
for i in range(2,lis[0]+2):
    if i-1 not in alist:
        steps[i]=(steps[i-1]+steps[i-2])
ans=steps[-1]%((10**9)+7)
print(ans)


### FIXED CODE ###

lis=list(map(int,input().split()))
alist=[0]*(lis[0]+1)
for i in range(lis[1]):
    a=int(input())
    alist[a]=1
steps=[0]*(lis[0]+2)
steps[1]=1
mod=(10**9)+7
for i in range(2,lis[0]+2):
    if alist[i-1]==0:
        steps[i]=(steps[i-1]+steps[i-2])%mod
ans=steps[-1]
print(ans)
### BUGGY CODE ###

S = raw_input()
Q = int(raw_input())
for _ in range(Q):
    q = raw_input()
    if q!='1':
        if q[2]=='1':
            S = q[4]+S
        else:
            S = S+q[4]
    else:
        S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
s = 1
for _ in range(Q):
    q = input()
    if q!='1':
        if (q[2]=='1' and s==1) or (q[2]!='1' and s!=1):
            S.extendleft(q[4])
        else:
            S.extend(q[4])
    else:
        s *= -1
S = ''.join(list(S))
if s==1:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

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

for _ in range(n):
    a = int(input())
    if a not in l:
        l.append(a)
    else:
        l.remove(a)


print(len(l))

### FIXED CODE ###

n = int(input())
l = []
 
for _ in range(n):
    a = int(input())
    l.append(a)

l.sort()

ans = 0
cnt = 1
tmp = l[0]
for i in range(1,len(l)):
    if tmp == l[i]:
        cnt += 1
        tmp = l[i]
    else:
        if cnt%2 != 0:
            ans += 1
            cnt = 1
            tmp = l[i]
        else:
            cnt = 1
            tmp = l[i]
if cnt%2 != 0:
    ans += 1

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

# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18
 
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
 
cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)
 
# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)
 
import heapq
 
len_max = 0
for i in range(2):
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue
 
# print("#", len_max)
 
if len_max % 3 == 1:
    print('Second')    
else:
    print('First')

### FIXED CODE ###

# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18
 
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
 
cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)
 
# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)
 
import heapq
 
len_max = 0
for i in range(2):
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue
 
# print("#", len_max)
 
if len_max % 3 == 1:
    print('Second')    
else:
    print('First')
### BUGGY CODE ###

from operator import mul
from functools import reduce
N, *A = map(int, open(0).read().split())
x = reduce(mul, A)
if x > 10 ** 18:
  x = -1
print(x)

### FIXED CODE ###

import sys

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

N, *A = map(int, read().split())

U = 10 ** 18
p = 1
for x in A:
    p *= x
    if p > U:
        p = U + 1

if p > U:
    print(-1)
else:
    print(p)
### BUGGY CODE ###

N = int(input())

my_list = [None] * N

for i in range(N):
    s_i = sorted(input())
    my_list[i] = s_i

sum = 0

for i in range(N):
    for j in range(i + 1, N):
        for k in range(10):
            if not(my_list[i][k] == my_list[j][k]):
                break
            elif k == 9:
                sum += 1


print(sum)


### FIXED CODE ###

n = int(input())
dict = {}
ans = 0

for i in range(n):
    s = str(sorted(input()))
    if s in dict.keys():
        ans += dict[s]
        dict[s] += 1
    else:
        dict[s] = 1
print(ans)
### BUGGY CODE ###


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

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

# 0 0 1 1 全部黒
# 0 1 2 2
# 0 1 1 1
# 0 1 1 2 全部白
#  # . #

sum = [0]*(n+1)
ans = n

for i in range(n+1):
    for j in range(0,i):
        # print('i = {}, j = {}'.format(i,j))
        if s[j] == '#':
            sum[j+1] = sum[j] + 1
        else:
            sum[j+1] = sum[j]
        if sum[j+1]>ans:
            break

    for k in range(i, n):
        # print('i = {}, k = {}'.format(i,k))
        if s[k] == '.':
            sum[k+1] = sum[k] + 1
        else:
            sum[k+1] = sum[k]
        if sum[k+1]>ans:
            break
    ans = min(ans, sum[n])
print(ans)

### FIXED CODE ###


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

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

sum_w = [0]*(n+1)
sum_b = [0]*(n+1)
ans = n

for i in range(n):
    if s[i] == '#':
        sum_b[i+1] = sum_b[i] + 1
    else:
        sum_b[i+1] = sum_b[i]

    if s[i] == '.':
        sum_w[i+1] = sum_w[i] + 1
    else:
        sum_w[i+1] = sum_w[i]

ans = n
for i in range(n+1):
    ans = min(ans, sum_b[i]+sum_w[n]-sum_w[i])
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
Islands=[[] for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1].append([b-1,c])
  Islands[b-1].append([a-1,c])
  Edge.append([a-1,b-1])
for m in range(M):
  a=Edge[m][0]
  b=Edge[m][1]
  for i in Islands[a]:
    if i[0]==b:
      c_m=i[1]
  List=[[a,0]]
  for l in List:
    c_base=l[-1]
    c=c_base
    if l[-2]==b:
      if c_m>c:
        S+=1
        break
    else:        
      for n in Islands[l[-2]]:
        if n[0] in l[0:-1]:
          pass
        else:
          c+=n[1]
          List.append(l[0:-1]+[n[0],c])  
          c=c_base
print(S)      
    

### FIXED CODE ###

N,M=map(int,input().split())
Islands=[[10**9]*N for i in range(N)]
Edge=[]
S=0
for i in range(M):
  a,b,c=map(int,input().split())
  Islands[a-1][b-1]=c
  Islands[b-1][a-1]=c
  Edge.append([a-1,b-1,c])
for k in range(N):
  for i in range(N):
    for j in range(N):
      Islands[i][j]=min(Islands[i][j],Islands[i][k]+Islands[k][j])

ans=0
for a,b,c in Edge:
  if Islands[a][b]!=c:
    ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7

def main():
  n, c = map(int, input().split())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  E = [[0]*(c+1) for _ in range(n)]
  for j in range(c+1):
    cumsum = tuple(pow(k, j, MOD) for k in range(401))
    cumsum = tuple(accumulate(cumsum))
    for i, (a, b) in enumerate(zip(A, B)):
      E[i][j] = cumsum[b] - cumsum[a-1]

  dp = [[0]*(c+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i, e in enumerate(E):
    for j, f in enumerate(e):
      for k in range(c+1-j):
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
  ans = dp[n][c]
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7

n, c = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
E = [[0]*(c+1) for _ in range(n)]
for j in range(c+1):
  cumsum = tuple(pow(k, j, MOD) for k in range(401))
  cumsum = tuple(i%MOD for i in accumulate(cumsum))
  for i, (a, b) in enumerate(zip(A, B)):
    E[i][j] = cumsum[b] - cumsum[a-1]

dp = [[0]*(c+1) for _ in range(n+1)]
dp[0][0] = 1
for i, e in enumerate(E):
  for j, f in enumerate(e):
    for k in range(c+1):
      if j+k <= c:
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
ans = dp[n][c]
print(ans)
### BUGGY CODE ###

n = int(input())

ans = 1
for i in range(1, n + 1):
    ans = ans * i

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


### FIXED CODE ###

n = int(input())

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

# ans = ans % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

def divisor(n):  # nの約数を全て求める
    i = 1
    table =0
    while i * i <= n:
        if n % i == 0:
            table+=2
            if i==n//i:
                table-=1
        i += 1
    
    return table
n = int(input().strip())

ans=0
for i in range(1,n+1):
    ans+=i*divisor(i)
print(ans)

### FIXED CODE ###

n = int(input().strip())

ans=0
for divisor in range(1,n+1):
    ans+=divisor*(n//divisor*(n//divisor+1)//2)

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

k,s = map(int,input().split())
cnt = 0
for x in range(0,k+1):
    for y in range(0,k+1):
        for z in range(0,k+1):
            if x+y == s-z:
                cnt +=1
print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(0,k+1):
    for y in range(0,k+1):
        if 0 >= x+y-s >= -k :
            cnt +=1
print(cnt)
### BUGGY CODE ###

from collections import Counter

def factorization(n):
    counter = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            counter[i] = cnt

    if temp!=1:
        counter[temp] = 1

    if len(counter)==0:
        counter[n] = 1

    return counter

mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))

A_primefact = [0]*N
union = Counter()
for i in range(N):
    A_primefact[i] = factorization(A[i])
    union = union | A_primefact[i]

ans = 0
for i in range(N):
    tmp = 1
    for prime in (union-A_primefact[i]).most_common():
        tmp *= prime[0]**prime[1]
        tmp %= mod
    ans += tmp
ans %= mod

print(ans)


### FIXED CODE ###

import fractions

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    lcm = 1
    for Ai in A:
        lcm = lcm*Ai//fractions.gcd(lcm,Ai)
    lcm %= mod
    ans = 0
    for Ai in A:
        ans += lcm*pow(Ai,mod-2,mod)%mod
        ans %= mod
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
s = sum(a)
m = (s + 1) // 2
m1 = m + 1

ab = [[-1] * m1 for _ in range(N + 1)]
for j in range(m):
    ab[N][j] = 0
ab[N][m] = 1
for j in range(N - 1, 0, -1):
    ab[j][m] = (3 * ab[j + 1][m]) % 998244353


def func(n, r):
    if r >= m:
        return ab[n][m]
    else:
        if ab[n][r] > -1:
            return ab[n][r]
        else:
            ret = (func(n + 1, r + a[n]) + 2 * func(n + 1, r)) % 998244353
            ab[n][r] = ret
            return ret


def func1(n, r):
    if n == N - 1:
        if r + a[n] == m:
            return 1
        else:
            return 0
    elif r + a[n] > m:
        return func1(n + 1, r)
    elif r + a[n] == m:
        return 1 + func1(n + 1, r)
    else:
        return (func1(n + 1, r + a[n]) + func1(n + 1, r)) % 998244353


ans1 = func(0, 0)
ans = 3 ** N % 998244353 - 3 * ans1
if s % 2 == 0:
    ans2 = func1(0, 0)
    ans += 3 * ans2

print(ans % 998244353)

### FIXED CODE ###

import numpy as np

N = int(input())
a = sorted([int(input()) for _ in range(N)])

s = sum(a)
m = (s + 1) // 2
m1 = m + 1


def func():
    ab = np.zeros((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = (2 * ab[i, :-c] + ab[i, c:]) % 998244353
        ab[i + 1, -c:] = (2 * ab[i, -c:] + ab[i, m]) % 998244353
    return ab[N, 0]


def func1():
    ab = np.zeros((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = (ab[i, :-c] + ab[i, c:]) % 998244353 
        ab[i + 1, -c:] = ab[i, -c:]
    return ab[N, 0]


ans = 3 ** N % 998244353 - 3 * func()
if s % 2 == 0:
     ans += 3 * func1()
print(ans % 998244353)
### BUGGY CODE ###

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

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

C = [1]
i = 0

while True:
    C.append(A[i])
    i = A[i]-1
    if i == 0:
        C.pop(len(C)-1)
        break
        
r = K % len(C)


print(C[r])

### FIXED CODE ###

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

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

C = [1]
D = {1}
i = 0
C1 = []
C2 = []
while True:
    if A[i] not in D:
        C.append(A[i])
        D.add(A[i])
        i = A[i]-1
    else:
        index = C.index(A[i])
        C1 = C[:index]
        C2 = C[index:]
        break

        
if K <= len(C1)-1:
    print(C1[K])
else:
    r = (K-len(C1))%len(C2)
    print(C2[r])
### BUGGY CODE ###

from collections import defaultdict

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

pre = [1<<i for i in range(n)]
bitcnt = [0]*(1<<n)
bitcnt[1] = 1
for i in range(1<<(n-1)):
    bitcnt[2*i] = bitcnt[i]
    bitcnt[2*i+1] = bitcnt[i]+1

DP = [defaultdict(lambda : float("inf")) for i in range(n)]

for i in range(n):
    DP[i][1<<i] = 0

# 枝刈り用
# 最後に選んだ数,その時点でのstateが同じものならcostが最小のものだけを残すようにした
s = defaultdict(lambda : float("inf"))
for i in range(n-1):
    nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
    for j in range(n):
        last = a[j] if (i-j)%2 == 0 else b[j]
        for state, cost in DP[j].items():
            for to in range(n):
                if state>>to&1:
                    continue
                nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                if last > nlast:
                    continue
                nstate = state|pre[to]
                ncost = cost
                ncost += bitcnt[state>>to]
                if s[(nstate, nlast)] <= ncost:
                    continue
                s[(nstate, nlast)] = ncost
                if nxt[to][nstate] > ncost:
                    nxt[to][nstate] = ncost
    DP = nxt
mask = (1<<n)-1
ans = float("inf")
for i in range(n):
    ans = min(ans, DP[i][mask])
if ans == float("inf"):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from collections import defaultdict

def main():

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

    if all(a[0] == a[i] for i in range(n)):
        print(0)
        exit()

    pre = [1<<i for i in range(n)]
    bitcnt = [0]*(1<<n)
    bitcnt[1] = 1
    for i in range(1<<(n-1)):
        bitcnt[2*i] = bitcnt[i]
        bitcnt[2*i+1] = bitcnt[i]+1

    DP = [defaultdict(lambda : float("inf")) for i in range(n)]

    for i in range(n):
        DP[i][1<<i] = 0
    s = defaultdict(lambda : float("inf"))
    for i in range(n-1):
        nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
        for j in range(n):
            last = a[j] if (i-j)%2 == 0 else b[j]
            for state, cost in DP[j].items():
                for to in range(n):
                    if state>>to&1:
                        continue
                    nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                    if last > nlast:
                        continue
                    nstate = state|pre[to]
                    ncost = cost
                    ncost += bitcnt[state>>to]
                    if s[(nstate, nlast)] <= ncost:
                        continue
                    s[(nstate, nlast)] = ncost
                    if nxt[to][nstate] > ncost:
                        nxt[to][nstate] = ncost
        DP = nxt
    mask = (1<<n)-1
    ans = float("inf")
    for i in range(n):
        ans = min(ans, DP[i][mask])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

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

# 2019/03/24
# AtCoder Beginner Contest 122 - C

# Input
n, q = map(int,input().split())
s = input()
sab = list()

for i in range(q):
    l, r = map(int,input().split())
    ans = 0
    
    for j in range(l-1, r-1, 1):
        if j == n:
            break
        else:
            if s[j] == "A" and s[j+1] == "C":
                ans += 1
    # Output
    print(ans)


### FIXED CODE ###

# 2019/04/28
# AtCoder Beginner Contest 122 - C

# Input
n, q = map(int,input().split())
s = input()

acgt = ["A", "C", "G", "T"]
acgtl = list()
acgtl.append(0)

# Search AC and make Accumed sum
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        acgtl.append(acgtl[i]+1)
    else:
        acgtl.append(acgtl[i])
        
# Calc AC count
for x in range(q):
    l, r = map(int,input().split())
    ans = acgtl[r-1] - acgtl[l-1]
    print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())

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

for i in range(N):
    for sum_w in range(1, W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


### FIXED CODE ###

MAX_V = 100100
MAX_N = 101
INF = pow(2, 70)

N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[INF for _ in range(MAX_V)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(MAX_V):
        # print(i, sum_v, sum_v - v[i] >= 0)
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        # print(dp[i + 1][sum_v])

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])
# for l in dp:
#     print([n for n in l if not n == INF])

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

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7

def fa(n):
    arr = []
    temp = n
    m = int(n**0.5//1)
    for i in range(2, m+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

l = []
for i in range(n):
	deg = fa(a[i])
	if i == 0:
		l = deg
	else:
		for j in range(len(deg)):
			for k in range(len(l)):
				if deg[j][0] == l[k][0]:
					l[k][1] = max(l[k][1], deg[j][1])
					break
			else:
				l.append(deg[j])
lcm = 1
for fac in l:
	factors = pow(fac[0], fac[1], MOD)
	lcm = (lcm*factors)%MOD
ans = 0
for i in range(n):
	ans += pow(a[i], MOD-2, MOD)
print((ans*lcm)%MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7

def fa(n):
    arr = []
    temp = n
    m = int(n**0.5//1)
    for i in range(2, m+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

l = []
for i in range(n):
	deg = fa(a[i])
	if i == 0:
		l = deg
	else:
		for j in range(len(deg)):
			for k in range(len(l)):
				if deg[j][0] == l[k][0]:
					l[k][1] = max(l[k][1], deg[j][1])
					break
			else:
				l.append(deg[j])
lcm = 1
for fac in l:
	factors = pow(fac[0], fac[1], MOD)
	lcm = (lcm*factors)%MOD
ans = 0
for i in range(n):
	ans += pow(a[i], MOD-2, MOD)
print((ans*lcm)%MOD)
### BUGGY CODE ###

s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
for i in range(len(s)):
    ans[tmp%2019]+=1
    tmp=10**i*int(s[-i-1])+tmp
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)

### FIXED CODE ###

s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
a=1
rs=reversed(s)
for i in rs:
    ans[tmp%2019]+=1
    tmp=(tmp+int(i)*a)%2019
    a*=10
    a%=2019
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)