Harryxun/stf_run huggingface dataset:
s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""

dp[len(s)][len(t)] = 0
for i in range(len(s)-1,-1,-1):
    for j in range(len(t)-1,-1,-1):
        if s[i] == t[j]:
            dp[i][j] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
# print(dp)
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)


### FIXED CODE ###

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)
n = int(raw_input())
ls = []
for i in range(n):
    cmd = map(str, raw_input().split())
    if cmd[0] == "insert":
        ls.insert(0, cmd[0])
    elif cmd[0] == "delete":
        ls.remove(ls.index(cmd[1]))
    elif cmd[0] == "deleteFirst":
        ls.remove(0)
    elif cmd[0] == "deleteLast":
        ls.remove(len(ls)-1)
print " ".join(map(str, ls))

### FIXED CODE ###

n = int(raw_input())
ls = []
bp = 0
for i in range(n):
	cmd = raw_input()
	if cmd[0] == "i":
		ls.append(cmd[7:])
	elif cmd[6] == " ":
		try:
			x = ls[::-1].index(cmd[7:])
			if x!=-1:
				del ls[-x-1]
		except:
			pass
	elif cmd[6] == "F":
		ls.pop()
	else:
		bp += 1

print " ".join(map(str, ls[bp:][::-1]))
import itertools
while True:
    n=raw_input()
    if n in "0":break
    try:
        k=input()
    except SyntaxError:
        break
    L=[raw_input() for i in range(int(n))]
    S=set()
    for t in itertools.permutations(L,k):
        S.add("".join(t))
    print len(S)

### FIXED CODE ###

import itertools
while True:
    n=raw_input()
    if n=="0 0":break
    else:
        k=input()
    if k==0:break
    L=[raw_input() for i in range(int(n))]
    S=set()
    for t in itertools.permutations(L,k):
        S.add("".join(t))
    print len(S)
T, X = map(int, raw_input().strip().split())
print '%.10d' % T*1./X

### FIXED CODE ###

T, X = map(float, raw_input().strip().split())
print T/X
a,b = int(input())
print("%.10f"%(a/b))

### FIXED CODE ###

a,b = map(int,input().split())
print("%.10f"%(a/b))
import math
k,a,b=map(int,input().split())
s=1:
if b-a<=2 or k-1<2:
    print(k+1)
else:
    t=max(0,math.ceil((k−(a−1))/2))
    ans=a
    k-=a-1
    if k%2==1:
        ans+=1
        k-=1
    ans+=(b-a)*k
    print(ans)


### FIXED CODE ###

import math
k,a,b=map(int,input().split())
s=1
if b-a<=2 or k-1<2:
    print(k+1)
else:
    ans=a
    k-=a-1
    if k%2==1:
        ans+=1
        k-=1
    ans+=(b-a)*(k//2)
    print(ans)
s = input()
K = int(input())


def calculate(s, k):
    if len(s) > 5:
        ignoreCriterion = ["f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
                           "y", "z"]
    else:
        ignoreCriterion = []

    length = len(s)

    objs = {}
    for i in range(1, length + 1):
        for j in range(0, length + 1 - i):
            if s[j] in ignoreCriterion:
                continue
            objs.__setitem__(s[j:j + i], True)

    s = sorted(objs.keys())

    print(s[k-1])


calculate(s, K)

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)

s = input()
K = int(input())


def calculate(str, k):
    s = sorted(list(set(str)))
    criteron = s[:k]
    objs = {}
    for index, s in enumerate(str):
        if s in criteron:
            if len(str)+1 > index + 1 + k:
                made = index + 1 + k
            else:
                made = len(str)+1
            for i in range(index+1,made):
                objs.__setitem__(str[index:i],True)

    arr = sorted(objs.keys())

    print(arr[k-1])

calculate(s, K)
(a, b) = [int(x) for x in input().split()]

di = a // b
m = a % b
df = a / b

print('{0} {1} {2:.8f}'.di, m, df))

### FIXED CODE ###

(a, b) = [int(x) for x in input().split()]

di = a // b
m = a % b
df = a / b

print('{0} {1} {2:.8f}'.format(di, m, df))
s=input()
if s[2]==s[3]&&s[4]==s[5]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s=input()
if (s[2]==s[3]) and (s[4]==s[5]):
  print("Yes")
else:
  print("No")
L,R,d = map(int, input().split())

minumum = math.ceil(L/d)
maximum = R//d

if maximum - minumum >=0:
    print(maximum - minumum+1)
else:
    print(0)

### FIXED CODE ###

import math
L,R,d = map(int, input().split())

minumum = math.ceil(L/d)
maximum = R//d

if maximum - minumum >=0:
    print(maximum - minumum+1)
else:
    print(0)
#E
H,N=map(int,input().split())
A,B=[0]*N,[0]*N
for i in range(N):
    A[i],B[i]=map(int,input().split())
    
memo=[0]*(H+10)
def dp(H):
    if H<=0:
        return 0
    else:
        if memo[H]==0:
            memo[H]=min([dp(H-A[i])+B[i] for i in range(N)])
        return memo[H]

print(dp(H))

### FIXED CODE ###

# ABC153 E Crested Ibis vs Monster
f=lambda:map(int,input().split())
H,N=f()
# dp[n][h]:=nthまでで体力をh削るときの最小魔力
INF=10**9
dp=[[INF]*(H+1) for _ in [0]*(N+1)]

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])
n = int(input())
a = list(map(int, input().split()))
print(ans)
for i in range(n):
  ans[a[i]-1] = i +1
for i in range(n):
  print(ans[i])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
  ans[a[i]-1] = i +1
for i in range(n):
  print(ans[i])
import numpy as np
n, W = map(int, input().split())
dp = np.zeros((n + 1, W + 1))

for i in range(n):
    w, v = map(int, input().split())
    dp[i + 1] = dp[i]
    if w <= W:
        dp[i + 1][w:] = np.maximum(dp[i][:W - w + 1] + v, dp[i][w:])
print(int(dp[n][W]))

### FIXED CODE ###

n, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(n + 1)]

dp[0][W] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j >= w:
            dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][W])
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N #-1なら未探索。数字はrenketuのindex
renketu = []
index = 0
def dfs(fr,cur,parent,index,li):
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
for i in range(N):
    if used[i] != -1:
        continue
    li = [i]
    used[i] = index
    dfs(fr,i,-1,index,li)
    index += 1
    renketu.append(li)
n = len(renketu)
MAX = 0
for i in range(n):
    lii = renketu[i]
    MAX = max(len(lii),MAX)
print(MAX)

            








### FIXED CODE ###

import sys
sys.setrecursionlimit(99999999)


[n,m]=list(map(int,input().split()))
friends=[]
for i in range(m):
    friends.append(list(map(int,input().split())))

tomodachi=[[]for i in range(n)]

for i in range(m):
    tomodachi[friends[i][0]-1].append(friends[i][1]-1)
    tomodachi[friends[i][1]-1].append(friends[i][0]-1)

for i in range(n):
    tomodachi[i]=list(set(tomodachi[i]))

namelist=[1 for i in range(n)]
teams=[]

def haba(x,kari,tomodachi,namelist):
    for i in range(len(tomodachi[x])):
        if namelist[tomodachi[x][i]]==1:#生き残っているなら
            kari.append(tomodachi[x][i])
            namelist[tomodachi[x][i]]=0#殺す
            haba(tomodachi[x][i],kari,tomodachi,namelist)
    return(kari)
            


for i in range(n):
    if namelist[i]==1:
        teams.append(list(set(haba(i,[i],tomodachi,namelist))))

saidai=0

for i in range(len(teams)):
    if saidai<len(teams[i]):
        saidai=len(teams[i])

ans=saidai

print(ans)
n = input()
list = []

for i in range(n):
    sp = input().split()
    s, p = sp[0], int(sp[1])
    list.append(i+1, s, p)

list.sort(key=lambda x:(x[0],x[1]))
for l in list:
    print(l[0])


### FIXED CODE ###


n = int(input())
list = []

for i in range(n):
    sp = input().split()
    s = str(sp[0])
    p = int(sp[1])
    list.append([i+1, s, p])

list.sort(key=lambda x:(x[1],-x[2]))
for l in list:
    print(l[0])
H,W = (int(_) for _ in input().split())                                                                                                                              
grid = [list(str(input())) for i in range(H)] 
dp = [[ -1 for i in range(W)] for j in range(H)]
dp[0][0] = 0 
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] =="#" or (i,j) == (0,0)):
            continue
        if(i-1 >=0 and j-1>=0):
            if(dp[i-1][j] >= 0 and dp[i][j-1]>=0):
                dp[i][j]= min(dp[i-1][j]+1,dp[i][j-1] + 1)
            elif(dp[i-1][j] >=0):
                dp[i][j] = dp[i-1][j]+1
            elif(dp[i][j-1] >=0):
                dp[i][j] = dp[i][j-1]+1
        elif(i -1 >= 0 and j -1 < 0): 
            if(dp[i-1][j] >= 0): 
                dp[i][j] = dp[i-1][j]+ 1
        elif(j-1 >= 0 and i-1 < 0): 
            if(dp[i][j-1] >= 0): 
                dp[i][j] = dp[i][j-1] + 1 
cnt=0
dic={}
for i in range(0,H):
    for j in range(0,W):
        if(grid[i][j] == "#" or (i,j) == (0,0)):
            continue
        if(dp[i][j] == -1):
            cnt+=1
        elif(dp[i][j] not in dic):
            dic[dp[i][j]] = 1 
        else:
            cnt+=1
if(dp[H-1][W-1] not in dic or dic[dp[H-1][W-1]] !=1):
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

N=int(input())
A=int(input())
tmp = N
while(N >=500):
    tmp = N%500
    N//=500
if(tmp <=A):
    print("Yes")
else:
    print("No")
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  for (char c = 97; c <= 122; c++) {
    if (count(s.begin(), s.end(), c) % 2 != 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;

  return 0;
}

### FIXED CODE ###

s = list(input())
if all(s.count(x) % 2 == 0 for x in set(s)):
  print("Yes")
else:
  print("No")
vx = [1, -1, 0, 0, 1, 1, -1, -1]
vy = [0, 0, 1, -1, 1, -1, 1, -1]


def dfs(col, row):
    c[col][row] = 0
    for x, y in zip(vx, vy):
        ny = col + y
        nx = row + x
        if nx < 0 or ny < 0 or nx >= w or ny >= h:
            continue
        if c[ny][nx] == 0:
            continue
        dfs(ny, nx)

while True:
    w, h = map(int, raw_input().split())
    if w == 0:
        break

    c = []
    for _ in range(h):
        c.append(map(int, raw_input().split()))

    cnt = 0

    for col in range(h):
        for row in range(w):
            if c[col][row] == 1:
                cnt += 1
                dfs(col, row)
    print cnt

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

vx = [1, -1, 0, 0, 1, 1, -1, -1]
vy = [0, 0, 1, -1, 1, -1, 1, -1]


def dfs(x, y):
    c[y][x] = 0
    for dx, dy in zip(vx, vy):
        nx = x + dx
        ny = y + dy
        if nx < 0 or ny < 0 or nx >= w or ny >= h:
            continue
        if c[ny][nx] == 0:
            continue
        dfs(nx, ny)

while True:
    w, h = map(int, raw_input().split())
    if w == 0:
        break

    c = []
    for _ in range(h):
        c.append(map(int, raw_input().split()))

    cnt = 0

    for y in range(h):
        for x in range(w):
            if c[y][x] == 1:
                cnt += 1
                dfs(x, y)
    print cnt
import math
a,b=[int(x) for x in input().split()]
i=1
g=math.gcd(a,b)
l=[]
while(i*i<=g):
    if g%i==0 and i*i!=g:
        l.append(i)
        l.append(g//i)
    if i*i==g:
        l.append(i)
    i=i+1
l=sorted(l)
i=1
while(i<len(l)):
    if l[i]!=0:
        j=i+1
        while(j<len(l)):
            if l[j]%l[i]==0:
                l[j] = 0
            j=j+1
    i=i+1
l=list(filter ( lambda x:x!=0,l))
print(len(l))


### FIXED CODE ###

a,b=[int(x) for x in input().split()]
i=1
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)
g=gcd(a,b)
l=[]
while(i*i<=g):
    if g%i==0 and i*i!=g:
        l.append(i)
        l.append(g//i)
    if i*i==g:
        l.append(i)
    i=i+1
l=sorted(l)
i=1
while(i<len(l)):
    if l[i]!=0:
        j=i+1
        while(j<len(l)):
            if l[j]%l[i]==0:
                l[j] = 0
            j=j+1
    i=i+1
l=list(filter ( lambda x:x!=0,l))
print(len(l))
k = int(input())
list=[]
import math

for i in range(k+1):
    for j in range(k+1):
        for m in range(k+1):
            n = math.gcd(i,j)
            a = math.gcd(n,m)
            list.append(int(a)

ans = sum(list)
print(ans)


### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
import math
r=int(input())
print(math.pi*r**2, math.pi*2*r)

### FIXED CODE ###

import math
r=float(input())
print(math.pi*r**2, math.pi*2*r)
N = int(input())
X = [i for i in input()]
sum_X = X.count("1")


def f(n, p):
    count = 1
    while True:
        n = int(n, 2) % p
        if n == 0:
            break
        n = format(n, "b")
        p = n.count("1")
        count += 1
    return count


for i in range(0, N):
    tempX = ""
    count = sum_X
    if X[i] == "0":
        count += 1
        X[i] = "1"
        tempX = "".join(X)
        X[i] = "0"
    else:
        count -= 1
        X[i] = "0"
        tempX = "".join(X)
        X[i] = "1"

    print(f(tempX, count))

### FIXED CODE ###

N = int(input())
X = input()
X_i = int(X, 2)
X_b = bin(X_i)
sum_X = X_b.count("1")
Xp = X_i % (sum_X + 1)
Xm = X_i % (sum_X - 1) if sum_X - 1 > 0 else -1


def f(n, p):
    count = 1
    n %= p
    while n != 0:
        p = bin(n).count("1")
        n %= p
        count += 1
    return count


for i in range(1, N + 1):
    if X[i - 1] == "1":
        if sum_X - 1 <= 0:
            print(0)
            continue
        nm = pow(2, N - i, sum_X - 1)
        print(f(Xm - nm, sum_X - 1))
    else:
        np = pow(2, N - i, sum_X + 1)
        print(f(Xp + np, sum_X + 1))
N = int(input())
X = int(input())
T = int(input())

a = N/X
b = N//X
k1 = a*T
k2 = k1 + 1
if b == 0:
  print(k1)
else:
  print(k2)

### FIXED CODE ###

s = input().split()
N = int(s[0])
X = int(s[1])
T = int(s[2])
a = N//X
b = N%X
k1 = a*T
k2 = k1 + T
if b == 0:
  print(k1)
else:
  print(k2)
import headq

heap=[]
N = input()
for i in range(10):
  heapq.heappush(heap,i)
print(heap)


### FIXED CODE ###

import heapq
 
heap=[]
N = int(input())
for i in range(1,10):
  heapq.heappush(heap,i)
for i in range(N):
  x = heapq.heappop(heap)
  if x%10!=0:
    heapq.heappush(heap,10*x+(x%10)-1)
  heapq.heappush(heap,10*x+(x%10))
  if x%10!=9:
    heapq.heappush(heap,10*x+(x%10)+1)
  
print(x)
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
G = {}
for i in range(N-1,0,-1):
    a = A[i]
    kmin = 0
    while 2**kmin<=a:
        kmin += 1
    kmax = 0
    while 2**kmax<=2*a:
        kmax += 1
    for k in range(kmin,kmax):
        b = 2**k-a
        ind = bisect_left(A[:i],b)
        if A[ind]==b and ind<i:
            if 2**k not in G:
                G[2**k] = []
            G[2**k].append((i,ind))
            ind += 1
            while A[ind]==b:
                G[2**k].append((i,ind))
                ind += 1
C = sorted([[a,len(G[a])] for a in G],key=lambda x:x[1],reverse=True)
hist = [0 for _ in range(N)]
cnt = 0
for c in C:
    a,_ = c
    for x in G[a]:
        i,j = x
        if hist[i]==0 and hist[j]==0:
            cnt += 1
            hist[i] = 1
            hist[j] = 1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
A = [[A[i],0] for i in range(N)]
cnt = 0
for i in range(N-1,0,-1):
    if A[i][1]==0:
        a = A[i][0]
        A[i][1]=1
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,[b,1])
        ind -= 1
        if ind<i and A[ind]==[b,0]:
            A[ind][1]=1
            cnt += 1
print(cnt)
a, b, c, n = map(int, input().split())
if a >= n:
    print(n)
elif n > a and a + b >= n:
    print(a)
else:
    print(2a - n + b)

### FIXED CODE ###

a, b, c, n = map(int, input().split())
if a >= n:
    print(n)
elif n > a and a + b >= n:
    print(a)
else:
    print(a + a - n + b)
from collections import Counter
import numpy as np
H, W = map(int, input().split())
a = []
r_idx = []
c_idx = []
#a.shape = (H, W)
for i in range(H):
    line = list(input())
    if Counter(line).most_common()[0][1] != W:
        r_idx.append(i)
    a.append(line)
a = np.array(a).T
#a.shape = (W, H)
b = []
for i in range(W):
    if Counter(a[i]).most_common()[0][1] == H:
        continue
    b.append(a[i])

b = np.array(b).T
c = []
for idx in r_idx:
    c.append(b[idx])

for i in range(len(c)):
    print("".join(c[i]))


### FIXED CODE ###

import bisect
N, K = map(int, input().split())
x = list(map(int, input().split()))
t = 2 * (x[-1] - x[0])
i = bisect.bisect_right(x, 0)
for j in range(0, N):
    if N <= j + K -1 :
        break
    if (j - (i - 0.1)) * (j + K- 1 - (i - 0.1)) >= 0:
        t = min(t, max(abs(x[j]), abs(x[j+K-1])))
    else:
        t = min(t, abs(2 * x[j]) + x[j+K-1])
        t = min(t, abs(x[j]) + 2 * x[j+K-1])
print(t)
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
 
DIV_NUM = 1000000000 + 7
 
INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])
 
A = [int(x) for x in input().split()]
AA = np.array(A , dtype='int64')

if N==1:
    print(0)
    exit()
 
tree = [0] * (N+1)

def BIT_update(x):
    while x <= N:
        tree[x] += 1
        y = x
        z = 1
        while y:
            if y % 2 == 1:
                x += z
                break
            y /= 2
            z *= 2
def BIT_sum(x):
    s = 0
    while x > 0:
        s += tree[x]
        y = x
        z = 1
        while y:
            if y % 2 == 1:
                x -= z
                break
            y /= 2
            z *= 2
    return s
 
answer = N*(N-1)//2
for i in AA:
    answer -= BIT_sum(int(i))
    BIT_update(int(i))

B = sorted(A)
 
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r
 
# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)
 

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

DIV_NUM = 1000000000 + 7

INPUT_NUMS = list(map(int, input().split()))
N=int(INPUT_NUMS[0])
K=int(INPUT_NUMS[1])

A = [int(x) for x in input().split()]
AA = np.array(A)
if N==1:
    print(0)
    exit()

# https://kira000.hatenadiary.jp/entry/2019/02/23/053917
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A)-1, i, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                cnt += 1
    return cnt

answer = bubble_sort(AA)

B = sorted(A)
q=0
p=B[0]
r=0
for i in range(1,N):
    if B[i]>p:
        p=B[i]
        r=i
    q += r

# print(answer,K)
answer = answer % DIV_NUM
answer = int(answer)
answer = (answer * K) % DIV_NUM
q = q % DIV_NUM
answer = answer + q * K * (K-1) // 2
answer = answer % DIV_NUM
print(answer)
N,ans,x=int(input()),0,0
s=sorted([int(input()) for i in range(N)])
for i in range(N):
    if s[i]>x:
        ans+=1
        x=s[i]
print(ans)        

### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
a,b=map(int,input().split())
ans=True
for i in range(a+1):
    for j in range(a+1-i):
        if ans==True:
            s=10000*i+5000*j+1000*(a-i-j)
            if s == b:
                print(str(i)+" "+str(j)+" "+str(a-i-j))
                ans = False
        else:
            break
if ans==True:
    print("-1 -1 -1")
n=int(input())
a = []
for _ in range(n):
    a.append(int(input()))
for x in range(n-1):
    for y in range(x+1,n):
        if a[y] == a[x]:
            a.remove(a[x])

print(len(a))


### FIXED CODE ###

n=int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b=[]
for x in range(1,101):
 for y in range(n):
     if a[y]==x:
        b.append(a[y])
        break

print(len(b))
n, m = [int(v) for v in input().split()]

count_map = [0] * m

count = 0
miss = 0
for i in range(m):
	p, s = input().split()
    
    if count_map[p] == True:
      continue
    
    if s == 'AC':
	    count_map[p] = True
        count += 1
    else:
      	miss += 1
      
print(count, miss)




### FIXED CODE ###

n, m = [int(v) for v in input().split()]

count_map = [0] * (n + 1)
miss_map = [0] * (n + 1)

count = 0
miss = 0
for i in range(m):
    p, s = input().split()
    p = int(p)

    if count_map[p]:
        continue

    if s == 'AC':
        count_map[p] = True
        count += 1
        miss += miss_map[p]
    else:
        miss_map[p] += 1

print(count, miss)
s =str(input())

if len(s) == 2:
    if s[0]==s[1]:
        sIndex = 1
        eIndex = 2
    else:
        sIndex = -1
        eIndex = -1
elif len(s)>2:
    sIndex=-1
    eIndex=-1
    for i in range(len(s)-2):
        par_str = s[i:i+3]
        if (par_str.count(par_str[0])>=2) | (par_str.count(par_str[1])>=2):
            sIndex = i + 1
            eIndex = i + 3
            break
    
ans = str(sIndex)+' '+str(eIndex)
print(ans)

### FIXED CODE ###

n = int(input())
sum = 0
for i in range(n+1):
    sum = sum + i
    
print(sum)
n = int(input())
d = set(map(int, input().split())) 
s=0

for i in range(n):
   for j in range(i+1,n):
      s += d[i]*d[j]
print(s)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split())) 
s=0
# print(d)
for i in range(n):
   for j in range(i+1,n):
      s += d[i]*d[j]
print(s)