Harryxun/stf_run huggingface dataset:
r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

N = int(input())
K = int(input())

digit = list(map(int, str(N)))
M = len(digit)

C = 0
if M >= K:
    for i in range(K):
        C += count(digit[i], M-i, K-i)

print(C)    


### FIXED CODE ###


def factorial(a):
    r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

def COUNT(N,K):
    digit = list(map(int, str(N)))
    M = len(digit)
    C = count(digit[0], M, K)
    if len(digit) > 1:
        N_ = int("".join(map(str, digit[1:])))
    else:
        N_ = 0
    return C, N_
    

N = int(input())
K = int(input())

C = 0
while (N>0) and (K>0):
    c, N = COUNT(N, K)
    C+= c
    K-= 1

print(C)
import copy
n = int(input())
def point_shift(s,i):
    tale = len(s[p+1:])
    if tale <= i:
        return int(s[:p]+s[p+1:].ljust(i,"0"))
    else:
        return int(s[:p]+s[p+1:p+i+1])

a = []
for i in range(n):
    s = input()
    if "." not in s:
        a.append(int(s)*10**9)
    else:
        a.append(point_shift(s,9))

memo = [[0,0] for _ in range(n)]
for i in range(n):
    t = a[i]
    while t%2 == 0:
        t //= 2
        memo[i][0] += 1
    while t%5 == 0:
        t //= 5
        memo[i][1] += 1

l0 = [[0]*100 for _  in range(100)]
for i in range(n):
    l0[memo[i][0]][memo[i][1]] += 1

l1 = copy.deepcopy(l0)
for i in range(100):
    for j in range(98,-1,-1):
        l1[i][j] += l1[i][j+1]
for i in range(98,-1,-1):
    for j in range(100):
        l1[i][j] += l1[i+1][j]

ans = 0
for i in range(100):
    for j in range(100):
        x0,y0 = i,j
        x1,y1 = 18-x0,18-y0
        if x0 >= 9 and y0 >= 9:
            ans += l0[x0][y0]*(l1[x1][y1]-1)
        else:
            ans += l0[x0][y0]*l1[x1][y1]
print(ans//2)


### FIXED CODE ###

import copy
n = int(input())
def point_shift(s,i):
    p = s.index(".")
    tale = len(s[p+1:])
    if tale <= i:
        return int(s[:p]+s[p+1:].ljust(i,"0"))
    else:
        return int(s[:p]+s[p+1:p+i+1])

a = []
for i in range(n):
    s = input()
    if "." not in s:
        a.append(int(s)*10**9)
    else:
        a.append(point_shift(s,9))

memo = [[0,0] for _ in range(n)]
for i in range(n):
    t = a[i]
    while t%2 == 0:
        t //= 2
        memo[i][0] += 1
    while t%5 == 0:
        t //= 5
        memo[i][1] += 1

l0 = [[0]*100 for _  in range(100)]
for i in range(n):
    l0[memo[i][0]][memo[i][1]] += 1

l1 = copy.deepcopy(l0)
for i in range(100):
    for j in range(98,-1,-1):
        l1[i][j] += l1[i][j+1]
for i in range(98,-1,-1):
    for j in range(100):
        l1[i][j] += l1[i+1][j]


ans = 0
for i in range(100):
    for j in range(100):
        x0,y0 = i,j
        x1,y1 = max(0,18-x0),max(0,18-y0)
        if x0 >= 9 and y0 >= 9:
            ans += l0[x0][y0]*(l1[x1][y1]-1)
        else:
            ans += l0[x0][y0]*l1[x1][y1]
print(ans//2)
import math
from functools import reduce
import itertools
import numpy as np


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


K = int(input())

l = [i for i in range(1, K + 1)]

temp_1 = np.array([])
for j in itertools.combinations(l, 3):
    temp_1=np.append(temp_1,gcd_list(list(j)))

a=np.sum(temp_1)*6

temp_2 = np.array([])

for j in itertools.combinations(l, 2):
    temp_2=np.append(temp_2,gcd_list(list(j[0],j[0],j[1])))
    temp_2=np.append(temp_2,gcd_list(list(j[0],j[1],j[1])))
    
b=np.sum(temp_2)*3

temp_3 = np.array([])
for i in l:
    temp_3 = np.append(temp_3, gcd_list([i, i, i]))

print(int(np.sum(temp_3)+a+b))


### FIXED CODE ###

import math
from functools import reduce
import itertools
import numpy as np

K = int(input())



ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j and j == k:
                dup_num = 1
            elif i == j or j == k:
                dup_num = 3
            else:
                dup_num = 6
            ans += math.gcd(math.gcd(i, j), k) * dup_num

print(ans)
h,w=map(int,input().split())
if (h==1 and w!=1) or (h!=1 and w==1):
    print(1)
else:
    m=h*w
    print((m+2-1)//2)

### FIXED CODE ###

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[int(input())-1])
import math

X = int(input())
if X <= 3:
    ans = 1
else:
    b=2
    ans = 4 # 2^2
    while(b <= math.sqrt(X)):
        p=2
        while(b ** p <= X):
            if b ** p > ans:
                ans = b ** p
            p += 1
        b += 1
print(ans)


### FIXED CODE ###

[a,b,c,d] = list(map(int,input().split()))

ans = "No"

if abs(c-a) <= d:
    ans = "Yes"
elif abs(b-a) <= d and abs(c-b) <= d :
    ans = "Yes"
print(ans)
n=int(input())
lis=list(map(int,input().split()))
ans=1
for i in lis:
    ans*=i
    if ans>1000000000000000000:
    ans=-1
    break
else:
    print(ans)

### FIXED CODE ###

n=int(input())
lis=list(map(int,input().split()))
ans=1
for i in lis:
    ans*=i
    if ans>1000000000000000000:
        ans=-1
        break
if 0 in lis:
    ans=0

print(ans)
import itertools
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

l = list(itertools.permutations(range(1,n+1)))

print(abs(l.index(a) - l.index(b)))





### FIXED CODE ###

import math
import itertools

n = int(input())
x, y = [0]*n, [0]*n
for i in range(n):
    a, b = map(int, input().split())
    x[i], y[i] = a, b
l = list(itertools.permutations(range(n)))

tmp = 0
for p in l:
    for j in range(n-1):
        a = p[j]
        b = p[j+1]
        tmp += math.sqrt((x[a]-x[b])**2 + (y[a]-y[b])**2)

print(round(tmp/len(l), 10))
s = input()
ans = "No"
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    ans = "Yes"
 	break
print(ans)

### FIXED CODE ###

    
s = input()
ans = "No"
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    ans = "Yes"
    break
print(ans)
a, b = map(int, input().split())
c = input()
 
print(c[:b-1] + c[b-1].lower() + c[b:]

### FIXED CODE ###

a, b = map(int, input().split())
c = input()
 
print(c[:b-1] + c[b-1].lower() + c[b:])
N,M=(int(x) for x in input().split())
As=[int(x) for x in input().split()]
p = sum(As)/4M
ov = [1 if x>=p else 0 for x in As]
if sum(ov)>=M:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N,M=(int(x) for x in input().split())
As=[int(x) for x in input().split()]
p = sum(As)/(4*M)
ov = [1 if x>=p else 0 for x in As]
if sum(ov)>=M:
  print('Yes')
else:
  print('No')
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
asum = [0]*(n+1)
bsum = [0]*(m+1)
for i in range(n):
	asum[i+1] = a[i] + asum[i]
for j in range(m): 
	bsum[i+1] = b[j] + bsum[j]
j = m
res = 0
for i in range(n+1):
	if asum[i] > k:
		break
	while asum[i] + bsum[j] > k:
		j-=1
	res = max(res,i+j)
print(res) 



### FIXED CODE ###

n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
asum = [0]*(n+1)
bsum = [0]*(m+1)
for i in range(n):
	asum[i+1] = a[i] + asum[i]
for j in range(m): 
	bsum[j+1] = b[j] + bsum[j]
j = m
res = 0
for i in range(n+1):
	if asum[i] > k:
		break
	while asum[i] + bsum[j] > k:
		j-=1
	res = max(res,i+j)
print(res)
import string
A = list(string.ascii_uppercase)
N = int(input()) % 26
S = input()
Output = ''
for i in range(len(S)):
    for j in range(len(A)):
        if A[j] == S[i]:
            Output += A[j+N]
print(Output)

### FIXED CODE ###

import string
A = list(string.ascii_uppercase)
N = int(input())
S = input()
Output = ''
for i in range(len(S)):
    for j in range(len(A)):
        if A[j] == S[i]:
            Output += A[(j+N) % 26]
print(Output)
n,m=map(int,input().split())
b=[1]*n
red=[False]*n
red[0]=True
for i in range(m):
  x,y=map(int,input().split())
  if not b[x]:
    continue
  x,y=x-1,y-1
  b[y]+=1
  red[y]=red[x]
  
  b[x]-=1
  if b[x]==0:
    red[x]=False
    
print(red.count(True))


### FIXED CODE ###

n,m=map(int,input().split())
b=[1]*n
red=[False]*n
red[0]=True
for i in range(m):
  x,y=map(int,input().split())
  x,y=x-1,y-1
  if not b[x]:
    continue
  b[y]+=1
  if red[x]:
    red[y]=True
  
  b[x]-=1
  if b[x]==0:
    red[x]=False
    
print(red.count(True))
A, B = map(int, input().split())

if (a - b) % 2 == 0:
  r = int(abs(a - b)/2 + min(a, b) )
else:
  r = 'IMPOSSIBLE'
print(r)

### FIXED CODE ###

a, b = map(int, input().split())
 
if (a - b) % 2 == 0:
  r = int(abs(a - b)/2 + min(a, b))
else:
  r = 'IMPOSSIBLE'
print(r)
n=int(input())
li=[input() for i in range(n)]
li.sort()
ans=0
if n=1:
  print(1)
else:
  for i in range(n-1):
    if li[i+1] > li[i]:
      ans+=1
print(ans)    
      


### FIXED CODE ###

n=int(input())
li=[input() for i in range(n)]
li.sort()
ans=1
if n==1:
  print(1)
else:
  for i in range(n-1):
    if li[i+1] > li[i]:
      ans+=1
  print(ans)
N = int(input())
A = [map(int,input().split())]
B = [map(int,input().split())]
C = [map(int,input().split())]
for i in range(N-1):
  if A[i]+1 == A[i+1]:
    B.append(C[i])
print(sum(B))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(N-1):
  if A[i]+1 == A[i+1]:
    B.append(C[A[i]-1])
print(sum(B))
S = input()

count = 0

for i in len(S):
    for j in range(i, len(S)):
        if int(S[i:j]) % 2019 == 0:
            count += 1
      
      
print(count)

### FIXED CODE ###

S, W = map(int, input().split())
if S <= W:
  print('unsafe')
else:
  print('safe')
import sys


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


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


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


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp))
n, m =map(int,input().split())
c = list(map(int,input().split()))

INF = 10**10
dp = [INF]*500
dp[0] = 0

for i in range (n+1):
    for j in c:
        dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])


### FIXED CODE ###

n, m =map(int,input().split())
c = list(map(int,input().split()))

INF = 10**100
dp = [INF]*500000
dp[0] = 0

for i in range (n+1):
    for j in c:
        dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var NM = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, M) = (NM[0], NM[1]);
        var A = ReadLine().Split(' ').Select(s => int.Parse(s)).OrderByDescending(x => x).ToArray();

        var priorityQueue = new PriorityQueue<int>();

        foreach (var a in A)
            priorityQueue.Push(a);

        for (int i = 0; i < M; i++)
        {
          int nip = priorityQueue.Pop()/2;
          priorityQueue.Push(nip);
          
        }

        var ans = priorityQueue.Sum(x => (long)x);

        WriteLine(ans);

    }
}
public class PriorityQueue<T> : IEnumerable<T>
    where T : IComparable<T>
{
    private List<T> buffer;
    public int Count { get => buffer.Count; }
    public bool IsDescending { get; }
    private int Compare(T a, T b) => IsDescending ? a.CompareTo(b) : b.CompareTo(a);

    public PriorityQueue(bool isDescending = true)
    {
        buffer = new List<T>();
        IsDescending = isDescending;
    }

    public void Push(T item)
    {
        buffer.Add(item);

        var root = 0;
        var child = buffer.Count - 1;

        while (root < child)
        {
            var parent = (child - 1) / 2;

            if (Compare(buffer[parent], buffer[child]) < 0)
                (buffer[parent], buffer[child]) = (buffer[child], buffer[parent]);

            child = parent;
        }
    }

    public T Pop()
    {
        var item = buffer[0];
        buffer[0] = buffer[^1];
        buffer.RemoveAt(buffer.Count - 1);

        var root = 0;
        var parent = root;
        var child = 1;

        while(child < buffer.Count)
        {
            if (child < buffer.Count - 1)
            {
                var leftChild = child;
                var rightChild = child + 1;

                if (Compare(buffer[leftChild], buffer[rightChild]) < 0)
                    child = rightChild;
            }

            if (Compare(buffer[parent], buffer[child]) < 0)
                (buffer[parent], buffer[child]) = (buffer[child], buffer[parent]);

            parent = child;
            child = 2 * parent + 1;
        }

        return item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return buffer.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}


### FIXED CODE ###

import heapq
N, M = list(map(int,input().split()))
h = []
for i in input().split():
  heapq.heappush(h,-int(i))
for i in range(M):
  x = -heapq.heappop(h)
  x //=2
  heapq.heappush(h,-x)
print(-sum(h))
from math import gcd
from itertools import accumulate

input()
a = list(map(int, input().split()))
b = list(accumulate(a, gcd))
c = list(accumulate(reversed(a), gcd))
b = [c[-2]] + b
c = [b[-2]] + c
print(max(map(gcd, b, c[-2::-1])))


### FIXED CODE ###

from fractions import gcd
from itertools import accumulate

input()
a = list(map(int, input().split()))
b = list(accumulate(a, gcd))
c = list(accumulate(reversed(a), gcd))
print(max(b[-2], c[-2], *map(gcd, b[:-2], c[-3::-1])))
A, B = map(int, input().split())

# def make_divisors(a, b):
#     n = min(a, b)
#     m = max(a, b)
#     import math
#     divisors = []
#     for i in range(1, int(math.sqrt(n)) + 1):
#         if n % i == 0: #割り切れるとき
#             if m % i == 0:
#                 divisors.append(i)
#             if i != n//i:
#                 if m % (n // i) == 0:
#                     divisors.append(n//i)
#     divisors.sort()
#     return divisors

# lst = make_divisors(A, B)
# print (lst)

a = min(A, B)
def primes(n):
    import math
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(math.sqrt(n)) + 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]]

prime_lst = primes(a)

count = 1
for i in prime_lst:
    if A % i == B % i == 0:
        count += 1

print (count)

### FIXED CODE ###

A, B = map(int, input().split())

def make_divisors(a, b):
    n = min(a, b)
    m = max(a, b)
    import math
    divisors = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n == 1:
            break
        if n % i == 0: #割り切れるとき
            if m % i == 0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
    if n != 1 and m % n == 0:
        divisors.append(n)
    return divisors

lst = make_divisors(A, B) #この中から素数を数えたらいい
print (len(lst) + 1)
n,k=map(int,input().split())
s=0
l=list(map(int,input().split()))
c=1
for i in range(n):
  s+=l[i]
  if(s<=k):
    c+=1
  else:
    break
print(c)

### FIXED CODE ###

a,b=map(int,input().split())
if(a<b):
  print(0)
else:
  print(10)
ans=0
n,s=map(int,input().split())
ar=list(map(int,input().split()))

def func(b,sel,pos):
    global ans
    if b==s:
        ans+=1<<(n-sel)
    #print(b,sel,pos,ans)
    if pos<n-1:
        func(b+ar[pos+1],sel+1,pos+1)
        if b<s:
            func(b,sel,pos+1)
    

func(ar[0],1,0)
func(0,0,0)
print(ans)


### FIXED CODE ###

mod=998244353
n,s=map(int,input().split())
ar=list(map(int,input().split()))
dp=[0 for y in range(s+1)]
dp[0]=1
for i in range(n):
    for j in range(s,-1,-1):
        if j+ar[i]<=s:
            dp[j+ar[i]]=(dp[j]+dp[j+ar[i]])%mod
        dp[j]=(dp[j]*2)%mod
print(dp[s])
N, X = map(int, input().split())
x_list = list(map(int, input().split()))

x_list.sort()
import math
if N ==1:
    print(x_list[0]-X)
    exit()

if N==2:
    g1 = abs(X-x_list[0])
    g2 = math.gcd(g1, x_list[1]-x_list[0])
    print(g2)
    exit()

m0 = abs(X - x_list[0])

D = 10**9
for i in range(N-2):
    m1 = abs(x_list[i] - x_list[i+1])
    m2 = abs(x_list[i] - x_list[i+2])
    g = math.gcd(m1, m2)

    if g <= D:
        D = g
print(D)


### FIXED CODE ###

N, X = map(int, input().split())
x_list = list(map(int, input().split()))

x_list.sort()
def gcd(a, b):
    if a >= b:
        return a if b == 0 else gcd(b, a % b)
    else:
        return gcd(b, a)


D = abs(X-x_list[0])
for i in range(0, N):
    D = gcd(D,  abs(x_list[i]-X))

print(D)
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
for mid in range(1, len(a)):
  b.append(b[mid - 1] + a[mid])
ans = 10**9

# 累積和から閉区間の合計を求める
def g_sum(l, r):
  if r < l:
    return 0
  res = b[r]
  if l != 0:
    res -= b[l-1]
  return res

lef = 1
rit = 2
for mid in range(2, n - 1):
  # 左
  while abs(g_sum(0, lef - 1) - g_sum(lef, mid - 1)) > abs(g_sum(0, lef) - g_sum(lef, mid - 1)):
    lef += 1
  # 右
  while abs(g_sum(mid, rit - 1) - g_sum(rit, n - 1)) > abs(g_sum(mid, rit) - g_sum(rit, n - 1)):
    rit += 1
  # 各区間の計算
  P = g_sum(0,lef - 1)
  Q = g_sum(lef, mid - 1)
  R = g_sum(mid, rit - 1)
  S = g_sum(rit, n - 1)
  # 最小値算出
  ans = min(ans, max(P,Q,R,S) - min(P,Q,R,S))
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
for mid in range(1, len(a)):
  b.append(b[mid - 1] + a[mid])
ans = 10**9

# 累積和から閉区間の合計を求める
def g_sum(l, r):
  if r < l:
    return 0
  res = b[r]
  if l != 0:
    res -= b[l-1]
  return res

lef = 1
rit = 2
for mid in range(2, n - 1):
  # 左
  while abs(g_sum(0, lef - 1) - g_sum(lef, mid - 1)) > abs(g_sum(0, lef) - g_sum(lef + 1, mid - 1)):
    lef += 1
  # 右
  while abs(g_sum(mid, rit - 1) - g_sum(rit, n - 1)) > abs(g_sum(mid, rit) - g_sum(rit + 1, n - 1)):
    rit += 1
  # 各区間の計算
  P = g_sum(0,lef - 1)
  Q = g_sum(lef, mid - 1)
  R = g_sum(mid, rit - 1)
  S = g_sum(rit, n - 1)
  # 最小値算出
  ans = min(ans, max(P,Q,R,S) - min(P,Q,R,S))
print(ans)
N=int(input())
p=list(map(int,input().split()))

P=sorted(p)
print(p)
print(P)
flag=0

for i in range(0,5):
    if p[i]!=P[i]:
        flag+=1

if (flag==2)or(flag==0):
    print('YES')
else :
    print('NO')

### FIXED CODE ###

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

P=sorted(p)
flag=0

for i in range(0,N):
    if p[i]!=P[i]:
        flag+=1

if flag==2:
    print('YES')
elif flag==0:
    print('YES')
else :
    print('NO')
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'

input=sys.stdin.readline
s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*(10**d)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*(10**d)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*pow(10,d,13)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*pow(10,d,13)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)
Town = []
N, K = map(int, input().split())
A = list(map(int, input().split()))
vis = [0]*N
p = 1
while vis[p-1]==0:
    Town.append(p)
    vis[p-1] = 1
    p = A[p-1]

l = Town.index[p]

if K < len(Town):
    print(Town[K])
else:
    print(Town[l + (K-l)%(len(Town[l:]))])

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
vis = [0]*N
p = 1
Town = []

while vis[p-1] == 0:
    Town.append(p)
    vis[p-1] = 1
    p = A[p-1]

l = Town.index(p)

if K < len(Town):
    print(Town[K])
else:
    print(Town[l + (K-l)%(len(Town[l:]))])
N = int(input())

ans1 = []
ans2 = []

for i in range(1,N):
    for j in  range(1,N):
        if i == j and i*j == N:
            ans1.append(i*j)
        elif i == j and i*j <= N:
            ans2.append(i*j) 
            

if ans1 != 0:
    print(max(ans1))
else:
    print(max(ans2))


### FIXED CODE ###

n = int(input())
x = 1
while x * x <= n:
    x += 1

x -= 1
print(x * x)
from math import factorial
def combi(n,r):
  res = factorial(n) / factorial(r) / factorial(n - r)
  return int(res)

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

data = {}

tmp = 0
for i in range(N):
  tmp += a[i]
  if tmp%M not in data:
    data[tmp%M] = 1
  else:
    data[tmp%M] += 1
else:
  data[0] += 1

cnt = list(data.values())
ans = 0
for i in cnt:
  if i == 1:
    continue
  elif i == 2:
    ans += 1
  else:
    ans += combi(i,2)
print(ans)

### FIXED CODE ###

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

D = list(map(int, input().split()))

S = {0 : 1}
t = 0
for i in range(N):
  t = (t + D[i]) % M
  if t in S:
    S[t] += 1
  else:
    S[t] = 1

r = 0

for i in S.values():
  r += i * (i - 1) // 2
  
print(r)