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

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1-A[0]
    left = 0
    base = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]-base

        for _ in range(A[i]):
            if R[i] <= base:
                return '-1'
            base += 1
            ret += 1+i-left
            while R[left] == base and left < i:
                left += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if 0 < A[0]:
        return '1' if n == 0 and A[0] == 1 else '-1'

    R = [0]*(n+1)
    R[0] = 1
    for i in range(1, n+1):
        R[i] = 2*(R[i-1]-A[i-1])

    prev = 0
    ret = 0
    for i in range(n, -1, -1):
        if R[i] < A[i]:
            ret = -1
            break

        prev = min(R[i], A[i]+prev)
        ret += prev

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	s = IS()
	r,g,b=[],[],[]

	def binary_search(lst, K):
		l = 0; r = len(lst);
		while(l+1<r):
			mid = (l+r)//2
	    #下記の操作を書き換えることによって探索条件を変更可能
			if(lst[mid]>K): r=mid
			else: l=mid
		return l

	for i,ss in enumerate(s):
		if ss=='R':
			r.append(i)
		elif ss=='G':
			g.append(i)
		else:
			b.append(i)
	ans=len(r)*len(g)*len(b)
	for rr in r:
		for gg in g:
			a=max(rr,gg)+abs(rr-gg)
			if a in b:
				ans-=1
			a=min(rr,gg)-abs(rr-gg)
			if a in b:
				ans-=1
			if((rr+gg)%2==0):
				a=(rr+gg)//2
				if a in b:
					ans-=1
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	s = IS()
	r,g,b=[],[],[]

	def binary_search(lst, K):
		l = 0; r = len(lst);
		while(l+1<r):
			mid = (l+r)//2
	    #下記の操作を書き換えることによって探索条件を変更可能
			if(lst[mid]>K): r=mid
			else: l=mid
		return l

	for i,ss in enumerate(s):
		if ss=='R':
			r.append(i)
		elif ss=='G':
			g.append(i)
		else:
			b.append(i)
	ans=len(r)*len(g)*len(b)
	for rr in r:
		for gg in g:
			a=max(rr,gg)+abs(rr-gg)
			if(a<n):
				if(s[a]=="B"):
					ans-=1
			a=min(rr,gg)-abs(rr-gg)
			if(a<n and a>=0):
				if(s[a]=="B"):
					ans-=1
			if((rr+gg)%2==0):
				a=(rr+gg)//2
				if(a<n):
					if(s[a]=="B"):
						ans-=1
	print(ans)







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

def li():
    return [int(x) for x in input().split()]

N = int(input())
A = [0] + li()
d = 10**9 + 7

total = 0

for i in range(1, N):
    for j in range(i+1, N+1):
        total += ((A[i] % d) * (A[j] % d))
        total = total % d

print(total)

### FIXED CODE ###

def li():
    return [int(x) for x in input().split()]

N = int(input())
A = li()
d = 10**9 + 7
B = [A[i] % d for i in range(len(A))]

s = 0
s2 = 0
for i in range(len(B)):
    s += B[i]
    s = s
    s2 += B[i] ** 2
    s2 = s2

ans = ((s**2 - s2) // 2) % d

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

import collections
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=1
if n%2==1 and collections.Counter(a)[0]==1:
    for i in range(2,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
        else:
            ans=(ans%(10**9+7))*2%(10**9+7)
    else:
        print(ans%(10**9+7))
elif n%2==0:
    for i in range(1,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
        else:
            ans=(ans%(10**9+7))*2%(10**9+7)
    else:
        print(ans%(10**9+7))
else:
    print(0)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
if n%2==1:
    b=[i for i in range(2,n,2)]
    b=b*2
    b.sort()
    #print(a,b)
    b=[0]+b
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
elif n%2==0:
    b=[i for i in range(1,n,2)]
    b=b*2
    b.sort()
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    # 約数
    N = ir()
    A = lr()
    A.sort()
    answer = 0
    bl = [0] * (A[-1]+1)

    def make_divisors(n):  # nの約数を列挙
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        divisors.sort()
        return divisors

    for i, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = 1
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x] == 1:
                flag = False
                break
        bl[a] = 1
        if flag:
            answer += 1

    print(answer)

main()

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        pass
    elif bl[a]:
        answer += 1
    if bl[a]:
        bl[a] = False
        next = a + a
        while next <= A[-1]:
            bl[next] = False
            next += a

print(answer)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[i * N1 + i] = dpmax[i * N1 + i] = 0
    for i in range(N):
        dpmin[i * N1 + i + 1] = -a[i]
        dpmax[i * N1 + i + 1] = a[i]

    def minimize(a, begin, end):
        x = dpmin[begin * N1 + end]
        if x >= 0:
            return x
        pt1 = -a[begin] + maximize(a, begin + 1, end)
        pt2 = -a[end - 1] + maximize(a, begin, end - 1)
        r = min(pt1, pt2)
        dpmin[begin * N1 + end] = r
        return r

    def maximize(a, begin, end):
        x = dpmax[begin * N1 + end]
        if x >= 0:
            return x
        pt1 = a[begin] + minimize(a, begin + 1, end)
        pt2 = a[end - 1] + minimize(a, begin, end - 1)
        r = max(pt1, pt2)
        dpmax[begin * N1 + end] = r
        return r

    return maximize(a, 0, N)


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


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

n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        _count = count-1
    else:
        _num = num+2**i
        _count = count+1
    while True:
        if _num == 0:
            break
        _num %= _count
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        ans[i] += 1
for i in range(n):
    print(ans[-(i+1)])

### FIXED CODE ###

n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

mod = [[0, 0] for _ in range(n)]
mod[0][0] = 1%(count-1) if count!=1 else 0
mod[0][1] = 1%(count+1)
for i in range(1, n):
    if mod[i-1][0] != 0:
        mod[i][0] = (mod[i-1][0]*2)%(count-1)
    if mod[i-1][1] != 0:
        mod[i][1] = (mod[i-1][1]*2)%(count+1)
mod1 = num%(count-1) if count!=1 else 0
mod2 = num%(count+1)

table = [0]*(2*10**5+10)
for i in range(2*10**5+10):
    _num = i
    while True:
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        if _num == 0:
            break
        _num %= _count
        table[i] += 1

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod2+mod[i][1])%(count+1)
    ans[i] = 1+table[_num]
for i in range(n):
    print(ans[-(i+1)])
### BUGGY CODE ###


def count_ans(w_start, K, info_list):
    ans = 0
    for x, y, c in info_list:
        ofs_x = w_start[0]
        ofs_y = w_start[1]
        x2 = (x - ofs_x) // K
        y2 = (y - ofs_y) // K
        if (x2 + y2) % 2 == 0:
            if c == "W":
                ans += 1
        else:
            if c == "B":
                ans += 1
    return ans


# 入力
N, K = map(int, input().split())
info_list = []
for i in range(N):
    tmp = input().split()
    tmp[0], tmp[1] = int(tmp[0]), int(tmp[1])
    info_list.append(tmp)

# 白チェッカーの左下位置リスト
w_start_list = [[x, y] for x in range(K) for y in range(K)]

current_max = 0
for w_start in w_start_list:
    # 合っている個数を数える
    ans = count_ans(w_start, K, info_list)
    ans = max(N - ans, ans)
    if current_max < ans:
        current_max = ans

print(current_max)


### FIXED CODE ###

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

score = [[0] * (K+1) for y in range(K+1)]
base_hope = 0

for i in range(N):
    x, y, c = input().split()
    x2, y2 = int(x) // K, int(y) // K
    x_coord, y_coord = int(x) % K + 1, int(y) % K + 1
    if ((x2 + y2) % 2 == 0 and c == "W") or ((x2 + y2) % 2 == 1 and c == "B"):
        score[y_coord][x_coord] += 1
        base_hope += 1
    else:
        score[y_coord][x_coord] -= 1

xy = [(x, y) for x in range(K) for y in range(K)]
for x, y in xy:
    score[y+1][x+1] += score[y+1][x] + score[y][x+1] - score[y][x]

max_hope = 0
for x, y in xy:
    hope = base_hope - score[K][x] - score[y][K] + 2 * score[y][x]
    true_hope = hope if hope > N - hope else N - hope
    if true_hope > max_hope:
        max_hope = true_hope

print(max_hope)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
S = list(map(lambda x: sorted(x), S))
cnt = 0 
for i, str1 in enumerate(S):
    for str2 in S[i + 1:]:
        if str1 == str2:
            cnt += 1
print(cnt)

### FIXED CODE ###

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

# sort
for i in range(N):
    S[i] = "".join(sorted(S[i]))

# main
t = dict()
for i in range(N):
    if S[i] in t:
        t[S[i]] += 1
    else:
        t[S[i]] = 1

print(sum(t[key]*(t[key] - 1) // 2 for key in t))
### BUGGY CODE ###

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

left, right = 0, M
while right - left > 1:
  mid = (left + right) // 2
  if A[mid] > X:
    mid = left
  if A[mid] < X:
    mid = right

res = max(mid, M - mid)
print(res)

### FIXED CODE ###

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

idx = 0

while idx < M:
    if A[idx] > X:
        break
    idx += 1

res = min(idx, M - idx)
print(res)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    b=int(input())
    if b in a:
        a.remove(b)
    else:
        a.append(b)
print(len(a)) 

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()
h=a[0]
ans=1
for i in a[1:]:
    if i!=h:
        ans+=1
        h=i
    else:
        ans-=1
        h=pow(10,10)    
print(ans)
### BUGGY CODE ###

N = input()
list1 = list(map(int, input().split()))
answer = 1
for i in list1:
    answer *= i
if answer > 10**(18):
    print(-1)
else:
    print(answer)

### FIXED CODE ###

import sys

N = input()
list1 = list(map(int, input().split()))
answer = 1
for i in list1:
    if i == 0:
        print(0)
        sys.exit()
for i in list1:
    answer *= i
    if answer > 10**18:
        print(-1)
        sys.exit()
print(answer)
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for sum_w in range(K + 1):
        for i in range(N):
            if sum_w - W[i] < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - W[i]] + V[i]
                )
    print(dp[-1][-1])


main()


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

import math
k=int(input())
res=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            res+=math.gcd(math.gcd(a,b),c)
print(res)

### FIXED CODE ###

import math
k=int(input())
res=0
A=[]
for a in range(1,k+1):
    for b in range(1,k+1):
        A.append(math.gcd(a,b))
for a in A:
    for c in range(1,k+1):
        res+=math.gcd(a,c)
print(res)
### BUGGY CODE ###

import sys
import numpy as np

def retmin(a, b):
    if a > b:
        return b
    return a

# N 足場の数、K カエルができる行動
n, k = map(int, input().split())

# H 各足場の高さ
h = list(map(int, input().split()))

# 初期化
dp = np.full(100100, 999999999999)
dp[0] = 0

for i in range(n):
    for j in range(k):
        if (i + j < n):
            dp[i+j] = retmin(dp[i+j], abs(h[i+j]-h[i-1])+dp[i-1])
print(int(dp[n-1]))

### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

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

h = np.array([int(x) for x in input().split()])

# 初期化
dp = np.zeros(n, dtype=int)

for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[n-1])
### BUGGY CODE ###

import heapq

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    score=[[10**10]*W  for i in range(H)]
    score[Sy][Sx] = 0
    heapq.heappush(q,(0,Sx,Sy))
    visited = [[False for j in range(W)] for i in range(H)]

    while q:
        cs,x,y = heapq.heappop(q) 

        if visited[y][x]:
            continue
        visited[y][x]=True


        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:

            score[y-1][x]=score[y][x]
            heapq.heappush(q,(cs,x,y-1))
        if y!=H-1 and MP[y+1][x]=='.' and score[y][x]<score[y+1][x]:


            score[y+1][x]=score[y][x]
            heapq.heappush(q,(cs,x,y+1))
  
        if x!=0 and MP[y][x-1]=='.' and score[y][x]<score[y][x-1]:

            score[y][x-1]=score[y][x]
            heapq.heappush(q,(cs,x-1,y))
        if x!=W-1 and MP[y][x+1]=='.' and score[y][x]<score[y][x+1]:

            score[y][x+1]=score[y][x]
            heapq.heappush(q,(cs,x+1,y))


        for i in range(max(0,y-2),min(H,y+3)):
            for j in range(max(0,x-2),min(W,x+3)):

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(cs+1,j,i))

    if score[Gy][Gx]==10**10:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()


### FIXED CODE ###

from collections import deque

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    mxxx = 10**10
    score=[[mxxx]*W  for i in range(H)]
    score[Sy][Sx] = 0
    deq = deque()
    deq.append((Sy,Sx))
    unvisited=set()
    for y,row in enumerate(MP):
        for x,i in enumerate(row):
            if i ==".":
                unvisited.add((y,x))

    while deq:
        y,x = deq.popleft()
        if not (y,x) in unvisited:
            continue
        unvisited.remove((y,x))

        if (y-1,x) in unvisited and score[y-1][x]>score[y][x]:
            score[y-1][x]=score[y][x]
            deq.appendleft((y-1,x))
        if (y+1,x) in unvisited and score[y+1][x]>score[y][x]:
            score[y+1][x]=score[y][x]
            deq.appendleft((y+1,x))
        if (y,x-1) in unvisited and score[y][x-1]>score[y][x]:
            score[y][x-1]=score[y][x]
            deq.appendleft((y,x-1))
        if (y,x+1) in unvisited and score[y][x+1]>score[y][x]:
            score[y][x+1]=score[y][x]
            deq.appendleft((y,x+1))

        for i in range(y-2,y+3):
            for j in range(x-2,x+3):
                if (i,j) in unvisited and score[i][j] > score[y][x]+1:
                    score[i][j] = score[y][x]+1
                    deq.append((i,j))
    
    if score[Gy][Gx] == 10**10:
        print(-1)
    else:
        print(score[Gy][Gx])




    
resolve()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

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

dp = []
for i in range(N + 1):
    dp.append(None)
dp.append(0)

dp[N] = 1

for i in range(N - 1, -1, -1):
    if i in A:
        dp[i] = 0
        continue
    dp[i] = (dp[i + 1] + dp[i + 2]) % 1000000007

# print('dp', dp)
print(dp[0])


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
s = sys.stdin.readline()
r = []
g = []
b = []
cnt = 0
i = 0
while i < n:
  if s[i] == "R":
    r.append(i)
  elif s[i] == "G":
    g.append(i)
  else:
    b.append(i)
for j in r:
  for k in g:
    for l in b:
      if l - k != k - j:
        cnt += 1
print(cnt)


### FIXED CODE ###

import sys

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))


n = ri()
s = rr()
ans = s.count('R') * s.count('G') * s.count('B')
for i in range(n-2):
    for j in range(i+1, n-1):
        k = j + j - i
        if k < n:
            if s[k] != s[j] and s[j] != s[i] and s[k] != s[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, A, B = MAP()

blues = 0
while N > 0:
    if N - A < 0:
        A = N
    N -= A
    blues += A

    N -= B

print(blues)


### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, A, B = MAP()



sets = N // (A+B) 
remain = N % (A+B)

blues = sets * A + min(remain, A)
print(blues)
### BUGGY CODE ###

s = input()
q = int(input())
query_list = [list(input().split()) for _ in range(q)]
for query in query_list:
    if query[0] == '1':
        s = ''.join(list(reversed(s)))
    elif query[0] == '2':
        if query[1] == '1':
            s = query[2]+s
        elif query[1] == '2':
            s = s + query[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
query_list = [list(input().split()) for _ in range(q)]
reverse_flag = False
concat = ''
initial = 0
for query in query_list:
    if query[0] == '1':
        reverse_flag = not reverse_flag
    elif query[0] == '2':
        if (query[1] == '1' and not reverse_flag) or (query[1] == '2' and reverse_flag):
            concat = query[2] + concat
            initial += 1
        elif (query[1] == '2' and not reverse_flag) or (query[1] == '1' and reverse_flag):
            concat = concat + query[2]
ans = ''
if reverse_flag:
    s = s[::-1]
    concat = concat[::-1]
    ans = concat[:-initial]+s+concat[-initial:]
else:
    ans = concat[:initial]+s+concat[initial:]
print(ans)