Harryxun/stf_run huggingface dataset:
import math
import scipy
def I():
  return input()
def II():
  return int(input())
def MII():
  return map(int, input().split())
def LMII():
  return list(map(int, input().split()))
n,a,b = MII()
print(2**n-1-scipy.misc.comb(n,a)-scipy.misc.comb(n,b))

### FIXED CODE ###

import math
MOD = 10**9+7
def modpow(a, n, p):
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p

def I():
  return input()
def II():
  return int(input())
def MII():
  return map(int, input().split())
def LMII():
  return list(map(int, input().split()))
n,a,b = MII()
fact_a = 1
fact_n_a = 1
fact_b = 1
fact_n_b = 1
for i in range(a):
    fact_a = fact_a * (i+1) % MOD
    fact_n_a = fact_n_a * (n-a+1+i) % MOD
cmb_a = fact_n_a * modpow(fact_a, MOD-2, MOD) % MOD
for i in range(b):
    fact_b = fact_b * (i+1) % MOD
    fact_n_b = fact_n_b * (n-b+1+i) % MOD
cmb_b = fact_n_b * modpow(fact_b, MOD-2, MOD) % MOD

print((modpow(2, n, MOD)-1-cmb_a-cmb_b)%MOD)
#coding:utf-8
a = int(input('a = '))

if a == 25:
	print "Christmas"
if  a == 24:
	print "Christmas Eve"
if  a == 23:
	print "Christmas Eve Eve"
if a==22:
	print "Christmas Eve Eve Eve"

### FIXED CODE ###

#coding:utf-8
a = int(input())

if a == 25:
	print('Christmas')
if a == 24:
	print('Christmas Eve')
if a == 23:
	print('Christmas Eve Eve')
if a==22:
	print('Christmas Eve Eve Eve')
s = input()
print('Yes' if s[0]!=s[1]&&s[1]!=s[2]&&s[0]!=s[2] else 'No')

### FIXED CODE ###

s = input()
print('Yes' if s[0]!=s[1] and s[1]!=s[2] and s[0]!=s[2] else 'No')
n=int(input())
print(int(n*(n-1)/2))

### FIXED CODE ###

s=input()
t=input()
c = 0
for i in range(3):
    if s[i]==t[i]:
        c+=1
print(c)
A=int(input(" enter no of apples")
P=int(input(" enter no of peices ")
n=A*3
pe=n+P
apple=pe//2
print(apple)

### FIXED CODE ###

A, P = map(int, input().split())
P += A * 3
print(int(P / 2))
#ARC068C

n=int(raw_input())
if x<=6:
 print 1
else:
 res=n/11*2
 if n%11>=6:
  res+=2
 else:
  res+=1
 print res


### FIXED CODE ###

#ARC068C

n=int(raw_input())

res=n/11*2
ref=n%11
if ref==0:
 print res
elif ref<=6:
 print res+1
else:
 print res+2
from collections import defaultdict

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

d = defaultdict(list)
class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self,rank,parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor == parent:
                continue
            neighbor.set_rank(rank=rank+1,parent=self)



trees = {i:Tree(i) for i in range(1,N+1)}

for a,b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
trees[1].set_rank(1,None)

group0 = [node.v for node in  trees.values() if node.rank %2 ==0]
group1 = [node.v for node in  trees.values() if node.rank %2]
x = [set(),set(),set()]
for i in range(1,N+1):
    x[i%3].add(i)
if len(group1) < len(group0):
    group1,group0 = group0,group1

result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()]= x[0].pop()
    y = x[0]|x[1]|x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
    if y:
        import time
        time.sleep(10)
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()


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



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]


class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self, rank, parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor is parent:
                continue
            neighbor.set_rank(rank=rank + 1, parent=self)


trees = {i: Tree(i) for i in range(1, N + 1)}

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

print(' '.join(str(result[i]) for i in range(1, N + 1)))
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def make_codivisors(n):
    divisors = []
    n0divisors = make_divisors(n[0])
    n0len = len(n0divisors)
    for i in n0divisors:
        for j in range(1, len(n)):
            if n[j] % i != 0:
                break
            if j == len(n)-1:
                divisors.append(i)
            
    # divisors.sort()
    return max(divisors)


n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
a.append(x)
a.sort()
b = [a[i]-a[i-1] for i in range(1, n+1)]

#print(b)
#print(a)

print(make_codivisors(b))

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def make_codivisors(n):
    divisors = []
    n0divisors = make_divisors(n[0])
    n0len = len(n0divisors)
    for i in n0divisors:
        for j in range(1, len(n)):
            if n[j] % i != 0:
                break
            if j == len(n)-1:
                divisors.append(i)
            
    # divisors.sort()
    return max(divisors)


n, x = list(map(int, input().split()))
a = list(map(int, input().split()))
a.append(x)
a.sort()
b = [a[i]-a[i-1] for i in range(1, n+1)]

#print(b)
#print(a)
if len(b) >= 2:
  print(make_codivisors(b))
else:
  print(b[0])
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])
    # l <= i < r
    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    def func(a, b):
        if a >= b:
            return a
        return b
    s = SegTree(A, func)
    d = {}
    for i in range(N):
        t = s.query(i+1, N) - A[i]
        d[t] = d.get(t, 0) + 1
    m = 0
    for i in d:
        if i > m:
            m = i
    return d[m]
print(main())


### FIXED CODE ###

class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])
    # l <= i < r
    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s
def main():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    if N == 2:
        return 1
    def func(a, b):
        if a >= b:
            return a
        return b
    s = SegTree(A, func)
    d = {}
    for i in range(N):
        t = s.query(i+1, N) - A[i]
        d[t] = d.get(t, 0) + 1
    m = 0
    for i in d:
        if i > m:
            m = i
    return d[m]
print(main())
n, k = [int(z) for z in input().strip().split()]
p = [int(z) - 1 for z in input().strip().split()]
c = [int(z) for z in input().strip().split()]

visited = [False for _ in range(n)]
cycle = []
for start in range(n):
    if visited[start]:
        continue
    now = start
    route = []
    while not visited[now]:
        visited[now] = True
        route.append(now)
        now = p[now]
    cycle.append(route)

min_c = min(c)
max_value = min_c
for route in cycle:
    full_value = sum([c[i] for i in route])
    double_route = route + route
    v = [c[i] for i in double_route]
    max_sum_step = []
    for step in range(1, len(route)):
        s = sum(v[:step])
        max_sum = max(s, min_c)
        for idx in range(step, step + len(route) - 1):
            s += v[idx]
            if idx >= step:
                s -= v[idx - step]
            max_sum = max(s, max_sum)
        max_sum_step.append(max_sum)
    addition = k % len(route)
    if full_value > 0:
        value1 = int(k / len(route)) * full_value + max(max_sum_step[:addition])
        value2 = (int(k / len(route)) - 1) * full_value + max(max_sum_step)
        value = max(value1, value2)
    else:
        value = max(max_sum_step[:min(k, len(max_sum_step))])
    max_value = max(max_value, value)
print(max_value)


### FIXED CODE ###

n, k = [int(z) for z in input().strip().split()]
p = [int(z) - 1 for z in input().strip().split()]
c = [int(z) for z in input().strip().split()]
 
visited = [False for _ in range(n)]
cycle = []
for start in range(n):
    if visited[start]:
        continue
    now = start
    route = []
    while not visited[now]:
        visited[now] = True
        route.append(now)
        now = p[now]
    cycle.append(route)
 
min_c = min(c)
max_value = min_c
for route in cycle:
    full_value = sum([c[i] for i in route])
    double_route = route + route
    v = [c[i] for i in double_route]
    max_sum_step = []
    for step in range(1, len(route)):
        s = sum(v[:step])
        max_sum = max(s, min_c)
        for idx in range(step, step + len(route) - 1):
            s += v[idx]
            if idx >= step:
                s -= v[idx - step]
            max_sum = max(s, max_sum)
        max_sum_step.append(max_sum)
    addition = k % len(route)
    if full_value > 0:
        addition_value = 0 if addition == 0 else max(max_sum_step[:addition])
        value1 = int(k / len(route)) * full_value + addition_value
        value2 = (int(k / len(route)) - 1) * full_value + max(max_sum_step)
        value = max(value1, value2)
    else:
        value = max(max_sum_step[:min(k, len(max_sum_step))])
    max_value = max(max_value, value)
print(max_value)
import numpy as np

n, m, c = map(int, input().split())
array = np.array(list(map(int,input().split())))
nm = []
for _ in range(n):
    _ = list(map(int,input().split()))
    nm.append(_)

count = 0
for _ in nm:
    if np.inner(array, _)+c>0:
        count += 1
print(count)

### FIXED CODE ###

import numpy as np

n, m, c = map(int, input().split())
array = np.array(list(map(int,input().split())))
nm = []
for _ in range(n):
    _ = list(map(int,input().split()))
    nm.append(_)

count = 0
for _ in nm:
    if np.inner(array, _)+c>0:
        count += 1
print(count)
N, M = open(0).readline().split()
from collections import Counter
cnt = Counter(open(0).read().split())
print('\n'.join(list(map(str,cnt.values()))))

### FIXED CODE ###

N, M, *cnt = open(0).read().split()
from collections import Counter
cnt = Counter(cnt)
for i in range(1,int(N)+1):
    print(cnt[str(i)])
from bisect import bisect_left
n,m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if v >= p:
    l, r = -1, n - p - 1
    while r - l > 1:
        flg = 0
        med = (l + r) // 2
        t = (v - p) * m
        for i in range(n - p + 1):
            if a[med] + m < a[i]:
                flg = 1
                break
        for i in range(n - p + 1):
            if i == med:
                continue
            t -= min(m, a[med] + m - a[i])
        if t > 0:
            flg = 1
        if flg:
            l = med
        else:
            r = med
    print(n - r)
else:
    exit(1)
    print(n - bisect_left(a,a[n - p] - m))


### FIXED CODE ###

from bisect import bisect_left
n,m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if v >= p:
    l, r = -1, n - p
    while r - l > 1:
        flg = 0
        med = (l + r) // 2
        t = (v - p) * m
        for i in range(n - p + 1):
            if a[med] + m < a[i]:
                flg = 1
                break
        for i in range(n - p + 1):
            if i == med:
                continue
            t -= min(m, a[med] + m - a[i])
        if t > 0:
            flg = 1
        if flg:
            l = med
        else:
            r = med
    print(n - r)
else:
    print(n - bisect_left(a,a[n - p] - m))
N = int(input())
count = 0
answer = 0
for x in range(1,N+1,2):
    for i in range(1,x+1):
        if x % i == 0:
            count += 1
    if count == 8:
        answer +=1
    count = 0
print (answer)

### FIXED CODE ###

b, c = map(int, input().split())
print ((b-1)*(c-1))
s=input()
n=len(s)
a=0
i=0
p=s[0]
while i<n-1:
  if s[i+1]==p:
    i+=2
  else:
    if i==n-2:a+=1
    i+=1
  a+=1
  p=s[i]
print(a)

### FIXED CODE ###

from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

s=StoI()
n=len(s)
dp=[[0]*n for i in range(2)]

for i in range(n):
    if i==0:
        dp[0][i]=1
    elif i==1:
        if s[1]==s[0]:
            dp[0][i]=0
            dp[1][i]=1
        else:
            dp[0][i]=2
            dp[1][i]=1
    else:
        if s[i]==s[i-1]:
            dp[0][i]=dp[1][i-1]+1
            dp[1][i]=max(dp[0][i-2],dp[1][i-2])+1
        else:
            dp[0][i]=max(dp[0][i-1],dp[1][i-1])+1
            dp[1][i]=max(dp[0][i-2],dp[1][i-2])+1

ans=max(dp[0][n-1],dp[1][n-1])
print(ans)
#coding:utf-8
from scipy.special import comb

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


for i in range(k):
    # 赤と赤の間に青を配置する場所の組み合わせ
    blue = comb(n-k+1, i+1, exact=True)
    # 青をいくつずつ配置するかの組み合わせ
    blue_num = comb(k-1, i, exact=True)
    ans = blue * blue_num % (10 ** 9 + 7)
    print(ans)


### FIXED CODE ###

#coding:utf-8
from scipy.misc import comb

n, k = map(int, input().split())
m = pow(10,9) + 7

for i in range(k):
    # 赤と赤の間に青を配置する場所の組み合わせ
    blue = comb(n-k+1, i+1, exact=True)
    # 青をいくつずつ配置するかの組み合わせ
    blue_num = comb(k-1, i, exact=True)
    print(blue * blue_num % m)
from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return P(n, n)

X, Y = map(int, input().split())
L, S = max(X, Y), min(Y, X)
if (S-(L-S))%3 != 0:
  print(0)
else:
  s = (S-(L-S))//3
  l = (S-(L-S))//3+(L-S)
  bunshi = factorial(s+l)
  bunbo = (factorial(s)*factorial(l))%mod
  print((bunshi*pow(bunbo,mod-2, mod))%mod)
  
  

### FIXED CODE ###

from functools import reduce
mod = 10**9+7

def P(n, k):
  return reduce(lambda x, y:x*y%mod, range(n-k+1, n+1))

def factorial(n):
  return P(n, n)

def C(n, k):
  k = min(k, n-k)
  if k == 0:
    return 1
  else:
    return (P(n, k)*pow(factorial(k), mod-2, mod))%mod

X, Y = map(int, input().split())
if (X+Y)%3 == 0:
  n = Y-(X+Y)//3
  m = X-(X+Y)//3
  if n < 0 or m < 0:
    print(0)
  else:
    print(C(n+m, n))
else:
  print(0)
def main():
    operator={
        "+":lambda x,y: x + y,
        "-":lambda x,y: x - y,
        "*":lambda x,y: x * y,
        "/":lambda x,y: x / y,
    }
while True:
    a,op,b=input().split()
    if op == "?":
        break
    print("d".format(opertor[op](int(a),int(b))))

if __name__=='__main__':
    main()


### FIXED CODE ###

while True:
  a,op,b = input().split()
  a=int(a)
  op=str(op)
  b=int(b)
  
  if op=='?':
    break
  elif  op=='+':
    print("{:d}".format(a+b))
  elif op=='-':
    print("{:d}".format(a-b))
  elif op=='/':
    print("{:d}".format(a//b))
  elif op=="*":
    print("{:d}".format(a*b))
K = int(input())
S =input()

def cmb(n,r,p):
    if(r<0) or (n<r):
        return 0
    r = min(r,n-r)
    return fact[n]*factinv[r]*factinv[n-r]%p

p = 10 ** 9 + 7
N = 10**6+3
fact = [1] * ( N + 3)
factinv = [1] * (N + 3)
inv = [0]* (N + 3)
inv[1] = 1

for i in range(2,N+1):
    fact[i] = fact[i-1] * i % p
    inv[i] = p-inv[p % i] * (p//i) % p
    factinv[i] = factinv[i-1] * inv[i] % p

def powmod(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n>>=1
    return res

ss = len(S)
ans = 0
k = 1;
for i in range(K+1):
    ans += cmb(ss+K-i-1,ss-1,p) * k * powmod(25,K-i,p)
    ans %= p
    k = k * 26 % p

print(ans)

### FIXED CODE ###

K = int(input())
S =input()

def cmb(n,r,p):
    if(r<0) or (n<r):
        return 0
    return fact[n]*factinv[r]*factinv[n-r]%p

p = 10 ** 9 + 7
N = 2 * 10**6+3
fact = [1] * ( N + 3)
factinv = [1] * (N + 3)
inv = [0]* (N + 3)
inv[1] = 1

for i in range(2,N+1):
    fact[i] = fact[i-1] * i % p
    inv[i] = p-inv[p % i] * (p//i) % p
    factinv[i] = factinv[i-1] * inv[i] % p

def powmod(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n>>=1
    return res

ss = len(S)
ans = 0
k = 1;
for i in range(K+1):
    ans += cmb(ss+K-i-1,ss-1,p) * k * powmod(25,K-i,p)
    ans %= p
    k = k * 26 % p

print(ans)
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
S = sum(A)
for i in range(P-1):
    x = A.pop()
    S -= x
total_score = M*(V-P+1)
kazu = N - P + 1
for i in range(N-P+1):
    a = A.pop(0)
    total_score -= M
    S -= a
    kazu -= 1
    T = (M+a)*kazu - S
    if (a+M) > A[-1]:
        if T >= total_score:
            ans = kazu + P
            break
print(ans)

### FIXED CODE ###

N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
S = sum(A)
for i in range(P-1):
    x = A.pop()
    S -= x
total_score = M*(V-P+1)
kazu = N - P + 1
for i in range(N-P+1):
    a = A.pop(0)
    total_score -= M
    S -= a
    kazu -= 1
    T = (M+a)*kazu - S
    if i == N - P:
        ans = P
    else:
        if (a+M) >= A[-1]:
            if T >= total_score:
                ans = kazu + P
                break
print(ans)
from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(n)
single = 0
for a in reversed(aaa):
    single += bit.sum(a - 1)
    bit.add(a, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)


### FIXED CODE ###

from collections import Counter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
bit = Bit(2001)
single = 0
for a in reversed(aaa):
    single += bit.sum(a)
    bit.add(a + 1, 1)
ans = single * k % MOD
coef = k * (k - 1) // 2 % MOD
cnt = Counter(aaa)
before = 0
for a, c in sorted(cnt.items()):
    ans = (ans + c * before * coef) % MOD
    before += c
print(ans)
n = int(input())
nums = list(map(int,input().split()))

l = [0]*200001

for num in nums:
    l[num] += 1

if max(l) == 1:
    print('YES')

else:
    print('NO')

### FIXED CODE ###

n = int(input())
nums = list(map(int,input().split()))
c = 0
nums = sorted(nums)

for i in range(n-1):
    if nums[i] == nums[i+1]:
        c += 1
        break
    
if c != 0:
    print('NO')

else:
    print('YES')
from math import sqrt

i = input().sqlit()
a = i[0]
b=i[1]

n = int(a+b)
s = int(sqrt(n))
if s*s==n :
	print("Yes")
else:
	print("No")

### FIXED CODE ###

import math
string = input().split(" ")
number = int(string[0]+string[1])
result = math.sqrt(number)
if int(result)*int(result) == number:
    print("Yes")
else:
    print("No")
k=int(input())
a,b=list(map(int,input().split()))
while True:
  x+=k
  if a<=x<=b:
    print('OK')
    break
  if x>b:
    print('NG')
    break

### FIXED CODE ###

k=int(input())
a,b=list(map(int,input().split()))
x=0
while True:
  x+=k
  if a<=x<=b:
    print('OK')
    break
  if x>b:
    print('NG')
    break