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

MOD = 10 ** 9 + 7

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

A = [list(map(int, input().split())) for _ in range(N)]

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    N = len(matrix[0])
    if n == 0:
        lst = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
        return lst
    lst = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # print (i, j, k)
                lst[i][j] += matrix[i][k] * matrix[k][j]
            lst[i][j] %= mod
    res = mod_pow(lst, n // 2, mod)

    lst = [[0] * N for _ in range(N)]
    if n % 2 == 1:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    lst[i][j] += res[i][k] * matrix[k][j]
                lst[i][j] %= mod
        return lst
    return res 

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i][j]
        ans %= MOD

ans %= MOD
print (ans)

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

A = [list(map(int, input().split())) for _ in range(N)]

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    N = len(matrix[0])
    if n == 0:
        lst = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
        return lst
    lst = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # print (i, j, k)
                lst[i][j] += matrix[i][k] * matrix[k][j]
            lst[i][j] %= mod
    res = mod_pow(lst, n // 2, mod)

    lst = [[0] * N for _ in range(N)]
    if n % 2 == 1:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    lst[i][j] += res[i][k] * matrix[k][j]
                lst[i][j] %= mod
        return lst
    return res 

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i][j]
        ans %= MOD

ans %= MOD
print (ans)
### BUGGY CODE ###

import functools
import operator

N = int(input())
A = list(map(int,input().split()))
over_value = 10 ** 18 + 1
total = functools.reduce(operator.mul, A)

if total >= over_value:
    total = -1
print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
over_value = 10 ** 18
total = 1
cnt = 0
while cnt < N:
    total *= A[cnt]
    if total > over_value:
        total = -1
        break
    cnt += 1
    
for i in range(N):
    if A[i] == 0:
        total = 0
print(total)
### BUGGY CODE ###

import math
from functools import reduce

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

k = int(input())
tmp = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      tmp += gcd_list([a, b, c])
print(tmp)


### FIXED CODE ###

import math
from functools import reduce

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

k = int(input())
tmp = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      #print('a='+str(a)+', b='+str(b)+', c='+str(c))
      if a == b and a == c:
        tmp += gcd_list([a, b, c]) 
      elif a == b and a != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      elif b == c and a != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      elif a == c and b != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      else:
        tmp += gcd_list([a, b, c]) * 6
#        tmp += gcd_list([a, c, b])
#        tmp += gcd_list([b, a, c])
#        tmp += gcd_list([b, c, a])
#        tmp += gcd_list([c, a, b])
#        tmp += gcd_list([c, b, a])
print(tmp)
### BUGGY CODE ###

s = input()
N = len(s)

# dp[何文字目][パーを出した回数]
dp = [[0] * (N // 2 + 1) for _ in range(N + 1)]
for i in range(1, N + 1) :
    p = (s[i-1] == 'p')
    dp[i][0] = dp[i-1][0] - (1 if p else 0)
    for j in range(1, i // 2 + 1) :
        dp[i][j] = max(dp[i-1][j-1] + (0 if p else 1), dp[i-1][j] - (1 if p else 0))
        
        
print(max(dp[-1]))

### FIXED CODE ###

s = input()

ret = 0
g, p = 0, 0
for s_ in s :
    if s_ == 'g' :
        if p < g :
            p += 1
            ret += 1
        else :
            g += 1
    else :
        if p < g :
            p += 1
        else :
            g += 1
            ret -= 1
            
print(ret)
### BUGGY CODE ###

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

ans = 0

for i in range(n):
  if all(e >= p[i] for e in p[: i + 1]):
    ans += 1
    
print(ans)

### FIXED CODE ###

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

tmp_min = p[0]
cnt = 0

for i in range(n):
    if p[i] <= tmp_min:
        tmp_min = p[i] #i番目までの最小値を更新
        cnt += 1

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

N = int(input())
color_list = []
for i in range(N):
    a = int(input())
    for j in range(len(color_list)):
        if a > color_list[j]:
            color_list[j] = a
            break
    else:
        color_list.append(a)
print(len(color_list))


### FIXED CODE ###

def reverse_bisect(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo

N = int(input())
color_list = []
color_len = 0
for i in range(N):
    a = int(input())
    index = reverse_bisect(color_list, a, 0, color_len)
    if(index == color_len):
        color_list.append(a)
        color_len += 1
    else:
        color_list[index] = a
print(color_len)
### BUGGY CODE ###

def f(s):
    n = len(s)
    dp = [[0, 0, 0, 0] for _ in range(n + 1)]
    pre = dp[0]
    for i, c in enumerate(s):
        cur = dp[i + 1]
        if c == "A":
            cur[0] = (pre[0] + 3 ** pre[3]) % md
            cur[1:] = pre[1:]
        elif c == "B":
            cur[0] = pre[0]
            cur[1] = (pre[0] + pre[1]) % md
            cur[2:] = pre[2:]
        elif c == "C":
            cur[:2] = pre[:2]
            cur[2] = (pre[1] + pre[2]) % md
            cur[3] = pre[3]
        else:
            cur[0] = (pre[0] * 3 + 3 ** pre[3]) % md
            cur[1] = (pre[1] * 3 + pre[0]) % md
            cur[2] = (pre[2] * 3 + pre[1]) % md
            cur[3] = (pre[3] + 1) % md
        pre = cur
    print(dp[-1][-2])

md = 10 ** 9 + 7
s = input()
f(s)


### FIXED CODE ###

md=10**9+7
s=input()
dp=[[0]*4 for _ in range(3)]
for c in s:
    if c=="A":dp[0][0]=(dp[0][0]+1)%md
    if c=="B":
        for j in range(2):dp[1][j]=(dp[1][j]+dp[0][j])%md
    if c=="C":
        for j in range(3):dp[2][j]=(dp[2][j]+dp[1][j])%md
    if c=="?":
        for j in range(3):dp[2][j+1]=(dp[2][j+1]+dp[1][j])%md
        for j in range(2):dp[1][j+1]=(dp[1][j+1]+dp[0][j])%md
        dp[0][1] = (dp[0][1] + 1) % md
ans=0
q=s.count("?")
for j in range(4):
    if q-j<0:break
    ans+=dp[2][j]*pow(3,q-j,md)
    ans%=md
print(ans)
### BUGGY CODE ###

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

for i in range(k):
    new_list = [0 for _ in range(n)]
    start_list = [0 for num in range(n)]
    end_list = [0 for num in range(n)]
    for j, a in enumerate(a_list):
        if j-a > 0:
            start_list[j-a] += 1
        else:
            start_list[0] += 1
        if a+j < n:
            end_list[a+j] += 1
        else:
            end_list[n-1] += 1
    now_sum = 0
    # print(start_list)
    # print(end_list)
    for j in range(n):
        now_sum += start_list[j]
        new_list[j] = now_sum
        now_sum -= end_list[j]
    # print(new_list)
    a_list = new_list.copy()

for a in a_list:
    print(a, end= ' ')


### FIXED CODE ###

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

diff_list = [0 for num in range(n)]
diff_list[0] = a_in[0]
for i in range(1, n):
    diff_list[i] = a_in[i] - a_in[i-1]

itr = k
if k > 41:
    itr = 41
for i in range(itr):
    new_list = [0 for num in range(n)]
    d_sum = 0
    for j, d in enumerate(diff_list):
        d_sum += d
        if j-d_sum > 0:
            new_list[j-d_sum] += 1
        else:
            new_list[0] += 1
        if d_sum+j+1 < n:
            new_list[j+d_sum+1] -= 1
    # print(new_list)
    diff_list = new_list.copy()

ans = 0
for d in diff_list:
    ans += d
    print(ans, end= ' ')
### BUGGY CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    A.sort()
    B.sort()
    C.sort()
    
    A_cand = [0 for i in range(N)]
    B_cand = [0 for i in range(N)]
    for i in range(N):
        cnt = 0
        for j in range(N):
            if B[i] < C[N-j-1]:
                cnt += 1
            else:
                break
        B_cand[i] = cnt
    
    for i in range(N):
        cnt = 0
        for j in range(N):
            if A[i] < B[N-j-1]:
                cnt += B_cand[N-j-1]
            else:
                break
        A_cand[i] = cnt
    print(sum(A_cand))
    

solve()

### FIXED CODE ###

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    A.sort()
    B.sort()
    C.sort()
    
    A_cand = [0 for i in range(N)]
    B_cand = [0 for i in range(N)]
    
    skip_loop = 0
    for i in range(N):
        cnt = skip_loop
        for j in range(N-skip_loop):
            if B[N-i-1] < C[N-skip_loop-j-1]:
                cnt += 1
            else:
                break
        B_cand[N-i-1] = cnt
        skip_loop = cnt
    
    skip_loop = 0
    ans = 0
    pre_loop_ans = 0
    for i in range(N):
        cnt = skip_loop
        ans += pre_loop_ans
        for j in range(N-skip_loop):
            if A[N-i-1] < B[N-skip_loop-j-1]:
                ans += B_cand[N-skip_loop-j-1]
                pre_loop_ans += B_cand[N-skip_loop-j-1]
                cnt += 1
            else:
                break
        A_cand[N-i-1] = cnt
        skip_loop = cnt
    print(ans)
    

solve()
### BUGGY CODE ###

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

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    dpi3, dpi2, dpi1, dpi = dp[i - 3:i + 1]
    for j in range(-(i // 2), i + 1):
        tmp = dpi3[j] * i12
        tmp += dpi2[j + 1] * (i - 1)
        tmp += dpi1[j - 1]
        dpi[j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)


### FIXED CODE ###

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

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    dpi3, dpi2, dpi1, dpi = dp[i - 3:i + 1]
    for j in range(-(i // 2), i + 1):
        tmp = dpi3[j] * i12
        tmp += dpi2[j + 1] * (i - 1)
        tmp += dpi1[j - 1]
        dpi[j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)
### BUGGY CODE ###

import itertools
n=(int)(input())
moji = []
s=input()
for i in itertools.combinations(range(n), n-3):
  t = list(s)
  #print(i)
  for j in range(n-3):
    del t[i[j]-j]
  moji.append(''.join(t))
print(len(list(set(moji))))

### FIXED CODE ###

import itertools
n=(int)(input())
moji = list('0123456789')
s=input()
count = 0

for i in itertools.product(moji, repeat=3):
  sousa = list(s)
  try:
    
    n1 = sousa.index(i[0])
    n2 = sousa[n1+1:].index(i[1])+n1+1
    n3 = sousa[n2+1:].index(i[2])+n2+1
    #print(sousa, sousa[n1+1:], sousa[n1+2:])
    count += 1
  except ValueError:
    continue
  #print(i)
  #moji.append(s[i[0]] + s[i[1]] + s[i[2]])
  #print(moji)
  
print(count)
### BUGGY CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    count = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                if (i != j and i != k and j != k and i < j < k):
                    if i+j+k == x:
                        count += 1
    print(count)

### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    count = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                if (i < j < k):
                    if i+j+k == x:
                        count += 1
    print(count)
### BUGGY CODE ###

N = int(input())
g = {}
for i in range(1, N+1):
    g[i] = []

cache = {}
def dfs(g,start,end):
    if cache.get((start,end),None) != None or cache.get((end,start),None) != None:
        return cache[(start,end)]
    stack = [(start, [start], 0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                cache[(start,end)] = length + l
                cache[(end,start)] = length + l
                return cache[(start,end)]
            else:
                stack.append((next, path + [next], length + l))

for i in range(N-1):
    a, b, c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))
Q, K = map(int,input().split())

for q in range(Q):
    x, y = map(int,input().split())
    print(dfs(g,x,K) + dfs(g,K,y))

### FIXED CODE ###

N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)

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

Q, K = map(int,input().split())

stack = [K]

while len(stack):
    v = stack.pop()
    for c,ln in g[v]:
        if l[c] != 0:
            continue
        l[c] = l[v] + ln
        stack.append(c)

for q in range(Q):
    x, y = map(int,input().split())
    print(l[x] + l[y])
### BUGGY CODE ###


n,p = list(map(int,input().split()))
s = input()

if p == 2 or p == 5:
  ans = 0
  for i,c in enumerate(s):
    if int(c)%p == 0:
      ans += i+1
  print(ans)
  exit()

S = list(map(int,[x for x in s]))
M = list(map(lambda x:x%p, S[::-1]))

MM = [0]*n
for i,m in enumerate(M):
  if i == 0:
    MM[i] = m
  else:
    MM[i] = m*10**(i) + MM[i-1]

M = list(map(lambda x:x%p, MM))

ans = 0
U = set(M)

for u in U:
  cnt = M.count(u)
  if u == 0:
    ans += (cnt*(cnt+1))//2
  else:
    ans += (cnt*(cnt-1))//2

print(int(ans))

### FIXED CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce
import copy
import numpy as np

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

def gcd_list(*numbers):
    return reduce(fractions.gcd, numbers)

temp = gcd_list(*A)
AA = list(A // temp)

temp2 = 0
for i in range(N):
    a = copy.copy(AA)
    a.pop(i)
    kouyaku = gcd_list(*a)
    temp2 = max(temp2, kouyaku)

print(temp * temp2)

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int,input().split()))
l = [0] * (N+1)
r = [0] * (N+1)

for i in range(1, N+1):
    l[i] = fractions.gcd(l[i-1], A[i-1])
for i in range(1, N+1):
    r[N-i] = fractions.gcd(r[N-i+1], A[N-i])

ans = 0
for i in range(N):
    kouyaku = fractions.gcd(l[i], r[i+1])
    ans = max(ans, kouyaku)

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

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, W):
    dp = [0] * (W + 1)
    wv = [list(map(int, input().rstrip().split())) for _ in range(n)]
    for wi, vi in wv:
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))


### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
s = [1]*(n+1)
if 1 in a:
    s[1] = 0
    
for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
    else:
        s[i+2] = (s[i+1] + s[i]) % (10**9+7)

print(s[-1])

### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])
### BUGGY CODE ###

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

A.sort()
B = [0]*N

for i in range(N):
    if B[i]:
        continue
    if i < N-1:
        if A[i] == A[i+1]:
            B[i] = 1
    x = A[i]
    for j in range(i+1, N):
        if B[j]:
            continue
        if A[j]%x == 0:
            B[j] = 1

print(N-sum(B))

### FIXED CODE ###

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

dlen = A[-1]+3
d = [True]*dlen
for a in A:
    if d[a]:
        for i in range(a*2, dlen, a):
            d[i] = False

res = 0
for i in range(N):
    if i > 0:
        if A[i] == A[i-1]:
            continue
    if i < N-1:
        if A[i] == A[i+1]:
            continue
    if d[A[i]]:
        res += 1
print(res)
### BUGGY CODE ###

import numpy as np

S = list(input())[::-1]

dp = np.array([1] + [0]*12)

nd = len(S)
for i in range(nd):
  if S[i] != '?':
    slide = (int(S[i])*(10**i)) % 13
    dp = np.r_[dp[-slide:], dp[:-slide]]
  
  else:
    new_dp = dp.copy()
    for j in range(1, 10):
      slide = int(j*(10**i)) % 13
      new_dp += np.r_[dp[-slide:], dp[:-slide]]
    
    dp = new_dp % (10**9 + 7)

print(dp[5])

### FIXED CODE ###

S = input()
S = S[::-1]
N = len(S)

mod = 10**9 + 7

dp = [[1] + [0]*12] + [[0]*13 for i in range(N)]

digit = 1
for i, s in enumerate(S):
  if s == '?':
    R = [j*digit % 13 for j in range(10)]
    for j in range(13):
      for r in R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*digit % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]
  
  digit *= 10
  digit %= 13

print(dp[-1][5])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(0,n-1):
    y = 0
    for j in range(i+1, n):
        y = y + a[j]

    x = (x + (a[i]*y) % (10**9+7)) % (10**9+7)

print(x)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
y = 0
for i in range(0,n):
    x = x + a[i]
for i in range(0,n):
    y = y + (a[i]**2)
print(((x**2-y)//2) % (10**9+7))
### BUGGY CODE ###

from bisect import bisect_right

def getINearests(ss, ts):
    iNearests = [-1] * len(ss)
    for iS, s in enumerate(ss):
        iT = bisect_right(ts, s)
        if iT == len(ts):
            iNearests[iS] = iT-1
        elif iT == 0:
            iNearests[iS] = 0
        else:
            d1 = abs(s - ts[iT-1])
            d2 = abs(s - ts[iT])
            if d1 <= d2:
                iNearests[iS] = iT-1
            else:
                iNearests[iS] = iT
    return iNearests


A, B, Q = map(int, input().split())
ss = [int(input()) for _ in range(A)]
ts = [int(input()) for _ in range(B)]
xs = [int(input()) for _ in range(Q)]

iTNearests = getINearests(ss, ts)
iSNearests = getINearests(ts, ss)

anss = [0] * Q
for iX, x in enumerate(xs):
    ans = float('inf')

    # 初手: 神社
    iS = bisect_right(ss, x)
    if iS > 0:
        cost = abs(x - ss[iS-1])
        cost += abs(ss[iS-1] - ts[iTNearests[iS-1]])
        ans = min(ans, cost)
    if iS < A:
        cost = abs(x - ss[iS])
        cost += abs(ss[iS] - ts[iTNearests[iS]])
        ans = min(ans, cost)

    # 初手: 寺
    iT = bisect_right(ts, x)
    if iT > 0:
        cost = abs(x - ts[iT-1])
        cost += abs(ts[iT-1] - ss[iSNearests[iT-1]])
        ans = min(ans, cost)
    if iT < B:
        cost = abs(x - ts[iT])
        cost += abs(ts[iT] - ss[iSNearests[iT]])
        ans = min(ans, cost)

    anss[iX] = ans

print('\n'.join(map(str, anss)))


### FIXED CODE ###

import sys
from bisect import bisect_right

def solve():
    def getINearests(ss, ts):
        iNearests = [-1] * len(ss)
        for iS, s in enumerate(ss):
            iT = bisect_right(ts, s)
            if iT == len(ts):
                iNearests[iS] = iT-1
            elif iT == 0:
                iNearests[iS] = 0
            else:
                d1 = abs(s - ts[iT-1])
                d2 = abs(s - ts[iT])
                if d1 <= d2:
                    iNearests[iS] = iT-1
                else:
                    iNearests[iS] = iT
        return iNearests


    A, B, Q = map(int, input().split())
    ss = [int(sys.stdin.readline()) for _ in range(A)]
    ts = [int(sys.stdin.readline()) for _ in range(B)]
    xs = [int(sys.stdin.readline()) for _ in range(Q)]

    iTNearests = getINearests(ss, ts)
    iSNearests = getINearests(ts, ss)

    anss = [0] * Q
    for iX, x in enumerate(xs):
        ans = float('inf')

        # 初手: 神社
        iS = bisect_right(ss, x)
        if iS > 0:
            cost = abs(x - ss[iS-1])
            cost += abs(ss[iS-1] - ts[iTNearests[iS-1]])
            if cost < ans: ans = cost
        if iS < A:
            cost = abs(x - ss[iS])
            cost += abs(ss[iS] - ts[iTNearests[iS]])
            if cost < ans: ans = cost

        # 初手: 寺
        iT = bisect_right(ts, x)
        if iT > 0:
            cost = abs(x - ts[iT-1])
            cost += abs(ts[iT-1] - ss[iSNearests[iT-1]])
            if cost < ans: ans = cost
        if iT < B:
            cost = abs(x - ts[iT])
            cost += abs(ts[iT] - ss[iSNearests[iT]])
            if cost < ans: ans = cost

        anss[iX] = ans

    print('\n'.join(map(str, anss)))

solve()
### BUGGY CODE ###

from collections import Counter

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

for i in range(1,N+1):
    print(Counter(A)[i])


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

d = defaultdict(int)

for i in A:
    d[i] += 1

for i in range(1,N+1):
    print(d[i])
### BUGGY CODE ###

n = int(input())
s = str(input())
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)
p = len(r)*len(g)*len(b)
for j in r:
    for k in g:
        for l in b:
            ls = [j,k,l]
            ls.sort()
            (a,c,d) = (ls[0],ls[1],ls[2])
            if (c-a) == (d-c):
                p -= 1
print(p)

### FIXED CODE ###

n = int(input())
s = str(input())
r = 0
g = 0
b = 0
for i in range(n):
    if s[i] == "R":
        r += 1
    elif s[i] == "G":
        g += 1
    else:
        b += 1
p = r*g*b
for i in range(n-2):
    for j in range(int(n/2)+1):
        if i + 2*j >n-1:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+2*j] != s[i+j]:
            p -= 1
print(p)
### BUGGY CODE ###

def cmb(n, r, p):
    r = min(n, n - r)
    upper = 1
    for i in range(n, n - r, -1):
        upper = (upper * i) % p

    lower = 1
    for i in range(1, r + 1):
        lower = (lower * i) % p

    return (upper * pow(lower, p - 2, p)) % p

mod = pow(10, 9) + 7
n, a, b = map(int, input().split())
ans = (pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)) % mod
print(ans)

### FIXED CODE ###

MOD = pow(10, 9) + 7

def modinv(a, mod):
    return pow(a, mod - 2, mod) % mod

def comb(n, r, mod):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) % mod
        res = res * modinv(i + 1, mod) % mod
    return res

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

ans = (pow(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)) % MOD

print(ans)