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

# この方法だと、
# 参加している女性の数を数える部分 : c = bin(state).count('1')
# 一人減らして場合の数を足す部分 : for i in range(N): ...
# で、それぞれO(N)なので、
# 全体として 2 * N * 2**N 回の計算が必要
# 最大で N = 21 のときは間に合わない

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7

dp = [0]*(2**N)
dp[0] = 1


for state in range(1, 2**N):
  c = bin(state).count('1')
  for i in range(N):
    if state & (1<<i):
      dp[state] += dp[state ^ (1<<i)]*A[c-1][i]
      dp[state] %= MOD

print(dp[2**N-1])

### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7

dp = [-1]*(2**N)
dp[0] = 1

# stateを二進数で表したときに、1である桁番号の女性がマッチングに参加
# 男性側は前から固定で女性と同じ人数だけ参加
def solve(state, c):
  global dp
  if dp[state] >= 0:
    return dp[state]
  else:
    dp[state] = 0 # 一旦、値を0に戻しておく
    for i in range(N):
      if state & (1<<i) and A[c-1][i]: 
        # i番目の女性がマッチングに参加しており、なおかつ
        # 最後の男性との相性が良い場合は、その2人でペアを作った場合の組合せを足し合わせる
        dp[state] += solve(state ^ (1<<i), c-1)
        dp[state] %= MOD
    
    return dp[state]

print(solve(2**N-1, N))
### BUGGY CODE ###

N = int(input())
As = str(input()).split(' ')
a_s = [int(a) for a in As]

sum = 0
index = 0
for Ai in a_s:
  for Aj in a_s[index+1:]:
    sum += Ai ^ Aj
  index += 1

  
print(sum%(10**9+7))

### FIXED CODE ###

N = int(input())
As = str(input()).split(' ')
a_s = [int(a) for a in As]

import numpy as np
a_s = np.array(a_s)
sum = 0
index = 0
for n in range(60):
  b = (a_s >> n) & 1
  x = np.count_nonzero(b)
  y = N - x
  ans = x * y
  for _ in range(n):
    ans *= 2
  sum += ans
  
print(sum%(10**9+7))
### BUGGY CODE ###

def main():
    ini_inp=list(map(lambda x:int(x),input().split()))
    N=ini_inp[0]
    M=ini_inp[1]

    L=[]
    R=[]
    for i in range(M):
        sec_inp=list(map(lambda x:int(x),input().split()))
        L.append(sec_inp[0])
        R.append(sec_inp[1])

    temp=set([i for i in range(1,N+1)])
    for i in range(M):
        number=set([i for i in range(L[i],R[i]+1)])
        temp=number & temp
        if len(temp)==0:
            break
    print(len(temp))

if __name__=="__main__":
    main()
        


### FIXED CODE ###

def main():
    ini_inp=list(map(lambda x:int(x),input().split()))
    N=ini_inp[0]
    M=ini_inp[1]

    L=[]
    R=[]
    for i in range(M):
        sec_inp=list(map(lambda x:int(x),input().split()))
        L.append(sec_inp[0])
        R.append(sec_inp[1])

    low=L[0]
    up=R[0]
    flag=0
    for i in range(1,M):
        if L[i]>up:
            flag=1
            break
        elif L[i]>=low:
            low=L[i]
        elif R[i]<=up:
            up=R[i]

    if flag==0:
        print(up-low+1)
    else:
        print(0)

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

from statistics import median


N = int(input())

X = input().split()
X = [ int(x) for x in X]
"""
N = 4
X = [2,4,4,3]
"""

#F = copy.deepcopy(X)
F = X[:]
F.sort()

median1 = int(N/2 - 1)
median2 = int(N/2) 

for i in range(N):
    #print(F, median1, median2)
    
    if X[i] < median(F):
        ans = F[median2]
    else:
        ans = F[median1]
    print(int(ans))

### FIXED CODE ###

from statistics import median, median_low, median_high


N = int(input())

X = input().split()
X = [ int(x) for x in X]
"""
N = 4
X = [2,4,4,3]
"""
median = median(X)
#F = copy.deepcopy(X)
"""
F = X[:]
F.sort()

median1 = int(N/2 - 1)
median2 = int(N/2) 

if median.is_integer():
    median1 = median
    median2 = median
else:
    median1 = median - 0.5
    median2 = median + 0.5
"""
median1 = median_low(X)
median2 = median_high(X)
   
for i in range(N):
    #print(F, median1, median2)
    
    if X[i] < median:
        ans = median2
    else:
        ans = median1
    print(int(ans))
### BUGGY CODE ###

n,q=map(int,input().split())
par=[-1 for i in range(n+1)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
p=[-1 for i in range(n+1)]
p[1]=0
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    x,y=a,b
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
        x,y=y,x
    par[a]+=par[b]
    par[b]=a
    p[b]=x
    
    return True
ll=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    ll.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

l=[0 for i in range(n+1)]
for i in range(q):
    r=[int(j) for j in input().split()]
    l[r[0]]+=r[1]
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs=[]
for i in range(n+1):
    inputs.append((p[i],i,l[i]))
g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, 0)
ans=[]
for i in range(1,n+1):
    ans.append(d.shortest_distance(i))

print(*ans)

### FIXED CODE ###

from collections import deque
n,q=map(int, input().split())
l=[[] for i in range(n+1)]
ans=[0]*(n+1)

for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l[a].append(b)
    l[b].append(a)
for i in range(q):
    p,x=[int(j) for j in input().split()]
    ans[p]+=x

que=deque()
que.append(1)
ll=[0]*(n+1)
while que:
    y=que.popleft()
    ll[y]=1
    for i in l[y]:
        if ll[i]==1:
            continue
        ans[i]+=ans[y]
        que.append(i)
print(*ans[1:])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]

nl = []
for i in range(N):
    for j in range(l[i][1]):
        nl.append(l[i][0])
    
sorted_nl = sorted(nl)

ans = 0
for i in range(M):
    ans += sorted_nl[i]
    
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]

sl = sorted(l)
buy = 0
ans = 0
for i in range(N):
    for j in range(sl[i][1]):
        if buy < M:
            ans += sl[i][0]
            buy += 1
        else:
            break

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

import sys

mod = 10**9 + 7
S = sys.stdin.readline().strip()

S = S[::-1]
ls = len(S)
dp = [0] * 13
dp[0] = 1
for i in range(ls):
    ndp = [0] * 13
    # print("S", S[i])
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
                r = k * pow(10, i, 13) + j
                r %= 13
                ndp[r] += dp[j]
                ndp[r] %= mod

        else:
            n = int(S[i])
            r = n * pow(10, i, 13) + j
            r %= 13
            ndp[r] += dp[j]
            ndp[r] %= mod

    # print(ndp)
    dp = ndp

print(dp[5])

### FIXED CODE ###

import sys

mod = 10**9 + 7
S = sys.stdin.readline().strip()

S = S[::-1]
ls = len(S)
dp = [0] * 13
dp[0] = 1
for i in range(ls):
    ndp = [0] * 13
    # print("S", S[i])
    for j in range(13):
        if dp[j] == 0:
            continue
        digit = pow(10, i, 13)
        if S[i] == "?":
            for k in range(10):
                r = k * digit + j
                r %= 13
                ndp[r] += dp[j]
                ndp[r] %= mod

        else:
            n = int(S[i])
            r = n * digit + j
            r %= 13
            ndp[r] += dp[j]
            ndp[r] %= mod

    # print(ndp)
    dp = ndp

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

n = int(input())
ans = 0
for a in range(1,n):
    for b in range(1,n):
        if a * b < n:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1,n):
    for b in range(1,a+1):
        if a * b < n:
            if a == b:
                ans += 1
            else:
                ans += 2
        else:
            break
print(ans)
### BUGGY CODE ###

import sys
N = int(input())
N = list(map(int,input().split()))
C= 1
if N==0:
    sys.exit()
for i in N:
  C = C*i
  if C > (10 ** 18):
    C=-1
print(C)

### FIXED CODE ###

def mul2():
    n = int(input())
    a = list(map(int, input().split()))
    
    if 0 in a:
        return 0
    ans = 1
    for i in a:
        ans *= i
        if ans > 1000000000000000000:
            return -1
        
    return ans 
print(mul2())
### BUGGY CODE ###

import math

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

def comb(m, n):
    return math.factorial(m) // (math.factorial(n) * math.factorial(m - n))


B = set(A)
for i in B:
    f = A.count(i)
    if f>=2:
        tt = tt + comb(f, 2)

for i in range(N):
    f = A.count(A[i])
    if f>=3:
        ans.append(tt - comb(f, 2) + comb(f-1, 2))
    elif f==2:
        ans.append(tt - comb(f, 2))
    else:
        ans.append(tt)

for i in ans:
    print(i)

### FIXED CODE ###

def main():
    import math
    import collections
    N = int(input())
    A = list(map(int, input().split()))
    tt = 0
    #ans = list()
    ann = 0

    def comb(m, n):
        #return math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
        return ((m - 1 + 1) / 1) * (m - 2 + 1) / 2

    '''
    def A_count(n):
        if n in memo:
            return memo[n]
        h = A.count(i)
        memo[n] = A.count(i)
        return h
    '''

    C = collections.Counter(A)
    for i in C.values():
        if i>=2:
            tt = tt + comb(i, 2)

    for i in A:
        f = C[i] #A_count(A[i])
        if f>=3:
            ann = (tt - comb(f, 2) + comb(f-1, 2))
        elif f==2:
            ann = tt - comb(f, 2)
        else:
            ann = tt
        print(int(ann))

    #for i in ans:
    #    print(i)


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

import sys
n, limit = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)
dp = [{} for i in range(n+1)]

for i in range(n):
    Lw, Lv =L[i][0], L[i][1] #①i番目の価値を重さテーブルに代入
    dp[i+1][Lw] = Lv 
    for w, v in dp[i].items():
        dp[i+1][w] = max(dp[i+1].get(w, 0), v) #② 一つ上の行の価値と比べて大きい方を代入
        if w + Lw <=limit:
            dp[i+1][w+Lw] = max(dp[i].get(w+ Lw, 0), Lv + v) #③一つ上の行の価値をループで1つづつ取り出し、i番目の価値と足し合わせる
        
print(max(dp[-1].values()))

### FIXED CODE ###

import sys
n, W = map(int, sys.stdin.readline().split())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0 for _ in range(W+1)] for _ in range(n)]
for w in range(W+1):
    if w>=L[0][0]:
        dp[0][w] = L[0][1]

#print(dp)
for i in range(1, n):
    for w in range(W+1):
        if w <L[i][0]: #そもそも加えられないとき
            dp[i][w] = dp[i-1][w] #前回の状態を代入。
        else: #加えようとしたら入るとき
            dp[i][w] = max(dp[i-1][w-L[i][0]] + L[i][1], dp[i-1][w]) #max(加えた時の価値, 前回の状態)
            
#print(dp)
print(max(dp[-1]))
### BUGGY CODE ###

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

total=1
for i in range(1,N):
    A=P[:i:]
    if P[i]<min(A):
        total+=1
print(total)

### FIXED CODE ###

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

total=1
minP=P[0]
for i in range(1,N):
    if P[i]<minP:
        total+=1
        minP=P[i]
print(total)
### BUGGY CODE ###

from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
queue = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
# for i in range(H):
#     for j in range(W):
#         if field[i][j] == True:
#             queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append((nh,nw))
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

import numpy

n,m = map(int,input().split(" "))
gates = []
for i in range(m):
    gates.append(list(map(int,input().split(" "))))

result = numpy.ones(n)

for card in gates:

    result[:(card[0])-1] = 0
    result[card[1]:] = 0

print(sum(result == 1))

### FIXED CODE ###



n,m = map(int,input().split(" "))
gates = []
for i in range(m):
    gates.append(list(map(int,input().split(" "))))

result = [1, n]

for card in gates:
    if result[0] < card[0]:
        result[0] = card[0]
    if result[1] > card[1]:
        result[1] = card[1]

tmp = result[1] - result[0] + 1 
if tmp >= 0:
    print(tmp)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
import itertools
A = []
t = 0
for i in range(n):
    A.append(sorted(list(input())))
for i in list(itertools.combinations(A,2)):
    a, b = i
    if a == b:
        t += 1
print(t)

### FIXED CODE ###

n = int(input())
import itertools
A = []
t = 0
for i in range(n):
    A.append("".join(sorted(list(input()))))


import collections

C = collections.Counter(A)


for i in C.values():
    t += i * (i - 1) // 2
print(t)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal, ROUND_CEILING
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

R, C, K = MAP()

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

field = [[0]*(C+1)] + [[0]*(C+1) for _ in range(R)]

for _ in range(K):
    r, c, v = MAP()
    field[r][c] = v

for i in range(1, R+1):
    for j in range(1, C+1):
        up_max = max(dp[i-1][j])
        p = field[i][j]
        dp[i][j][0] = max(up_max, dp[i][j-1][0])
        dp[i][j][1] = max(up_max+p, dp[i][j-1][1], dp[i][j-1][0]+p)
        dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1]+p)
        dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2]+p)

print(max(dp[R][C]))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal, ROUND_CEILING
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

R, C, K = MAP()

dp1 = [[0]*4 for _ in range(C+1)]
dp2 = [[0]*4 for _ in range(C+1)]

field = [[0]*(C+1)] + [[0]*(C+1) for _ in range(R)]

for _ in range(K):
    r, c, v = MAP()
    field[r][c] = v

for i in range(1, R+1):
    for j in range(1, C+1):
        if i%2 == 0:       
            up_max = max(dp1[j])
            p = field[i][j]
            dp2[j][0] = max(up_max, dp1[j-1][0])
            dp2[j][1] = max(up_max+p, dp2[j-1][1], dp2[j-1][0]+p)
            dp2[j][2] = max(dp2[j-1][2], dp2[j-1][1]+p)
            dp2[j][3] = max(dp2[j-1][3], dp2[j-1][2]+p)
        else:
            up_max = max(dp2[j])
            p = field[i][j]
            dp1[j][0] = max(up_max, dp2[j-1][0])
            dp1[j][1] = max(up_max+p, dp1[j-1][1], dp1[j-1][0]+p)
            dp1[j][2] = max(dp1[j-1][2], dp1[j-1][1]+p)
            dp1[j][3] = max(dp1[j-1][3], dp1[j-1][2]+p)

a = max(dp1[-1])
b = max(dp2[-1])
print(max(a, b))
### BUGGY CODE ###

import sys

def intinput():
    return map(int,sys.stdin.readline().split())

n,m=intinput()
a = list(intinput())
a.sort()
l = []
for i in range(m):
    b,c=intinput()
    for j in range(b):
        l.append(c)
l.sort(reverse=1)
if len(l)<len(a):
    for r in range(len(a)-len(l)):
        l.append(0)
sum=0
for i in range(len(a)):
    sum += max(a[i],l[i])
print(sum)

### FIXED CODE ###

import sys

def intinput(): return map(int,sys.stdin.readline().split())

n,m=intinput()
a = list(intinput())
a = [(a[x],1) for x in range(n)]
for i in range(m):
    b,c=intinput()
    a.append((c,b))
a.sort(reverse=1)
res,cnt=0,n
for (x,y) in a:
    k = min(cnt,y)
    res += k*x
    cnt -= k
print(res)
### BUGGY CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import product, combinations, permutations
from copy import deepcopy
import sys
sys.setrecursionlimit(4100000)
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = len(A)%K
    prev = None
    L = 0

    for i in range(N-K+1):
        check = A[i:i+K]
        if i==0:
            acc = 1
            for c in check:
                acc *= c
                prev = acc
        else:
            acc = 1
            for c in check:
                acc *= c
            if prev<acc:
                print("Yes")
            else:
                print("No")
            prev = acc

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
ACC = []
ACC.append(0)
sum = 0
for a in A:
    sum += a
    ACC.append(sum)


L = N-K+1
prev = ACC[K] - ACC[0]
for i in range(1, L):
    score = ACC[i+K] - ACC[i] 
    if prev < score:
        print("Yes")
    else:
        print("No")
    prev = score
### BUGGY CODE ###

class Mod13DPTable:
    MOD = 10**9 + 7
    def __init__(self, length):
        self.mod13 = [{j:0 for j in range(13)} for i in range(length)]
        self.MOD = 10**7 + 7
    def set_start(self, units_digit):
        if units_digit == '?':
            for i in range(10):
                self.mod13[0][i] = 1
        else:
            self.mod13[0][int(units_digit)] = 1
    def get_table(self, digit):
        return self.mod13[digit]
    def update(self, num, digit):
        for k, v in self.mod13[digit-1].items():
            remain = ((num * 10**digit) + k) % 13
            self.mod13[digit][remain] = (self.mod13[digit][remain] + v) % Mod13DPTable.MOD
            
def main():
    MOD = 10**9 + 7
    S = input()
    mod13dp = Mod13DPTable(len(S))
    mod13dp.set_start(S[-1])
    for i, m in enumerate(reversed(list(S[:-1]))):
        i += 1
        if m == '?':
            for j in range(10):
                mod13dp.update(j, i)
        else:
            mod13dp.update(int(m), i)
    print(mod13dp.get_table(-1)[5])
main()

### FIXED CODE ###

class Mod13DPTable:
    MOD = 10**9 + 7
    def __init__(self, length):
        self.mod13 = [{j:0 for j in range(13)} for i in range(length)]
        self.MOD = 10**7 + 7
    def set_start(self, units_digit):
        if units_digit == '?':
            for i in range(10):
                self.mod13[0][i] = 1
        else:
            self.mod13[0][int(units_digit)] = 1
    def get_table(self, digit):
        return self.mod13[digit]
    def update(self, num, digit, multi):  # multi = 10**digit % 13
        for k, v in self.mod13[digit-1].items():
            remain = ((num * multi) + k) % 13
            self.mod13[digit][remain] = (self.mod13[digit][remain] + v) % Mod13DPTable.MOD
            
def main():
    MOD = 10**9 + 7
    S = input()
    mod13dp = Mod13DPTable(len(S))
    mod13dp.set_start(S[-1])
    multi = 10
    for i, m in enumerate(reversed(list(S[:-1]))):
        i += 1
        if m == '?':
            for j in range(10):
                mod13dp.update(j, i, multi)
        else:
            mod13dp.update(int(m), i, multi)
        multi = multi*10 % 13
    print(mod13dp.get_table(-1)[5])
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def isprime(n):
    for i in xrange(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

limit = 1000000
ansList = [0]*limit # 1 is not prime
cnt = 0
for i in xrange(2, limit):
    if isprime(i): cnt += 1
    ansList[i-1] = cnt

for line in ["999999"]:
#for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    n = List[0]
    print ansList[n-1]

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

limit = 1000000

prime01List = [1]*limit
prime01List[0] = 0 # 1 is not prime
for i in xrange(2, int(limit**0.5)+1):
    n = 2*i
    while(n <= limit):
        prime01List[n-1] = 0
        n += i


ansList = [0]*limit
cnt = 0
for i in xrange(limit):
    cnt += prime01List[i]
    ansList[i] = cnt


#for line in ["999999"]:
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    n = List[0]
    print ansList[n-1]