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

n = (int)(input())
s = []
t = []
for _ in range(n):
    a, b = (list)(map(int, input().split()))
    s.append(a)
    t.append(b)
mi = min(s)
ma = max(t)


def isPrime(n):
    if n == 0 or n == 1:
        return False
    for i in range(2, n):  # 第二引数は sqrt(num)+1 でも良い
        if n % i == 0:
            return False

    return True


def prime(s, t):
    l = [0]*(t+1)
    c = 0
    s = 0
    for i in range(s, t+1):
        if isPrime(i) and isPrime((i+1)//2):
            c += 1
        l[i] = c
    return l


primes = prime(mi, ma)
for i in range(n):
    print(primes[t[i]] - primes[s[i]-1])


### FIXED CODE ###

from itertools import accumulate

N = 100000
prime = [True]*(N+1)

prime[0] = prime[1] = False

for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False

prime2 = [0] * (N+1)

for i in range(N+1):
    if prime[i] and prime[(i+1)//2]:
        prime2[i] = 1

acc = list(accumulate(prime2))

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(acc[r]-acc[l-1])
### BUGGY CODE ###

n, m = map(int, input().split())
P = [input().split() for i in range(m)]
P = sum(P,[])
ac_list = []
wa_list = [0] * n

counta = 0
countb = 0
for i in range(1, m * 2, 2):
    if P[i] == "AC" and int(P[i - 1]) not in ac_list:
        counta += 1
        ac_list.append(int(P[i - 1]))
        countb += wa_list[int(P[i - 1]) - 1]
    elif P[i] == "WA":
        wa_list[int(P[i - 1]) - 1] += 1
    else:
        continue

print(counta, countb)

### FIXED CODE ###

import itertools
n, m = map(int, input().split())
P = [input().split() for i in range(m)]
P = list(itertools.chain.from_iterable(P))
ac_list = [0] * n
wa_list = [0] * n
counta = 0
countb = 0
for i in range(1, m * 2, 2):
    if P[i] == "AC" and ac_list[int(P[i - 1])-1] == 0:
        counta += 1
        ac_list[int(P[i - 1])-1] = 1
        countb += wa_list[int(P[i - 1]) - 1]
    elif P[i] == "WA":
        wa_list[int(P[i - 1]) - 1] += 1
    else:
        continue

print(counta, countb)
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        q = deque([])
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            q.append(j)
            score += C[j]
            cnt += 1
            j = P[j]
        for j in q:
            f_cnt[j] = cnt
            f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur] - 1)
            cnt = cnt % f_cnt[cur] + f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans = max(ans, f(i, K))
    
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    P = [int(x)-1 for x in input().strip().split()]
    C = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    f_cnt = [0] * N
    f_score = [0] * N
    for i in range(N):
        if f_cnt[i]:
            continue
        flag = [False] * N
        j = i
        cnt = 0
        score = 0
        while not flag[j]:
            flag[j] = True
            score += C[j]
            cnt += 1
            j = P[j]
        for j in range(N):
            if flag[j]:
                f_cnt[j] = cnt
                f_score[j] = score
    # print(*f_cnt)
    # print(*f_score)

    def f(cur, cnt):
        ret = -float('inf')
        ret_ = 0
        if f_score[cur] >= 0:
            ret_ += f_score[cur] * (cnt // f_cnt[cur] - 1)
            cnt = cnt % f_cnt[cur] + f_cnt[cur]
            ret = ret_
        else:
            cnt = min(cnt, f_cnt[cur])

        while cnt:
            # print('  cur = {}, cnt = {}, ret = {}'.format(cur, cnt, ret_))
            cur = P[cur]
            ret_ += C[cur]
            ret = max(ret, ret_)
            cnt -= 1

        return ret

    for i in range(N):
        # print('i = {}'.format(i))
        ans = max(ans, f(i, K))
    
    print(ans)

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

N=int(input())

def lucas(N):
  if N==0:
    return 2
  elif N==1:
    return 1
  else:
    return lucas(N-2)+lucas(N-1)
  
print(lucas(N))

### FIXED CODE ###

N=int(input())
L=[]

for i in range(N+1):
  if i==0:
    L.append(2)
  elif i==1:
    L.append(1)
  else:
    L.append(L[-2]+L[-1])

print(L[-1])
### BUGGY CODE ###

n,t,a,*u=map(int,open(0).read().split())
for u,b in zip(u[::2],u[1::2]):
    while t*b!=a*u:
        if t*b<a*u:t+=1
        else:a+=1
print(t+a)

### FIXED CODE ###

n,t,a,*u=map(int,open(0).read().split())
for u,b in zip(u[::2],u[1::2]):
    x=0-min(-t//u,-a//b)
    t,a=u*x,b*x
print(t+a)
### BUGGY CODE ###

#!/usr/bin/env python
n = int(input())
s = input()
ans = float('inf')
for i in range(n):
    if i==0:
        cnt = s[1:].count('E')
    elif i==n-1:
        cnt = s[:n-2].count('W')
    else:
        cnt = s[i+1:].count('E') + s[:i-1].count('W')
    ans = min(ans, cnt)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python
n = int(input())
s = input()
ans = float('inf')
E_total = s.count('E')
W_total = s.count('W')
cnt = {'E': 0, 'W': 0}
for i in range(n):
    turn = cnt['W'] + (E_total - cnt['E'])
    if s[i] == 'E':
        turn -= 1
    ans = min(ans, turn)
    cnt[s[i]] += 1
print(ans)
### BUGGY CODE ###

import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
aa=m/gg
bb=n/gg
ab=(m/gg)*(n/gg)
result = ll
for i in xrange(ll) :
    if not (i % ab):
            tmp1=i/aa
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
print result

### FIXED CODE ###

import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n/gg*m
result = ll
for i in xrange(n):
    if not (i*m) % n :
            tmp=i*m/n
            if s[i] != t[tmp] :
                result= -1
print result
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    A, B, N = [int(i) for i in input().strip().split()]
    ans = 0
    if N >= B:
        for n in range(B-1, N+1, B):
            ans = max(ans, ((A * n) // B) - (A * (n // B)))
    else:
        ans = ((A * N) // B) - (A * (N // B))
    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    A, B, N = [int(i) for i in input().strip().split()]
    ans = 0
    if N >= B:
        if A >= B:
            n = range(B - 1, N + 1, B)[-1]
        else:
            n = range(B - 1, N + 1, B)[0]
        ans = ((A * n) // B) - (A * (n // B))
    else:
        ans = ((A * N) // B) - (A * (N // B))
    return ans


if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

N = int(input())
S = input().split()
w_index = []
r_index = []
length_ = len(S[0])

for i in range(len(S[0])):
    s = S[0][i]
    if s =='W':
        w_index.append(i)
    else:
        r_index.append(i)
        
if len(w_index) == 0 or len(r_index) == 0:
    print(0)

else:
    
    ng_num = 0
    for r_i in range(len(r_index)):

        if r_i not in r_index:
            ng_num += 1
        
    print(ng_num)

### FIXED CODE ###

N = int(input())
S = input().split()[0]

length = len(S)

W_count = S.count('W')
R_count = S.count('R')

c = 0
if R_count < W_count:
    
    for i in range(R_count):
        s = S[i]
        if s !='R':
            c+=1
        
            
else:
    for i in range(W_count):
        s = S[-1-i]
        if s != 'W':
            c+=1
print(c)
### BUGGY CODE ###

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

tot=0

for i in range(len(num)):

  tot += (num[i] % (10**9+7) * sum(num[i+1:]) % (10**9+7))
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)

### FIXED CODE ###

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

tot = 0
num2 = [0]*(N-1)
numtot = sum(num)

for i in range(len(num)-1):
  numtot -= num[i]
  num2[i] = numtot % (10**9+7)
  
  num1 = num[i] % (10**9+7)
  
  tot += num1 * num2[i]
  
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7

def combination(n, m):
    m = min(m, n-m)
    c = 1
    for i in range(m):
        c *= n - i
    for i in range(2, m+1):
        c //= i
    return c % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    # for d in range(1, val):
    #     ret += (val - d) * d
    return (val * (val - 1) * val // 2 - (val - 1) * (2 * val - 1) * val // 6) % MOD

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    m = min(n-m, m)
    for i in range(m):
        c = c * (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)
### BUGGY CODE ###

# Problem D - String Formation

# input process
S = input()
Q = int(input()) # query number

# initialization
sento = 1

# process
for i in range(Q):
    query_num = input()
    # クエリが１の時
    if query_num[0]=="1":
        # 反転処理
        if sento==1:
            sento = 10
        else:
            sento = 1
    else: # query num 2
        n, f, c = query_num.split()
        if f=="1": # 先頭追加処理
            # 先頭の位置によって変わる
            if sento==1:
                S = c + S
            else:
                S = S + c
        else: # 末尾追加処理
            if sento==1:
                S = S + c
            else:
                S = c + S

# output process
if sento==1:
    print(S)
else:
    print(S[::-1])


### FIXED CODE ###

# Problem D - String Formation

from collections import deque

# input process
S = input().replace("\n", "")
S = deque(list(S))
Q = int(input()) # query number

# initialization
sento = 1

# process
for i in range(Q):
    query_num = input()
    # クエリが１の時
    if query_num[0]=="1":
        # 反転処理
        if sento==1:
            sento = 10
        elif sento==10:
            sento = 1
    elif query_num[0]=="2":
        n, f, c = query_num.split()
        f = int(f)
        if f==1: # 先頭追加処理
            # 先頭の位置によって変わる
            if sento==1:
                S.appendleft(c)
            elif sento==10:
                S.append(c)
        elif f==2: # 末尾追加処理
            if sento==1:
                S.append(c)
            elif sento==10:
                S.appendleft(c)

# output process
if sento==1:
    print("".join(S))
else:
    print("".join(list(S)[::-1]))
### BUGGY CODE ###

n = int(input())
lis = list(map(int,input().split()))
a = 1
for i in range(n):
    a = a*lis[i]

if a > 10**18:
    print("-1")
else:
    print(a)

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
a = 1
i = 0
while a<= 10**18 and i <=n-1:
    a = a*lis[i]
    i = i + 1

if 0 in lis:
    print(0)
elif a > 10**18:
    print("-1")
else:
    print(a)
### BUGGY CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
H_list=input().split()
H_list=[int(i) for i in H_list]
path_list=[]
for i in range(M) :
  b=input().split()
  path_list.append([int(b[0]),int(b[1])])
count=0


c=list(range(1,N+1))
for i in path_list :
    if H_list[i[0]-1]>H_list[i[1]-1] :
        if  i[1] in c :
            c.remove(i[1])
    elif H_list[i[0]-1]<H_list[i[1]-1]  :
        if i[0] in c :
            c.remove(i[0])
    else :
        if i[0] in c :
            c.remove(i[0])
        if i[1] in c :
            c.remove(i[1])
print(len(c))

### FIXED CODE ###

a=input().split()
N=int(a[0])
M=int(a[1])
H_list=input().split()
H_list=[int(i) for i in H_list]
path_list=[]
for i in range(M) :
  b=input().split()
  path_list.append([int(b[0]),int(b[1])])
count=0


c=[]
for i in path_list :
    if H_list[i[0]-1]>H_list[i[1]-1] :
        c.append(i[1])
    elif H_list[i[0]-1]<H_list[i[1]-1]  :
        c.append(i[0])
    else :
        c.append(i[0])
        c.append(i[1])
k=list(set(c))
print(N-len(k))
### BUGGY CODE ###

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

from collections import defaultdict

count = defaultdict(int)
for i in A:
    count[i] += 1

for i in A:
    count[i] -= 1
    tmp = 0
    for j in count.values():
        tmp += j * (j-1) // 2
    print(tmp)
    count[i] += 1


### FIXED CODE ###

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

from collections import defaultdict

count = defaultdict(int)
for i in A:
    count[i] += 1

diff = {}
total = 0
for i in count.keys():
    tmp = count[i] * (count[i]-1) // 2
    if tmp == 0:
        diff[i] = 0
    else:
        diff[i] = tmp - (count[i]-1) * (count[i]-2) // 2
    total += tmp

prnt = 0
for i in A:
    prnt = total
    prnt -= diff[i]
    print(prnt)
### BUGGY CODE ###

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

tmp = [S[0], '']

for s in S[1:]:

    length = len(tmp)

    for i in range(length):
        if s not in tmp[i]:
            tmp.append(tmp[i]+s)

print(len(tmp)-1)

### FIXED CODE ###

from collections import Counter

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

ans = 1

for value in S.values():
    if value == 1:
        ans *= 2
    else:
        ans *= (value+1)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

import numpy as np

a, b, q = map(int, input().split())
sh = []
te = []


def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]


def checkshrine(x):
    x_near_sh = getNearestValue(sh, x)
    xsash = np.abs(x_near_sh - x)
    sh_near_te = getNearestValue(te, x_near_sh)
    return xsash + np.abs(sh_near_te - x_near_sh)


def checktemple(x):
    x_near_te = getNearestValue(te, x)
    xsate = np.abs(x_near_te - x)
    te_near_sh = getNearestValue(sh, x_near_te)
    return xsate + np.abs(te_near_sh - x_near_te)


for i in range(a):
    sh.append(int(input()))

for i in range(b):
    te.append(int(input()))

for i in range(q):
    x = int(input())
    checkshrinevalue = checkshrine(x)
    checktemplevalue = checktemple(x)
    if (checkshrinevalue > checktemplevalue):
        print(checktemplevalue)
    else:
        print(checkshrinevalue)


### FIXED CODE ###


import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

N=int(input())
s=[sorted(input()) for _ in range(N)]
m=0
for i in range(N):
  c=s.count(s[i])
  if c>1:
    m+=c-1
    s[i]=[]
print(m)

### FIXED CODE ###

N=int(input())
c_dict={}
c=0
for i in range(N):
  s=sorted(input())
  s=''.join(s)
  if s in c_dict.keys():
    c_dict[s]+=1
    c+=c_dict[s]-1
  else:
    c_dict[s]=1
print(c)
### BUGGY CODE ###

from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    a = sorted(a)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, 10**6 + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

import numpy as np
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    for _a in a:
        if table[_a]:
            table[2*_a::_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
b=[]
c=[]
for i in range(0, m):
    ib,ic = map(int, input().split(" "))
    b.append(ib)
    c.append(ic)
for i in range(0, m):
    if c[i] < a[0]:
        continue
    a[0:b[i]] = list(map(lambda x: x if c[i] < x else c[i], a[0:b[i]]))
    a.sort()
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
from collections import deque
def bfs(maze):
    d = [[-1] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                que.append([i, j])
                d[i][j] = 0
    #que = deque([[sy, sx]])
    #d[sy][sx] = 0
    while que:
        y, x = que.popleft()
 
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
                
    return d
import numpy as np
ansray = np.array(bfs(maze))
print(np.max(ansray))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

import numpy as np


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = np.zeros((city_count + 1, city_count + 1), np.uint32)

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    np.cumsum(city_list, 1, out=city_list)

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[p:q + 1, q].sum())


if __name__ == '__main__':
    main()


### FIXED CODE ###

from array import array
from itertools import accumulate, repeat, starmap
from operator import add, itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for city_index in range(2, city_count + 1):
        city_list[city_index] = array('L', starmap(
            add, zip(*(city_list[city_index + i] for i in (-1, 0)))))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[q][q] - city_list[p - 1][q])


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

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k = mi()
#a^-1 (mod P)
mod = 10 ** 9 +7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

#  これは計算量rでncr mod p を求められる。
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def main():
    if k >= n -1:
        ans = combination(2*n -1,n-1)
        print(ans)
    else:
        ans = 1
        for i in range(1,k+1):
            zero_comb = combination(n,i)
            cou = combination(n-1,n-i-1) * zero_comb % mod
            #print(cou)
            ans = (ans +cou) % mod
        print(ans)
main()


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,k = mi()
#a^-1 (mod P)
mod = 10 ** 9 +7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

'''
ここは任意
'''

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

#  これは計算量rでncr mod p を求められる。
def combination2(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def main():
    if k >= n -1:
        ans = combination2(2*n -1,n-1)
        print(ans)
    else:
        ans = 1
        for i in range(1,k+1):
            zero_comb = combination(n,i)
            cou = combination(n-1,n-i-1) * zero_comb % mod
            #print(cou)
            ans = (ans +cou) % mod
        print(ans)
main()