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

#デフォルト
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

ans = 1
sub = 10 ** 18

for i in a:
    ans *= i

if ans > sub:
    ans = -1
print(ans)

### FIXED CODE ###

#デフォルト
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

ans = 1
sub = 10 ** 18
for i in range(n):
    if a[i] == 0:
        print("0")
        exit()
for i in a:
    ans *= i
    if ans > sub:
        ans = -1
        break

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

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
from math import log
mx = min(int(log(K)) + 10**4, K)
for _ in range(mx):
    left_right = [0] + [(i-A[i], i+A[i]) for i in range(1, N+1)]
    ini = [0]*(N+1)
    for i in range(1, 1+N):
        l, r = left_right[i]
        l = max(1, l)
        ini[l] += 1
        if r+1 <= N:
            ini[r+1] -= 1
    A[1] = ini[1]
    for i in range(2, N+1):
        A[i] = A[i-1] + ini[i]
print(*A[1:])


### FIXED CODE ###

from math import log
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    from math import log
    mx = min(int(log(K)) + 100, K)
    for _ in range(mx):
        left_right = [0] + [(i-A[i], i+A[i]) for i in range(1, N+1)]
        ini = [0]*(N+1)
        for i in range(1, 1+N):
            l, r = left_right[i]
            l = max(1, l)
            ini[l] += 1
            if r+1 <= N:
                ini[r+1] -= 1
        is_all_n = True
        A[1] = ini[1]
        if A[1] != N:
            is_all_n = False
        for i in range(2, N+1):
            A[i] = A[i-1] + ini[i]
            if A[i] != N:
                is_all_n = False
        if is_all_n:
            break
    print(*A[1:])
main()
### BUGGY CODE ###

N, M = map(int, input().split())
li = []
for i in range(M):
  liin = input().split()
  li.append([int(liin[0]), liin[1]])

ans = [0, 0]
done = []
miss = {}

for i in range(M):
  if li[i][0] in done:
    continue
  if li[i][1] == "AC":
    ans[0] += 1
    done.append(li[i][0])
    if li[i][0] in miss:
      ans[1] += miss[li[i][0]]
      del miss[li[i][0]]
  else: # "WA"
    if li[i][0] in miss:
      miss[li[i][0]] += 1
    else:
      miss[li[i][0]] = 1

print(ans[0],ans[1])

### FIXED CODE ###

N, M = map(int, input().split())
li = []
for i in range(M):
  liin = input().split()
  li.append([int(liin[0]), liin[1]])

ans1, ans2 = 0, 0
done = set([0])
miss = {}

for i in range(M):
  if li[i][0] in done:
    continue
  if li[i][1] == "AC":
    ans1 += 1
    done.add(li[i][0])
    if li[i][0] in miss:
      ans2 += miss[li[i][0]]
      del miss[li[i][0]]
  else: # "WA"
    if li[i][0] in miss:
      miss[li[i][0]] += 1
    else:
      miss[li[i][0]] = 1

print(ans1,ans2)
### BUGGY CODE ###

n = int(input())

def warshall_floyd(d):
    for x in range(n):
        for y in range(n):
            for z in range(n):
                d[y][z] = min(d[y][z],d[y][x]+d[x][z])
    return d
    

graph = [[float("inf")]*n for _ in range(n)]

for i in range(n-1):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

for i in range(n):
    graph[i][i] = 0

G = warshall_floyd(graph)

ans = []
q,k = map(int,input().split())
for i in range(q):
    x,y = map(int,input().split())
    ans.append(G[k-1][x-1] + G[k-1][y-1])

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

from collections import deque

def f(k,edge,n):
    root = [[] for _ in range(n)]
    for i in range(n-1):
        a,b,c = edge[i][0],edge[i][1],edge[i][2]
        root[a-1].append([b-1,c])
        root[b-1].append([a-1,c])
    
    que = deque()
    for l in root[k]:
        que.append(l)
    
    dist = [float("inf")]*n
    dist[k] = 0
    visited = [False]*n
    que = deque([k])

    while que:
        pos = que.popleft()
        if not visited[pos]:
            visited[pos] = True
        for x,y in root[pos]:
            if not visited[x]:
                dist[x] = dist[pos] + y
                visited[x] = True
                que.append(x)
    return dist

n = int(input())
edge = [list(map(int,input().split())) for _ in range(n-1)]

q,k = map(int,input().split())

ans = []
d = f(k-1,edge,n)
for i in range(q):
    x,y = map(int,input().split())
    ans.append(d[x-1] + d[y-1])

print(*ans , sep = "\n")
### BUGGY CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=float("inf")
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')

### FIXED CODE ###

from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=10**19
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  que=[]
  d=[INF]*n
  d[s]=0
  visited={s}
  heappush(que,[0,s])
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,[d[node],node])
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
print(*ans_list[::-1], sep='\n')
### BUGGY CODE ###

expected_value_dic = {}

def get_expected_value(x):
    if x in expected_value_dic:
        return expected_value_dic[x]
    result = 0
    for i in range(1, x+1):
        result += i / x
    expected_value_dic[x] = result
    return result

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

P = list(map(int, input().split()))
expected_values = [get_expected_value(p) for p in P]

selected_array = [expected_values[i] for i in range(k)]
max_sum = sum(selected_array)
for i in range(k, len(P)):
    del selected_array[0]
    selected_array.append(expected_values[i])
    array_sum = sum(selected_array)
    if array_sum > max_sum:
        max_sum = array_sum


print(max_sum)


### FIXED CODE ###

expected_value_dic = {}

def get_expected_value(x):
    return (1 + x) / 2

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

P = list(map(int, input().split()))
expected_values = [get_expected_value(p) for p in P]
cumulative_values = [expected_values[0]]
for expected_value in expected_values[1:]:
    cumulative_values.append(cumulative_values[-1] + expected_value)

result = cumulative_values[k-1]
for i in range(k, n):
    temp = cumulative_values[i] - cumulative_values[i - k]
    if temp > result:
        result = temp

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

N,M = map(int,input().split())
Xs = list(map(int,input().split()))
Xs.sort()
diffs = []
for i in range(1,M):
    diffs.append(Xs[i]-Xs[i-1])

if len(diffs) != 0:
    for i in range(N-1):
        diffs[diffs.index(max(diffs))] = 0

print(sum(diffs))

### FIXED CODE ###

N,M = map(int,input().split())
Xs = list(map(int,input().split()))
Xs.sort()
diffs = []
for i in range(1,M):
    diffs.append(Xs[i]-Xs[i-1])
if len(diffs) > 0 and M > N:
    diffs.sort()
    print(sum(diffs[:M-N]))
else:
    print(0)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

dp = [[float('inf') for _ in range(sum(v) + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[何番目までの品物で][この価値以下を達成する]:=最小の重量

for i in range(N):
    for j in range(sum(v) + 1):
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
        else:
            dp[i + 1][j] = dp[i][j]

for j in sorted(range(sum(v) + 1), reverse=True):
    t = dp[N][j]
    if t <= W:
        print(j)
        break


### FIXED CODE ###

INF = 10 ** 12
MV = 10 ** 5

N, W = map(int, input().split())
dp = [[INF for _ in range(MV + 1)] for _ in range(N + 1)]
dp[0][0] = 0
# dp[品物のidx][価値の総和] = 実現する最小重量

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MV + 1):
        if j - v >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = -1
j = MV
while j >= 0:
    if dp[N][j] <= W:
        ans = j
        break
    j -= 1
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(N):
    pp = dp.copy()
    dp = [0 for _ in range(13)]
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])


### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0 for _ in range(13)]
pp = [0 for _ in range(13)]

dp[0] = 1
for i in range(N):
    pp, dp = dp, pp
    for d in range(13):
        dp[d] = 0
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])
### BUGGY CODE ###

mod=10**9+7
s=input()

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b

p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
d={i:0 for i in range(13)}
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1

    for i,v in enumerate(rev[num+1:]):
        #print(i+num+1)
        if v=="?":
            tmp=10**(i+num+1)%13
            t_d={i:0 for i in range(13)}
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d.values())
            for j in range(13):
                d[j]=t_d[j]
            #print(t_d)
    #print(d)
    print(d[cal]%mod)
        



### FIXED CODE ###

#%%time
mod=10**9+7
s=input()


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:
    #print(i+num+1)
    if v=="?":
        t_d=[0 for _ in range(13)]
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])
### BUGGY CODE ###

N=int(input())
X=list(map(int,input().split()))
for i in range(N):
    Z=sorted(X[:i]+X[i+1:])
    print(Z[N//2-1])

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
Y=sorted(X)
for i in range(N):
    if X[i]<=Y[N//2-1]:
        print(Y[N//2])
    else:
        print(Y[N//2-1])
### BUGGY CODE ###

import bisect

Q = int(input())

A = []
A_size = 0
A_med_min = 0
A_med_max = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        #常にソート済リストを作れる
        A.insert(bisect.bisect_left(A,a),a)
        A_size+=1
        #中央値との差分からA群からなる最小値を更新
        sabun = 0
        if a<A_med_min:
            sabun = A_med_min - a
        elif a>A_med_max:
            sabun = a - A_med_max
        MIN_SCORE += sabun + b if A_size>1 else b
        #中央値の更新
        if A_size%2==0:
            A_med_min = A[(A_size//2)-1]
            A_med_max = A[A_size//2]
        else:
            A_med_min = A[A_size//2]
            A_med_max = A[A_size//2]
    elif q[0]=="2":
        print(A_med_min,MIN_SCORE)

### FIXED CODE ###

import heapq

Q = int(input())

A_left = [] #最大を取り出すのでminus queueにする
A_right = [] #最小を取り出す
A_middle = 0
A_size = 0
MIN_SCORE = 0
for i in range(Q):
    q = input()
    if q[0]=="1": #更新
        dummy,a,b = map(int,q.split())
        A_size+=1
        sabun = 0
        if A_size==1: #初期設定
            A_middle = a
            sabun = 0
        elif A_size%2==0: #偶数処理
            if a <= A_middle:
                sabun = A_middle - a
                heapq.heappush(A_left,a*(-1))
                heapq.heappush(A_right,A_middle)
            else:
                sabun = a - A_middle
                heapq.heappush(A_left,A_middle*(-1))
                heapq.heappush(A_right,a)
            A_middle = 0 #デバッグ用
        else: #奇数処理
            if a<A_left[0]*(-1):
                sabun = A_left[0]*(-1) - a
                A_middle = heapq.heappop(A_left)*(-1)
                heapq.heappush(A_left,a*(-1))
            elif a>A_right[0]:
                sabun = a - A_right[0]
                A_middle = heapq.heappop(A_right)
                heapq.heappush(A_right,a)
            else:
                sabun = 0
                A_middle = a
        MIN_SCORE += sabun + b if A_size>1 else b
    elif q[0]=="2":
        if A_size%2==0:
            print(A_left[0]*(-1),MIN_SCORE)
        else:
            print(A_middle,MIN_SCORE)
### BUGGY CODE ###

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

for cnt in range(K):
  B = [0] * (N+1)
  for i in range(N):
    bright = A[i]
    l = max(i-bright,0)
    r = min(i+bright+1, N)
    B[l] += 1
    B[r] -= 1
  for i in range(N):
    B[i+1] += B[i]
  
  A = B[:-1]
  #print(A)
  if min(A) == N:
    #print(cnt)
    break
    
print(" ".join(map(str,A)))



### FIXED CODE ###

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

for cnt in range(K):
  B = [0] * (N+1)
  for i in range(N):
    bright = A[i]
    l = max(i-bright,0)
    r = min(i+bright+1, N)
    B[l] += 1
    B[r] -= 1
  for i in range(N):
    B[i+1] += B[i]
  
  A = B[:-1]
  #print(A)
  if min(A) == N:
    #print(cnt)
    break
    
print(" ".join(map(str,A)))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
    for j in range(i, N):
       if j - i == A[i] + A[j]:
           ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
dp = [0] * 10 ** 7
ans = 0
for i in range(N):
    x = i + 1 - A[i]
    if x >= 0:
        ans += dp[x]
    y = i + 1 + A[i]
    if y < 10 ** 7:
        dp[y] += 1

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

n = int(input())
from collections import defaultdict
G = defaultdict(list)
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = set(range(n))
    while len(Q) != 0:
        u = mind(Q, d)
        Q = Q - set([u])
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
    return d

for i,j in enumerate(dijkstra(G)):
    print(i, j)

### FIXED CODE ###

n = int(input())
import heapq
G = {}
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = [(d[i], i) for i in range(n)]
    heapq.heapify(Q)
    while len(Q) != 0:
        _, u = heapq.heappop(Q)
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(Q, (d[v], v))
    return d

for i,j in enumerate(dijkstra(G)):
    print(i, j)
### BUGGY CODE ###

def COMint():
  fac[0]=1
  fac[1]=1
  finv[0]=1
  finv[1]=1
  inv[1]=1
  for i in range(2,N+1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
def com(n,k):
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

MOD=10**9+7
N,K=[int(x) for x in input().split()]
A= [int(x) for x in input().split()]
A= sorted(A)
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
COMint()
ans=0
#print(fac)
for j in range(N-1,-1,-1):
  for i in range(j-K+2):
    mi = A[i]
    ma = A[j]
    #print(ma,mi,i,j,L[j-i-1])
    if j-i-1>=K-2:
 #     print(j-i-1,com(j-i-1,K-2))
      ans+=(ma-mi)*com(j-i-1,K-2)
print(ans%(10**9+7))

### FIXED CODE ###

def COMint():
  fac[0]=1
  fac[1]=1
  finv[0]=1
  finv[1]=1
  inv[1]=1
  for i in range(2,N+1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD
def com(n,k):
  if n<k:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
MOD=10**9+7
N,K=[int(x) for x in input().split()]
A= [int(x) for x in input().split()]
A= sorted(A)
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
COMint()
ans=0
#print(fac)
for j in range(N):
  ans+=(A[j])*com(j,K-1)
  ans-=(A[j])*com(N-1-j,K-1)
print(ans%(10**9+7))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import chain
from itertools import combinations as comb
# form bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter
# import numpy as np


def solve(N: int, K: int, p: "List[int]"):
    answer = min(map(sum, comb(p, K)))
    return answer

def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, K, p = map(int, line.split())
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, K, p)
    print(answer)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import chain

# form bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter
# import numpy as np


def solve(N: int, K: int, p: "List[int]"):
    p = sorted(p)
    return sum(p[:K])


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, K, p = map(int, line.split())
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, K, p)
    print(answer)


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

N = int(input())
A = list(map(int, input().split()))
L = [0 for i in range(N)]

total = 0

for i in range(N):
  r = 0
  for j in range(N):
    if i != j and A[i] == A[j]:
      r += 1
  L[i] = r
  total += r

total = total // 2

for i in L:
  print(total - i)


### FIXED CODE ###

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

for i in A:
  if i in dict:
    dict[i] = dict[i] + 1
  else:
    dict[i] = 1

#print(dict)
total = 0;
for i in dict:
#  print("i:" + str(i) + " " + str(dict[i]))
  total += dict[i]*(dict[i]-1) // 2

#print("T:" + str(total))

for i in A:
  print(total - dict[i] + 1)
### BUGGY CODE ###

n,m = map(int,input().split())
L =  [] 
for i in range(m):
    L.append(int(input()))
#print(L)
mod = 10**9+7
dp = [0]*(n+1)
dp[0]= 1
dp[1] = 1
#dp[2] = 2
for i in range(1,n+1):
    if 1 in L:
        dp[1] = 0
    if i in L:
        continue
    else:
        if i <= 1:
            dp[i] = dp[i-1]
        elif i>=2 :
            dp[i] = (dp[i-1]+ dp[i-2])%mod
        #print(dp)
print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
li = [int(input()) for i in range(m)]

st = [1]*(n+1)
for i in range(m):
    st[li[i]-1] = 0

if st[0] == 0 and st[1] == 0:
    print(0)
    exit()
elif st[0] == 0 and st[1] != 0:
    st[1] = 1
elif st[0] == 1 and st[1] != 0:
    st[1] = 2

for i in range(2,n+1):
    if st[i] == 0:
        continue
    else:
        st[i] = (st[i-1] + st[i-2])%1000000007
print(st[n-1])
### BUGGY CODE ###

import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0

def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()

### FIXED CODE ###

import math
N,W=map(int,input().split())
dp=[[math.inf for _ in range(100001)] for _ in range(N+1)]
#print(dp[-1][100000])
dp[0][0]=0
def min_(a,b):
  if a<b:
    return a
  else:
    return b
  
def nap():
  for i in range(N):
    w,v=map(int,input().split())
    for j in range(100001):
      if j-v>=0:
        #print(dp[i-1][j-w[i]])
        dp[i+1][j]=min(dp[i+1][j],dp[i][j-v]+w)
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
  ans=100000
  #print(dp[0][:4])
  while dp[-1][ans]>W:
    ans-=1
  print(ans)

nap()
### BUGGY CODE ###

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
ans = [0]*(K+1)
for i in range(K):
    if i % 2 == 0:
        ans[i+1] = ans[i]
    elif i in prime and (i+1)/2 in prime:
        ans[i+1] = ans[i] + 1
    else:
        ans[i+1] = ans[i]
        
for j in range(Q):
    if r[j] == l[j]:
        print(1)
    else:
        print(ans[r[j]]-ans[l[j]])
        



### FIXED CODE ###

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

Q = int(input())
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
 
K = max(r)
prime = prime(K)
a = [1]*(K+1)
s = [0]*(K+1)
a[0] = 0
a[1] = 0
for i in range(2,K+1):
    if a[i]:
        for j in range(i*i, K+1, i):
            a[j] = 0

for i in range(3,K+1,2):
    if a[i] and a[(i+1)//2]:
        s[i] = 1

for i in range(K):
    s[i+1] += s[i]

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if s[ll]-s[ll-2] == 1:
            print(1)
        else:
            print(0)
    else:
        print(s[rr] - s[ll-1])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0, N-3):
    for j in range(i, N-1):
        I = S[i]
        J = S[j]
        if I != J:
            color = ['R', 'G', 'B']
            color.remove(I)
            color.remove(J)
            ans += S[j+1:].count(color[0])
            try:
                if S[j+(j-i)] == color[0]:
                    ans -= 1
            except IndexError:
                continue
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
ans = r*g*b

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