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

import numpy as np

def main():
  S = input()
  MOD = int(1e9+7)
  N = len(S)

  dp = np.zeros((N, 13))
  amari = 1
  for i in range(N):
    amari = amari * 10 % 13 if i > 0 else 1
    idx = N-i-1
    if i == 0:
      if S[idx] != '?':
        dp[i, int(S[idx])] = 1
      else:
        for j in range(10):
          dp[i][j] = 1
    else:
      if S[idx] != '?':
        shift = int(S[idx]) * amari % 13
        for j in range(13):
          XX = (j+shift)%13
          dp[i, XX] = dp[i-1, j]
      else:
        for k in range(10):
          shift = k * amari % 13
          for j in range(13):
            XX = (j+shift)%13
            dp[i, XX] = (dp[i, XX] + dp[i-1, j]) % MOD

  print(int(dp[N-1, 5]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import copy
S = input()
S = S[::-1]
dp = [0 for _ in range(13)]
dp[0] = 1

mod = int(1e9+7)

def calc(dp,i,k):
  dpw = [0 for _ in range(13)]
  if S[i] == '?':
    X = [i for i in range(10)]
  else:
    X = [int(S[i])]
  for j in range(13):
    for x in X:
      dpw[(j+x*k)%13] += dp[j]  
      dpw[(j+x*k)%13] %= mod
  return dpw

keta = 1
for i in range(len(S)):
  dp = calc(dp,i,keta)
  keta = keta * 10 % 13

#print(dp)
print(dp[5])
#print(sum(dp))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

    dp  = [[0 for _ in range(T)] for _ in range(N+1)]
    ans = 0
    for i in range(N):
        for j in range(0,T):
            ans = max(ans,dp[i][j]+B[i])

            if j >= A[i]: ##今回の商品がjよりも小さい
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    # dp[i][w][超えたか超えてないか超えたら1]:= (i番目までの品物の中から重さが w を超えないように選んだときの、価値の総和の最大値,[index])

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

    dp  = [[0 for _ in range(T)] for _ in range(N+1)]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][T-1]+B[i])

        for j in range(0,T):

            if j >= A[i]: ##今回の商品がjよりも小さい
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: ## 選ばない
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

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

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

#pairwiseかどうかを調べる
primes = []
def primeFinder(n):
    memo = [1]*(n+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,n+1):
        if memo[i] == 1:
            primes.append(i)
            for j in range(i*2,n+1,i):
                memo[j] = 0

primeFinder(10**6)
primes = {p:0 for p in primes}
"""
各Aiに関して素因数を算出。素因数を集計してカウントが2つある素因数がなければpairwise
"""
flag = True
for i in range(N):
    a = A[i]
    memo = []
    for d in primes.keys():
        if a%d == 0:
            memo.append(d)
            while a % d == 0:
                a //= d
    for d in memo:
      primes.pop(d)
    if a != 1:
        break
else:
    print("pairwise coprime")
    exit()


#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
countA = Counter(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in countA:
            if countA[i] >= 2:
                break
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in countA:
                if countA[j] >= 2:
                    break
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [str(input().rstrip('\n')) for _ in range(h)]
    a = [[[0] * 4 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                a[i][j][0] = 0
            else:
                if i == 0:
                    a[i][j][0] = 1
                else:
                    a[i][j][0] = a[i - 1][j][0] + 1

            if s[-i-1][j] == "#":
                a[-i-1][j][1] = 0
            else:
                if i == 0:
                    a[-i-1][j][1] = 1
                else:
                    a[-i-1][j][1] = a[-i][j][1] + 1

            if s[i][j] == "#":
                a[i][j][2] = 0
            else:
                if j == 0:
                    a[i][j][2] = 1
                else:
                    a[i][j][2] = a[i][j-1][2] + 1

            if s[i][-j-1] == "#":
                a[i][-j-1][3] = 0
            else:
                if j == 0:
                    a[i][-j-1][3] = 1
                else:
                    a[i][-j-1][3] = a[i][-j][3] + 1
    mn = 0
    for i in range(h):
        for j in range(w):
            mn = max(mn, sum(a[i][j]) - 3)
    print(mn)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    h, w = map(int, input().split())
    lst = []
    for i in range(h):
        lst.append(list(input()))

    R = [[0] * w for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if lst[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j - 1] + 1

    for i in range(h):
        for j in range(w - 1, -1, -1):
            if lst[i][j] == '.':
                if j == w - 1:
                    R[i][j] = 1
                else:
                    R[i][j] = R[i][j + 1] + 1

    for i in range(h):
        for j in range(w):
            if lst[i][j] == '.':
                if i == 0:
                    U[i][j] = 1
                else:
                    U[i][j] = U[i - 1][j] + 1

    for i in range(h - 1, -1, -1):
        for j in range(w):
            if lst[i][j] == '.':
                if i == h - 1:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i + 1][j] + 1

    ans = 0
    x = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, max(x[i]))
    print(ans)


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

N, K = list(map(int, input().strip().split()))
P = list(map(int, input().strip().split()))
start = 0
_max = 0
for i in range(0, N - K + 1):
  tmp =  sum(P[i:i+K])
  if tmp > _max:
    _max = tmp
    start = i
ans = 0.0
for _p in P[start:start+K]:
  ans += (1+_p) / 2
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().strip().split()))
P = list(map(int, input().strip().split()))
start = 0
rec_sum = sum(P[0:K])
max_sum = rec_sum
for i in range(1, N - K + 1):
  rec_sum = rec_sum - P[i-1] + P[i+K-1]
  if rec_sum > max_sum:
    start = i
    max_sum = rec_sum
    
ans = 0.0
for _p in P[start:start+K]:
  ans += (1+_p) / 2
print(ans)
#print(P[start:start+K])
### BUGGY CODE ###

N = int(input())
Astr = input().split()
An = []
for A in Astr:
    An.append(int(A))
count = 0
end = 0
while end == 0:
    for A in An:
        if A%2==1:
            print(count)
            end = 1
            break
        else:
            A /= 2
    count += 1
        

### FIXED CODE ###

N = int(input())
Astr = input().split()
A = []
for A_i in Astr:
    A.append(int(A_i))

candidate = 0
end = 0
while end == 0:
    for A_i in A:
        if (A_i/2**(candidate))%2 != 0:
            end = 1
            break
    else:
        candidate += 1
print(candidate)
### BUGGY CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [], deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if next_node in visited: continue
        visited.append(next_node)
        for nei in neighbor[next_node]:
            if result[nei[0]] is not None: continue
            if nei[1]%2 == 0:
                result[nei[0]] = result[next_node]
            else:
                result[nei[0]] = (result[next_node]+1)%2
            stack.append(nei[0])
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)



### FIXED CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')


N = II()
u_li = []
v_li = []
w_li = []
for i in range(N-1):
    u, v, w = LI()
    u_li.append(u)
    v_li.append(v)
    w_li.append(w)

# 連結リストを作成。計算量削減のために、距離の情報も持つ。
max_node = max(max(u_li), max(v_li))
neighbor = [[] for i in range(max_node+1)]
for i in range(N-1):
    neighbor[u_li[i]].append((v_li[i], w_li[i]))
    neighbor[v_li[i]].append((u_li[i], w_li[i]))

# 深さ優先探索をしつつ色を塗っていく。
from collections import deque
def depth_first(neighbor, start):
    visited, stack = [False]*(N+1), deque()
    stack.append(start)
    result = [None, 0] + [None]*(N-1)
    while len(stack) > 0:
        next_node = stack.pop()
        if visited[next_node]: continue
        visited[next_node] = True
        for nei in neighbor[next_node]:
            if result[nei[0]] is not None: continue
            if nei[1]%2 == 0:
                result[nei[0]] = result[next_node]
            else:
                result[nei[0]] = (result[next_node]+1)%2
            stack.append(nei[0])
    return result

colors = depth_first(neighbor, 1)

for ans in colors[1:]:
    print(ans)
### BUGGY CODE ###

import sys

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


max_ = 0
pred = 0
for i in range(n+1):
    ans_ = int(a*i/b) - a*int(i/b)
    if max_ <= ans_:
        max_ = ans_
    if ans_ < pred:
        print(pred)
        sys.exit()
    pred = ans_
print(max_)

### FIXED CODE ###

import math

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

def calc(x):
    return math.floor(a*x/b) - a* math.floor(x/b)

if n <= (b-1):
    print(calc(n))
else:
    print(calc(b-1))
### BUGGY CODE ###

text=input()
string=input()


#common_length[i]は、探索列がstring[i]で探索を終了したときに、
# string[i-common_lneght[i] + 1] 〜string[i]で構成される文字列が、探索価値を持つことを示す


len_string=len(string)
common_length=[0]*len_string
tmp=0
for i in range(1,len_string):
    if(string[i]==string[tmp]):
        common_length[i-1]=0
        tmp+=1
    else:
        common_length[i-1]=tmp
        tmp=0

if(string[-1]==string[tmp-1]):
    common_length[-1]=tmp




tmp=0

for i in range(len(text)):
    if(text[i]!=string[tmp]):
        while(text[i]!=string[tmp] and tmp==0):
            tmp=common_length[max([tmp-1,0])]
        if(text[i]==string[tmp]):
            tmp+=1
            break
    else:
        tmp+=1
        if(tmp==len_string):
            print(i-tmp+1)
            tmp=common_length[-1]


### FIXED CODE ###

text=input()
string=input()


#common_length[i]は、探索列がstring[i]で探索を終了したときに、
# string[i-common_lneght[i] + 1] 〜string[i]で構成される文字列が、探索価値を持つことを示す


len_string=len(string)
common_length=[0]*len_string
tmp=0
tmp_tmp=0
for i in range(1,len_string):
    if(string[i]==string[tmp]):
        tmp_tmp=tmp
        while(string[i]==string[tmp_tmp] and tmp_tmp >0):
            tmp_tmp=common_length[max([tmp_tmp-1,0])]
        common_length[i-1]=tmp_tmp
        tmp+=1
    else:
        common_length[i-1]=tmp
        while(string[i]!=string[tmp] and tmp>0):
            tmp=common_length[max([tmp-1,0])]

if(string[-1]==string[tmp-1]):
    common_length[-1]=tmp
common_length[0]=0


tmp=0

for i in range(len(text)):
    if(text[i]!=string[tmp]):
        while(text[i]!=string[tmp] and tmp>0):
            tmp=common_length[max([tmp-1,0])]
        if(text[i]==string[tmp]):
            tmp+=1
    else:
        tmp+=1
        if(tmp==len_string):
            print(i-tmp+1)
            tmp=common_length[-1]
### BUGGY CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
        updates.append([nw, nv])
    else:
      t[nw] = nv
      updates.append([nw, nv])
  for u in updates:
    for key in list(t.keys()):
      if u[0] > key and u[1] >= t[key]:
        del t[key]
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

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

dp = [10**18] * (10**5+10)
dp[0] = 0

for i in range(n-1):
  k = min(k, n-i-1)
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1], dp[i] + abs(h[i+j+1] - h[i]))

print(dp[n-1])

### FIXED CODE ###

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

dp = [10**18] * (10**5+10)
dp[0] = 0

for i in range(n-1):
  k = min(k, n-i-1)
  for j in range(k):
    dp[i+j+1] = min(dp[i+j+1], dp[i] + abs(h[i+j+1] - h[i]))

print(dp[n-1])
### BUGGY CODE ###

import itertools
S=input()
# S = "??2??5"
# S = "?44"
# S = "?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"
# S = "".join(["1" for _ in range(10**5)])
ROT = [1,10,9,12,3,4]
rcnt = [0 for i in range(6)]
MOD = 10**9+7
remain = 0
mod = -1
for i,ss in enumerate(S[::-1]):
  mod = (mod+1)%6
  r = ROT[mod]
  # print(ss,r)
  if ss=="?":
    rcnt[mod] += 1
  else:
    remain += int(ss)*10**i
    remain = remain%13

# print(rcnt, remain)

dp = {}

for rem in range(13):
  dp[(0,rem)] = 0
dp[(0,0)] = 1
for i in range(1,max(rcnt)+1):
  for rem in range(13):
    dp[(i, rem)] = 0
  for rem in range(13):
    for num in range(10):
      key = (i,(rem+num)%13 )
      # if key == (2,0):
      #   print(rem,num, dp[(i-1,rem)])
      dp[key] += dp[(i-1,rem)]

# print(dp)

seq = list(range(13))
am = 0
for k in itertools.product(seq,repeat=6):
  sm = 0
  for i in range(6):
    sm += k[i]*ROT[i]
  if (sm+remain)%13==5:
    cros = 1
    for i in range(6):
      cros*=dp[(rcnt[i], k[i])]
    # if cros>=1:
      # print(k, cros)
    am = (am+cros)%MOD
print(am)


### FIXED CODE ###

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)
### BUGGY CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].append(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = list()
            for nxt in dp[i-1][j]:
                tmp += dp[0][nxt]
            dp[i][j] = set(tmp)
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N*3)]
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].add(N*1+v)
        adj[N*1+u].add(N*2+v)
        adj[N*2+u].add(v)
    S, T = map(int, input().split())
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost//3)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


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

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

bit = [0] * 60
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    c = 0
    for x in a:
        if x >> i & 1:
            c += 1
    ans = (ans + c * (n - c) * (2 ** i)) % mod

print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

bit = [0] * 60
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    n1 = np.count_nonzero((a >> i) & 1)
    n0 = n - n1
    ans += (2 ** i) * n1 * n0 % mod
print(ans % mod)
### BUGGY CODE ###

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

dp = [[None for _ in range(N+1)] for _ in range(W+1)]

items = []
for _ in range(N):
  items.append(list(map(int,input().split())))

def f(dp,wleft,index):
  if index > N:
    return 0
  if dp[wleft][index] is not None:
    return dp[wleft][index]
  
  if wleft < items[index-1][0]:
    return f(dp,wleft,index+1)
  dp[wleft][index] = max(f(dp,wleft,index+1),items[index-1][1]+f(dp,wleft-items[index-1][0],index+1))
  return dp[wleft][index]
  
print(f(dp,W,1))


### FIXED CODE ###

import numpy as np
N,W = map(int, input().split())
# np.maximum https://www.sejuku.net/blog/69175
# 第一引数と第二引数の大小関係を要素ごとに比較して、大きい方を格納した配列を返す
dp = np.zeros(W+1, dtype=np.int64)
# その重さでの最大valueが保存されている
for _ in range(N):
    w,v = map(int,input().split())
    # w以下ならvを足したもの、w以上ならそのままの値で、最大値を求める
    # 出力はw以上の配列として返す(それ以下は重さwなので関与しない)
    # 足す場合が前者、足さない場合が後者
    np.maximum(dp[:W-w+1]+v,dp[w:],out=dp[w:]) 

print(dp[-1])
### BUGGY CODE ###

import numpy as np
from numba import jit

@jit
def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if np.all(num_light == n):
    break
    
print(*num_light)


### FIXED CODE ###

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)
### BUGGY CODE ###

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

count = 0
for i in range(N):
    if min(arr[0:i+1]) >= arr[i]:
        count += 1

print(count)

### FIXED CODE ###

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

count = 0
mn = float('inf')
for i in range(N):
    if mn >= arr[i]:
        count += 1
        mn =min(mn,arr[i])

print(count)
### BUGGY CODE ###

def is_ok(arg):
  #問題の定義
  return l[i]-l[j] < l[arg]
 
def nibutan(ng,ok):
  while (abs(ok-ng)>1):
    mid = (ok+ng)//2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

n = int(input())
l = list(map(int,input().split()))
c = 0
l.sort(reverse=True)
for i in range(n-2):
  for j in range(i+1,n-1):
    a = nibutan(n,j)
    c += a-j
print(c)

### FIXED CODE ###

#関数を持ってくる
from bisect import bisect_left
#入力
n = int(input())
l_list = list(map(int,input().split()))
#ソート
l_list.sort()
#答えの数を数えるものを作る
ans = 0
#三角形の中で一番短い辺aに対して
for i in range(n-2):
  a = l_list[i]
  #2番目に短い辺bが存在し
  for j in range(i+1,n-1):
    b = l_list[j]
    #一番長い辺cの下限値であるa+bのリスト内で入る位置x
    x = bisect_left(l_list,a+b)
    #cとして考えられる値はjとxの間の個数
    ans += x-j-1
print(ans)
### BUGGY CODE ###


line = int(input())

v1 = 1
for i in range(1,line+1) :
  v1 = v1 * i
	
print(v1%(10**9+7))

### FIXED CODE ###


line = int(input())

v1 = 1
for i in range(1,line+1) :
  v1 = v1 * i % (10**9+7)
	
print(v1)
### BUGGY CODE ###

s = input()
k = int(input())
x = []
n = len(s)
for i in range(n):
    for j in range(n-i):
        t = s[j:j+i+1]
        if not t in x:
            x.append(t)
x.sort()
print(x[k-1])

### FIXED CODE ###

s = input()
k = int(input())
x = []
n = len(s)
for i in range(k):
    for j in range(n-i):
        t = s[j:j+i+1]
        if not t in x:
            x.append(t)
x.sort()
print(x[k-1])