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

# -*- coding: utf-8 -*-

import math
import itertools
import re

# 入力
N = int(input())
S = str(input())
#M1, D1 = map(int, input().split())

si = ""
cnt = 0
for i in range(1000) :
  
  si = str(i).zfill(3)
  
  if si[0] in S and si[1] in S and si[2] in S :
    pattern = "^.*"+ si[0] + ".*" + si[1] + ".*" + si[2] + ".*$"
    if re.match(pattern, S) :
      cnt += 1

print (cnt)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import re
 
# 入力
N = int(input())
S = str(input())
#M1, D1 = map(int, input().split())
 
si = ""
cnt = 0
for i in range(1000) :
  
  si = str(i).zfill(3)
  
  c = 0
  for x in range(N) :
    if S[x] == si[c] :
      c += 1
      if c == 3 :
        cnt += 1
        break    

print (cnt)
### BUGGY CODE ###

n = int(input())
s = [list(str(input())) for k in range(n)]
s_sorted = list(map(lambda x: sorted(x), s))
ans = 0
for i in range(n):
    counter = s_sorted[:i+1].count(s_sorted[i])
    ans += counter - 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
s_sorted = []
for _ in range(n):
    s_sorted.append(''.join(sorted(input())))
s_count = Counter(s_sorted)
ans = 0
for i in s_count:
    ans += (s_count[i] * (s_count[i] - 1)) // 2
print(ans)
### BUGGY CODE ###

from heapq import nsmallest

s = input()
K = int(input())
subs = set()
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        subs.add(s[i:j])
arr = list(subs)
print(nsmallest(K, arr)[-1])


### FIXED CODE ###

from heapq import nsmallest

s = input()
K = int(input())
subs = set()
for i in range(len(s)):
    for j in range(i + 1, min(i + 6, len(s) + 1)):
        subs.add(s[i:j])
arr = list(subs)
print(nsmallest(K, arr)[-1])
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

cnt = [[10 ** 10] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
def bfs(q, v, c):
    while q:
        y, x = q.pop()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                v[ny][nx] = 1
                c[ny][nx] = min(c[ny][nx], c[y][x] + 1)
                q.append([ny, nx])





for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            queue = deque()
            queue.append([i, j])
            visited = [[0] * w for _ in range(h)]
            bfs(queue, visited, cnt)
ans = 0
for i in range(h):
    ans = max(ans, max(cnt[i]))
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

cnt = [[10 ** 10] * w for _ in range(h)]
visited = [[0] * w for _ in range(h)]
queue = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
            queue.append([i, j])
            visited[i][j] = 1

def bfs(q, v, c):
    while q:
        y, x = q.popleft()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                c[ny][nx] = c[y][x] + 1
                v[ny][nx] = 1
                q.append([ny, nx])

bfs(queue, visited, cnt)

ans = 0
for i in range(h):
    ans = max(ans, max(cnt[i]))
print(ans)
### BUGGY CODE ###

N, C = map(int, input().split())
R = [[0, 0]]
L = [[0, 0]]
for i in range(N):
    x, v = map(int, input().split())
    R.append([x, v])
for i in R[::-1]:
    L.append([C - i[0], i[1]])
L.pop(-1)

R_sum = [0]
L_sum = [0]
R_sum2 = [0]
L_sum2 = [0]
total_1 = 0
total_2 = 0
total_3 = 0
total_4 = 0
for i in range(1, N + 1):
    total_1 += R[i][1] - (R[i][0] - R[i-1][0])
    total_2 += L[i][1] - (L[i][0] - L[i-1][0])
    total_3 += R[i][1] - 2*(R[i][0] - R[i-1][0])
    total_4 += L[i][1] - 2*(L[i][0] - L[i-1][0])
    R_sum.append(total_1)
    L_sum.append(total_2)
    R_sum2.append(total_3)
    L_sum2.append(total_4)
ans = 0
for i in range(N + 1):
    for j in range(N - i + 1):
        ans = max([ans, R_sum[i] + L_sum2[j], L_sum[i] + R_sum2[j]])
print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
R = [[0, 0]]
L = [[0, 0]]
R_half = -1
for i in range(N):
    x, v = map(int, input().split())
    R.append([x, v])
for i in R[::-1]:
    L.append([C - i[0], i[1]])
L.pop(-1)

R_sum = [0]
L_sum = [0]
R_sum2 = [0]
L_sum2 = [0]
total_1 = 0
total_2 = 0
total_3 = 0
total_4 = 0
for i in range(1, N + 1):
    total_1 += R[i][1] - (R[i][0] - R[i-1][0])
    total_2 += L[i][1] - (L[i][0] - L[i-1][0])
    total_3 += R[i][1] - 2*(R[i][0] - R[i-1][0])
    total_4 += L[i][1] - 2*(L[i][0] - L[i-1][0])
    R_sum.append(total_1)
    L_sum.append(total_2)
    R_sum2.append(total_3)
    L_sum2.append(total_4)
result_1 = max(R_sum)
result_2 = max(L_sum)
big_R = []
big_L = []
t = 0
p = 0
for i in range(N+1):
    t = max(t, R_sum[i])
    big_R.append(t)
    p = max(p, L_sum[i])
    big_L.append(p)
result_3 = 0
result_4 = 0
for i in range(N+1):
    result_3 = max(result_3, L_sum2[i] + big_R[N - i])
    result_4 = max(result_4, R_sum2[i] + big_L[N - i])
print(max([result_1, result_2, result_3, result_4]))
### BUGGY CODE ###

import sys #追加
sys.setrecursionlimit(500*500)

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)

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

LCM = lcm(A)

ans = 0
for a in A:
    ans += LCM//a
    if (ans >= 1000000007):
        ans %= 1000000007

print(ans)

### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(500*500)

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)

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

LCM = lcm(A)

ans = 0
for a in A:
    ans += LCM//a

ans %= 1000000007

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

#ALDS1_3-C Elementary data structures - Doubly Linked List
n=int(input())
cmds={"insert":lambda cmd: L.insert(0,cmd[1]),
      "delete":lambda cmd: L.remove(cmd[1]) if (cmd[1] in L) else "none",
      "deleteFirst":lambda cmd: L.pop(0),
      "deleteLast": lambda cmd: L.pop()
     }
L=[]
for i in range(n):
    cmd=input().split()
    cmds[cmd[0]](cmd)
s=""
for i in L:
    s+=i+" "
print(s[:-1])

### FIXED CODE ###

#ALDS1_3-C Elementary data structures - Doubly Linked List
import collections
import sys
q = collections.deque()
n=int(input())
_input = sys.stdin.readlines()
cmds={"insert":lambda cmd: q.appendleft(cmd[1]),
      "delete":lambda cmd: q.remove(cmd[1]) if (q.count(cmd[1]) > 0) else "none",
      "deleteFirst":lambda cmd: q.popleft(),
      "deleteLast": lambda cmd: q.pop()
     }

for i in range(n):
    cmd=_input[i].split()
    cmds[cmd[0]](cmd)
print(*q)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        for j in range(1, k+1):
            ny, nx = y + dy[i] * j, x + dx[i] * j
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))

print(-1)


            
    


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
                if dist + 1 > dp[ny][nx]:
                    break
            else:
                break
print(-1)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353


dp=[defaultdict(int) for n in range(3001)]
for n in range(N):
    a=A[n]
    for s in range(0,3000)[::-1]:
        if s+a<=3000:
            for h in dp[s]:
                dp[s+a][h+1]+=dp[s][h]
    dp[a][1]+=1
c=0
for a in dp[S]:
    c+=pow(2,N-a,mod)*dp[S][a]
    c%=mod
print(c)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

gyaku=pow(2,mod-2,mod)
N2=pow(2,N-1,mod)
dp=[[0,0] for n in range(3001)]
for n in range(N):
    a=A[n]
    for s in range(0,S+1)[::-1]:
        if s+a<=S:
            dp[s+a][1]+=dp[s][1]*gyaku%mod
            dp[s+a][1]%=mod
    dp[a][1]+=N2

print(dp[S][1])
#print(c)
### BUGGY CODE ###

import copy

def Many_Medians(n , xl):

    ans = []
    ap = n // 2 - 1

    for i in range(n):
        outi = copy.copy(xl)
        outi.pop(i)
        outi.sort()
        ans.append(outi[ap])

    return ans

def main():
    n = int(input())
    xl = list(map(int , input().split()))
    ans = Many_Medians(n, xl)
    for i in range(n):
        print(ans[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy

def Many_Medians(n , xl):

    ans = []
    left = n // 2
    right = n // 2 - 1
    sort_xl = sorted(xl)

    for x in xl:
        if x < sort_xl[left]:
            ans.append(sort_xl[left])
        else:
            ans.append(sort_xl[right])

    return ans

def main():
    n = int(input())
    xl = list(map(int , input().split()))
    ans = Many_Medians(n, xl)
    for i in range(n):
        print(ans[i])

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

N = int(input())

double = 1

for i in range(1, N+1):
  double = double*i
  
print(double%(10**9+7))


### FIXED CODE ###

N = int(input())
 
double = 1
a = 10**9+7
 
for i in range(1, N+1):
  double *= i
  double %= a
  
print(double)
### BUGGY CODE ###

'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    def dp(num):
        dp = [[0]*(K) for _ in range(N)]
        dp[0][0] = 1
        b = a[:num]+a[num+1:] #N-1個
        for i in range(N-1):
            for j in range(K):
                if b[i]<=j:
                    dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
                else:
                    dp[i+1][j]=dp[i][j]
        return any(dp[N-1][K-a[num]:])

    left = 0
    right = N-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)


    import numpy as np
    def dp(omit):
        dp = np.zeros((n+1, K), dtype=np.bool)
        dp[0,0] = 1
        for i in range(n):
            # まとめて遷移
            dp[i+1] |= dp[i]
            if i != omit and a[i] < K:
                dp[i+1,a[i]:] |= dp[i,:K-a[i]]
        # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
        for j in range(max(0, K-a[omit]), K):
            if dp[n,j]:
                return True
        # なければ不要
        return False


    # def dp(num):
    #     dp = [[0]*(K) for _ in range(n)]
    #     dp[0][0] = 1
    #     b = a[:num]+a[num+1:] #N-1個
    #     for i in range(n-1):
    #         for j in range(K):
    #             if b[i]<=j:
    #                 dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
    #             else:
    #                 dp[i+1][j]=dp[i][j]
    #     return any(dp[n-1][K-a[num]:])

    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

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

from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(10**(n-i-1)%mod))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

ans = 0
for i in arr.values():
    ans += i*(i-1)//2
print(ans)


### FIXED CODE ###

from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(pow(10,n-i-1,mod)))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

ans = 0
for i in arr.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = [1]+list(map(int,input().split()))
 
for i in range(1,N+1):
  A[i] = A[i-1]*A[i]
 
for i in range(K+1, N+1):
  prev = A[i-1] // A[i-K-1]
  now = A[i] // A[i-K]
  if now > prev:
    print('Yes')
  else:
    print("No")

### FIXED CODE ###

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

for i in range(K, N):
  if A[i] > A[i-K]:
    print('Yes')
  else:
    print("No")
### BUGGY CODE ###

N = int(input())

l = []
for i in range(N):
    S = input()
    if not S in l:
        l.append(S)
print(len(l))


### FIXED CODE ###

N = int(input())

l = set()
for i in range(N):
    S = input()
    l.add(S)
print(len(l))
### BUGGY CODE ###

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

seta.sort(reverse=True)
c2 = []
c4 = 0
for i in seta:
  if a.count(i)>=2:
    c2.append(i)
    if len(c2) == 2:
      break
  
for i in seta:
  if a.count(i)>=4:
    c4=i
    break

if c4 == 0 and len(c2)<2:
  print(0)
elif c4 == 0 and len(c2)>=2:
  print(c2[0]*c2[1])
elif c4 > 0 and len(c2)<2:
  print(c4**2)
else:
  print(max(c4**2,c2[0]*c2[1]))

### FIXED CODE ###

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

e=[]
a.sort(reverse=True)
for i in range(len(a)-1):
  if a[i] == a[i+1] and a[i] not in e:
    e.append(a[i])
    if len(e) == 2:
      break
e.sort(reverse=True)

c4 = 0
for i in e:
  if a.count(i)>=4:
    c4=i
    break

if c4 == 0 and len(e)<2:
  print(0)
elif c4 == 0 and len(e)>=2:
  print(e[0]*e[1])
elif c4 > 0 and len(e)<2:
  print(c4**2)
else:
  print(max(c4**2,e[0]*e[1]))
### BUGGY CODE ###

import sys
from bisect import bisect, bisect_left

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])
        #print(self.tree)

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)

def solve():
    input = sys.stdin.readline
    N = int(input())
    R = [[int(i) for i in input().split()] for _ in range(N)]
    R.sort()
    mod = 998244353
    X = [R[i][0] for i in range(N)]
    D = [R[i][1] for i in range(N)]
    Connect = RMQ(N, 0)
    DP = [1] * (N + 1)
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, X[i] + D[i]), 0, Connect.size, 0))
        Connect.update(i, right)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from bisect import bisect, bisect_left

class SquareDiv(): #区間の最大値を求める
    def __init__(self, N, V):
        k = 1
        while k ** 2 < N: k += 1
        self.array = [V] * k
        self.size = k
        self.indivisual = [V] * N

    def update(self, i, v): #i番目をvに更新する
        self.indivisual[i] = v
        self.array[i // self.size] = max(self.array[i // self.size], v)

    def search(self, left, right): #[left, right]の最大値を求める
        lk, rk = left // self.size, right // self.size
        if lk == rk:
            maxN = 0
            for i in range(left, right + 1): maxN = max(maxN, self.indivisual[i])
            return maxN
        else:
            maxN = self.search(left, (lk + 1) * self.size - 1)
            for k in range(lk + 1, rk): maxN = max(maxN, self.array[k])
            maxN = max(maxN, self.search(rk * self.size, right))
            return maxN

def solve():
    input = sys.stdin.readline
    N = int(input())
    R = [[int(i) for i in input().split()] for _ in range(N)]
    R.sort()
    mod = 998244353
    X = [R[i][0] for i in range(N)]
    Connect = SquareDiv(N, 0)
    DP = dict()
    DP[N] = 1
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, sum(R[i])) - 1))
        Connect.update(i, right)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])
    

    return 0

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

import math
A,B,N= map(int,input().split())

if N>=B:
  N=B
  
max=0
for i in reversed(range(1, N+1)):
  y=math.floor(A*i/B)-A*math.floor(i/B)
  if max < y :
    max=y
print(int(max))

### FIXED CODE ###

import math
A,B,N= map(int,input().split())

max=0
if N>B:
  N=B-1
  y=math.floor(A*N/B)-A*math.floor(N/B)
  print(int(y))
elif N==B:
  N=B-1
  y=math.floor(A*N/B)-A*math.floor(N/B)
  print(int(y))
else:
	y=math.floor(A*N/B)-A*math.floor(N/B)
	print(int(y))
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
#a本、b本の制限を無視すると、2^n - 1の選び方が存在する。
ans = pow(2, n, mod) - 1 % mod

def choose(n, a):
    x = y = 1
    for i in range(a):
        y *= (i + 1) % mod
        x *= (n - i) % mod
    return x * pow(y, mod - 2, mod) % mod 
#上記で求めた値から、a本を選んだ時とb本を選んだ時の組み合わせ数を引く
ans -= choose(n, a)
ans -= choose(n, b)

print(ans % mod)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
#a本、b本の制限を無視すると、2^n - 1の選び方が存在する。
ans = pow(2, n, mod) - 1 

def choose(n, a):
    x, y = 1, 1
    for i in range(a):
        y = y * (i + 1) % mod
        x = x * (n - i) % mod
    return x * pow(y, mod - 2, mod) % mod 
#上記で求めた値から、a本を選んだ時とb本を選んだ時の組み合わせ数を引く
ans -= choose(n, a)
ans -= choose(n, b)

print(ans % mod)
### BUGGY CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(sum(list(map(reverse, tail))))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

diff = [r-b for r, b in zip(sum_red, sum_blue)]
print(max(diff))


### FIXED CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))
### BUGGY CODE ###

n, m = map(int, input().split(" "))

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

for _ in range(m):
    max_ix = a.index(max(a))
    a[max_ix] //= 2

print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split(" "))

a = [- int(i) for i in input().split(" ")]
heapq.heapify(a)

for _ in range(m):
    largest = heapq.heappop(a)
    heapq.heappush(a, int(largest / 2))

print(- sum(a))