Harryxun/stf_run huggingface dataset:
# ABC 164 E 草案
import sys
sys.setrecursionlimit(10**6)

n,m,s= map(int, input().split())
g= [list(map(int, input().split())) for i in range(m)]
# 両替所
c= [list(map(int, input().split())) for i in range(n)]

x=2501
# 作るグラフ (点,所有銀貨,必要時間)
gg=[[]*x for i in range(n)]
for i in range(n):
    for j in range(x-1):
        # 金貨を銀貨に交換
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i][j].append((i,y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        # 銀貨足りる時移動できる
        if i-a>=0:
            gg[v][i].append((u,i-a,b))
            gg[u][i].append((v,i-a,b))





#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source,gold):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [[float('inf')]*x for i in range(n)]
    distance[source][gold] = 0
    visited = [[False]*x for i in range(n)]
    pq = []
    heappush(pq, (0, source,gold))
    while pq:
        dist_v, u,v = heappop(pq)
        visited[u][v] = True
        for u,v, weight in edges[u][v]:
            if not visited[u][v]:
                new_dist = dist_v + weight
                if distance[u][v] > new_dist:
                    distance[u][v] = new_dist
                    heappush(pq, (new_dist, u,v))
    return distance
s=min(2500,s)
ans=dijkstra(gg,n,0,s)

for i in range(1,n):
    print(min(ans[i]))

### FIXED CODE ###

# ABC 164 E 草案
import sys
sys.setrecursionlimit(10**6)

n,m,s= map(int, input().split())
g= [list(map(int, input().split())) for i in range(m)]
# 両替所
c= [list(map(int, input().split())) for i in range(n)]

x=2501
# 作るグラフ (辺*所有銀貨,必要時間)
gg=[[] for i in range(n*x)]
for i in range(n):
    for j in range(x-1):
        # 金貨を銀貨に交換
        y=j+c[i][0]
        if y>=x-1:
            y=x-1
        gg[i*x+j].append((i*x+y,c[i][1]))


for i in range(1,x):
    for u,v,a,b in g:
        u-=1
        v-=1
        # 銀貨足りる時移動できる
        if i-a>=0:
            gg[v*x+i].append((u*x+i-a,b))
            gg[u*x+i].append((v*x+i-a,b))




#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance
s=min(s,2500)
ans=dijkstra(gg,n*x,s)

for i in range(1, n):
    print(min(ans[x * i:x * (i + 1)]))
def is_left_removed(i, S, td):
  direction = {'L': -1, 'R': +1}
  for t, d in td:
    if S[i] == t:
      i += direction[d]
    if i < 0:
      return True
  return False
def is_right_removed(i, S, td):
  direction = {'L': -1, 'R': +1}
  for t, d in td:
    if S[i] == t:
      i += direction[d]
    if i >= N:
      return True
  return False

N, Q = map(int, raw_input().split())
s = raw_input()
td = [raw_input().split() for _ in range(Q)]

# left
l = 0
r = N - 1
l_res = -1
while (l <= r):
  target = (r + l) / 2
  if is_left_removed(target, s, td):
    l = target + 1
    l_res = target
  else:
    r = target - 1

# right
l = 0
r = N - 1
r_res = N
while (l <= r):
  target = (r + l) / 2
  if is_right_removed(target, s, td):
    r = target - 1
    r_res = target
  else:
    l = target + 1

print N - min(N, l_res + 1 + N - r_res)

### FIXED CODE ###

def is_left_removed(i, S, td):
  direction = {'L': -1, 'R': +1}
  for t, d in td:
    if S[i] == t:
      i += direction[d]
    if i < 0:
      return True
    if i >= N:
      return False
  return False
def is_right_removed(i, S, td):
  direction = {'L': -1, 'R': +1}
  for t, d in td:
    if S[i] == t:
      i += direction[d]
    if i >= N:
      return True
    if i < 0:
      return False
  return False

N, Q = map(int, raw_input().split())
s = raw_input()
td = [raw_input().split() for _ in range(Q)]

# left
l = 0
r = N - 1
l_res = -1
while (l <= r):
  target = (r + l) / 2
  if is_left_removed(target, s, td):
    l = target + 1
    l_res = target
  else:
    r = target - 1

# right
l = 0
r = N - 1
r_res = N
while (l <= r):
  target = (r + l) / 2
  if is_right_removed(target, s, td):
    r = target - 1
    r_res = target
  else:
    l = target + 1

print N - min(N, l_res + 1 + N - r_res)
N,K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
minToatalCostList = [0 for i in range(N)]
minToatalCostList[0] = 0

for i in range(1,N) :
	for j in range(1,K+1) :
		if j <= i and minTotalCostList[i] != 0 and j != 1 :
			minToatalCostList[i] = min(minToatalCostList[i], (abs(h[i] - h[i-j]) + minToatalCostList[i-j] ))
		elif j > i or minToatalCostList[i] == 0 :
			break
		elif j == 1 :
			minToatalCostList[i] = (abs(h[i] - h[i-j]) + minToatalCostList[i-j] )

print(minToatalCostList[N-1])

### FIXED CODE ###

N = int(input())
h = [int(i) for i in input().split()]
minToatalCostList = [0 for i in range(N)]

for i in range(N) :
	if i > 1 :
		minToatalCostList[i] = min( abs(h[i] - h[i-1]) + minToatalCostList[i-1], abs(h[i] - h[i-2]) + minToatalCostList[i-2] )
	elif i == 1:
		minToatalCostList[i] = abs(h[i] - h[i-1])
	else :
		minToatalCostList[i] = 0

print(minToatalCostList[N-1])
n,q=map(int,input().split())
s=input()
c=[0]
t=0
for i in range(1:N):
    t+=1 if (s[i-1]=='A' and s[i]=='C') else 0
    c.append(t)
for i in range(q):
    l,r=map(int,input().split())
    print(c[r]-c[l])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0]
t=0
for i in range(1,n):
    t+=1 if (s[i-1]=='A' and s[i]=='C') else 0
    c.append(t)
for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])
from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0 and K%2:
    ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    print(ans)
    exit()
assert False


### FIXED CODE ###

from functools import reduce

N, K = map(int, input().split())
A = list(map(int, input().split()))
Ap = [a for a in A if a>0]
Am = [a for a in A if a<0]
mod = 10**9+7
if len(Ap) + len(Am) < K:
    print(0)
    exit()
if len(Ap) + len(Am) == K:
    if 0 in A and len(Am) % 2:
        print(0)
    else:
        ans = reduce(lambda a, b: a * b % mod, Ap+Am, 1)
        print(ans)
    exit()
Ap.sort(reverse=True)
Am.sort()
if len(Ap) == 0:
    if K%2:
        if 0 in A:
            ans = 0
        else:
            ans = reduce(lambda a, b: a*b%mod, Am[-K:], 1)
    else:
        ans = reduce(lambda a, b: a*b%mod, Am[:K], 1)
    print(ans)
    exit()

idx_Am = 0
n = 0
ans = 1
for idx_Ap, ap in enumerate(Ap+[0]):
    while idx_Am < len(Am) and n < K and -Am[idx_Am] > ap:
        ans = ans * Am[idx_Am] % mod
        idx_Am += 1
        n += 1
    if n == K:
        break
    n += 1
    idx_Ap += 1
    ans = ans * ap % mod
    if n == K:
        break
else:
    assert False
if idx_Am % 2 == 0:
    print(ans)
else:
    if idx_Ap == len(Ap) or (idx_Am != len(Am) and idx_Ap > 0 and Am[idx_Am] * Am[idx_Am-1] > Ap[idx_Ap] * Ap[idx_Ap-1]):
        ans = ans * Am[idx_Am] * pow(Ap[idx_Ap-1], mod-2, mod) % mod
    else:
        ans = ans * Ap[idx_Ap] * pow(Am[idx_Am-1], mod-2, mod) % mod
    print(ans)
import numpy

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

lcm = int(a * b / numpy.gcd(a, b))
print(lcm)

### FIXED CODE ###

import fractions

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

lcm = int(a * b / fractions.gcd(a, b))
print(lcm)
n = int(input())
p = list(range(n+1))

for i in range(n):
    p[i], p[n] = map(int, input().split())

# table[i][j] : M_i??????M_j??????????????????????°?????????°
table = [[0] * n for i in range(n)]

# ??£????????£???2????????????????????????
for i in range(n-1):
    table[i][i+1] = p[i]*p[i+1]*p[i+2]


for k in range(3, n+1):    # ?????????k???????????????????????????
    for i in range(n+1-k): # M_i?????????
        j = i + k - 1      # M_j?????§???k??????

        table[i][j] = float('inf')

        for x in range(i, j+1): # M_i~M_x??¨M_(x+1)~M_j??§????????????(i<=x<=k)
            cost = table[i][x] + table[x+1][j] + p[i]*p[x+1]*p[j+1]
            table[i][j] = min(table[i][j], cost)
            

print(table[1][n])

### FIXED CODE ###

n = int(input())
p = list(range(n+2))

for i in range(1,n+1):
    p[i], p[n+1] = map(int, input().split())

# table[i][j] : M_i??????M_j??????????????????????°?????????°
table = [[0] * (n+1) for i in range(n+1)]

# ??£????????£???2????????????????????????
for i in range(1,n):  # 1<=i,i+1<=n
    table[i][i+1] = p[i]*p[i+1]*p[i+2]


for k in range(3, n+1):    # ?????????k???????????????????????????3<=k<=n
    for i in range(1,n+2-k): # M_i?????????1<=i<=n-k+1
        j = i + k - 1      # M_j?????§???k??????

        table[i][j] = float('inf')

        for x in range(i, j): # M_i~M_x??¨M_(x+1)~M_j??§????????????(i<=x,x+1<=j<=n)
            # print(i, x, j)
            cost = table[i][x] + table[x+1][j] + p[i]*p[x+1]*p[j+1]
            table[i][j] = min(table[i][j], cost)
            

print(table[1][n])
import math
a, b ,c = map(int, input().split())
aa = math.sqrt(a)
bb = math.sqrt(b)
cc = math.aqrt(c)
if (c-a-b-2*aa*bb)/(cc+aa+bb)>0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import math
a, b ,c = map(int, input().split())
if 4*a*b < (c-a-b)**2 and (c-a-b) >0:
    print('Yes')
else:
    print('No')
def dfs(GF,group,gn,i):
    size = 1
    group[i]=gn
    for node in GF[i]:
        if group[node]==-1:
            group[node]=gn
            size+=dfs(GF,group,gn,node)
    return size

def main():
    from sys import stdin
    n,m,k = map(int,stdin.readline().rstrip().split())
    F=[]
    for _ in range(m):
        F.append(list(map(int,stdin.readline().rstrip().split())))
    GF = [[] for _ in range(n+1)]
    for a,b in F:
        GF[a].append(b)
        GF[b].append(a)
    
    B=[]
    for _ in range(k):
        B.append(list(map(int,stdin.readline().rstrip().split())))
    GB = [[] for _ in range(n+1)]
    for a,b in B:
        GB[a].append(b)
        GB[b].append(a)    

    U = []
    group= [-1]*(n+1)
    gn = 0

    for i in range(1,n+1):
        if group[i] == -1:
            sz = dfs(GF,group,gn,i)
            gn+=1
            U.append(sz)
    
    for i in range(1,n+1):
        g = group[i]
        ans = U[g]-1-len(GF[i])

        for b in GB[i]:
            if group[b]==g:
                ans-=1
        print(ans,end=" ")
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(GF,group,gn,i):
    size = 1
    group[i]=gn
    for node in GF[i]:
        if group[node]==-1:
            group[node]=gn
            size+=dfs(GF,group,gn,node)
    return size

def main():
    from sys import stdin
    n,m,k = map(int,stdin.readline().rstrip().split())
    F=[]
    for _ in range(m):
        F.append(list(map(int,stdin.readline().rstrip().split())))
    GF = [[] for _ in range(n+1)]
    for a,b in F:
        GF[a].append(b)
        GF[b].append(a)
    
    B=[]
    for _ in range(k):
        B.append(list(map(int,stdin.readline().rstrip().split())))
    GB = [[] for _ in range(n+1)]
    for a,b in B:
        GB[a].append(b)
        GB[b].append(a)    

    U = []
    group= [-1]*(n+1)
    gn = 0

    for i in range(1,n+1):
        if group[i] == -1:
            sz = dfs(GF,group,gn,i)
            gn+=1
            U.append(sz)
    
    for i in range(1,n+1):
        g = group[i]
        ans = U[g]-1-len(GF[i])

        for b in GB[i]:
            if group[b]==g:
                ans-=1
        print(ans,end=" ")
main()
import math

N=int(input())
l=10**9+7
nums=list(map(int,input().split()))
k=int(math.log2(max(nums)))+1
mat=[]
for each in nums:
    num=str(bin(each))[2:].zfill(k)
    mat.append(list(num))
 
mat=list(zip(*mat))
ans=0
 
for i in range(k):
    b=mat[i].count("1")
    ans+=b*(N-b)*pow(2,(k-i-1),l)
print(ans%l)

### FIXED CODE ###

mod=10**9+7
N=int(input())
str_a = ''.join(['{:060b}'.format(a) for a in map(int, input().split())])

ans=0
for i in range(60):
    ones=str_a[59-i::60].count("1")
    ans+= pow( 2, i ,mod)* ones *(N-ones)
print(ans%mod)
import numpy as np


def solve(n, pts):
    ans = [0] * n

    div = 200000
    a = np.linspace(0, 2 * np.pi, div)
    b = np.dot(pts, [np.sin(a), np.cos(a)])
    c = np.argmax(b, axis=0)
    for i, v in zip(*np.unique(c, return_counts=True)):
        ans[i] = v / div
    return ans


n = int(input())
pts = [list(map(int, input().split())) for _ in range(n)]
print('\n'.join(map(str, solve(n, pts))))


### FIXED CODE ###

import numpy as np
from scipy.spatial import ConvexHull
from scipy.spatial.qhull import QhullError


def solve(n, pts):
    ans = [0] * n

    try:
        hull = ConvexHull(pts)
    except QhullError:
        lm = np.argmin(pts, axis=0)
        rm = np.argmax(pts, axis=0)
        if lm[0] != rm[0]:
            l, r = lm[0], rm[0]
        elif lm[1] != rm[0]:
            l, r = lm[1], rm[0]
        else:
            l, r = lm[0], rm[1]
        ans[l] = ans[r] = 0.5
        return ans

    ps = np.array(list(map(pts.__getitem__, hull.vertices)))
    vs = ps - np.roll(ps, 1, axis=0)

    vt = vs.T
    vt[0] *= -1
    arcs = np.arctan2(*vt)
    arcs = np.append(arcs, arcs[0])
    da = np.diff(arcs) / (2 * np.pi) % 1

    for i, a in zip(hull.vertices, da):
        ans[i] = a

    return ans


n = int(input())
pts = [list(map(int, input().split())) for _ in range(n)]
print('\n'.join(map(str, solve(n, pts))), end='')
N = int(input())
L = [int(i) for i in input().split()]
M = max(L)
Z_L = list()
for i in range(1, M):
  ZZ = 0
  for j in range(N):
    Z =  pow(L[j] - i, 2)
    ZZ += Z
  Z_L.append(ZZ)
print(min(Z_L))

### FIXED CODE ###

N = int(input())
L = [int(i) for i in input().split()]
M = max(L)
A = min(L)
Z_L = list()
for i in range(A, M + 1):
  ZZ = 0
  for j in range(N):
    Z =  pow(L[j] - i, 2)
    ZZ += Z
  Z_L.append(ZZ)
print(min(Z_L))
from collections import Counter

N = int(input())

index = 0
even_numbers = []
odd_numbers = []

for i in input().split():
    if index % 2 == 0:
        even_numbers.append(int(i))
    else:
        odd_numbers.append(int(i))
    index += 1

even = Counter(even_numbers).most_common(2)
odd = Counter(odd_numbers).most_common(2)

if even[0][1] == odd[0][1]:
    print(min(N - even[0][1] - odd[1][1], N - even[1][1] - odd[0][1]))
else:
    print(N - even[0][1] - odd[0][1])


### FIXED CODE ###

from collections import Counter

N = int(input())

index = 0
even_numbers = []
odd_numbers = []

for i in input().split():
    if index % 2 == 0:
        even_numbers.append(int(i))
    else:
        odd_numbers.append(int(i))
    index += 1

even = Counter(even_numbers).most_common(2)
odd = Counter(odd_numbers).most_common(2)

if even[0][0] == odd[0][0]:
    if len(even) == 1:
        print(N//2)
    else:
        print(N - even[0][1] - max(even[1][1], odd[1][1]))
else:
    print(N - even[0][1] - odd[0][1])
t = int(input())
wlist = [0]*4
for i in range(t):
    w = input()
    if w == "AC":
        wlist[0] += 1
    elif w == "WA":
   	    wlist[1] += 1
    elif w == "TEL":
        wlist[2] += 1
    else:
        wlist[3] += 1
print("AC x " + wlist[0])
print("WA x " + wlist[1])
print("TEL x " + wlist[2])
print("RE x " + wlist[3])

### FIXED CODE ###

t = int(input())
wlist = [0]*4
for i in range(t):
    w = input()
    if w == "AC":
        wlist[0] += 1
    elif w == "WA":
        wlist[1] += 1
    elif w == "TLE":
        wlist[2] += 1
    else:
        wlist[3] += 1
print("AC x " + str(wlist[0]))
print("WA x " + str(wlist[1]))
print("TLE x " + str(wlist[2]))
print("RE x " + str(wlist[3]))
import math
n,k=map(int,input().split())
mod=pow(10,9)+7
ans=0
l=[0]*(k+1)

for i in reversed(range(1,k+1)):
    l[i]=pow(math.floor(k/i),n)%mod
    a=2*i
    while a<=k:
        l[i]-=l[a]
        a+=i
    ans+=l[i]*i%mod

for i in range(n+1):
    print(i,l[i])

print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
mod=10**9+7
ans=0
l=[0]*(k+1)
 
for i in range(k,0,-1):
    l[i]=pow(k//i,n,mod)
    for j in range(2*i,k+1,i):
        l[i]-=l[j]
        l[i]%=mod
    ans+=l[i]*i
    ans%=mod
 
print(ans)
s = list(input())
k = int(input())
sub = []
sub += s[:]
 
for j in range(2,K+1):
    charGram = [''.join(s[i:i+j]) for i in range(len(s)-1)]
    sub += charGram
sub = list(set(sub))
print(sorted(sub)[k-1])

### FIXED CODE ###

s = list(input())
k = int(input())
sub = []
sub += s[:]
 
for j in range(2,k+1):
    charGram = [''.join(s[i:i+j]) for i in range(len(s)-1)]
    sub += charGram
sub = list(set(sub))
print(sorted(sub)[k-1])
# -*- coding: utf-8 -*-

# input
N = int(input())
L = list(map(int, input().split()))

# solve
ans = 0
L.sort()
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(k + 1, N):
            if L[k] < L[j] + L[i]:
                ans += 1

# output
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect

# input
N = int(input())
L = list(map(int, input().split()))

# solve
ans = 0
L.sort()
for i in range(N):
    for j in range(i + 1, N):
        r = bisect.bisect_left(L, L[i] + L[j])
        l = j + 1
        ans += max(0, r - l)

# output
print(ans)
import os, sys, re, math

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

candle = list(map(int,input().split(' ')))
ret = math.inf

for i in range(N-K+1):
    s = candle[i]
    e = candle[i+K-1]
    if e < 0:
        ret = min(-s, ret)
    elif s > 0:
        ret = min(e, ret)
    else:
        ret = min(-s*2+e, -s+e*2, ret)

print(ret)


### FIXED CODE ###

import os, sys, re, math

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

candle = list(map(int,input().split(' ')))
ret = float('inf')

for i in range(N-K+1):
    s = candle[i]
    e = candle[i+K-1]
    if e < 0:
        ret = min(-s, ret)
    elif s > 0:
        ret = min(e, ret)
    else:
        ret = min(-s*2+e, -s+e*2, ret)

print(ret)
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007


def step_state(n, broken):
    if n == 0:
        return 1
    elif n == 1:
        if broken[1]:
            return 0
        else:
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            return 0
        elif broken[n - 1]:
            return step_state(n-2, broken) % MOD
        elif broken[n-2]:
            return step_state(n-1, broken) % MOD
        else:
            return (step_state(n-1, broken)+step_state(n-2, broken)) % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

### FIXED CODE ###

if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])

   MOD = 1000000007

   dp = [0 for i in range(n+1)]
   dp[0] = 1
   if 1 in a:
      dp[1] = 0
   else:
      dp[1] = 1

   for i in range(2,n+1):
      if (i-1 in a) and (i-2 in a):
         dp[i] = 0
      elif i-1 in a:
         dp[i] = dp[i-2] % MOD
      elif i-2 in a:
         dp[i] = dp[i-1] % MOD
      else:
         dp[i] = (dp[i-1] + dp[i-2]) % MOD

   print(dp[n])
literal = ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
           'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z')
x = int(input())
str2 = ''
str3 = ''
q = x
while q > 26:
    q, mod = divmod(x, 26)
    str1 = ''
    if q > 26:
        x = q
        str1 = literal[mod - 1]
        str3 = str1 + str2
        str2 = str3
        str3 = ''
    else:
        str1 += literal[q - 1]
        str1 += literal[mod - 1]
        str3 = str1 + str2
print(str3)

### FIXED CODE ###

a = input()
if a.islower():
    print('a')
else:
    print('A')
import numpy as np

N = int(input())
d = list(map(int, input().split()))

ans = 0
for K in range(1, 10**5+1):
  if np.sum(d[d>=K]) == np.sum(d[d<K]): ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
d = list(map(int, input().split()))

d = sorted(d)
print(d[N//2] - d[(N//2)-1])
from string import ascii_lowercase as alph

def gen_pattern(N, pre="", m=-1):
  for i, c in enumerate(alph[:m+2]):
    pat = pre+c
    if len(pattern) == N:
      yield pattern
    else:
      yield from gen_pattern(N, pat, max(i,m))

for pattern in gen_pattern(int(input())):
  print(pattern)


### FIXED CODE ###

from itertools import product, combinations_with_replacement
N=int(input())
s="abcdefghij"
 
def get_gen(a, N):
  for c in s[:s.index(max(a))+2 if a else 1]:
    t = a+c
    if len(t) == N:
      print(t)
    else:
      get_gen(t,N)

get_gen("", N)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
from sys import stdin
import math
 
# 標準入力をスペースで区切って、intに変換 listに収納
#int_list  = [int(x) for x in stdin.readline().rstrip().split()]
N = int(input())
 
total = int(N*(N-1)/2)
print(total)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin
import math

# 標準入力をスペースで区切って、intに変換 listに収納
S = stdin.readline()
T = stdin.readline()

cnt=0
for i in range(3):
    if S[i] == T[i]:
        cnt+=1


print(cnt)
x = input()
print(x^3)


### FIXED CODE ###

x = int(input())
print(x**3)
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())

a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
  if i==0:
    for k in range(10):
      dp[i][(now+a[i][k])%13] = 1
  else:
    for k in range(10):
      temp = a[i][k]
      for l in range(13):
        dp[i][(l+temp)%13] += dp[i-1][l]
        dp[i][(l+temp)%13] = dp[i][(l+temp)%13]%mod
print(dp[len(a)-1][5])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

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


### FIXED CODE ###

a=input()
print a**3