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

N = int(input())
sX = input()
 
origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1
 
one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2) + int(b) % one_r_count
    zero_mod = (zero_mod * 2 ) + int(b) % zero_r_count
 
f = [0] * 220000
pop = [0]* 220000
 
for i in range(1,220000):
    pop[i] = pop[i//2] + i%2
    f[i] = f[i % pop[i]] + 1
    
onepow = [1] * 220000
zeropow = [1]* 220000
 
for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count
 
for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

### FIXED CODE ###

N = int(input())
sX = input()

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    if sX[i-1] == '0':
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, M, K = [int(s) for s in input().split()]
n = 0
A = [0]
for s in input().split():
    n = n + int(s)
    A.append(n)

n = 0
B = [0]
for s in input().split():
    n = n + int(s)
    B.append(n)

ans = 0
for i, a_time in enumerate(A):
    if a_time <= K:
        for j, b_time in enumerate(B):
            read_time = a_time + b_time
            if read_time <= K:
                if ans <= i + j:
                    ans = i + j
            else:
                break
    else:
        break

print(ans)

### FIXED CODE ###

import sys

N, M, K = [int(s) for s in sys.stdin.readline().split()]
n = 0
A = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    A.append(n)

n = 0
B = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    B.append(n)

ans = 0
for i in range(N + 1):
    if A[i] > K:
        break
    for j in range(M, -1, -1):
        if A[i] + B[j] <= K:
            ans = max(ans, i + j)
            M = j
            break

print(ans)
### BUGGY CODE ###

from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, a, b = map(int, readline().split())
  fact = [1, 1]  # fact[n] = (n! mod p)
  factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
  inv = [0, 1]  # factinv 計算用
  
  for i in range(2, n + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)
  
  def cmb(n, r, mod):
    if (r < 0) or (n < r):
      return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
  if n==2:
    print(0)
  else:
    total = pow(2, n, MOD) %MOD
    nca = cmb(n,a,MOD)
    ncb = cmb(n,b,MOD)
    ans = (total-nca-ncb-1)%MOD
    print(int(ans))
  
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

#nが大きいがa,bが小さいので、a,bを個別に計算する

def main():
  n, a, b = map(int, readline().split())
  def nCr(r):
    bunshi = 1
    bunbo = 1
    for i in range(r):
      bunshi = (bunshi * (n-i)) % MOD
      bunbo = (bunbo * (i+1)) % MOD
    return bunshi * pow(bunbo, MOD - 2, MOD) % MOD
  
  if n==2:
    print(0)
  else:
    total = pow(2, n, MOD) %MOD
    nca = nCr(a)
    ncb = nCr(b)
    ans = (total-nca-ncb-1)%MOD
    print(int(ans))
  
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        for i in range(n):
            if int(s[i])%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    keta = n-1
    for i, si in enumerate(s):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= int(si)*10**keta
        keta -= 1
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

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

N = int(input())
S = list(input().strip())

Is = [1 if s == 'W' else 0 for s in S]

res = N
for i in range(0,N):
 left = Is[:max(i - 1,0)]
 right = Is[min(i + 1,N - 1):]
 tmp = sum(left) + (len(right) - sum(right))
 res = min(tmp,res)

print(res)

### FIXED CODE ###

N = int(input())
S = list(input().strip())

cnt = S[1:].count('E')

res = cnt
for i in range(1,N):
    if S[i] == 'E':
        cnt -= 1
    if S[i - 1] == "W":
        cnt += 1
    res = min(res,cnt)

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

n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [10, 20, 30, 40]
inf = 10**20
DP = [[None for r in range(n+1)] for l in range(n)]
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])


def f(l, r):
    if r <= l+1:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    DP[l][r] = S[r]-S[l]+min([f(l, i)+f(i, r) for i in range(l+1, r)])
    return DP[l][r]


print(f(0, n))


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [10, 20, 30, 40]
inf = 10**20
DP = [[None for r in range(n+1)] for l in range(n)]
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])


def f(l, r):
    if r <= l+1:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    DP[l][r] = S[r]-S[l]+min([f(l, i)+f(i, r) for i in range(l+1, r)])
    return DP[l][r]


print(f(0, n))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc127/abc127_d
import sys
from itertools import chain

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    A = i2nn()
    bc = [0] * M
    for j in range(M):
        B, C = i2nn()
        bc[j] = [C] * B
    A.extend(chain.from_iterable(bc))
    A.sort(reverse=True)
    print(sum(A[:N]))
    return

main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc127/abc127_d
import sys
from operator import itemgetter

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

      


def main():
    N, M = i2nn()
    A = [(1, x) for x in i2nn()]
    S = [0] * M
    for j in range(M):
        S[j] = tuple(i2nn())
    S.extend(A)
    R = sorted(S, key=itemgetter(1))
    sum = 0
    while True:
        p = R.pop()
        if N - p[0] > 0:
            sum += p[0] * p[1]
            N -= p[0]
        else:
            sum += p[1] * N
            break
    print(sum)
    return

main()
### BUGGY CODE ###

from collections import Counter


def main():
    n = int(input())
    ss = [input() for _ in range(n)]
    max_num = Counter(ss).most_common()[0][1]
    max_verbs = [Counter(ss).most_common()[0][0]]
    for i in range(1, len(Counter(ss).most_common())):
        if Counter(ss).most_common()[i][1] != max_num:
            break
        max_verbs.append(Counter(ss).most_common()[i][0])

    max_verbs = sorted(max_verbs)
    for ans in max_verbs:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    ss = {}
    max_s = 0
    for _ in range(n):
        s = input()
        if s not in ss:
            ss[s] = 0
        else:
            ss[s] += 1
            max_s = max(max_s, ss[s])

    ss = sorted(ss.items(), key=lambda x: x[0])
    anss = [s for s, i in ss if i == max_s]
    for ans in anss:
        print(ans)


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

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

cnt = 0
for i in range(N):
    if P[i] == min(P[:i+1]):
        cnt += 1
print(cnt)

### FIXED CODE ###

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

m = P[0] #その時点での最小値
cnt = 1 #P[0]の時点でcnt=1
for i in range(N):
    if P[i] < m:
        m = P[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
S = []
m = 0
for i in range(n):
    S.append(input())
A = set(S)
al = {}
for i in A:
    al[i] = S.count(i)
    if S.count(i) > m:
        m = S.count(i)
s = []
for i in al:
    if al[i] == m:
        s.append(i)
s.sort()
for i in s:
    print(i)

### FIXED CODE ###

import collections

n = int(input())
S = []
for i in range(n):
    S.append(input())

a = collections.Counter(S)
m = max(a.values())
s = []
for i in a:
    if a[i] == m:
        s.append(i)
s.sort()
for i in s:
    print(i)
### BUGGY CODE ###

N = input()

l = []

for i in range(N):
    x = input()
    if (x in l):
        l.remove(x)
    else:
        l.append(x)

print len(l)


### FIXED CODE ###

N = input()

l = []

for i in range(N):
    l.append(input())

l.sort()

ptr = 0
res = 0
while ptr < N:
    cc = l[ptr]
    f = 0
    while (ptr < N and l[ptr] == cc):
        f += 1
        ptr += 1
    res += f%2

print res
### BUGGY CODE ###

class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

    def insert(self, key):
        i = len(self.keys)
        self.keys.append(key)
        parent = (i - 1) // 2
        while i > 0 and self.keys[parent] < self.keys[i]:
            self.keys[i], self.keys[parent] = self.keys[parent], self.keys[i]
            i = parent
            parent = (parent - 1) // 2

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        print(max_key)


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        S.heapExtraMax()
    else:
        pass

### FIXED CODE ###

def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey
    setHeapDown_max(heap, pos)

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

ans = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        ans.append(heapPop_max(S))
    else:
        pass

print(*ans, sep = '\n')
### BUGGY CODE ###

def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0 for i in range(t)] for j in range(n + 1)]
    ls = [[[] for i in range(t)] for j in range(n + 1)]
    for i in range(n):
        for j in range(t):
            if j - f[i][0] >= 0 and dp[i][j - f[i][0]] + f[i][1] > dp[i][j]:
                dp[i + 1][j] = dp[i][j - f[i][0]] + f[i][1]
                ls[i + 1][j] = ls[i][j - f[i][0]] + [i]
            else:
                dp[i + 1][j] = dp[i][j]
                ls[i + 1][j] = ls[i][j][:]
    res = dp[n][t - 1]
    ff = [f[i][1] for i in range(n) if not i in ls[n][t - 1]]
    if ff:
        return res + max(ff)
    else:
        return res


print(main())


### FIXED CODE ###



def main():
    n, t = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(n)]
    dp1 = [[0 for i in range(t)]for j in range(n+1)]
    dp2 = [[0 for i in range(t)]for j in range(n+1)]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[i][0] >= 0:
                dp1[i+1][j] = max(dp1[i][j - f[i][0]] + f[i][1],dp1[i][j])
            else:
                dp1[i+1][j] = dp1[i][j]
    for i in range(n):
        for j in range(t - 1, -1, -1):
            if j - f[n-1-i][0] >= 0:
                dp2[i+1][j] = max(dp2[i][j - f[n-1-i][0]] + f[n-1-i][1],dp2[i][j])
            else:
                dp2[i+1][j] = dp2[i][j]

    res = 0
    for i in range(n):
        for j in range(t):
            res = max(res,dp1[i][j]+f[i][1]+dp2[n-1-i][t-1-j])

    return res




print(main())
### BUGGY CODE ###

s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]  + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)

### FIXED CODE ###

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)
### BUGGY CODE ###

from itertools import permutations
n, m, r = map(int, input().split())
goals = list(map(int, input().split()))
goals = [g-1 for g in goals]

g = [[pow(10, 16)] * n for i in range(n)]

for i in range(m):
    a, b , c = map(int,input().split())
    a-=1; b-=1
    g[a][b] = c
    g[b][a] = c

for i in range(n):
    for s in range(n):
        for t in range(n):
            g[s][t] = min(g[s][t], g[s][i] + g[i][t])

ans = float('inf')
for p in permutations(goals):
    cost = 0
    for s,t in zip(p[:-1], p[1:]):
        cost += g[s][t]
    ans = min(ans, cost)
print(ans)


### FIXED CODE ###

from itertools import permutations
n, m, r = map(int, input().split())
goals = list(map(int, input().split()))
goals = [g-1 for g in goals]

g = [[pow(10, 16)] * n for i in range(n)]

for i in range(m):
    a, b , c = map(int,input().split())
    a-=1; b-=1
    g[a][b] = c
    g[b][a] = c

for i in range(n):
    for s in range(n):
        for t in range(n):
            g[s][t] = min(g[s][t], g[s][i] + g[i][t])

ans = float('inf')
for p in permutations(goals):
    cost = 0
    for s,t in zip(p[:-1], p[1:]):
        cost += g[s][t]
    ans = min(ans, cost)
print(ans)
### BUGGY CODE ###

e = list(map(int,input().split()))
a = e[0]
b = e[1]
c = e[2]
d = e[3]
cnt = 0

for i in range(a,b+1):
    if (int(i/c)-i/c != 0) and (int(i/d)-i/d != 0):
        cnt += 1
    else:
        pass
print(cnt)

### FIXED CODE ###

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

def gcd(x,y):
    while y !=0:
        x,y = y,x%y
    return x

def sums(x):
    S1 = x//c
    S2 = x//d
    S3 = x// (c*d//gcd(c,d))
    return x - S1 - S2 + S3


print(sums(b)-sums(a-1))
### BUGGY CODE ###

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

ans = 0

for x in range(min(a),max(a)+1):
    tmp = 0
    tmp += a.count(x)
    tmp += a.count(x-1)
    tmp += a.count(x+1)
    
    ans = max(ans,tmp)
    
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
cnt = [0] * 100010
for a in A:
    if a > 0:
        cnt[a - 1] += 1
    cnt[a] += 1
    cnt[a + 1] += 1

print(max(cnt))
### BUGGY CODE ###

X = int(input())
x = 1
while ((x-1)**2)*9 < X:
    x += 1
for i in range(x):
    for j in range(-x, i):
        if i**5-j**5 == X:
            a = [i,j]
            break 
print(*a)


### FIXED CODE ###

X = int(input())
x = 1
while ((x-1)**4)*5 < X:
    x += 1
for i in range(x):
    for j in range(-x, i):
        if i**5-j**5 == X:
            a = [i,j]
            break 
print(*a)
### BUGGY CODE ###

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

one, two, three = 0, 0, 0
for ai in a:
    if ai == 1: one += 1
    if ai == 2: two += 1
    if ai == 3: three += 1

u = N + 10
dp = [[[-1]* u for _ in range(u)] for _ in range(u)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    res = 0
    if i > 0: res += rec(i-1, j, k) * i
    if j > 0: res += rec(i+1, j-1, k) * j
    if k > 0: res += rec(i, j+1, k-1) * k
    res += N
    res /= (i + j + k)
    dp[i][j][k] = res

    return res

rec(one, two, three)
print(dp[one][two][three])

### FIXED CODE ###

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

one, two, three = 0, 0, 0
for ai in a:
    if ai == 1: one += 1
    if ai == 2: two += 1
    if ai == 3: three += 1

u = N + 1
dp = [[[-1]* u for _ in range(u)] for _ in range(u)]
dp[0][0][0] = 0

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

print(rec(one, two, three))
### BUGGY CODE ###

import numpy as np

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

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

  for i in range(N):
    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:
      amari = (10 ** i) % 13
      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 ###

import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

label = [-1] * N
n_label = [0] * N

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, lab):
    if label[v] != -1:
        return 0
    label[v] = lab
    n_label[lab] += 1
    for n in F[v]:
        dfs(n, lab)
    return 1


# labeling
count = 0
for i in range(N):
    count += dfs(i, count)
n_label = n_label[:count]

# calc friend candidate
blocked = 0
for b in B[0]:
    if label[b] == label[0]:
        blocked += 1
print(n_label[label[0]] - 1 - len(F[0]) - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if label[b] == label[i]:
            blocked += 1
    print(n_label[label[i]] - 1 - len(F[i]) - blocked, end='')
print('')


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

label = [-1] * N
n_label = [0] * N

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, lab):
    if label[v] != -1:
        return 0
    label[v] = lab
    n_label[lab] += 1
    for n in F[v]:
        dfs(n, lab)
    return 1


# labeling
count = 0
for i in range(N):
    count += dfs(i, count)
n_label = n_label[:count]

# calc friend candidate
blocked = 0
for b in B[0]:
    if label[b] == label[0]:
        blocked += 1
print(n_label[label[0]] - 1 - len(F[0]) - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if label[b] == label[i]:
            blocked += 1
    print(n_label[label[i]] - 1 - len(F[i]) - blocked, end='')
print('')