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

def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**18
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used=defaultdict(lambda:True)
  l=[]
  f=g=False
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    if a<2:f=True
    if b==n:g=True
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
  if not(f and g):
    print(-1)
    exit()
  d=defaultdict(lambda:inf)
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while len(edgelist):
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min(d[i]for i in set(l))
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

ans = 1
for i in a:
  ans *= i
if ans <= 10**18:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

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

if 0 in a:
  print(0)
  exit()

ans = 1
for i in a:
  ans *= i
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()

L=[0]*9
D=[0]*100
C=0
for i in range(N-2):
    if(C==1000):
        break
    for j in range(i+1,N-1):
        s=str(S[i])+str(S[j])
        if(D[int(s)]==0):
            D[int(s)]=1
            C+=len(set(S[j+1:N]))
print(C)



### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for a in range(10):
  for b in range(10):
    for c in range(10):
      a, b, c = str(a), str(b), str(c)
      a_find = s.find(a)
      if a_find == -1:
        continue
      b_find = s.find(b, a_find + 1)
      if b_find == -1:
        continue
      c_find = s.find(c, b_find + 1)
      if c_find == -1:
        continue
      ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split(" ")))
#n=7
#a=[1,-1,1,-1,1,-1,1]
c=0
for i in range(n):
  for j in range(i+1,n+1):
    if sum(a[i:j])==0:
      c+=1
print(c)

### FIXED CODE ###

import collections

n=int(input())
a=list(map(int,input().split(" ")))
#n=5
#a=[1,-2,3,-4,5]
s=[0 for i in range(n+1)]
for i in range(1,n+1):
  s[i]=s[i-1]+a[i-1]
c=collections.Counter(s).most_common()
d=0
for i in c:
  if i[1]<2:
    break
  d+=i[1]*(i[1]-1)//2
print(d)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    k = I()
    seen = set()
    h = []
    for i in range(len(s)):
        curS = s[i]
        if curS not in seen:
            heapq.heappush(h, curS)
            seen.add(curS)
        for j in range(i+1, len(s)):
            curS += s[j]
            if curS not in seen:
                heapq.heappush(h, curS)
                seen.add(curS)
    print(heapq.nsmallest(k, h)[-1])

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    K = I()
    subs = set()
    for j in range(1, 6):
        for i in range(len(s)):
            st = i
            en = min(st + j, len(s))
            subs.add(s[st:en])
    print(sorted(list(subs))[K-1])
main()
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    count = 0
    while count < b:
        a.append(c)
        count += 1
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []
for i in range(m):
    b, c = map(int, input().split())
    l.append((b, c))
for i in a:
    l.append((1, i))
l.sort(key=lambda x: x[1], reverse=True)
#print(l)
count = n
ans = 0
for item in l:
    b, c = item
    ans += c*min(b, count)
    count -= b
    if count <= 0:
        break
print(ans)
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = collections.deque([])
res = collections.deque([])
tree = collections.deque([])
level = collections.deque([])
parent = collections.deque([])
cache = collections.deque([])
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)
    parent.append(-1)
    cost.append(0)
    cache.append(-1)

for loop in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for loop in range(q):
    p, x = map(int, input().split())
    cost[p] += x

def make_level(index, lev, pp):
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        if level[next] != -1:
            continue
        parent[next] = index
        cost[next] += cost[index]
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

res = list(map(str, cost))
print(" ".join(res[1:n+1]))

### FIXED CODE ###

edge = []
n, q = map(int, input().split())
for _ in range(n+100):
    edge.append([])
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
res = [0] * (n+1)
cost = [0] * (n+1)
for _ in range(q):
    a,b = map(int, input().split())
    res[a] += b

import collections
q = collections.deque([[1, 0]])
used = [False] * (n+1)
while len(q) > 0:
    #print(q)
    curnode, cost = q.popleft()
    res[curnode] += cost
    used[curnode] = True
    for i in range(len(edge[curnode])):
        nnext = edge[curnode][i]
        if used[nnext] is True:
            continue
        else:
            q.append([nnext, res[curnode]])
res=res[1:]
print(" ".join(list(map(str, res))))
### BUGGY CODE ###

def main():
    S=input()
    N=len(S)
    cnt=0
    for i in range(N-1):
        for j in range(i+1, N):
            if int(S[i:j+1])%2019==0:
                cnt+=1
    print(cnt)

main()


### FIXED CODE ###

def main():
    MOD=2019
    S=input()[::-1]
    count=[1]+[0]*MOD
    r,tmp=0,1
    for i in S:
        r += int(i)*tmp
        r %= MOD
        tmp *= 10
        tmp %= MOD
        count[r] += 1

    print(sum([i*(i-1)//2 for i in count]))

main()
### BUGGY CODE ###

from collections import defaultdict
import math

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

MOD = 10 ** 9 + 7

primes = defaultdict(int)

for a in A:
    x = a
    p = 2
    for p in range(2, int(math.sqrt(a)) + 1):
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        primes[p] = max(primes[p], cnt)
    if x > 1:
        primes[x] = max(primes[x], 1)

l = 1
for p in primes:
    l = (l * pow(p, primes[p], MOD)) % MOD

res = 0
for a in A:
    res = (res + l * pow(a, MOD - 2, MOD)) % MOD

print(res)


### FIXED CODE ###

from fractions import gcd
import sys

input = sys.stdin.readline

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

MOD = 10 ** 9 + 7


def lcm(a, b):
    return a * b // gcd(a, b)


l = A[0]
for a in A:
    l = lcm(l, a)

res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD)) % MOD) % MOD
    # res = (res + l // a) % MOD

print(res)
### BUGGY CODE ###

N = int(input())
train = [[] for _ in range(N)]
take_time = []
for cnt in range(N - 1):
    x, y , z = map(int,input().split())
    take_time.append(x)
    for _ in range(10**6+1):
        train[cnt].append(y)
        y += z

from bisect import bisect_left
for place in range(N):
    now = 0
    for i in range(place,N - 1):
        index = bisect_left(train[i],now)
        now = train[i][index]
        now += take_time[i]
    print(now)



### FIXED CODE ###

N = int(input())
train = [[] for _ in range(N)]
L = []
for cnt in range(N - 1):
    l = list(map(int,input().split()))
    L.append(l)

from math import ceil

from bisect import bisect_left
for place in range(N):
    now = 0
    for i in range(place,N - 1):
        k = max(0,ceil((now - L[i][1]) / L[i][2]))
        now = L[i][1] + L[i][2] * k
        now += L[i][0]
    print(now)
### BUGGY CODE ###

H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
for i in range(Q):
	L,R=list(map(int,input().split()))
	S=[0]*(H*W+1)
	for i in range(D+1,H*W+1):
		S[i]=S[i-D]+abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])
	print(S[R]-S[L])

### FIXED CODE ###

H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
L=[]
R=[]
S=[0]*(H*W+1)

for i in range(Q):
	l,r=list(map(int,input().split()))
	L.append(l)
	R.append(r)

for i in range(D+1,H*W+1):
	S[i]=S[i-D]+abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])

for i in range(Q):
	print(S[R[i]]-S[L[i]])
### BUGGY CODE ###

import numpy as np
n, m, k = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]
B = [int(n) for n in input().split()]

A = [a for a in np.cumsum([0] + A) if a <= k]
B = [b for b in np.cumsum([0] + B) if b <= k]
n_read = max([i + j for i, a in enumerate(A) for j, b in enumerate(B) if a + b <= k])
print(n_read)

### FIXED CODE ###

from numpy import cumsum
n, m, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = cumsum([0] + A)
B = cumsum([0] + B)
n_read = 0
l = len(B) - 1
for i, a in enumerate(A):
    if a > k:
        break
    for j, b in enumerate(B[l::-1]):
        if a + b <= k:
            l -= j
            n_read = max(n_read, i + l)
            break
print(n_read)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [[None] * (N + 1) for _ in range(N + 1)]
    def dp(r, l, A, c):
        if r == l:
            return A[r]
        if c[r][l] != None:
            return c[r][l]
        t = max(-dp(r + 1, l, A, c) + A[r],
                -dp(r, l - 1, A, c) + A[l])
        c[r][l] = t
        return t
    
    print(dp(0, N - 1, A, c))


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * N
    for r in reversed(range(N)):
        ar = A[r]
        c[r] = t = ar
        for l in range(r + 1, N):
            c[l] = t = max(ar - c[l], A[l] - t)
    
    print(c[-1])


main()
### BUGGY CODE ###

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

s = x

ans = 0

#print(s[0],s[1],s[2])

for i in range(2**(len(s))):
    tmp = i
    #print(tmp,tmp,tmp)
    temp = 0
    cnt = 0
    for j in range(len(s)):
        #print(ans)
        #temp += int(s[j])
        #print(temp)
        if tmp % 2 == 0:
            #temp = temp * 10
            #print(0)
            b = 1
            #if j == len(s)-2:
                #ans += temp + int(s[j+1])
        else:
            #ans += s[i]
            temp += x[j]
            cnt += 1
            #ans += temp
            #temp = 0
        if j == len(s)-1:
            #ans += temp + int(s[j+1])
            if cnt == 0:
                continue
            #print(temp,cnt,a)
            if temp / cnt == a:
                #print(temp,cnt)
                ans += 1
        tmp = tmp // 2
    
print(ans)

### FIXED CODE ###

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

sum_x = sum(x)

dp = [[[0 for i in range(n+1)]for j in range(sum_x+1)]for k in range(n+1)]

dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(sum_x+1):
            dp[i+1][k][j] += dp[i][k][j]
            if k + x[i] > sum_x:
                continue
            dp[i+1][k+x[i]][j+1] += dp[i][k][j]
            
ans = 0

for i in range(n):
    if a*(i+1) > sum_x:
        break
    ans += dp[n][a*(i+1)][i+1]

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

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
if 1 in a:
    dp[1]=0
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[None]*(n+1)
dp[0]=1
dp[1]=1
if 1 in a:
    dp[1]=0
for i in a:
    dp[i]=0
for i in range(2,n+1):
    if dp[i]!=0 :
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%(10**9+7))
### BUGGY CODE ###

h, ｎ = map(int, input().split())
dp = [10**10] * (h + 1)
dp[0]=0
ab = []

for i in range(n):
  temp = list(map(int, input().split()))
  ab.append(temp)

for i in range(h):
  t = 10 ** 10
  for j in ab:
    ht = i + j[0]
    if ht >= h: ht = h
    dp[ht] = min(dp[ht], dp[i] + j[1]) 

print(dp[h])


### FIXED CODE ###

h, ｎ = map(int, input().split())
dp = [-1] * (h + 1)
dp[0]=0
ab = []

for i in range(n):
  temp = list(map(int, input().split()))
  ab.append(temp)

for i in range(h):
  if dp[i] == -1: continue
  for j in ab:
    ht = i + j[0]
    if ht >= h: ht = h
    if dp[ht] != -1:
      dp[ht] = min(dp[ht], dp[i] + j[1])
    else:
      dp[ht] = dp[i] + j[1]

print(dp[h])
### BUGGY CODE ###

import bisect


N, Q = map(int, input().split(" "))
check_points = [input() for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect.bisect_left
for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        if time[q] == -1 or time[q] > x:
            time[q] = x

for q in querys:
    print(time[q])


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

def gcd(a,b):
    if a<b: a,b=b,a
    while b: a,b = b, a%b
    return a
def main():
  a, b = map(int, input().split())
  c = gcd(a, b)
  ans = 1
  i = 2
  while c!=1:
    if c%i==0: ans+=1
    while c%i==0: c//=i
    i+=1
  print(ans)
if __name__=="__main__":main()

### FIXED CODE ###

def prefactor(x):
  ret = set()
  for i in range(2, int(x**0.5)+1):
    if x%i==0: ret.add(i)
    while x%i==0: x //= i
  if x>1: ret.add(x)
  return ret
    

a, b = map(int, input().split())
print(1+len(prefactor(a) & prefactor(b)))
### BUGGY CODE ###

from collections import Counter
import numpy as np
n=int(input())
c=input()
d=Counter(c)
wn,rn=Counter(c)["W"], Counter(c)["R"]

MIN=min(wn,rn)
ans=np.full(n+1,200001)

for i in range(MIN):
  w=Counter(c[:i])["W"]
  r=rn-(i-w)
  if w<=r:
    ans[i]=r
  else:
    ans[i]=w
    
l=[i for i in range(n) if ans[i]!=200001]

if l:
  print(np.min(ans))
else:
  print(0)


### FIXED CODE ###

from collections import Counter
n=int(input())
c=input()
d=Counter(c)
w,r=Counter(c)["W"], Counter(c)["R"]
ans=0
for i in range(r):
  if c[i]=="W":
    ans+=1

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

N = int(input())
An = list(map(int, input().split()))
Bn = []
Bn.append(0)
for i, A in enumerate(An):
    Bn.append(A+Bn[i])
ans = 0
for i in range(N+1):
    for j in range(i+1, N+1):
#         print(i, Bn[i], j, Bn[j])
        if (Bn[i] == Bn[j]):
#             print("0")
#             print(An[i:j])
            ans += 1
print(ans)


### FIXED CODE ###

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

N = int(input())
An = list(map(int, input().split()))
Bn = []
Bn.append(0)
for i, A in enumerate(An):
    Bn.append(A+Bn[i])
Cn = collections.Counter(Bn)
ans = 0
for c in Cn.values():
    if c < 2:
        continue
    ans += c * (c-1) // 2
print(ans)
### BUGGY CODE ###

# coding: utf-8
#-------------------------------------------------------------------
import sys
#def p(*a):
  #s=" ".join(map(str,a))
  ##print(s)
  #sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

H,W=map(int, input().split())
M = list( list(input()) for _ in range(H) )

#p(H,W)
#p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

#p(M)


for h in range(H):
	for w in range(W-1):
		i=M[h][0+w]
		j=M[h][1+w]
		
		if i==0: continue
		if j==0: M[h][1+w]=i+1
		if j>i+1:M[h][1+w]=i+1

	for w in range(W-1):
		i=M[h][-1-w]
		j=M[h][-2-w]

		if i==0: continue
		if j==0: M[h][-2-w]=i+1
		if j>i+1:M[h][-2-w]=i+1

#p(M)

for w in range(W):
	for h in range(H-1):
		i=M[0+h][w]
		j=M[1+h][w]
		
		if i==0: continue
		if j==0: M[1+h][w]=i+1
		if j>i+1:M[1+h][w]=i+1
	
	for h in range(H-1):
		i=M[-1-h][w]
		j=M[-2-h][w]
	
		if i==0: continue
		if j==0: M[-2-h][w]=i+1
		if j>i+1:M[-2-h][w]=i+1

#p(M)

ans=0
for h in range(H):
	ans=max(ans, max(M[h]))

print( max(0,ans-1) )



### FIXED CODE ###

H, W = map(int, input().split())


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

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

n,k =map(int,input().split())
h =[0]*n

for i in range(n):
  h[i]= int(input())

sort_h = sorted(h)
diff=10**9

for times in range(n-k+1):
  maxh=0
  minh=10**9
  for i in range(times,k+times):
    if sort_h[i] > maxh:
      maxh= sort_h[i]
    if sort_h[i] < minh:
      minh=sort_h[i]

  if diff > maxh-minh:
    diff = maxh-minh

print(diff)

### FIXED CODE ###

n,k =map(int,input().split())
h =[0]*n

for i in range(n):
  h[i]= int(input())

sort_h = sorted(h)
diffmin=10**9

for times in range(n-k+1):

  diff = sort_h[k+times-1]-sort_h[times]
  if diffmin > diff:
    diffmin=diff

print(diffmin)
### BUGGY CODE ###

from functools import reduce
N = int(input())
A = reduce(lambda x, y:x*y if x*y <= 10**18 else -1, map(int, input().split()))
print(A)


### FIXED CODE ###

from math import log
from functools import reduce
N = int(input())
A = sorted(list(map(int, input().split())))
if A[0] == 0:
  print(0)
else:
  ans = 1
  for a in reversed(A):
    ans *= a
    if ans > 10**18:
      ans = -1
      break
  print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
  res=0
  for j in range(i,i+k):
    res+=p[j]/2+float(0.5)
  ans=max(ans,res)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
data=[0]*n
for i in range(n):
  data[i]=p[i]/2+float(0.5)
res=sum(data[0:k])
ans=sum(data[0:k])
for i in range(n-k):
  res-=data[i]-data[i+k]
  ans=max(ans,res)
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md
def way(h, w):
    if h < 0 or w < 0:
        return 0
    else:
        return com(h + w, h)

# combinationの準備
# md>n_maxの条件
md = 10 ** 9 + 7
n_max = 200005
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def main():
    h, w, n = MI()
    rc = [LI1() for _ in range(n)]
    # i番目の壁まで無傷で来る方法の数
    # (全ルート)－(i-1までの壁にぶつかる分)
    rc.sort(key=lambda x: x[0] + x[1])
    dp = [0] * n
    for i, (r, c) in enumerate(rc):
        dp[i] = way(r, c) - sum(v * way(r - pr, c - pc) % md for v, (pr, pc) in zip(dp[:i], rc[:i]))
        dp[i] %= md
    h, w = h - 1, w - 1
    ans = way(h, w) - sum(v * way(h - r, w - c) % md for v, (r, c) in zip(dp, rc))
    print(ans % md)

main()


### FIXED CODE ###

def f():
    h, w, n = map(int, input().split())
    md = 10 ** 9 + 7
    k = [list(map(int, input().split())) for _ in range(n)] + [[h, w]]

    # 壁をマンハッタン距離順に
    k.sort(key=lambda x: x[0] + x[1])

    # 階乗と逆元とコンビネーションを事前準備
    fct = [1]
    re_fct = []
    fct_i = 1
    for i in range(1, h + w + 1):
        fct_i = fct_i * i % md
        fct += [fct_i]
    # fct_i**(md-2)が逆元re_i
    re_i = 1
    p = md - 2
    while p:
        if p & 1:
            re_i = re_i * fct_i % md
        p >>= 1
        fct_i = fct_i ** 2 % md
    for i in range(h + w, -1, -1):
        re_fct += [re_i]
        re_i = re_i * i % md
    re_fct = re_fct[::-1]
    cmb = lambda a, b: fct[a] * re_fct[b] * re_fct[a - b] % md

    # こっから本体
    dp = [0] * (n + 1)
    for i, [r, c] in enumerate(k):
        dpi = cmb(r + c - 2, r - 1) % md
        for j in range(i):
            dr, dc = r - k[j][0], c - k[j][1]
            if dr >= 0 and dc >= 0:
                dpi = (dpi - dp[j] * cmb(dr + dc, dr)) % md
        dp[i] = dpi
    print(dp[-1])


f()