Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline
mod=1e9+7

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    dp=[[0 for i in range(M+1)] for j in range(N+1)]
    for i in range(N+1):
        dp[i][0]=1
    for i in range(M+1):
        dp[0][i]=1


    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = dp[i + 1][j]+dp[i ][j + 1]-dp[i][j]
            if S[i]==T[j]:
                dp[i+1][j+1]+=dp[i][j]

    print(int(dp[N][M]%mod))


### FIXED CODE ###

mod=1e9+7
import sys
input=sys.stdin.readline

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    S=list(map(int,input().split()))
    T=list(map(int,input().split()))
    sum=[[0 for i in range(M+1)] for j in range(N+1)]
    dp=[[0 for i in range(M+1)] for j in range(N+1)]

    for i in range(N):
        for j in range(M):
            if S[i]==T[j]:
                dp[i+1][j+1]+=sum[i][j]+1
                dp[i+1][j+1]%=mod
            else:
                dp[i + 1][j + 1] =0

            sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]-sum[i][j]+dp[i+1][j+1]
            sum[i + 1][j + 1]%=mod


    ans=sum[N][M]+1
    print(int(ans))
N, M=map(int,input().split())
alist = list(map(int,input().split()))
alist.sort(reverse = True)
su = 0
correct = True
for i in alist:
    su += i
for i in range[M-1]:
    if alist[i] < 1/(4*M) :
        print("No")
        correct = False
if correct:
    print("Yes")


### FIXED CODE ###

N, M=map(int,input().split())
alist = list(map(int,input().split()))
alist.sort(reverse = True)
abc = sum(alist)
if alist[M-1] >= abc/(4*M):
    print("Yes")
else:
    print("No")
N=input()
A=input()
N!=0
B=N%500
if(int(B) <= int(A)):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

N=int(input())
A=int(input())
N!=0
B=int(N%500)
if(B <= A):
    print("Yes")
else:
    print("No")
N = int(input())
alphabet = "zabcdefghijklmnopqrstuvwxy"
num = N
cnt = 0
div = 26
res = ""
while True:
  # print(num, div)
  sho = num // div
  amari = num % div
  # print(sho, amari, alphabet[amari])
  # print("--")
  res += alphabet[amari]
  if amari != 0:
    num = sho
  else:
    num = sho
    div += 1
  if sho == 0:
    break
  elif sho == 1 and amari == 0 and alphabet[amari] == "z":
    break
print(res[::-1])

### FIXED CODE ###

N = int(input())
alphabet = "zabcdefghijklmnopqrstuvwxy"
num = N
cnt = 0
div = 26
res = ""
while True:
  # print(num, div)
  sho = num // div
  amari = num % div
  # print(sho, amari, alphabet[amari])
  # print("--")
  res += alphabet[amari]
  if amari != 0:
    num = sho
  else:
    num = sho -1
  if sho == 0:
    break
  elif sho == 1 and amari == 0 and alphabet[amari] == "z":
    break
print(res[::-1])
a, b = map(int, input().split())
c = 1
for i in range(20):
    if b > c:
        c += a-1
    else:
        break
print(-(-(c-1) // a-1))

### FIXED CODE ###

a,b,c = input()
d,e,f = input()
count = 0
if a == d:
    count+= 1
if b == e:
    count+= 1
if c == f:
    count+= 1
print(count)
s = input().sort()
t = input().sort(reverse=True)
if s<t:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = list(input())
t = list(input())
if s==t:
    print('No')
    exit()

s = sorted(s)
s = ''.join(s)
t = sorted(t, reverse=1)
t = ''.join(t)
l = [s,t]
k = sorted(l)
if l==k:
    print('Yes')
else:
    print('No')
o = input()
e = input() + [""]

for x,y in zip( o, e ) : print( x+y, sep="" )

### FIXED CODE ###

o = list(input())
e = list(input()) + [""]

for x,y in zip( o, e ) : print( x+y, end="" )
s = input()
m = str(len(s) -2)

print(s[0] +　m + s[-1])

### FIXED CODE ###

s = input()

print(s[0]+str(len(s)-2)+s[-1])
import numpy as np
a = []
for i in range(4):
    a.append(np.zeros((3,10), dtype = int))
border = '#'*20
n = int(input())
for i in range(n):
    b,f,r,v = map(int,input().split())
    a[b-1][f-1][r-1] += v
    
for i in range(4):
    for k in a[i]:
        for l in k:
            print('{} '.format(l), end ='')
        print()
    if i != 3:
        print(border)


### FIXED CODE ###

a = [[[0 for i in range(10)]for i in range(3)]for i in range(4)]
border = '#'*20
n = int(input())
for i in range(n):
    b,f,r,v = map(int,input().split())
    a[b-1][f-1][r-1] += v
    
for i in range(4):
    for k in a[i]:
        for l in k:
                print(' {}'.format(l), end ='')
        print()
    if i != 3:
        print(border)
x,n = map(int,input().split())
p = list(map(int,input().split()))
p1 = [i for i in range(1,101)]
for i in p:
    if i in p1:
        p1.remove(i)
ans = 1000
al = []

for i in p1:
    ans = min(abs(i-x),ans)
    if ans >= abs(i-x):
        al.append(i)

if len(al) == 0:
    if x < 50:
        print(0)
    else:
        print(101)
elif abs(al[-1]-x) == abs(al[-2]-x):
    print(al[-2])
else:
    print(al[-1])

### FIXED CODE ###

x,n = map(int,input().split())
p = list(map(int,input().split()))
p1 = [i for i in range(0,102)]
for i in p:
    if i in p1:
        p1.remove(i)
ans = 1000
al = []
for i in p1:
    if ans >= abs(i-x):
        ans = min(abs(i-x),ans)
        al.append(i)

if len(al) == 0:
    if x < 50:
        print(0)
    else:
        print(101)
elif len(al) > 1:
    if abs(al[-1]-x) == abs(al[-2]-x):
        print(al[-2])
    else:
        print(al[-1])
else:
    print(al[-1])
x,a,b=map(nt,input().split())
print("delicious" if a-b>=0 else "safe" if b-a<=x else "dangerous")

### FIXED CODE ###

x,a,b=map(int,input().split())
print("delicious" if a-b>=0 else "safe" if b-a<=x else "dangerous")
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

sum = 0
for i in range(n):
    for j in range(n):
        if i != j:
            sum += sqrt((l[i][0] - l[j][0]) * (l[i][0] - l[j][0]) + (l[i][1] - l[j][1]) * (l[i][1] - l[j][1]))
print(sum / n)


### FIXED CODE ###

n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]

from itertools import permutations
import math
m = math.factorial(n)
per = permutations(xy,n)

d = 0
c = 0
for j in per :
    for i in range(n-1):
        d += ((j[i+1][0]-j[i][0])**2 + (j[i+1][1]-j[i][1])**2) ** 0.5

print(d/m)
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
heapq.heapify(A)

CB = []
for i in range(M):
  b, c = map(int, input().split())
  CB.append([c, b])

CB.sort()
D = []
for c, b in CB:
  D += [c]*b

for i in range(N):
  d = D.pop()
  g = heapq.heappushpop(A, d)
  if d == g:
    break

print(sum(A))

### FIXED CODE ###

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

CB = []
for i in range(M):
  b, c = map(int, input().split())
  CB.append([c, b])

D = [[a, 1] for a in A] + CB

D.sort()

ans = 0
while N > 0:
  c, b = D.pop()
  ans += min(N, b)*c
  N -= b

print(ans)
import numpy as np
import math
x = int(input())
flag = False
for i in range(10**10):
    for j in range(1,10**10):
        if (i+j)**5-i**5 == x:
            print(i+j,j)
            flag = True
            break
    if Flag:
        break

### FIXED CODE ###

import numpy as np
import math
x = int(input())
ys = []
i = 1
while i**2 < x:
    if x%i == 0:
        ys.append(i)
        ys.append(x//i)
    i += 1
if i**2 == x:
    ys.append(i)

f = False

for j in ys:
    for i in range(10**3):
        if i**5-(i-j)**5 == x:
            print(i,i-j)
            break
        elif i**5-(i-j)**5 > x and i-j > 0:
            break
    if f:
        break
import sys
sys.setrecursionlimit(10**10)

def search_max_gcd(M, possible):
    if possible == 1:
        return 1
    elif (M % possible) == 0:
        return possible
    else:
        return search_max_gcd(M, possible-1)

def main():
    N, M = map(int, input().split())
    first_possible = M//N
    print(search_max_gcd(M, first_possible))

main()

### FIXED CODE ###

from math import *

def main():
    N, M = map(int, input().split())
    if N==1:
        print(M)
        return
    special_value = M//N
    divisor_set = set(i for i in range(1, (int(sqrt(M)) + 1)) if (M % i == 0))
    divisor_set = divisor_set.union(M/j for j in divisor_set)
    print(int(max([i for i in divisor_set if special_value >= i])))
    return

main()
n, k = map(int, input().split())

if k == 0:
    print(hoge)
    exit()

if k > (n - 1) * (n - 2) // 2:
    print(-1)
    exit()

ans = [[0 for _ in range(n)] for _ in range(n)]

for i in range(1, n):
    ans[0][i] = 1

m = n-1

temp = (n-1) * (n-2) // 2 - k
for i in range(1, n):
    for j in range(i+1, n):
        ans[i][j] = 1
        m += 1
        temp -= 1
        if temp == 0:
            break
    if temp == 0:
        break

print(m)
for i in range(n):
    for j in range(n):
        if ans[i][j] == 1:
            print(i+1, j+1)

### FIXED CODE ###

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

if k > (n - 1) * (n - 2) // 2:
    print(-1)
    exit()

ans = [[0 for _ in range(n)] for _ in range(n)]

for i in range(1, n):
    ans[0][i] = 1

m = n-1

temp = (n-1) * (n-2) // 2 - k
for i in range(1, n):
    if temp == 0:
        break
    for j in range(i+1, n):
        ans[i][j] = 1
        m += 1
        temp -= 1
        if temp == 0:
            break

print(m)
for i in range(n):
    for j in range(n):
        if ans[i][j] == 1:
            print(i+1, j+1)
n, m = map(int,input().split())
students = [None]*n
points = [None]*m
for i in range(n):
  students[i] = tuple(map(int,input().split()))
for i in range(m):
  points[i] = tuple(map(int,input().split()))

ans = [None]*n
for s in students:
  tmp = [None]*m
  for p in points:
    tmp[p] = abs(students[s][0] - points[p][0]) + abs(students[s][1] - points[p][1])
  ans[s] = tmp.index(min(tmp))
for i in range(n):
  print(ans[i])


### FIXED CODE ###

n, m = map(int,input().split())
students = [None]*n
points = [None]*m
for i in range(n):
  students[i] = tuple(map(int,input().split()))
for i in range(m):
  points[i] = tuple(map(int,input().split()))

ans = []
for s in students:
  tmp = []
  for p in points:
    tmp.append(abs(s[0] - p[0]) + abs(s[1] - p[1]))
  ans.append(tmp.index(min(tmp)) + 1)
for i in range(n):
  print(ans[i])
n=int(input())
rec=[2,1]
for i in range(2,n):
  rec.append(rec[i-2]+rec[i-1])
print(rec[n])

### FIXED CODE ###

n=int(input())
rec=[2,1]
if n>=2:
    for i in range(2,n+1):
        rec.append(rec[i-2]+rec[i-1])
print(rec[n])
import sys

a,b = sys.stdin.readline().rstrip().strip(' ')
print(int(a)*int(b))

### FIXED CODE ###

import sys

a,b = map(int, sys.stdin.readline().rstrip().split(' '))
print("{} {}".format(a*b,(a+b)*2))
a,b,c = map(int, input().split())
a,b,c = c,a,b
print(f"{a} {b} {c}")

### FIXED CODE ###

a,b,c = map(int, input().split())
a,b,c = c,a,b
print("{} {} {}".format(a,b,c))
a, op, b = [input().split()]
eval(a+op+b)


### FIXED CODE ###

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

if op == "+":
    ans = a+b
else:
    ans = a-b
print(ans)
n,m = map(int,input().split())
ls = [[int(x) for x in input().split()] for _ in range(m)]

cnt = [[0] for _ in range(n+1)]

for i in range(m):
    idx = ls[i][0]
    cnt[idx].append(ls[i][1])

for i in range(m):
    cnt[i].sort()


for i in range(m):
    idx = ls[i][0]
    print("{:06d}{:06d}".format(idx,cnt[idx].index(ls[i][1])))

### FIXED CODE ###

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

for i in range(m):
    a,b = map(int,input().split())
    ls[a].append((b,i))
ans = [None]*m
for i,l in enumerate(ls):
    l.sort()
    for j,(a,b) in enumerate(l):
        ans[b]= "{:06d}{:06d}".format(i,j+1)
for i in range(m):
    print(ans[i])
int(input())
s = 180 * (n - 2)

print(s)
print(type(n))


### FIXED CODE ###

n = int(input())
s = 180 * (n - 2)
print(s)
S = input()
T = input()
res = ''
end = -1
for i in range(len(S) - len(T) + 1):
    for j in range(len(T)):
        start = i
        
        if S[i+j] == T[j]:
            end = i + j
            flag = 1
        elif S[i+j] == '?':
            end = i + j
            flag = 0
        else:
          	flag = 0
            pass
            break
    if flag == 1:
        break
            
if end == -1:
    print('UNRESTORABLE')
    
else:
    j = 0
    for i in range(len(S)):
        if start <= i <= end:
            res += T[j]
            j += 1

        elif S[i] == '?':
            res += 'a'

        else:
            res += S[i]

    print(res)

### FIXED CODE ###

S = input()
T = input()


    
if True:
    tmp = -1
    for i in range(len(S) - len(T) + 1):
        start = -1
        for j in range(len(T)):
            if S[i+j] == T[j] or S[i+j] == '?':
                start = i
            else:
                start = -1
                break
                
        
        if start != -1:
                tmp = i
    if tmp == -1:
        print('UNRESTORABLE')
    else:
        res = ''
        count = 0
        for i in range(len(S)):
            if tmp <= i < tmp + len(T):
                res += T[count]
                count += 1
            elif S[i] == '?':
                res += 'a'
            else:
                res += S[i]

        print(res)
N=int(input())
A=list(map(int,input().split()))
A.sort()
a=0
B=[]
C=[]
count=1
for i in range(len(A)):
    if A[i]==a:
        count+=1
    else:
        if count>=2:
            B.append(A[i-1])
        if count>=4:
            C.append(A[i-1])
        a=A[i]
        count=1
if count>=2:
    B.append(A[N-1])
if len(B)<2 and len(C)<1:
    print(0)
else:
    print(max(B[len(B)-1]*B[len(B)-2],C[len(C)]*C[len(C)]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
a=0
H=0
W=0
count=1
for i in range(len(A)):
    #print(A[i],H,W)
    if A[i]==a:
        count+=1
    else:
        if count>=4:
            if H<A[i-1]:
                H=A[i-1]
            if W < A[i - 1]:
                W=A[i-1]
        elif count>=2:
            if H!=0:
                W=A[i-1]
            else:
                H=A[i-1]
        a=A[i]
        count=1
        if H!=0 and W!=0:
            print(H*W)
            exit(0)
if count>=4:
    if H<A[i-1]:
        H=A[i-1]
    if W < A[i - 1]:
        W=A[i-1]
elif count>=2:
    if H!=0:
        W=A[i-1]
    else:
        H=A[i-1]
print(H*W)
# -*- coding: utf-8 -*-

from collections import deque

n = int(input())
word = deque()

for i in range(n):
    command, num = map(int, input().split())
    if command == 0:
        word.append(num)
    elif command == 1:
        print('{0}'.format(word[num]))
    elif command == 2:
        word.pop()



### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque

n = int(input())
word = deque()

for i in range(n):
    command = list(map(int, input().split()))
    if command[0] == 0:
        word.append(command[1])
    elif command[0] == 1:
        print('{0}'.format(word[command[1]]))
    elif command[0] == 2:
        word.pop()
N = input()

N = N % 10

if N == 2 or N == 4 or N == 5 or N == 7 or N == 9:
  print("hon")
  
elif N == 0 or N == 1 or N == 6 or N == 8:
  print("pon")
  
else:
  print("bon")

### FIXED CODE ###

N = int(input())

N = N % 10

if N == 2 or N == 4 or N == 5 or N == 7 or N == 9:
  print("hon")
  
elif N == 0 or N == 1 or N == 6 or N == 8:
  print("pon")
  
else:
  print("bon")
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10*5+2)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

    
    

### FIXED CODE ###

n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10**5+10)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)
import math
A, B = map(int, input().split())
print(A * B // math.gcd(A, B))


### FIXED CODE ###

import fractions
A, B = map(int, input().split())
print(A * B // fractions.gcd(A, B))
import numpy as np

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

if area<=a*b/2.0:
    h=2*area/b
    print(90-np.degrees(np.arctan(h/b)))
else:
    h=2*b-2*area/a
    print(np.degrees(np.arctan(h/a)))

### FIXED CODE ###

import numpy as np

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

if area<=a*b/2.0:
    h=2*area/b
    print(90-np.degrees(np.arctan(h/b)))
else:
    h=2*b-2*area/a
    print(np.degrees(np.arctan(h/a)))
N, K=map(int, input().split())
List=sorted(list(map(int,input().split())))
a = 0
for i in range(N - k):
  a = a + List[i]
print(a)

### FIXED CODE ###

N, K=map(int, input().split())
List=sorted(list(map(int,input().split())))
a = 0
for i in range(N - K):
  a = a + List[i]
print(a)
A, B = map(int, input().split())
 
if A % B == 0:
  print(A+B)
else:
  print(A-B)
A, B = map(int, input().split())

if A % B == 0:
  print(A+B)
else:
  print(B-A)

### FIXED CODE ###

A, B = map(int, input().split())
 
if B % A == 0:
  print(A+B)
else:
  print(B-A)
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]

def main():
    state = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for w in range(N):
            for h in range(N):
                cost = D[grid[h][w]-1][c]
                state[(h+w)%3][c] += cost

    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c3 == c1 or c3 == c2:
                    continue
                cost = state[0][c1] + state[1][c2] + state[2][c3]
                if c1 == 0 and c2 == 1 and c3 == 2:
                    ans = cost
                    continue
                ans = min(cost, ans)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

N = int(input())

if N < 1000:
    print('ABC')
else:
    print('ABD')
#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

flag = False
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
                flag = True
                print(f"{i} {j} {k}")
                break
        if flag:
            break
    if flag:
        break

if not flag:
    print("-1 -1 -1")


### FIXED CODE ###

#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

found = False
for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        k = n - (i + j)
        if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
            found = True
            print("{} {} {}".format(i, j, k))
            break
    if found:
        break

if not found:
    print("-1 -1 -1")
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    new = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            new = s_arr[start:j+1].sum(axis=0, keepdims=True)
            if np.any(new>k):
                new = -1
                break
            kouryo = np.concatenate((kouryo, new), axis=0)
            start=j+1
    if new == -1: continue
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    wa = kouryo[:, 0]
    for j in range(1, w):
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)
r = int(raw_input())
pai = 3.1415
print('%.5f %.5f' % (r*r*pai, 2*pai*r))

### FIXED CODE ###

import math
r = float(raw_input())
print('%.5f %.5f' % (r*r*math.pi, 2*math.pi*r))
n=int(input())
ans=1
t=0
for i in input().split():
    a=int(i)
    if pre==0:
        pre=a
    else:
        if pre>a:
            if -t<0 and t**2==1:
                ans+=1
                t=-2
            else:
                t=-1
        elif pre<a:
            if t<0 and t**2==1:
                ans+=1
                t=2
            else:
                t=1
        else:
            continue
print(ans)


### FIXED CODE ###

n=int(input())
pre=0
ans=1
t=0
for i in input().split():
    a=int(i)
    if pre==0:
        pre=a
    else:
        if pre>a:
            if -t<0 and t**2==1:
                ans+=1
                t=-2
            else:
                t=-1
        elif pre<a:
            if t<0 and t**2==1:
                ans+=1
                t=2
            else:
                t=1
        else:
            continue
        pre=a
print(ans)
A,B,C,D = map(int,input().split())
if abs(A-C)<=D:
  print('Yes')
else:
  if abs(A-B)<=D an abs(B-C)<=D:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

A,B,C,D = map(int,input().split())
if abs(A-C)<=D:
  print('Yes')
else:
  if abs(A-B)<=D and abs(B-C)<=D:
    print('Yes')
  else:
    print('No')
N = int(input())

numbers = list(map(int, input()))
counter = 0

while all(number % 2 == 0 for number in numbers):
    numbers = [number / 2 for number in numbers]
    counter += 1

print(counter)


### FIXED CODE ###

input()
numbers = list(map(int, input().split()))

counter = 0

while all(number % 2 == 0 for number in numbers):
    numbers = [number / 2 for number in numbers]
    counter += 1

print(counter)
n = r()
tens=1
nines=1
eights=1
mod = 10**9+7
for i in range(n):
    tens=(tens*10)%mod
    nines=(nines*9)%mod
    eights=(eights*8)%mod
print((tens-2*nines+eights)%mod)

### FIXED CODE ###

import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

n = r()
tens=1
nines=1
eights=1
mod = 10**9+7
for i in range(n):
    tens=(tens*10)%mod
    nines=(nines*9)%mod
    eights=(eights*8)%mod
print((tens-2*nines+eights)%mod)