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

N=int(input())
A=list(map(int,input().split()))
L=[]
for i in range(N):
    L.append([A[i],i])
#print(L)
ans=0
import copy
from collections import deque
for i in range(1,N):
    cnt=0
    a=copy.deepcopy(L[:i])
    b=copy.deepcopy(L[i:])
    #print(a,b)
    a.sort(reverse=True)
    b.sort(reverse=True)
    #print("ab",a,b)
    A=deque([N-len(a)+j for j in range(len(a)) ])
    B=deque([j for j in range(len(b))])
    #print(A)
    #print(B)
    for j in range(len(a)):
        if abs(a[j][0]*(a[j][1]-A[0]))>abs(a[j][0]*(a[j][1]-A[-1])):
            cnt+=abs(a[j][0]*(a[j][1]-A[0]))
            A.popleft()
        else:
            cnt+=abs(a[j][0]*(a[j][1]-A[-1]))
            A.pop()
    #print("A",cnt)
    for j in range(len(b)):
        if abs(b[j][0]*(b[j][1]-B[0]))>abs(b[j][0]*(b[j][1]-B[-1])):
            cnt+=abs(b[j][0]*(b[j][1]-B[0]))
            B.popleft()
        else:
            cnt+=abs(b[j][0]*(b[j][1]-B[-1]))
            B.pop()
    #print(cnt)
    if ans<cnt:
        ans=cnt
print(ans)


### FIXED CODE ###

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

L=[[10**10,0]]
for i in range(N):
    L.append([A[i],i])
L.sort(reverse=True)
#print(L)
DP=[[0 for i in range(N+1)]for j in range(N+1)]
#j=右に押し込んだ数
for i in range(1,N+1):
    for j in range(i+1):
        if j==0:
            DP[i][j]=DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1))
            #print(DP,DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1)))
        elif j==i:
            DP[i][j]=DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j))
            #print(DP,DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
        else:
            DP[i][j]=max(DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
            #print(DP,DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
print(max(DP[-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W, D = map(int, input().split())

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

Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
    
# H*Wのマスをマスの数値をkeyにした辞書にする
A_dict = {}
for i, sub_a in enumerate(A):
    for j, a in enumerate(sub_a):
        A_dict[a] = (i+1, j+1)
#print(A_dict)
    
def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

N = H*W+1
graph = [[float("inf") for i in range(N)] for i in range(N)] 
edges = []

for i in range(1, N):
    s = i
    g = i+D
    if g >= N:
        break
    cost = abs(A_dict[s][0]-A_dict[g][0])+abs(A_dict[s][1]-A_dict[g][1])
    edges.append((s,g,cost))

for x,y,z in edges:
    graph[x][y] = z
for i in range(N):
    graph[i][i] = 0 #自身のところに行くコストは０
shortest = warshall_floyd(graph, N)

for l, r in LR:
    print(shortest[l][r])

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W, D = map(int, input().split())

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

Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
# H*Wのマスをマスの数値をkeyにした辞書にする
A_dict = {}
for i, sub_a in enumerate(A):
    for j, a in enumerate(sub_a):
        A_dict[a] = (i+1, j+1)

# costの辞書化
from collections import defaultdict
cost_dict = defaultdict(lambda: {})
N = H*W+1
for i in range(1, N):
    s = i
    g = i+D
    if g >= N:
        break
    cost = abs(A_dict[s][0]-A_dict[g][0])+abs(A_dict[s][1]-A_dict[g][1])
    cost_dict[s][g] = cost
    

dist = defaultdict(lambda: {})
for i in range(1, D+1):
    dist[i][i] = 0
    s = i
    g = i+D
    while g < N:
        dist[i][g] = dist[i][s] + cost_dict[s][g]
        s = g
        g = s + D

    
#print(dist)
for l, r in LR:
    idx = r%D
    if idx == 0:
        idx = D
    print(dist[idx][r]-dist[idx][l])
### BUGGY CODE ###

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

ss = []
cnt = 0
for i in range(N):
    x = "".join(sorted(list(s[i])))
    if x in ss:
        cnt += ss.count(x)
    ss.append(x)

print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
 
ctr = Counter()
ans = 0
for s in S:
    a = ''.join(sorted(list(s)))
    if a in ctr:
        ans += ctr[a]
    ctr[a] += 1
print(ans)
### BUGGY CODE ###

import fractions
A,B=map(int,input().split())

li=[]
count=1

for i in range(2,fractions.gcd(A,B)+1):
    judge=True
    if A%i==0 and B%i==0:
        for l in li:
            if i%l==0:
                judge=False
        if judge==True:
            li.append(i)

print(len(li)+1)
    

### FIXED CODE ###

import fractions
A,B=map(int,input().split())

base=fractions.gcd(A,B)
count=1


for i in range(2,int(pow(base,1/2)+1)):
    if base==1:
        break
    else:
        if base%i==0:
            count+=1
            while base%i==0:
                base//=i
if base!=1:
    count+=1
print(count)
### BUGGY CODE ###

from scipy.misc import comb

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

upper = 0
lower = 0
for i in range(N - K + 1):
    c = comb(K + i - 1, i, exact=True)
    upper = (upper + (As[K + i - 1] * c)) % (10 ** 9 + 7)
    lower = (lower + (As[N - K - i] * c)) % (10 ** 9 + 7)
print(((upper - lower) % (10 ** 9 + 7) + 10 ** 9 + 7) % (10 ** 9 + 7))

### FIXED CODE ###

# from scipy.misc import comb

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

mod = 10**9+7 #出力の制限
# N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

upper = 0
lower = 0
for i in range(N - K + 1):
    # c = comb(K + i - 1, i, exact=True)
    c = cmb(K + i - 1, i, mod)
    upper = (upper + (As[K + i - 1] * c)) % (10 ** 9 + 7)
    lower = (lower + (As[N - K - i] * c)) % (10 ** 9 + 7)
print(((upper - lower) % (10 ** 9 + 7) + 10 ** 9 + 7) % (10 ** 9 + 7))
### BUGGY CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    kitai = [0]*n

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n - k + 1):
        count = 0
        for w in range(i , i + k):
            count += kitai[w]

        ans = max(ans , count)

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    count = 0
    kitai = [0]*n
    kitaisum = [0]*n
    mod = 10**9+7

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n):
        if i == 0:
            kitaisum[i] += kitai[i]
        else:
            kitaisum[i] += kitai[i] + kitaisum[i-1]

    for i in range(n - k + 1):

        ans = max(ans , (kitaisum[i + k - 1] - kitaisum[i-1]) if i != 0 else kitaisum[i + k - 1])

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

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

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

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    for k in range(j,N):
        if j - i == k - j:
          if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1

print(ans)


### FIXED CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

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

l, r = map(int, input().split())
ans = []

if l - r < 2019:
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            ans.append((i * j) % 2019)
    print(min(ans))
else:
    print(0)

### FIXED CODE ###

l, r = map(int, input().split())
ans = []

if r - l < 2019:
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            ans.append((i * j) % 2019)
    print(min(ans))
else:
    print(0)
### BUGGY CODE ###

a,b,x = map(int, input().split())
ans = 0
for i in range(a, b+1):
    if i%x == 0:
        ans +=1
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

import math

def main(): 

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

    max_value = max(a)
    max_list = [i for i, x in enumerate(a) if x == max_value]
    
    a.pop(max_list[0])
    second_max = max(a)

    for i in range(n):
        if i not in max_list:
            print(max_value)
        else:
            print(second_max)




if __name__ == "__main__":
    main() 

### FIXED CODE ###


def main(): 

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

    max_v = 0
    max_sv = 0

    for i in range(n):
        if a[i] > max_v:
            max_sv = max_v
            max_v = a[i]
        elif a[i] > max_sv:
            max_sv = a[i]

    for i in range(n):
        if a[i] != max_v:
            print(max_v)
        else:
            print(max_sv)




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

import sys
input = sys.stdin.readline
import itertools
import bisect

def main():
    N = int(input())
    L = [int(x) for x in input().split()]
    ans = 0
    L_sorted = sorted(L)
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            a = L_sorted[i]
            b = L_sorted[j]
            l = bisect.bisect_left(L_sorted, max(a - b, b - a), lo=j + 1)
            r = bisect.bisect_left(L_sorted, a + b, lo=j + 1)
            ans += r - l

    print(ans)



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools
import bisect

def main():
    N = int(input())
    L = [int(x) for x in input().split()]
    ans = 0
    L_sorted = sorted(L)
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            a = L_sorted[i]
            b = L_sorted[j]
            l = bisect.bisect_left(L_sorted, max(a - b, b - a), lo=j + 1)
            r = bisect.bisect_left(L_sorted, a + b, lo=j + 1)
            ans += r - l

    print(ans)



    

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

import sys
from fractions import Fraction
from math import factorial

rl = sys.stdin.readline


def solve():
    N = int(rl())
    x = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    acc = [Fraction(0)] * N
    for i in range(1, N):
        acc[i] = acc[i - 1] + Fraction(1, i)
    
    ans = 0
    for i in range(N - 1):
        ans = ans + (x[i + 1] - x[i]) * acc[i + 1] % MOD
    
    ans = int(ans * factorial(N - 1) % MOD)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
from math import factorial

rl = sys.stdin.readline


def mod_div(x, y, mod=10 ** 9 + 7):
    return x * pow(y, mod - 2, mod) % mod


def solve():
    N = int(rl())
    x = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    acc = [0] * N
    k = factorial(N - 1)
    for i in range(1, N):
        acc[i] = (acc[i - 1] + k) % MOD
        k = k * mod_div(i, i + 1) % MOD
    
    ans = 0
    for i in range(N - 1):
        ans = (ans + (x[i + 1] - x[i]) * acc[i + 1]) % MOD
    print(ans)


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

import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = 10**9
def score(point = 0, n = 0, now=0, done=[]):
    global m
    donecp = copy.deepcopy(done)
    if point >= g:
        if m > n: m = n
    else:
        pointcp = point
        ncp = n
        for i in range(1,P[now]+1):
            pointcp += 100*(now+1)
            ncp += 1
            if pointcp >= g:
                if m > ncp:
                    m = ncp
                break
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

n, k = map(int,input().split())
li = list(int(input()) for i in range(n))

li.sort()
num = 0
li2,li3 = [],[]
for i in range(len(li)-k+1):
    li2.append(li[i:i+k])

for i in range(len(li2)):
    li3.append(max(li2[i]) - min(li2[i]))
print(min(li3))

### FIXED CODE ###

n, k = map(int,input().split())
li = list(int(input()) for i in range(n))

li.sort()
num = 0
li2 = []
for i in range(len(li)-k+1):
    li2.append(li[i+k-1] - li[i])

print(min(li2))
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    V = {}

    for i in range(N):
        w, v = map(int, input().split())

        # 重さ j+w での最大価値
        X = {}
        for j in V.keys():
            if j+w <= W:
                X[j+w] = max(V.get(j+w, 0), V.get(j, 0) + v)

        for k in X.keys():
            V[k] = X[k]

        # 重さ w での最大価値 (単体での最大価値)
        if w <= W:
            V[w] = max(V.get(w, 0), v)

    print(max(V.values()))


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


### FIXED CODE ###

def solve(N,W,wv):
    dp=[-1]*(W+1)
    dp[0]=0
    for i in range(N):
        cur_w=wv[i][0]
        cur_v=wv[i][1]
        for j in range(W-cur_w,-1,-1):
            if dp[j]==-1:
                continue
            if dp[j+cur_w]<dp[j]+cur_v:
                dp[j+cur_w]=dp[j]+cur_v
    return max(dp)


N,W=map(int,input().split())
wv=tuple(tuple(map(int,input().split())) for _ in range(N))
print(solve(N,W,wv))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
A = [int(i) for i in input().split()]

def f(i,j):
  a = 0
  if not 2*j-1 <= i <= 2*j+1+(N-2*int(N/2)):
    a = 0
  elif i == 1 and j == 0:
    a = 0
  elif i == 1 and j == 1:
    a = A[0]
  elif i == 2 and j == 1:
    a = max(A[0],A[1])
  elif i == 2 and j == 0:
    a = 0
  else:
    a = max(f(i-2,j-1)+A[i-1],f(i-1,j))
  return a

print(f(N,int(N/2)))

### FIXED CODE ###

import math

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

B = [{} for _ in range(N+1)]


for i in range(1,N+1):
  if i == 1:
    B[1][0] = 0
    B[1][1] = A[0]
  elif i == 2:
    B[2][1] = max(A[0],A[1])
    if N % 2 == 1:
      B[2][0] = 0
  else:
    if N % 2 == 0:
      for j in range(math.ceil((i-1)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else -float('inf')
        m2 = B[i-1][j] if j in B[i-1] else -float('inf')
        B[i][j] = max(m1,m2)
    else:
      for j in range(math.ceil((i-2)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else -float('inf')
        m2 = B[i-1][j] if j in B[i-1] else -float('inf')
        B[i][j] = max(m1,m2)
      

print(B[N][N//2])
### BUGGY CODE ###

from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
INF = float("inf")
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

done = [[0] * w for _ in range(h)]
done[0][0] = 1

que = deque([(0, 0)])

dist = 0 
flag = False
while que:
    dist += 1

    for i in range(len(que)):
        x, y = que.popleft()
        if x == w-1 and y == h-1:
            flag = True
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and done[ny][nx] == 0 and field[ny][nx] == ".":
                que.append((nx, ny))
                done[ny][nx] == 1
    if flag:
        break

if not flag:
    print(-1)
    exit()

white_num = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == ".":
            white_num += 1
print(white_num-dist)





### FIXED CODE ###

from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
nokoshi = 1
que = deque([(0, 0)])
done = [[False] * w for _ in range(h)]

white_num = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == ".":
            white_num += 1

while que:
    for i in range(len(que)):
        y, x = que.popleft()

        if y == h - 1 and x == w - 1:
            print(white_num - nokoshi)
            exit()

        if y < 0 or y >= h or x < 0 or x >= w or field[y][x] == "#" or done[y][x] is True:
            continue
        done[y][x] = True

        for dy, dx in directions:
            que.append((y+dy, x+dx))

    nokoshi += 1
print(-1)
### BUGGY CODE ###

S = input()
N = int(S.split(' ')[0])
A = int(S.split(' ')[1])
B = int(S.split(' ')[2])
 
b_count = 0
for i in range(0, N):
  if i % (A+B) < A:
    b_count = b_count + 1
print(b_count)

### FIXED CODE ###

S = input()
N = int(S.split(' ')[0])
A = int(S.split(' ')[1])
B = int(S.split(' ')[2])
 
b_count = (N // (A+B)) * A
rem = N % (A+B)
b_count = b_count + min(rem, A)
print(b_count)
### BUGGY CODE ###

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

if x < min(A):
    print(0)
    exit()

A.sort()
ans = 0
i = 0
while x > 0 and ans < N:
    if x >= A[i]:
        x -= A[i]
        ans += 1
        i += 1

if x > 0:
    ans -= 1

print(ans)


### FIXED CODE ###

n, x = map(int,input().split())
li = list(map(int,input().split()))

li.sort()
ans = 0

for i in range(n):
    x = x-li[i]
    if x < 0:
        ans = i
        break
    ans = i+1

if x > 0:
    ans -=1

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

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

pts = [K - Q]*N
for ai in A:
    for i, _ in enumerate(pts):
        if (i+1)==ai:
            pts[i] += 1

for p in pts:
    if p>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = []
for _ in range(Q):
    A.append(int(input()))
    
pts = [K - Q]*N
for ai in A:
    pts[ai-1] += 1

for p in pts:
    if p>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
ab = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

MOD = 10**9+7


def dfs(v, pv, n):
    k = K-1 if pv == -1 else K-2
    a = 1
    for u in ab[v]:
        if u != pv:
            a *= dfs(u, v, k)
            a %= MOD
            k -= 1
    return a*n % MOD


print(dfs(0, -1, K))


### FIXED CODE ###

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
ab = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

MOD = 10**9+7


def dfs(v, pv, n):
    k = K-1 if pv == -1 else K-2
    a = 1
    for u in ab[v]:
        if u != pv:
            a *= dfs(u, v, k)
            a %= MOD
            k -= 1
    return a*n % MOD


print(dfs(0, -1, K))
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for j in range(2,n+1):
    if j not in a:
        step[j] = step[j-1] + step[j-2]
print(step[n] % 1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,n+1):
    if i in a:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])
### BUGGY CODE ###

import sys

maxnum = 50000
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    cnt = 0
    for i in xrange(2,int(d/2+1)):
        if primes[i] and primes[d-i]: cnt += 1
    print cnt

### FIXED CODE ###

from itertools import *
import sys

maxnum = 50001
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

p = [ i for i in xrange(maxnum) if primes[i] ]
c = [0]*maxnum*2
for i,j in combinations_with_replacement(p,2):
    c[i+j] += 1

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    print c[d]
### BUGGY CODE ###

X=input()
pre="a"
while True:
    X=X.replace("ST","")
    if pre==X:
        break
    else:
        pre=X

print(len(X))


### FIXED CODE ###

X=list(input())
N=len(X)
count=0

for x in X:
    if x=="S":
        count+=1
    else:
        if count>0:
            count-=1
            N-=2
print(N)
### BUGGY CODE ###

n = int(input())
s = str(input())

check = dict()
def get_pattern2(i, j):
    a = s[i]
    b = s[j]
    total = 0
    check_str = ""
    if a == "R" or b == "R":
        check_str += "R"
    if a == "G" or b == "G":
        check_str += "G"
    if a == "B" or b == "B":
        check_str += "B"

    center = j - i
    if n < j + 1 + center:
        center = 0

    for k in range(j+1+center, n):
        if check_str+str(k) in check:
            total += check[check_str+str(k)]
            break
        if a != s[k] and b != s[k]:
            total += 1
    check[check_str+str(j+1+center)] = total

    for k in range(j+1, j+center):
        if a != s[k] and b != s[k]:
            total += 1
    return total

def get_pattern(i):
    a = s[i]
    total = 0
    for j in range(i+1, n):
        center = j - i
        if n < j + 1 + center:
            if a+str(i) in check:
                total += check[a+str(i)]
                break
        if a != s[j]:
            total += get_pattern2(i, j)
    check[a+str(i)] = total
    return total

total = 0
for i in range(n-1, -1, -1):
    total += get_pattern(i)
print(total)


### FIXED CODE ###

n = int(input())
s = str(input())

check = dict()
def get_pattern2(i, j):
    a = s[i]
    b = s[j]
    total = 0
    check_str = ""
    if a == "R" or b == "R":
        check_str += "R"
    if a == "G" or b == "G":
        check_str += "G"
    if a == "B" or b == "B":
        check_str += "B"

    for k in range(j+1, n):
        if check_str+str(k) in check:
            total += check[check_str+str(k)]
            break
        if a != s[k] and b != s[k]:
            total += 1
    check[check_str+str(j+1)] = total
    return total

def get_pattern(i):
    a = s[i]
    total = 0
    for j in range(i+1, n):
        if a+str(j) in check:
            total += check[a+str(j)]
            break
        if a != s[j]:
            total += get_pattern2(i, j)
    check[a+str(i+1)] = total

    # k-j = i-jなものをぬく
    for j in range(i+1, n):
        k = j + j - i
        if k >= n:
            break
        if a != s[k] and s[j] != s[k] and a != s[j]:
            total -= 1
    return total

total = 0
for i in range(n-1, -1, -1):
    total += get_pattern(i)
print(total)