Harryxun/stf_run huggingface dataset:
from collections import deque

S = input()
B = deque()
res = 0
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    A = list(map(str, input().split()))
    if int(A[0]) == 1:
        if res == 0:
            res = 1
        else:
            res = 0
    else:
        if int(A[1]) == 1:
            if res == 0:
                B.appendleft(A[2])
            else:
                B.append(A[2])
        else:
            if res == 0:
                B.append(A[2])
            else:
                B.appendleft(A[2])
if res == 0:
    print(''.join(B))
else:
    B = B[::-1]
    print(''.join(B))

### FIXED CODE ###

from collections import deque

S = input()
B = deque()
res = 0
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    A = list(map(str, input().split()))
    if int(A[0]) == 1:
        if res == 0:
            res = 1
        else:
            res = 0
    else:
        if int(A[1]) == 1:
            if res == 0:
                B.appendleft(A[2])
            else:
                B.append(A[2])
        else:
            if res == 0:
                B.append(A[2])
            else:
                B.appendleft(A[2])
if res == 0:
    print(''.join(B))
else:
    B.reverse()
    print(''.join(B))
n = int(input())
a = [int(n) for n in input().split(" ")]

a.sort()

print(a[::-2] - a[-2::-2])

### FIXED CODE ###

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

a.sort()

print(sum(a[::-2]) - sum(a[-2::-2]))
n,c,k = map(int,input().split())
t = [int(input()) for i in range(n)]
t.sorted()

pas = 1
last_bus = t[0] + k
ans = 1

for i in t[1:]:
  if i <= last_bus and pas < c:
    pas +=1
  else:
    ans +=1
    pas =1
    last_bus = i + k
    
    
print(ans)
  
  


### FIXED CODE ###

n,c,k = map(int,input().split())
t = [int(input()) for i in range(n)]
t.sort()

pas = 1
last_bus = t[0] + k
ans = 1

for i in t[1:]:
  if i <= last_bus and pas < c:
    pas +=1
  else:
    ans +=1
    pas =1
    last_bus = i + k
    
    
print(ans)
n = int(input())
l = list(int(input()) for i in range(n))
a = -(-n//min(l))+4
print(a)

### FIXED CODE ###

n = int(input())
l = list(int(input()) for i in range(5))
a = -(-n//min(l))+4
print(a)
a = input()
 
if True == a.isupper():
  Print("A")
else :
  print("a")

### FIXED CODE ###

a = input()
 
if True == a.isupper():
  print("A")
else :
  print("a")
N,A,B=map(int,input().split())
if N==1:
    if A==B:
        ans=1
    else:
        ans=0
elif:
    if A>B:
        ans=0
    else:
        ans=(B-A)*(N-2)+1
print(ans)

### FIXED CODE ###

N,A,B=map(int,input().split())
if N==1:
    if A==B:
        ans=1
    else:
        ans=0
else:
    if A>B:
        ans=0
    else:
        ans=(B-A)*(N-2)+1
print(ans)
h,w,d=[int(i) for i in input().split()]
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a0 =[int(i0) for i0 in input().split()]
  a.append(a0)
  for j in range(w):
    p[a0[j]]=[i,j]

n=int(input())

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

@lru_cache(maxsize=None)
def dist_d(s,g,d):
  if s==g:
    return 0
  else:
    y0,x0=p[s]
    s = a[y0][x0]+d
    y,x = p[s]
    return abs(x-x0)+abs(y-y0) + dist_d(s,g,d)
  
for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
 
  print(dist_d(s,g,d))


### FIXED CODE ###

I=lambda:map(int,input().split())
h,w,d=I()
H={}
W={}
for i in range(1,h+1):
  for j,k in enumerate(I(),1):
    H[k],W[k]=i,j
x=1+h*w
s=[0 for _ in range(x)]
for i in range(d+1,x):
  s[i]=s[i-d]+abs(H[i]-H[i-d])+abs(W[i]-W[i-d])

for _ in range(int(input())):
  a,b=I()
  print(s[b]-s[a])
N,M=map(int,input().split())

flag=list(range(N))
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p

for i in range(M):
    x,y,z = map(int,input().split())
    x,y = map(takeflag,(x,y))
    x,y = min(x,y),max(x,y)
    flag[x]=y

st=set()
for i in range(N):
    st.add(takeflag(i))

print(len(st))

### FIXED CODE ###

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

flag=list(range(N))
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p

for i in range(M):
    x,y,z = map(int,input().split())
    x,y=x-1,y-1
    x,y = map(takeflag,(x,y))
    x,y = min(x,y),max(x,y)
    flag[x]=y

st=set()
for i in range(N):
    st.add(takeflag(i))

print(len(st))
n = int(input())
s = input()

if n % 2 == 1:
    print("No")
else:
    s_1 = s[:n/2]
    s_2 = s[n/2:n]
    if s_1 != s_2:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

a = int(input())
print(a**2)
from itertools import combinations
import numpy as np
n,m,x = map(int,input().split())
a_list = []
price_list = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    price_list.append(tmp.pop(0))
    a_list.append(tmp)
    
all_list = [x for x in range(len(a_list))]
prices = []
for i in range(1,len(a_list)+1):
    for y in combinations(all_list,i):
        tmp = np.zeros(3)
        price = 0
        for ch in y:
            tmp += np.array(a_list[ch])
            price += price_list[ch]
        if np.all(tmp>=x):
            prices.append(price)
if prices != []:
    print(min(prices))
else:
    print(-1)

### FIXED CODE ###

from itertools import combinations
import numpy as np
n,m,x = map(int,input().split())
a_list = []
price_list = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    price_list.append(tmp.pop(0))
    a_list.append(tmp)
    
all_list = [x for x in range(len(a_list))]
prices = []
for i in range(1,len(a_list)+1):
    for y in combinations(all_list,i):
        tmp = np.zeros(m)
        price = 0
        for ch in y:
            tmp += np.array(a_list[ch])
            price += price_list[ch]
        if np.all(tmp>=x):
            prices.append(price)
if prices != []:
    print(min(prices))
else:
    print(-1)
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import ceil
def main():
    a, b, c, d, e, f = map(int, input().split())
    a *= 100
    b *= 100

    # 濃度0%のケース
    if e == 0 or min(a, b) == f:
        print(a, 0)
        sys.exit()
    water = [0] * 6001
    water[0] = True
    for i1 in range(3001):
        if water[i1]:
            water[i1 + a] = True
            water[i1 + b] = True
    sugar = [0] * 6001
    sugar[0] = True
    for i1 in range(3001):
        if sugar[i1]:
            sugar[i1 + c] = True
            sugar[i1 + d] = True

    noudo = 0
    r1 = 0
    r2 = 0
    for i1 in range(1, f + 1):
        if water[i1]:
            for i2 in range(f + 1):
                if i1 + i2 > f:
                    break
                if sugar[i2]:
                    if i1 * e >= i2 * 100:
                   

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    a, b, c, d, e, f = map(int, input().split())
    a *= 100
    b *= 100

    # 濃度0%のケース
    if e == 0 or min(a, b) == f:
        print(a, 0)
        sys.exit()

    water = [0] * 6001
    water[0] = True
    for i1 in range(3001):
        if water[i1]:
            water[i1 + a] = True
            water[i1 + b] = True
    sugar = [0] * 6001
    sugar[0] = True
    for i1 in range(3001):
        if sugar[i1]:
            sugar[i1 + c] = True
            sugar[i1 + d] = True

    noudo = 0
    r1 = 0
    r2 = 0
    for i1 in range(1, f + 1):
        if water[i1]:
            for i2 in range(f + 1):
                if i1 + i2 > f:
                    break
                if sugar[i2]:
                    if i1 * e >= i2 * 100:
                        if noudo < i2 / (i1 + i2):
                            noudo = i2 / (i1 + i2)
                            r1 = int(i1 + i2)
                            r2 = int(i2)
                    else:
                        break
    if noudo == 0:
        print(a, 0)
    else:
        print(r1, r2)

if __name__ == '__main__':
    main()
N=int(input())
K=int(input())

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

### FIXED CODE ###

N=input()
K=int(input())

dpsm=[[0]*(K+1) for _ in range(len(N))] #dpsm[i][k]
dp=[[0]*(K+1) for _ in range(len(N))]

dpsm[0][0]=1
dpsm[0][1]=int(N[0])-1
dp[0][1]=1

for i in range(1,len(N)):
    for k in range(K-1,-1,-1):
        dpsm[i][k+1]+=dpsm[i-1][k]*9

    
    if N[i]=="0":
        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dp[i][k]+=dp[i-1][k]
    else:
        for k in range(K-1,-1,-1):
            dpsm[i][k+1]+=dp[i-1][k]*(int(N[i])-1)
            dp[i][k+1]+=dp[i-1][k]

        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dpsm[i][k]+=dp[i-1][k]
          
print(dp[-1][-1]+dpsm[-1][-1])
# -*- coding: utf-8 -*-
a,b = map(str,input().split())
H1 = "1"
D1= "-1"
H = int(H1)
D = int(D1)
A = int(a)
B = int(b)
if B * A == 1:
  print("H")
else:
  print("D")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b = map(str,input().split())
if (a == "H" and b == "H")or(a =="D" and b == "D"):
  print("H")
else:
  print("D")
n,m=map(int,input().split())
edges=[[]for i in range(n)]
visited=[False]*n
cnt=0
def dfs(u,cnt,visited):
  visited=visited[:]
  cnt=cnt
  visited[u]=True
  if visited[-1]==True:
    return cnt,visited
  cnt+=1
  for v in edges[u]:
    if visited[v]==False:
      dfs(v,cnt,visited)
  return cnt,visited

for i in range(m):
  a,b=map(int,input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)

cnt,visited=dfs(0)
if visited[-1]==True and cnt==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

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


for i in range(m):
  a,b=map(int,input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)

for v in edges[-1]:
  if 0 in edges[v]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // 移動方向


int n;
int h[101];

void input(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> h[i];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    int cnt = 0;
    for(int l=0;l<n;l++){
        while(h[l] > 0){
            int r;
            for(r=l+1;r<n;r++){
                if (h[r] == 0) break; 
            }
            for(int x=l;x<r;x++) h[x]--;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

### FIXED CODE ###

import sys
input = sys.stdin.readline

def lsearch(h): # 左端を探す
    for i in range(len(h)):
        if h[i] != 0:
            return i
    return len(h)-1

def rsearch(h, l): # 右端を探す
    for i in range(l, len(h)):
        if h[i] == 0:
            return i
    return len(h)

n=int(input())
h=list(map(int, input().split()))
cnt=0
while any(h):
    l=lsearch(h)
    r=rsearch(h, l)
    for i in range(l, r):
        h[i] -= 1
    cnt+=1
print(cnt)
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0
        
        if sign>ans: ans=sign
        sign=0

    print(ans)
        

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    ans=["Sunny","Cloudy","Rainy"]
    print(ans[(ans.index(input())+1)%3])
if __name__ == '__main__':
    main()
N,M=map(int,input().split())
mod=10**9+7

from math import factorial
from collections import Counter

def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)

def product(a):
    pro=1
    for b in a:
        pro=pro*b%mod
    return pro

#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod

def dp(cur,init,seq,lest,num):
    if cur==N:
        if lest==0:
            cnt=sorted(list(Counter(seq).values()),reverse=True)
            #print(cnt)
            bunbo=product(map(factorial,cnt[1:]))%mod
            memo[num]=(memo[num]+nPr(sum(cnt),sum(cnt[1:]),mod)//bunbo)%mod #ここがおかしい
    elif lest==0:
        dp(N,init,seq+[0]*(N-cur),0,num)
    else:
        for i in range(0,lest+1):
            if cur==0:
                dp(cur+1,init,seq+[i],lest-i,num)
            elif i<=seq[-1]:
                dp(cur+1,init,seq+[i],lest-i,num)

p=list(Counter(soinsuu(M)).values())
memo=[0]*len(p)

for i in range(len(p)):
    dp(0,p[i],[],p[i],i)
#print(memo)
print(product(memo))
#print(p)

### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
 
from math import factorial
from collections import Counter
 
def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)
 
def product(a):
    pro=1
    for b in a:
        pro=pro*b%mod
    return pro
 
#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod
    
nPr_list=[nPr(N,i) for i in range(30)]
bunbo_list=dict()

def dp(cur,init,seq,lest,num):
    #print(cur,init,seq,lest,num)
    if cur==N:
        if lest==0:
            cnt=sorted(list(Counter(seq).values())+[N-len(seq)],reverse=True)
            bunbo=product(map(factorial,cnt[1:]))
            if bunbo not in bunbo_list.keys():
                bunbo_list[bunbo]=inv_n(bunbo)
            memo[num]=(memo[num]+nPr_list[N-cnt[0]]*bunbo_list[bunbo])%mod
    elif lest==0:
        dp(N,init,seq,0,num)
    else:
        if cur==0:
            for i in range(1,lest+1):
                dp(cur+1,init,seq+[i],lest-i,num)
        else:
            for i in range(1,min(lest,seq[-1])+1):
                dp(cur+1,init,seq+[i],lest-i,num)
 
p=list(Counter(soinsuu(M)).values())
memo=[0]*len(p)


for i in range(len(p)):
    dp(0,p[i],[],p[i],i)
print(product(memo))
n = int(input())
a = [int(i) for i in input().split()]
s = sum(a)
ans = 0 
for i in range(n-1):
	s-=a[i]
	ans+=s*a[i]
print(ans%(10**9+7))

### FIXED CODE ###

D,T,S = map(int,input().split())
if D/S<=T:
	print("Yes")
else:
	print("No")
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def 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 pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

from math import factorial
def c(n, r):
    a = factorial(n) / factorial(r) / factorial(n - r)
    return a

result = 0
counts = collections.Counter(s)
red = [i for i in counts.values() if i != 1]
tmp = 1
for i in red:
    tmp *= i
#  print('tmp', tmp)
chars = list(set(s))
for i in range(1, len(s)+1):
    #  print(i)
    #  import pdb
    #  pdb.set_trace()
    #  combis = list(itertools.combinations(chars, i))
    #  combis = list(itertools.combinations(counts, i))
    #  print('combis' ,combis)
    result += c(len(s), i)
    #  for combi in combis:
    #      #  print('combi', combi)
    #      tmp = 1
    #      for c in combi:
    #          #  print('c', c)
    #          tmp *= counts[c]
    #      #  print('tmp', tmp)
    #      result += tmp
for i in range(1, tmp):
    result -= c(tmp, i)
print(int(result))


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def 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 pf(s): return print(s, flush=True)


N = I()
s = S()

inf = 10**9+7

counts = collections.Counter(s)
result = 1
for i in counts.values():
    result *= i+1
result -= 1
print(result%inf)
exit()
import sys

N = input()


N = N.split(',')

AC_num = 0
WA_num = 0
TLE_num = 0
RE_num = 0


N_num = int(N[0])

if N_num < 1 or N_num > 100000:
    print('error')
    sys.exit()


for i in range(N_num):
    print(i+1)
    
    if 'AC' == N[i+1]:
        AC_num += 1
        #print(AC_num)
    
    elif 'WA' == N[i+1]:
        WA_num += 1
        #print(WA_num)

    elif 'TLE' == N[i+1]:
        TLE_num += 1
        #print(TLE_num)
    
    elif 'RE' == N[i+1]:
        RE_num += 1
        #print(RE_num)
        
    else:
        print('nun')

print('AC','x',AC_num)
print('WA','x',WA_num)
print('TLE','x',TLE_num)
print('RE','x',RE_num)

### FIXED CODE ###

N_num = int(input())

N = []

for i in range(N_num):
    N.append(input())
    

AC_num = 0
WA_num = 0
TLE_num = 0
RE_num = 0

for i in range(N_num):
    #print(i+1)
    
    if 'AC' == N[i]:
        AC_num += 1
        #print(AC_num)
    
    elif 'WA' == N[i]:
        WA_num += 1
        #print(WA_num)

    elif 'TLE' == N[i]:
        TLE_num += 1
        #print(TLE_num)
    
    elif 'RE' == N[i]:
        RE_num += 1
        #print(RE_num)


print('AC x {}'.format(AC_num))
print('WA x {}'.format(WA_num))
print('TLE x {}'.format(TLE_num))
print('RE x {}'.format(RE_num))
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 = 100
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) 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) 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()
x,y=map(int,input().split())
print("=" if x==y else ">" if x>y else "<")

### FIXED CODE ###

x,y=input().split()
print("=" if x==y else ">" if x>y else "<")
import itertools import product
a=list(map(str,input().split()))

for b in product(["+","-"],repeat=3):
  if(eval(a[0]+b[0]+a[1]+b[1]+a[2]+b[2]+a[3])==7):
    print(str(a[0]+b[0]+a[1]+b[1]+a[2]+b[2]+a[3]=7))
    break:
      

### FIXED CODE ###

from itertools import product
a=list(input())

for b in product(["+","-"],repeat=3):
  if(eval(a[0]+b[0]+a[1]+b[1]+a[2]+b[2]+a[3])==7):
    print(str(a[0]+b[0]+a[1]+b[1]+a[2]+b[2]+a[3]+"=7"))
    break
a,b,c = input().split()

i=0
if a==1:
    i++
if b==1:
    i++
if c==1:
    i++
print(i)


### FIXED CODE ###

count=0
str = list(input())

for x in str:
  if x=="1":
    count=count+1

print(count)
int N = input()
int S = input()
print(S.count("ABC"))

### FIXED CODE ###

N = input()
S = input()
print(S.count("ABC"))
n = int(input())
data = [input().split() for i in range(n)]
light = [0]*n
light[0] = 1
count = 1
bool = False
temp = int(data[0][0])
for i in range(n):
    temp = int(data[temp - 1][0])
    count += 1
    if temp == 2:
        print(count)
        exit()
print(-1)

### FIXED CODE ###

x,a,b = map(int,input().split())
if b <= a:
    print('delicious')
elif b - a <= x:
    print('safe')
else:
    print('dangerous')
s_input =   input().split()
if(s_input[1] == '+'):
    print(int(s_input[0]+int(s_input[2])))
else:
    print(int(s_input[0]-int(s_input[2])))

### FIXED CODE ###

s_input =   input().split()
if(s_input[1] == '+'):
    print(int(s_input[0])+int(s_input[2]))
else:
    print(int(s_input[0])-int(s_input[2]))
T=input()

res = ""
for i in len(T) :
    if (T[i] != "?") :
        res += T[i]
        continue

    if (i != 0) :
        if (T[i-1] == "P") :
            res += "D"
        else :
            res += "D"

print(res)


### FIXED CODE ###

T=input()

res = ""
for i in range(len(T)) :
    if (T[i] != "?") :
        res += T[i]
        continue
    res += "D"

    # if (i != 0) :
    #     if (T[i-1] == "P") :
    #         res += "D"
    #     else :
    #         res += "D"

print(res)