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

s = input()
divisor = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(s) + 1)]
dp[0][0] = 1
lut = [i % 13 for i in range(130)]
for i in range(len(s)):
  dpi = dp[i]
  dpi1 = dp[i + 1]
  if s[i] == '?':
    for j in range(13):
      dpij = dpi[j]
      j10 = j * 10
      for k in range(10):
        dpi1[lut[j10 + k]] += dpij
  else:
    t = int(s[i])
    for j in range(13):
      dpi1[lut[j * 10 + t]] += dpi[j]
  for k in range(13):
    dp[i + 1][k] %= divisor
print(dp[len(s)][5])


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

N=int(input())
arr = list(map(int,list(input().split())))
############################################

allxor=0
for i in range(len(arr)):
	allxor=allxor ^ arr[i]


for i in range(len(arr)):
	if i==0 :
		s=str(allxor ^ arr[i])
	else:
		s=s + ' ' + str((allxor ^ arr[i]))

print(s)


### FIXED CODE ###

N=int(input())
arr = list(map(int,list(input().split())))
ds = set(arr)
############################################

allxor=0
for i in range(N):
	#if len(ds)==0:
	#	break
	#allxor=allxor ^ ds.pop()
	allxor=allxor ^ arr[i]

for i in range(N):
	print(allxor ^ arr[i],end='')
	print(' ',end='')

#for i in range(N):
#	if i==0 :
#		s=str(allxor ^ arr[i])
#	else:
#		s=s + ' ' + str((allxor ^ arr[i]))
#print(s)
### BUGGY CODE ###

n = int(input())
s = [list(input()) for _ in range(n)]
ans = 0
alphcnt = [0] * 26
for i in range(n):
    for j in range(n):
        alphcnt[ord(s[i][j]) - 97] += 1
if max(alphcnt) == pow(n, 2):
    print(pow(n, 2))
    exit()
for k in range(n):
    c = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not s[(i + k) % n][j] == s[(j + k) % n][i]:
                c = 0
                break
        if c == 0:
            break
    if c == 1:
        ans += n
print(ans)

### FIXED CODE ###

n = int(input())
s = [list(input()) for _ in range(n)]
ans = 0
alphcnt = [0] * 26
for i in range(n):
    for j in range(n):
        alphcnt[ord(s[i][j]) - 97] += 1
if max(alphcnt) == pow(n, 2):
    print(pow(n, 2))
    exit()
for k in range(n):
    c = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not s[(i + k) % n][j] == s[(j + k) % n][i]:
                c = 0
                break
        if c == 0:
            break
    if c == 1:
        ans += n
print(ans)
### BUGGY CODE ###

N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
for _ in range(M):
    tmp=list(map(int,input().split()))
    for _ in range(tmp[0]):
        A.append(tmp[1])
A.sort()
print(sum(A[-N:]))

### FIXED CODE ###

from collections import Counter
N,M=list(map(int,input().split()))
cards=list(map(int,input().split()))
all_c=Counter(cards)

for i in range(M):
    time,val=list(map(int,input().split()))
    try:
        all_c[val]+=time
    except:
        all_c[val]=time

tmp=list(all_c.keys())
tmp.sort(reverse=True)
total=0
sum_time=0
for i in tmp:
    if sum_time>=N:
        break
    sum_time+=all_c[i]
    if sum_time<N:
        total+=i*all_c[i]
    else:
        total+=i*(all_c[i]+N-sum_time)
print(total)
### BUGGY CODE ###

x, y = map(int, input().split())
dp = [0]*(y+1)

for i in range(x):
    w, v = map(int, input().split())
    for j in range(y, w-1, -1):
        num = dp[j-w]+v
        if num > dp[j]:
            dp[j] = num
print(dp[-1])

### FIXED CODE ###

def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    dp = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[w])


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

N=int(input())
S=list(input())
ans=0
R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)
lenb=len(B)
for r in R:
    for g in G:
        flag=0
        for b in B:
            a=r+g+b
            if a%3==0:
                a=a//3
                if a==r or a==g or a==b:
                    flag=flag+1
        ans=ans+lenb-flag
print(ans)


### FIXED CODE ###

N=int(input())
S=list(input())
ans=0
R=0
G=0
B=0
for i in range(N):
    if S[i]=="R":
        R=R+1
    elif S[i]=="G":
        G=G+1
    else:
        B=B+1
ans=R*G*B
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if N<=k:
                continue
            if S[i]!=S[k] and S[k]!=S[j]:
                ans=ans-1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)


### FIXED CODE ###

n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)
### BUGGY CODE ###

S=input()
lens=len(S)

mod=10**9+7

Alist=[0]*lens
Blist=[0]*lens
Clist=[0]*lens
qlist=[0]*lens

Asum=[0]*lens
Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Alist[i]=1
    elif S[i]=="B":
        Blist[i]=1
    elif S[i]=="C":
        Clist[i]=1
    elif S[i]=="?":
        qlist[i]=1

    Asum[i]=Asum[i-1]+Alist[i]
    Bsum[i]=Bsum[i-1]+Blist[i]
    Csum[i]=Csum[i-1]+Clist[i]
    qsum[i]=qsum[i-1]+qlist[i]

ASUM=Asum[lens-1]
CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

print(count%mod)

### FIXED CODE ###

S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-3),mod)%mod
        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K=int(input())

i=1
j=1
k=1
r=0

while(i<K+1):
  j=1
  while(j<K+1):
    k=1
    while(k<K+1):
      r+=gcd(i, j, k)
      k+=1
    j+=1
  i+=1

print(r)

### FIXED CODE ###

import math

K=int(input())
r=0

for i in range(1,K+1):
  for j in range(1,K+1):
    a=math.gcd(i,j)
    for k in range(1,K+1):
      b=math.gcd(a,k)
      r+=b
print(r)
### BUGGY CODE ###

#C問題
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 0
div = 0
flag = True
while flag:
    flag = False
    for i in range(N):
        if B[i] > B[i-1]+B[(i+1)%N] and B[i] != A[i]:
            div = (B[i]-A[i])//(B[i-1]+B[(i+1)%N])
            B[i] -= (B[i-1]+B[(i+1)%N])*div
            ans+=div
            flag = True
            
print(ans if A == B else -1)

### FIXED CODE ###

#C問題
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 0
div = 0
flag = 1
while flag == 1:
    flag = 0
    for i in range(N):
        if B[i]-B[i-1]-B[(i+1)%N] >= A[i]:
            div = (B[i]-A[i])//(B[i-1]+B[(i+1)%N])
            B[i] -= (B[i-1]+B[(i+1)%N])*div
            ans+=div
            flag = 1
            
print(ans if A == B else -1)
### BUGGY CODE ###

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

mod = 10**9 + 7

if a > n//2:
	a = -1 * (a-n)
if b > n//2:
	b = -1 * (b-n)

#print(a,b)

num = 1
ans = 1
for i in range(n//2):
	num = (num * (n-i)) // (i+1)
	ans += num * 2
	if a == i+1:
		ans -= num
	if b == i+1:
		ans -= num
if n % 2 == 0:
	ans -= num
if a == 0:
	ans -= 1
if b == 0:
	ans -= 1

print(ans)


### FIXED CODE ###

def pow_k(x, n):
    """
    O(log n)
    """
    MOD = 10 ** 9 + 7
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= MOD
        x *= x
        x %= MOD
        n //= 2

    return K * x

def cmb(n, r):
	MOD = 10**9+7
	if n - r < r: r = n - r
	if r == 0: return 1
	if r == 1: return n

	numerator = [n - r + k + 1 for k in range(r)]
	denominator = [k + 1 for k in range(r)]

	for p in range(2,r+1):
		pivot = denominator[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p-1,r,p):
				numerator[k - offset] /= pivot
				denominator[k] /= pivot

	result = 1
	for k in range(r):
		if numerator[k] > 1:
			result *= int(numerator[k])
			result %= MOD

	return result

n,a,b = map(int,input().split())
MOD = 10**9+7

ans = pow_k(2,n)-1

print((ans - cmb(n,a) - cmb(n,b))%MOD)
### BUGGY CODE ###


import collections
n, m = [ int(v) for v in input().split() ]
num_list = [ int(v) for v in input().split() ]
total_counter = collections.Counter(num_list)
for i in range(m):
    b, c =  [ int(v) for v in input().split() ]
    total_counter[c] += b


total_counter_2 = list(zip(total_counter.keys(), total_counter.values()))

ans_list = []
c = 0
for i in sorted(total_counter_2,reverse = True):
    p, q = i
    for j in range(q):
        ans_list.append(p)
    c += q
    if c >= n:
        break
print(sum(ans_list[:n]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

def swap(a):
    return ((a[1],a[0]))


n, m = [ int(v) for v in input().split() ]
num_list = [ (int(v), 1) for v in input().split() ]
change_list = [ swap([ int(v) for v in input().split() ]) for i in range(m) ]
total_list = sorted(num_list + change_list, reverse = True)

k = n
ans = 0

for i in total_list:

    j = min(i[1], k)
    k -= j
    ans += i[0] * j
    if k == 0:
        break
print(ans)
### BUGGY CODE ###

a,b=map(int,input().split())
b=b*2+1
c=1
while 1:
  if a-b>0:
    c+=1
  else:
    break
  
print(c)    

### FIXED CODE ###

a,b=map(float,input().split())

d=b*2+1

c=a/d

if c>int(c):
  print(int(c)+1)
else:
  print(int(c))
### BUGGY CODE ###

n = int(input())
a = input().replace(" ", "")

for i in range(1, n):
    print(a.count(str(i)))

print(0)

### FIXED CODE ###

n = int(input())
b = [0] * n
a = list(map(int, input().split()))

for i in a:
    b[i-1] += 1
for i in b:
    print(i)
### BUGGY CODE ###

S = list(reversed(input()))
size = len(S)
ans = 0
d = [-1]*(size)#余りを格納

def cnt(num):
  return d.count(num)
  
for i in range(size):
  s = ''.join(reversed(S[:i+1]))
  md = int(s) % 2019
  if md == 0:#その数自身が割り切れた場合
    ans+=1
  ans += cnt(md)
  d[i] = md

print(ans)
  
  

### FIXED CODE ###

S = input()
size = len(S)
ans = 0
d = [0]*2019
pre = ''
ln = 0
v = 1
  
for i in range(1,size+1):
  md = (ln +(int(S[-1*i])*v))%2019
  d[md] += 1
  ln = md
  v *= 10
  v %= 2019

d[0] += 1
for i in range(2019):
  ans += d[i]*(d[i]-1)/2 #1~(n-1)までの和

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

n, m, q = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(m)]
y = [tuple(map(int, input().split())) for _ in range(q)]

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

for i, j in x:
    table[i-1][j-1] += 1

for i, j in y:
    ans = 0
    for s in range(i-1, j):
        for t in range(i-1, j):
            ans += table[s][t]
    print(ans)

'''
for i in range(n):
    for j in range(1, n):
        table[i][j] += table[i][j-1]

for i in range(n-1, 0, -1):
    for j in range(n):
        table[i-1][j] += table[i][j]

for i, j in y:
    print(table[i-1][j-1])
'''


### FIXED CODE ###

n, m, q = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(m)]
y = [tuple(map(int, input().split())) for _ in range(q)]

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

for i, j in x:
    table[i-1][j-1] += 1

for i in range(n):
    for j in range(1, n):
        table[i][j] += table[i][j-1]

for i in range(n-1, 0, -1):
    for j in range(n):
        table[i-1][j] += table[i][j]

for i, j in y:
    print(table[i-1][j-1])
### BUGGY CODE ###

import math
import numpy

N , Y = map(int, input().split())
conc = True
a_ = Y // 10000
for i in range(a_ + 1):
	a = i
	b_ = (Y - 10000*a) // 5000
	for k in range(b_ + 1):
		b = k
		if ((Y - 10000*a - 5000*b) % 1000) == 0:
			c = int((Y - 10000*a - 5000*b) / 1000)
			if (a + b + c) == N:
				print(str(a) +" "+ str(b) + " " + str(c))
				conc = False
				break
	if conc == False:
		break
if conc:
	print("-1 -1 -1")

### FIXED CODE ###

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

flag = True

for i in range(Y // 10000 + 1):
    for k in range((Y - 10000*i) // 5000 + 1):
        l = int((Y - 10000*i - 5000*k) / 1000)
        if (i + k + l) == N:
            print(str(i) + " " + str(k) + " " + str(l))
            flag = False
            break
    if flag == False:
        break
if flag:
    print("-1 -1 -1")
### BUGGY CODE ###

n=int(input())
p=list(map(int, input().split()))
c=0
x = sorted(p)
a,b= x[int(n/2)-1], x[int(n/2)]
for k in range(a, b+1):
  arc = []
  abc = []
  for i in p:
    if k >= i:
      arc.append(arc)
    elif k <= i:
      abc.append(abc)
  if len(arc) == len(abc):
    c+=1
print(c)

### FIXED CODE ###

n=int(input())
p=sorted(list(map(int, input().split())))
print(p[int(n/2)]-p[int(n/2)-1])
### BUGGY CODE ###

def im(a):
    imos = [0] * (3*N+1)
    for i in range(N):
        imos[N+i-min(N,a[i])] += 1
        imos[N+i+min(N,a[i])+1] -= 1
    cs = [0]
    for i in range(1,2*N+1):
        cs.append(cs[i-1]+imos[i-1])
    return cs[N+1:]

N,K,*A = map(int, open(0).read().split())
for i in range(K):
    A = im(A)
print(*A)

### FIXED CODE ###

def im(a):
    imos = [0] * (3*N+1)
    for i in range(N):
        imos[N+i-min(N,a[i])] += 1
        imos[N+i+min(N,a[i])+1] -= 1
    cs = [0]
    for i in range(1,2*N+1):
        cs.append(cs[i-1]+imos[i-1])
    return cs[N+1:]

N,K,*A = map(int, open(0).read().split())
for i in range(K):
    A = im(A)
    if A.count(N) == N:
        break
print(*A)
### BUGGY CODE ###

s = list(input())
q = int(input())
flg = False
for i in range(q):
    try:
        t,f,c = input().split()
        if flg:
            if f == '1':
                s.append(c)
            else:
                s.insert(0,c)
        else:
            if f == '1':
                s.insert(0,c)
            else:
                s.append(c)
    except ValueError:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    print(''.join(s[::-1]))
else:
    print(''.join(s))

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())
flg = True
for _ in range(q):
    try:
        t,f,c = input().split()
        if flg:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)
    except ValueError:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    print(''.join(s))
else:
    s = list(reversed(s))
    print(''.join(s))
### BUGGY CODE ###

from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        # そもそもcがaやbより大きいので、下の解法のようにilを求める必要などなく、il=で考えれば良かったんや！
        k = bisect_left(L, L[i]+L[j], lo=j)
        ans += k - j - 1



"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1
"""

print(ans)


### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]

        il = bisect_right(L, l, j)
        ir = bisect_left(L, r, j)

        if il == N-1:
            break

        ans += ir - il - 1

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

n=int(input())
List=list(map(int,input().split()))
newList =[0] * n
count = 0
for i in range(1, n + 1):
    # print(i)
    # print(List[0:i])
    # print(min(List[0:i]))
    newList[i - 1] = min(List[0:i])

# print(newList)
for j in range(n):
    if(List[j] <= newList[j]):
        count = count + 1
print(count)

### FIXED CODE ###

n=int(input())
List=list(map(int,input().split()))
newList =[0] * n
count = 0
min = List[0]
# print(List)
for i in List:
    # 最小値更新
    if i < min:
        min = i
    # カウントする
    if min >= i:
        count = count + 1

print(count)
### BUGGY CODE ###

L, R = map(int,input().split())
ans = 2019
print(min([i*j%2019 for i in range(L, R) for j in range(i+1, R+1)]))

### FIXED CODE ###

L, R = map(int,input().split())
if R - L >= 2019:
    print(0)
else:
    ans = 2019
    print(min([i*j%2019 for i in range(L, R) for j in range(i+1, R+1)]))
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
AC_or_No=[]
ans=[]
n=0

while n<=N-2:
    if S[n]=="A":
        if S[n+1]=="C":
            AC_or_No.append(1)
            AC_or_No.append(0)
            n+=2
    else:
        AC_or_No.append(0)
        n+=1

for _ in range(Q):
    l,r=map(int,input().split())
    ans.append(sum(AC_or_No[l-1:r-1]))

for i in ans:
    print(i)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
AC_or_No=[0]
ans=[]
n=0

while n<=N-2:
    if S[n]=="A" and S[n+1]=="C":
        AC_or_No.append(AC_or_No[n]+1)
    else:
        AC_or_No.append(AC_or_No[n])
    n+=1

for _ in range(Q):
    l,r=map(int,input().split())
    ans.append(AC_or_No[r-1]-AC_or_No[l-1])

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

N = int(input())
A = list(map(int, input().split()))  # O(N)
p = len(format(max(A), 'b')) # O(N)
digit = ['0' + str(p) + 'b'] * N
S = list(map(format, A, digit))  # O(N)

r = [0] * p
for s in S:
  for j in range(p):
    r[j] += int(s[j])

ans = 0
for j in range(p):
  ans += r[-(j+1)] * (N - r[-(j+1)]) * (2 ** j)

print(ans % ((10 ** 9) + 7))

### FIXED CODE ###

import numpy as np 
N = int(input())
A = np.fromstring(input(), dtype = np.int64, sep = ' ')

res = 0
for bit in range(60):
  c = int((A & 1).sum())
  res += c * (N - c) * (1 << bit)
  A >>= 1

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

# 2 6=>4 (1,6)*2,(2,3)*2
# 3 12=>18 (1,1,12)*3,(1,2,6)*6,(1,3,4)*6,(2,2,3)*3
import math
def comb(a,b): # aCb
    return math.factorial(a)//math.factorial(a-b)//math.factorial(b)

n,m=map(int,input().split())
divisor={}
tmp=m
# for i in range(2,m+1):
i=2
while i*i<=m:
    while tmp%i==0:
        tmp//=i
        divisor.setdefault(i,0)
        divisor[i]+=1
    # if tmp==1:
    #     break
    i+=1
if tmp>1:
    divisor[tmp]=1
# print(divisor)
cnt=1
for key in divisor:
    c=divisor[key]
    cnt*=comb(c+n-1,c)
print(cnt%1000000007)


### FIXED CODE ###

# うまく効率化できなかった
# 2 6=>4 (1,6)*2,(2,3)*2
# 3 12=>18 (1,1,12)*3,(1,2,6)*6,(1,3,4)*6,(2,2,3)*3
# import math
# def comb(a,b):
#     return math.factorial(a)//math.factorial(a-b)//math.factorial(b)
def comb(a,b): # aCb
    b=min(b,a-b)
    result=1
    for i in range(a,a-b,-1):
        result*=i
    for i in range(1,b+1):
        result//=i
    return result

n,m=map(int,input().split())
divisor={}
tmp=m
# for i in range(2,m+1):
#     while tmp%i==0:
#         tmp//=i
#         divisor.setdefault(i,0)
#         divisor[i]+=1
#         if tmp==1:
#             break
i=2
while i*i<=m:
    while tmp%i==0:
        tmp//=i
        divisor.setdefault(i,0)
        divisor[i]+=1
    i+=1
if tmp>1:
    divisor[tmp]=1
# print(divisor)
cnt=1
for key in divisor:
    c=divisor[key]
    cnt*=comb(c+n-1,c)
print(cnt%1000000007)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(N):
  ans+=(i+1)
print(ans - N)

### FIXED CODE ###

N=int(input())
print((N+1) * (N // 2) - N if N%2==0 else (N+1) * (N // 2) + int(N/2+1) - N)
### BUGGY CODE ###

N,a,b=map(int,input().split())
m = 10**9+7
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

M = pow(2, N)%m

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
res = 1
for i in range(1,N+1):
    res = res*i%m
for i in range(1,N-a+1):
    res = res*mod_inv(i,m)%m
for i in range(1,a+1):
    res = res*mod_inv(i,m)%m

rs = 1
for i in range(1,N+1):
    rs = rs*i%m
for i in range(1,N-b+1):
    rs = rs*mod_inv(i,m)%m
for i in range(1,b+1):
    rs = rs*mod_inv(i,m)%m

print(M-1-res-rs)

### FIXED CODE ###

N,a,b=map(int,input().split())
m = 10**9+7

M = pow(2, N, m)

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    else:
        a = b = 1
        for i in range(r):
            a = a * (n - i) % m
            b = b * (r - i) % m
        return (a * pow(b,m-2,m)) % m
 
ans = M - 1 - nCr(N,a) - nCr(N,b)
print(ans%m)