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

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(len(a)):
    if a[i]<=min(a[:i+1]):
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt=0
min_num=p[0]
for i in p:
    if i<=min_num:
        min_num=i
        cnt+=1
print(cnt)
### BUGGY CODE ###

N, P = map(int, input().split())
S=input()
dp=[[[0 for _ in range(P)] for _ in range(2)] for _ in range(N)]

dp[0][1][int(S[0])%P]=1
tmp=10%P

#print(dp)
for i in range(N-1):
    c=int(S[i+1])
    #print(c)
    for j in range(P):
        dp[i+1][0][j]=dp[i][0][j]+dp[i][1][j]
        dp[i+1][1][(tmp*j+c)%P]+=dp[i][1][j]
    dp[i+1][1][c%P]+=1
    #print(dp)
print(dp[N-1][0][0]+dp[N-1][1][0])

### FIXED CODE ###

N, P=map(int, input().split())
S=input()

ans=0
if 10%P==0:
    for r in range(N):
        if int(S[r])%P==0:
            ans+=r+1
else:
    d=[0 for _ in range(N+1)] # Pで割った余りの累積和
    ten=1 # 10の何乗か
    for i in range(N-1, -1, -1): # 右から見ていく
        a=int(S[i])*ten%P
        d[i]=(d[i+1]+a)%P
        ten=(ten*10)%P
    cnt=[0 for _ in range(P)]
    for i in range(N, -1, -1):
        ans+=cnt[d[i]]
        cnt[d[i]]+=1
print(ans)
### BUGGY CODE ###

import math

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

_max = 0
for i in range(n + 1):
    val = math.floor((a * i) / b) - (a * math.floor(i / b))
    if _max > 0 and val == 0: break
    _max = max(_max, val)

print(_max)

### FIXED CODE ###

import math

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

k = min(n, b - 1)
print(math.floor(a * k / b) - a * math.floor(k / b))
### BUGGY CODE ###

import re

S = 'S' + input()
new_s = list(S.replace('BC', 'D'))


cnt = 0
i = 1
while i < len(new_s):
    if new_s[i-1] == 'A' and  new_s[i] == 'D':
        cnt += 1
        new_s[i-1] = 'D'
        new_s[i] = 'A'
        i -= 2
    else:
        i += 1
    new_s = list(''.join(new_s).replace('BC', 'D'))

print(cnt)

### FIXED CODE ###

import re

S = 'S' + input()
new_s = list(S.replace('BC', 'D'))


cnt = 0
A = 0
for i in range(len(new_s)):
    if new_s[i] == 'A':
        A += 1
    elif new_s[i] == 'D':
        cnt += A
    else:
        A = 0
print(cnt)
### BUGGY CODE ###

import numpy as np
N,M = map(int,input().split())
A = np.zeros(M,dtype=int)
B = np.zeros(M,dtype=int)
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())

def check_connect(connect,cnt,A,B):
    a = cnt[A]
    b = cnt[B]
    if a == b:
        return connect,0,cnt
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    connect[a] = connect[a] + connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return connect,(tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2,cnt

connect = [[i] for i in range(N)]
cnt = np.arange(N)
dfubensa = np.zeros(M,dtype=int)
for i in range(M-1,-1,-1):
    connect,dfubensa[i],cnt = check_connect(connect,cnt,A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa = fubensa+ dfubensa[i]
    print(fubensa)

### FIXED CODE ###

N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())

def check_connect(A,B):
    a = cnt[A]
    b = cnt[B]
    if a==-1 and b==-1:
        connect.append([A,B])
        cnt[A] = len(connect)-1
        cnt[B] = cnt[A]
        return 1
    if a == b:
        return 0
    if a == -1:
        a,b,A,B = b,a,B,A
    if b==-1:
        connect[a] += [B]
        cnt[B] = a
        return len(connect[a])-1
        
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    if tmp2 > tmp1:
        a,b = b,a
    connect[a] += connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return (tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2

connect = []
cnt = [-1]*N
dfubensa = [0]*M
for i in range(M-1,-1,-1):
    dfubensa[i] = check_connect(A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa += dfubensa[i]
    print(fubensa)
### BUGGY CODE ###

def do():
    s=str(input())
    count=[0]*2019
    ans=0
    for i in range(len(s)):
        count_t=[0]*2019
        count_t[int(s[i])]+=1
        for k in range(2019):
            t=(k*10+int(s[i]))%2019
            count_t[k]-=count[k]
            count_t[t]+=count[k]
            if t==0:
                ans+=count[k]
        #print(count[0:20])
        #print(count_t[0:20])
        count=list(map(lambda x,y: x+y, count, count_t ))
    print(ans)
                
if __name__ == '__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    cnt=[0]*2019
    cnt[0]=1
    temp=0
    keta=1
    ans=0
    for i in s[::-1]:
        temp=(temp+int(i)*keta)%2019
        keta=(keta*10)%2019
        cnt[temp]+=1
    for i in cnt:
        ans+=(i*(i-1))//2
    print(ans)
    
    
if __name__ == '__main__':
    do()
### BUGGY CODE ###

N = int(input())
S = input()
# N桁のSからN-3桁の数字を削除して(N<30000)３桁の数字を残す．残った数字の組み合わせて押してありえるのは何通りか？
# 実際に10^4通りから３通り選ぶのは 10^4C3通りくらい計算量的には計算できる?
# 更にあり得る組み合わせの上限==1000通りを終えた時点で終了すれば更に早い？
# 右の数字から数えていって1を取れるかみたいにしていけば最大１０００のループで終わる？
# 0001がNの中から取れるかの判定まず最初の0について左側からとっていって，0があれば存在すればとり，そこのindexを記録，．次に1として次のindexから検索していく

#for n in N_str:
#なぜ224とかの時に上手く行かないのだ?
#0224
count=0
NUM = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
for i in NUM:
    i_3d = i
    index_num = 0
    for j,i_s in enumerate(i_3d): # 1,2
        S_mid = S[index_num:]
        for s_s in S_mid: # 2 ひょっとして個々がコストが高い??もしかするとここで配列を取り出して新たな配列オブジェクトに入れてみたいな糞めんどくさいことをしてるのかも？？？
            index_num+= 1 #3
            if s_s == i_s: #2 == 2
                if j == len(i_3d)-1:  # 最後の文字がマッチングした
                    count+=1
                break
        # i_sについて探索しても何も見つからなかった場合,最後まで探索したとき，次のindexがあふれる時には停止する
        if index_num == len(S): # 3==4:False
            break
print(count)




### FIXED CODE ###

N = int(input())
S = input()
# N桁のSからN-3桁の数字を削除して(N<30000)３桁の数字を残す．残った数字の組み合わせて押してありえるのは何通りか？
# 実際に10^4通りから３通り選ぶのは 10^4C3通りくらい計算量的には計算できる?
# 更にあり得る組み合わせの上限==1000通りを終えた時点で終了すれば更に早い？
# 右の数字から数えていって1を取れるかみたいにしていけば最大１０００のループで終わる？
# 0001がNの中から取れるかの判定まず最初の0について左側からとっていって，0があれば存在すればとり，そこのindexを記録，．次に1として次のindexから検索していく

#for n in N_str:
#なぜ224とかの時に上手く行かないのだ?
#0224
count=0
NUM = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
for i in NUM:
    i_3d = i
    S_mid = S
    for j,i_s in enumerate(i_3d): # 1,2
        if i_s in S_mid: # S_mid中にi_sがそんざいしていたら
            ind = S_mid.index(i_s)
            if j == len(i_3d)-1:  # 最後の文字がマッチングした
                count+=1
                break # break はforとwhileを抜け出すのに使われる
            elif ind+1 == len(S): # 文字はマッチングしたが最後の文字ではなく次の探索ができない場合
                break
            S_mid = S_mid[ind+1:]
        else: # S_mid中に存在しない
            break
print(count)
### BUGGY CODE ###

import numpy as np

a = np.array([int(c) for c in input().strip()])
m = a % 2019
keta = 1
count = np.count_nonzero(m == 0)
while len(m) > 1:
  m = (10*m[:-1] + a[keta:]) % 2019
  keta += 1
  count += np.count_nonzero(m == 0)
print(count)


### FIXED CODE ###

def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())
### BUGGY CODE ###

from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [10**11]
t=[int(input()) for _ in range(B)] + [10**11]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))


### FIXED CODE ###

from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [10**11]
t=[int(input()) for _ in range(B)] + [10**11]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))
### BUGGY CODE ###

import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0
ab = []

for i in range(N):
    ab.append(iip())

ab= sorted(ab, key=lambda x:x[1])

for i in range(N):
    a, b = ab[i]
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

### FIXED CODE ###

import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]

        for k in range(1, min(a, H) + 1):
            mp_for_damage[k] = min(mp_for_damage[k], b)
            # print(k, b)

        if a >= H:
            mp_for_damage[H] = min(mp_for_damage[H], b)
            continue

        if a < H and mp_for_damage[a] < b:
            continue

        for j in range(H-a+1):
            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()
### BUGGY CODE ###

def main():
    n = int(input())
    numlist = []
    for _ in range(n):
        numlist.append(int(input()))

    maxprofit = numlist[1] - numlist[0]
    for i in range(n-1):
        if maxprofit < max(numlist[i+1:n]) - numlist[i]:
            maxprofit = max(numlist[i+1:n]) - numlist[i]
    print(maxprofit)

if __name__ == '__main__':
    main()



### FIXED CODE ###

n = int(input())
a0 = int(input())
a1 = int(input())
max_profit = a1 - a0
min_i = min(a1, a0)
for i in range(n-2):
    c=int(input())
    if c - min_i > max_profit:
        max_profit = c - min_i
    min_i = min(min_i, c)
print(max_profit)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
k=[[0]*20 for i in range(n)]
for i in range(n):
    for j in range(20):
        k[i][j] = 1 if (a[i] % 2**(j+1)) >= 2**j else 0

l=0
r=0
c20=[0]*20
r0=-1
ans=[0]*n
while l < n:
    if r > r0:
        for _ in range(20):
            c20[_]+=k[r][_]
    else:
        for _ in range(20):
            c20[_]-=k[l-1][_]
    l0=l
    r0=r
    if sum(list(map(lambda x:x>1 ,c20))) == 0:
        ans[l]=max(ans[l],r)
        if r < n-1:
            r+=1
        else:
            l+=1
    else:
        ans[l]=max(ans[l],r-1)
        l+=1
print(sum([ans[i]-i+1 for i in range(n)]))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=0
r=0
now=0
ans=[0]*n
while l < n:
    if r < n and now^a[r] == now + a[r]:
        now += a[r]
        ans[l]=r
        r+=1
    else:
        now -= a[l]
        l+=1
        ans[l-1]=r-1
print(sum([ans[i]-i+1 for i in range(n)]))
### BUGGY CODE ###

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

start = []
goal = []
flag = False

for i in range(m):
    if 1 in a[i]:
        start.append(a[i])
    if n in a[i]:
        goal.append(a[i])

for i in range(len(goal)):
    middle_i = goal[i][0]
    for j in range(len(start)):
        if start[j][1] == middle_i:
            flag = True
            break
    else:
        continue
    break

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

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

ans = []
flag = False

for i in range(m):
    if 1 in a[i]:
        ans.append(a[i][1])
    if n in a[i]:
        ans.append(a[i][0])

if len(set(ans)) != len(ans):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))


R, C, N = rli()
lis = []
idx = 0
i = 0
for j in range(N):
    x1, y1, x2, y2 = rli()
    if((x1 % R == 0 or y1 % C == 0) and (x2 % R == 0 or y2 % C == 0)):
        i += 1
        for _ in range(2):
            if(y1 == 0):
                lis.append([x1, i])
            elif(x1 == R):
                lis.append([R+y1, i])
            elif(y1 == C):
                lis.append([2*R+C-x1, i])
            elif(x1 == 0):
                lis.append([2*R+2*C-y1, i])
            x1 = x2
            y1 = y2
lis.sort()
stack = []
ans = True
for k in range(2*i):
    if(lis[k][1] in stack):
        if(lis[k][1] != stack.pop()):
            ans = False
            break
    else:
        stack.append(lis[k][1])

if(ans):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(input())
def pli(a): return "".join(list(map(str, a)))


R, C, N = rli()
lis = []
idx = 0
i = 0
for j in range(N):
    x1, y1, x2, y2 = rli()
    if((x1 % R == 0 or y1 % C == 0) and (x2 % R == 0 or y2 % C == 0)):
        i += 1
        for _ in range(2):
            if(y1 == 0):
                lis.append([x1, i])
            elif(x1 == R):
                lis.append([R+y1, i])
            elif(y1 == C):
                lis.append([2*R+C-x1, i])
            elif(x1 == 0):
                lis.append([2*R+2*C-y1, i])
            x1 = x2
            y1 = y2
lis.sort()
stack = []
exist = [False for _ in range(2*i)]
ans = True
for k in range(2*i):
    if(exist[lis[k][1]]):
        if(lis[k][1] != stack.pop()):
            ans = False
            break
        exist[lis[k][1]] = False
    else:
        stack.append(lis[k][1])
        exist[lis[k][1]] = True
if(ans):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
arr=[1]*len(inp)
inp.sort()
ans=0
for i in range(len(inp)):
    if arr[i]==0:
        continue
    else:
        if c[inp[i]]==1:
            ans+=1
        for j in range(i+1,len(inp)):
            if inp[j]%inp[i]==0:
                arr[j]=0
print (ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
arr=[1]*(max(inp)+1)
inp.sort()
d=Counter([])
for i in range(len(arr)):
    if c[i]>=1 and arr[i]==1:
        if d[i]==0:
            d[i]+=1
        else:
            continue
        k=2
        while k*i<len(arr):
            arr[k*i]=0
            k+=1
ans=0
for item in d.keys():
    if c[item]==1:
        ans+=1
print (ans)
### BUGGY CODE ###

#input
D = int(input())
c_list = list(map(int, input().split()))

s_grid = []
for i in range(D):
    array = list(map(int, input().strip().split(' ')))
    s_grid.append(array)

t_list = [(i % 26) for i in range(D)] #task_list

def calculate_score(t_list,score_list,last_grid,change_query_number):
    score_list = score_list[:change_query_number]
    last_grid = last_grid[:change_query_number]

    if len(score_list) > 1:
        score = score_list[change_query_number-1]
        last_list = last_grid[change_query_number-1]
    else:
        score = 0
        last_list = [0 for i in range(26)]

    for d in range(change_query_number,D):
        score += s_grid[d][t_list[d]]
        last_list = [n+1 for n in last_list]
        last_list[t_list[d]] = 0
        for i in range(26):
            score -= c_list[i]*last_list[i]
        score_list.append(score)
        last_grid.append(last_list)
    return score_list, last_grid

#first cal.
previous_s, previous_l = calculate_score(t_list,[],[[0 for i in range(26)]],0)
score = previous_s[-1]

if True:
    for k in range(D-1,0,-1):
        X = -1  # k-日目に変える番号を探す
        t_list_loop = t_list
        for i in range(26): #26通り試す
            t_list_loop[k] = i
            score_list_k , last_grid_k = calculate_score(t_list_loop,previous_s,previous_l,k)
            if score_list_k[-1] > score:
                X = i
                score = score_list_k[-1]
                score_list_t = score_list_k
                last_grid_t = last_grid_k

        if X != -1:
            t_list[k] = X
            previous_s = score_list_t
            previous_l = last_grid_t

        #print(k,X,score)
        for j in range(len(t_list)):
            print(int(t_list[j])+1)

### FIXED CODE ###

t_list = [i % 26 for i in range(365)]
for i in range(365):
	print(t_list[i]+1)
### BUGGY CODE ###

N, M, Q = map(int, input().split())

t = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    t[L][R] += 1

for i in range(N + 1):
    for j in range(N):
        t[i][j + 1] += t[i][j]

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
print('\n'.join(str(v) for v in result))


### FIXED CODE ###

N, M, Q = map(int, input().split())

t = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    t[L][R] += 1

for i in range(N + 1):
    for j in range(N):
        t[i][j + 1] += t[i][j]

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
print('\n'.join(str(v) for v in result))
### BUGGY CODE ###

import sys
from collections import Counter
n, *lst = sys.stdin.read().split()
n = int(n)
c = []
for i in lst:
  tmpc = Counter(i)
  tmpc = ''.join(str(tmpc[chr(key)]) if chr(key) in tmpc else str(0) for key in range(97, 124))
  c.append(tmpc)

c = Counter(c)
res = 0
for key in c:
  res += c[key] * (c[key] - 1) // 2
print(res)

### FIXED CODE ###

import sys
from collections import defaultdict

n, *lst = sys.stdin.read().split()
n = int(n)
c = defaultdict(int)
for i in lst:
  tmpi = ''.join(sorted(i))
  c[tmpi] += 1
res = 0
for key in c:
  res += c[key] * (c[key] - 1) // 2
print(res)
### BUGGY CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

A, B = map(int, input().split())
if A > B:
    A, B = B, A
c = gcd(A, B)
ans = 1

for i in range(2, c+1):
    if i > c:
        break
    if c%i == 0:
        ans += 1
        while c%i == 0:
            c = c//i

print(ans)

### FIXED CODE ###

from math import sqrt, ceil

# ユークリッドの互除法で最大公約数を返す
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

A, B = map(int, input().split())
if A > B:
    A, B = B, A
g = gcd(A, B)
s = set(); s.add(1)
sqrt_g_plus = ceil(sqrt(g))+1
i = 2

# 最大公約数の平方根までの素数を見つける
while i < sqrt_g_plus:
    if g%i == 0:
        s.add(i)
        g //= i
    else:
        i += 1
# 平方根以上の素数がある場合、追加する（あるとした場合一つだけである）
if g > 1:
    s.add(g)

print(len(s))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
B=[0]*N
for i in range(N):
  flg=True
  for j in range(i, i+N):
    B[i]+=A[j%N] if flg else (-1)*A[j%N]
    flg=not flg
print(" ".join(str(b) for b in B))

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
B=[0]*N
for i in range(N):
  B[0]+=A[i] if i&1==0 else (-1)*A[i]
for i in range(1, N):
  B[i]=2*A[i-1]-B[i-1]
print(" ".join(str(b) for b in B))
### BUGGY CODE ###

N,M = map(int,input().split())
a = []

for _ in range(M):
  a.append(input())

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if str(n) in a:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = (S[n-1] + S[n-2])%1000000007

print(S[n])

### FIXED CODE ###

N,M = map(int,input().split())
a = [True] * (N+1)

for _ in range(M):
  a[int(input())] = False

S = [0] * (N+1)
S[0] = 1
for n in range(1, N+1):
    if a[n]==False:
        S[n] = 0
    elif n==1:
        S[n] = 1
    else:
        S[n] = (S[n-1] + S[n-2])%1000000007

print(S[n])
### BUGGY CODE ###

from collections import Counter

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

if len(a) == len(set(a)):
    for i in range(n):
        print(0)
else:
    for i in range(n):
        ans = 0
        temp = a[:i] + a[i + 1:]
        for k in [temp.count(x) for x in set(temp)]:
            if k != 1:
                ans += k * (k - 1) // 2

        print(ans)


### FIXED CODE ###

from collections import Counter

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

if len(a) == len(set(a)):
    for i in range(n):
        print(0)
else:
    kw = Counter(a)
    ans = sum([x * (x - 1) // 2 for x in kw.values()])

    for i in range(n):
        print(ans - kw[a[i]] + 1)
### BUGGY CODE ###

s = list(input())
n = len(s)
s.reverse()
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        for j in range(13):
            k = (s1*(10**i))%13
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        for j in range(13):
            for x in range(10):
                k = (x*((10**i)%13))%13
                dp[i][(j+k)%13] += dp[i-1][j]
            dp[i] = [dp[i][j]%(10**9 + 7) for j in range(13)]
print(dp[n-1][5])

### FIXED CODE ###

s = list(input())
n = len(s)
s.reverse()
m = 10**9 + 7
p = 10
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        k = (s1*p)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        for x in range(10):
            k = (x*p)%13
            for j in range(13):
                dp[i][(j+k)%13] += dp[i-1][j]
                dp[i][(j+k)%13] %= m
    p = (p * 10) % 13
print(dp[n-1][5])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
result = 0
max_height = 0

for i in range(n):
  an = a[i]
  if i == 0:
    max_height = an
    continue

  if an >= max_height:
    max_height = an
    continue

  max_height = max(a[0:i])
  result += (max_height - an)

print(result)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split(' ')]
result = 0
max_height = 0

for i in range(n):
  an = a[i]
  if i == 0:
    max_height = an
    max_height_idx = 0
    continue

  if an >= max_height:
    max_height = an
    max_height_idx = i
    continue

  result += (max_height - an)

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

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            d = math.gcd(i,j)
            ans += math.gcd(d,k)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            d = math.gcd(i,j)
            ans += math.gcd(d,k)
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
dic = Counter(list(map(int,input().split())))
rslt = 1
r = 10**9 + 7
if n % 2 == 0:
    if dic != Counter(sum([[i,i] for i in range(1, n, 2)], [])):
        rslt = 0
    else:
        for _ in range(n//2):
            rslt = rslt * 2 % r
else:
    if dic != Counter(abs(i) for i in range(-n+1, n, 2)):
        rslt = 0
    else:
        for _ in range(n//2):
            rslt = rslt * 2 % r
print(rslt)

### FIXED CODE ###

from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
rslt = 0
a = 10 ** 9 + 7
cnt = Counter(ns)
if n % 2 == 0:
    for i in range(1, n, 2):
        if cnt[i] != 2:
            print(0)
            exit()
    rslt = pow(2, n // 2, a)
else:
    for i in range(2, n, 2):
        if cnt[i] != 2:
            print(0)
            exit()
    if cnt[0] == 1:
        rslt = pow(2, n // 2, a)
print(rslt)