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

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

def main():
     k = int(input())

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     index = 0
     s = 9
     while(s < k):
          runrun, s = make(runrun[index], runrun, s)
          index += 1
          # print(runrun)

     print(runrun[k-1])

def make(n, r, s):
     num = n % 10
     p = n * 10 + num
     if num == 0:          
          return r + [p, p + 1], s + 2
     elif num == 9:
          return r + [p - 1, p], s + 2
     else:
          return r + [p - 1, p, p + 1], s + 3

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
     k = int(input())

     runrun = [1, 2, 3, 4, 5, 6, 7, 8, 9]
     count = 0
     while(len(runrun) < k):
          target = runrun[count]
          num = target % 10
          if num != 0:
               runrun.append(target * 10 + num - 1)
          runrun.append(target * 10 + num)
          if num != 9:
               runrun.append(target * 10 + num + 1)

          count += 1
          # print(runrun)

     print(runrun[k-1])

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

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

count = 0
for i in range(n-1):
    for j in range(i+a_l[i]+1,n):
        if (j-i) == (a_l[j] + a_l[i]):
            count += 1

print(count)



### FIXED CODE ###

n = int(input())
a_l = list(map(int,input().split()))
ia = list(enumerate(a_l))

x_dict = {}
y_dict = {}
for i, a in ia:
    x = i+a
    y = i-a
    if x in x_dict:
        x_dict[x] += 1
    else:
        x_dict[x] = 1
    if y in y_dict:
        y_dict[y] += 1
    else:
        y_dict[y] = 1

count = 0
for xkey in x_dict.keys():
    if xkey in y_dict:
        count += x_dict[xkey] * y_dict[xkey]

print(count)
### BUGGY CODE ###

import numpy as np

x, move, d = map(int, input().split())

for k in range(move):

    if np.sign(x) == 1 or np.sign(x) == 0:
        x = x-d
    else:
        x = x+d

    if abs(x) <= d/2 and (move-(k+1))%2==0:
        break
    elif abs(x) <= d/2 and (move-(k+1))%2!=0:
        if np.sign(x) == 1 or np.sign(x) == 0:
            x = x-d
        else:
            x = x+d

        break


print(abs(x))


### FIXED CODE ###

import numpy as np

x, move, d = map(int, input().split())

num = int(abs(x)/d)
ans = 0

if move <= num:
    if np.sign(x) == 1:
        ans = x-d*move
    else:
        ans = x+d*move

elif (move-num)%2==0:
    if np.sign(x) == 1:
        ans = x-d*num
    else:
        ans = x+d*num

elif (move-num)%2!=0:
    if np.sign(x) == 1:
        ans = x-d*(num+1)
    else:
        ans = x+d*(num+1)


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

n = int(input())
A = list(map(int, input().split()))
q = int(input())
B,C = [], []

for _ in range(q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1
for b, c in zip(B,C):
    d.setdefault(b, 0)
    d.setdefault(c, 0)
    d[c] += d[b]
    d[b] = 0
    ans = 0
    for i, v in d.items():
        ans += i*v
    print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
B,C = [], []

for _ in range(q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

ans = sum(A)

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

for b, c in zip(B,C):
    d.setdefault(b, 0)
    d.setdefault(c, 0)
    ans -= d[c] * c
    ans -= d[b] * b
    d[c] += d[b]
    d[b] = 0
    ans += d[c] * c
    ans += d[b] * b
    print(ans)
### BUGGY CODE ###

n, m = map(int, raw_input().split())
graph = {}
visited = {}
# 0: not visited, 1: visited
scores = {}
for i in range(n):
    if i == 0:
        scores[i+1] = 0
    else:
        scores[i+1] = float("inf")
    graph[i+1] = {}

for i in range(m):
    a, b, c = map(int, raw_input().split())
    graph[a][b] = -c
    # {1: {2: 4, 3: 5}, 2: {3: 4}}

for i in range(n):
    for v in graph.keys():
        for e in graph[v].keys():
            if scores[e] > scores[v] + graph[v][e]:
                scores[e] = scores[v] + graph[v][e]

ans = -scores[n]
negative = {}
for i in range(n):
    negative[i+1] = False

for i in range(n+1):
    for v in graph.keys():
        for e in graph[v].keys():
            if scores[v] + graph[v][e] < scores[e]:
                scores[e] = scores[v] + graph[v][e]
                negative[e] = True
                if negative[v]:
                    negative[e] = True

if negative[n]:
    print 'inf'
else:
    print ans

### FIXED CODE ###

n, m = map(int, raw_input().split())
graph = {}
visited = {}
# 0: not visited, 1: visited
scores = {}
for i in range(n):
    if i == 0:
        scores[i+1] = 0
    else:
        scores[i+1] = float("inf")
    graph[i+1] = {}

for i in range(m):
    a, b, c = map(int, raw_input().split())
    graph[a][b] = -c
    # {1: {2: 4, 3: 5}, 2: {3: 4}}

for i in range(n):
    for v in graph.keys():
        for e in graph[v].keys():
            if scores[e] > scores[v] + graph[v][e]:
                scores[e] = scores[v] + graph[v][e]

ans = -scores[n]
negative = {}
for i in range(n):
    negative[i+1] = False

for i in range(n+1):
    if negative[n]:
        break
    for v in graph.keys():
        for e in graph[v].keys():
            if scores[v] + graph[v][e] < scores[e]:
                scores[e] = scores[v] + graph[v][e]
                negative[e] = True
                if negative[v]:
                    negative[e] = True

if negative[n]:
    print 'inf'
else:
    print ans
### BUGGY CODE ###

import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def get_primes(n=10**3):
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def prime_factor(n):
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort()
    lst = []
    ans = []
    while aa:
        x = aa[0]
        lst = []
        flag=False
        for a in aa[1:]:
            if a%x!=0:
                lst.append(a)
            else:
                if a==x:
                    flag=True
        if not flag:
            ans.append(x)
        aa = lst
        # print(ans)
    print(len(ans))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort()
    maxa = aa[-1]
    dp = [False]*(maxa+1)
    for a in aa:
        dp[a] = True
    dup = set()
    for a in aa:
        if a in dup:
            dp[a] = False
            continue
        else:
            dup.add(a)
        if dp[a]:
            for j in range(a*2,maxa+1,a):
                dp[j] = False
    print(sum(1 for d in dp if d))



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

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

def check(lst):
    if (N == lst[0]) and (len(set(lst)) == 1):
        return True
    else:
        return False

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for _ in range(K):
    A = move(A)
    if check(A):
        break

print (*A[:-1])


### FIXED CODE ###

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

def check(lst):
    for i in range(N):
        if lst[i] != N:
            return False
    return True

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for i in range(K):
    A = move(A)
    if check(A):
        # print (i)
        break

print (*A[:-1])
### BUGGY CODE ###

from bisect import bisect_left

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

for _ in range(M):
    b, c = map(int, input().split())
    index = bisect_left(A, c)
    i = min(index, b)
    A = [c] * i + A[i:]
    A.sort()

print(sum(A))



### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
X = []
for _ in range(M):
    b, c = map(int, input().split())
    X.append((b, c))

X = sorted(X, key=itemgetter(1), reverse=True)

for b, c in X:
    BC.extend([c] * b)
    if len(BC) >= N:
        break

Y = A + BC
Y.sort(reverse=True)
answer = sum(Y[:N])
print(answer)
### BUGGY CODE ###

N = int(input())
b_list = list(map(int,input().split()))
d_list = [True for i in range(N)]
s = True
b_list.append(1000000000)
for _ in range(N):
  for i in range(len(b_list)-1):
    if (b_list[i] > b_list[i+1]):
      if (d_list[i]):
        b_list[i] -= 1
        d_list[i] = False
      else:
        s = False
        break
if (s):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N = int(input())
b_list = list(map(int,input().split()))
s = True
if (b_list[0] > 1):
  b_list[0] -= 1
for i in range(1,len(b_list)):
  if (b_list[i-1] < b_list[i]):
    b_list[i] -= 1
for i in range(len(b_list)-1):
  if (b_list[i] > b_list[i+1]):
    s = False
if (s):
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

i = 0
p = list(map(int, input().split()))
n = p[0]
k = p[1]
q = p[2]
a = []
point = []
for i in range(q):
    a.append(int(input()))
j = 0
u = 0
for u in range(n):
    point.append(k)
while (j < q):
    m = 0
    while(m < n):
        if (m != a[j-1]):
            point[m-1] -= 1
        m += 1
    j += 1
g = 0
while(g < n):
    if(point[g] > 0):
        print("Yes")
    else:
        print("No")
    g += 1

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [0 for  _ in range(q)]
point = [0 for _ in range(n)]

for i in range(q):
    a[i] = int(input())

for i in range(q):
    point[a[i]-1] += 1

for i in range(n):
    if(point[i] > q-k):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(m):
 G=[]
 for i in range(m):
  G.append(3*i + 1)
 G.reverse()
 return G

for m in range(1, 100):
 G = Gmake(m)
 A2 = shellSort(A, n, m, G)
 if cnt < n ** 1.5:
  print(str(m))
  print(" ".join(map(str, G)))
  print(str(cnt))
  for i in A2:
   print(str(i))
  break

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(n):
 G=[]
 k = 1
 while k <= n and len(G) < 100:
  G.append(k)
  k = 3 * k + 1
 G.reverse()
 return G

G = Gmake(n)
A2 = shellSort(A, n, len(G), G)
print(str(len(G)))
print(" ".join(map(str, G)))
print(str(cnt))
for i in A2:
 print(str(i))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]  # 黒ならdist[i][j]は0、白なら-1

black_cells = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black_cells.append((i, j))
            dist[i][j] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h_black, w_black = black_cells.popleft()
        d=dist[h_black][w_black]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h_black+dy
            new_w = w_black+dx
            if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return max(sum(dist,[]))

d = bfs(black_cells, dist)
print(d)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

dist = [[-1]*W for _ in range(H)]

black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float("inf") for _ in range(n)]
    cost[0] = 0
    for i in range(n):
        for j in range(1, min(k+1, n-i)):
            cost[i+j] = min(cost[i+j], cost[i] + abs(h[i+j]-h[i]))
    print(cost[n-1])
resolve()

### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float("inf")]*n
    cost[0] = 0
    for i in range(n):
        for j in range(1, min(k+1, n-i)):
            cost[i+j] = min(cost[i+j], cost[i] + abs(h[i+j]-h[i]))
    print(cost[n-1])
resolve()
### BUGGY CODE ###

import copy

NOT_FOUND = False

# 二分探索
def binarySearch(n, S, t):
     
    left = 0
    right = n
    key = t
    while left < right:
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        elif key < S[mid]:
            right = mid
        else:        
            left = mid + 1
    return NOT_FOUND
 
if __name__ == '__main__':
     
    # 入力
    n = int(input()) # 数列Sに含まれる整数の個数
    S = list(map(int,input().split())) # 整数を含む数列
    q = int(input()) # 数列Tに含まれる異なる整数の個数
    T = list(map(int,input().split())) # 異なる整数を含む数列
     
    # 初期化
    C = 0 # Tに含まれる整数の中でSに含まれるものの個数
     
    # 数列T内の整数を1つずつチェック
    for i in range(q):
        isExist = binarySearch(n, copy.deepcopy(S), T[i])
         
        # 存在してたらカウント
        if isExist :
            C = C + 1
    # 出力
    print(C)


### FIXED CODE ###

import copy

NOT_FOUND = False

# 二分探索
def binarySearch(n, S, t):
     
    left = 0
    right = n
    key = t
    while left < right:
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        elif key < S[mid]:
            right = mid
        else:        
            left = mid + 1
    return NOT_FOUND
 
if __name__ == '__main__':
     
    # 入力
    n = int(input()) # 数列Sに含まれる整数の個数
    S = list(map(int,input().split())) # 整数を含む数列
    q = int(input()) # 数列Tに含まれる異なる整数の個数
    T = list(map(int,input().split())) # 異なる整数を含む数列
     
    # 初期化
    C = 0 # Tに含まれる整数の中でSに含まれるものの個数
     
    # 数列T内の整数を1つずつチェック
    for i in range(q):
        isExist = binarySearch(n, S, T[i])
         
        # 存在してたらカウント
        if isExist :
            C = C + 1
    # 出力
    print(C)
### BUGGY CODE ###

N = int(input())
min = N
max_i = 0
max_j = 0
for i in range(1,N):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j

print(max_i + max_j - 2)

### FIXED CODE ###

N = int(input())
min = N
max_i = 0
max_j = 0
for i in range(1,1000000):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j
for i in range(1000000,N // 1000000 + 1):
    if N % i == 0:
        j = N // i
        if abs(i - j) < min:
            min = abs(i - j)
            max_i = i
            max_j = j

print(max_i + max_j - 2)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    if i==0:
        ans=a[i]
    else:
        ans*=a[i]
        if 0 in a:
            print(0)
            exit()
        if ans>10**18:
            print(-1)
            exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if 0 in a:
    print(0)
    exit()
for i in range(n):
    if i==0:
        ans=a[i]
    else:
        ans*=a[i]
        if ans>10**18:
            print(-1)
            exit()
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
found = 0
for n in range(N):
    for i in range(n+1, N):
        if (i-n) == A[n] + A[i]:
            found += 1
print(found)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
found = 0
dt = defaultdict(int)
for n in range(N):
    found += dt[n - A[n]]
    dt[n + A[n]] += 1
print(found)
### BUGGY CODE ###

n = input()
 
S = [int(x) for x in raw_input().split()]
 
q = input()
 
T = [int(x) for x in raw_input().split()]
 
C = 0
 
for i in T:
 for j in S:
  if i==j:
   C += 1
   break
 
print C

### FIXED CODE ###

n = input()
  
S = [int(x) for x in raw_input().split()]
  
q = input()
  
T = [int(x) for x in raw_input().split()]
  
C = 0

 
for key in T:
  left = 0
  right = n
  while left<right:
    mid = (right + left)/2
    if key==S[mid]:
      C += 1
      break
    elif key<S[mid]:
      right = mid
    elif key>S[mid]:
      left = mid+1
 

print C
### BUGGY CODE ###

n = int(input())
lis = list(map(int, input().split()))
print(*[1+lis.index(i) for i in range(1, n+1)])


### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
a = [0]*n

for i, item in enumerate(lis):
    a[item - 1] = i + 1

print(*a)
### BUGGY CODE ###

import bisect

N=int(input())

line=[-1]*10**5

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line[0]=A
    else:
        line[index-1]=A
    line.sort()
    #print(line)
ans=[]
while line:
    num=line.pop(-1)
    if num==-1:
        break
    else:
        ans.append(num)

print(len(ans))

### FIXED CODE ###

import bisect
import collections

N=int(input())

line=collections.deque()

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.appendleft(A)
    else:
        line[index-1]=A
    #print(line)
    
    #print(line)

print(len(line))
### BUGGY CODE ###

n,m = map(int, input().split())
dic = {}
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    
    if a in dic.keys():
        tmp = dic[a]
        tmp.append(b)
        dic[a] = tmp
    else:
        tmp = [b]
        dic[a] = tmp
    
    if b in dic.keys():
        tmp = dic[b]
        tmp.append(a)
        dic[b] = tmp
    else:
        tmp = [a]
        dic[b] = tmp

dist = {}
queue = []
visited = []
pre = {}

dist[0] = 0 
queue.append(0)

while len(queue) > 0:
    v = queue.pop(0)
    
    for i in dic[v]:
        if i in visited:
            continue
        
        visited.append(i)
        dist[i] = dist[v] + 1
        pre[i]= v
        queue.append(i)


print("Yes")
for i in range(n):
    ans = 0
    
    if(i == 0):
        continue
    
    ans = pre[i]
    ans += 1
    print(ans)

### FIXED CODE ###

from collections import deque

n,m = map(int, input().split())
dic = {}

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

dic = [[] for _ in range(n + 1)]

for a,b in AB:
    a -= 1
    b -= 1

    dic[a].append(b)
    dic[b].append(a)

#dist = {}
queue = deque([0])
visited = []
pre = [-1] * (n+1)

#dist[0] = 0 
queue.append(0)

while queue:
    v = queue.popleft()
    
    for i in dic[v]:
        if pre[i] == -1:
        #dist[i] = dist[v] + 1
            pre[i]= v
            queue.append(i)

print("Yes")
for i in range(n):
    ans = 0
    
    if(i == 0):
        continue
    
    ans = pre[i]
    ans += 1
    print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
A = []
from collections import Counter
d = Counter(S)
for key, value in d.items():
    if value == max(d.values()):
        A.append(key)
As = sorted(A)
for i in range(len(As)):
    print(As[i])

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
A = []
from collections import Counter
d = Counter(S)
md = d.most_common(1)[0][1]
for key, value in d.items():
    if value == md:
        A.append(key)
As = sorted(A)
for a in As:
    print(a)
### BUGGY CODE ###

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

import sys
input = sys.stdin.readline
mod = 10**9+7  
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a = sorted(a)
a = tuple(a)

ans = 0
for i in range(n):
  p = a[i]*comb(n-1-i,k-1,mod)
  q = a[i]*comb(i,k-1,mod)
  if n-i < k:
    p = 0
  if i < k-1:
    q = 0
  #print(p,q)
  ans += (q%mod)
  ans -= (p%mod)
  ans %= mod
print(ans)

### FIXED CODE ###

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        # モジュラ逆数の性質
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

import sys
input = sys.stdin.readline
mod = 10**9+7  
n,k = [int(i) for i in input().split()]
fact, fact_inv = make_array_for_comb(n,mod)
a = [int(i) for i in input().split()]
a = sorted(a)
a = tuple(a)

ans = 0
for i in range(0,n-k+1):
  p = a[i]*comb(n-1-i,k-1,mod)
  ans -= (p%mod)
  ans %= mod
for i in range(k-1,n):
  q = a[i]*comb(i,k-1,mod)
  ans += (q%mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    for i in range(min(k,N)):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    d = {}
    for i in range(N):
        if S[i] == 'D':
            d[i] = MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if i+k < N:
            if S[i+k] == 'M':
                M += 1
            elif S[i+k] == 'C':
                C += 1
                MC += M
    res = 0
    for i in d:
        res += d[i]

    return res
        
Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

### FIXED CODE ###

N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))