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

X = input()

while 'ST' in X:
	X = X.replace('ST','')

print(len(X))

### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

S = input()
ans = 0
tmp = 0
for s in S:
	if s == 'S':
		tmp += 1
	elif s == 'T':
		tmp -= 1
		if tmp < 0:
			tmp = 0
			ans += 1

print(ans+tmp)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
def solve():
    N, K = map(int,input().split())
    MOD = 10 ** 9 + 7
    ans = []
    for i in range(1,K+1):
        com1 = COM(K-1,i-1,MOD)
        if N-K-(i-1) < 0:
            ans.append(0)
            continue
        com2 = COM(N-K+1,N-K-(i-1),MOD)
        ans.append(com1*com2%MOD)
    
    print(*ans,sep='\n')

def COM(n,r,MOD):
    return calcNumerator(n,r,MOD) // calcDenominator(r,MOD)

def calcNumerator(n,r,MOD):
    if r == 0:
        return 1
    return n % MOD * calcNumerator(n-1,r-1,MOD)

def calcDenominator(r,MOD):
    if r == 0:
        return 1
    return r % MOD * calcDenominator(r-1,MOD)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N, K = map(int,input().split())
    MOD = 10 ** 9 + 7
    fac, finv, inv = COMinit(N+1,MOD)
    ans = []
    for i in range(1,K+1):
        com1 = COM(K-1,i-1,MOD,fac,finv,inv)
        if N-K-(i-1) < 0:
            ans.append(0)
            continue
        com2 = COM(N-K+1,N-K-(i-1),MOD,fac,finv,inv)
        ans.append(com1*com2%MOD)
    
    print(*ans,sep='\n')

# COMの前処理
# テーブルを作る
# O(n)
def COMinit(N, mod):
    fac = [0] * N
    finv = [0] * N
    inv = [0] * N

    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

    for i in range(2, N):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    
    return fac, finv, inv

# nCrを計算 前処理としてCOMinitの実行が必要
# O(1)
def COM(n, r, mod, fac, finv, inv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

redpoints = p[:x]
greenpoints = q[:y]
points = redpoints + greenpoints
flag=True
while(flag):
    rep = min(points)
    if len(r) < 1:
        flag = False
    elif rep < r[0]:
        points[points.index(rep)] = r.pop(0)
    else:
        flag = False
print(sum(points))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

sortp = sorted(p)[::-1]
sortq = sorted(q)[::-1]
redpoints = sortp[:x]
greenpoints = sortq[:y]
sortedpoints = sorted(redpoints+greenpoints+r)[::-1]
print(sum(sortedpoints[:x+y]))
### BUGGY CODE ###

def dist(list):
  d=abs(list[0])+abs(list[-1])
  for i in range(len(list)-1):
    d+=abs(list[i+1]-list[i])
  return(d)
n=int(input())
A=[int(i) for i in input().split()]
for i in range(n):
  print(dist(A[:i]+A[i+1:]))

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
A.append(0)
D=[abs(A[0])]
for i in range(n-1):
  D+=[abs(A[i]-A[i+1])]
D.append(abs(A[n-1]))
d=sum(D)
for i in range(n):
  print(d+abs(A[i-1]-A[i+1])-D[i]-D[i+1])
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n = int(input())
    s = tuple(input())

    unique_num = [0] * n
    for i1 in range(n):
        unique_num[i1] = len(set(s[i1:]))
    d1 = defaultdict(int)
    for keta1 in range(n - 2):
        for keta2 in range(keta1 + 1, n - 1):
            d1[(s[keta1], s[keta2])] = max(d1[(s[keta1], s[keta2])], unique_num[keta2 + 1])
    r = sum(d1.values())
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#from collections import defaultdict
def main():
    n = int(input())
    s = tuple(map(int, tuple(input())))
    num_pos = [] # 各数字がｓ中に最後にあらわれる位置。
    for num in range(10):
        if num in s:
            num_pos.append(n - s[::-1].index(num) - 1)
    unique_num = [0] * n # ｓの各桁でその桁以降にある数字の種類。
    for i1 in range(n):
        unique_num[i1] = sum([np >= i1 for np in num_pos])
    unique_num.append(0)
    r = 0
    for keta1 in range(10):
        if keta1 in s:
            keta1_pos = s.index(keta1)
            for keta2 in range(10):
                if keta2 in s[keta1_pos + 1:]:
                    keta2_pos = s[keta1_pos + 1:].index(keta2) + keta1_pos + 1
                    r += unique_num[keta2_pos + 1]
    print(r)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = list()
for i in A:
    for j in B:
        AB.append(i+j)

AB.sort(reverse=True)
ABC = list()

for i in AB[:K]:
    for j in C:
        ABC.append(i+j)

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

ans = list()
for i in range(X):
    for j in range(Y):
        if (i+1)*(j+1) > K:
            break
        else:
            for k in range(Z):
                if (i+1)*(j+1)*(k+1) > K:
                    break
                else:
                    ans.append(A[i]+B[j]+C[k])

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

a,b,k = map(int,input().split())
for _ in range(k):
    if a >0:
        a -=1
    elif a ==0 and b > 0:
        b -=1
print (a,b)
    

### FIXED CODE ###

a,b,k = map(int,input().split())
A = max(a-k,0)
B = max(b-max(k-a,0),0)
print(A,B)
### BUGGY CODE ###

N ,K = map(int,input().split())
P = list(map(int,input().split()))
ex = []
ans = 0
for i in range(N-K+1):
    for j in range(K):
        ans += (P[i+j]+1)/2
    ex.append(ans)
    ans = 0
print(max(ex))

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
for i in range(N):
  P[i]=(P[i]+1)/2
point=sum(P[:K])
tmp=point
for i in range(N-K):
  tmp=tmp-P[i]+P[i+K]
  if tmp>point:point=tmp
  
print(point)
### BUGGY CODE ###

from collections import deque
MAX_VAL = 10 ** 9
H, W = map(int, input().split())



border_row = "#"*(W+2)
field = [border_row]
num_blacks = 0
for i in range(H):
    line = input()
    for c in line:
        if c == "#":
            num_blacks += 1
    field.append("#"+line+"#")
field.append(border_row)

cost = [[MAX_VAL]*(W+2) for _ in range(H+2)]

if field[1][1] == ".":
    cost[1][1] = 1
else:
    cost[1][1] = MAX_VAL

visited = [[False]*(W+2) for _ in range(H+2)] 
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((1, 1))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if field[ny][nx] == ".":
                cost[ny][nx] = min(cost[ny][nx], cost[y][x]+1)
                if not visited[ny][nx]:
                    q.append((nx, ny))
        visited[y][x] = True

bfs()
print(H*W-num_blacks-cost[H][W]) if cost[H][W] < MAX_VAL else print(-1)




### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append(line)

cost = [[-1]*(W) for _ in range(H)]

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append((start,0))
dist[start] = 0

while dq:
    p,d = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    if d>dist[p]:
        continue
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dist[q] = dist[p]
                        dq.appendleft((q,dist[q]))
                else:
                    if dist[q]>dist[p]+1:
                        dist[q] = dist[p] + 1
                        dq.append((q,dist[q]))

print(-1 if dist[goal]==10**10 else dist[goal])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])
### BUGGY CODE ###

N = int(input())


def lc():
    l0, l1 = 2, 1
    while 1:
        yield l0 + l1
        l0, l1 = l1, l0 + l1


for i, n in enumerate(lc()):
    if i == N - 2:
        print(n)
        break


### FIXED CODE ###

N = int(input())


def lc():
    l0, l1 = 2, 1
    while 1:
        yield l0 + l1
        l0, l1 = l1, l0 + l1


if N > 1:
    for i, n in enumerate(lc()):
        if i == N - 2:
            print(n)
            break
else:
    print(1)
### BUGGY CODE ###

import math
n = int(input())

den = int(1e9 + 7)
c = lambda a, b: (math.factorial(a) // (math.factorial(a - b) * math.factorial(b)))
ans = 0
if n == 1:
    ans = 0
elif n == 2:
    ans = 2
else:
    for i in range(2, n + 1):   # number of 0|9
        ans = (ans + (8 ** (n - i) * (2 ** i - 2) * c(n, i))) % den
print(ans)

### FIXED CODE ###

n = int(input())

den = int(1e9 + 7)
print((10**n - 2 * 9**n + 8**n) % den)
### BUGGY CODE ###

def main():
    import bisect
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(py)] * 2):
        bisect.insort_left(d[i], j)

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = bisect.bisect_right(d[i], j)
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import bisect
    n, m, *py = map(int, open(0).read().split())
    d = [[] for _ in range(n + 1)]
    for i, j in zip(*[iter(py)] * 2):
        d[i].append(j)

    for i in d:
        i.sort()

    ans = ''
    for i, j in zip(*[iter(py)] * 2):
        k = bisect.bisect_right(d[i], j)
        id = str(i).zfill(6) + str(k).zfill(6)
        ans += id + '\n'

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys

def input():
    return sys.stdin.readline().rstrip()

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
price = [a[i][0] for i in range(N)]
min_num = 0
min_place = 0
bought = 0
total_price = 0

for i in range(N):
    min_num = min(price)
    min_place = price.index(min_num)
    if bought + a[min_place][1] <= M:
        total_price += a[min_place][0] * a[min_place][1]
        bought += a[min_place][1]
    else:
        total_price += (M - bought) * a[min_place][0]
        break
    a.pop(min_place)
    price.pop(min_place)
print(total_price)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys

def input():
    return sys.stdin.readline().rstrip()

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
price = [a[i][0] for i in range(N)]
stock = [a[i][1] for i in range(N)]
bought = 0
total_price = 0

for i in range(N):
    if bought + stock[i] <= M:
        total_price += price[i] * stock[i]
        bought += stock[i]
    else:
        total_price += price[i] * (M - bought)
        break
print(total_price)
### BUGGY CODE ###

s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = 10**9+7

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1

for i in range(1, len(s) - 1):
    if s[i]=='B' or s[i]=='?':
        a1 = 3*z[i][0]+z[i][1]
        a2 = 3**(z[i][1]-1)%t
        c1 = 3*z[i][2]+z[i][3]
        c2 = 3**(z[i][3]-1)%t
        ans += (a1*a2*c1*c2)%t
    ans %=t

print(int(ans))

### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
T = [1] * (N)
for i in range(N):
  for j in range(N):
    if i != j and A[j] % A[i] == 0:
      T[j] = 0
print(sum(T))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = max(A)
num = [0] * (M)
T = [0] * (M)
for a in A:
  num[a-1] += 1
  T[a-1] = 1
for i in range(M):
  if num[i] != 0 and T[i] == 1:
    n = 2 * (i + 1)
    while n <= M:
      T[n-1] = 0
      n += (i + 1)
ans = 0
for i in range(M):
  if T[i] == 1 and num[i] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[]] + A

cnt = 0
ok = True

for _ in range(N * (N - 1) // 2):
    match = []
    fin = True
    for i in range(1, N + 1):
        if not A[i]:
            continue

        fin = False
        l = A[i][-1]
        r = A[l][-1]

        if r == i:
            match.append(l)

    if fin:
        break

    if not match:
        ok = False
        break

    for i in match:
        A[i].pop()

    cnt += 1


if ok:
    print(cnt)
else:
    print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[-1]] + A


def check(a, q=[]):
    if not A[a]:
        return False

    b = A[a][-1]
    b_op = A[b][-1]

    ok = False
    if a == b_op:
        ok = True

        if b < a:
            a, b = b, a
        q.append((a, b))

    return ok


q = []
for i in range(1, N + 1):
    check(i, q)

q = list(set(q))

day = 0
while q:
    nq = []
    for a, b in q:
        A[a].pop()
        A[b].pop()
        check(a, nq)
        check(b, nq)

    day += 1
    q = list(set(nq))

for i in range(1, N + 1):
    if len(A[i]) != 0:
        print(-1)
        exit()

print(day)
exit()
### BUGGY CODE ###

def low_left(ls,key):
    left,right = -1,len(ls)
    while right - left > 1:
        mid = (right+left)//2
        if ls[mid] >= key:
            right = mid
        else:
            left = mid
    return len(ls[:(left+1)])


def high_right(ls,key):
    left,right = -1,len(ls)
    while right - left > 1:
        mid = (right+left)//2
        if ls[mid]<=key:
            left = mid
        else:
            right = mid
    return len(ls[right:])


def test():
    n = int(input())
    A,B,C = [list(sorted(map(int,input().split()))) for i in range(3)]
    ans = 0

    for b in B:
        ans += high_right(C,b)*low_left(A,b)
    print(ans)


if __name__ == "__main__":
    test()


### FIXED CODE ###

def test():
    n = int(input())
    A,B,C = [list(sorted(map(int,input().split()))) for i in range(3)]
    ans = 0

    for b in B:
        ans += low_left(A,b) * (n-high_right(C,b))
    print(ans) 


def low_left(ls,t):
    low,high = 0,len(ls)
    while low<high:
        mid = (low+high)//2
        if ls[mid] < t:
            low = mid + 1
        else:
            high = mid
    return low


def high_right(ls,t):
    low,high = 0,len(ls)
    while low<high:
        mid = (low+high)//2
        if ls[mid] > t:
            high = mid
        else:
            low = mid + 1
    return low


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

import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
cost = []
res = []
tree = []
level = []
childs = []
parent = []
cache = []
for i in range(210000):
    res.append(0)
    tree.append([])
    level.append(-1)
    childs.append([])
    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)

def make_level(index, lev, pp):
    l = 0
    level[index] = lev
    parent[index] = pp
    for next in tree[index]:
        #print("index {0} search {1}".format(index, next))
        # 逆走はしない
        if level[next] != -1:
            #print("CANNOT MOVE to {0}".format(next))
            continue
        # 子供に親を設定
        parent[next] = index
        curparent = index
        make_level(next, lev + 1, index)

make_level(1, 0, -1)

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

#print("parent")
#print(parent[0:10])

def calc_cost(index):
    if index == -1:
        return 0
    #print("index = {0}, parent = {1}".format(index, parent[index]))
    if cache[parent[index]] != -1:
        #print(" parent has cache: {0}".format(cache[parent[index]]))
        cache[index] = cost[index] + cache[parent[index]]
        #print(" RET index = {0}, COST = {1}".format(index, cost[index] + cache[parent[index]]))
        return cost[index] + cache[parent[index]]
    else:
        cc = calc_cost(parent[index])
        #print(" parent hasNOT cache: {0}".format(cc))
        cache[index] = cost[index] + cc
        #print(" RET index = {0}, COST = {1}".format(index,cost[index] + cc))
        return cost[index] + cc



for i in range(1, n+1):
    #print("llll:{0}".format(i))
    res[i] = calc_cost(i)

res = list(map(str, res))
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 ###

n, m = map(int, input().split())
id = set(i for i in range(1, n + 1))
for i in range(m):
    l, r = map(int, input().split())
    check = set(i for i in range(l, r + 1))
    id = id & check
print(len(id))

### FIXED CODE ###

n, m = map(int, input().split())
id = set(i for i in range(1, n + 1))
L = []
R = []
for i in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
print( min(R) - max(L) + 1 if min(R) - max(L) + 1 > 0 else 0)
### BUGGY CODE ###

from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

def power(x, y):
  if y == 0:
    return 1
  elif y == 1:
    return x % MOD
  elif y % 2 == 0:
    return power(x, y // 2) ** 2 % MOD
  else:
    return mul(power(x, y // 2) ** 2, x)

def div(a, b):
  return mul(a, power(b, MOD - 2))

numer_cache = defaultdict(dict)
denom_inv_cache = {}

def numer(n, r):
  if r == 0:
    return 1
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer(n, r - 1), n - r + 1)
  return numer_cache_n[r]

def denom_inv(r):
  if r == 0:
    return 1
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv(r - 1), r)
  return denom_inv_cache[r]

def combinations_count(n, r):
  r = min(r, n - r)
  return mul(numer(n, r), denom_inv(r))

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)


### FIXED CODE ###

from collections import defaultdict
from functools import reduce

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

MOD = 10 ** 9 + 7

def mul(a, b):
  return a * b % MOD

def power(x, y):
  res = 1
  while True:
    if y & 1:
      res = res * x % MOD
    if y == 1:
      return res
    x = x * x % MOD
    y >>= 1

def div(a, b):
  return a * power(b, MOD - 2) % MOD

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_inv_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer_cache_n[r - 1], n - r + 1)
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv_cache[r - 1], r)
  return mul(numer_cache_n[r], denom_inv_cache[r])

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)