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

from math import factorial

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

fact=[factorial(i) for i in range(n)]
s=0
#maxについて
for i in range(k-1,n):
	s+=a[i]*fact[i]//fact[k-1]//fact[i-k+1]
	s%=10**9+7
for i in range(n-k+1):
	s-=a[i]*fact[n-i-1]//fact[k-1]//fact[n-k-i]
	s%=10**9+7
print(s)

### FIXED CODE ###

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
    
n,k=map(int,input().split())
a=sorted(list(map(int, input().split())))
MOD=10**9+7

fac, ifac=make_tables(MOD,n)

s=0
for i in range(k-1,n):
	s+=(a[i]-a[n-i-1])*cmb(i,k-1,MOD,fac,ifac)
	s%=10**9+7
print(s)
### BUGGY CODE ###

import math
N = (int(input()))
items = list(map(int,input().split()))
for i in range(len(items)):    
    rest = items[:i] + items[i+1:]
    rest_unique = list(set(rest))
    out = 0
    for j in rest_unique:
        cnt = sum([1 for x in rest if x == j])
        if cnt >= 2:
            out = out + math.factorial(cnt)/math.factorial(cnt-2)/2
    print(int(out))

### FIXED CODE ###

import math
input()
items = list(map(int,input().split()))
d = {}
for i in items:
    if i in d.keys():
        d[i] = d[i]+1
    else:
        d[i] = 1

p = {}
for k in d.keys():
    cnt = d[k]
    p[k] = (cnt*(cnt-1))/2

total = sum(p.values())

for item in items:
    print(int(total - d[item] + 1))
### BUGGY CODE ###

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

list = 0
for i in range(N-K+1):
    p = pn[i:i+K]
    list = max(list, sum(p))

ans = (list+K)/2
print(ans)


### FIXED CODE ###

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
c = 0
B = []
C = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        B.append(b)
    elif b == n:
        C.append(a)
for i in B:
    if i in C:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

import collections
n, m = map(int, input().split())
c = 0
B = []
C = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        B.append(b)
    elif b == n:
        B.append(a)
C = collections.Counter(B)
for i in C:
    if C[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(raw_input())
x = [0 for i in range(n)]
pf = 0
pb = 0

li = []
for i in range(n):
    s = (raw_input().split())
    if s[0] == 'insert':
        pf += 1
        x[pf]=int(s[1])
    elif s[0] == 'delete':
        try:
            p = x[pf::-1].index(int(s[1]))
            x[pf-p] = 0
            while x[pf]==0:
                pb -= 1
            while x[pb]==0:
                pb += 1
        except:
            pass
    elif s[0] == 'deleteFirst':
        x[pf]=0
        pf -= 1
    elif s[0] == 'deleteLast':
        x[pb] = 0
        pb += 1
for e in x[pb:pf+1][::-1]:
    if e != 0:
        print e,

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
set_a=list(set(a))
a_4=[]
for i in set_a:
    if a.count(i)==1:
        a.remove(i)
    if 4<=a.count(i):
        a_4.append(i)
        a.remove(i)
if len(a)==0:
    print(0)
    exit()
a=list(set(a))
a.sort()
a.reverse()
a_4.sort()
a_4.reverse()
v=0
x=0
z=0
if 1<=len(a_4):
    v=a_4[0]*a_4[0]
if 1<=len(a):
    x=a[0]*a[1]
if 1<=len(a) and 1<=len(a_4):
    z=a[0]*a_4[0]
print(max(v,x,z))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
from collections import Counter
data=Counter(a)
two_i=[]
four_i=[]
for i,j in data.items():
    if 4<=j:
        four_i.append(i)
    elif 2<=j:
        two_i.append(i)
two_i.sort()
four_i.sort()
two_i.reverse()
four_i.reverse()
if len(four_i)==0:
    four_i.append(0)
if len(two_i)<=1:
    two_i.append(0)
    two_i.append(0)
four_area=four_i[0]*four_i[0]
two_area=two_i[0]*two_i[1]
mix_area=two_i[0]*four_i[0]
print(max(four_area,two_area,mix_area))
### BUGGY CODE ###

import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
index = 0
answer = []
while(Q > 0):
    lr = [int(i) for i in input().split()]
    l = lr[0]
    r = lr[1]
    new_str = S[l-1:r]
    answer.append(len(re.findall("AC",new_str)))
    Q -= 1
    index += 1

index2 = 0
while(index > 0):
    print(answer[index2])
    index2 += 1
    index -= 1

### FIXED CODE ###

import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
LR = [[int(i) for i in input().split()] for j in range(Q)]
check = [0] * N
for i in range(N - 1):
    check[i + 1] = check[i] + (1 if S[i:i + 2] == "AC" else 0)


for j in range(Q):
    print((check[LR[j][1] - 1]) - (check[LR[j][0] - 1]))
### BUGGY CODE ###

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

dp = [[0] * (n+1) for _ in range(n+1)]

for length in range(1, n + 1):
    for i in range(n - length + 1):
        j = i + length

        if ((n - length) % 2 == 0):
            dp[i][j] = max(dp[i+1][j] + arr[i], dp[i][j-1] + arr[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - arr[i], dp[i][j-1] - arr[j-1])


print(dp[0][n])


### FIXED CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))
### BUGGY CODE ###

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

ans_index = 0
max_sum = 0
for i in range(len(dices) - K + 1):
    summation = 0
    for j in range(K):
        summation += dices[i + j]
    if max_sum < summation:
        max_sum = summation
        ans_index = i

ans = 0
for dice in dices[ans_index:ans_index + K]:
    ans += sum(list(range(1, dice + 1))) / dice
print(ans)

### FIXED CODE ###

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

dices = list(map(int, input().split()))

# 期待値は(1+P)/2 https://rikeilabo.com/sum-formula-of-numerical-sequence
# 累積和を求めておく．隣接するK個の和はS_{j+K} - S_j
# 期待値の前計算→累積和の計算→隣接するK項の和の計算 (１乗オーダー)
E_list = []
for dice in dices:
    E_list.append((1 + dice) * 0.5)

S_list = []  # i番目までのサイコロの期待値の累積和
for i in range(len(dices)):
    # S_list.append(sum(E_list[:i + 1]))  # アホ
    S_list.append(E_list[0] if i == 0 else S_list[i - 1] + E_list[i])

print(max(list(S_list[j + K] - S_list[j] for j in range(len(dices) - K))) if len(dices) != K else S_list[-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append([h-1, w-1])
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    for i in maxhindex:
        for j in maxwindex:
            if [i, j] not in bombs:
                print(ans)
                exit()

    print(ans-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append(tuple([h-1, w-1]))
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    bombs = set(bombs)
    for i in maxhindex:
        for j in maxwindex:
            if (i, j) not in bombs:
                print(ans)
                exit()

    print(ans-1)

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

import sys
sys.setrecursionlimit(10**7)

def dfs(x, y):
    cnt = 0
    if x == xn and y == yn:
        return 1
    if x+1 > xn or y+1 > yn:
        return 0
    cnt += dfs(x+1,y+2)
    cnt += dfs(x+2,y+1)
    return cnt


xn,yn=map(int, input().split())
print(dfs(0,0)%(10**9+7))


### FIXED CODE ###

from numpy.linalg import solve


def COM(n, r):
    fac = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    for i in range(2, MAX):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(-inv[MOD % i] * (MOD // i))
        finv.append(finv[i - 1] * inv[i] % MOD)
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD


MOD = 10 ** 9 + 7
MAX = 10**6
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
    exit(0)
l = solve([[2, 1], [1, 2]], [x, y])
if l[0] < 0 or l[1] < 0:
    print(0)
    exit(0)
print(COM(int(l[0]+l[1]), int(l[0])))
### BUGGY CODE ###

L,R = list(map(int, input().split()))


MOD=[0] * (2019*2019)

def myidx(i,j):
    return i * 2019 + j

for i in range(2019):
    for j in range(2019):
        idx = myidx(i,j)
        MOD[idx] = (i*j) % 2019

for i in range(2019):
    idx = myidx(i,i)
    MOD[idx] = 2019

MMM = []

if L+2019 <= R:
    MMM = MOD

Lmod = L % 2019
Rmod = R % 2019
if Lmod <= Rmod:
    for i in range(Lmod, Rmod+1):
        for j in range(i+1, Rmod+1):
            idx = myidx(i,j)
            MMM.append(MOD[idx])

if Lmod > Rmod:
    for i in list(range(0,Rmod+1)) + list(range(Lmod, 2019)):
        for j in list(range(i+1,Rmod+1)) + list(range(i+1, 2019)):
            idx = myidx(i,j)
            MMM.append(MOD[idx])

MMM.sort()
print(MMM.pop(0))


### FIXED CODE ###

L,R = list(map(int, input().split()))

MOD=[0] * (2019*2019)

def myidx(i,j):
    return i * 2019 + j

for i in range(2019):
    for j in range(i+1,2019):
        idx = myidx(i,j)
        MOD[idx] = (i*j) % 2019

#for i in range(2019):
#    idx = myidx(i,i)
#    MOD[idx] = 2019

MMM = []
MIN = 2019
Lmod = L % 2019
Rmod = R % 2019

if L+2019 <= R:
    for i in range(2019):
        for j in range(i+1,2019):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])
elif Lmod <= Rmod:
    for i in range(Lmod, Rmod+1):
        for j in range(i+1, Rmod+1):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])

elif Lmod > Rmod:
    for i in list(range(0,Rmod+1)) + list(range(Lmod, 2019)):
        for j in list(range(i+1,Rmod+1)) + list(range(max(Lmod,i+1), 2019)):
            idx = myidx(i,j)
            MIN = min(MIN, MOD[idx])
            #MMM.append(MOD[idx])

#MMM=list(set(MMM))
#MMM.sort()
#print(MMM.pop(0))
print(MIN)
### BUGGY CODE ###

import copy

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

tmp = copy.deepcopy(s)
wait = 0
last_day = k
count = []

for num, i in enumerate(tmp):
    if last_day == 0:
        break
    if wait>0:
        wait -= 1
        continue
    if i == 'o':
        s[num] = 'a'
        count.append(num)
        wait = c
        last_day -= 1

# print(count)        
ans = []    
for j in count:
    if s[j] =='o':
        continue
    wait = 0
    tmp = copy.deepcopy(s)
    last_day = k
    tmp[j] = 'x'
    for num, i in enumerate(tmp):
        if last_day == 0:
            break
        if wait>0:
            if i == 'a':
                tmp[num] = 'o'
            wait -= 1
            continue
        if i == 'o' or i == 'a':
            wait = c
            last_day -= 1
    if last_day > 0:
        ans.append(j+1)
    else:
        s = copy.deepcopy(tmp)
        
for i in ans:
    print(i)

### FIXED CODE ###

import copy

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

tmp = copy.deepcopy(s)
wait = 0
last_day = k
count = set()

for num, i in enumerate(tmp):
    if wait>0:
        wait -= 1
        continue
    if i == 'o':
        count.add(num)
        wait = c
        last_day -= 1
        if last_day == 0:
            break

tmp = copy.deepcopy(s)
wait = 0
last_day = k
count2 = set()
for num, i in enumerate(reversed(tmp)):
    if wait>0:
        wait -= 1
        continue
    if i == 'o':
        count2.add(n - num - 1)
        wait = c
        last_day -= 1
        if last_day == 0:
            break

count = list(count)
count2 = list(count2)
count.sort()
count2.sort()
ans = []
for i in range(len(count)):
    if count[i]==count2[i]:
        ans.append(count[i]+1)

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

M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
A=[x for x in set(A) if A.count(x) == 1]
s=set(k) & set(A)
print(len(s))

### FIXED CODE ###

M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print(1)
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print(len(s))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
f={}
x=1
for i in range(n):
    f[x]=l[i]
    x+=1
    
ans=0   
for i in range(n):
    flag=1
    for j in range(i):
        if l[i]>l[j]:
            flag=0
    if flag:
        ans+=1
        
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
f={}
x=1
   
ans=n
min=l[0]
c=0
for i in range(n):
    if l[i]<=min:
        #ans+=1
        min=l[i]
    else:
        c+=1
        #print(l[i])
        
    #print(min)
    
print(ans-c)
### BUGGY CODE ###

s = str(input())
L = len(s)
dict = [0] * 2019
dict[0] += 1
for i in range(L):
  amari = (int(s[i:])) % 2019
  dict[amari] += 1
ans = 0
for j in range(2019):
  ans += (dict[j]*(dict[j]-1))/2
print(int(ans))

### FIXED CODE ###

s = str(input())
L = len(s)
dict = [0] * 2019
dict[0] += 1
num = 0
for i in range(L-1, (-1), (-1)):
    num += (int(s[i]) * pow(10,(L-i-1), 2019))%2019
    amari = num % 2019
    dict[amari] += 1
ans = 0
for j in range(2019):
    ans += (dict[j]*(dict[j]-1))/2
print(int(ans))
### BUGGY CODE ###

#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1  = [] 
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    lst1.append(int(Decimal(s)*(10**9)))

dp = [[0]*20 for _ in range(50)]

ans = 0

for i in range(n):
    res = lst1[i]
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    for i in range(18-t,50):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)


### FIXED CODE ###

#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1  = [] 
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    lst1.append(int(Decimal(s)*(10**9)))

dp = [[0]*20 for _ in range(45)]

ans = 0

for i in range(n):
    res = lst1[i]
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    for i in range(18-t,45):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

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

import re
n = input().split()
N = int(n[0])
Q = int(n[1])
S = input()

for i in range(Q):
    lr = input().split()
    tmp = S[int(lr[0])-1:int(lr[1])]
    j = -1
    for j, m in enumerate(re.finditer('AC', tmp)):
        pass
    j += 1
    print(str(j))




### FIXED CODE ###

from itertools import accumulate

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

tmp = []
for i in range(N-1):
    tmp_S  = S[i:i+2]
    if tmp_S == 'AC':
        tmp.append(1)
    else:
        tmp.append(0)

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))
#print(tmp2)

for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, p = map(int, input().split())
s = input()

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + i + 1
    print(ret)
else:
    c_list = [0] * n
    power = 1
    for i in range(len(s)):
        c_list[i] = (c_list[i-1] + (int(s[-i-1]) * power)) % p
        power *= 10
    c_list.append(0)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, p = map(int, input().split())
s = input()

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + i + 1
    print(ret)
else:
    c_list = [0] * n
    power = 1
    for i in range(len(s)):
        c_list[i] = (c_list[i-1] + (int(s[-i-1]) * power)) % p
        power *= 10
        power = power % p
    c_list.append(0)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)
### BUGGY CODE ###

import itertools

n = int(input())
list_score = list(map(int, input().split()))
list_score.sort()
p_list = list(itertools.combinations(list_score, 3))
a = len(p_list)
ans = 0

for i in range(a):
    if p_list[i][0] + p_list[i][1] > p_list[i][2]:
       ans += 1

print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
list_L = list(map(int, input().split()))
list_L.sort()
ans = 0

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

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

#142c
N = int(input())
A_list = list(map(int, input().split()))

#高橋くんは N人の生徒たちのいるクラスの担当教師です。
#生徒たちには 1から Nまでの出席番号が重複なく割り当てられています。
#今日は全ての生徒たちが相異なるタイミングで登校しました。
#高橋くんは、出席番号 iの生徒が登校した時点で、教室に Ai 人の生徒たちがいたことを記録しています(出席番号 iの生徒を含む)。
#記録された情報を元に、生徒たちの登校した順番を復元してください。

#出力 生徒たちの出席番号を登校した順に出力せよ。

#8
#出席番号
#1 2 3 4 5 6 7 8
#登校時の人数
#8 2 7 3 4 5 6 1

#8 2 4 5 6 7 3 1

print(' '.join(map(str, [A_list.index(i)+1 for i in range(1,N+1)])))

### FIXED CODE ###

#142c
N = int(input())
A_list = list(map(int, input().split()))

#高橋くんは N人の生徒たちのいるクラスの担当教師です。
#生徒たちには 1から Nまでの出席番号が重複なく割り当てられています。
#今日は全ての生徒たちが相異なるタイミングで登校しました。
#高橋くんは、出席番号 iの生徒が登校した時点で、教室に Ai 人の生徒たちがいたことを記録しています(出席番号 iの生徒を含む)。
#記録された情報を元に、生徒たちの登校した順番を復元してください。

#出力 生徒たちの出席番号を登校した順に出力せよ。

#8
#出席番号
#1 2 3 4 5 6 7 8
#登校時の人数
#8 2 7 3 4 5 6 1

#8 2 4 5 6 7 3 1

index_list = [i for i in range(1,N+1)]
class_dict = dict(zip(A_list,index_list))

#print(' '.join(map(str, [A_list.index(i)+1 for i in range(1,N+1)])))

class_sorted = sorted(class_dict.items(),key=lambda x:x[0])
ans = [i[1] for i in class_sorted]
print(' '.join(map(str, ans)))
### BUGGY CODE ###

def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    flg = 0
    for i in range(n-1):
        if a[i]==0:
            continue
        for j in range(i+1,n):
            if a[j]==a[i]:
                flg = 1
            if a[j]%a[i]==0:
                a[j] = 0
        if flg == 1:
            a[i] = 0
            flg = 0
    ans = 0
    for i in range(n):
        if a[i]!=0:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [-1 for i in range(a[-1])]
    for i in range(n):
        if dp[a[i]-1]==-1:
            dp[a[i]-1]=1
            for j in range(2,a[-1]//a[i]+1):
                dp[a[i]*j-1]=0
        elif dp[a[i]-1]==1:
            dp[a[i]-1]=0
    ans = 0
    for i in range(len(dp)):
        if dp[i]==1:
            ans += 1
    print(ans)

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

def main():
    N, K = map(int, input().split())
    P = map(int, input().split())
    E = [(p+1)/2 for p in P]
    V = [sum(E[i:i+K]) for i in range(N-K+1)]
    print(max(V))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = map(int, input().split())
    E = [(p+1)/2 for p in P]
    sums = [sum(E[0:K])]
    for i in range(N-K):
        sums.append(sums[-1] - E[i] + E[i+K])
    print(max(sums))


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

L = int(input(),2)
t = 0
c = 0
ans = 0
while(L > 0):
	if L % 2 == 1:
		t = t+1
		ans *= 2
		ans += 3 ** c
	L //= 2
	c += 1
print(((ans + 2**t))%1000000007)

### FIXED CODE ###

L = input()
length = len(L)
a = 2
b = 1
c = 4
for l in L[1:]:
	if l  == '1':
		a = (a * 3) % 1000000007
		b = (b * 3) % 1000000007
		c = (c * 2) % 1000000007
	else:
		a = (a * 3 - c) % 1000000007
		b = (b * 3) % 1000000007
print((a + b)%1000000007)