Problem:
 Score : 400 points    Problem Statement Mountaineers Mr. Takahashi and Mr. Aoki recently trekked across a certain famous mountain range.
The mountain range consists of N mountains, extending from west to east in a straight line as Mt. 1 , Mt. 2 , ..., Mt. N .
Mr. Takahashi traversed the range from the west and Mr. Aoki from the east.  The height of Mt. i is h_i , but they have forgotten the value of each h_i .
Instead, for each i ( 1 ≤ i ≤ N ), they recorded the maximum height of the mountains climbed up to the time they reached the peak of Mt. i (including Mt. i ).
Mr. Takahashi's record is T_i and Mr. Aoki's record is A_i .  We know that the height of each mountain h_i is a positive integer.
Compute the number of the possible sequences of the mountains' heights, modulo 10^9 + 7 .  Note that the records may be incorrect and thus there may be no possible sequence of the mountains' heights.
In such a case, output 0 .      Constraints  1 ≤ N ≤ 10^5  1 ≤ T_i ≤ 10^9  1 ≤ A_i ≤ 10^9  T_i ≤ T_{i+1} ( 1 ≤ i ≤ N - 1 )  A_i ≥ A_{i+1} ( 1 ≤ i ≤ N - 1 )         Input The input is given from Standard Input in the following format:  N  T_1  T_2  ...  T_N  A_1  A_2  ...  A_N       Output Print the number of possible sequences of the mountains' heights, modulo 10^9 + 7 .        Sample Input 1 5
1 3 3 3 3
3 3 2 2 2      Sample Output 1 4  The possible sequences of the mountains' heights are:   1, 3, 2, 2, 2   1, 3, 2, 1, 2   1, 3, 1, 2, 2   1, 3, 1, 1, 2    for a total of four sequences.       Sample Input 2 5
1 1 1 2 2
3 2 1 1 1      Sample Output 2 0  The records are contradictory, since Mr. Takahashi recorded 2 as the highest peak after climbing all the mountains but Mr. Aoki recorded 3 .       Sample Input 3 10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5      Sample Output 3 884111967  Don't forget to compute the number modulo 10^9 + 7 .       Sample Input 4 1
17
17      Sample Output 4 1  Some mountain ranges consist of only one mountain.

Solution (Python):
MOD = int(1e9) + 7


def calc(N, T, A):
    highest = max(T)
    if highest != max(A):
        return 0
    l = T.index(highest)
    r = A.index(highest)
    if N - (l + r) <= 0:
        return 0
    elif N - (l + r) == 1:
        ans = 1
    else:
        free = N - (l + r) - 2
        ans = pow(highest, free, MOD)
    prev = 0
    for i in range(l):
        if T[i] == prev:
            ans = (ans * T[i]) % MOD
        prev = T[i]
    prev = 0
    for i in range(r):
        if A[i] == prev:
            ans = (ans * A[i]) % MOD
        prev = A[i]
    return ans


def main():
    N = int(input())
    T = list(map(int, input().split()))
    A = list(map(int, input().split()))[::-1]
    ans = calc(N, T, A)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
mod=10**9+7
n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
a=[-1]*n
b=[-1]*n
c=[-1]*n
s=arr1[0]
a[0]=s
for i in range(n):
  if arr1[i]==1:
    a[i]=1
  else:
    if s!=arr1[i]:
      a[i]=arr1[i]
      s=arr1[i]
s=arr2[-1]
b[-1]=s
for i in range(1,n+1):
  if arr2[-i]==1:
    b[-i]=1
  else:
    if s!=arr2[-i]:
      b[-i]=arr2[-i]
      s=arr2[-i]
flag=False
for i in range(n):
  if a[i]==-1 and b[i]==-1:
    c[i]=-1
  elif a[i]==-1:
    if arr1[i]>=b[i]:
      c[i]=b[i]
    else:
      flag=True
  elif b[i]==-1:
    if arr2[i]>=a[i]:
      c[i]=a[i]
    else:
      flag=True
  else:
    if a[i]==b[i]:
      c[i]=a[i]
    else:
      flag=True
if flag==True:
  print(0)
else:
  l=0
  r=0
  ans=1
  cnt=0
  for i in range(n):
    if c[i]==-1:
      if cnt==0:
        l=c[i-1]
      cnt+=1
    else:
      if cnt!=0:
        r=c[i]
        for _ in range(cnt):
          ans=(ans*min(l,r))%mod
        cnt=0
  print(ans)

Solution (Python):
N = int(input())

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

X = [[T[0], 1]]
Y = [[A[N-1], 1]]

for i in range(1,N) :
    pv,pf = X[i-1]
    nv = T[i]
    
    if nv == 1 :
        X.append([nv, 1])
    elif pv >= nv :
        X.append([nv, 0])
    else :
        X.append([nv, 1])
    
    pv,pf = Y[i-1]
    nv = A[N-1-i]
    
    if nv == 1 :
        Y.append([nv, 1])
    elif pv >= nv :
        Y.append([nv, 0])
    else :
        Y.append([nv, 1])

Y = Y[::-1]

ans = 1

mat = 0
maa = 0

for i in range(N) :
    tv,tf = X[i]
    av,af = Y[i]
    
    mat = max(mat, tv)
    maa = max(maa, av)
    
    if tf == 1 and af == 0 :
        if tv > maa :
            ans = 0
            break
    elif tf == 0 and af == 1 :
        if av > mat :
            ans = 0
            break
    elif tf == 1 and af == 1 :
        if tv != av :
            ans = 0
            break
    else :
        ans *= min(tv,av)
        ans %= (10**9+7)
        
print(ans)

Solution (Python):
N=int(input())

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

count=0
for i in range(N):
    if A[i]==T[N-1] and T[i]==T[N-1]:
        count+=1


if count==0:
    print(0)
else:
    count=max(0,count-2)

    mod = 10**9+7
    d = pow(T[N-1],count,mod)

    from collections import Counter

    tc=Counter(T)

    for key in tc.keys():
        if key!=T[N-1]:
            d*=pow(key,tc[key]-1,mod)
            d%=mod

    ac=Counter(A)

    for key in ac.keys():
        if key!=T[N-1]:
            d*=pow(key,ac[key]-1,mod)
            d%=mod

    print(d)

Solution (Python):
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))

t = [0]+t+[t[-1]]
a = [a[0]]+a+[0]

ans = 1

for i in range(1,n+1):
    if t[i]==t[i-1] and a[i]==a[i+1]:
        ans *= min(t[i],a[i])
        ans %= 10**9+7
    elif t[i]!=t[i-1] and a[i]!=a[i+1]:
        if t[i]!=a[i]:
            print(0)
            exit()
    elif t[i]!=t[i-1] and t[i]>a[i]:
        print(0)
        exit()
    elif a[i]!=a[i+1] and a[i]>t[i]:
        print(0)
        exit()

print(ans)

Solution (Python):
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
max_T = max(T)
max_A = max(A)
if max_A != max_T:
    print(0)
    exit()
mt,ma = 0,0
ans = 1
for i in range(N):
    if T[i] == max_T:

        break
    else:
        if T[i] > mt:
            mt = T[i]
        else:
            ans *= mt
            ans %= mod
for j in range(N)[::-1]:
    if A[j] == max_A:
        break
    else:
        if A[j] > ma:
            ma = A[j]
        else:
            ans *= ma
            ans %= mod
if i == j:
    print(ans)
    exit()
elif j < i:
    print(0)
    exit()
else:
    ans *= pow(max_A,j-i-1,mod)
    ans %= mod
    print(ans)

Solution (Python):
def inpl(): return list(map(int, input().split()))

N = int(input())
T = inpl()
A = inpl()

OK = True
D = [0]*N
D[0] = 1

for i in range(1, N):
    if T[i-1] < T[i]:
        D[i] = 1

if D[-1] and (A[-1] != T[-1]):
    OK = False
else:
    D[-1] = 1

for i in range(N-2, -1, -1):
    if A[i] > A[i+1]:
        if D[i] and (A[i] != T[i]):
            OK = False
        else:
            if A[i] > T[i]:
                OK = False
            D[i] = 1

ans = OK
MOD = 10**9 + 7
for i in range(N):
    if D[i] == 0:
        ans = ans * min(A[i], T[i]) % MOD
print(ans*1)

Solution (Python):

N = int(input())
T = list(map(int,input().split()))
A = list(map(int,input().split()))
T = [0] + T + [T[-1]]
A = [A[0]] + A + [0]

K = [0 for k in range(N+2)]
L = [0 for k in range(N+2)]
for k in range(1,N+2):
    if T[k-1] != T[k]:
        K[k] = T[k]
for k in range(1,N+2):
    if A[N-k+2] != A[N-k+1]:
        L[N-k+1] = A[N-k+1]

MOD = 10**9 + 7
ans = 1
for k in range(1,N+1):
    if K[k] == L[k] == 0:
        ans *= min(A[k],T[k])
        ans %= MOD
    elif (K[k]>0 and A[k]<K[k]) or (L[k]>0 and T[k]<L[k]):
        print(0)
        exit(0)
print(ans)

Solution (Python):
MOD = 10**9 + 7
n = int(input())
t = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

height = [0] * n
height[0] = t[0]
for i in range(1, n):
    if t[i] > t[i-1]:
        height[i] = t[i]
        if t[i] > a[i]:
            print(0)
            exit()
if height[-1] == 0:
    height[-1] = a[-1]
elif height[-1] != a[-1]:
        print(0)
        exit()

for i in range(n-1, 0, -1):
    if a[i] < a[i-1]:
        if height[i-1] == 0:
            height[i-1] = a[i-1]
            if a[i-1] > t[i-1]:
                print(0)
                exit()
        elif height[i-1] != a[i-1]:
            print(0)
            exit()

ans = 1
for i, item in enumerate(height):
    if item == 0:
        ans *= min(t[i], a[i])
        ans %= MOD

print(ans)

Solution (Python):

"""
C - 二人のアルピニスト / Two Alpinists
https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c

"""
import sys


def solve(N, T, A):
    mountains_t = dict()
    peak_t = T[0]
    mountains_t[1] = (peak_t, peak_t)
    for i, t in enumerate(T[1:], start=2):
        if t > peak_t:
            peak_t = t
            mountains_t[i] = (peak_t, peak_t)
        else:
            if t < peak_t:
                return 0
            mountains_t[i] = (1, peak_t)

    mountains_a = dict()
    peak_a = A[-1]
    mountains_a[N] = (peak_a, peak_a)
    for j, a in zip(range(N-1, 0, -1), reversed(A[:-1])):
        if a > peak_a:
            peak_a = a
            mountains_a[j] = (peak_a, peak_a)
        else:
            if a < peak_a:
                return 0
            mountains_a[j] = (1, peak_a)

    MOD = 10**9 + 7
    ans = 1
    for i in range(1, N+1):
        lt, ht = mountains_t[i]
        la, ha = mountains_a[i]
        if lt == ht or la == ha:
            if lt == ht and la == ha:
                if lt != la:
                    return 0
            elif lt == ht:
                if not la <= lt <= ha:
                    return 0
            else:
                if not lt <= la <= ht:
                    return 0
        else:
            high = min(ht, ha)
            ans = ans * high% MOD
    return ans


def main(args):
    N = int(input())
    T = [int(t) for t in input().split()]
    A = [int(a) for a in input().split()]
    ans = solve(N, T, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=[0,T[0]]
Ares[-1]=[0,A[-1]]
for i in range(1,n):
  if T[i]>T[i-1]:
    Tres[i]=[0,T[i]]
  else:
    Tres[i]=[1,T[i]]
  if A[-i-1]>A[-i]:
    Ares[-i-1]=[0,A[-i-1]]
  else:
    Ares[-i-1]=[1,A[-i-1]]
ans=1
for i in range(n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==1 and aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)

Solution (Python):
mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)

Solution (Python):
N=int(input())
T=list(map(int,input().split()))
A=list(map(int,input().split()))
mod=10**9+7
Tres=[0]*N
Ares=[0]*N
Tres[0]=(0,T[0])
Ares[N-1]=(0,A[N-1])
for i in range(1,N):
    if T[i]>Tres[i-1][1]:
        Tres[i]=(0,T[i])
    else:
        Tres[i]=(1,T[i])
    if A[N-i-1]>Ares[N-i][1]:
        Ares[N-i-1]=(0,A[N-i-1])
    else:
        Ares[N-i-1]=(1,A[N-i-1])
if Tres[0]<=Ares[0]:
    ans=1
else:
    ans=0
for i in range(1,N):
    x,t=Tres[i]
    y,a=Ares[i]
    if x==y==1:
        ans=ans*min(t,a)%mod
    elif x==1 and y==0 and t<a:
        ans=0
    elif x==0 and y==1 and t>a:
        ans=0
    elif x==0 and y==0 and t!=a:
        ans=0
print(ans)

Solution (Python):
import sys
mod = 10**9 + 7

def nai():
    print(0)
    sys.exit()

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

M = max(A)
if M != max(T):
    nai()

iT = T.index(M)
iA = N - 1 - A[::-1].index(M)
if iA < iT:
    nai()
ans = pow(M, max(0, iA - iT - 1), mod)
pre = -1
for t in T[:iT]:
    if pre == t:
        ans = t*ans%mod
    pre = t
pre = -1
for a in A[::-1]:
    if a == M:
        break
    if pre == a:
        ans = a*ans%mod
    pre = a
print(ans)

Solution (Python):
N=int(input())
T=list(map(int,input().split()))
t=[1]
for i in range(1,N):
    if T[i]!=T[i-1]:
        t.append(1)
    else:
        t.append(T[i])
    if T[i]<T[i-1]:
        print(0)
        exit()
A=list(map(int,input().split()))
A=A[::-1]
a=[1]
for i in range(1,N):
    if A[i]!=A[i-1]:
        a.append(1)
    else:
        a.append(A[i])
    if A[i]<A[i-1]:
        print(0)
        exit()
A=A[::-1]
a=a[::-1]


M=max(A)

for i in range(N):
    if T[i]==M:
        if A[i]==M:
            break
        else:
            print(0)
            exit()

for i in range(N):
    if A[N-1-i]==M:
        if T[N-1-i]==M:
            break
        else:
            print(0)
            exit()
ans=1
mod=(10**9+7)
for i in range(N):
    ans*=min(t[i],a[i])
    ans%=mod
print(ans)

Solution (Python):
MOD = 1000000007
n = int(input())
tli = [ int(it) for it in input().split() ]
ali = [ int(it) for it in input().split() ]


mav1 = max(tli)
mav2 = max(ali)
mav = mav1

if (mav1!=mav2):
  print (0)
else:
  mai1 = tli.index(mav)
  mai2 = n-1-list(reversed(ali)).index(mav)
  
  if (mai2<mai1):
    print (0)
  else:
    s = 1
    tma = -1
    for i in range(0,mai1+1):
      if tli[i]>tma:
        tma = tli[i]
        
      else:
        s*=(tli[i])
        s%=MOD
        
    tma = -1
    for i in range(n-1,mai2-1,-1):
      if ali[i]>tma:
        tma = ali[i]
        
      else:
        s*=(ali[i])
        s%=MOD
        
    if (mai2-mai1>1):
      for i in range(mai2-mai1-1):
        s*=mav
        s%=MOD
    print ( s%(1000000007) )

Solution (Python):

N=int(input())
mod=10**9+7
T=list(map(int,input().split()))
A=list(map(int,input().split()))
ansT=[0]*N
ansA=[0]*N
ansT[0]=-1*T[0]
ansA[N-1]=-1*A[N-1]
for i in range(1,N):
    if T[i]>T[i-1]:
        ansT[i]=-1*T[i]
    else:
        ansT[i]=T[i]
    if A[N-1-i]>A[N-i]:
        ansA[N-1-i]=-1*A[N-1-i]
    else:
        ansA[N-1-i]=A[N-1-i]
ans=1
for i in range(N):
    if ansT[i]<0 and ansA[i]<0 and ansT[i]!=ansA[i]:
        ans=0
        break
    elif ansT[i]>0 and ansA[i]>0:
        ans=(ans*min(ansT[i],ansA[i]))%mod
    elif ansT[i]<0 and ansA[i]>0 and abs(ansT[i])>ansA[i]:
        ans=0
        break
    elif ansT[i]>0 and ansA[i]<0 and abs(ansA[i])>ansT[i]:
        ans=0
        break
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
T=LIST()
A=LIST()


Hs1=[0]*N
Hs1[0]=T[0]
fixed=[False]*N
fixed[0]=True
for i in range(1, N):
    if T[i-1]!=T[i]:
        Hs1[i]=T[i]
        fixed[i]=True
Hs2=[0]*N
Hs2[-1]=A[-1]
fixed[-1]=True
for i in range(N-2, -1, -1):
    if A[i+1]!=A[i]:
        Hs2[i]=A[i]
        fixed[i]=True

for i in range(N):
    
    if Hs1[i]!=0 and Hs2[i]!=0 and Hs1[i]!=Hs2[i]:
        print(0)
        exit()
    if Hs1[i]!=0:
        if Hs1[i]>A[i]:
            print(0)
            exit()
    if Hs2[i]!=0:
        if Hs2[i]>T[i]:
            print(0)
            exit()
ans=1
for i in range(N):
    if not fixed[i]:
        
        ans=(ans*min(T[i], A[i]))%MOD
print(ans)

Solution (Python):
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 1
mod = 10**9 + 7
h = [0 for _ in range(n)]
last = 0
for i in range(n):
    if t[i] != last:
        h[i] = t[i]
        last = t[i]
last = 0
for i in range(n):
    j = n-i-1
    if a[j] != last:
        if (h[j] > 0 and h[j] != a[j]) or a[j] > t[j]:
            ans = 0
            break
        h[j] = a[j]
        last = a[j]
for i in range(n):
    if h[i] == 0:
        ans = ans * min(t[i], a[i]) % mod
print(ans)

Solution (Python):
mod = 1000000007
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
T_max = 0
T_max_i = 0
for i in range(N):
    if T[i] > T_max:
        T_max = T[i]
        T_max_i = i
A_max = 0
A_max_i = 0
for i in range(N):
    if A[i] >= A_max:
        A_max = A[i]
        A_max_i = i
if T_max != A_max or T_max_i > A_max_i:
    print(0)
else:
    ans = 1
    h = 0
    for i in range(T_max_i + 1):
    	if T[i] > h:
    		h = T[i]
    	else:
    		ans = (ans * h) % mod
    for i in range(T_max_i + 1, A_max_i):
    	ans = (ans * h) % mod
    for i in range(A_max_i + 1, N):
    	if A[i] < h:
    		h = A[i]
    	else:
    		ans = (ans * h) % mod
    print(ans)

Solution (Python):
mod = 1000000007
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
T_max = 0
T_max_i = 0
for i in range(N):
    if T[i] > T_max:
        T_max = T[i]
        T_max_i = i
A_max = 0
A_max_i = 0
for i in range(N):
    if A[i] >= A_max:
        A_max = A[i]
        A_max_i = i
if T_max != A_max or T_max_i > A_max_i:
    print(0)
else:
    ans = 1
    h = 0
    for i in range(T_max_i + 1):
    	if T[i] > h:
    		h = T[i]
    	else:
    		ans = (ans * h) % mod
    for i in range(T_max_i + 1, A_max_i):
    	ans = (ans * h) % mod
    for i in range(A_max_i + 1, N):
    	if A[i] < h:
    		h = A[i]
    	else:
    		ans = (ans * h) % mod
    print(ans)

Solution (Python):
from itertools import groupby
from functools import reduce

MOD = 1000000007

def mod_pow(x, k):
    ret = 1
    while k > 0:
        if k & 1:
            ret *= x
            ret %= MOD
        k >>= 1
        x *= x
        x %= MOD
    return ret


def max_t():
    i, t_max = 0, 0
    for j, v in enumerate(t):
        if v < t_max:
            print(0)
            quit(0)
        if v > t_max:
            t_max = v
            i = j
    return i, t_max


def validate_a(i, t_max):
    for v in a[:i + 1]:
        if v != t_max:
            print(0)
            quit(0)
    for v in a[i + 1:]:
        if v > t_max:
            print(0)
            quit(0)


if __name__ == '__main__':
    n = int(input())
    t = [int(s) for s in input().split()]
    a = [int(s) for s in input().split()]
    i, t_max = max_t()
    validate_a(i, t_max)

    highests = [min(x, y) for x, y in zip(a, t)]
    print(reduce(lambda x, y: x * y % MOD, (mod_pow(v, ((length - 1) if v < t_max else max(length - 2, 0))) for v, length in ((v, len(list(l))) for v, l in groupby(highests)))))

Solution (Python):
n = int(input())
mount = [0]*n
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mount[0] = a[0]
mount[-1] = b[-1]
pat = 1
mod = 10**9+7
for i in range(1,n):
  if a[i] > a[i-1]:
    if mount[i] != 0 and mount[i] != a[i]:
      print(0)
      exit()
    else:
      mount[i] = a[i]
  if b[n-i-1] > b[n-i]:
    if mount[n-i-1] != 0 and mount[n-i-1] != b[n-i-1]:
      print(0)
      exit()
    else:
      mount[n-i-1] = b[n-i-1]
for i in range(n):
  if mount[i] == 0:
    dx = 1
    while mount[i+dx] == 0:
      dx += 1
    this = min(mount[i-1],mount[i+dx])
    pat = pat*(this**dx)%mod
    for j in range(dx):
      mount[i+j] = this
a2 = [0]*n
b2 = [0]*n
a2[0] = mount[0]
b2[-1] = mount[-1]
for i in range(1,n):
  a2[i] = max(mount[i],a2[i-1])
  b2[n-i-1] = max(mount[n-i-1],b2[n-i])
if a != a2 or b != b2:
  print(0)
else:
  print(pat)

Solution (Python):
n = int(input())
t = list(map(int,input().split()))
a = list(map(int,input().split()))
MOD = 10**9 + 7

m_left =[[1,t[0]]]
for i in range(1,n):
    if t[i] > t[i-1]:
        m_left.append([1,t[i]])
    else:
        m_left.append([0,t[i]])

m_right = [[1,a[n-1]]]
for i in range(n-2,-1,-1):
    if a[i] > a[i+1]:
        m_right.append([1,a[i]])
    else:
        m_right.append([0,a[i]])
m_right = m_right[::-1]



ans = 1
for i in range(n):
    if m_right[i][0] == 1 and m_left[i][0] == 1:
        if m_right[i][1] != m_left[i][1]:
            ans = 0
    elif m_right[i][0] == 1:
        if m_right[i][1] > m_left[i][1]:
            ans = 0
    elif m_left[i][0] == 1:
        if m_left[i][1] > m_right[i][1]:
            ans = 0
    else:
        ans *= min(m_right[i][1], m_left[i][1])
        ans %= MOD

print(ans)

Solution (Python):
n=int(input())
a=[0]+list(map(int,input().split()))
b=list(map(int,input().split()))+[0]
c=[[0,0]for i in range(n)]
p=0
mod=10**9+7
d=1
for i in range(n,0,-1):
    if a[i-1]!=a[i]:
        c[i-1]=[1,a[i]]
    else:
        c[i-1]=[0,a[i]]
for i in range(n):
    if b[i]!=b[i+1]:
        if c[i][0]==1:
            if b[i]!=c[i][1]:
                print(0)
                break
        else:
            if b[i]<=c[i][1]:
                c[i]=[1,b[i]]
            else:
                print(0)
                break
    else:
        if c[i][0]!=1:
            c[i]=[0,min(b[i],c[i][1])]
        else:
            if c[i][1]>b[i]:
                print(0)
                break
    if c[i][0]!=1:
        d=d*c[i][1]%mod
else:
    print(d)

Solution (Python):

n = int(input())
tl = list(map(int, input().split()))
al = list(map(int, input().split()))

mod = 10**9 + 7

res = 1
for i in range(1,n-1):
    if tl[i-1]<tl[i]:
        if tl[i]>al[i]:
            res = 0
        continue
    elif al[i]>al[i+1]:
        if al[i]>tl[i]:
            res = 0
        continue
    else:
        res *= min(al[i],tl[i])
        res %= mod
if tl[-1]!=al[0]:
    res = 0
print(res)

Solution (Python):
n=int(input())
t=tuple([0]+list(map(int,input().split()))+[0])
a=tuple([0]+list(map(int,input().split()))+[0])
c=1
m=10**9+7
for i in range(1,n+1):
    if t[i]>t[i-1]:
        if a[i]>a[i+1]and a[i]!=t[i]or a[i]==a[i+1]and a[i]<t[i]:
            print(0)
            exit()
    else:
        if a[i]>a[i+1]and a[i]>t[i]:
            print(0)
            exit()
        if a[i]==a[i+1]:
            c=min(t[i],a[i])*c%m
print(c)

Solution (Python):
n=int(input())
t=tuple([0]+list(map(int,input().split()))+[0])
a=tuple([0]+list(map(int,input().split()))+[0])
if n==1 and t[1]!=a[1]:
    print(0)
    exit()
c=1
m=10**9+7
for i in range(1,n):
    if t[i]>t[i-1]:
        if a[i]>a[i+1]and a[i]!=t[i]or a[i]==a[i+1]and a[i]<t[i]:
            print(0)
            exit()
    else:
        if a[i]>a[i+1]and a[i]>t[i]:
            print(0)
            exit()
        if a[i]==a[i+1]:
            c=min(t[i],a[i])*c%m
print(c)

Solution (Python):
n=int(input())
t=tuple([0]+list(map(int,input().split()))+[0])
a=tuple([0]+list(map(int,input().split()))+[0])
if n==1 and t[1]!=a[1]:
    print(0)
    exit()
c=1
m=10**9+7
for i in range(1,n):
    if t[i]>t[i-1]:
        if a[i]>a[i+1]and a[i]!=t[i]or a[i]==a[i+1]and a[i]<t[i]:
            print(0)
            exit()
    else:
        if a[i]>a[i+1]and a[i]>t[i]:
            print(0)
            exit()
        if a[i]==a[i+1]:
            c=min(t[i],a[i])*c%m
print(c)

Solution (Python):
n = int(input())
t = [int(m) for m in input().split()]
a = [int(m) for m in input().split()]
trcd = []
arcd = []
for i in range(n):
    if i == 0:
        trcd.append([t[i], 1])
    else:
        if t[i - 1] < t[i]:
            trcd.append([t[i], 1])
        elif t[i - 1] == t[i]:
            trcd.append([t[i], t[i]])

for i in reversed(range(n)):
    if i == n - 1:
        arcd.append([a[i], 1])
    else:
        if a[i] > a[i + 1]:
            arcd.append([a[i], 1])
        elif a[i] == a[i + 1]:
            arcd.append([a[i], a[i]])

ans = 1
mod = 10 ** 9 + 7
for i in range(n):
    if trcd[i][1] == arcd[-i-1][1] and trcd[i][1] == 1:
        if trcd[i][0] != arcd[-i-1][0]:
            print(0)
            exit()
    elif (trcd[i][0] > arcd[-i-1][0] and trcd[i][1] == 1) or (trcd[i][0] < arcd[-i-1][0] and arcd[-i-1][1] == 1):
        print(0)
        exit()
    else:
        ans *= min(trcd[i][1], arcd[-i-1][1])
        ans %= mod
print(ans)

Solution (Python):
MOD = 10**9 + 7

N = int(input())
Ts = list(map(int, input().split()))
As = list(map(int, input().split()))

minTs, maxTs = [1]*N, [10**9]*N
minAs, maxAs = [1]*N, [10**9]*N

minTs[0] = maxTs[0] = Ts[0]
for i in range(1, N):
    if Ts[i-1] < Ts[i]:
        minTs[i] = maxTs[i] = Ts[i]
    else:
        maxTs[i] = Ts[i]

minAs[-1] = maxAs[-1] = As[-1]
for i in reversed(range(N-1)):
    if As[i] > As[i+1]:
        minAs[i] = maxAs[i] = As[i]
    else:
        maxAs[i] = As[i]

ans = 1
for minT, maxT, minA, maxA in zip(minTs, maxTs, minAs, maxAs):
    minH = max(minT, minA)
    maxH = min(maxT, maxA)
    ans *= max(0, maxH - minH + 1)
    ans %= MOD
print(ans)

Solution (Python):
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

not_fixed = [True] * N


MAX = 0
for i in range(N):
    if T[i] > MAX:
        MAX = T[i]
        not_fixed[i] = False
        if T[i] > A[i]:
            print(0)
            exit()

MAX = 0
for i in reversed(range(N)):
    if A[i] > MAX:
        MAX = A[i]
        not_fixed[i] = False
        if A[i] > T[i]:
            print(0)
            exit()


MIN = [min(t, a) for t, a in zip(T, A)]
ans = 1
mod = 10 ** 9 + 7

for i in range(N):
    if not_fixed[i]:
        ans *= MIN[i]
        ans %= mod

print(ans)

Solution (Python):



def main():
    from bisect import bisect_right
    from bisect import bisect_left

    n = int(input())
    t = list(map(int, input().split()))
    a = list(map(int, input().split()))[::-1]
    t_candidates = [1 for _ in range(n)]
    a_candidates = [1 for _ in range(n)]
    ans = 1

    if max(t) != max(a):
        print(0)
        exit()
    else:
        if bisect_left(t, max(t)) > (n - bisect_left(a, max(a)) - 1):
            print(0)
            exit()

    for i in range(1, n):
        if t[i] == t[i - 1]:
            t_candidates[i] = t[i]

        if a[i] == a[i - 1]:
            a_candidates[i] = a[i]

    for t_candidate, a_candidate in zip(t_candidates, a_candidates[::-1]):
        ans *= min(t_candidate, a_candidate)
        ans %= 10 ** 9 + 7

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
t_list = list(map(int, input().split()))
a_list = list(map(int, input().split()))

t_max = -1
t_i = 0
a_max = -1
a_i = 0
ans = 1
mod = 10 ** 9 + 7

for i in range(N):
    t = t_list[i]
    a = a_list[i]
    if t > t_max:
        t_max = t
        t_i = i
    if a >= a_max:
        a_max = a
        a_i = i
if a_max == t_max and t_i <= a_i:
    prev_a = a_list[-1]
    prev_t = t_list[0]
    for i in range(1, t_i):
        t = t_list[i]
        if t == prev_t:
            ans *= prev_t
            ans %= mod
        prev_t = t
    for i in range(N-2, t_i, -1):
        a = a_list[i]
        if a == prev_a:
            ans *= prev_a
            ans %= mod
        prev_a = a
    print(ans % mod)
else:
    print(0)

Solution (Python):
N = int(input())
T = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
mod = 10**9 + 7
upT = set()
upA = set()
for i in range(N):
    if i == 0 or T[i - 1] < T[i]:
        upT.add(i)
    if i == N - 1 or A[i] > A[i + 1]:
        upA.add(i)
ans = 1
for i in range(N):
    if i in upT:
        if T[i] > A[i]:
            ans = 0
            break
    elif i in upA:
        if T[i] < A[i]:
            ans = 0
            break
    else:
        ans *= min(T[i], A[i])
        ans %= mod
print(ans)

Solution (Python):
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

tmax = T[-1]
amax = A[0]
tf = T.index(tmax)
af = N - (list(reversed(A))).index(amax) - 1

if tf > af or tmax != amax:
	print(0)

else:
	ans = 1
	for i in range(1, tf + 1):
		if T[i] == T[i - 1]:
			ans = (ans * T[i - 1]) % 1000000007

	for i in range(af - tf - 1):
		ans = (ans * tmax) % 1000000007
	for i in range(af + 1, N):
		if A[i] == A[i - 1]:
			ans = (ans * A[i - 1]) % 1000000007

	print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
mod = 10**9+7
N = int(input())
T = inpl()
A = inpl()
summit =  T[-1]
S = [i == j == summit for i, j in zip(A, T)]
ans, pre = 1, 0
if A[0] != summit:
    ans = 0
if not any(S):
    ans = 0

k = sum([min(i, j) == summit for i, j in zip(A, T)]) 
for i in T:
    if i == summit:
        break
    if i == pre:
        ans = ans*pre %mod
    else:
        pre = i
pre = 0
for i in reversed(A):
    if i == summit:
        break
    if i == pre:
        ans = ans*pre %mod
    else:
        pre = i
print(ans*summit**max(k-2, 0)%mod)

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

Solution (Python):
N = int(input())
T = [int(t) for t in input().split()]
A = [int(a) for a in input().split()]
mod = 7 + 10**9

TS, AS = [None for i in range(N)], [None for j in range(N)] 
TS[0], AS[-1] = True, True
for i in range(1, N):
    if T[i] > T[i-1]: TS[i] = True
    else: TS[i] = False
    if A[N-1-i] > A[N-i]: AS[N-1-i] = True
    else: AS[N-1-i] = False

Ans = 1
for i in range(N): 
    if TS[i] and AS[i]:
        if T[i] != A[i]: 
            Ans = 0
            break
    elif TS[i]:
        if A[i] < T[i]:
            Ans = 0
            break
    elif AS[i]:
        if T[i] < A[i]:
            Ans = 0
            break
    else:
        Ans *= min(T[i], A[i])
        Ans %= mod

print(Ans)

Solution (Python):
N=int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
a = 1
if T[0]>A[0] or A[-1]>T[-1] or T[-1]!=A[0]:
    a*=0
for i in range(1,N-1):
    if T[i-1]!=T[i]:
        if T[i]>A[i]:
            a*=0
            break
        else:
            a*=1
            
    elif A[i]!=A[i+1]:
        if T[i]<A[i]:
            a*=0
            break
        else:
            a*=1
    else:        
        a=(a*min(T[i],A[i]))%(10**9+7)
print(a)

Solution (Python):
N=int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))
a = 1
if T[0]>A[0] or A[-1]>T[-1] or T[-1]!=A[0]:
    a*=0
for i in range(1,N-1):
    if T[i-1]!=T[i]:
        if T[i]>A[i]:
            a*=0
            break
        else:
            a*=1
            continue
    if A[i]!=A[i+1]:
        if T[i]<A[i]:
            a*=0
            break
        else:
            a*=1
            continue
    a=(a*min(T[i],A[i]))%(10**9+7)
print(a)