CodeEff/ECCO huggingface dataset:
# Original solution
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

dp = [False] * (K+1)

for i in range(1, K+1):
    for j in range(N):
        if 0 <= i - a[j] and not dp[i-a[j]]:
            dp[i] = True

print(("First" if dp[K] else "Second"))

# Optimized solution
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

dp = [False] * (K+1)

for i in range(1, K+1):
    for j in range(N):
        if 0 <= i - a[j] and not dp[i-a[j]]:
            dp[i] = True
            break

print(("First" if dp[K] else "Second"))
# Original solution
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
dp = [False]*(k+1)
for i in range(1,k+1):
    for j in range(n):
        if i-a[j]<0:
            break
        if dp[i-a[j]]==False:
            dp[i] = True
if dp[k]==True:
    print("First")
else:
    print("Second")


# Optimized solution
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
dp = [False]*(k+1)
for i in range(1,k+1):
    for j in range(n):
        if i-a[j]<0:
            break
        if dp[i-a[j]]==False:
            dp[i] = True
            break
if dp[k]==True:
    print("First")
else:
    print("Second")
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[False]*(k+1)
for i in range(k+1):
    for j in range(n):
        if i-a[j]>=0:
            dp[i]|=not dp[i-a[j]]
if dp[k]:
    print('First')
else:
    print('Second')

# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[False]*(2*k+1)
for i in range(k+1):
    for j in a:dp[i+j]|=not dp[i]
if dp[k]:
    print('First')
else:
    print('Second')
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[0]*(2*k+1)
for i in range(k+1):
    for j in a:dp[i+j]|=~dp[i]
if dp[k]:
    print('First')
else:
    print('Second')

# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[False]*(2*k+1)
for i in range(k+1):
    for j in a:dp[i+j]|=not dp[i]
if dp[k]:
    print('First')
else:
    print('Second')
# Original solution
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

dp = [0] * (K + 1)

for i in range(1, K + 1):
    for j in range(N):
        if i - a[j] >= 0 and dp[i - a[j]] == 0:
            dp[i] = 1

print(('First' if dp[K] else 'Second'))


# Optimized solution
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

dp = [0] * (K + 1)

for i in range(1, K + 1):
    for j in a:
        if i - j >= 0 and dp[i - j] == 0:
            dp[i] = 1

print(('First' if dp[K] else 'Second'))
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
mini=min(a)
dp1=[-1 for i in range(k+1)]
dp2=[-1 for i in range(k+1)]
for x in range(k+1):
	if x == 0 or mini > x:
		dp1[x]=False
		dp2[x]=False
		continue
	dp1[x]=False
	dp2[x]=False
	for v in a:
		if v>x:
			continue
		dp1[x]=dp1[x] or not dp2[x-v]
		dp2[x]=dp2[x] or not dp1[x-v]

if dp1[k]:
	print("First")
else:
	print("Second")

# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
mini=min(a)
dp=[-1 for i in range(k+1)]

for x in range(k+1):
	if x == 0 or mini > x:
		dp[x]=False
		continue
	dp[x]=False
	for v in a:
		if v>x:
			continue
		dp[x]=dp[x] or not dp[x-v]

if dp[k]:
	print("First")
else:
	print("Second")
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))

dp=[False]*(k+1)

for i in range(1,len(dp)):
  for x in a:
    if i-x>=0:
      dp[i]|=not dp[i-x]

print((("Second","First")[dp[k]]))

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

dp=[False]*(k+1+max(a))

for i in range(1+k):
  if not dp[i]:
    for x in a:
      dp[i+x]=True

print((("Second","First")[dp[k]]))
# Original solution
import math,itertools,fractions,heapq,collections,bisect,sys,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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  n,k=LI()
  dp=[0]*100100
  l=LI()

  for i in range(k):
    for x in l:
      if i+x<=k:
        if dp[i+x]==0 and dp[i]==0:
          dp[i+x]=1

  # print(dp[:k+1])
  return 'First' if dp[k] else 'Second'

# main()
print((main()))


# Optimized solution
import math,itertools,fractions,heapq,collections,bisect,sys,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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  n,k=LI()
  l=LI()

  dp=[0]*100100

  for i in range(k):
    for x in l:
      y=dp[i]

      if y==0 and i+x<100100:
        dp[i+x]=1

  if dp[k]==1:
    return 'First'
  return 'Second'

# main()
print((main()))
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * (k+1)
for i in range(k+1):
    dp[i] = 0
    for j in a:
        if j > i:
            break
        dp[i] = dp[i] or (1 - dp[i-j])
print((['Second', 'First'][dp[k]]))

# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * (k+1) #残りの石iで回ってきたときの勝敗
for i in range(k+1):
    dp[i] = 0
    for j in a:
        if j > i:
            break
        if 1 - dp[i-j]:
            dp[i] = 1
            break
print((['Second', 'First'][dp[k]]))
# Original solution
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
a_list = list(map(int, input().split()))
dp = [False]*(k+1)

for i in range(1,k+1):
  for j in range(n):
    if i-a_list[j] >= 0:
      dp[i] |= not(dp[i-a_list[j]])


if dp[k]:
  print('First')
else:
  print('Second')

# Optimized solution
import sys
input = sys.stdin.readline

def main():
  n, k = list(map(int, input().split()))
  a_list = list(map(int, input().split()))
  dp = [False]*(k+1)

  for i in range(1,k+1):
    for j in range(n):
      if i-a_list[j] >= 0:
        dp[i] |= not(dp[i-a_list[j]])


  if dp[k]:
    print('First')
  else:
    print('Second')
main()
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
S = [ord(c) for c in input().rstrip()]
Q = int(eval(input()))
k = list(map(int, input().split()))

dd = ord('D')
mm = ord('M')
cc = ord('C')

for l in k:
    D = M = tmp = ans = 0
    for i in range(N):
        if i >= l:
            if S[i-l] == dd:
                tmp -= M
                D -= 1
            if S[i-l] == mm:
                M -= 1
        if S[i] == dd:
            D += 1
        if S[i] == mm:
            M += 1
            tmp += D
        if S[i] == cc:
            ans += tmp
    print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    N = int(eval(input()))
    S = input().rstrip()
    Q = int(eval(input()))
    k = list(map(int, input().split()))

    for l in k:
        D = 0
        M = 0
        tmp = 0
        ans = 0
        for i in range(N):
            if i >= l:
                if S[i-l] == 'D':
                    tmp -= M
                    D -= 1
                if S[i-l] == 'M':
                    M -= 1
            if S[i] == 'D':
                D += 1
            if S[i] == 'M':
                M += 1
                tmp += D
            if S[i] == 'C':
                ans += tmp
        print(ans)

main()
# Original solution
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print(('\n'.join(map(str,x))))
def printline(x):print((' '.join(map(str,x))))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()

ans = []
for k in K:
    m = 0
    c = 0
    a = [0]
    d = S.find('D')
    e = S.rfind('D')
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a[-1] += m
    a.append(a[-1])
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a[-1] += m
        if S[i-1]=='M':
            m -= 1
            a[-1] -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            if i==e:
                break
            else:
                a.append(a[-1])
    ans.append(sum(a))
printrows(ans)




# Optimized solution
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print(('\n'.join(map(str,x))))
def printline(x):print((' '.join(map(str,x))))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()
d = S.find('D')
e = S.rfind('D')
ans = []
for k in K:
    m = 0
    c = 0
    a = 0
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a += m
    b = a
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a += m
        if S[i-1]=='M':
            m -= 1
            a -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            b += a
            if i==e:
                break
    ans.append(b)
printrows(ans)
# Original solution
import sys
rl = sys.stdin.readline
N = int(rl())
S = rl()
Q = int(rl())
ks = list(map(int,rl().split()))

ans = []
for k in ks:
    d = m = 0
    dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)

print(*ans,sep='\n')


# Optimized solution
import sys
input = sys.stdin.readline
N = int(input())
S = input()
Q = int(input())
K = list(map(int,input().split()))

ans = []
for k in K:
    d = m = dm = dmc = 0
    for i in range(N):
        if i >= k:
            if S[i-k] == 'D':
                d -= 1
                dm -= m
            elif S[i-k] == 'M':
                m -= 1
        if S[i] == 'D':
            d += 1
        elif S[i] == 'M':
            m += 1
            dm += d
        elif S[i] == 'C':
            dmc += dm
    ans.append(dmc)
print(*ans, sep='\n')
# Original solution
N = int(eval(input()))
S = input().strip()
qn = int(eval(input()))
qs = list(map(int, input().split()))
dp = [[0,0,0]]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            dd, mm, dmm = dp[ll]
            As[j] += dm - dmm - dd*(m-mm)
    dp.append([d,m,dm])
for a in As:
    print(a)


# Optimized solution
N = int(eval(input()))
S = input().strip()
qn = int(eval(input()))
qs = list(map(int, input().split()))
dd,mm,cc = [0],[0],[0]
As = [0]*qn
d=m=dm=0
for i, w in enumerate(S):
    i += 1
    if w=="D":
        d+=1
    elif w == "M":
        m+=1
        dm+=d
    elif w == "C":
        for j, q in enumerate(qs):
            ll = max(i-q, 0)
            As[j] += dm - cc[ll] - dd[ll]*(m-mm[ll])
    dd.append(d)
    mm.append(m)
    cc.append(dm)
for a in As:
    print(a)
# Original solution
# -*- coding: utf-8 -*-


s = input().strip()
#----------
loc_A=len(s)+1
loc_Z=-1
for i in range(len(s)):
    if s[i] == "Z" and loc_Z < i:
        loc_Z = i
    elif s[i] == "A" and i < loc_A:
        loc_A = i

print(( loc_Z - (loc_A - 1) ))


# Optimized solution
# -*- coding: utf-8 -*-

s=input().strip()

for i,word in enumerate(s):
    if word == "A":
        start = i
        break

for i,word in enumerate( reversed(s) ):
    if word == "Z":
        end = len(s)-1-i
        break

print(( end-start+1 ))
# Original solution
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    s,e = 0,0

    for i in range(len(S)):
        if S[i] == 'A':
            s = i
            break
    for i in range(len(S)):
        if S[::-1][i] == 'Z':
            e = i
            break

    print((len(S) - s - e))




if __name__ == '__main__':
    main()


# Optimized solution
import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    A, Z = MAX, 0

    for i in range(len(S)):
        if S[i] == 'A':
            A = min(A, i)
        elif S[i] == 'Z':
            Z = max(Z, i)
    print((Z - A + 1))


if __name__ == '__main__':
    main()
# Original solution
string = input().rstrip("\n")
string_r = "".join(reversed(string))
print((len(string) - string_r.index("Z") - string.index("A")))

# Optimized solution
[print(len(string) - string[::-1].index("Z") - string.index("A")) for string in [input()]]
# Original solution
prime = [False] * (10 ** 6)
prime[0] = True
prime[1] = True

for i in range(2, 10 ** 6):
    if prime[i] == False:
        for j in range(i * 2, 10 ** 6, i):
            prime[j] = True

while True:
    a, d, n = list(map(int, input().split()))

    if a == 0:
        break

    cnt = 0
    for i in range(a, 10 ** 6, d):
        if prime[i] == False:
            cnt += 1
        if cnt == n:
            print(i)
            break

# Optimized solution
import math

prime = [False] * (10 ** 6)
prime[0] = True
prime[1] = True

limit = int(math.sqrt(10 ** 6) + 1)

for i in range(2, limit):
    if prime[i] == False:
        for j in range(i * 2, 10 ** 6, i):
            prime[j] = True

while True:
    a, d, n = list(map(int, input().split()))

    if a == 0:
        break

    cnt = 0
    for i in range(a, 10 ** 6, d):
        if prime[i] == False:
            cnt += 1
        if cnt == n:
            print(i)
            break
# Original solution
import sys

N = int(sys.stdin.readline().strip())
T = list(map(int, sys.stdin.readline().strip().split()))
A = list(map(int, sys.stdin.readline().strip().split()))

# i番目の山が取りうる高さの下限、上限
cand = [[1, float("inf")] for _ in range(N)]

l_max = 0
for i in range(N):
    if l_max < T[i]:
        l_max = T[i]
        if cand[i][0] > T[i] or cand[i][1] < T[i]:
            # print("here1", cand[i][0], cand[i][1], T[i])
            print((0))
            sys.exit()
        else:
            cand[i] = [T[i], T[i]]

    else:
        cand[i][1] = min(cand[i][1], T[i])

r_max = 0
for i in range(N-1, -1, -1):
    if r_max < A[i]:
        r_max = A[i]
        if cand[i][0] > A[i] or cand[i][1] < A[i]:
            # print("here2", cand[i][0], cand[i][1], A[i])
            print((0))
            sys.exit()
        else:
            cand[i] = [A[i], A[i]]
    else:
        cand[i][1] = min(cand[i][1], A[i])

# print(l_max, r_max)
if l_max != r_max:
    print((0))
else:
    ans = 1
    for h_min, h_max in cand:
        ans *= (h_max - h_min + 1)
        ans %= 10**9 + 7

print(ans)

# Optimized solution
import sys

input = sys.stdin.readline

N = int(eval(input()))
T = list(map(int, input().split()))
A = list(map(int, input().split()))

if N == 1:
    if T[0] == A[0]:
        print((1))
    else:
        print((0))
    sys.exit()

mod = 10**9 + 7
ans = 1
for i in range(N):
    if i == 0:
        if A[i] < T[i]:
            print((0))
            sys.exit()
    elif i == N-1:
        if T[i] < A[i]:
            print((0))
            sys.exit()
    else:
        if T[i-1] < T[i] and A[i+1] < A[i] and T[i] != A[i]:
            print((0))
            sys.exit()
        else:
            if T[i-1] < T[i]:
                if A[i] < T[i]:
                    print((0))
                    sys.exit()
            elif A[i+1] < A[i]:
                if T[i] < A[i]:
                    print((0))
                    sys.exit()
            else:
                ans *= min(T[i], A[i])
                ans %= mod

print(ans)
# Original solution
# code-festival-2016-qualcC - 二人のアルピニスト / Two Alpinists
from bisect import bisect_left as bs


def main():
    """
      /----\     <- xi (= yi)
     /      \--\
    /           \
      xi  yi
    0 ~ xi / xi ~ yi / yi+1 ~ N-1
    """
    N = int(eval(input()))
    T = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    x, y = T[-1], A[0]  # max of x, y
    xi, yi = T.index(x), N - A[::-1].index(y) - 1  # indices of x, y
    if x != y or xi > yi:
        print((0))
        return
    MOD = 10 ** 9 + 7
    ans, cur = 1, 0
    for i in T[: xi + 1]:
        if i > cur:  # point of new altitude -> no choice (ans * 1)
            cur = i
        else:
            ans = (ans * cur) % MOD  # mulitple choices (1, 2, ..., cur)
    for _ in range(xi + 1, yi):
        ans = (ans * cur) % MOD
    for i in A[yi + 1 :]:
        if i < cur:
            cur = i
        else:
            ans = (ans * cur) % MOD
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# code-festival-2016-qualcC - 二人のアルピニスト / Two Alpinists
def main():
    """
      /----\     <- x = y
     /      \--\
    /           \
      xi  yi
    0 ~ xi / xi ~ yi / yi+1 ~ N-1
    """
    N = int(eval(input()))
    T = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))
    x, y = T[-1], A[0]  # max of x, y
    xi, yi = T.index(x), N - A[::-1].index(y) - 1  # indices of x, y
    if x != y or xi > yi:  # corner case
        print((0))
        return
    MOD = 10 ** 9 + 7
    ans, cur = 1, 0
    for i in T[: xi + 1]:
        if i > cur:  # point of new altitude -> no choice (ans * 1)
            cur = i
        else:
            ans = (ans * cur) % MOD  # mulitple choices (1, 2, ..., cur)
    for _ in range(xi + 1, yi):
        ans = (ans * cur) % MOD
    for i in A[yi + 1 :]:
        if i < cur:
            cur = i
        else:
            ans = (ans * cur) % MOD
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python3
#CODEFESTIVAL2016 qualC C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
t = LI()
a = LI()
x = [0]*n
y = [0]*n
if a[0] != t[-1]:
    print((0))
    quit()
for i in range(1,n):
    if t[i] > t[i-1]:
        x[i] = 1
for i in range(1,n)[::-1]:
    if a[i] < a[i-1]:
        y[i-1] = 1
ans = 1
for i in range(1,n-1):
    if x[i] == 1 and y[i] == 1:
        if t[i] != a[i]:
            print((0))
            quit()
        continue
    elif x[i] == 1:
        if a[i] >= t[i]:
            continue
        else:
            print((0))
            quit()
    elif y[i] == 1:
        if a[i] <= t[i]:
            continue
        else:
            print((0))
            quit()
    ans *= min(t[i],a[i])
    ans %= mod
print(ans)


# Optimized solution
#!/usr/bin/env python3
#CODEFESTIVAL2016 qualC C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
t = LI()
a = LI()
x = [0]*n
y = [0]*n
if a[0] != t[-1]:
    print((0))
    quit()
for i in range(1,n):
    if t[i] > t[i-1]:
        x[i] = 1
for i in range(1,n)[::-1]:
    if a[i] < a[i-1]:
        y[i-1] = 1
ans = 1
for i in range(1,n-1):
    if x[i] == 1 and y[i] == 1:
        if t[i] != a[i]:
            print((0))
            quit()
    elif x[i] == 1:
        if a[i] < t[i]:
            print((0))
            quit()
    elif y[i] == 1:
        if a[i] > t[i]:
            print((0))
            quit()
    else:
        ans *= min(t[i],a[i])
        ans %= mod
print(ans)
# Original solution
n = int(eval(input()))
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

ans, l, r = 1, 0, n - 1
for i in range(1, n):
    if t[i] == t[i - 1]:
        ans = ans * t[i] % mod
    if t[i] == a[i]:
        l = i
        break
for i in range(n - 1)[::-1]:
    if a[i] == a[i + 1]:
        ans = ans * a[i] % mod
    if t[i] == a[i]:
        r = i
        break

if t[l] != max(t) or a[r] != max(a) or max(t) != max(a):
    print((0))
else:
    print((ans * pow(t[l], max(r - l - 1, 0), mod) % mod))


# Optimized solution
n = int(eval(input()))
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

ans = 1
if n == 1:
    print((int(t == a)))
    exit()
for i in range(1, n - 1):
    ht, ha = 0, 0
    if t[i - 1] < t[i] and a[i] > a[i + 1]:
        if t[i] != a[i]:
            print((0))
            break
    elif t[i - 1] < t[i]:
        if t[i] > a[i]:
            print((0))
            break
    elif a[i] > a[i + 1]:
        if t[i] < a[i]:
            print((0))
            break
    else:
        ans = ans * min(t[i], a[i]) % mod
else:
    print(ans)