Harryxun/stf_run huggingface dataset:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,d = list(map(int, input().split()))
if d<0:
    x = x + d*(n-1)
    d *= -1
    
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
if x!=0:
    g = gcd(x,d)
    l = x*d//g
    lx = l//x
    ld = l//d
d = {i:[0,None] for i in range(n)} # (要素数, 最大値)
for i in range(n):
    # iX+sD
    if x!=0:
        ii = i - (i//lx)*lx
    else:
        ii = 0
    jj = (i//lx)*ld
    nn, m = d[ii]
    num = ((2*n-1-i)*i//2 + jj) - max(i*(i-1)//2 + jj - 1, m if m is not None else -float("inf"))
    d[ii] = [d[ii][0]+num, (2*n-1-i)*i//2 + jj]
ans = sum(v[0] for k,v in d.items() if v[1] is not None)
print(ans+1)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,d = list(map(int, input().split()))
if d==0:
    if x==0:
        ans = 1
    else:
        ans = n+1
else:
    if d<0:
        x *= -1
        d *= -1
#         x = x + d*(n-1)
#         d *= -1
    D = {} # (要素数, 最大値)
    for i in range(n+1):
        # iX+sD
        if x!=0:
            ii = i*x % d
            jj = (i*x-ii)//d
        else:
            ii = 0
            jj = 0
#         print(ii,jj)
        if ii not in D:
            D[ii] = []
        D[ii].append((i*(i-1)//2 + jj, (2*n-1-i)*i//2 + jj))
    ans = 0
    for k,v in D.items():
        v.sort()
        m = -float("inf")
        val = 0
        for l,r in v:
#             val += (r - (max(l-1, m)))
            val += max(r - (max(l-1, m)), 0)
            m = max(m, r)
        ans += val
                    
#         num = ((2*n-1-i)*i//2 + jj) - max(i*(i-1)//2 + jj - 1, m if m is not None else -float("inf"))
#         D[ii] = [D[ii][0]+num, (2*n-1-i)*i//2 + jj]
#         print(D)
#         if ii==0 and (2*n-1-i)*i//2 + jj >= 0 >= i*(i-1)//2 + jj:
#             zz = True
#     ans = sum(v[0] for k,v in D.items() if v[1] is not None) + (not zz)
# print(ans)
print(ans)
"""
まず、答えは必ずAの総和以下になる。なぜなら、A同士の差の最大値がAの総和だからである。
移動回数が足りるのであれば、一つだけAの総和になるような項を作って、他を全部0にするのがよい。
ここからわかるのは、数を移動させ終わった後の各Aは全て0以上になるということである。

また答えはからなずAの総和の約数になる。
理由：
答えをXとすると、各AはbXと表すことができる。
したがって、Aの総和＝(bの総和*X)となる。
ゆえに、答えXはAの総和の約数である。

解法としては、Aの総和の約数を列挙して、大きい順に実現可能かどうかを試していく。
実現可能かどうかを試すには、各Aを総和の約数dで割ったときの余りをもとめて、小さい順にソートする。
そのうえで、左からL番目までを「数を与える側」、L+1番目以降を「数をもらう側」として余りが0になるように調整できないかを確かめる。
これは累積和を活用することですくない計算量で実行可能である。
最後に、移動した数がK以下かどうかを確認する。
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
sumA = sum(A)
 
yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    #約数の大きい順に、実現可能かどうかを試していく。
    rest = [a%d for a in A]
    rest.sort()
    
    rest = [a%d for a in A]
    rest.sort()
    Rrest = [d-r for r in rest]
    Rrest = Rrest[::-1]
    rest = [0]+list(accumulate(rest))
    Rrest = [0]+list(accumulate(Rrest))
    for i in range(N+1):
        if rest[i] == Rrest[N-i]:
            if rest[i] <= K:
                print(d)
                exit()
            break

### FIXED CODE ###

"""
最大公約数を追い求める。

少なくとも、Aの合計値より答えが大きくなることはない。
なぜなら、どんなに頑張ってもA同士の差分はAの合計値以下になるからである。

答えの最大値はAの合計値。
マイナスを作る必要はない。
0を作る必要はある。

やっぱり、Aの合計値の約数のどれかが答えになりそうだな。証明はできないけど。
Aの合計値の約数を大きいものから順に、実現可能かどうかを検証していけばよい。

"""

from itertools import accumulate

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

yakusu = []
d = 1
while d*d < sumA:
    if sumA%d == 0:
        yakusu.append(d)
        yakusu.append(sumA//d)
    d += 1
if d*d == sumA:
    yakusu.append(d)
yakusu.sort(reverse=True)
for d in yakusu:
    #約数の大きい順に、実現可能かどうかを試していく。
    rest = [a%d for a in A]
    rest.sort()
    Rrest = [d-r for r in rest]
    Rrest = Rrest[::-1]
    rest = [0]+list(accumulate(rest))
    Rrest = [0]+list(accumulate(Rrest))
    for i in range(N+1):
        if rest[i] == Rrest[N-i]:
            if rest[i] <= K:
                print(d)
                exit()
            break
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

### FIXED CODE ###

import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()
N,M = list(map(int,input().split()))
xarray = sorted(list(map(int,input().split())))
 
diff = []
if len(xarray) == 1:
    print(0)
elif N == M:
    print(0)
else:
    for i in range(len(xarray)-1):
        diff.append(abs(xarray[i+1]-xarray[i]))
 
    if len(diff) == 0:
        print(0)
    else:
        diff2 = sorted(diff, reverse = True)
        
 
        if N == 1:
            
            print(sum(diff2))
        else:
            for j in range(N-1):
                diff2[j] = 0
            
            print(sum(diff2))

### FIXED CODE ###

N,M = list(map(int,input().split()))
xarray = sorted(list(map(int,input().split())))
 
diff = []
if len(xarray) == 1:
    print(0)
elif N >= M:
    print(0)
else:
    for i in range(len(xarray)-1):
        diff.append(abs(xarray[i+1]-xarray[i]))
 
    if len(diff) == 0:
        print(0)
    else:
        diff2 = sorted(diff, reverse = True)
        
 
        if N == 1:
            
            print(sum(diff2))
        else:
            for j in range(N-1):
                diff2[j] = 0
            
            print(sum(diff2))
N = int(input())
 A = [int(x) for x in input().split()]
for i in A:
   	if A.count(i) >= 2:
   	   print('YES')
       return
print('NO')

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
mySet = set()
for i in A:
  if i in mySet:
    print('NO')
    exit()
  else:
      mySet.add(i)
print('YES')
def solve(X):
    for a in range(1 + X // 100):
        for b in range(1 + X // 101):
            for c in range(1+ X // 102):
                for d in range(1 + X // 103):
                    for e in range(1 + X // 104):
                        for f in range( 1 + X // 105):
                            if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 == X:
                                return 1
                            elif a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
                                break
                #        if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
                 #           break
              #      if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
               #         break
            #    if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
             #       break
          #  if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
           #     break
        #if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
         #   break
    return 0

X = int(input())
print(solve(X))
~

### FIXED CODE ###

def solve(X):
    for a in range(1 + X // 100):
        for b in range(1 + X // 101):
            for c in range(1+ X // 102):
                for d in range(1 + X // 103):
                    for e in range(1 + X // 104):
                        for f in range( 1 + X // 105):
                            if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 == X:
                                return 1
                            elif a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
                                break
                #        if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
                 #           break
              #      if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
               #         break
            #    if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
             #       break
          #  if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
           #     break
        #if a*100 + b*101+ c*102 + d * 103 + e * 104 + f * 105 > X:
         #   break
    return 0

X = int(input())
print(solve(X))
N = int(input())
if N[-1] == 2 or 4 or 5 or 7 or 9:
    print("hon")
elif N[-1] == 0 or 1 or 6 or 8:
    print("pon")
else:
    print("bon")

### FIXED CODE ###

N = input()
n = N[-1]
if n == "2" or n == "4" or n == "5" or n == "7" or n == "9":
    print("hon")
elif n == "0" or n == "1" or n == "6" or n == "8":
    print("pon")
else:
    print("bon")
a, b, c = map(int, input().split())
print(sum(a, b, c) - max(a, b, c))

### FIXED CODE ###

a, b, c = map(int, input().split())
print((a + b + c) - max(a, b, c))
def main():
    A, B, C = map(int, input().split())
    m = max(A, B, C)
    d = sum(A, B, C) - m
    if d % 2 == 0:
        print(d//2)
    else:
        print((d//2)+2)

main()


### FIXED CODE ###

def main():
    A, B, C = map(int, input().split())
    m = [A,B,C]
    m.sort(reverse=True)
    d = (m[0] - m[1]) + (m[0] - m[2])
    if d % 2 == 0:
        print(d//2)
    else:
        print((d//2)+2)

main()
from math import gcd

def dp():
    n=int(input())
    l=list(map(int,input().split()))
    lcm=1
    for i in l:
        lcm=(lcm*i)//gcd(lcm,i)
    ans=0
    mod=1000000007
    for i in l:
        ans=(ans+(lcm//i))%mod
    print(ans)

if __name__ == "__main__":
    dp()

### FIXED CODE ###

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

def Lcm(a,b):
    return (a*b)//gcd(a,b)

def dp():
    n=int(input())
    l=list(map(int,input().split()))
    lcm=l[0]
    for i in range(n):
        lcm=Lcm(lcm,l[i])
    ans=0
    mod=1000000007
    for i in range(n):
        ans+=lcm//l[i]
    print(ans%mod)

if __name__ == "__main__":
    dp()
a, b = map(int, input().split())

ans=a+b

if ans>=24
  ans=ans-24
  
print(ans)

### FIXED CODE ###

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

m=a+b

if m>=24:
  print(int(m-24))
else:
  print(int(m))
days = list(str(input()))
days_real = list(str(input()))
for i in range(3):
  if days[i] == days_real[i]:
    count += 1
print(count)

### FIXED CODE ###

days = list(str(input()))
days_real = list(str(input()))
count = 0
for i in range(3):
  if days[i] == days_real[i]:
    count += 1
print(count)
H, W = [int(i) for i in input().split()]

if H==1 or W==1:
    print(1)
    quit()
if H%2==0:
    H //= 2
    print(H*W)
elif W%2==0:
    W //= 2
    print(H*W)
else:
    W -= 1
    c = (W//2)*H
    c += H//2 + 1
    print(c)


### FIXED CODE ###

print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())-1])
import fraction
A,B,C,D=map(int,input().split())
L=C*D//(fraction.gcd(C,D))
print(int(B-A+1-(B//C-((A-1)//C))-(B//D-((A-1)//D))+(B//L-((A-1)//L))))

### FIXED CODE ###

import fractions
A,B,C,D=map(int,input().split())
L=C*D//(fractions.gcd(C,D))
print(int(B-A+1-(B//C-((A-1)//C))-(B//D-((A-1)//D))+(B//L-((A-1)//L))))
a,b,c,d=map(int, input().split())
sub=b-a
tmpc=sub//c
tmpd=sub//d
import fractions
def lcm(x,y):
    return (x*y) // fractions.gcd(x,y)
tmplcm=sub//lcm(c,d)
print(max(sub-(tmpc+tmpd-tmplcm)), 0)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
from fractions import gcd
lcm=(c*d)//gcd(c,d)
n=(b//c)-((a-1)//c)
n+=(b//d)-((a-1)//d)
print(b-a+1-n+((b//lcm)-((a-1)//lcm)))
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
arrow = [0] * (N + 1)

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(st, graph):
    INF = 10 ** 18
    dist = [0] * len(graph)
    dist[st] = 1
    queue = deque([st])
    while queue:
        q = queue.popleft()
        for r in graph[q]:
            if dist[r] == 0:
                dist[r] = q
                queue.append(r)
    return dist

answer = bfs(1, graph)[2:]
print("Yes")
for a in answer:
    print(a)

### FIXED CODE ###

from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
arrow = [0] * (N + 1)

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(st, graph):
    INF = 10 ** 18
    dist = [0] * len(graph)
    dist[st] = 1
    queue = deque([st])
    while queue:
        q = queue.popleft()
        for r in graph[q]:
            if dist[r] == 0:
                dist[r] = q
                queue.append(r)
    return dist

answer = bfs(1, graph)[2:]
print("Yes")
for a in answer:
    print(a)
a = int(input())
s = string(input())
if a >= 3200:
  print(s)
else:
  print('red')

    
  

### FIXED CODE ###

a = int(input())
s = str(input())
if a >= 3200:
  print(s)
else:
  print('red')
n, m = map(int, input().split())
a_l = [ int(input()) for _ in range(m) ]

dp = [0] * (n+1)
dp[0] = 1
if 1 not in a_l:
    dp[1] = 1
else:
    dp[1] = 0
if 2 not in a_l:
    dp[2] = dp[0] + dp[1]
else:
    dp[2] = 0
for i in range(2,n+1):
    if i not in a_l:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = 0
print(dp[-1]%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
a_l = [ int(input()) for _ in range(m) ]

dp = [1] * (n+1)
dp[0] = 1
if 1 not in a_l:
    dp[1] = 1
else:
    dp[1] = 0
if n > 1:
    for i in a_l:
        dp[i] = 0
    if 2 not in a_l:
        dp[2] = dp[0] + dp[1]
    else:
        dp[2] = 0
    for i in range(2,n+1):
        if dp[i] != 0:
            dp[i] = (dp[i-1] + dp[i-2])%1000000007
print(dp[-1])
N = int(input())
arr = map(int, input().split(' '))
for i in range(N//2, 0, -1):
  arr[i] = sum(arr[i::i]) % 2
ans = [i for i, j in enumerate(arr) if j == 1]
print(len(ans))
print(*ans)


### FIXED CODE ###

def main():
    n = int(input())
    A = [0] + list(map(int, input().rstrip().split()))
    for i in range(n // 2, 0, -1):  # second half: no multiples
        A[i] = sum(A[i::i]) % 2
    ans = [i for i, j in enumerate(A) if j]
    print(len(ans))  # all cells: [1] -> len() (much faster than sum())
    print(*ans)


if __name__ == "__main__":
    main()
N = str(input())

#N = str(14282668646)

count = 0
lenN = len(N)+1
for i in range(0, lenN):
#    t = i
    for j in range(i+5, i+8):
#        print (i, j)
        number = int(str(N[i:j]))
#        if number%2019 == 0:
#            count +=1
#            break
#            print (i, j)
#T = int(N)//2019
#
#for t in range (T):
#    den = 2019*t
#    length = len(str(den))
#    sum_length = len(N)
#    for i in range(sum_length-length):
#        if den == int(N[i:i+length]):
#            count +=1

print (count

### FIXED CODE ###

N, K = map(int, input().split())
sumR = 0
for i in range(K, N+2):
    front = i*(2*N + 2 - i + 1)/2
    rear = i*(i+1)/2
    number = front - rear + 1
#    print (i)
#    print (number)
    sumR += number
print (int(sumR%(1000000007)))
s = int(input())
w = int(input())

if s <= w:
    print('unsafe')
else:
    print('safe')

### FIXED CODE ###

s ,w = map(int, input().split())

if s <= w:
    print('unsafe')
else:
    print('safe')
S = str(input())
w = int(input())
idx = 0
ans = ""
while idx <= len(S):
  ans += S[idx]
  idx += w
print(ans)

### FIXED CODE ###

S = str(input())
w = int(input())
idx = 0
ans = ""
while idx < len(S):
  ans += S[idx]
  idx += w
print(ans)
L, R = map(int, input().split())

module = []
for i in range(L, R):
    for j in range(i+1, R+1):
        print("({} * {}) mod 2019 = {}".format(i, j, (i * j) % 2019))
        if (i * j) % 2019 == 0:
            print("0")
            exit()
        else:
            module.append((i * j) % 2019)

if not module:
    print("0")
else:
    print(min(module))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
X = [0] * N

X[0] = sum(A) - 2 * (sum([A[i] for i in range(N) if i % 2 == 1]))

for i in range(N - 1):
    X[i + 1] = 2 * A[i] - X[i]

print(" ".join(map(str, X)))
N = int(input())
I = int(input())

if I <= 13:
    print(N)
elif 6 <= I <=12:
    print(N/2)
elif I <= 5:
    print("0")


### FIXED CODE ###

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

c = 0
if a >= 13:
    print(b)
elif 6 <= a <=12:
    c = int(b /2)
    print(c)
elif a <= 5:
    print("0")
N_,Y_=input().split()
N=(int)(N_)
Y=(int)(Y_)

count = 0
a_ = Y//10000
if a_>N:
    a_ = N
for a in range(a_+1):
    Y_ = Y-a*10000
    N_ = N-a
    b_ = Y_//5000
    if b_>N_ and b_>=0:
        b_ = N_
    for b in range(b_+1):
        Y_ = Y_-b*5000
        N_ = N_-b
        if c_%1000:
            c_ = Y_//1000
            if c_==N_ and c_>=0:
                print((str)(a)+" "+(str)(b)+" "+(str)(c_))
                exit(0)
print("-1 -1 -1")


### FIXED CODE ###

N_,Y_=input().split()
N=(int)(N_)
Y=(int)(Y_)

count = 0
a_ = Y//10000
if a_>N:
    a_ = N
for a in range(a_+1):
    Y_ = Y-a*10000
    N_ = N-a
    b_ = Y_//5000
    if b_>N_ and b_>=0:
        b_ = N_
    for b in range(b_+1):
        Y__ = Y_-b*5000
        N__ = N_-b
        c_ = Y__//1000
        if Y__%1000==0:
            if c_==N__ and c_>=0:
                print((str)(a)+" "+(str)(b)+" "+(str)(c_))
                exit(0)
print("-1 -1 -1")
n = int(input())
ans = 0
for i in range(1,n + 1):
    if 10 <= i < 100 or 1000 <= i < 10000 or i == 100000:
        ans = ans
    else:
        ans += 1
print(ans)

### FIXED CODE ###

a, b, c = map(int,input().split())
print(b + c - a if b + c - a > 0 else 0)
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
mi=1
ma=n
for i in range(n):
  mi=max(mi,a[i][0])
  ma=min(ma,a[i][1])

if mi>ma:
  print("0")
else:
  print(ma-mi+1)



### FIXED CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
mi=1
ma=n
for i in range(m):
  mi=max(mi,a[i][0])
  ma=min(ma,a[i][1])

if mi>ma:
  print("0")
else:
  print(ma-mi+1)
x = int(inpuut())
if x ==1:
  print(0)
else:
  print(1)
    

### FIXED CODE ###

x = int(input())
if x ==1:
  print(0)
else:
  print(1)
def p(boundary):
    step=[0]*(boundary+1)
    step[0]=0
    step[1]=1
    step[2]=2
    for i in range(2,boundary-1):
        step[i+1]=step[i]+step[i-1]
    d=step[boundary]
    return d


N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)] 
b=[]
for i in range(0,M-2):
    b.append(a[i+1]-a[i]-2)
b.append(N-a[M-1]-1)
ans=p(a[0]-1)
for i in range(M):
    c=b[i]
    ans=p(c)*ans
print(ans)

### FIXED CODE ###

N,M = (int(i) for i in input().split())
ban=[False]*(N+1)
for i in range(M):
    a=int(input())
    ban[a]='True'
    
dp=[0]*(N+1)
dp[0]=1
if ban[1]=='True':
    dp[1]=0
else:
    dp[1]=1

for i in range(2,N+1):
    if(ban[i]):
        dp[i]=0
    else:
        dp[i]=dp[i-2]+dp[i-1]
print(dp[N]%1000000007)
h,w=map(int,input().split())
x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1

def go_next(I,J):
    global dp,w,h
    if 0<=I<h-1:
        if x[I+1][J]==".":
            if dp[I+1][J]>dp[I][J]+1:
                dp[I+1][J]=dp[I][J]+1
                go_next(I+1,J)

    if 0<I<=h-1:
        if x[I-1][J]==".":
            if dp[I-1][J]>dp[I][J]+1:
                dp[I-1][J]=dp[I][J]+1
                go_next(I-1,J)
    if 0<=J<w-1:
        if x[I][J+1]==".":
            if dp[I][J+1]>dp[I][J]+1:
                dp[I][J+1]=dp[I][J]+1
                go_next(I,J+1)
    if 0<J<=w-1:
        if x[I][J-1]==".":
            if dp[I][J-1]>dp[I][J]+1:
                dp[I][J-1]=dp[I][J]+1 
                go_next(I,J-1)

go_next(0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])


### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
a = int(raw_input())
b = int(raw_input())
c = int(raw_input())
x = int(raw_input())

def dfs(x, i, m, v):
  	if x < 0: return 0
  	if x == 0: return 1
  	if i == 2: return 1 if x % 50 else 0  	
  	r = 0
  	for k in range(0, m[i] + 1):
  		r += dfs(x - k * v[i], i+1, a,b,c)
  	return r
m,v = {0:a,1:b,2:c}, {0:500,1:100,2:50}
print dfs(x,0,m,v)


### FIXED CODE ###

n,mat = raw_input(),[ map(int,raw_input().split()) for i in range(2)]
def f(mat,i,j):
	if i<0 or j <0:
		return -float('inf')
	if i == 0 and j == 0:
		return mat[i][j] 
	return mat[i][j] + max(f(mat,i-1,j),f(mat,i,j-1))
print f(mat,1,len(mat[0])-1)
n, m = map(int,(input().split()))
d = {}
for i in range(n):
    a, b = map(int,(input().split()))
    d[a]=b
d = sorted(d.items())
ans = 0
for i in range(n):
    if d[i][1] >= m:
        ans += d[i][0]*m
        break
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]
        if m <= 0:
            break
print(ans)

### FIXED CODE ###

n, m = map(int,(input().split()))
d = []
for i in range(n):
    a, b = map(int,(input().split()))
    d.append([a,b])
d = sorted(d)
ans = 0
for i in range(n):
    if d[i][1] >= m: # 残り本数 >= この値段の本数
        ans += d[i][0]*m
        break
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]
        if m <= 0:
            break
print(ans)
a, b = map(int, input().split())

def test(n):
    x = n * 8 // 100
    y = n * 10 // 100
    return (x==a) and (y==b)

answer = -1
for n in range(int(2e+4)):
    if test(n):
        ans = n
        break
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
A,B = map(int,read().split())
 
def test(n):
    x = n * 8 // 100
    y = n * 10 // 100
    return (x == A) and (y == B)
 
answer = -1
for n in range(20000):
    if test(n):
        answer = n
        break
print(answer)
a,b = list(map(int,input().strip()).split()))
ans1 = a + b
ans2 = b - a
if b % a == 0:
    print(ans1)
else:
    print(ans2)

### FIXED CODE ###

a,b = list(map(int,input().strip().split()))
if b % a == 0:
    print(a + b)
else:
    print(b - a)