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

import sys

N, K = map(int, input().split())
X, Y = [], []
for i in range(N):
    xi, yi = map(int, sys.stdin.readline().split())
    X.append(xi)
    Y.append(yi)

ans = float('inf')
for i in range(N):  # 左
    for j in range(N):  # 右
        if X[i] >= X[j]:
            continue
        for k in range(N):  # 下
            for l in range(N):  # 上
                if Y[k] >= Y[l]:
                    continue
                cnt = 0
                for x, y in zip(X, Y):  # 含まれてるかカウント
                    if X[i] <= x <= X[j] and Y[k] <= y <= Y[l]:
                        cnt += 1
                        if cnt == K:
                            ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
                            break

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
XY = []
YX = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y, i])
    YX.append([y, x, i])
XY.sort()
YX.sort()

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

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

import numpy as np

s = input()
t = input()

num_s = len(s)
num_t = len(t)

dp = np.zeros((num_s + 1, num_t +1), dtype='int64')


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

# print(dp)

is_search = True
res=''
pos_s = num_s
pos_t = num_t


while len(res) < np.max(dp):
    temp = dp[pos_s, pos_t]
    # print(temp)
    if dp[pos_s-1, pos_t] == temp:
        pos_s -= 1

    if dp[pos_s, pos_t-1] == temp:
        pos_t -= 1

    if dp[pos_s-1, pos_t-1] != temp:
        res += s[pos_s-1]
        pos_s -= 1
        pos_t -= 1

    # print(res, pos_s-1)
        

print(res[::-1])


### FIXED CODE ###

import numpy as np

def main():
    s = np.array([str(i) for i in input()], dtype=np.unicode)
    t = np.array([str(i) for i in input()], dtype=np.unicode)

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int64')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        if s[pos_s - 1] == t[pos_t - 1]:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
        
    print(res[::-1])

main()
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i] != S[j] and S[i] != 'R' and S[j] != 'R':
          ans += S[j:N].count('R')
          if j+(j-i) < N and S[j+(j-i)] == 'R':
            ans -= 1
        elif S[i] != S[j] and S[i] != 'G' and S[j] != 'G':
          ans += S[j:N].count('G')
          if j+(j-i) < N and S[j+(j-i)] == 'G':
            ans -= 1
        elif S[i] != S[j] and S[i] != 'B' and S[j] != 'B':
          ans += S[j:N].count('B')
          if j+(j-i) < N and S[j+(j-i)] == 'B':
            ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R*G*B
for i in range(N):
    for k in range(i+1,N):
        if (k+i)%2 == 1:
            continue
        else:
            j = (k+i)//2
            if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
X = [list(map(int, input().split()))for _ in range(Q)]
l =[]
for i in range(Q):
    l.append(S[X[i][0]-1:X[i][1]].count("AC"))
[print(i)for i in l]

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
X = [list(map(int, input().split()))for _ in range(Q)]

a =[0]*N
for i in range(1,N):
    if S[i] =="C" and S[i-1] =="A":
        a[i] = a[i-1]+1
    else:
        a[i] = a[i-1]
# print(a)
for i in range(Q):
    print(a[X[i][1]-1]-a[X[i][0]-1])
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(n):
    si=s[i]
    for j in range(i+1,n):
        sj=s[j]
        if si==sj:
            pass
        else:
            for k in range(j+1,n):
                sk=s[k]
                if sk==si or sk==sj:
                    continue
                if j-i==k-j:
                    continue
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
for i in range(n):
    for j in range(n):
        if i+j+j>=n:
            break
        s1=s[i]
        s2=s[i+j]
        s3=s[i+j*2]
        if s1!=s2 and s2!=s3 and s1!=s3:
            ans-=1
print(ans)
### BUGGY CODE ###

#辺の重み(変化量)が0である場合は01DFSって特別なやつ
#0の場合はそこでBFSできる
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        if i>0:
            if dp[i-1][j]!=-1:
                if dp[i-1][j]>dp[i][j]:
                    dp[i-1][j]=dp[i][j]
                    now.appendleft([i-1,j])
        if j>0:
            if dp[i][j-1]!=-1:
                if dp[i][j-1]>dp[i][j]:
                    dp[i][j-1]=dp[i][j]
                    now.appendleft([i,j-1])
        if i<h-1:
            if dp[i+1][j]!=-1:
                if dp[i+1][j]>dp[i][j]:
                    dp[i+1][j]=dp[i][j]
                    now.appendleft([i+1,j])
        if j<w-1:
            if dp[i][j+1]!=-1:
                if dp[i][j+1]>dp[i][j]:
                    dp[i][j+1]=dp[i][j]
                    now.appendleft([i,j+1])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w:
                    if dp[i+k][j+l]!=-1:
                        if dp[i+k][j+l]>dp[i][j]+1:
                            dp[i+k][j+l]=dp[i][j]+1
                            now.appendleft([i+k,j+l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

### FIXED CODE ###

#辺の重み(変化量)が0である場合は01DFSって特別なやつ
#0の場合はそこでBFSできる
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        if i>0:
            if dp[i-1][j]!=-1:
                if dp[i-1][j]>dp[i][j]:
                    dp[i-1][j]=dp[i][j]
                    now.appendleft([i-1,j])
        if j>0:
            if dp[i][j-1]!=-1:
                if dp[i][j-1]>dp[i][j]:
                    dp[i][j-1]=dp[i][j]
                    now.appendleft([i,j-1])
        if i<h-1:
            if dp[i+1][j]!=-1:
                if dp[i+1][j]>dp[i][j]:
                    dp[i+1][j]=dp[i][j]
                    now.appendleft([i+1,j])
        if j<w-1:
            if dp[i][j+1]!=-1:
                if dp[i][j+1]>dp[i][j]:
                    dp[i][j+1]=dp[i][j]
                    now.appendleft([i,j+1])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w:
                    if dp[i+k][j+l]!=-1:
                        if dp[i+k][j+l]>dp[i][j]+1:
                            dp[i+k][j+l]=dp[i][j]+1
                            now.append([i+k,j+l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)
### BUGGY CODE ###

import collections

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

for i in range(len(a)):
    ans = 0
    for item, value in c.items():
        if item == a[i]:
            value -= 1
        ans += value * (value-1) // 2

    print(ans)


### FIXED CODE ###

import collections

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

mx = 0

for item, value in c.items():
    mx += value * (value-1) // 2

for i in range(len(a)):
    ans = mx

    t = c[a[i]]
    ans -= t * (t-1) //2
    ans += (t-1)*(t-2) //2
    print(ans)
### BUGGY CODE ###

n, m =map(int,input().split())
s = list(map(int,input().split()))
a = []*m
b = []*m
ans = 0
for __ in range(m):
  _= list(map(int, input().split()))
  a.append(_)
  if s[_[0]-1] > s[_[1]-1]:
    b.append(_[0])
  elif s[_[0]-1] < s[_[1]-1]:
    b.append(_[1])
  else:
    b.append(0)
for i in range(n):
  count = 0
  for j in range(m):
    if i+1 in a[j]:
      count += 1
  if b.count(i+1) == count:
      ans += 1
print(ans)

### FIXED CODE ###

n, m =map(int,input().split())
s = list(map(int,input().split()))
t = [0]*n #展望台が良いと0
for __ in range(m):
  a, b =map(int,input().split())
  if s[a-1] >= s[b-1]:
    t[b-1] += 1
  if s[a-1] <= s[b-1]:
    t[a-1] += 1
print(t.count(0))
### BUGGY CODE ###

import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

ans_list = [0] * (N+1)

dq = collections.deque()

dq.append(1)

print("Yes")
for hoge in range(500000):
    i = dq.popleft()
    iList = [temp for temp in ABs if i in temp]

    iList = list(itertools.chain.from_iterable(iList))
    iList = [temp for temp in iList if iList !=i]

    for hoge in iList:
        if(ans_list[hoge] == 0):
            ans_list[hoge] = i
        dq.append(hoge)

    if(0 not in ans_list[2:]):
        break

for ans in ans_list[2:]:
    print(ans)    



### FIXED CODE ###

import collections
import itertools
N, M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

loads = [[] for _ in range(N+1)]

for AB in ABs:
    loads[AB[0]].append(AB[1])
    loads[AB[1]].append(AB[0])


dq = collections.deque()

dq.append(1)
ans_list = [0 for _ in range(N+1)]

#print(loads)
print("Yes")
while len(dq) != 0:
    i = dq.popleft()

    for vec in loads[i]:
#        print(vec)
        if(ans_list[vec] == 0):
            ans_list[vec] = i
            dq.append(vec)
#        print(ans_list)
#        print(dq)


for ans in ans_list[2:]:
    print(ans)
### BUGGY CODE ###

n=int(input())

for p in range(1, n+1):
  right=int((p**(1/3)))+2
  cnt=0
  for i in range(1, right):
    for j in range(1, i+1):
      for k in range(1, j+1):
        if (i+j+k)**2-i*j-j*k-k*i==p:
          if i==j and j==k:
            cnt+=1
          elif i==j and j!=k:
            cnt+=3
          elif j==k and k!=i:
            cnt+=3
          elif k==i and i!=j:
            cnt+=3
          elif i!=j and j!=k and k!=i:
            cnt+=6
  print(cnt)

### FIXED CODE ###

n=int(input())
lst=[0]*10000000
for i in range(1, 101):
  for j in range(1, i+1):
    for k in range(1, j+1):
      temp=i**2+j**2+k**2+i*j+j*k+k*i
      if i==j and j==k:
        lst[temp+1]+=1
      elif i==j and j!=k:
         lst[temp+1]+=3
      elif j==k and k!=i:
         lst[temp+1]+=3
      elif k==i and i!=j:
         lst[temp+1]+=3
      elif i!=j and j!=k and k!=i:
         lst[temp+1]+=6
for p in range(1, n+1):
  print(lst[p+1])
### BUGGY CODE ###

K = int(input())

sevens = int('7' * len(str(K)))
flag = False
for i in range(K):
    if sevens % K == 0:
        flag = True
        break
    sevens = sevens * 10 + 7
print(len(str(sevens)) if flag else -1)


### FIXED CODE ###

K = int(input())

#sevens = int('7' * len(str(K)))
sevens_mod = 7 % K
flag = False
ans = -1
for i in range(K):
    if sevens_mod == 0:
        flag = True
        ans = i + 1
        break
    sevens_mod = (sevens_mod * 10 + 7) % K
print(ans if flag else -1)
### BUGGY CODE ###

s=input()
lim=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s))]
if s[0] =="?":
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,len(s)):
    for j in range(13):
        if s[i] ==  "?":
            for k in range(10):
                dp[i][(j*10 + k)%13] += dp[i-1][j]
        else:
            dp[i][(j*10 + int(s[i]))%13] += dp[i-1][j]
print(dp[-1][5]%lim)

### FIXED CODE ###

s=input()
lim=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s))]
if s[0] =="?":
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,len(s)):
    for j in range(13):
        if s[i] ==  "?":
            for k in range(10):
                dp[i][(j*10 + k)%13] = (dp[i][(j*10 + k)%13]+dp[i-1][j])%lim
        else:
            dp[i][(j*10 + int(s[i]))%13] = (dp[i][(j*10 + int(s[i]))%13]+dp[i-1][j])%lim
print(dp[-1][5])
### BUGGY CODE ###

K=int(input())
import math 
c=0
for i in range(1,K+1):
    for j in range (1,K+1):
        for k in range (1,K+1):
            a=math.gcd(i,j)
            b=math.gcd(a,k)
            c=c+b
print(c)

### FIXED CODE ###

K=int(input())
from math import gcd 
c=0
for i in range(1,K+1):
    for j in range (1,K+1):
        for k in range (1,K+1):
            c=c+gcd(gcd(i,j),k)
print(c)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import sys
sys.setrecursionlimit(4100000)

n,m= map(int,readline().split())
a = list(map(int,readline().split()))

if a[0] == 1:
  print(1)
  exit()
  
d = [0]
def dfs(now,cc,d):
    if cc == m:
      return now
    else:
      next = a[now]
      next -= 1
      if not next in d:
        d.append(next)
        return dfs(next,cc+1,d)
      else:
        for i,di in enumerate(d[::-1]):
          if di == next:
            return (i+1,cc,now)

def f(now,cc):
    global mar
    if cc == mar:
      return now
    else:
      next = a[now]
      next -= 1
      return f(next,cc+1)
    
res = dfs(0,0,d)
if type(res) == int:
  print(res+1)
else:
  m -= res[1]
  mar = m % res[0]
  print(f(res[2],0)+1)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import sys
sys.setrecursionlimit(4100000)

n,m= map(int,readline().split())
a = list(map(int,readline().split()))

if a[0] == 1:
  print(1)
  exit()
  
d = set([0])
def dfs(now,cc,d):
    if cc == m:
      return now
    else:
      next = a[now]
      next -= 1
      if not next in d:
        d.add(next)
        return dfs(next,cc+1,d)
      else:
        d = list(d)
        for i,di in enumerate(d[::-1]):
          if di == next:
            return (i+1,cc,now)

def f(now,cc):
    global mar
    if cc == mar:
      return now
    else:
      next = a[now]
      next -= 1
      return f(next,cc+1)
    
res = dfs(0,0,d)
if type(res) == int:
  print(res+1)
else:
  m -= res[1]
  mar = m % res[0]
  print(f(res[2],0)+1)
### BUGGY CODE ###

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

# n??????????´??????????????????????q???????????¢??¢?´¢????????£??????O(qn)?????¢?????´???????????§?§£????????¨?????§??????


def linear_search(S, T):
    count = 0
    for i in xrange(len(T)):
        if T[i] in S:
            count += 1
    return count

if __name__ == '__main__':
    n = input()
    S = map(int, raw_input().split())
    q = input()
    T = map(int, raw_input().split())

    print linear_search(S, T)

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ????????¢?´¢ '''

# n??????????´??????????????????????q????????¢?´¢????????£?????´???
# ?¨??????????O(qlogn)


def binary_search(key, A):
    imin, imax = 0, len(S)

    while imin < imax:
        mid = int((imin + imax) / 2)
        if A[mid] == key:
            return True
        elif key < A[mid]:
            imax = mid
        else:
            imin = mid + 1
    return False


if __name__ == '__main__':
    NS = int(input())
    S = list(map(int, input().split()))
    NT = int(input())
    T = list(map(int, input().split()))

    count = 0

    for t in T:
        if binary_search(t, S):
            count += 1
    print(count)
### BUGGY CODE ###

import math

MAX=10**6+3
table = list(range(MAX))
i=2
n=MAX
while i<=n:
    table[i] = 2
    i+=2

p=3
while p*p<=n:
    if table[p]<p:
        continue
    x=p
    while x<=n:
        table[x]=p
        x+=p

def primeFactorSet(n):
    result = set()
    while table[n]!=1:
        result.add(table[n])
        n //= table[n]
    return result
    

n = int(input())
A = list(map(int,input().split()))
pairwise = True
flags = [False for _ in range(MAX)]

for i in range(n):
    a=A[i]
    if pairwise:
        t = primeFactorSet(a)
        for p in t:
            if flags[p]:
                pairwise = False
                break
            flags[p]=True
    if i==0:
        g=a
    else:
        g=math.gcd(g,a)
    
if g>1:
    print("not coprime")
elif pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")


### FIXED CODE ###

import math

MAX=10**6+3
table = list(range(MAX))
i=2
n=MAX
while i<n:
    table[i] = 2
    i+=2
p=3
while p*p<=n:
    if table[p]<p:
        p+=2
        continue
    x=p
    while x<=n:
        table[x]=p
        x+=p
    p+=2


def primeFactorSet(n):
    result = set()
    while table[n]!=1:
        result.add(table[n])
        n //= table[n]
    return result
    

n = int(input())
A = list(map(int,input().split()))
pairwise = True
flags = [False for _ in range(MAX)]

for i in range(n):
    a=A[i]
    if pairwise:
        t = primeFactorSet(a)
        for p in t:
            if flags[p]:
                pairwise = False
                break
            flags[p]=True
    if i==0:
        g=a
    else:
        g=math.gcd(g,a)
    
if g>1:
    print("not coprime")
elif pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n,m = LI()
    a = LIR(m)
    for i in range(n):
        a.sort(key = lambda x:x[1])
        mi = a[0][1]
        l = 0
        r = len(a)
        a.sort(key = lambda x:x[0])
        while r-l>1:
            j = (l+r)//2
            if a[j][0] < mi:
                l = j
            else:
                r = j
        a = a[l+1:]
        if len(a) == 0:
            print(i+1)
            quit()
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n,m = LI()
    a = LIR(m)
    a.sort(key = lambda x:x[1])
    x = 0
    ans = 0
    for i in range(m):
        if a[i][0] >= x:
            x = a[i][1]
            ans += 1
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

S = input()[::-1]

a = [0] * 13
n = [0] * 13

from functools import lru_cache

@lru_cache(maxsize=10000000)
def get_base(d):
    if d==0:
        return 1
    base = get_base(d-1)
    base *= 10
    base %= 13
    return base

@lru_cache(maxsize=1000)
def get_shift(d, num):
    shift = num
    shift *= get_base(d)
    shift %= 13
    return shift

def calc(d, num):
#    shift = (num * (10 ** d))%13
    shift = get_shift(d, num)
    if d==0:
        n[shift] = 1
    else:
        for i in range(13):
            n[(i+shift)%13] += a[i]
    

for d, s in enumerate(S):
    if s=='?':
        for i in range(10):
            calc(d, i)
    else:
        calc(d, int(s[0]))
    a, n = n, a
    for i in range(13):
        a[i] %= 1000000007
        n[i] = 0

print(a[5])





### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    S = input()
    d = 1
    dp = [0] * 13
    dp[0] = 1
    dp_n = [None] * 13
    for s in reversed(S):
        for i in range(13):
            dp[i] %= N1097
            dp_n[i] = 0
        if s == '?':
            for s in range(10):
                diff = (s*d) % 13
                for i in range(13):
                    dp_n[(i+diff)%13] += dp[i]
        else:
            s = int(s)
            diff = (s*d) % 13
            for i in range(13):
                dp_n[(i+diff)%13] += dp[i]
        dp_n, dp = dp, dp_n
        d = (10 * d) % 13
    print(dp[5] % N1097)

main()
### BUGGY CODE ###

n = int(input())
l = list(map(float,input().split()))
dp = [[0 for _ in range(n+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0]*(1-l[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j]*(1-l[i-1]) + dp[i-1][j-1]*l[i-1]
ans = 0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(float,input().split()))
dp = [[0 for _ in range(n+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0]*(1-l[i-1])
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j] = dp[i-1][j]*(1-l[i-1]) + dp[i-1][j-1]*l[i-1]
ans = 0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)