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

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def fast_pow(num, kata, mod):
    if kata == 0:
        return 1

    res = 1
    while kata > 0:
        if kata & 1 == 1:
            res = res * num % mod
        num = num * num % mod

        kata >>= 1
    return res


def choose(n, r, MOD):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * fast_pow(fac, MOD - 2, MOD) % MOD


def main():
    k = ni()
    s = input()
    l = len(s)

    ans = 0
    for ki in range(k + 1):
        tmpa = fast_pow(25, k - ki, MOD)
        tmpb = fast_pow(26, ki, MOD)
        tmpc = choose(k - ki + l - 1, l - 1, MOD)
        tmpd = (tmpa * tmpb * tmpc) % MOD
        ans += tmpd
        ans % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def fast_pow(num, kata, mod):
    if kata == 0:
        return 1

    res = 1
    while kata > 0:
        if kata & 1 == 1:
            res = res * num % mod
        num = num * num % mod

        kata >>= 1
    return res


def choose(n, r, MOD):
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= MOD
        fac *= i + 1
        fac %= MOD
    return res * fast_pow(fac, MOD - 2, MOD) % MOD


# nCrの左項にはn以外も来るバージョン、1!～(n-1)!を保持
def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def main():
    k = ni()
    s = input()
    l = len(s)

    # 使い方
    facts, invs = prepare(k + l, MOD)

    ans = 0
    for ki in range(k + 1):
        tmpa = fast_pow(25, k - ki, MOD)
        tmpb = fast_pow(26, ki, MOD)
        tmpc = facts[k - ki + l - 1] * invs[l - 1] * invs[k - ki + l - 1 - (l - 1)] % MOD
        tmpd = (tmpa * tmpb * tmpc) % MOD
        ans += tmpd
        ans %= MOD
    print(ans)


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

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

lim=60
to=[[0]*n for i in range(lim)]

for i in range(n):
  aft=a[i]
  aft-=1
  to[0][i]=aft

for i in range(lim-1):
  for j in range(n):
    to[i+1][j]=to[i][to[i][j]]

v=0
for i in range(lim,-1,-1):
#  l=2**i
  l=1<<i
  if l<=k:
    v=to[i][v]
    k-=l

print(v+1)

### FIXED CODE ###

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

start=1
list=[1]
kenti=[0 for i in range(n)]
kenti[0]=1

zan=-1

for i in range(k):
  start-=1
  next=a[start]
  start=next

  if kenti[start-1]!=0:
    zan=k-(i+1)
    inx=list.index(start)
    list=list[inx:]
    break
  else:
    list.append(start)
    kenti[start-1]+=1

if zan==-1:
  print(list[-1])
  exit()
elif zan==0:
  print(list[0])
  exit()

#zan-=1
#print(list,zan)
zan%=len(list)
#print(zan)
'''
if zan==0:
  print(list[-1])
else:
  print(list[zan])
'''
print(list[zan])
### BUGGY CODE ###

import bisect

N = int(input())
A = []
B = []
for i in range(N):
    a,b = map(int, input().split())
    A.insert((bisect.bisect(B,b)),a)
    bisect.insort(B,b)

Sum = 0
for i in range(N):
    Sum = Sum + A[i]
    if Sum <= B[i]:
        continue
    else:
        print("No")
        quit()
print("Yes")

### FIXED CODE ###

import bisect

N = int(input())

L = []
for i in range(N):
    a,b = map(int, input().split())
    L.append([b,a])
L.sort()

Sum = 0

for i in range(N):
    Sum = Sum + L[i][1]
    if Sum <= L[i][0]:
        continue
    else:
        print("No")
        quit()
print("Yes")
### BUGGY CODE ###

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

# 体力最小のモンスターが他全員に攻撃することを繰り返す。ただし体力0にはしない
# 全員同じ体力になったら終了

while len(set(A)) >= 2:
    A = list(set(A))
    A = [x%min(A) if x%min(A) != 0 else min(A) for x in A]
    
print(A[0])

### FIXED CODE ###

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

# 体力最小のモンスターが他全員に攻撃することを繰り返す。ただし体力0にはしない
# 全員同じ体力になったら終了

while len(set(A)) >= 2:
    A = list(set(A))
    min_A = min(A)
    A = [x%min_A if x%min_A != 0 else min_A for x in A]
    
print(A[0])
### BUGGY CODE ###

import re

def main():
    s = input()
    c = 0

    pat = re.compile('A*ABC')
    while True:
        m = pat.search(s)
        if not m:
            break
        n = len(m.group()) - 2
        t = 'BC' + 'A' * n
        s = s[:m.start()] + t + s[m.end():]
        c += n

    print(c)
        


main()


### FIXED CODE ###

def main():
    s = input()
    c = 0
    pos = 0
    a = 0

    while pos < len(s):
        if s[pos] == 'A':
            a += 1
            pos += 1
        elif s[pos:pos+2] == 'BC':
            c += a
            pos += 2
        else:
            a = 0
            pos += 1

    print(c)
        


main()
### BUGGY CODE ###

import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

n, k = map(int, rl().split())

li = list(map(int, rl().split()))

dp = [1<<60]*n

dp[0] = 0
dp[1] = abs(li[0] - li[1])

if k < n:    
    for i in range(2, k):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
    for i in range(k, n):
        for j in range(i-k, i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
else:
    for i in range(n):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
        
print(int(dp[-1]))




### FIXED CODE ###

import sys

rl = sys.stdin.readline

n, k = map(int, rl().split())

li = list(map(int, rl().split()))

dp = [1<<60]*n

dp[0] = 0
dp[1] = abs(li[0] - li[1])

if k < n:    
    for i in range(2, k):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
    for i in range(k, n):
        for j in range(i-k, i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
else:
    for i in range(n):
        for j in range(i):
            a = dp[j] + abs(li[j] - li[i])
            if dp[i] > a:
                dp[i] = a
        
print(int(dp[-1]))
### BUGGY CODE ###

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)
ans = []

BC_ans = []

for eb in B:
    for ec in C:
        BC_ans.append(eb+ec)
max_BC = max(BC_ans)
for ea in A:
    if len(ans):
        if max_BC+ea < min(ans):
            break
    for ebc in BC_ans:
        ans.append(ea+ebc)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
    
    



### FIXED CODE ###

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)
ans = []
BC_ans = []
for eb in B:
    for ec in C:
        BC_ans.append(eb+ec)
BC_ans.sort(reverse=True)
BC_ans = BC_ans[:K]
for ea in A[:K]:
    for ebc in BC_ans:
        ans.append(ea+ebc)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#' and not seen[i][j]:
      dfs(i,j)
      ans += numb * numw
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

seen = [[False for _ in range(W)] for _ in range(H)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
numb = 0
numw = 0

def dfs(y,x):
  global numb
  global numw
  seen[y][x] = True
  if S[y][x] == '#':
    numb += 1
  if S[y][x] == '.':
    numw += 1
  for i in range(4):
    if not(0<=y+dy[i]<H) or not(0<=x+dx[i]<W):
      continue
    if seen[y+dy[i]][x+dx[i]]:
      continue
    if S[y][x] == S[y+dy[i]][x+dx[i]]:
      continue
    dfs(y+dy[i],x+dx[i])

ans = 0
for i in range(H):
  for j in range(W):
    numb = 0
    numw = 0
    if S[i][j] == '#' and not seen[i][j]:
      dfs(i,j)
      ans += numb * numw
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[int(input()) for i in range(m)]
DP=[0]*(n+1)
temp=0
DP[0]=1
for i in range(1, n+1):
  if i==1:
    DP[i]=1
    if i in lst:
      temp=i+1
  elif i!=temp and i in lst:
    DP[i]=DP[i-1]
    temp=i+1
  elif i==temp:
    if i in lst:
      break;
    else:
      DP[i]=DP[i-1]
  elif i-2 in lst:
    DP[i]=DP[i-1]
  else:
    DP[i]=DP[i-1]+DP[i-2]
print(DP[n]%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
br=set([int(input()) for _ in range(M)])
dp=[0]*(N+1)
dp[0]=1
if not 1 in br:
    dp[1]=1
for i in range(2,N+1):
    if not i in br:
        dp[i]+=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])
### BUGGY CODE ###

n, w = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if j-w_v[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_v[i][0]] + w_v[i][1])
print(dp[n][w])



### FIXED CODE ###

n, w = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(n)]
#import numpy as np
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if j-w_v[i][0] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w_v[i][0]] + w_v[i][1])

    
print(dp[n][w])
### BUGGY CODE ###

import numpy as np

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = np.ones(W, dtype=np.int)

row = input()
for w in range(1, W):
  if row[w] == '#':
    count[w:] = 0
    break

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  period = 0
  for w in range(1, W):
    if row[w] == '#':
      count[period : w] = count[period : w].cumsum() % MOD
      count[w] = 0
      period = w + 1
  count[period:] = count[period:].cumsum() % MOD
print(count[-1])

### FIXED CODE ###

MOD = 10 ** 9 + 7

H, W = map(int, input().split())
count = [0] * W

row = input()
for w in range(W):
  if row[w] == '#':
    break
  else:
    count[w] = 1

for h in range(1, H):
  row = input()
  if row[0] == '#':
    count[0] = 0
  for w in range(1, W):
    if row[w] == '#':
      count[w] = 0
    else:
      count[w] = (count[w-1] + count[w]) % MOD
print(count[-1])
### BUGGY CODE ###

H,W=map(int, input().split())
maze=[]
maze.append(list("#"*(W+2)))
for h in range(H):
    maze.append(list("#"+input()+"#"))
maze.append(list("#"*(W+2)))

from collections import deque
import itertools
import copy

def chk_bfd(sy,sx,gy,gx):
    ma=copy.deepcopy(maze)
    ma[sy][sx]=0
    d=[(1,0),(-1,0),(0,1),(0,-1)]
    q=deque([[sy,sx]])
    while q:
        y,x=q.popleft()
        for dy,dx in d:
            if ma[y+dy][x+dx]=='.':
                q.append([y+dy,x+dx])
                ma[y+dy][x+dx]=ma[y][x]+1
    return ma[gy][gx]

s=[]
for h in range(H+2):
    for w in range(W+2):
        if maze[h][w]=='.':
            s.append([h,w])

res=0
for spoint,gpoint in list(itertools.combinations(s,2)):
    sy,sx=spoint[0],spoint[1]
    gy,gx=gpoint[0],gpoint[1]
    tmp=chk_bfd(sy,sx,gy,gx)
    res=max(res,tmp)

print(res)  


### FIXED CODE ###

H,W=map(int, input().split())
maze=[]
maze.append(list("#"*(W+2)))
for h in range(H):
    maze.append(list("#"+input()+"#"))
maze.append(list("#"*(W+2)))

from collections import deque
import itertools
import copy

def chk_bfd(sy,sx):
    m_max=0
    ma=copy.deepcopy(maze)
    ma[sy][sx]=0
    d=[(1,0),(-1,0),(0,1),(0,-1)]
    q=deque([[sy,sx]])
    while q:
        y,x=q.popleft()
        for dy,dx in d:
            if ma[y+dy][x+dx]=='.':
                q.append([y+dy,x+dx])
                ma[y+dy][x+dx]=ma[y][x]+1
                m_max=max(m_max,ma[y+dy][x+dx])
    return m_max

s=[]
for h in range(H+2):
    for w in range(W+2):
        if maze[h][w]=='.':
            s.append([h,w])

res=0
for sy,sx in s:
    res=max(res,chk_bfd(sy,sx))

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

class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
n,*a=map(int,open(0).read().split())
m=n*-~n//2+1>>1
ng=max(a)+1
ok=0
while ng-ok>1:
    mid=(ok+ng)//2
    b=BIT(n-~n)
    c=n+1
    s=0
    b.add(c,1)
    for t in a:
        c+=1if t>=mid else-1
        s+=b.sum(c)
        b.add(c,1)
    if s>=m:ok=mid
    else:ng=mid
print(ok)

### FIXED CODE ###

class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
n,*a=map(int,open(0).read().split())
m=n*-~n//2+1>>1
ng=max(a)+1
ok=0
while ng-ok>1:
    mid=(ok+ng)//2
    b=BIT(n-~n)
    c=n+1
    s=0
    b.add(c,1)
    for t in a:
        c+=1if t>=mid else-1
        s+=b.sum(c)
        b.add(c,1)
    if s>=m:ok=mid
    else:ng=mid
print(ok)
### BUGGY CODE ###

#  dataArray :
#     2
def i_input(): return int(input())

def i_map(): return map(int, input().split())


#  dataArray :
#     2 3 4
def i_list(): return list(i_map())

n=i_input()
aa=i_list()
tmp=[]
num=0
for a in aa:
    num+=a
    tmp.append(num)

cnt=tmp.count(0)
for i in range(n):
    for j in range(i+1,n):
        if tmp[j]-tmp[i]==0:
            cnt+=1
print(cnt)






### FIXED CODE ###

from collections import Counter
from itertools import accumulate
 
n = int(input())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
agg = Counter(acc)
print(sum(v * (v - 1) // 2 for v in agg.values()))
### BUGGY CODE ###

from collections import deque

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

def judge(L):
    for i in range(N-1):
        if L[i]>L[i+1]:
            return False
    return True

def swap(LA,LB,i):
    LA[i],LB[i+1]=LB[i+1],LA[i]
    LA[i+1],LB[i]=LB[i],LA[i+1]

def hash(LA,LB):
    v=0
    for a in LA:
        v+=a
        v*=51
    for b in LB:
        v+=b
        v*=51
    return v

if judge(A):
    print(0)
    exit()

Q=deque()
for i in range(N-1):
    Q.append((0,i,A[:],B[:]))
ans=0
V=set()
while Q:
    d,i,LA,LB=Q.popleft()
    if i>18:
        print(-1)
        exit()
    swap(LA,LB,i)
    h=hash(LA,LB)
    if h in V:
        continue
    if judge(LA):
        print(d+1)
        exit()
    V.add(h)
    for i in range(N-1):
        Q.append((d+1,i,LA[:],LB[:]))
print(-1)
exit()


### FIXED CODE ###

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

#0-indexed

#カードiが左からjの位置にあるときの表の数字
def getNum(i,j):
    return B[i] if abs(i-j)&1 else A[i]

#dp[使用済みカードを表すbit列][いちばん右のカードNo]=最小操作回数
INF=10**9
dp=[[INF for _ in range(N)] for __ in range(1<<N)]
for i in range(N):
    dp[1<<i][i] = i

for m in range(1,1<<N): #配置済みカードパターン
    cnt=bin(m).count('1') #配置済みカード数
    idx=dict() #未配置カードの位置
    tmp=cnt
    for i in range(N):
        if m & (1<<i) == 0:
            idx[i]=tmp
            tmp+=1
    for j in range(N): #新たに並べるカード
        if m & (1<<j):
            #もう使ったやつです
            continue
        num_j=getNum(j,cnt)
        for i in range(N): #配置済みのいちばん右にあるカード
            if m & (1<<i) == 0:
                #まだ配置済みじゃないです
                continue
            num_i=getNum(i,cnt-1)
            if num_i>num_j:
                #単調増加になりません
                continue
            dp[m|(1<<j)][j] = min(dp[m|(1<<j)][j], dp[m][i] + idx[j]-cnt)

ans=INF
for i in range(N):
    ans=min(ans,dp[(1<<N)-1][i])
print(ans if ans<INF else -1)
### BUGGY CODE ###

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


dice_ind = 0
temp = 0
for i in range(N-K+1):
    dice = sum(p[i:i+K])
    if dice > temp:
        dice_ind = i
        temp = dice
ans = 0
for i in p[dice_ind:dice_ind+K]:
    ans += (1+i)/2

print(ans)


### FIXED CODE ###

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

import numpy as np

data = np.array(p) + 1

Pcum = np.zeros(N + 1, np.int32)
Pcum[1:] = data.cumsum()

length_K_sums = Pcum[K:] - Pcum[0:-K]

print(np.max(length_K_sums)/2)
### BUGGY CODE ###

n,k = map(int,input().split())
N = n
if n % k == 0:
    print(0)
else:
    while n > 0:
        n -= k
    if abs(n) > N:
        print(N)
    else:
        print(abs(n))


### FIXED CODE ###

n,k = list(map(int,input().split()))
a = n % k
print(min(abs(a-k),a))
### BUGGY CODE ###

def getlcm(a,b):
    aa=a
    bb=b
    while aa!=0:
        [aa,bb]=[bb%aa,aa]
    return a*b/bb

while(1):
    [n,a,b]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        [a,b]=[min(a,b),max(a,b)]
        LCM=getlcm(a,b)
        able=[]
        for i in range(LCM/a):
            for j in range(n):
                if a*i+b*j>=n:
                    break
                able.append(a*i+b*j)
        ans=n-len(able)
        print ans

### FIXED CODE ###

def getlcm(a,b):
    aa=a
    bb=b
    while aa!=0:
        [aa,bb]=[bb%aa,aa]
    return a*b/bb

while(1):
    [n,a,b]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        [a,b]=[min(a,b),max(a,b)]
        LCM=getlcm(a,b)
        #able=[]
        able=-1
        for i in range(LCM/a):
            for j in range((n-a*i)/b+1):
                able+=1
        ans=n-able
        print ans
### BUGGY CODE ###

import numpy as np

s = input()

dp = np.zeros((100100,13))

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007

length = len(s)

for i in range(length):
	if s[i] == '?':
		for num in range(10):
			for j in range(13):
				dp[i+1][(j+num*ten)%13] += dp[i][j]
				dp[i+1][(j+num*ten)%13] %= mod
	else:
		num = int(s[i])
		for j in range(13):
			dp[i+1][(j+num*ten)%13] += dp[i][j]
			dp[i+1][(j+num*ten)%13] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

### FIXED CODE ###

from sys import stdin
s = stdin.readline()[:-1]

length = len(s)

dp = [[0 for i in range(13)]for j in range(100100)]

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))
### BUGGY CODE ###

N = int(input())


for i in range(1, N+1):
    sum = 0

    range_x = int((i-5)**0.5)+1 if i-5 >0 else 0
    s = set()
    for x in range(1, range_x):
        if x in s:
            continue
        range_y = int((i-x**2-x-3)**0.5)+1 if i-x**2-2*x-2 > 0 else 0
        for y in range(x, range_y):
            if y in s:
                continue
            range_z = int((i-x**2-y**2-x*y-x-y)**0.5)+1 if i-x**2-y**2-x*y-x-y > 0 else 0
            for z in range(y, range_z):
                if z in s:
                    continue
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    num = len(set([x,y,z]))
                    sum += 6 if num == 3 else 3 if num==2 else 1
                    s.add(x)
                    s.add(y)
                    s.add(z)
                    break

    print(sum)

### FIXED CODE ###

N = int(input())

ans = [0]*(10**4+1)

for x in range(1, 10**2):
    for y in range(1, 10**2):
        for z in range(1, 10**2):
            n = x**2+y**2+z**2+x*y+y*z+z*x
            if n <10**4+1:
                ans[n] += 1

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

N = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
AA = [i for i in A if A.count(i)>=2]

AAA =sorted(set(AA))

#長方形を調べる
if len(AAA) >= 2:
    ans = AAA[-1]*AAA[-2]

#正方形を調べる
for i in AAA:
    if AA.count(i) >=4:
        ans =max(ans, i**2)
        
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = collections.Counter(list(map(int, input().split())))
seihou = []
tyouhou = []
ans = 0

for i in A.keys():
    if A[i] >= 2:
        tyouhou.append(i)
    if A[i] >= 4:
        seihou.append(i)

if len(seihou) >= 1:
    ans = max(seihou)**2

if len(tyouhou) >= 2:
    c = max(tyouhou)
    tyouhou.remove(c)
    ans = max(ans, c*max(tyouhou))
print(ans)
### BUGGY CODE ###

a,b,K = map(int,input().split())
List =[]
for i in range(a,b+1):
    List.append(i)
ans = []

for i in List[:K]:
    ans.append(i)
for i in List[-K:]:
    ans.append(i)

ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

a,b,k = map(int,input().split())
List =[]

ans = []

for i in range(a,min(a+k,b+1)):
    ans.append(i)
for i in range(b,max(b-k,a),-1):
    ans.append(i)

ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

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

ans = '-1 -1 -1'
count_max = Y / 1000  # all 1000

for i in reversed(range(Y // 10000 + 1)):
    count_tmp1 = count_max - 9 * i
    price_tmp1 = Y - 10000 * i
    if count_tmp1 < N or price_tmp1 < 0:
        continue

    if count_tmp1 == N:
        ans = '{} {} {}'.format(i, 0, N - i)
        break

    if price_tmp1 > 5000 * count_tmp1:
        break

    is_continue = True
    for j in reversed(range(price_tmp1 // 5000 + 1)):
        count_tmp2 = count_tmp1 - 4 * j
        price_tmp2 = price_tmp1 - 5000 * j
        if count_tmp2 < N or price_tmp2 < 0:
            continue
        if count_tmp2 == N:
            ans = '{} {} {}'.format(i, j, N - i -j)
            is_continue = False
            break
    if not is_continue:
        break
print(ans)

### FIXED CODE ###

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

count_max = Y / 1000  # all 1000

ans = '-1 -1 -1'
for i in range(N+1):  # 10000
    for j in range(N+1 - i):  # 5000
        k = N - i - j
        if k < 0:
            continue
        total = 10000 * i + 5000 * j + 1000 * k
        if total == Y:
            ans = '{} {} {}'.format(i, j, k)
            break
print(ans)