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



MAX = 200005

def add_num(nn, x):
    if nn == -1:
        return
    Tree[nn][0] += x
    for ni in Tree[nn][1]:
        add_num(ni, x)


ipt = input().split()
N = int(ipt[0])
Q = int(ipt[1])



Tree = []
for m in range(MAX-1):
    Tree.append([-1, [-1]])

nodes = set()
nodes.add(1)

for i in range(N-1):
    ipti = input().split()
    a = int(ipti[0])
    b = int(ipti[1])

    Tree[a][0] = 0
    Tree[a][1].insert(0, b)
    Tree[b][0] = 0

    nodes.add(b)



for i in range(Q):
    ipti = input().split()
    p = int(ipti[0])
    x = int(ipti[1])

    cands = set()

    Tree[p][0] += x

    for pi in range(p,MAX-1):
        if Tree[pi] == -1:
            break
        for pii in Tree[pi][1]:
            cands.add(pii)
    for ci in cands:
        Tree[ci][0] += x

    #add_num(p, x)


for n in nodes:
    print(Tree[n][0])








### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
import sys

sys.setrecursionlimit(500000)

visited = set()

n,q = nm()

tval = [0]*n
t = [[] for _ in range(n)]

for i in range(n-1):
    a,b = nm()
    t[a-1].append(b-1)
    t[b-1].append(a-1)

for i in range(q):
    p,x = nm()
    tval[p-1] += x

ans = [0]*n
def dfs(num,val):
    visited.add(num)
    now = val+tval[num]
    ans[num] = now
    for nn in t[num]:
        if nn not in visited:
            dfs(nn,now)

dfs(0,0)

for i in ans:
    print(i)
### BUGGY CODE ###

n, b, r = map(int,input().split())
l = list()
k = 0
for i in range(0,n,b+r):
  for j in range(b):
    l.append('b')
  for j in range(r):
    l.append('r')
for j in range(b):
  l.append('b')
for j in range(r):
  l.append('r')
print(l[0:n].count('b'))

### FIXED CODE ###

n, b, r = map(int,input().split())
a = n//(b+r) * b
c = n%(b+r)
a += min(c,b)
print(a)
### BUGGY CODE ###

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

for i in range(1,n+1):
    j = a.index(i)
    b.append(str(j+1))

print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = [ int(i) for i in input().split()]
b = [""] * n

for i, ai in enumerate(a):
    b[ai-1] = str(i+1)

print(" ".join(b))
### BUGGY CODE ###

S=list(input())
Q=int(input())
which=0#0 normal #1 reverse
check=[list(map(str,input().split())) for i in range(Q)]
#print(check)
for i in range(Q):
    if check[i][0]=="1":
        which+=1
        which%=2
        continue
    if check[i][0]!="1":
        if which==0:
            if check[i][1]=="1":
                S.insert(0,check[i][2])
            if check[i][1]=="2":
                S.append(check[i][2])
        if which==1:
            if check[i][1]=="1":
                S.append(check[i][2])
            if check[i][1]=="2":
                S.insert(0,check[i][2])
if which==1:
    S=S[::-1]
print("".join(S))

### FIXED CODE ###

S=str(input())
Q=int(input())
which=0
front=""
back=""
for i in range(Q):
    a=list(map(str,input().split()))
    if a==["1"]:
        which+=1
        which%=2
        continue
    else:
        if which==0:
            if a[1]=="1":
                front=a[2]+front
            if a[1]=="2":
                back+=a[2]
        if which==1:
            if a[1]=="1":
                back+=a[2]
            if a[1]=="2":
                front=a[2]+front

S=front+S+back
if which==1:
    print(S[::-1])
if which==0:
    print(S)
### BUGGY CODE ###

s = input()
t = input()

dp = [[0 for i in range(len(s)+1)] for j in range(len(t)+1)]
s = "0"+s
t = "0"+t

q = []

for i in range(1, len(t)):
    for j in range(1, len(s)):
        if s[j] == t[i]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

i = len(t)-1
j = len(s)-1

while i != 0 and j != 0:
    if dp[i][j] != dp[i-1][j] and  dp[i][j] != dp[i][j-1]:
        q.append(t[i])
        i -= 1
        j -= 1
    elif dp[i][j] != dp[i-1][j] and  dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j] and  dp[i][j] != dp[i][j-1]:
        i -= 1
    else:
        i -= 1

print(''.join(q[::-1]))




### FIXED CODE ###

### The code is worked in dp, with a 2D matrix technique.

s = input()
t = input()

dp = [[0 for i in range(len(s)+1)] for j in range(len(t)+1)]
s = "0"+s
t = "0"+t

q = []

for i in range(1, len(t)):
    for j in range(1, len(s)):
        if s[j] == t[i]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

i = len(t)-1
j = len(s)-1

while i != 0 and j != 0:
    if dp[i][j] != dp[i-1][j] and  dp[i][j] != dp[i][j-1]:
        q.append(t[i])
        i -= 1
        j -= 1
    elif dp[i][j] != dp[i-1][j] and  dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j] and  dp[i][j] != dp[i][j-1]:
        i -= 1
    else:
        i -= 1

print(''.join(q[::-1]))
### BUGGY CODE ###

n=int(input())
d=1
for i in range(2,n+1):
  d*=i
print(int(d%int(7+1e9)))

### FIXED CODE ###

import math;print(math.factorial(int(input()))%int(7+1e9))
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
  w,v=map(int,input().split())
  for j in range(1,W+1):
    if w<=j:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
    else:
      dp[i][j]=dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
w=[0 for i in range(N+1)]
v=[0 for i in range(N+1)]
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())
N_max=max(v[i] for i in range(N+1))
INF=float('inf')
dp=[[INF for i in range(N*N_max+1)]for j in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  for j in range(N*N_max+1):
    if v[i]<=j:
      dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    else:
      dp[i][j]=dp[i-1][j]
ans=0
for i in range(1,N*N_max+1):
  if dp[N][i]<=W:
    ans=i
print(ans)
### BUGGY CODE ###

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

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()

dp = list3d(N+1, 4, 1000, 0)
dp[0][0][0] = 1
for i in range(N):
    a = int(S[i])
    for j in range(4):
        for k in range(1000):
            dp[i+1][j][k] |= dp[i][j][k]
            if j == 0 and k+a*100 < 1000:
                dp[i+1][j+1][k+a*100] |= dp[i][j][k]
            if j == 1 and k+a*10 < 1000:
                dp[i+1][j+1][k+a*10] |= dp[i][j][k]
            if j == 2 and k+a < 1000:
                dp[i+1][j+1][k+a] |= dp[i][j][k]
ans = 0
for k in range(1000):
    ans += dp[N][3][k]
print(ans)


### FIXED CODE ###

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

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 list4d(a, b, c, d, e): return [[[[e] * d for j in range(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(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()

def check(x):
    i = 0
    for a in S:
        if a == x[i]:
            i += 1
            if i == 3:
                return True
    return False

cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x = str(i)+str(j)+str(k)
            if check(x):
                cnt += 1
print(cnt)
### BUGGY CODE ###

import bisect

n = (int)(input())
a = sorted(list(map(int, input().split(" "))))
b = sorted(list(map(int, input().split(" "))))
c = sorted(list(map(int, input().split(" "))))

count = 0
for i in b:
  #print((a[:bisect.bisect(a, i - 1)]), i, c[bisect.bisect_left(c, i + 1):]) 
  count += len(a[:bisect.bisect(a, i - 1):]) * len(a[bisect.bisect_right(c, i):]) 
print(count)

### FIXED CODE ###

import bisect

n = (int)(input())
a = sorted(list(map(int, input().split(" "))))
b = list(map(int, input().split(" ")))
c = sorted(list(map(int, input().split(" "))))

count = 0
for i in b:
  #print((a[:bisect.bisect_right(a, i - 1)]), i, c[bisect.bisect_left(c, i + 1):]) 
  #print(bisect.bisect_right(a, i - 1), i, (n - bisect.bisect_left(c, i + 1)) ) 
  count += bisect.bisect_right(a, i - 1) * (n - bisect.bisect_left(c, i + 1)) 
print(count)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
seen = set()
maxN = 1e6
count = 0
for i in range(1, n):
    if arr[i] == arr[i-1]:
        seen.add(arr[i])
for num in arr:
    if num not in seen:
        count += 1
    curr = num
    while curr <= maxN:
        seen.add(curr)
        curr += num
print(count)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
ap = defaultdict(int)
for i in range(1, n):
    if arr[i] == arr[i-1]:
        ap[arr[i]] = 1
        
for i in range(n):
    if not ap[arr[i]]:
        count += 1
    if i == 0 or arr[i] != arr[i-1]:
        for j in range(arr[i], 1000001, arr[i]):
            ap[j] = 1
print(count)
### BUGGY CODE ###

import math
import sys

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

def nCr(n, r):
  c = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  return c

for i in range(m-1):
  if a[i] + 1 == a[i+1]:
    print('0')

    sys.exit()


a.insert(0, -1)
a.append(n+1)

cnt = 1

for i in range(m+1):
  step = (a[i+1] - 1) - (a[i] + 1)
  pattern = 1
  for j in range(1, step//2 + 1):
    pattern += nCr(step - j, j)
  cnt *= pattern

print(cnt%1000000007)

### FIXED CODE ###

n,m = map(int, input().split())
step = []

now = 0
for i in range(m):
  next = int(input()) - 1
  step.append(next - now)
  now = next + 2

step.append(n-now)  
step.sort()

def fibo():
  s = []
  a = 1
  b = 1
  s.append(a)
  s.append(b)
  for i in range(n):
    c = a+b
    a = b
    b = c
    s.append(c)
  return s

ans = 1

if step[0] < 0:
  ans = 0

else:
  f = fibo()
  for i in step:
    ans *= f[i]

print(ans % 1000000007)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
indices = {}
for i in range(n):
    indices.setdefault(s[i], [])
    indices[s[i]].append(i)
g = [1 for _ in range(n)]
for _ in range(q):
    t, d = input().split()
    for i in indices.get(t, []):
        if d == 'L':
            if i != 0:
                g[i-1] += g[i]
        else:
            if i != n-1:
                g[i+1] += g[i]
        g[i] = 0
print(sum(g))

### FIXED CODE ###

import sys
def vanish_on_left(i, n, s, tds):
    for t, d in tds:
        if s[i] != t:
            continue
        if d == 'L':
            if i == 0:
                return True
            i -= 1
        else:
            if i == n-1:
                return False
            i += 1
    return False

def vanish_on_right(i, n, s, tds):
    for t, d in tds:
        if s[i] != t:
            continue
        if d == 'L':
            if i == 0:
                return False 
            i -= 1
        else:
            if i == n-1:
                return True
            i += 1
    return False


n, q = map(int, input().split())
s = input()
tds = []
for _ in range(q):
    tds.append(tuple(input().split()))
if vanish_on_left(0, n, s, tds):
    if vanish_on_left(n-1, n, s, tds):
        print(0)
        sys.exit()
    l0, r0 = 1, n-1
    while l0 < r0:
        k = (l0 + r0) // 2
        if vanish_on_left(k, n, s, tds):
            l0 = k+1
        else:
            r0 = k
else:
    l0 = 0
if vanish_on_right(n-1, n, s, tds):
    if vanish_on_right(l0, n, s, tds):
        print(0)
        sys.exit()
    l1, r1 = l0, n-2
    while l1 < r1:
        k = (l1 + r1 + 1) // 2
        if vanish_on_right(k, n, s, tds):
            r1 = k-1
        else:
            l1 = k
else:
    l1 = n-1
print(l1 - l0 + 1)
### BUGGY CODE ###

from string import ascii_lowercase


def solve(s):
    d = {c: {0: ''} for c in ascii_lowercase}
    while True:
        e = {}
        ans = set()
        for c in ascii_lowercase:
            f = {}
            for dc, dd in d.items():
                for di, ds in dd.items():
                    ci = s.find(c, di) + 1
                    ns = ds + c
                    if not ci:
                        ans.add(ns)
                        continue
                    if ci in f and ns > f[ci]:
                        continue
                    f[ci] = ns
            e[c] = f
        if ans:
            return min(ans)
        d = e


print(solve(input().strip()))


### FIXED CODE ###

from string import ascii_lowercase
from bisect import bisect


def solve(s):
    pos = [[] for _ in range(26)]
    offset = ord('a')
    for i, c in enumerate(s):
        c = ord(c) - offset
        pos[c].append(i)
    for l in pos:
        l.append(len(s))

    all_char_sequence_start_pos = []
    pos_i = [len(l) - 1 for l in pos]
    while all(pi >= 0 for pi in pos_i):
        i = min(l[pi] for pi, l in zip(pos_i, pos))
        all_char_sequence_start_pos.append(i)
        for j in range(26):
            while pos_i[j] >= 0 and pos[j][pos_i[j]] >= i:
                pos_i[j] -= 1
    all_char_sequence_start_pos.reverse()
    ans = []
    curr = -1
    for i in all_char_sequence_start_pos:
        for c in range(26):
            cj = bisect(pos[c], curr)
            j = pos[c][cj]
            if j >= i:
                ans.append(c)
                curr = j
                break
    return ''.join(chr(c + offset) for c in ans)


print(solve(input().strip()))
### BUGGY CODE ###

n = int(input())
an = list(input().split())
b = []

cnt = 1
for i in an:
    if cnt % 2 == 0 :
        b.insert(0, i)
    else:
        b.append(i)
    cnt += 1

if n % 2 == 1:
    b.reverse()

print(' '.join(b))


### FIXED CODE ###

n = int(input())
a = list(input().split())
if n == 1:
    print(a[0])
elif n % 2:
    print(*(a[-1::-2] + a[1::2]))
else:
    print(*(a[-1::-2] + a[0::2]))
### BUGGY CODE ###

s = input()
k = int(input())

len_s =  len(s)
L = []

for i in range(1, len_s+1):
    for j in range(len_s-i+1):
        L.append(s[j:j+i])
L = list(set(L))
L.sort()
print(L[k-1])


### FIXED CODE ###

s = input()
k = int(input())

len_s =  len(s)
L = []
m = 0
for i in range(1, k+1):
    for j in range(len_s-i+1):
        if s[j:j+i] not in L:
            L.append(s[j:j+i])


L.sort()
print(L[k-1])
### BUGGY CODE ###

n = int(input())
a=[0]
for i in range(n):
  a.append(int(input()))
c = 1
k = a[1]
while k != 1:
  if k == 2:
    print(c)
    exit()
  k = a[k]
  c += 1
print(-1)  

### FIXED CODE ###

n = int(input())
a=[0]
for i in range(n):
  a.append(int(input()))
c = 1
k = a[1]
while c <= n:
  if k == 2:
    print(c)
    exit()
  k = a[k]
  c += 1
print(-1)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

if (ans > 1000000000000000000):
    ans = -1

print(ans)


### FIXED CODE ###

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

A.sort()

ans = 1
for a in A:
    ans *= a
    if ans ==0 or ans > 1000000000000000000:
        break
    
if (ans > 1000000000000000000):
    ans = -1

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

# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    ret = m*pow(m-1, n-1, mod) % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*pow(m-1, n-1-i, mod)*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    ncr = 1
    p = m*bpow(m-1, n-1, mod) % mod
    ret = p
    inv = bpow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*bpow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import collections
s=list(map(str,input()))
c=0
cl=collections.Counter(s)
while cl["1"]!=0 and cl["0"]!=0 :
    for i in range(1,len(s)):
        if s[i-1] != s[i]:
            del s[i-1]
            del s[i-1]
            c+=2
            cl=collections.Counter(s)
            break
        else:
            pass

print(c)
    


### FIXED CODE ###

import collections
s=list(map(str,input()))
c=collections.Counter(s)
print(2*min(c["1"],c["0"]))
### BUGGY CODE ###

from sys import stdin
readline = stdin.readline
H, N = map(int, readline().split())
AB = [list(map(int, readline().split())) for _ in range(N)]

dp = [100000000] * (H + 10 ** 4 + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == 100000000:
        continue
    for a, b in AB:
        t = dp[i] + b
        if t < dp[i + a]:
            dp[i + a] = t
print(min(dp[H:]))




### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()
### BUGGY CODE ###

N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    lst = [0] * P
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * pow(10, N - n - 1, P)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    def rec(i, j, k):
        if dp[i][j][k] >= 0:
            return dp[i][j][k]
        if i == 0 and j == 0 and k == 0:
            return 0.0

        res = 0.0
        if i > 0:
            res += rec(i - 1, j, k) * i
        if j > 0:
            res += rec(i + 1, j - 1, k) * j
        if k > 0:
            res += rec(i, j + 1, k - 1) * k
        res += N
        res *= 1.0 / (i + j + k)
        dp[i][j][k] = res

        return dp[i][j][k]

    N = int(input())
    A = list(map(int, input().split()))
    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
    print(rec(one, two, three))


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for sushi in range(1, N + 1):
        for k in range(sushi + 1):
            for j in range(0, sushi - k + 1):
                i = sushi - k - j
                if i != 0:
                    dp[i][j][k] += dp[i - 1][j][k] * i / sushi
                if j != 0:
                    dp[i][j][k] += dp[i + 1][j - 1][k] * j / sushi
                if k != 0:
                    dp[i][j][k] += dp[i][j + 1][k - 1] * k / sushi
                dp[i][j][k] += N / sushi
    print(dp[one][two][three])


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

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

ans = 1

for i in range(M):
  temp = 0
  l = int(input()) - 1
  if s > l:
    print(0)
    exit()
  step = l - s
  for j in range(1 + (step // 2)):
    temp += comb(step-j, j)
    temp = temp % MOD
  ans *= temp
  ans = ans % MOD
  s = l + 2
l = N
step = l - s
temp = 0
for i in range(1 + (step // 2)):
  temp += comb(step-i, i)
  temp = temp % MOD
ans *= temp
ans = ans % MOD

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
s = 0

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

def calc_from_step(step):
  temp = 0
  for i in range(1 + (step // 2)):
    temp += comb(step-i, i)
  return temp


arr = [1, 1]
steps = []
step = 0
s = 0
for i in range(M):
  l = int(input()) - 1
  steps.append(l-s)
  if s > l:
    print(0)
    exit()
  if step < l - s:
    step = l - s
  s = l + 2
l = N
steps.append(l-s)
if step < l - s:
  step = l - s

for i in range(step - 1):
  arr.append((arr[i] + arr[i+1])%MOD)
ans = 1

for i in steps:
  ans *= arr[i]
  ans = ans % MOD
print(ans)
### BUGGY CODE ###

import numpy as np


N = int(input())
A = np.array([int(i) for i in input().split()])
Q = int(input())
B, C = [], []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for b, c in zip(B, C):
    A = np.where(A==b, c, A)
    print(A.sum())

### FIXED CODE ###

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

sum_A = sum(A)
memo = [0] * 100001
for a in A:
    memo[a] += 1

for _ in range(Q):
    B, C = map(int, input().split())
    sum_A += (C - B) * memo[B]
    memo[C] += memo[B]
    memo[B] = 0
    print(sum_A)
### BUGGY CODE ###

#14:05
n = int(input())
krus = []
wf = []
for i in range(n):
  tmp = list(map(int,input().split()))
  wf.append(tmp)
  for j in range(n):
    krus.append([tmp[j],i,j])
krus.sort()
#print(krus)
ans = 0
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][j] > wf[i][k] + wf[k][j]:
        print(-1)
        exit()
inf = 10 ** 3
wf = [[inf for _ in range(n)] for _ in range(n)]
for x in krus:
  d,i,j = x
  if wf[i][j] == d:
    continue
  wf[i][j] = d
  ans += d
  for a in range(n):
    for b in range(n):
      wf[a][b] = min(wf[a][b], wf[a][i] + d + wf[j][b])
      wf[b][a] = min(wf[b][a], wf[b][i] + d + wf[j][a])
  #print(wf)
  #print(x)
print(ans//2)

### FIXED CODE ###

n = int(input())
wf = []
for _ in range(n):
  wf.append(list(map(int,input().split())))
cnt = [[0 for _ in range(n)] for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][j] > wf[i][k] + wf[k][j]:
        print(-1)
        exit()
      elif wf[i][j] == wf[i][k] + wf[k][j]:
        cnt[i][j] += 1
#print(cnt)
ans = 0
for i in range(n):
  for j in range(n):
    if cnt[i][j] <= 2:
      ans += wf[i][j]
print(ans//2)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans =0 
for i in range(0,N):
    for j in range(0,i):
        if(P[i]>P[j]):
            break
    else: 
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0 
m = 10 ** 6
for i in range(N):
    if m > P[i]:
        ans += 1
    m = min(m,P[i])
print(ans)