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

from sys import stdin, setrecursionlimit


def cmb(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    x = y = 1
    for i in range(r):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()

    a_cmb = [0] * n
    a_cmb[k - 1] = 1
    for i in range(k, n):
        a_cmb[i] = a_cmb[i - 1] * i // (i - k + 1)

    ans = 0

    for i in range(n):
        if 0 <= i < n - k + 1:
            ans -= a[i] * a_cmb[n - 1 - i]
        if k - 1 <= i < n:
            ans += a[i] * a_cmb[i]

    print(ans % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    n, k = map(int, stdin.readline().split())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    ans = 0

    m = n + 1

    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def initialize_cmb(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % mod
                inv[i] = mod - inv[mod % i] * (mod // i) % mod
                finv[i] = finv[i - 1] * inv[i] % mod

    def cmb(n, k, mod=10 ** 9 + 7):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod

    initialize_cmb(m)

    for i in range(n - k + 1):
        ans -= a[i] * cmb(n - 1 - i, k - 1)
        ans %= mod
    for i in range(k - 1, n):
        ans += a[i] * cmb(i, k - 1)
        ans %= mod
    print(ans % mod)


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

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

#d = deque(['S'])

#d = ['S']
d = ['S']
rev = 0

for i in range(q):
    if query[i][0] == '2':
        if query[i][1] == '1':
            d.insert(0,query[i][2])
        else:
            d.append(query[i][2])
    else:
        d.reverse()
        rev += 1


if rev % 2 == 1:
    s = ''.join(list(reversed(s)))
"""
while len(d):
    tmp = d.popleft()
    if tmp == 'S':
        ans.append(s)
    else:
        ans.append(tmp)
"""
d = [s if i == 'S' else i for i in d]

print(*d,sep='')

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = False

for i in range(q):
    if query[i][0] == '1':
        rev = not rev
        continue
    
    if not rev:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.appendleft(query[i][2])
            else:
                d.append(query[i][2])
    else:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.append(query[i][2])
            else:
                d.appendleft(query[i][2])

#ans = deque()
if rev:
    #d = ''.join(list(reversed(d)))
    s = s[::-1]



while len(d):
    if rev:
        tmp = d.pop()
    else:
        tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

#print(*ans,sep='')
### BUGGY CODE ###

class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
U = 2 * 10 ** 6 + 10
comb = Combination(U, mod)
pow26 = [1] * U
pow25 = [1] * U
for i in range(1, U):
    pow25[i] = pow25[i - 1] * 25 % mod
    pow26[i] = pow26[i - 1] * 26 % mod

K = int(input())
S = input()
N = len(S)

ans = 0
for i in range(K + 1):
    res = K - i
    pos = comb(N - 1 + i, i)
    tmp = pow26[res] * pos % mod * pow25[i] % mod
    ans = (ans + tmp) % mod
print(ans)

### FIXED CODE ###

class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6 + 10, mod)

K = int(input())
S = input()
N = len(S)

ans = 0
for i in range(K + 1):
    res = K - i
    right = pow(26, res, mod)
    pos = comb(N - 1 + i, i)
    cnt = pow(25, i, mod)
    tmp = right * pos % mod * cnt % mod
    ans = (ans + tmp) % mod
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    N = int(input())
    A = inpl()
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = inpl()
        edges[u].append(v)
        edges[v].append(u)
    DPs = [None] * (N + 1)
    DPs[0] = []

    Q = deque()
    Q.append(1)
    parent = [-1] * (N + 1)
    parent[1] = 0
    while Q:
        nv = Q.popleft()
        DPs[nv] = DPs[parent[nv]].copy()
        t = bisect(DPs[nv], A[nv - 1])
        if t >= len(DPs[nv]):
            DPs[nv].append(A[nv - 1])
        else:
            DPs[nv][t] = A[nv - 1]

        for kouho in edges[nv]:
            if parent[kouho] == -1:
                Q.append(kouho)
                parent[kouho] = nv

    for i in range(1, N + 1):
        print(len(DPs[i]))
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


class solve:
    def __init__(self, N):
        self.ans = [0] * N
        self.DP = []

    def recur(self, i, pi=-1):
        # DPテーブルを更新し、答えを求める。
        # また、巻き戻す値を覚える。
        rev_i = bisect(self.DP, self.A[i])
        if rev_i == len(self.DP):
            self.DP.append(self.A[i])
            rev_v = None
        else:
            rev_v = self.DP[rev_i]
            self.DP[rev_i] = self.A[i]

        self.ans[i] = len(self.DP)

        for nv in self.edges[i]:
            if nv != pi:
                self.recur(nv, i)

        # 巻き戻す。.
        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


def main():
    N = int(input())
    S = solve(N)
    S.A = inpl()
    S.edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = inpl()
        S.edges[u - 1].append(v - 1)
        S.edges[v - 1].append(u - 1)

    S.recur(0)

    print(*S.ans, sep='\n')
    # print(edges)
    # print(parent)
    # print(DPs)


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

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

def get_input() -> int:
    """
    標準入力を取得する.

    Returns:\n
        int: 標準入力
    """
    N = int(input())

    return N


def main(N: int) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 正整数（1 <= N <= 10^7）
    """
    # 求解処理
    F = [0 for n in range(N + 1)]
    for n in range(1, N + 1):
        for i in range(1, N // n + 1):
            F[n * i] += 1

    ans = sum([n * F[n] for n in range(N + 1)])

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N = get_input()

    # メイン処理
    main(N)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())

def g(N: int) -> int:
    return int(N * (N + 1) / 2)

# 求解処理
ans = 0
for n in range(1, N + 1):
    ans += n * g(N // n)
            
# 結果出力
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q=[int(j) for j in input().split()]
l=[]
for i in range(n):
    s,t,x=[int(j) for j in input().split()]
    l.append((s-x,1,x))
    l.append((t-x,0,x))

for i in range(q):
    d=int(input())
    l.append((d,2,i))

l.sort()

ans=[-1]*q
ll=set()
m=10**18
p=False
for i,j,x in l:
    if j==1:
        ll.add(x)
        if m>x:
            m=x
            p=True
    elif j==0:
        ll.remove(x)
        if x==m:
            p=False
    else:
        if not p:
            if ll:
                p=True
                m=min(ll)
            else:
                m=-1
        ans[x]=m
print('\n'.join(map(str,ans)))



### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=[int(j) for j in input().split()]
l=[]
for i in range(n):
    s,t,x=[int(j) for j in input().split()]
    l.append((s-x,1,x))
    l.append((t-x,0,x))

for i in range(q):
    d=int(input())
    l.append((d,2,i))

l.sort()

ans=[-1]*q
ll=set()
m=10**18
p=False
for i,j,x in l:
    if j==1:
        ll.add(x)
        if m>x:
            m=x
            p=True
    elif j==0:
        ll.remove(x)
        if x==m:
            p=False
    else:
        if not p:
            if ll:
                p=True
                m=min(ll)
            else:
                m=-1
        ans[x]=m
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
ans=0
flag=True
for i in range(N):
  for j in range(i):
    if(P[i]>P[j]):
      flag=False
      break
  if flag:ans+=1
  flag=True
print(ans)

### FIXED CODE ###

from sys import stdin
N=int(input())
P=[int(x) for x in stdin.readline().rstrip().split()]
ans=1
min=P[0]

for i in range(1,N):
  if(P[i] < min):
    ans+=1
    min=P[i]
print(ans)
### BUGGY CODE ###

def cal(a):

    return ((1 + a) / 2)

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []

for i in range(0, N):
    p[i] = cal(p[i])

for i in range(0, N - K + 1):
    ans = 0
    for j in range(i, i + K):
        ans += p[j]
    ans_raw.append(ans)


print(max(ans_raw))

### FIXED CODE ###

def cal(a):
 	return ((1 + a) / 2)
 
N, K = map(int, input().split())
p = list(map(int, input().split()))
ans_raw = []
sum_raw = []
sum_cal = 0
 
for i in range(0, N):
    p[i] = cal(p[i])


for i in range(0, N):
	sum_cal += p[i]
	sum_raw.append(sum_cal)

for i in range(0, N - K):
	ans = sum_raw[i + K] - sum_raw[i]
	ans_raw.append(ans)

ans_0 = sum_raw[K - 1]
ans_raw.append(ans_0)

print(max(ans_raw))
### BUGGY CODE ###

import queue
n,m = map(int, input().split())
t = [[] for i in range(n)]
dis = [n for i in range(n)]
dis[0] = 0
near = [0 for i in range(n)]
q = queue.Queue()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    dis[t[0][i]] = 1
    near[t[0][i]] = 0
    q.put(t[0][i])
while not q.empty():
    e = q.get()
    for j in range(len(t[e])):
        if dis[t[e][j]] >= dis[e] +1:
            dis[t[e][j]] = dis[e] +1
            near[t[e][j]] = e
            q.put(t[e][j])
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)


### FIXED CODE ###

from collections import deque
n,m = map(int, input().split())
t = [[] for i in range(n)]
near = [-1 for i in range(n)]
near[0] = 0
q = deque()
for i in range(m):
    a,b = map(int, input().split())
    t[a-1].append(b-1)
    t[b-1].append(a-1)
for i in range(len(t[0])):
    c = t[0][i]
    near[c] = 0
    q.append(c)
while len(q) > 0:
    e = q.popleft()
    for j in range(len(t[e])):
        c = t[e][j]
        if near[c] == -1:
            near[c] = e
            q.append(c)
print('Yes')
for i in range(1,len(near)):
    print(near[i]+1)
### BUGGY CODE ###

n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    s.append([int(_) for _ in input().split()])
# print(s)
dp = [0 for i in range(n)]
dp[0] = 1
dp_s = [0 for i in range(n+1)]
dp_s[1] = 1
# print(dp)
# print(dp_s)
# print('*****************')
for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    # print(dp)
    dp_s[i+1] += dp_s[i] + dp[i]
    # print(dp_s)
    # print('*****************')
print(dp[-1]%998244353)

### FIXED CODE ###

n, k = [int(_) for _ in input().split()]
s = []
for i in range(k):
    s.append([int(_) for _ in input().split()])
# print(s)
dp = [0 for i in range(n)]
dp[0] = 1
dp_s = [0 for i in range(n+1)]
dp_s[1] = 1
# print(dp)
# print(dp_s)
# print('*****************')
for i in range(1, n):
    for j in range(len(s)):
        r, l = s[j]
        if i-r >= 0:
            if i-l >= 0:
                dp[i] += dp_s[i-r+1] - dp_s[i-l]
            else:
                dp[i] += dp_s[i-r+1] - dp_s[0]
    dp[i] = dp[i] % 998244353
    # print(dp)
    dp_s[i+1] += dp_s[i] + dp[i]
    dp_s[i+1] = dp_s[i+1] % 998244353
    # print(dp_s)
    # print('*****************')
print(dp[-1])
### BUGGY CODE ###

# ABC-142-D
A, B = map(int, input().split())
ans = 1

#x以下の素数を全て出す
def get_prime_number(x):
    if x == 1:
        return []
    max = int(x ** 0.5)
    search_list = [i for i in range(2,x+1)]
    prime_num = []
    while search_list[0] <= max:
        prime_num.append(search_list[0])
        tmp = search_list[0]
        search_list = [i for i in search_list if i % tmp != 0]
    prime_num.extend(search_list)
    return prime_num

#xの素因数を全て出す
def get_prime_factor(x):
    search_list = get_prime_number(x)
    prime_factor_list = []
    for i in search_list:
        if x % i == 0:
            prime_factor_list.append(i)
    return prime_factor_list

A_prime_factor = get_prime_factor(A)
B_prime_factor = get_prime_factor(B)

for item in A_prime_factor:
    if item in B_prime_factor:
        ans += 1
print(ans)

### FIXED CODE ###

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)
### BUGGY CODE ###

n = int(input())
i = 1
ret = ""
while True:
    x = i
    if  x % 3 == 0:
        ret += " " + str(i)
    elif x % 10 == 3:
        ret += " " + str(i)
    else:
        x /= 10
        while x > 0:
            if x % 10 == 3:
                ret += " " + str(i)
                x /= 10
                if x == 0:
                    break
    i+=1
    if i > n:
        break

print(ret)



### FIXED CODE ###

#
# 5d
#

def main():
    n = int(input())
    s = ""
    for i in range(1, n+1):
        x = i
        if x % 3 == 0 or x % 10 == 3:
            s += " " + str(i)
        else:
            x //= 10
            while x:
                if x % 10 == 3:
                    s += " " + str(i)
                    break
                x //= 10
    print(s)


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

from collections import deque

n = int(input())
q = deque()
for i in range(n):
    com = input().split()
    if com[0] == 'insert':
        q.appendleft(int(com[1]))
    elif com[0] == 'delete':
        try:
            q.remove(int(com[1]))
        except:
            pass
    elif com[0] == 'deleteFirst':
        q.popleft()
    else:
        q.pop()
print(*q)


### FIXED CODE ###

from collections import deque

n = int(input())
q = deque()
for i in range(n):
    com = input().split()
    if com[0] == 'insert':
        q.appendleft(com[1])
    elif com[0] == 'delete':
        try:
            q.remove(com[1])
        except:
            pass
    elif com[0] == 'deleteFirst':
        q.popleft()
    else:
        q.pop()
print(" ".join(q))
### BUGGY CODE ###

import queue
import copy
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
#######
p = queue.Queue()
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            p.put([h-1,w])
            p.put([h+1,w])
            p.put([h,w-1])
            p.put([h,w+1])
ans = 0
while True:
    q = copy.copy(p)
    p = queue.Queue()
    while not(q.empty()):
        x = q.get()
        h,w = x[0],x[1]
        if h<0 or h>=H or w<0 or w>=W or A[h][w]=="#":
            continue
        A[h][w] = "#"
        p.put([h-1,w])
        p.put([h+1,w])
        p.put([h,w-1])
        p.put([h,w+1])
    if p.empty():
        break
    ans+=1
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        s = l[i]+l[j]
        start = j+1
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        ans += end-j-1
print(ans)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
max = l[N-1]
tc = N
st = [j+1 for j in range(N-1)]
for i in range(N-2):
    if l[i]+l[i+1] > max:
        k = N-i-1
        ans += ((k-1)*k*(k+1))//6
        break
    for j in range(i+1,N-1):
        if j == tc:
            ans += tp
            break
        s = l[i]+l[j]
        if s <= l[j+1]:
            continue
        if s > max:
            tc = j 
            tp = (N-j-1) * (N-j) //2 #これをiの中でできないか
            ans += tp
            break
        start = st[j]
        if s <= l[start]:
            ans += start-j-1
            continue
        end = N
        while start != end:
            center = (start + end)//2
            if s <= l[center]:
                end = center
            else:
                start = center + 1
        st[j] = end
        ans += end-j-1
print(ans)
### BUGGY CODE ###

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

mod = (10**9 + 7)
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        ans += (alist[i]*alist[j])
        ans = ans%mod

print(ans)

### FIXED CODE ###

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

mod = (10**9 + 7)
ans = 0

import numpy
alistsum = numpy.cumsum(alist)
asum = sum(alist)

for i in range(n-1):
    ans += alist[i]*(asum - alist[i])
    asum -= alist[i]
    ans = ans%mod
print(ans)
### BUGGY CODE ###

import numpy as np
s=input()
t=input()

ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
pp=np.full((ns+1,nt+1),'-1')
for i in range(ns):
  for j in range(nt):
    a=np.array([dp[i][j]+1 if s[i]==t[j] else -1,dp[i+1][j],dp[i][j+1]])
    dp[i+1][j+1]=np.max(a)
    pp[i+1][j+1]=np.argmax(a)

i=ns
j=nt
ans=[]
while i>0 and j>0:
  sw=pp[i][j]
  if sw==0:
        i-=1
        j-=1
        ans.append(s[i])
  elif sw==1:
        j-=1
  elif sw==2:
        i-=1
ans1=''
for _ in range(len(ans)):
      ans1+=ans.pop()
print(ans1)


### FIXED CODE ###

import numpy as np
s=np.array(list(input()))
t=np.array(list(input()))
is_eq=np.array(s[:,None]==t[None,])
# is_eq[i][j]:sのi文字目とtのj文字目が等しいかどうか
# print(is_eq)
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)

# dp[i+1][j+1]:sのi文字目までとtのj文字目までで最長の部分列
# dp[0][j]=0,dp[i][0]=0,dp[n+1][w+1]の値がsとtで最長の部分列の長さ
for i in range(ns): #sのi文字目までの文字列で調査
    dp[i+1][1:]=np.maximum(dp[i][:-1]+is_eq[i],dp[i][1:])#左上からの更新、真上からの更新
    dp[i+1]=np.maximum.accumulate(dp[i+1])#左からの更新
i=ns
j=nt
ans=['']
while i>0 and j>0:
      if dp[i][j]==dp[i-1][j]:
            i-=1
      elif dp[i][j]==dp[i][j-1]:
            j-=1
      else:
            ans.append(s[i-1])
            i-=1
            j-=1
a=''
for _ in range(len(ans)):
      a+=ans.pop()
print(a)
### BUGGY CODE ###

#三井住友2019_D
n=int(input())
s=input()

cnt=0
for i in range(0,1000):
    t='0'*(3-len(str(i)))+str(i)
    flg1,flg2,flg3=[False]*3
    for j in range(n):
        if flg1:
            if flg2:
                if s[j]==t[2]:
                    flg3=True
                    break
            else:
                if s[j]==t[1]:
                    flg2=True
        else:
            if s[j]==t[0]:
                flg1=True
    cnt+=1 if flg3 else 0
    
print(cnt)



### FIXED CODE ###

#三井住友2019_D
n=int(input())
s=input()

cnt=0
for i in range(0,1000):
    t='0'*(3-len(str(i)))+str(i)
    flg1,flg2,flg3=[False]*3
    for j in range(n):
        if flg1:
            if flg2:
                if s[j]==t[2]:
                    flg3=True
                    break
            else:
                if s[j]==t[1]:
                    flg2=True
        else:
            if s[j]==t[0]:
                flg1=True
    cnt+=1 if flg3 else 0
    
print(cnt)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [K] * N
B = []

for i in range(Q):
    B.append(int(input()))

for i in range(N):
    A[i] -= Q - B.count(i+1)
    if A[i] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0] * N
B = []

for i in range(Q):
    a = int(input())
    A[a-1] += 1

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

import itertools

n = int(input())
l = list(map(int, input().split()))
total = 0
mod = 1000000007
L = itertools.combinations(l, 2)
for a,b in L:
    total += ((a % mod) * (b % mod)) % mod
print(total % mod)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
mod = 1000000007
q = sum(l)
ans = 0
for i in range(len(l)):
    q -= l[i]
    ans += l[i] * q % mod
print(ans % mod)
### BUGGY CODE ###

s=list(input())
n=len(s)
mod=10**9 + 7
dp=[[0]*(13) for i in range(n)]

if s[n-1]=='?':
    for i in range(10):
        dp[0][i]=1
else:
    dp[0][int(s[n-1])]=1

for i in range(n-1):
    if s[n-2-i]=='?':
        for j in range(13):
            if dp[i][j]>0:
                for k in range(10):
                    dp[i+1][(j+(10**(i+1))*k)%13]+=dp[i][j]%mod
    else:
        for j in range(13):
            if dp[i][j]>0:
                dp[i+1][(j+(10**(i+1))*int(s[n-2-i]))%13]+=dp[i][j]%mod
print(dp[n-1][5]%mod)

### FIXED CODE ###

mod=10**9+7
r=[[(j-k)*9%13 for j in range(10)] for k in range(13)]
dp=[1]+[0]*12
for c in input():
  dp = [sum(dp[j] for j in k)%mod for k in r] if c>'9' else [dp[(int(c)-k)*9%13] for k in range(13)]
print(dp[5])