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

import sys
import collections
rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] = 1
    deg = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while deg:
        i = deg.popleft()
        for j in li[i]:
            dpj = dp[j]
            dpi = dp[i]
            if dpj < dpi + 1:
                dp[j] = dpi + 1
            deg.appendleft(j)
    print(max(dp))
a()




        




### FIXED CODE ###

import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

def a():
    N, M = map(int, rl().split())
    li = [[] for _ in range(N)]
    deg = [0] * N
    for _ in range(M):
        a, b = map(int, rl().split())
        a -= 1
        b -= 1
        li[a].append(b)
        deg[b] += 1
    d = collections.deque([i for i in range(N) if deg[i] == 0])
    dp = [0] * N
    while d:
        i = d.popleft()
        for j in li[i]:
            deg[j] -= 1
            if deg[j] == 0:
                dp[j] = max(dp[j] ,dp[i] + 1)
                d.append(j)
    print(max(dp))
a()
### BUGGY CODE ###


import collections as c

n = int(input())

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

q = int(input())

s = sum(a)

cnt = [0]*100000

for i in range(100000):
    cnt[i] = a.count(i+1)

for i in range(q):
    b,c = map(int,input().split())
    x = cnt[b-1]
    cnt[b-1] = 0
    cnt[c-1] = cnt[c-1] + x
    s += (c-b)*x
    print(s)

### FIXED CODE ###

import collections as c

n = int(input())

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

q = int(input())

s = sum(a)

cnt = c.Counter(a)

for i in range(q):
    b,c = map(int,input().split())
    s += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(s)
### BUGGY CODE ###

import math

N = int(input())
if N == 0:
    N = 9
logN = math.log10(N)
keta = int(logN)
sum = 0
for i in range(keta,-1,-1):
    tem =int(N/10**i)
    sum += tem
    N = N - tem*10**i

if sum % 9 == 0:
    print("Yes")
else:
    print("No")
    

### FIXED CODE ###

N = int(input())
if N % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def splitting_pile():
	n = int(raw_input())
	nums = list(map(int, raw_input().split(" ")))
	ans = abs(sum(nums[:1])-sum(nums[1:]))
	for i in range(1, n):
		ans = min(ans, abs(sum(nums[:i])-sum(nums[i:])))
	print ans


if __name__ == "__main__":
	splitting_pile()

### FIXED CODE ###

def splitting_pile_2():
	n = int(raw_input())
	nums = list(map(int, raw_input().split(" ")))
	total_sum = sum(nums)
	left_sum = nums[0]
	ans = abs(total_sum-left_sum*2)

	for i in range(1, n-1):
		left_sum = left_sum + nums[i]
		ans = min(ans, abs(total_sum-left_sum*2))
	print ans


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

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    S = input().rstrip()

    dp = [[[] for _ in range(N + 1)] for _ in range(N + 1)]  # dp[l1][length] = [l2, l2, ...]

    for l1 in range(N):
        for l2 in range(l1 + 1, N):
            if S[l1] == S[l2]:
                dp[0][l1].append(l2)

    for length in range(1, N):
        for l1 in range(N):
            for l2 in dp[length - 1][l1]:
                if l2 + length >= N:
                    continue
                if l1 + length >= l2:
                    continue
                if S[l1 + length] == S[l2 + length]:
                    dp[length][l1].append(l2)

    ans = 0
    for length in range(N + 1):
        for l1 in range(N + 1):
            if dp[length][l1]:
                ans = max(ans, length + 1)

    print(ans)

sol()

### FIXED CODE ###

from collections import deque

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

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

E=[[] for i in range(N+1)]

for i in range(M):
    a,b,cost=map(int,input().split())

    E[a].append((b,cost))
    E[b].append((a,cost))


Q=int(input())
Query=[list(map(int,input().split())) for i in range(Q)]

ANS=[[(N+10,0) for i in range(N+1)] for j in range(N+1)]

from collections import deque
import heapq

for start in range(1,N+1):

    ANS[start][start]=(0,0)

    checking=[((0,0),start)]

    while checking:
        #print(checking)
        c,checktown=heapq.heappop(checking)
        h,cost0=c

        if ANS[start][checktown]<c:
            continue

        for to,cost in E[checktown]:
            
            if cost0+cost<=L and (h,cost0+cost)<ANS[start][to]:
                ANS[start][to]=(h,cost0+cost)
                heapq.heappush(checking,((h,cost0+cost),to))

            elif cost<=L and (h+1,cost)<ANS[start][to]:
                ANS[start][to]=(h+1,cost)
                heapq.heappush(checking,((h+1,cost),to))

for x,y in Query:
    if ANS[x][y][0]==N+10:
        print(-1)
    else:
        print(ANS[x][y][0])
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

E=[[] for i in range(N+1)]

for i in range(M):
    a,b,cost=map(int,input().split())

    E[a].append((b,cost))
    E[b].append((a,cost))


Q=int(input())
Query=[list(map(int,input().split())) for i in range(Q)]

ANS=[[(N+10,0) for i in range(N+1)] for j in range(N+1)]

from collections import deque
import heapq

for start in range(1,N+1):

    ANS[start][start]=(0,0)

    checking=[((0,0),start)]

    while checking:
        #print(checking)
        c,checktown=heapq.heappop(checking)
        h,cost0=c

        if ANS[start][checktown]<c:
            continue

        for to,cost in E[checktown]:
            
            if cost0+cost<=L and (h,cost0+cost)<ANS[start][to]:
                ANS[start][to]=(h,cost0+cost)
                heapq.heappush(checking,((h,cost0+cost),to))

            elif cost<=L and (h+1,cost)<ANS[start][to]:
                ANS[start][to]=(h+1,cost)
                heapq.heappush(checking,((h+1,cost),to))

for x,y in Query:
    if ANS[x][y][0]==N+10:
        print(-1)
    else:
        print(ANS[x][y][0])
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
for i in range(1000):
    num = ''
    num += str(i // 100)
    num += str((i // 10) % 10)
    num += str(i % 10)
    j = 0
    for n in range(N):
        if S[n] == num[j]:
            j += 1
        if j == 3:
            break
    if j == 3:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
cnt = 0
for i in range(1000):
    num = ''
    num += str(i // 100)
    num += str((i // 10) % 10)
    num += str(i % 10)
    j = 0
    for n in range(N):
        if S[n] == num[j]:
            j += 1
        if j == 3:
            break
    if j == 3:
        cnt += 1
print(cnt)
### BUGGY CODE ###

from sys import stdin
S = input()
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            S += Q[i][2]#先頭
        else :
            S1 = Q[i][2]+ S
            S = S1

if flag == True:
    print(S)
else:
    print(S[::-1])  


### FIXED CODE ###

from sys import stdin
S = input()
x = S
y =str()   
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            x += Q[i][2]#先頭
        else :
            y += Q[i][2]
M = "".join([y[::-1],x])
if flag == True:
    print(M)
else:
    print(M[::-1])
### BUGGY CODE ###

import numpy as np
import math
N, D, A = map(int, input().split())
xh = np.array(sorted([list(map(int, input().split())) for _ in range(N)]))
b = 0
c = 0
while 1:
  if all(xh[:, 1]<=0):
    break
  x, h = xh[c]
  c += 1
  if h<=0:
    continue
  r = min(x+2*D, xh[-1, 0])
  times = math.ceil(h/A)
  xh[np.where(xh[:, 0]<=r, True, False)] -= times*A
  b += times
print(b)

### FIXED CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)
### BUGGY CODE ###

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

cr = 1
for a in A[:k]:
    cr *= a

for i in range(n-k):
    tmp = A[k+i] * cr // A[i]
    if tmp > cr:
        print("Yes")
    else:
        print("No")
    cr = tmp


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A)

for i in range(n-k):
    if A[k+i] > A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
step = [1] + [0]*n
mod = 10**9 + 7
for i in range(1,n+1):
    if i in a:
        continue
    else:
        if i-1 not in a:
            step[i] += step[i-1]%mod
        if i-2 not in a and i>=2:
            step[i] += step[i-2]%mod
        if i-1 in a and i-2 in a:
            print(0)
            exit()
print(step[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n+1):
    dp[i] = (dp[i-1]+dp[i-2])%mod if i not in a else 0 #かけたところは0にしとこう、ってことか…
print(dp[n])
### BUGGY CODE ###

def around(K,A):
    N2 = A.pop(0)
    A.append(N2+K)
    return A  

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

X = 0
X_min = 1000000000
for j in range(0,len(A)):
    X=0
    for i in range(0,len(A)-1): #i番目の家からスタート
        X += A[i+1] - A[i]
        if X > X_min:
            i=0
            break
    if i == len(A)-2:
        X_min = X
    A=around(K,A)
#     print(X_min)
    
print(X_min)

### FIXED CODE ###

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

X = 0
space = 0
idx = 0
A.append(A[0]+K)
for j in range(0,len(A)-1):
    X=0
    X = A[j+1] - A[j]
    if space < X:
        space = X
        idx = j
    
print(A[idx] + K - A[idx+1] )
### BUGGY CODE ###

import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(dict)
    for l in range(1, N//2+1):
        for i in range(N-l+1):
            if S[i:i+l] not in d[l]:
                d[l][S[i:i+l]] = [[i, i+l-1]]
            else:
                d[l][S[i:i+l]].append([i, i+l-1])


    for l in range(N//2, 0, -1):
        if l in d:
            for s in d[l]:
                if len(d[l][s]) > 1:
                    # print(d[l][s], l)
                    i, j = d[l][s][0]
                    k, m = d[l][s][-1]
                    if j < k:
                        return l
    return 0

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1] == S[j-1] and dp[i-1][j-1] < (j-i):
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] == 0
    return ans

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

a, b = map(int, input().split())
c = []
for i in range(a):
    x = i + 1
    if a%x == 0:
        if b%x == 0:
            c.append(x)
print(c[-1])



### FIXED CODE ###

a, b = map(int, input().split())
c = []
if a > b:
    a, b = b, a
if b%a == 0:
    print(a)
else:
    while True:
        for i in range(a):
            x = i + 2
            if a%x == 0:
                if b%x == 0:
                    c.append(x)
                    a = a//x
                    b = b//x
                    break
                elif b%(a//x) == 0:
                    c.append(a//x)
                    a = x
                    b = b//(a//x)
                    break
            if x > a**0.5:
                break
        if x > a**0.5:
            break
    s = 1
    for j in c:
        s = s * j
    print(s)
### BUGGY CODE ###

N = int(input())
#a,b = map(int,input().split())
A = list(map(int,input().split()))
#A = [int(input()) for i in range(N)]
#A = [list(map(int,input().split())) for i in range(N)]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    gcda = gcd(a,b)
    return a*b//gcda
def lcmlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        from functools import reduce
        return reduce(lcm,lista)
mod = 10**9 + 7
lcml = lcmlist(A)
ans = 0
for i in A:
    ans = (ans + lcml//i)%mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
LCM = 1
for i in A:
    GCD = gcd(LCM,i)
    LCM = LCM*i//GCD
ans = 0
for i in A:
    ans += LCM//i
print(ans%mod)
### BUGGY CODE ###

n = int(input())
S = map(int,raw_input().split())
q = int(input())
T = map(int,raw_input().split())
count = 0
for v in T:
    for i in range(n):
        if S[i] == v:
            count += 1
            break
print count

### FIXED CODE ###

n = int(input())
S = set(raw_input().split())
q = int(input())
T = set(raw_input().split())
print len(S&T)
### BUGGY CODE ###

import sys

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

for i in reversed(range(y//10000 + 1)):
	n -= i
	y -= 10000 * i
	if 10000 * i + 5000 * (n-i) < y:
		break
	for j in reversed(range(y//5000 + 1)):
		n -= j
		y -= 5000 * j
		for k in reversed(range(y//1000 + 1)):
			n -= k
			y -= 1000 * k
			if y == 0 and n == 0:
				print(i,j,k)
				sys.exit()
			n += k
			y += 1000 * k
		n += j
		y += 5000 * j
	n += i
	y += 10000 * i

print("-1 -1 -1")


### FIXED CODE ###

import sys

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

if y // 10000 > n:
	print("-1 -1 -1")
	sys.exit()

for i in reversed(range(y//10000 + 1)):
	n -= i
	y -= 10000 * i
	if 10000 * i + 5000 * (n-i) < y:
		break
	for j in reversed(range(y//5000 + 1)):
		n -= j
		y -= 5000 * j
		for k in reversed(range(y//1000 + 1)):
			n -= k
			y -= 1000 * k
			if y == 0 and n == 0:
				print(i,j,k)
				sys.exit()
			else:
				n += k
				y += 1000 * k
				break
		n += j
		y += 5000 * j
	n += i
	y += 10000 * i

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

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

A = sorted(A,reverse=True)
#print(A)

for i in range(M):
    A[0] //= 2
    for i in range(N-1):
        if A[i] < A[i+1]:
            x = A[i]
            A[i] = A[i+1]
            A[i+1] = x
            
        else:
            break

ans = 0
for i in A:
    ans += i

print(ans)




### FIXED CODE ###

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

A = sorted(A,reverse=True)
#print(A)
X = M
for i in range(M):
    A[0] //= 2
    X -= 1
    count = 0
    for j in range(min(N-1,M)):
        if A[j] < A[j+1]:
            x = A[j]
            A[j] = A[j+1]
            A[j+1] = x
            count += 1
        else:
            break
            
    if count >= X:
        for j in range(X):
            A[j] //= 2
        break
    else:
        for j in range(count):
            A[j] //= 2
        X -= count
        A = sorted(A,reverse=True)
        
        
ans = 0
for i in A:
    ans += i

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

N = int(input())
A = tuple(map(int, input().split()))
mod = 10**9+7

ans = 0
for k in range(61):
    num1 = 0
    for a in A:
        if (a >> k) & 1:
            num1 += 1
    ans += (num1 * (N-num1)) << k
    ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))
mod = 10**9+7

def solve(N, A):
    ans = 0
    for k in range(61):
        num1 = 0
        for a in A:
            if (a >> k) & 1:
                num1 += 1
        ans += (num1 * (N-num1)) << k
        ans %= mod
    return ans
    
print(solve(N, A))
### BUGGY CODE ###

s = input()
sl = list(s)
ls = range(len(s) - 1)
loop = 1
c = 0
while (loop):
    loop = 0
    for i in ls:
        if sl[i:i + 3] == ['A', 'B', 'C']:
            sl[i] = 'B'
            sl[i + 1] = 'C'
            sl[i + 2] = 'A'
            c += 1
            loop = 1
print(c)

### FIXED CODE ###

def b():
    import re
    s = input()
    s = re.sub(r'BC', 'D', s)
    ls = range(len(s))
    ac, c = 0, 0
    for i in ls:
        if s[i] == 'A':
            ac += 1
        elif s[i] == 'D':
            c += ac
        else:
            ac = 0
    return c


ans = b()
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input().split()[1])
s=input()

def count(l,r):
    global s
    lr_str = s[l-1:r]
    #print(lr_str)
    As_ind = [i for i, x in enumerate(lr_str) if x == 'A']
    count=0
    for a in As_ind:
        if a<len(lr_str)-1:
            #print(a+1)
            if lr_str[a+1]=='C':
                count+=1
    print(count)

for i in range(n):
    lr=input().split()
    count(int(lr[0]),int(lr[1]))
    



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

def main():
    import sys
    import decimal
    input = sys.stdin.readline
    n, m, d = [int(x) for x in input().strip().split()]
    if d == 0:
        print(((n-d)*pow(n, m-2)*(m-1)) / pow(n, m))
        return True
    print(((n-d)*2*pow(n, m-2)*(m-1)) / pow(n, m))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import decimal
    input = sys.stdin.readline
    n, m, d = [int(x) for x in input().strip().split()]
    if d == 0:
        print((m-1)/n)
        return True
    print(((n-d)*2*(m-1) / pow(n, 2)))

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

N = int(input())
power = 1
for i in range(N):
  power *= (i + 1)
print(power % (10**9 + 7))

### FIXED CODE ###

import math
N = int(input())
n = 10**9 + 7
power = math.factorial(N)
print(power % n)
### BUGGY CODE ###

#coding: utf-8
n = int(input())

answer = 0

for i in range(1,n):
	answer += i
print(answer) 


### FIXED CODE ###

#coding: utf-8
from decimal import Decimal
n = int(input())
n = n-1
answer = 0

if n % 2 == 0:
	answer = (Decimal(n)+Decimal(1))*(Decimal(n)/2)
else:
	answer = Decimal(n)*((Decimal(n)-Decimal(1))/2) + Decimal(n)

print(int(round(answer,0)))
### BUGGY CODE ###

n=int(input())
a=[]
ans=0
for i in range(1,n+1):
  a.append(i)
b=a.copy()
b.append(a[0])
del b[0]

for i in range(n):
  ans+=a[i]%b[i]
  
print(ans)

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

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

    A.sort()
    ans = 0
    temp = 0
    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    for i in range(N):
        if i == 0 and A[i+1] != A[i]:
            ans += 1
            continue

        temp = A[i]

        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue

        for j in range(N):
            if A[j] <= temp/2 and A[i]%A[j] == 0:
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print(main())


### FIXED CODE ###

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

    A.sort()
    dict = {}
    for i in range(1,A[N-1]+1):
        dict[i] = 0

    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    temp = 1

    for num in A:
        while True:
            if num*temp <= A[N-1]:
                dict[num*temp] += 1
                temp += 1
            else:
                temp = 1
                break

    ans = 0
    for num2 in A:
        if dict[num2] <= 1:
            ans += 1

    return ans


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

K = int(input())
N = 3
def common_divisor(num1,num2):
    if num1%num2==0:
        return num2
    elif num2%num1==0:
        return num1
    temp = max(num1,num2)%min(num1,num2)
    while True:
        if temp!=0:
            num1 = min(num1,num2)
            num2 = temp
            temp = num1%num2
        else:
            return num2

sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for m in range(1,K+1):
            sum = sum+common_divisor(common_divisor(i,j),m)

print(sum)

### FIXED CODE ###

import math
K = int(input())

sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        temp = math.gcd(i,j)
        for m in range(1,K+1):
            sum = sum+math.gcd(m,temp)
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    if i in A:
        a = 0
        a2 = a1
        a1 = a
    else:
        a = a2+a1
        a2 = a1
        a1 = a
print(1 if N == 1 else a%1000000007)


### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
### BUGGY CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(M)]

seki = set(list(range(LR[0][0],LR[0][1]+1)))
for i in range(M):
    seki &= set(list(range(LR[i][0], LR[i][1]+1)))

print(len(seki))

### FIXED CODE ###

# 解説を見ての解答
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
lr = [list(map(int, stdin.readline().rstrip().split())) for i in range(m)]

l, r = lr[0][0], lr[0][1]
for i in range(m):
    l = max(l, lr[i][0])
    r = min(r, lr[i][1])

print(max(0,r-l+1))
### BUGGY CODE ###

import copy
N = int(input())
lst = []
for i in range(N):
    lst.append(int(input()))


for i in range(N):
    lst2 = lst[:]
    lst2.pop(i)
    print(max(lst2))


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
B = sorted(A, reverse = True)

for i in range(N):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
p=1
for i in range(n):
    p=p*a[i]

    if i>=k-1:
        b.append(p)
        p=p//a[i-k+1]

for i in range(1,len(b)):
    if b[i]>b[i-1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
input=sys.stdin.readline


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

for i in range(k,n):

    if a[i]>a[i-k]:

        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import itertools

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

cnt = 0
while len(strs) != 0:
  s = strs.pop()
  anagrams = set(["".join(a) for a in itertools.permutations(s)])
  for anag in anagrams:
    if anag in strs:
      cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())
strs = ["".join(sorted(str(input()))) for _ in range(n)]

cache = {}
cnt = 0
for s in strs:
  if s in cache.keys():
    cnt = cnt + cache[s]
    cache[s] = cache[s] + 1
  else:
    cache[s] = 1
print(cnt)