Harryxun/stf_run huggingface dataset:
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    N = read_int()
    A = read_ints()
    T = [0, 0, 0]
    answer = 1
    modulo = 1000000007
    for a in A:
        answer = (answer*T.count(a))%modulo
        T[T.index(a)] += 1
    return answer


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


### FIXED CODE ###



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    N = read_int()
    A = read_ints()
    T = [0, 0, 0]
    answer = 1
    modulo = 1000000007
    for a in A:
        if a not in T:
            return 0
        answer = (answer*T.count(a))%modulo
        T[T.index(a)] += 1
    return answer


if __name__ == '__main__':
    print(solve())
a,b,x=map(int,input().split())

import numpy as np
if x>a*a*b/2:#半分よりも多い場合
    theta=np.arctan(2*(a*a*b)/a*a*a)
else:#半分に満たない場合
    theta=np.arctan((a*b*b)/(2*x))
theta = theta * 180 / np.pi
print(theta)

### FIXED CODE ###

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

from math import atan, degrees
if x>=a*a*b/2:#半分よりも多い場合
    rad=atan(2/a*(b-x/a**2))
else:
    rad=atan((a*b*b)/(2*x))
print(degrees(rad))
import math
a,b,c,d=map(int,input().split())
x=b-b//c-b//d+b//(c*d//math.gcd(c*d))
y=(a-1)-(a-1)//c-(a-1)//d+(a-1)//(c*d//math.gcd(c*d))
print(x-y)

### FIXED CODE ###

import math
a,b,c,d=map(int,input().split())
x=b-b//c-b//d+b//(c*d//math.gcd(c,d))
y=(a-1)-(a-1)//c-(a-1)//d+(a-1)//(c*d//math.gcd(c,d))
print(x-y)
import sys
N, C, K = list(map(int, input().split()))
listT = [int(input()) for _ in range(N)]

listT.sort()

def func(listT,bus):
    if len(listT)<2:
            print(bus+1)
            sys.exit()

    elif len(listT)>=2:
        for i in range(1,max(C,len(listT))):

            if listT[i]-listT[0]>K:
                bus += 1
                return func(listT[i:],bus)

        bus += 1

        if len(listT)<C:
            print(bus)
            sys.exit()


        return func(listT[C:],bus)

func(listT,0)


### FIXED CODE ###

import sys
N, C, K = list(map(int, input().split()))
listT = [int(input()) for _ in range(N)]

listT.sort(reverse = True)

count=0
while listT != []:
    bus =[]
    time = listT[0]
    count += 1
    while len(bus) != C and time - K <= listT[0]:
        bus.append(listT.pop(0))
        if listT ==[]:
            break

print(count)
#include <bits/stdc++.h>
using namespace std;

int main(void){

  int n,k;
  vector<int> p(n);
  cin >> n >> k;
  for(int i=0; i<n ; ++i){
    cin >> p.at(i);
  }
  vector<double> exps;
  vector<double> sums;

  for(int i=0; i<n ; ++i){
    double tmp = 0.0;
    for(int j=1 ; j <= p[i] ; ++j){
      tmp += j;
    }   
    tmp /= p[i];
    exps.push_back(tmp);
  }

  for(int i=0; i<n-(k-1) ; ++i){
    double tmp = 0;
    for(int j=0; j<k ; ++j){
      tmp += exps.at(i+j);
    }   
    sums.push_back(tmp);
  }

  sort(sums.begin(), sums.end(), greater<double>());

  // for debug
//  cout << "exps" << endl;
//  for(auto a: exps){
//    cout << a << ", " ;
//  }
//  cout << endl;
//  cout << "sums" << endl;
//  for(auto a: sums){
//    cout << a << ", " ;
//  }
//  cout << endl;

  cout << sums.at(0) << endl;

  return 0;
}

### FIXED CODE ###

#!/usr/bin/env python3

import numpy as np

n, k = map(int, input().split())
p = list(map(int, input().split()))
exps = []

for i in range(n):
    #exps.append(sum(list(range(1, p[i]+1)))/p[i])
    exps.append((1+p[i])/2)

exps = np.array(exps)
cumexps = exps.cumsum()
cumexps = np.insert(cumexps, 0, 0)

#print(exps)
#print(cumexps)

ans = -1
for i in range(n-k+1):
    tmp = -cumexps[i] + cumexps[i+k]
    if ans <= tmp:
        ans = tmp 

print(ans)
N, M = map(int, input().split())
MOD = 10**9 + 7
if M == 0:
    print(pat[N] % MOD)
else:
    A = [int(input()) for _ in range(M)]
    pat = [0] * (N+1)
    pat[1] = 1
    pat[2] = 2
    for i in range(3, N+1):
        pat[i] = (pat[i-1] + pat[i-2]) % MOD
    steps = []
    for i in range(M-1):
        d = A[i+1] - A[i]
        if d  > 2:
            steps.append(d)
        elif d == 1:
            steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10**9 + 7
A = [int(input()) for _ in range(M)]
pat = [0] * (N+3)
pat[1] = 1
pat[2] = 2
for i in range(3, N+1):
    pat[i] = (pat[i-1] + pat[i-2]) % MOD
if M == 0:
    print(pat[N] % MOD)
else:
    steps = []
    if len(A) > 1:
        for i in range(M-1):
            d = A[i+1] - A[i]
            if d > 2:
                steps.append(d-2)
            elif d == 1:
                steps.append(0)
    if A[0] != 1:
        steps = [A[0] - 1] + steps
    if A[-1] != N-1:
        steps += [N - A[-1] - 1]
    ans = 1
    for s in steps:
        ans = (ans * pat[s]) % MOD
    print(ans)
n=int(input())
a=list(map(int,input().split()))
l=[0]
r=[0]
ans=0
from  math import gcd
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
    r.append(gcd(r[i],a[-1]-i))
for i in range(n):
    ans=max(ans,gcd(l[i],r[-1-i]))

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[0]
r=[0]
ans=0
from  fractions import gcd
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
    r.append(gcd(r[i],a[-1-i]))
for i in range(n):
    ans=max(ans,gcd(l[i],r[-1-i]))

print(ans)
import numpy as np
n = int(input())
lst1 = np.array([list(range(1,n))])

if n==1:
  print(0)
else:
  print(lst1.sum())

### FIXED CODE ###

n = int(input())
print(int(n*(n-1)//2))
K, X = map(int, input().split())

if (500 * K - X） >= 0  :
  print('Yes') 
else:
  print('No') 


### FIXED CODE ###

K, X = map(int, input().split())

if 500 * K - X >= 0  :
  print('Yes') 
else:
  print('No')
while True:
n = [int(i) for i in input().split()]
count = 0
for a in range(1,4):
    for b in range(a+1,5):
        for c in range(b+1, 6):
            if a + b + c == 9:
                count += 1
print(count)

### FIXED CODE ###

while True:
    (n, x) = [int(i) for i in input().split()]
    if n == x == 0:
        break
    count = 0
    for a in range(1,n+1):
        for b in range(a+1,n+1):
            for c in range(b+1, n+1):
                if a + b + c == x:
                    count += 1
    print(count)
[n, m, k] = [int(x) for x in input().split()]

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

if sum(a)+sum(b) <= k:
    print(n+m)


else:
    if sum(a) < sum(b):
        small = a
        big = b
    else:
        small = b
        big = a

    # print(sum(small))

    if sum(small) == k:
        print(len(small))


    if sum(small) < k:
        count = 0
        while sum(small) < k:
            small.append(big.pop(0))
            count += 1
        
        print(len(small) + count)

    elif sum(small) > k:
        # print("here")
        while len(small) > 0 and sum(small) > k:
            small.pop(0)
        count = 0
        while len(small) > 0 and sum(small) <= k:
            small.append(big.pop(0))
            if sum(small) > k:
                small.pop()
            count += 1
        print(len(small))
        # print(small)

    


    
# ans = 0
# temp = 0
# for i in range(len(a)):
#     if temp+a[i] <= k:
#         temp+=a[i]
#         ans += 1

#     else:
#         break

# for i in range(len(b)):
#     if temp+b[i] <= k:
#         temp+=b[i]
#         ans += 1

#     else:
#         break

# print(ans)


# ans =0 


# while k > 0 and len(b)>0 and len(a)>0:
#     if len(a) > 0 and a[0] <= b[0]:
#         if k >= a[0]:
#             k -= a[0]
#             ans += 1
#             a.pop(0)
#         else:
#             break

#     elif len(b) > 0 and  b[0] <= a[0]:
#         if k >= b[0]:
#             k -= b[0]
#             ans += 1
#             b.pop(0)
#         else:
#             break


# if len(b)>0:
#     while len(b)>0 and k >= b[0]:
#         k -= b[0]
#         ans += 1
#         b.pop(0)

# elif len(a)>0:
#     while len(a)>0 and k >= a[0]:
#         k -= a[0]
#         ans += 1
#         a.pop(0)






### 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)
import itertools
f = lambda n:sum(i for i in range(n+1))

def sol():
    res = 0
    while q:
        x0 = q.popleft()
        x1 = q.popleft()
        res += f(max(x0, x1)) + f(min(x0, x1) -1)
    return res

s = input()

q = collections.deque()
for k, g in itertools.groupby(s):
    q.append(len(list(g)))
if len(q) % 2:
    q.append(1)

print(sol())


### FIXED CODE ###

def main():
  s = input().rstrip('\n')
  n = len(s)
  dp = [0] * (1 + n)
  for i,c in enumerate(s):
    if c == '<':
      dp[i+1] = dp[i] + 1
  for i in range(n-1, -1, -1):
    if s[i] == '>':
      dp[i] = max(dp[i], dp[i+1] + 1)
  return sum(dp)

print(main())
import sys
import math

a,b,x=(int(x) for x in input().split())

if a*a*b/2 <= x:
	T=a*(b-(x/(a*a)))
	c=2*T/a 
	d = math.atan2(c, a)
	d_deg=math.degrees(d)
else:
	e=2*X/(a*b)
	d = math.atan2(e, b)
	d_deg=math.degrees(d)
	
#print(d)
print(d_deg)
 

### FIXED CODE ###

import sys
import math

a,b,x=(int(x) for x in input().split())

if a*a*b/2 <= x:
	T=a*(b-(x/(a*a)))
	c=2*T/a 
	d = math.atan2(c, a)
	d_deg=math.degrees(d)
else:
	e=2*x/(a*b)
	d = math.atan2(b, e)
	d_deg=math.degrees(d)
	
#print(d)
print(d_deg)
h,w,k = map(int,input().split())
a = []
for i in range(h):
  b = input()
  tmp = []
  for j in range(w):
    tmp.append(b[j])
    if b[j] == "S":
      sx = i
      sy = j
  a.append(tmp)
ma = [[0]*w for i in range(h)]
def dfs(x,y):
  if ma[x][y] == 1:
    return
  ma[x][y] = 1
  if x > 0 and a[x-1][y]== ".":
    dfs(x-1,y)
  if y > 0 and a[x][y-1]== ".":
    dfs(x,y-1)
  if x <h-1 and a[x+1][y]==".":
    dfs(x+1,y)
  if y <w-1 and a[x][y+1]==".":
    dfs(x,y+1)
dfs(sx,sy)
ans = float("inf")
for i in range(h):
  for j in range(w):
    if ma[i][j] == 1:
      ans = min(ans,1+(h-i-1)//k+ (1 if (h-i-1)%k else 0),1+(w-j-1)//k+ (1 if (w-j-1)%k else 0),
               1+(i)//k+ (1 if (i)%k else 0),1+(j)//k+ (1 if (j)%k else 0))
print(ans)

### FIXED CODE ###

from collections import deque
h,w,k = map(int,input().split())
a = []
for i in range(h):
  b = input()
  tmp = []
  for j in range(w):
    tmp.append(b[j])
    if b[j] == "S":
      sx = i
      sy = j
  a.append(tmp)
ma = [[0]*w for i in range(h)]
def dfs(x,y,z):
  if ma[x][y] == 1:
    return
  if z>k:
    return
  ma[x][y] = 1
  if x > 0 and a[x-1][y]== ".":
    que.append([x-1,y,z+1])
  if y > 0 and a[x][y-1]== ".":
    que.append([x,y-1,z+1])
  if x <h-1 and a[x+1][y]==".":
    que.append([x+1,y,z+1])
  if y <w-1 and a[x][y+1]==".":
    que.append([x,y+1,z+1])
que = deque([[sx,sy,0]])
while que:
  x,y,z = que.popleft()
  dfs(x,y,z)
ans = float("inf")
for i in range(h):
  for j in range(w):
    if ma[i][j] == 1:
      ans = min(ans,1+(h-i-1)//k+ (1 if (h-i-1)%k else 0),1+(w-j-1)//k+ (1 if (w-j-1)%k else 0),
               1+(i)//k+ (1 if (i)%k else 0),1+(j)//k+ (1 if (j)%k else 0))
print(ans)
from math import factorial
def comb(n,k):
    return factorial(n)//factorial(k)//factorial(n-k)
def main():
    n,k=map(int,input().split())
    mod=10**9+7
    for i in range(1,k+1):
        print(comb(n-k+1,i)*comb(k-1,i-1)%mod)
main()

### FIXED CODE ###

def ExtGCD(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ExtGCD(b, a % b)
        x -= (a // b) * y
        return d, y, x
def ModInv(a, mod):
    return ExtGCD(a, mod)[1] % mod
def ModComb(n, k, mod):
    if n < k or n < 0 or k < 0:
        return 0
    elif n == 0 or k == 0:
        return 1
    q, a = 1, 1
    for i in range(n-k+1, n+1):
        q = (q * i) % mod
    for i in range(2, k+1):
        a = (a * i) % mod
    return int(q * ModInv(a, mod) % mod)
def main():
    n,k=map(int,input().split())
    mod=10**9+7
    for i in range(1,k+1):
        print(ModComb(n-k+1,i,mod)*ModComb(k-1,i-1,mod)%mod)
        # 最後のに%modつけるの忘れてた。。。。。。
main()
# -*- coding: utf-8 -*-
s=str(input())
n=len(n)
print('x'*n)

### FIXED CODE ###

# -*- coding: utf-8 -*-
s=str(input())
n=len(s)
print('x'*n)
n,m = map(int, input().split())
a = [[0]*m for i in range(n)]
ans = 0
if n == 1:
    if m == 1:
        ans = 1
    elif m == 2:
        ans = 0
    else:
        ans = m - 2

if n == 2:
    ans = 0

if n > 2:
    if m == 1:
        ans = n-2
    elif m == 2:
        ans = 0
    else:
        ans = (n-2)*(m-2)
    



print(ans)


### FIXED CODE ###

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

ans = 0
if n == 1:
    if m == 1:
        ans = 1
    elif m == 2:
        ans = 0
    else:
        ans = m - 2

if n == 2:
    ans = 0

if n > 2:
    if m == 1:
        ans = n-2
    elif m == 2:
        ans = 0
    else:
        ans = (n-2)*(m-2)
    



print(ans)
N,A,B=map(int,iput(),split())
if A*N<B :
  print(A*N)
else:
    print(B)

### FIXED CODE ###

N,A,B=map(int,input().split())
if A*N<B :
  print(A*N)
else:
  print(B)
def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = cd.copy()
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

if __name__ == "__main__":
  main() 

### FIXED CODE ###

def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = cd.copy()
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

if __name__ == "__main__":
  main()
N,Q = map(int,input().split())
S = input()
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    s = S[l-1:r]
    print(s.count('AC'))


### FIXED CODE ###

S = input()

if S == 'A':
    print('T')
elif S == 'C':
    print('G')
elif S == 'G':
    print('C')
elif S == 'T':
    print('A')
def ok(m,e):
    for z in range(m+1):
        if z**3 > e: return False
        for y in range(m-z+1):
            if z**3 + y**2 > e: break
            x = m-z-y
            if z**3 + y**2 + x == e: return True
    return False

while True:
    E = int(input())
    if E == 0: break
    m = 1
    while not ok(m,E):
        m += 1
    print(m)

### FIXED CODE ###

import math
while True:
    E = int(input())
    if E == 0: break
    ans = 10**10
    z = 0
    while z**3 <= E:
        y = int(math.sqrt(E - z**3))
        x = E - z**3 - y**2
        ans = min(x+y+z, ans)
        z += 1
    print(ans)
from operator import mul
from functools import reduce
n = int(input())
a = list(map(int,input().split()))

if 0 in a:
	print(0)
else:
	M = 10**18
	ans = reduce(mul, a)
	if ans > M:
		print(-1)
		break
	else:
		print(ans)


### FIXED CODE ###

n = int(input())
s = sorted(map(int,input().split()))
M = 10 ** 18
ans = 1
for ss in s:
	ans *= ss
	if ans > M:
		ans = -1
		break
	elif ans == 0:
		break
print(ans)
n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]

large = 10**9 +7
count = [0]*(n+1)
itr = 0
count[0] = 1
if a[0] != 1 :
    count[1] = 1
else:
    count[1] = 0
    itr = 1

for i in range(2,n+1):
    if itr<len(a) and a[itr] == i:
        itr +=1
        continue
    else:
        count[i] = (count[i-1] + count[i-2])%large

print(count[n])




### 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
if 1 not in a:
    dp[1]=1
for i in range(2,n+1):
    if i in a :
        continue
    else:
        dp[i]= dp[i-1] + dp[i-2]
        dp[i]%= mod


print(dp[n])
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


def main():
    n = int(input())
    graph = np.zeros((n + 1, n + 1))
    for i in range(n-1):
        a, b, c = [int(x) for x in input().split()]
        graph[a, b] = c
    graph = csr_matrix(graph)
    q, k = [int(x) for x in input().split()]
    dist = dijkstra(csgraph=graph, directed=False, indices=k)
    for j in range(q):
        l, r = [int(x) for x in input().split()]
        print(int(dist[l]+dist[r]))


main()


### FIXED CODE ###

import sys
import collections

n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b, c = [int(x) for x in input().split()]
    adj[a].append((b, c))
    adj[b].append((a, c))
q, k = [int(x) for x in input().split()]
dist = [0] * (n + 1)
queue = collections.deque()
queue.append(k)
while len(queue) > 0:
    u = queue.popleft()
    for v, weight in adj[u]:
        if dist[v] == 0:
            queue.append(v)
            dist[v] = dist[u] + weight
for j in range(q):
    l, r = [int(x) for x in input().split()]
    print(dist[l] + dist[r])
# print(*data, sep='\n')
N,M=int(input().split())

a = list(map(int,input().strip().split()))[:n] 
  
number=0
total=0
for i in range(N):
  v=a[i]
  total=total+v
for i in range(N):
  v=a[i]
  if v < (1/(4*M))*total:
    number=number
  else:
    number = number+1
if number >= M:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N,M=input().split()
N,M=[int(N),int(M)]
 
a = list(map(int,input().strip().split()))[:N]
  
number=0
total=0
for i in range(N):
  v=a[i]
  total=total+v
for i in range(N):
  v=a[i]
  if v < (1/(4*M))*total:
    number=number
  else:
    number = number+1
if number >= M:
  print("Yes")
else:
  print("No")
N,M = [int(i) for i in input().split()]

q = [0] * N
for _ in range(N):
    a,b = [int(i) for i in input().split()]
    q[a-1] += 1
    q[b-1] += 1

for i in range(M):
    if q[i]%2 != 0:
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

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

q = [0] * N
for _ in range(M):
    a,b = [int(i) for i in input().split()]
    q[a-1] += 1
    q[b-1] += 1

for i in range(M):
    if q[i]%2 != 0:
        print('NO')
        exit()

print('YES')
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))


x = 0
for i in range(k-1, n):
	s = 0
	tmp = []
	for j in range(i-(k-1), i+1):
		tmp.append(p[j])
		s += p[j]
	if x < s:
		x = s
		y = tmp

ans = 0
for i in y:
	a = 0
	for j in range(1, i+1):
		a += j
	ans += a / i

print(ans)


### FIXED CODE ###

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

a = set(a)

if len(a) != n:
	print('NO')
else:
	print('YES')
def acinput():
    return list(map(int,input().split(" ")))


N,M=acinput()
a=[0]*(N+100)
for i in range(M):
    a[int(input())]=1


Mod=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    if x<0:
        return 0

    res=0
    zeroflg=True
    if  x-1>=0 and a[x-1]!=1:
        res+=solve(x-1)%Mod
        zeroflg=False
    if x-2>=0 and a[x-2]!=1:
        res+=solve(x-2)%Mod
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

dp=[-1]*(N+10)
dp[0]=1
dp[1]=1

print(solve(N)%Mod)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


dp = [-1]*(N+1)
dp[0] = 1
dp[1] = 1

print(solve(N) % Mod)


'''
5 1
1
'''
print(int(input())-N)


### FIXED CODE ###

N=int(input())
print(1110-N)
from bisect import bisect_right

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)

res = 0
for b, c in bc:
    count = bisect_right(a, c, hi=b)
    res += count * c
    if count < len(a):
        a = a[count:]
    else:
        a = []
        break

print(res + sum(a))


### FIXED CODE ###

from bisect import bisect_right

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)

res = 0
fin = 0
for b, c in bc:
    count = bisect_right(a, c, lo=fin, hi=min(fin+b, len(a))) - fin
    fin += count
    res += count * c
for i in range(fin, len(a)):
    res += a[i]

print(res)
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

dp=[-1]*(W+1)
dp[0]=0
for i in range(N):
  w,v=WV[i]
  for j in range(W-w,-1,-1):
    if dp[j]!=-1:
      dp[j+w]=max(dp[j+w],dp[j]+v)
print(max(dp))

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

dp=np.full(10**5+10,10**18,int)
dp[0]=0
for w,v in WV:
  np.minimum(dp[v:], dp[:-v].copy()+w, out=dp[v:])
print(np.where(dp<=W)[0][-1])
n = int(input())
a = list(map(int, input().split()))
d = [x1 - x0 for x1, x0 in zip(a[1:], a) if x1 - x0 != 0]

def sign(x):
    if x > 0:
        return 1
    elif x < 0:
        return -1
    else:
        return 0

cnt = 0
prev = d[0]
kept = 1
for i in range(1, len(d)):
    if sign(d[i]) == prev:
        kept = 1
    else:
        if kept == 1:
            cnt += 1
            kept = 0
        else:
            kept = 1
    prev = d[i]
else:
    cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = n
prev = a[0]
trend ='N'

for i in range(1, n):
    if a[i] > prev:
        if (trend == 'U' or trend == 'N'):
            cnt -= 1
            trend ='U'
        else:
            trend = 'N'
    if a[i] < prev:
        if (trend == 'D' or trend == 'N'):
            cnt -= 1
            trend = 'D'
        else:
            trend = 'N'
    if a[i] == prev:
        cnt -= 1
    prev = a[i]
print(cnt)
# AtCoder Grand Contest 041
# A - Table Tennis Training

def f(A,B,n):
    judge=abs(B-A)
    if judge%2==0:
        n+=judge//2
        return(n)
    else:
        if 1-A < N-B :
            if A>2:
                A-=1
                B-=1
                n+=1
            else:
                B-=1
                n+=1
            return f(A,B,n)
        else:
            if B<N:
                B+=1
                A+=1
                n+=1
            else:
                A+=1
                n+=1
            return f(A,B,n)



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

print(f(A,B,0))

### FIXED CODE ###

# AtCoder Grand Contest 041
# A - Table Tennis Training

def f(A,B,n) :
    judge=B-A

    if judge%2==0 :
        n+=judge//2
        return(n)

    else :
        if abs(A-1) < abs(N-B) :
            if A==1 :
                A=A
                B-=1
                n+=1
            else:
                B-=A-1
                n+=A-1
                A-=A-1
            return f(A,B,n)
        else :
            if B==N :
                B=B
                A+=1
                n+=1
            else :
                A+=abs(N-B)
                n+=abs(N-B)
                B+=abs(N-B)
            return f(A,B,n)

N,A,B=map(int,input().split())
print(f(A,B,0))