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

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] == inf:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)
### BUGGY CODE ###

from functools import reduce

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    ans = 0

    ans = reduce(lambda x,y:int(x)*int(y), A)
        

    if ans > 10**18:
        ans = -1
    print(ans)
         


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    A = sorted(list(map(int, input().split())))
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
#print(dp)
print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a.append(1000000)
dp = [0]*(n+1)
dp[0] = 1
j = 0
if a[j] == 1:
    j += 1
else:
    dp[1] = 1

for i in range(2,n+1):
    if i == a[j]:
        j += 1
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
#print(dp)
print(dp[n])
### BUGGY CODE ###

def main():
  s=input()
  l=len(s)
  mod=2019
  x=[0]*l
  x[0]=(int(s[0])*(pow(10,l-1)))%mod
  for i in range(1,l):
    x[i]=((int(s[i])*(pow(10,l-i-1)))%mod+x[i-1])%mod
  cnt=x.count(0)
  print(l-len(set(x))+cnt)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  s=input()[::-1]
  l,mod=len(s),2019
  x=[0]*mod
  x[0]=1
  a,t=0,1
  for i in range(l):
    a = (a + int(s[i])*t) % 2019
    x[a]+=1
    t=(t*10)%mod
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
for j in range(N-1):
  count = 0
  for k in range(j+1, N):
    if H[k] <= H[k-1]:
      count += 1
    else:
      break
  if count > m_max:
    m_max = count
print(m_max)

### FIXED CODE ###

N = int(input())
H = [int(i) for i in input().split()]
m_max = 0
count = 0
for j in range(1, N):
  if H[j] <= H[j-1]:
    count += 1
    if j == N-1:
      if count > m_max:
        m_max = count
  else:
    if count > m_max:
      m_max = count
    count = 0
print(m_max)
### BUGGY CODE ###


n = int(input())

xs = sorted(map(int, input().split()))
ys = sorted(map(int, input().split()))
zs = sorted(map(int, input().split()))

bs = [0] * n
for i in range(n):
    for j in range(n):
        if xs[j] < ys[i]:
            bs[i] += 1
        else:
            break

cs = [0] * n
for i in range(n):
    for j in range(n):
        if ys[j] < zs[i]:
            cs[i] += bs[j]
        else:
            break

print(sum(cs))


### FIXED CODE ###


n = int(input())

xs = sorted(map(int, input().split()))
ys = sorted(map(int, input().split()))
zs = sorted(map(int, input().split()))

bs = [0] * n
j = 0
for i in range(n):
    while j < n and xs[j] < ys[i]:
        j += 1
    bs[i] = j

cs = [0] * n
j = 0
k = 0
for i in range(n):
    while j < n and ys[j] < zs[i]:
        k += bs[j]
        j += 1
    cs[i] = k

print(sum(cs))
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
arr = list(sorted(list(map(int, input().split()))))
bc = []
for _ in range(m):
    b, c = map(int, input().split())
    bc.append([b, c])

bc = list(sorted(bc, key=lambda x: x[1], reverse=True))
ans = 0

for bci in bc:
    d = bisect.bisect_left(arr, bci[1])
    arr = arr[min(d, bci[0]) :]
    ans += min(d, bci[0]) * bci[1]
print(ans + sum(arr))


### FIXED CODE ###

# 書き換える枚数は確定できる
# cの大きい順にしたものでaの小さい順にしたものを置き換えるイメージ
# なんか尺取っぽくなった

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

bcs = []
for _ in range(m):
    bc = list(map(int, input().split()))
    bcs.append(bc)

bcs = sorted(bcs, key=lambda x: x[1], reverse=True)
ans = 0

i = 0
for b in bcs:
    while i < n and arr[i] < b[1] and b[0] > 0:
        ans += b[1]
        b[0] -= 1
        i += 1
print(ans + sum(arr[i:]))
### BUGGY CODE ###

N = int(input())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
Isx = sorted(range(N), key=lambda i: (xys[i][0], xys[i][1]))
Isy = sorted(range(N), key=lambda i: (xys[i][1], xys[i][0]))
#print(Isx)
#print(Isy)
M = set()
for i in range(N):
  p, q = Isx[i-1], Isx[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
for i in range(N):
  p, q = Isy[i-1], Isy[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
#print(M)
F = [{i} for i in range(N)]
S = list(M)
S.sort(reverse=True)
#print(S)
r = 0
while S:
  cost, p, q = S.pop()
  for i in range(N):
    s = F[i]
    if p in s:
      break
  for j in range(N):
    s = F[j]
    if q in s:
      break
  #print(i, j)
  if i != j:
    r += cost
    s = F[i]|F[j]
    F.pop(max(i, j))
    F.pop(min(i, j))
    F.append(s)
  #print(F)
print(r)


### FIXED CODE ###

N = int(input())
xys = []
for i in range(N):
  x, y = map(int, input().split())
  xys.append((x, y))
Isx = sorted(range(N), key=lambda i: (xys[i][0], xys[i][1]))
Isy = sorted(range(N), key=lambda i: (xys[i][1], xys[i][0]))
#print(Isx)
#print(Isy)
M = set()
for i in range(1, N):
  p, q = Isx[i-1], Isx[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
for i in range(1, N):
  p, q = Isy[i-1], Isy[i]
  a, b = xys[p]
  c, d = xys[q]
  cost = min(abs(a-c), abs(b-d))
  M.add((cost, p, q))
#print(M)
S = list(M)
S.sort(reverse=True)
#print(S)
r = 0
UF = list(range(N))
def par(m):
  if UF[m] == m:
    return m
  ret = par(UF[m])
  UF[m] = ret
  return ret
while S:
  cost, p, q = S.pop()
  i = par(p)
  j = par(q)
  if i != j:
    r += cost
    UF[i] = j
  #print(UF)
print(r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ in range(n+1)] #グラフ
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=set()
def dfs(v):
    visited.add(v)
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if not g[v][i] in visited:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
ans_chr=""
for i in range(1,n+1):
    ans_chr=ans_chr+str(ans[i])+" "
print(ans_chr)


### FIXED CODE ###

import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ in range(n+1)] #グラフ
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=[0]*(n+1)
def dfs(v):
    visited[v]+=1
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if visited[g[v][i]]==0:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
print(" ".join(map(str, ans[1:])))
### BUGGY CODE ###

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

s=set()
l, r = map(int, input().split())
for i in range(l, r+1):
  s.add(i)
  
for i in range(m-1):
  l, r = map(int, input().split())
  t = set()
  for j in range(l, r+1):
    t.add(j)
    
  s = s & t
  
print(len(s))

### FIXED CODE ###

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

max_left = 1
min_right = n

for i in range(m):
    left, right = map(int, input().split())
    max_left = max(max_left, left)
    min_right = min(min_right, right)

print(max(min_right - max_left + 1, 0))
### BUGGY CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for i in range(len(L)-1):
  for j in range(i+1,len(L)):
    left=bisect.bisect_left(L, L[i]+L[j])
    right=bisect.bisect_right(L, L[j]-L[i])
    if left > j:
      ans+=left-j-1
 # break
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for i in range(len(L)-1):
  for j in range(i+1,len(L)):
    left=bisect.bisect_left(L, L[i]+L[j])
    if left > j:
      ans+=left-j-1
print(ans)
### BUGGY CODE ###

import operator
import functools
prod = functools.partial(functools.reduce, operator.mul)
n = int(input())

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




if(ans > 10**18):
    print("-1")
else:
    print(ans)

### FIXED CODE ###

from collections import deque
import sys
n = int(input())

a = list(map(int,input().split()))
a.sort()
if(a[0] == 0):
    print("0")
    sys.exit()
ans = 1
for i in range(n):

    ans = ans * a[i]
    if(ans > 10**18):
        print("-1")
        sys.exit()
     




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

import collections
import itertools

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) - 1, input().split())
gy, gx = map(lambda x:int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

seen = [[-1] * w for _ in range(h)]
seen[sy][sx] = 0
que = collections.deque()
que.append((sy, sx))

cnt = 0
while True:
    if seen[gy][gx] != -1:
        break
    
    while que:
        py, px = que.popleft()
        for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            ny = py + dy
            nx = px + dx
            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                seen[ny][nx] = cnt
                que.append((ny, nx))
    
    flag = True
    d = [-2, -1, 0, 1, 2]
    for py in range(h):
        for px in range(w):
            if seen[py][px] == cnt:
                for i in range(5):
                    for j in range(5):
                        ny = py + d[i]
                        nx = px + d[j]
                        if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                            seen[ny][nx] = cnt + 1
                            que.append((ny, nx))
                            flag = False
    cnt += 1
    if flag:
        break

print(seen[gy][gx])

### FIXED CODE ###

import collections
import itertools

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) - 1, input().split())
gy, gx = map(lambda x:int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

seen = [[-1] * w for _ in range(h)]
seen[sy][sx] = 0
que = collections.deque()
que.append((sy, sx))
tmp2 = [(sy, sx)]
cnt = 0
while True:
    tmp1 = []
    for sy, sx in tmp2:
        if maze[sy][sx] == ".":
            que.append((sy,sx))
            tmp1.append((sy, sx))
            while que:
                py, px = que.popleft()
                for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    ny = py + dy
                    nx = px + dx
                    if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                        seen[ny][nx] = cnt
                        que.append((ny, nx))
                        tmp1.append((ny, nx))
                        maze[sy][sx] = "#"
                        
    if seen[gy][gx] != -1:
        break

    flag = True
    d = [-2, -1, 0, 1, 2]
    tmp2 = []
    for py, px in tmp1:
        for i in range(5):
            for j in range(5):
                ny = py + d[i]
                nx = px + d[j]
                if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                    seen[ny][nx] = cnt + 1
                    que.append((ny, nx))
                    flag = False
                    tmp2.append((ny, nx))
    cnt += 1
    if flag:
        break
    if seen[gy][gx] != -1:
        break

print(seen[gy][gx])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)


## input
N,Q = map(int, sys.stdin.readline().rstrip().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, sys.stdin.readline().rstrip().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, sys.stdin.readline().rstrip().split())
  cnt[p-1] += x

## solve
@lru_cache(maxsize=1000)
def dfs(p,q):
  if p in route[q]:
    route[q].remove(p)
  for r in route[q]:
    cnt[r] += cnt[q]
    dfs(q,r)

dfs(-1,0)
for c in cnt[:-1]:
  print(c,end=" ")
print(cnt[-1])


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
stk = deque([0])
cost = [-1 for _ in range(N)]
cost[0] = cnt[0]
while len(stk) > 0:
  p = stk.pop()
  for q in route[p]:
    if cost[q] >= 0:
      continue
    cost[q] = cost[p] + cnt[q]
    stk.append(q)

print(*cost)
### BUGGY CODE ###

N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
while sw:
    tab = set()
    c = 0
    for i in range(1, N + 1):
        if Cs[i] == N - 1:
            continue
        a = 0
        b = 0
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                break
            Cs[a] += 1
            Cs[b] += 1
        else:
            tab.add((a, b))
    if c == 0:
        d = 0
        break
    d += 1
print(d - 1)

### FIXED CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))
### BUGGY CODE ###

import math
import copy

n = int(input())
#n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
num = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
#s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

kotae = 0
for i in range(0,n-1):
    for j in range(i+1,n):
        if(abs(i-j) == num[i]+num[j]):
            kotae += 1

print(kotae)


### FIXED CODE ###

import math
import copy

n = int(input())
#n, k = [int(i) for i in input().split()]
#table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
num = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
# s = [input() for i in range(n)]
#s = input()
# list = list(s)
# dp = [[0 for _ in range(2)] for _ in range(13)]
#s = [input() for i in range(n)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

kotae = 0
temp = 0
a = {}
b = {}

for i in range(n):
    temp = i - num[i]
    if (temp in a):
        a[temp] += 1
    else:
        a[temp] = 1

for i in range(n):
    temp = i + num[i]
    if (temp in b):
        b[temp] += 1
    else:
        b[temp] = 1

for i in range(200000):
    if ((i in a) and (i in b)):
        kotae += a[i] * b[i]

print(kotae)
### BUGGY CODE ###

K, S = [ int(i) for i in input().split() ]
count = 0
for X in range(K+1):
    for Y in range(K+1):
        for Z in range(K+1):
            if X + Y + Z == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = [ int(i) for i in input().split() ]
count = 0
for X in range(K+1):
    for Y in range(K+1):
        if (X + Y) <= S and S - (X+Y) <= K:
            count += 1
print(count)
### BUGGY CODE ###

n = int(input())
print(sum([i for i in range(0, n)]))

### FIXED CODE ###

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

S = input()
Q = int(input())

S_list = list(S)

for i in range(Q):
    Query = input()
    #Query = Query.replace(' ', '')
    #Query = list(Query)
    T, F, C = 0, 0, ''
    if Query[0] == '2':
        T = int(Query[0])
        F = int(Query[2])
        C = Query[4]
    else:
        T = int(Query[0])
    
    if T == 1:
        S_list = S_list[::-1]
        
    if T == 2:
        if F == 1:
            S_list = S_list[::-1]
            S_list.append(C)
            S_list = S_list[::-1]
        else:
            S_list.append(C)
            
print(''.join(S_list))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

S_list = list(S)

r = 1
a = []
b = []
d = deque(a)

for i in range(Q):
    q = input().split()
    if q[0] == '1':
        r *= -1
        continue
    elif len(q) == 3:
        if q[1] == '1':
            if r == -1:
                b.append(q[2])
            else:
                d.appendleft(q[2])
        else:
            if r == -1:
                d.appendleft(q[2])
            else:
                b.append(q[2])
                
answer = list(d) + S_list + b

if r == -1:
    answer = answer[::-1]
    
print(''.join(answer))
### BUGGY CODE ###

def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    ma = 0

    for i in range(len(a)+1):
        sum = 0
        cnt = i
        for j in range(i):
            sum += a[j]
        if(sum>k):
            break
        for j in range(len(b)):
            sum += b[j]
            if(sum>k):
                break
            else:
                cnt += 1
        ma = max(ma,cnt)
        
    print(ma)
            
main()

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

n = int(raw_input())
F = [0] * (n+1)

def makeFibonacci(n):
    global F
    F[0] = 1
    F[1] = 1
    for i in xrange(2,n+1):
        F[i] = makeFibonacci(i-2) + makeFibonacci(i-1)
    return F[n]

def main():
    ans = makeFibonacci(n)
    print ans
    return 0

main()

### FIXED CODE ###

n = int(raw_input())
F = [0] * (n+1)



def fibonacci(n):
    global F
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    if F[n] != 0:
        return F[n]
    F[n] = fibonacci(n-2) + fibonacci(n-1)
    return F[n]

def makeFibonacci(n):
    global F
    F[0] = 1
    F[1] = 1
    for i in xrange(2,n+1):
        F[i] = makeFibonacci(i-2) + makeFibonacci(i-1)
    return F[n]

def main():
    ans = fibonacci(n)
    print ans
    return 0

main()
### BUGGY CODE ###

#import sys

#input = sys.stdin.readline

import heapq

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=2
    k=1
    c=max(a,b)
    count=1
    sosu=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
    for i in range(len(sosu)):
        if a%sosu[i]==0 and b%sosu[i]==0:
            count+=1
            a//=sosu[i]
            b//=sosu[i]

    while m < c:
        m = 6 * k +1
        if a % m == 0 and b % m == 0:
            count += 1
        k += 1
    k = 1
    m = 2
    while m < c:
        m = 6 * k -1
        if a % m == 0 and b % m == 0:
            count += 1
        k += 1
    print(count)
#    for i in range(h):
#            print(aaa)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys

#input = sys.stdin.readline

#import heapq
import math
import fractions

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True

def main():
#    h,w,a,b = map(int, input().split())
    a,b=map(int,input().split())
    m=4
    k=1

    count=1
    if a>b:
        a,b=b,a
    sosu=set()
    a = fractions.gcd(a,b)
    if a%2==0:
        sosu.add(2)
        while a%2==0:
            a//=2
    if a%3==0:
        sosu.add(3)
        while a%3==0:
            a//=3
#    print(d)
    c=math.sqrt(a)+1
 #   print(c)
    while m<=c and m!=1:
        if a%m==0:
            sosu.add(m)
            while a%m==0:
                a//=m

        m+=1
#    print(sosu)
    if sosu==set() and a!=1:
        sosu.add(a)
    if sosuhante(a) and a!=1:
        sosu.add(a)
#    print(sosu)
    count+=len(sosu)
    print(count)
#    for i in range(h):
#            print(aaa)

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

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

for i in range(1,N+1):
    print(A.index(i)+1,end=" ")


### FIXED CODE ###

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

B=[]
for i in range(N):
    B.append([A[i]])

for i in range(N):
    B[i].append(i+1)

B.sort()

for i in range(N):
    print(B[i][1],end=" ")