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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()
  l=getPrimeList(n)

  mn=len(str(n))
  for i in range(2**len(l)):
    a=n
    b=1
    for j in range(len(l)):
      if ((i>>j)&1):
        a//=l[j]
        b*=l[j]
    mn=min(mn,max(len(str(a)),len(str(b))))

  return mn

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()
  l=getPrimeList(n)

  mn=len(str(n))
  for i in range(2**len(l)):
    a=n
    b=1
    for j in range(len(l)):
      if ((i>>j)&1):
        a//=l[j]
        b*=l[j]
    mn=min(mn,max(len(str(a)),len(str(b))))

  return mn

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

s=input()
t=input()

def c(a,b,s):
    t=s.replace(a,".")
    u=t.replace(b,a)
    v=u.replace(".",b)
    
    return v
    

for i in range(len(t)):
    if s[i]!=t[i]:
        s=c(s[i],t[i],s)

if s==t:
    print("Yes")
else:
    print("No")
        
    

### FIXED CODE ###

s=input()
t=input()


def f(s):
    l=[]
    a="abcdefghijklmnopqrstuvwxyz"
    r=""
    for i in range(len(s)):
        if s[i] in l:
            for j in range(len(l)):
                if s[i]==l[j]:
                    r+=a[j]
        else:
            r+=a[len(l)]
            l.append(s[i])
    return r

if f(s)==f(t):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

for n in range(M):
    a_append(int(input()))

mod = 1000000007

# check
check = {}
for n in range(N + 1):
    if n in a:
        check[n] = False
    else:
        check[n] = True

dp = {0: 1}
if check[1] is True:
    dp[1] = 1
else:
    dp[1] = 0

for n in range(2, N + 1):
    dp[n] = 0
    if check[n - 1] is True:
        dp[n] += dp[n - 1]
    if check[n - 2] is True:
        dp[n] += dp[n - 2]
    dp[n] %= mod

print(dp[N])


### FIXED CODE ###

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

for n in range(M):
    a_append(int(input()))

mod = 1000000007

# check
check = [True] * (N + 1)
for i in a:
    check[i] = False

dp = {0: 1}
if check[1] is True:
    dp[1] = 1
else:
    dp[1] = 0

for n in range(2, N + 1):
    dp[n] = 0
    if check[n - 1] is True:
        dp[n] += dp[n - 1]
    if check[n - 2] is True:
        dp[n] += dp[n - 2]
    dp[n] %= mod

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

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

dic = {}
for i in d:
    if i in dic.keys():
        dic[i] += 1
    else:
        dic[i] = 1
for i in t:
    if i in dic.keys():
        dic[i] -= 1
        if dic[i] == 0:
            del(dic[i])
    else:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

def main():
    n = int(input())
    d = list(map(int, input().split()))
    m = int(input())
    t = list(map(int, input().split()))
    d.sort()
    t.sort()
    x = -1
    y = -1
    while x < n and y < m-1:
        x += 1
        y += 1
        while x < n and d[x] != t[y]:
            x += 1
    if x < n:
        print("YES")
    else:
        print("NO")

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
ret = 0
for i in range(n-k+1):
  p_s=0
  for j in range(k):
    p_i = p[i+j]
    p_s+=(1+p_i)*p_i/(2*p_i)
  if p_s>ret:
    ret = p_s
print(ret)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
max_i=0
ret = 0
p_s=sum(p[0:k])
s_max=p_s
for i in range(n-k):
  p_s=p_s-p[i]+p[i+k]
  if s_max<p_s:
    s_max=p_s

print(s_max/2+k/2)
### BUGGY CODE ###

x,y = map(int,input().split())
d = y//x
ans = 0
while 0 < d:
  ans += 1
  d // 2
print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
d = y//x
ans = 0
while 0 < d:
  ans += 1
  d //= 2
print(ans)
### BUGGY CODE ###

def binary_search(a, f, target, left, right):
    ans = a[-1] * f[-1]
    while left + 1 < right:
        mid = (left+right)//2
        cost = 0
        for aa,ff in zip(a,f):
            if ff > mid:
                cost += aa
            elif aa - mid // ff > 0:
                cost += aa - mid // ff
        if cost > target:
            left = mid
        else:
            right = mid
    return right

n,k = map(int,input().split())
a = sorted(map(int, input().split()), reverse=True)
f = sorted(map(int, input().split()))
target = binary_search(a,f,k,-1,max(a) * max(f))
mx = 0
cost = 0
for aa, ff in zip(a,f):
    if ff > target:
        cost += aa
        aa = 0
    elif aa - target // ff > 0:
        cost += aa - target // ff
        aa = (target // ff)
    if mx < aa * ff:
        mx = aa * ff
print(mx)


### FIXED CODE ###

def binary_search(a, f, target, left, right):
    ans = a[-1] * f[-1]
    while left + 1 < right:
        mid = (left+right)//2
        cost = 0
        for aa,ff in zip(a,f):
            if ff > mid:
                cost += aa
            elif aa - mid // ff > 0:
                cost += aa - mid // ff
        if cost > target:
            left = mid
        else:
            right = mid
    return right

n,k = map(int,input().split())
a = sorted(map(int, input().split()), reverse=True)
f = sorted(map(int, input().split()))
target = binary_search(a,f,k,-1,max(a) * max(f))
mx = 0
cost = 0
for aa, ff in zip(a,f):
    if ff > target:
        cost += aa
        aa = 0
    elif aa - target // ff > 0:
        cost += aa - target // ff
        aa = (target // ff)
    if mx < aa * ff:
        mx = aa * ff
print(mx)
### BUGGY CODE ###

N,K=map(int,input().split())
score=list(map(int,input().split()))
for i in range(N-K):
  pre=1
  af=1
  for t in range(K):
    pre*=score[t+i]
    af*=score[t+1+i]
  if pre<af:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

N,K=map(int,input().split())
score=list(map(int,input().split()))
for i in range(N-K):
  if score[i]<score[K+i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from collections import defaultdict
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend, block = defaultdict(set), defaultdict(set)
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    i = -1
    belonging = [-1] * n
    group = []
    next_search = []
    is_searched = [False] * n
    while not all(is_searched):
        if not next_search:
            for j, s in enumerate(is_searched):
                if not s:
                    next_search.append(j)
                    group.append(set())
                    i += 1
                    break
        j = next_search.pop()
        if is_searched[j]:
            continue
        is_searched[j] = True
        belonging[j] = i
        group[i].add(j)
        next_search += friend[j]
    suggestion = [len(group[belonging[i]].difference(friend[i]).difference(block[i])) - 1 for i in range(n)]
    print(*suggestion)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [[] for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] = pf
    print(*[len(potential[i]) - len(block[i] & potential[i]) - len(friend[i]) - 1 for i in range(n)])

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

n = int(input())
t = 0
c = [0] * (n-1)
s = [0] * (n-1)
f = [0] * (n-1)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split())

for i in range(n-1):
    t = 0
    for j in range(i,n-1):
        start = s[j] #the time you should leave station_i
        while True:
            if t <= start:
                break
            else:
                start += f[j]
        #print(start)
        t = start + c[j] #the time you reach station_i+1
        #print(t)
    print(t)
print(0)

### FIXED CODE ###

n = int(input())
t = 0
c = [0] * (n-1)
s = [0] * (n-1)
f = [0] * (n-1)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split())

for i in range(n-1):
    t = 0
    for j in range(i,n-1):
        if t < s[j]:
            t = s[j]
        elif t % f[j] != 0:
            t = t + f[j] - (t % f[j])
        t += c[j]
            
    print(t)
print(0)
### BUGGY CODE ###

N = int(input())
P = list(map(float,input().split()))
ans = 0
dp = [[0 for _ in range(N+1)] for __ in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1-P[i-1])
        else:
            dp[i][j]=dp[i-1][j-1]*P[i-1] + dp[i-1][j]*(1-P[i-1])

for i in range(N+1):
    if i>N/2:
        ans += dp[N][i]
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(float,input().split()))
ans = 0
dp = [[0 for _ in range(N+1)] for __ in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1-P[i-1])
        else:
            dp[i][j]=dp[i-1][j-1]*P[i-1] + dp[i-1][j]*(1-P[i-1])

for i in range(N+1):
    if i>N/2:
        ans += dp[N][i]
print(ans)
### BUGGY CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 15

count = 0
for x in range(k+1):
    if s < x:
        break
    for y in range(k+1):
        if s < x + y:
            break
        if x + 2*k < s:
            break
        for z in range(k+1):
            if x + y + z == s:
                count = count + 1
                break
            if x + y + k < s:
                break

print(count)


### FIXED CODE ###

import numpy as np
import sys

x = [[int(i) for i in input().split()] for j in range(1)]
k = x[0][0]
s = x[0][1]


#k = 5
#s = 14

count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z <= k and 0 <= z:
            count += 1
print(count)
### BUGGY CODE ###

class Unbalanced:
	def searchStrings(self,s):
		words=[[[0 for j in range(26)] for i in range(len(s)-1)]for k in range(len(s))]
		for k in range(len(s)):
			for i in range(0,k+1):
				words[k][i][ord(s[i])-97]+=1
				for j in range(i+1,k+1):
					words[k][i][ord(s[j])-97]+=1
					if max(words[k][i])>=len(s[i:j+1])/2+1:
						print i+1,j+1
						return
		print -1,-1

if __name__ == "__main__":
	s=raw_input()
	u=Unbalanced()
	u.searchStrings(s)

### FIXED CODE ###

class nUnbalanced:
	def searchStrings(self,s):
		if len(s)==2:
			x_f=s[0]; x_s=s[1]
			if x_f==x_s: print 1,2; return
			else: print -1,-1; return
		for base in range(len(s)-2):
			x_f=s[base]; x_s=s[base+1]; x_t=s[base+2]
			if x_f==x_s or x_s==x_t or x_f==x_t: print base+1,base+3; return
		print -1,-1

if __name__ == "__main__":
	s=raw_input()
	u=nUnbalanced()
	u.searchStrings(s)
### BUGGY CODE ###

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

    num=[2]
    max = A[N-1]
    for k in range(3,max):
        chk=True
        for k2 in num:
            if k%k2 == 0:chk=False
        if chk==True:num.append(k)

    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
#もし素数ならループから外す
        if temp in num:
            ans += 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 ###

n = int(input())
a = [int(input()) for i in range(n)]
check = []
cnt = 0
i = 0
while True:
    if i not in check:
        check.append(i)
        i = a[i]-1
    elif i in check:
        print(-1)
        break
    elif cnt >= n:
        print(-1)
        break
    if i == 1:
        print(len(check))
        break
    cnt += 1
    
    

### FIXED CODE ###

n = int(input())
a = [None]
for j in range(n):
    a.append(int(input()))

i = 1
c = 0
r = [1]
while True:
    c += 1
    i = a[i]
    if i == 2:
        print(c)
        break
    if c > (10**5):
        print(-1)
        break
### BUGGY CODE ###

from math import factorial
from collections import Counter

def combinations_count(n, r):
    if n <= 1:
        return 0
    else:   
        return factorial(n) // (factorial(n - r) * factorial(r))

N = int(input())
A = list(input().split())
sum = 0
counter = Counter(A)
for key,value in counter.items():
    sum = sum + combinations_count(value,2)

for k in range(N):
    add = 0
    add = sum - combinations_count(counter[A[k]],2) + combinations_count(counter[A[k]]-1,2) 
    print(add)


### FIXED CODE ###

from math import factorial
from collections import Counter

def combinations_count(n, r):
    if n <= 1:
        return 0
    else:
        return (n * (n-1)) // 2 
        #return factorial(n) // (factorial(n - r) * factorial(r))

N = int(input())
A = list(input().split())
sum = 0
counter = Counter(A)
for key,value in counter.items():
    sum = sum + combinations_count(value,2)

for k in range(N):
    add = 0
    add = sum - combinations_count(counter[A[k]],2) + combinations_count(counter[A[k]]-1,2) 
    print(add)
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h.sort()
subs = []
for i in range(1,n):
    subs.append(h[i]-h[i-1])

minimum = 10**10
for i in range(len(subs)-1):
    minimum = min(minimum,sum(subs[i:k+i-1]))


print(minimum)


### FIXED CODE ###

import itertools
import math
import fractions
import functools
n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h.sort()
subs = []
for i in range(1,n):
    subs.append(h[i]-h[i-1])

amount = [0]*(n)
sums = 0
for i in range(0,len(subs)):
    sums += subs[i]
    amount[i+1] = sums


minimum = 10**10
for i in range(k-1,n):
    minimum = min(minimum,amount[i]-amount[i-k+1])

print(minimum)
### BUGGY CODE ###

K=int(input())
if K%2==0:
    print('-1')
    exit()
a=0
i=1
while True:
    a=(a*10+7)%K
    if a==0:
        print(i)
        break
    i+=1


### FIXED CODE ###

K=int(input())
if K%2==0 or K%5==0:
    print('-1')
    exit()
a=0
i=1
while True:
    a=(a*10+7)%K
    if a==0:
        print(i)
        break
    i+=1
### BUGGY CODE ###

from math import gcd
import sys
si = sys.stdin.readline
d = {}


def main():
    k = int(si())
    ans = 0
    for p in range(1, k+1):
        for q in range(1, k+1):
            for r in range(1, k+1):
                if (q, r) in d:
                    t1 = d[(q, r)]
                elif (r, q) in d:
                    t1 = d[(r, q)]
                else:
                    t1 = gcd(q, r)
                    d[(q, r)] = t1
                    d[(r, q)] = t1

                if (p, t1) in d:
                    t2 = d[(p, t1)]
                elif (t1, p) in d:
                    t2 = d[(t1, p)]
                else:
                    t2 = gcd(p, t1)
                    d[(p, t1)] = t2
                    d[(t1, p)] = t2
                ans += t2
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import gcd
import sys
si = sys.stdin.readline

# def gcd(u, v):
#     if v:
#         return gcd(v, u % v)
#     else:
#         return u


def main():
    k = int(si())
    cnt = 0
    for p in range(1, k+1):
        for q in range(1, k+1):
            for r in range(1, k+1):
                cnt += gcd(p, gcd(q, r))
    print(cnt)


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

from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
endflag=[[False]*2501 for i in range(n)]
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    endflag[node][silver]=True
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        if costmoney<=silver and not endflag[atnode][silver-costmoney]:
            heappush(hp,(time+costtime,silver-costmoney,atnode))

    if silver!=2500 and not endflag[node][min(silver+c[node],2500)]:
        heappush(hp,(time+d[node],min(silver+c[node],2500),node))
        
print(*mintimes[1:],sep="\n")

### FIXED CODE ###

from heapq import *
n,m,s=map(int,input().split())
c=[0]*n
d=[0]*n
g=[[]for i in range(n)]

for i in range(m):
    u,v,a,b=map(int,input().split())
    u-=1
    v-=1
    g[u].append((v,a,b))
    g[v].append((u,a,b))
for i in range(n):
    c[i],d[i]=map(int,input().split())

flag=0 #if this == (1<<n)-1 then finish roop
lasttime=[[10**15]*2501 for i in range(n)]
lasttime[0][min(2500,s)]=0
mintimes=[10**15]*n
hp=[(0,min(2500,s),0)]#(time,silver,node)

while flag!=((1<<n)-1):
    time,silver,node = heappop(hp)
    flag=flag|(1<<node)
    mintimes[node]=min(mintimes[node],time)

    for atnode,costmoney,costtime in g[node]:
        nexttime,nextsilver=time+costtime,silver-costmoney
        if costmoney<=silver and lasttime[atnode][nextsilver]>nexttime:
            heappush(hp,(nexttime,nextsilver,atnode))
            lasttime[atnode][nextsilver]=min(lasttime[atnode][nextsilver],nexttime)

    nexttime,nextsilver=time+d[node],min(silver+c[node],2500)
    if silver!=2500 and lasttime[node][nextsilver]>nexttime:
        heappush(hp,(nexttime,min(silver+c[node],2500),node))
        lasttime[node][nextsilver]=min(lasttime[node][nextsilver],nexttime)
        
print(*mintimes[1:],sep="\n")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
	ans.append(a[i])
	ans.reverse()
#数字列を空白あり文字列として出力する
print(' '.join(map(str,ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
head_s = [] 
back_s = []
n2 = 1
if n%2 == 0:
	n2 = 0
for h in range(n-1,-1,-2):
	head_s.append(a[h])
for b in range(n2,n,2):
	back_s.append(a[b])
#print(head_s,back_s)
ans_h = (' '.join(map(str,head_s)))
ans_b = (' '.join(map(str,back_s)))
print(ans_h,ans_b)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0 
for i in range(N):
    for j in range(i+1,N):
        if(A[j]==j-i-A[i]):
            cnt+=1

print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
AP = [0]*N
AM = [0]*N

for i in range(N):
    AP[i]=i+A[i]
    AM[i]=i-A[i]

cnt=0
QC = Counter(AP)
for m in AM:
    cnt += QC[m]

print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input())for i in range(M)]
MOD = 10 ** 9 + 7
ans = []
dp = [1] * N

for i in range(N):
    if (i + 1) in a:
        dp[i] = 0
    elif i == 0:
        dp[i] = 1
    elif i == 1 and dp[0] == 1:
        dp[i] = 2
    elif i == 1 and dp[0] == 0:
        dp[i] = 1
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N-1] % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input())for i in range(M)]
MOD = 10 ** 9 + 7
ans = []
dp = [1] * (N + 1)

for i in a:
    dp[i] = 0

for i in range(2, N + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2])

print(dp[N] % MOD)
### BUGGY CODE ###

n = int(input())
sl = []
for _ in range(n):
    sl.append(input())
rl=[]
ll=[]
rslt=0
for i in range(n):
    r=sorted(sl[i])
    if r in rl: tmp=rl.index(r); ll[tmp]+=1; rslt+=ll[tmp]
    else: rl.append(r); ll.append(0)
print(rslt)


### FIXED CODE ###

n = int(input())
S=[input() for _ in range(n)]
S=[''.join(sorted(i)) for i in S]
d={}
rslt=0
for s in S:
    if s in d:
        rslt+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(rslt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
SUM = 0
for i in range(1,N):
    for j in range(i):
        SUM += A[i]*A[j]
print(SUM % (10**9+7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
sumA = sum(A)
SUM = 0
for i in range(1,N):
    sumA -= A[i]
    SUM += A[i]*sumA
print(SUM % (10**9+7))