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

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline

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

es = [[] for _ in range(N)]
g = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    g[a] += 1
    es[b].append(a)
    g[b] += 1

s = -1
b = -1
for i, gg in enumerate(g):
    if gg > b:
        b = gg
        s = i

gs = [0] * (N + 1)
gs[s] = -1
gs[N] = -1
visited = [False] * N
ans = 1


def rec(v, bf):
    global ans
    visited[v] = True
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if not visited[nv]:
            rec(nv, v)
    return


rec(s, N)
print(ans)
# print(gs)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


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

es = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)
### BUGGY CODE ###

n = int(input())
commands = [input().split() for _ in range(n)]

l = []
for com in commands:
    if com[0]=='insert':
        l.insert(0, com[1])
    elif com[0]=='delete':
        try:
            l.remove(com[1])
        except:
            pass
    elif com[0]=='deleteFirst':
        l.pop(0)
    elif com[0]=='deleteLast':
        l.pop()
s = ' '.join(l)
print(s)


### FIXED CODE ###

from collections import deque

n = int(input())
commands = [input() for _ in range(n)] # splitとかしてると間に合わない

l = deque()
for com in commands:
    if com[0]=='i':
        l.appendleft(com[7:])
    elif com[6]=='F':
        l.popleft()
    elif com[6]=='L':
        l.pop()
    else:
        try:
            l.remove(com[7:])
        except:
            pass

s = ' '.join(l)
print(s)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))
current = a[:]
for _ in range(k):
    next = np.array([0]*n)
    for j, v in enumerate(current):
        c = np.array([1 if j-v <= k <= j+v else 0 for k in range(n)])
        next += c
    current = next
print(*next)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
current = a[:]
for _ in range(min(42, k)):
    nex = [0]*n
    for i, v in enumerate(current):
        l = max(0, i-v)
        r = min(n-1, i+v)
        nex[l] += 1
        if r+1 < n:
            nex[r+1] -= 1
    for i in range(1, n):
        nex[i] += nex[i-1]
    current = nex

print(*current)
### BUGGY CODE ###

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


class Warshall(object):
    """ 全てのノード間の最短路を計算する """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

            for j in range(n):
                if i == j:
                    self.adjacency_dict[i][j] = 0
                else:
                    self.adjacency_dict[i][j] = float('inf')

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self):
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    self.adjacency_dict[i][j] = min(
                        self.adjacency_dict[i][j],
                        self.adjacency_dict[i][k] + self.adjacency_dict[k][j]
                    )


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    g = Warshall(N)
    g2 = Warshall(N)
    for _ in range(M):
        v1, v2, w = map(int, input().split())
        if w <= L:
            g.add_edge(v1 - 1, v2 - 1, w, undirected=True)
            g2.add_edge(v1 - 1, v2 - 1, 1, undirected=True)

    g.run()

    g2.adjacency_dict = g.adjacency_dict
    for i in range(N):
        for j in range(N):
            if g.adjacency_dict[i][j] <= L:
                g2.adjacency_dict[i][j] = 1
    g2.run()

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        ans = g2.adjacency_dict[s-1][t-1]
        if ans == float('inf'):
            print(-1)
        else:
            print(ans -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)
### BUGGY CODE ###

# import re
N, Q = map(int, input().split())
S = input()
qs = [tuple(map(int, input().split())) for _ in range(Q)]

# print(qs)

# regex =  re.compile('AC')
for q in qs:
    # print(q)
    print(S[q[0]-1:q[1]].count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
query = [list(map(int,input().split())) for _ in range(Q)]

cum_sum = [0,0]
tmp = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C":
        tmp += 1
    cum_sum.append(tmp)
# print(cum_sum)

for q in query:
    print(cum_sum[q[1]] - cum_sum[q[0]])
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
    query = input().split()

    if query[0] == '1':
        s = s[::-1]

    elif query[0] == '2' and query[1] == '1':
        s = query[2] + s

    elif query[0] == '2' and query[1] == '2':
        s += query[2]

print(s)


### FIXED CODE ###

s = input()
q = int(input())

sl = ['']*(q*2+2)
sl[q] = s
m = q-1
u = q+1
rev = False
for _ in range(q):
    query = input().split()

    if query[0] == '1' and not(rev):
        rev = True
    elif query[0] == '1' and rev:
        rev = False

    elif query[0] == '2' and query[1] == '1' and not(rev):
        sl[m] = query[2]
        m -= 1

    elif query[0] == '2' and query[1] == '1' and rev:
        sl[u] = query[2]
        u += 1

    elif query[0] == '2' and query[1] == '2' and not(rev):
        sl[u] = query[2]
        u += 1

    elif query[0] == '2' and query[1] == '2' and rev:
        sl[m] = query[2]
        m -= 1

if rev:
    sl[q] = s[::-1]
    sl.reverse()
    print(''.join(sl))
else:
    print(''.join(sl))
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XYP = [list(map(int, readline().split())) for _ in range(N)]

x_cost = [0] * ((1 << N) * N)
y_cost = [0] * ((1 << N) * N)

for bit in range(1 << N):
    for i, (xi, yi, _) in enumerate(XYP):
        x_cost[bit * N + i] = abs(xi)
        y_cost[bit * N + i] = abs(yi)

        for k, (xk, yk, _) in enumerate(XYP):
            if bit & (1 << k):
                x_cost[bit * N + i] = min(x_cost[bit * N + i], abs(xi - xk))
                y_cost[bit * N + i] = min(y_cost[bit * N + i], abs(yi - yk))

ans = [sys.maxsize for _ in range(N + 1)]

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    bit_ = bit
    while bit_ >= 0:
        bit_ &= bit
        cost = 0
        for k in range(N):
            cost += 1 * XYP[k][2] * min(x_cost[bit_ * N + k],
                                        y_cost[(bit - bit_) * N + k])
        ans[cnt] = min(ans[cnt], cost)

        bit_ -= 1
for i in range(N + 1):
    print(ans[i])

### FIXED CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XYP = [list(map(int, readline().split())) for _ in range(N)]

costs = [sys.maxsize] * N
for i, (x, y, c) in enumerate(XYP):
    costs[i] = c * min(abs(x), abs(y))

x_cost = [sys.maxsize] * ((1 << N) * N)
y_cost = [sys.maxsize] * ((1 << N) * N)

for bit in range(1 << N):
    for i, (xi, yi, _) in enumerate(XYP):
        x_cost[bit * N + i] = min(costs[i], x_cost[bit * N + i])
        y_cost[bit * N + i] = min(costs[i], y_cost[bit * N + i])
        if not (bit & (1 << i)):
            continue
        for k, (xk, yk, c) in enumerate(XYP):
            x_cost[bit * N + k] = min(x_cost[bit * N + k], abs(xi - xk) * c)
            y_cost[bit * N + k] = min(y_cost[bit * N + k], abs(yi - yk) * c)

ans = [sys.maxsize] * (N + 1)

for bit in range(1 << N):
    cnt = bin(bit).count('1')
    bit_ = bit
    while bit_ >= 0:
        bit_ &= bit
        cost = 0
        y_bit = bit - bit_
        for k in range(N):
            cost += min(x_cost[bit_ * N + k], y_cost[(y_bit) * N + k])
        ans[cnt] = min(ans[cnt], cost)

        bit_ -= 1
for i in range(N + 1):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
edge = set(tuple(map(int, input().split())) for i in range(N-1))
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]

# dist[-i]:頂点Kから頂点iまでの距離
dist = [None for i in range(N)]
dist[-K] = 0
while edge:
    rm = set()
    for a, b, c in edge:
        if dist[-a] is not None:
            dist[-b] = dist[-a] + c
            rm.add((a, b, c))
        elif dist[-b] is not None:
            dist[-a] = dist[-b] + c
            rm.add((a, b, c))
    edge -= rm

for x, y in query:
    print(dist[-x] + dist[-y])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())

adj = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    adj[-a].append((b, c))
    adj[-b].append((a, c))

Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]

# dist[-i]:頂点Kから頂点iまでの距離
dist = [0 for i in range(N)]

def dfs(v, prv, ds):
    dist[-v] = ds
    for nxt, c in adj[-v]:
        if nxt != prv:
            dfs(nxt, v, ds + c)

dfs(K, None, 0)

for x, y in query:
    print(dist[-x] + dist[-y])
### BUGGY CODE ###

def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = [0 for i in range(a[-1])]
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            prm[p_-1] += 1
    for i in range(1,len(prm)):
        if prm[i]>1:
            print('setwise coprime')
            return
    print('pairwise coprime')

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]+1):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = {}
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            if prm.get(p_)==None:
                prm[p_] = 1
            else:
                print('setwise coprime')
                return
    print('pairwise coprime')

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

def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

n= int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]

cnt=0
chkflg=True

while chkflg:

    if any(x % 4 == 0 for x in arr):

        val=max(list(filter(lambda x : x%4 ==0, arr)))        
        idx=arr.index(val)
        
        arr=[x*3 for x in arr]
        arr[idx]//=6
               
        cnt+=1
    
    elif any(x % 2 == 0 for x in arr):
    
        val=max(list(filter(lambda x : x%2 ==0, arr)))        
        idx=arr.index(val)
        
        arr=[x*3 for x in arr]
        arr[idx]//=6
        
        cnt+=1
    
    else:
        chkflg=False
        
print(cnt)      



### FIXED CODE ###

def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

n= int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]
arr01 = [x for x in arr if x % 4 ==0] 
arr02 = [x for x in arr if x % 4 !=0 and x % 2==0] 

cnt=0
if len(arr)>0:

    for i in arr01:

        while i % 2==0:

            i//=2
        
            cnt+=1
    
    cnt+=len(arr02)
   
print(cnt)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[[] for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0].append(0)
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            if dp[i][j-a[i]] == []:
                continue
            for k in range(len(dp[i][j-a[i]])):
                x = copy.deepcopy(dp[i][j-a[i]][k])
                x += 1
                dp[i+1][j].append(x)
            if j == s and len(dp[i+1][j]):
                for e in dp[i+1][j]:
                    ans += pow(2,n-e,mod)
                    ans %= mod
        for j in range(s-1,-1,-1):
            for k in range(len(dp[i][j])):
                dp[i+1][j].append(dp[i][j][k])
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0] = pow(2,n,mod)
    MODINV2 = mod_inv(2,mod)
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            dp[i+1][j] += dp[i][j-a[i]]*MODINV2
            dp[i+1][j] %= mod
        for j in range(s,-1,-1):
            if j == s:
                ans += dp[i+1][j]
                ans %= mod
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, raw_input().split())
A = map(int, raw_input().split())

AX = [0]
s = 0
for a in A:
    s += a
    AX.append(s)

result = []
for i in range(1, N+1):
    for j in range(1, N+1):
        if i <= j:
            if (AX[j] - AX[i-1]) % M == 0:
                result.append((i,j,AX[j] - AX[i-1]))
print(len(result))


### FIXED CODE ###

N, M = map(int, raw_input().split())
A = map(int, raw_input().split())

AX = []
s = 0
for a in A:
    s += a
    AX.append(s)

B = {}
B[0] = 1
for i in range(N):
    e = AX[i] % M
    if e not in B:
        B[e] = 1
    else:
        B[e] += 1

res = 0
for _,v in B.items():
    res += v * (v-1) / 2

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def rec(i, j, k):
    global dp
    if dp[i][j][k] < float("inf"):
        return dp[i][j][k]
    if i+j+k == 0:
        return 0

    num = float(i+j+k)
    ans = float(N) / num
    if i > 0:
        ans += (rec(i-1, j, k) * i) / num
    if j > 0:
        ans += (rec(i+1, j-1, k) * j) / num
    if k > 0:
        ans += (rec(i, j+1, k-1) * k) / num
    dp[i][j][k] = ans
    return ans

N = ii()
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1

dp = dp3(float("inf"), cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
dp[0][0][0] = 0

print(rec(cnt[0], cnt[1], cnt[2]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
N_f = float(N)
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1

#dp = dp3(-1.0, cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
dp = dp3(0.0, N+1, N+1, N+1)
#dp = dp3(0.0, 301, 301, 301)
dp[0][0][0] = 0

for k in range(cnt[2]+1):
#for i in range(N+1):
    for j in range(cnt[1]+cnt[2]+1-k):
    #for j in range(N+1):
        #for k in range(cnt[2]+1):
        #for k in range(N+1):
        for i in range(N+1-j-k):
            #print(i, j, k)
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

print(dp[cnt[0]][cnt[1]][cnt[2]])
### BUGGY CODE ###

h = int(input())
cnt = 0
while(True):
	if h / 2 > 0:
		cnt += 1
		h = int(h / 2)
	if h == 1:
		break
print(2 ** (cnt + 1) - 1)

### FIXED CODE ###

h = int(input())
cnt = 1
if h == 1:
	print(1)
	exit()
    
while(True):
	cnt += 1
	h = int(h / 2)
	if h == 1:
		break
print(2 ** cnt - 1)
### BUGGY CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p1 = []
p2 = []
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p1.append(a)
    p2.append(b)
d = [[1], ]
c = [[0], ]
l = 0
flag = True
for j in range(1, n):
    a = []
    b = []
    for i, t in enumerate(p1):
        for h in d[l]:
            if t == h:
                a.append(p2[i])
                b.append(t)
    for i, t in enumerate(p2):
        for h in d[l]:
            if t == h:
                a.append(p1[i])
                b.append(t)
    d.append(a)
    c.append(b)
    if len(d) > l:
        l += 1
    else:
        flag = False
        break
con = []
for i in range(2, n+1):
    for y, j in enumerate(d):
        flfl = True
        if i in j:
            for w, k in enumerate(j):
                if k == i:
                    con.append(c[y][w])
                    flfl=False
                    break
        if not flfl:
            break
    if flfl:
        con.append(0)
        break

if 0 in con:
    print('No')
else:
    print('Yes')
    for i in con:
        print(i)

### FIXED CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])
### BUGGY CODE ###

s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=(10**(n-1-i))%13
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
print(DP[n][5]%(10**9+7))

### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
      DP[i+1][k]%=mod
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)
### BUGGY CODE ###

from sys import stdin
import sys

A, B, N = [int(x) for x in stdin.readline().rstrip().split()]
# N, M = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
ans = int((A*N)/B)-A*int(N/B)
p = N//10
for i in range(p, N+1):
    temp = int((A*i)/B)-A*int(i/B)
    if temp > ans:
        # print(i)
        ans = temp

print(ans)


### FIXED CODE ###

from sys import stdin
import sys

A, B, N = [int(x) for x in stdin.readline().rstrip().split()]
# N, M = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
x=min(B-1,N)
ans = int((A*x)/B)-A*int(x/B)
print(ans)
# if N >= B:
### BUGGY CODE ###

from sys import stdin
import itertools

n = int(stdin.readline().rstrip())
l = [int(x) for x in stdin.readline().rstrip().split()]
c = itertools.combinations(l, 3)

cnt = 0
for i in c:
    a, b, c = i[0], i[1], i[2]
    if (a < b + c) and (b < c + a) and (c < a + b):
        cnt += 1

print(cnt)

### FIXED CODE ###

from sys import stdin
import bisect
        
N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
L.sort()

ans = 0
for a in range(len(L)-2):
    for b in range(a + 1, len(L)-1):
        c = bisect.bisect_left(L, L[a] + L[b])
        if c > b:
            ans += c - 1 - b

print(ans)