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

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

b = []

for i in range(n):
    if i % 2 != n % 2:
        b.insert(0, a[i])
    else:
        b.append(a[i])

for i in range(n):
    print(b[i], end=" ")


### FIXED CODE ###

from collections import deque

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

b = deque()

for i in range(n):
    if i % 2 != n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])

print(" ".join(map(str, b)))
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
l = A.pop(0)
r = A.pop(-1)
while len(A)>0:
  if r<l:
    r+=A.pop(-1)
  else:
    l+=A.pop(0)
print(abs(r-l))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
l = A.pop(0)
idxl = 0
r = A.pop(-1)
idxr = -1

for i in range(n-2):
  if r<l:
    r+=A[idxr]
    idxr -= 1
  else:
    l+=A[idxl]
    idxl += 1
  
print(abs(r-l))
### BUGGY CODE ###

s = str(input())
s += '0'
k = int(input())
result = []
if k > len(s):
    for i in range(1, k+1):
        for j in range(len(s)-i):
            result.append(s[j:j+i])
else:
    for i in range(len(s)):
        for j in range(i+1, len(s)):
            result.append(s[i:j])
r = set(result)
out = list(r)
out.sort()

print(out[k-1])

### FIXED CODE ###

def main():
    s = str(input())
    s += '0'
    k = int(input())
    result = set()
    for i in range(1, 6):
        for j in range(len(s)-i):
            result.add(s[j:j+i])
    out = list(result)
    out.sort()
    print(out[k-1])
if __name__ =='__main__':
    main()
### BUGGY CODE ###

from collections import deque

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort(key = lambda x:x[0])
xh = deque(xh)

cnt = 0
while xh:
    x, h = xh.popleft()
    if h < 1:
        continue
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    cnt += atk_cnt
    for i in range(len(xh)):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= a * atk_cnt

print(cnt)

### FIXED CODE ###

import math
from collections import deque

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
xh = deque(xh)

xh_field = deque()

cnt = 0
now_damage = 0
while xh:
    pos, hp = xh.popleft()
    if xh_field:
        while (xh_field and xh_field[0][0] < pos) :
            now_damage -= a * xh_field[0][1]
            xh_field.popleft() 
    if hp <= now_damage:
        pass
    elif hp > now_damage:
        atk_cnt = math.ceil((hp - now_damage) / a)
        cnt += atk_cnt
        now_damage += atk_cnt * a
        xh_field.append((2*d + pos, atk_cnt))        
print(cnt)
### BUGGY CODE ###

n=int(input())
ans=0
hoge=list(map(int,input().split()))
for i in range(n):
  if(hoge.count(hoge[i]-1)+hoge.count(hoge[i])+hoge.count(hoge[i]+1)>=ans):
    ans=hoge.count(hoge[i]-1)+hoge.count(hoge[i])+hoge.count(hoge[i]+1)
print(ans)

### FIXED CODE ###

n=int(input())
hoge=list(map(int,input().split()))
huga=[0]*(10**5+1)
for i in hoge:
  if(i==10**5):
    huga[i-1]+=1
    huga[i]+=1
  elif(i==0):
    huga[i]+=1
    huga[i+1]+=1
  else:
    huga[i-1]+=1
    huga[i]+=1
    huga[i+1]+=1
print(max(huga))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
S.append(0)
List = []
tmp_input = []
count = 0
for i in range(Q):
    tmp_input = input().split()
    List.append(tmp_input)

for i in range(Q):
    count = 0
    tmp_x = int(List[i][0])
    tmp_y = int(List[i][1])
    tmp_List = S[tmp_x-1:tmp_y]
    tmp_List.append(0)
    for j in range(len(tmp_List)-1):
        if (tmp_List[j] == 'A') & (tmp_List[j+1] == 'C') ==True:
            count += 1
    print(count)




### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())
S.append(0)
par = [0]*(N+1)#par[0]は無視
Ans = []
for i in range(N):
        par [i+1]=par[i]+(1 if (S[i]=='A') & (S[i+1]=='C') else 0)
for i in range(Q):
        x,y = map(int,input().split())
        print(par[y-1]-par[x-1])
### BUGGY CODE ###

from collections import deque
from sys import stdin


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    As = [int(x) for x in stdin.readline().rstrip().split()]
    pos = 1
    tmp = deque([pos])
    for _ in range(K):
        pos = As[pos - 1]
        if pos in tmp:
            idx_s = tmp.index(pos)
            break
        tmp.append(pos)
    else:
        print(list(tmp)[-1])
        return

    K = K - idx_s
    tmp = list(tmp)
    print(tmp[idx_s:][K % (len(tmp) - idx_s)])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
from sys import stdin


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    As = [int(x) for x in stdin.readline().rstrip().split()]
    pos = 1
    a = [False] * N
    a[0] = True
    tmp = deque([pos])
    for _ in range(K):
        pos = As[pos - 1]
        if a[pos - 1]:
            idx_s = tmp.index(pos)
            break
        a[pos - 1] = True
        tmp.append(pos)
    else:
        print(list(tmp)[-1])
        return

    K = K - idx_s
    tmp = list(tmp)
    print(tmp[idx_s:][K % (len(tmp) - idx_s)])


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

import sys
input = sys.stdin.readline

n = int(input())

a = []
for i in range(n):
  v = list(map(int, input().split()))
  a.append(v)

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

N = int(input())
a = list(map(int,(input().split())))
X = sum(a)
A = X-a[0]*2
for i in range(N-1):
  B = X -sum(a[0:i+1])*2
  if abs(B) < abs(A):
    A = B
print(abs(A))

         


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
total = sum(A)
snk = A[0]
ari = total - snk
ans = abs(snk - ari)
for i in range(1,N-1):
  snk += A[i]
  ari -= A[i]
  ans = min(ans,abs(snk - ari))

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

n = int(input())
a = list(map(int, input().split()))
sum_rain = sum(a) // 2
a += a
ans_rain = []

for i in range(n):
    rest_rain = 0
    for j in range(i + 1, i + n, 2):
        rest_rain += a[j]
    ans_rain.append((sum_rain - rest_rain) * 2)

print(*ans_rain)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sum_rain = sum(a) // 2

rest_rain = 0
for i in range(1, n, 2):
    rest_rain += a[i]
first_ans = (sum_rain - rest_rain) * 2

res = []

res.append(first_ans)
prev_ans = first_ans

for i in range(n - 1):
    ans = (a[i] - prev_ans // 2) * 2
    res.append(ans)
    prev_ans = ans

print(*res)
### BUGGY CODE ###

n, m = map(int, input().split())
bridge = list()

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

def find_group(groups, a):
    for i in range(0, len(groups)):
        g = groups[i]
        if a in g:
            return i
    return -1


while len(bridge) > 0:
    bridge = bridge[1:]
    groups = []
    for i in range(0, n):
        groups.append(i)
    for b in bridge:
        a1 = groups[b[0]]
        a2 = groups[b[1]]
        if a1 == a2:
            continue
        if a1 < a2:
            groups[b[0]] = a1
            groups[b[1]] = a1
            for i, g in enumerate(groups):
                if g == a2:
                    groups[i] = a1
        else:
            groups[b[0]] = a2
            groups[b[1]] = a2
            for i, g in enumerate(groups):
                if g == a1:
                    groups[i] = a2
    counts = list()
    for i in range(0, len(groups)):
        counts.append(0)
    for g in groups:
        counts[g] += 1
    
    count = 0
    for i in range(0, len(counts) - 1):
        for j in range(i + 1, len(counts)):
            count += counts[i] * counts[j]
    print(count)

### FIXED CODE ###

n, m = map(int, input().split())
bridge = list()

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

bridge = bridge[1:]
bridge = reversed(bridge)
result = []


parent = [-1] * n
size = [1] * n
def root(v):
    p = parent[v]
    if p >= 0:
        return root(p)
    return v

value = n * (n - 1) // 2
result.append(value)

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    p0 = root(b[0])
    p1 = root(b[1])
    if p0 == p1:
        result.append(value)
        continue
    s0 = size[p0]
    s1 = size[p1]
    if p0 < p1:
        parent[p1] = p0
        size[p0] += size[p1]
    else:
        parent[p0] = p1
        size[p1] += size[p0]
    value -= s0 * s1
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)
### BUGGY CODE ###


import sys,fractions
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

gcd = gcd_list(l)
L = [l[i]//gcd for i in range(N)]
lcm = lcm_list(L)

# print(lcm,gcd,'aaa')
ANS = 0
for i in range(N):
    elm = L[i]
    ANS += (lcm//elm)
    ANS %= u
print(ANS)

### FIXED CODE ###

import sys
from fractions import gcd
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

lcm = 1
s = 0
for i in range(N):
    k = l[i]
    g = gcd(k,lcm)
    t = k//g
    lcm = lcm*t
    s = s*t + lcm//k
print(s%u)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = input().split()
for k in range(N):
  A_ = A.copy()
  del A_[k]
  dic = set(A_)
  ans = 0
  for i in dic:
    tmp = A_.count(i)
    if tmp == 1:
      continue
    ans += int(tmp * (tmp - 1) / 2)

  print('{}'.format(ans))

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))

dict = {}
for i in range(N):
  if A[i] in dict.keys():
    dict[A[i]] += 1
  else:
    dict[A[i]] = 1

def comb(n):
  if n<2:
    return 0
  return int(n * (n - 1) / 2)

# all
ret = 0
for key in dict.keys():
  val = dict[key]
  ret += comb(val)

# i >= 0
for i in range(N):
  val_n = dict[A[i]]
  next_ret = ret - comb(val_n) + comb(val_n - 1)
  print(next_ret)
### BUGGY CODE ###

K=int(input())
S=input()
mod=10**9+7

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


LEN=len(S)
ANS=0
for i in range(K+1):
    ANS+=Combi(i+LEN-1,LEN-1)*pow(25,i,mod)*pow(26,K-i,mod)
print(ANS%mod)

### FIXED CODE ###

K=int(input())
S=input()
mod=10**9+7

FACT=[1]
for i in range(1,2*10**6+3):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6+2,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


LEN=len(S)
ANS=0
for i in range(K+1):
    ANS+=Combi(i+LEN-1,LEN-1)*pow(25,i,mod)*pow(26,K-i,mod)
print(ANS%mod)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
que = deque()
data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que = next

print(count - 1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
que = deque()
data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que = next

print(count - 1)
### BUGGY CODE ###

(_, M) = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()
for i in range(M):
  A[A.index(max(A[:i+1]), 0, i+1)] //= 2
print(sum(A))

### FIXED CODE ###

from heapq import heappush, heappop
def main():
	(N, M) = map(int, input().split())
	hq =  list(map(lambda x:-x, map(int, input().split())))
	hq.sort()
	for i in range(M):
		b = - heappop(hq) // 2
		heappush(hq, -b)
	print(-sum(hq))
main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n = int(input())

MOD = 998244353
MAX_N = n 

fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
fn = 1
finv = 1
p2 = 1
for i in range(1, MAX_N+1):
    fn *= i
    fn %= MOD

    finv *= pow(i, MOD-2, MOD)
    finv %= MOD
    fac_inv[i] = finv
    p2 *= 2
    p2 %= MOD
    mod_pow2_n[i] = p2

ans = 0
for i in range(n//2+1, n+1):
    ans += (fn * fac_inv[n-i]) % MOD * (fac_inv[i] * mod_pow2_n[n-i]) % MOD
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)
### BUGGY CODE ###

N, x, y = map(int, input().split())
x -= 1
y -= 1

for n in range(1,N):
  ans = 0
  for i in range(N-1):
    for j in range(i+1,N):
      if n == min([abs(j-i), abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x)]):
        ans += 1
  print(ans)

### FIXED CODE ###

N, x, y = map(int, input().split())
x -= 1
y -= 1
dist = [0] * (N)

for i in range(N-1):
  for j in range(i+1,N):
    d = min([abs(j-i), abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x)])
    dist[d] += 1

for i in range(1,N):
  print(dist[i])
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
grid=None
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(max(p-1,0))

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

def solve():
  n = int(input())
  query = []
  query2 = []
  ans = [0]*n
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans[tmp-1] = c[i]
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

  print(sum(ans)-max(ans))
  print(*ans)
  
solve()
### BUGGY CODE ###

s = list(input())
q = int(input())
t = [list(map(str,input().split())) for _ in range(q)]

for i in range(q):
  if len(t[i]) == 1:
    s = s[::-1]
  else:
    if t[i][1] == '1':
      s = list(t[i][2]) + s
    else:
      s = s + list(t[i][2])
      
print(''.join(s))

### FIXED CODE ###

from collections import deque

s = list(input())
q = int(input())
t = [list(map(str,input().split())) for _ in range(q)]

d = deque(s)

cnt = 0
for i in range(q):
  if len(t[i]) == 1:
    cnt += 1
  else:
    if (int(t[i][1])+cnt) % 2 != 0:
      d.appendleft(t[i][2])
    else:
      d.append(t[i][2])
      
if cnt%2 != 0:
  d = list(d)[::-1]
print(''.join(d))
### BUGGY CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = [int(input()) for _ in range(M)] 
dp[-2] = 1

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

print(dp[0])

### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

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

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

n,m=map(int,input().split())
a=[]
p,q,r=1,0,0
for i in range(m):
  a.append(int(input()))
for i in range(1,n+1):
  s,r,q=r,q,p
  if i in a:
    p=0
  else:
    p=(q+r)%(10**9+7)
print(p%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=0
cnt=1
p,q,r=1,0,0
#print(cnt,p)
for i in range(m):
  a=int(input())
  while cnt<n and cnt<a:
      s,r,q=r,q,p
      p=(q+r)%(10**9+7)
      cnt+=1
      #print(cnt,p)
  if a==cnt:
    s,r,q=r,q,p
    p=0
    cnt+=1
    #print(cnt,p)
    
while cnt<=n:
    s,r,q=r,q,p
    p=(q+r)%(10**9+7)
    cnt+=1
    #print(cnt,p)
print(p%(10**9+7))
### BUGGY CODE ###

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

### FIXED CODE ###

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

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
#print(l)
for i in range(m):
    n=1
    for j in range(m):
        if l[i][0]==l[j][0] and l[i][1]>l[j][1]:
            n+=1
    print(str('%06d'%l[i][0])+str('%06d'%n))

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=[]
for i in enumerate(l):
    s.append(i)
s=sorted(s,key=lambda x:(x[1][0],x[1][1]))
#print(s)
a=1
for i in range(m):
    if i==0:
        s[0][1][1]=1
    elif s[i][1][0]==s[i-1][1][0]:
        a+=1
        s[i][1][1]=a
    elif s[i][1][0]!=s[i-1][1][0]:
        a=1
        s[i][1][1]=a
#print(s)
s=sorted(s,key=lambda x:x[0])
#print(s)
for i in s:
    print('%06d'%i[1][0]+'%06d'%i[1][1])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

# ACの位置を記憶
ac_pos = []
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac_pos.append(i+1) # 1-index

for i in range(q):
    count = 0
    for j in ac_pos:
        if lr[i][0] <= j < lr[i][1]:
            count += 1
    print(count)        

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

# 0-index
for i in range(q):
    for j in range(2):
        lr[i][j] -= 1

# 'AC'のカウントの累積和
ac_cnt = [0 for i in range(n)]
for i in range(n-1):
    ac_cnt[i+1] = ac_cnt[i] + (1 if s[i:i+2] == 'AC' else 0)

for i in range(q):
    print(ac_cnt[lr[i][1]] - ac_cnt[lr[i][0]])