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

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    num = [1] * (N - K + 1)
    for i, j in zip(range(K, N), range(1, N)):
        num[j] = num[j-1] * i // j
    
    ans = sum(a * n for a, n in zip(A[K-1:], num))
    ans -= sum(a * n for a, n in zip(A, num[::-1]))
    
    print(ans % mod)

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i * pow(j, mod - 2, mod) % mod
        ans += (A[i] - A[N-i-1]) * comb
        ans %= mod
    
    print(ans)

solve()
### BUGGY CODE ###

N = int(input())

if N%2==1:
    print(0)
    exit()
elif N==0 or N==2:
    print(0)
    exit()

index = 1
ans = 0
for i in range(2, N+1, 2):
    s = str(i)
    index2 = index
    if int(s[len(s)-1:len(s)]) == 0:
        ans += 1
    else:
        index2 *= int(s[len(s)-1:len(s)])
        s2 = str(index2)
        if int(s2[len(s2)-1:len(s2)]) == 0:
            ans += 1
        else:
            index = index2


print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

N = int(input())

if N % 2 == 1:
    print(0)
else:
    ret = 0
    for i in range(1, 27):
        ret += N // (2*5**i)


    print(ret)
### BUGGY CODE ###

import fractions
import math

a,b = map(int,input().split())

if a>b:
  a,b = b,a
  
n=fractions.gcd(a,b)

d = [1]
num = 2

while n>1:
  if n%num == 0:
    d.append(num)
  while n%num == 0:
    n = n//num
  num+=1
  
print(len(d))

### FIXED CODE ###

def main():
  import fractions
  import math

  a,b = map(int,input().split())
  g = fractions.gcd(a,b)
  
  d = [1]
  num = 2

  while num**2 <= g:
    #print("num",num)
    if g%num == 0:
      d.append(num)
    while g%num == 0 and g>1:
      g = g//num
      #print(g)
    num += 1
  
  print(len(d) + (g > 1))

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

R, G, B, N = map(int, input().split())
counter = 0
r = N // R + 1
for s in range(r):
	g = (N - s*R) // G + 1
	for t in range(g):
		if s*R + t*G <= N and (N - (s*R + t*G)) % B == 0:
			counter += 1
print(counter)


### FIXED CODE ###

r, g, b, n = map(int, input().split())
counter = 0
for s in range(n+1):
  for t in range(n-s+1):
    u = n - r*s - g*t
    if u >= 0 and u % b == 0:
      counter += 1
print(counter)
### BUGGY CODE ###

from math import factorial
MOD = 10**9 + 7

# 階乗を用意
fact = [1] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD

def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    global fact
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = fact[n]
    b = fact[k]
    c = fact[n-k]
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p

def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p

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


a.sort()

ans = 0

# pos
for i in range(1, n):
    ans += a[i] * comb(i, k-1, MOD)
    ans %= MOD

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



### FIXED CODE ###

from math import factorial
MOD = 10**9 + 7

# 階乗を用意
fact = [1] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD

def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    global fact
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = fact[n]
    b = fact[k]
    c = fact[n-k]
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p

def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p

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

ans = 0

# pos
for i in range(n-1):
    c = comb(n-1-i, k-1, MOD)
    ans += a[n-1-i] * c
    ans %= MOD
    ans -= a[i] * c
    ans %= MOD
print(ans)
### BUGGY CODE ###

#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = [int(input()) for _ in range(n)]

    lsbs = []
    for a in al:
        if len(lsbs) == 0:
            lsbs.append([a])
        else:
            added = False
            for lsb in lsbs:
                if lsb[-1] < a:
                    lsb.append(a)
                    added = True
                    break
            if not added:
                lsbs.append([a])
    print(len(lsbs))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = [int(input()) for _ in range(n)]

    lsbs = deque()
    for a in al:
        pos = bisect.bisect_left(lsbs, a)
        if pos == 0:
            lsbs.appendleft(a)
        else:
            if pos == len(lsbs):
                lsbs[-1] = a
            else:
                lsbs[pos-1] = a
        # print(lsbs)
    print(len(lsbs))


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

a=1;c={"R":0,"G":0,"B":0}
m=998244353
for i in range(1,int(input())+1):
	a*=i%m
for i in input():
	s=sorted(c.values())
	c[i]+=1
	if c[i]>s[2]:pass
	elif c[i]>s[1]:a*=s[2]-s[1]
	else:a*=s[1]-s[0]
	a%=m
print(a)

### FIXED CODE ###

import math
n=int(input())
c={"R":0,"G":0,"B":0}
a=1
mod=998244353
for i in input():
	s=sorted((c["R"],c["G"],c["B"]))
	c[i]+=1
	if c[i]>s[2]:
		pass
	elif c[i]>s[1]:
		a*=s[2]-s[1]
	else:
		a*=s[1]-s[0]
	a%=mod
print(math.factorial(n)*a%mod)
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [10**10]*(N+1)
dp[1] = 0
dp[2] = abs(h[0] - h[1])

for i in range(3,N+1):
  Kl = max(1,i-K)
  dp[i] = min([dp[j]+abs(h[j-1] - h[i-1]) for j in range(Kl, i)])
print(dp[N])

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [10**10]*(N+1)
dp[1] = 0
dp[2] = abs(h[0] - h[1])

for i in range(3,N+1):
  Kl = max(1,i-K)
  dp[i] = min([dp[j]+abs(h[j-1] - h[i-1]) for j in range(Kl, i)])
print(dp[N])
### BUGGY CODE ###

import sys

MAX_VALUE = 10 ** 5 + 100

def input():
    return sys.stdin.readline().strip()

def main():
    N,W = map(int,input().split())
    goods = [list(map(int,input().split())) for _ in range(N)]
    
    dp = [[float('inf') for _ in range(MAX_VALUE+1)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(MAX_VALUE):
            if v >= goods[i][1]:
                dp[i+1][v] = min(dp[i][v-goods[i][1]]+goods[i][0],dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    for v in range(MAX_VALUE):
        if dp[N][v] <= W:
            ans = v
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

MAX_VALUE = 10 ** 5 + 100

def input():
    return sys.stdin.readline().strip()

def main():
    N,W = map(int,input().split())
    goods = [list(map(int,input().split())) for _ in range(N)]
    
    dp = [[float('inf') for _ in range(MAX_VALUE+1)] for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for v in range(MAX_VALUE):
            if v >= goods[i][1]:
                dp[i+1][v] = min(dp[i][v-goods[i][1]]+goods[i][0],dp[i][v])
            else:
                dp[i+1][v] = dp[i][v]
    for v in range(MAX_VALUE):
        if dp[N][v] <= W:
            ans = v
    print(ans)

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

N = int(input())
S = []
for i in range(N):
  S.append(''.join(sorted(input())))

ans = 0
for i in range(N-1):
  for j in range(1+i,N):
    if S[i]==S[j]:
      ans += 1
print(ans)
    
  

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  S.append(''.join(sorted(input())))

import collections
import math

c = collections.Counter(S)
ans = 0
for i in c.values():
    if i == 1:
      continue
    else:
      ans += i*(i-1)//2
print(int(ans))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
l1=[]
#print(a,end=" a\n")
#print(b,end=" b\n")

l1=list([i+j for i in a for j in b])
l1.sort(reverse=True)
#for i in a:
#  for j in b:
#    # print(i,j)
#    l1.append(i+j)
#l1.sort(reverse=True)
#print(l1)
l1=l1[:min(len(l1),k)]
l2=list([i+j for i in l1 for j in c])
#l2=[]
#for i in l1:
#  for j in c:
#    l2.append(i+j)
l2.sort(reverse=True)
#print(l2)
#print("\n".join(map(str,l2[:k])))
for i in l2[:k]:
  print(i)


### FIXED CODE ###

import sys
input=sys.stdin.readline
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
l1=sorted([i+j for i in a for j in b],reverse=True)[:k]
l2=sorted([i+j for i in l1 for j in c],reverse=True)[:k]
for i in l2:
  print(i)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = I()
    sli = [input() for i in range(n)]
    setli = set(sli)
    rank = defaultdict(lambda: 0)
    for i in setli:
        j = sli.count(i)
        rank[i] = j
    for i in sorted([k for k, v in rank.items() if v == max(rank.values())]):
        print(i)


# Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = I()
    sli = [input() for i in range(n)]
    rank = defaultdict(lambda: 0)
    for i in sli:
        rank[i] += 1
    rank = list(rank.items())
    rank.sort(key=lambda x: (-x[1], x[0]))
    for i, j in rank:
        if j == rank[0][1]:
            print(i)


# Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N = int(input())
X = input()

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

for i in range(N):
    if X[i] == '0':
        res = (plu + (1 << (N-1-i)) % (pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        res = (mai - (1 << (N-1-i)) % (pop-1)) % (pop-1)
    print(arr[res] + 1)

### FIXED CODE ###

N = int(input())
X = input()

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

#bi = 1 << N
for i in range(N):
    #bi = bi >> 1
    if X[i] == '0':
        #res = (plu + bi % (pop+1)) % (pop+1)
        res = (plu + pow(2, N-1-i, pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        #res = (mai - bi % (pop-1)) % (pop-1)
        res = (mai - pow(2, N-1-i, pop-1)) % (pop-1)
    print(arr[res] + 1)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
D = []
L = [0] * N
Ans = 0
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

for i in D:
  if 1 not in L[i[0]:i[1]]:
    L[i[1]-1] = 1
    Ans += 1
print(Ans)

### FIXED CODE ###

N, M = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[1]-1
    Ans += 1
print(Ans)
### BUGGY CODE ###

import sys
 
def kensho(x,tlist):
    for lis in tlist:
        if((x>>(lis[1]-1)) & 1 == lis[2]):
            pass
        else:
            return -1
 
    return bin(x).count('1')
 
 
def main():
    N = int(input())
    xy=[]
    ans=0
 
    for i in range(1,N+1):
        An= int(input())
        for j in range(0,An):
            x, y = map(int, input().split())
            xy.append([i,x,y])
 
    cnt = N
 
    tlist=[]
    for x in range (2 ** cnt):
        for y in range(cnt):
            if((x>>y) & 1):
                for z in xy:
                    if(z[0]==y+1):
                        tlist.append(z)
 
        anstack = kensho(x,tlist)
        if(ans<anstack):
            ans=anstack
 
        del tlist[:]
 
    print(ans)
 
main()

### FIXED CODE ###

import sys

def kensho(x,tlist):
    for lis in tlist:
        if((x>>(lis[1]-1)) & 1 == lis[2]):
            pass
        else:
            return -1

    return bin(x).count('1')


def main():
    N = int(input())
    xy=[]
    ans=0

    for i in range(1,N+1):
        An= int(input())
        for j in range(0,An):
            x, y = map(int, input().split())
            xy.append([i,x,y])

    cnt = N

    tlist=[]
    for x in range (2 ** cnt):
        for y in range(cnt):
            if((x>>y) & 1):
                for z in xy:
                    if(z[0]==y+1):
                        tlist.append(z)

        anstack = kensho(x,tlist)
        if(ans<anstack):
            ans=anstack

        del tlist[:]

    print(ans)

main()
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:

        cnt = costs[p]

        for c in childs_list[p]:
            if cnt+1 > costs[c]:
                costs[c] = cnt+1
                # l.append( c ) 
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))
        
        



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
g = [ list(map(lambda x: int(x)-1, input().split())) for _ in range(M) ]

from collections import Counter, defaultdict
childs  = Counter( x[1] for x in g)
childs_list  = defaultdict(list)

for x,y in g:
    childs_list[x].append(y)
roots = []
for i in range(N):
    if childs[i] == 0:
        roots.append(i)

l = [ i for i in roots]
costs = [ 0 for _ in range(N)]

while l: 

    nex_stack = []
    # p = l.pop()
    for p in l:
        # cnt = costs[p]
        for c in childs_list[p]:
            costs[c] = max(costs[p]+1, costs[c])
            childs[c] -= 1
            if childs[c] == 0:
                nex_stack.append(c)
    
    l = nex_stack


print(max(costs))
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
ans = 0
while A:
    tmp = A[0]
    if len(A) > 1:
        if tmp not in A[1:]:
            ans += 1
        A = [a for a in A[1:] if a % tmp != 0]
    else:
        ans += 1
        break
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
counter = Counter(A)
ans = 0
cache = set()
for a in A:
    if a in cache:
        continue
    tmp = a
    while tmp <= 10**6:
        cache.add(tmp)
        tmp += a
    if counter[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    for i in sousa:
        d.extend([i[1]] * i[0])

    d.sort()
    dIdx = len(d) - 1

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx -= 1
            if dIdx < 0:
                break

    print(sum(a))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import operator

input=sys.stdin.readline

def main():
    n,m = map(int, input().split())
    a = [int(i) for i in input().split()]
    sousa = []
    d = []
    for _ in range(m):
        sousa.append([int(i) for i in input().split()])

    a.sort()
    
    sousa.sort(key=operator.itemgetter(1), reverse = True)

    for i in sousa:
        d.extend([i[1]] * i[0])
        if len(d)>n:
            break

    dIdx = 0
    dLen = len(d)

    for i in range(len(a)):
        if a[i] < d[dIdx]:
            a[i] = d[dIdx]
            dIdx += 1
            if dIdx >= dLen:
                break

    print(sum(a))

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

n,m= map(int,input().split())
par = [-1]*(n)
def find(x):
    if par[x]<0:return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    px,py=find(x),find(y)
    if px==py:return False
    else:
        if px<py:px,py=py,px
        par[px]+=par[py]
        par[py]=px
        return True
p= list(map(int,input().split()))
for i in range(m):
    x,y= map(int,input().split())
    unite(x-1,y-1)
gr={}
for c in range(n):#par:
    ap=find(c)
    gr[ap]=gr.get(ap,[])+[c]
g=0
for key in gr.keys():
    temp=[p[index]-1 for index in gr[key]]
    newset = set(gr[key]) & set(temp)
    g+=len(newset)
print(g)

### FIXED CODE ###

n,m= map(int,input().split())
par = [-1]*(n)
def find(x):
    if par[x]<0:return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    px,py=find(x),find(y)
    if px==py:return False
    else:
        if px<py:px,py=py,px
        par[px]+=par[py]
        par[py]=px
        return True
p= list(map(int,input().split()))
gl=[[] for _ in range(n)]
for i in range(m):
    x,y= map(int,input().split())
    unite(x-1,y-1)
for c in range(n):#par:
    ap=find(c)
    gl[ap].append(c)
g=0
for sg in gl:
    temp=[p[index]-1 for index in sg]
    newset = set(sg) & set(temp)
    g+=len(newset)
print(g)
### BUGGY CODE ###

n = int(input())
boss = list(map(str, input().split()))
exective = sorted(set(boss))

for i in range(1, n + 1):
    if str(i) in exective:
        print(boss.count(str(i)))
    else:
        print(0)

### FIXED CODE ###

n = int(input())
boss = list(map(str, input().split()))
ans = [0] * n
for b in boss:
    ans[int(b) - 1] += 1
for a in ans:
    print(a)
### BUGGY CODE ###

MOD = 10**6+3

def main():
    # preprocess
    fac = [1, 1]
    f_inv = [1, 1]
    inv = [0, 1]

    for i in range(2, MOD+1):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

    Q = int(input())
    for i in range(Q):
        x, d, n = map(int, input().split())

        if d == 0:
            print(pow(x, n, MOD))
            continue
        
        xd = ((x % MOD) * pow(d, MOD-2, MOD)) % MOD
        if xd == 0 or xd + (n-1) >= MOD:
            print(0)
            continue

        print(pow(d, n, MOD) * fac[xd+(n-1)] * f_inv[xd - 1] % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

MOD = 10**6+3

def main():
    # preprocess
    fac = [1, 1]
    f_inv = [1, 1]
    inv = [0, 1]

    for i in range(2, MOD+1):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

    Q = int(input())
    for i in range(Q):
        x, d, n = map(int, input().split())

        if d == 0:
            print(pow(x, n, MOD))
            continue
        
        xd = (x * pow(d, MOD-2, MOD)) % MOD
        if xd == 0 or xd + (n-1) >= MOD:
            print(0)
            continue

        print(pow(d, n, MOD) * fac[xd+(n-1)] * f_inv[xd-1] % MOD)


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

# D - Digits Parade

# dp[i][j] 末尾からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート

S = input()

MOD = 10**9 + 7
dp = [[0]*13 for _ in range(len(S))]

if S[-1] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    for j in range(13):
        if j == int(S[-1]):
            dp[0][j] = 1

for i in range(2, len(S)+1):
    if S[-i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            tmp = (q_number * 10**(i-1)) % 13
            for back_number in range(13):
                dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
                dp[i-1][(tmp + back_number) % 13] %= MOD
    else:
        for back_number in range(13):
            tmp = (int(S[-i]) * 10**(i-1)) % 13
            dp[i-1][(tmp + back_number) % 13] += dp[i-2][back_number]
            dp[i-1][(tmp + back_number) % 13] %= MOD

print(dp[len(S)-1][5] % MOD)


### FIXED CODE ###

# D - Digits Parade

# dp[i][j] Sの大きい位からi桁の数で、あり得るもののうち、13で割った余りがjになるものの個数。0桁スタート
# 大きい位から順に始めないと13で割ったときの余りを求める計算量が大きくなる

S = input()

MOD = 10**9 + 7
dp = [[0]*13 for _ in range(len(S))]

if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1

for i in range(1, len(S)):
    if S[i] == "?":
        for q_number in range(10): # ?の中身としてあり得る数字
            for front_number in range(13):
                dp[i][(10 * front_number + q_number) % 13] += dp[i-1][front_number]
                dp[i][(10 * front_number + q_number) % 13] %= MOD
    else:
        for front_number in range(13):
            dp[i][(10 * front_number + int(S[i])) % 13] += dp[i-1][front_number]
            dp[i][(10 * front_number + int(S[i])) % 13] %= MOD

print(dp[len(S)-1][5] % MOD)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
d=[0]*n
d[0]=0
for i in range(1,n):
    x=l[i]
    d[i]=min([d[j]+abs(l[j]-x) for j in range(max(0,i-k),i)])
print(d[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])