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

import sys
from collections import defaultdict
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=10**9+7
    n=II()
    aa=LI()
    cs=[0]
    for a in aa:cs.append(cs[-1]^a)
    #print(cs)
    cnt=np.zeros((2,max(cs)+1),dtype="i8")
    cnt[0]=1
    for s in cs[1:]:
        if s==0:
            cnt[0]+=cnt[1]
        else:
            cnt[1][s]+=cnt[0][s]
    #print(cnt)
    if cs[-1]==0:print(np.sum(cnt[1])+pow(2,cs.count(0)-2,md))
    else:print(cnt[0][cs[-1]])

main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=10**9+7
    n=II()
    aa=LI()
    cs=[0]
    for a in aa:cs.append(cs[-1]^a)
    #print(cs)

    cnt={}
    cnt0=[1]*len(cs)
    for i,s in enumerate(cs[1:],1):
        if s==0:
            cnt0[i]=cnt0[i-1]+1
        elif s in cnt:
            cnt0[i]=cnt0[i-1]
            c0=cnt0[i]-cnt0[cnt[s][2]]
            cnt[s][0]=(cnt[s][0]+cnt[s][1]*c0)%md
            cnt[s][1]=(cnt[s][1]+cnt[s][0])%md
            cnt[s][2]=i
        else:
            cnt0[i]=cnt0[i-1]
            cnt[s]=[1,1,i]
    #print(cnt)
    #print(cnt0)

    if cs[-1]==0:ans=sum(v[1] for v in cnt.values())+pow(2,cnt0[-1]-2,md)
    else:ans=cnt[cs[-1]][0]
    print(ans%md)

main()
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

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

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

d = ((1, 0), (0, 1), (0, -1), (-1, 0))


# def bfs(y, x, cnt):

# if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
#    return
#print(y, x, cnt)


while (queue):
    y, x, cnt = queue.popleft()
    # print(l)
    ans = max(ans, cnt)
    for ddx, ddy in d:
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))
    # print(queue)
print(ans)

### 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 ###

#d,t,s=map(int,input().split())
n=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(n):
  for j in range(i+1,n):
    ans+=(A[i]%(10**9+7))*(A[j]%(10**9+7))
print(ans%(10**9+7))

### FIXED CODE ###

import itertools
#h,w=map(int,input().split())
#S=[list(map(int,input().split())) for _ in range(h)]
n=int(input())
A=list(map(int,input().split()))
Ar=list(itertools.accumulate(A))
ans=0
for i in range(n-1):
    ans+=A[i]*(Ar[n-1]-Ar[i])
    ans%=10**9+7
print(ans)
### BUGGY CODE ###

L,R = [int(x) for x in input().split()]
 
#L = input_arr[0]
#R = input_arr[1]
 
min_ans = 10**18
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = (i*j)%2019
        
        if ans < min_ans:
            min_ans = ans
        if min_ans == 0:
            break
print(min_ans)


### FIXED CODE ###

L,R = [int(x) for x in input().split()]
 
min_ans = 10**18

if R-L>=2019:
  min_ans=0
else:
  for i in range(L,R):
      for j in range(i+1,R+1):
          ans = (i*j)%2019

          if ans < min_ans:
              min_ans = ans
          if min_ans == 0:
              break
print(min_ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
slist = tuple(input() for i in range(n))
sset = set(slist)
slist2 = list(sset)
slist2.sort()
count_list = []
c = 0
for i in slist2:
  count_list.append(slist.count(i))
  if slist.count(i) > c:
    c = slist.count(i)
for i in range(len(count_list)):
  if c == count_list[i]:
    print(slist2[i])
  

### FIXED CODE ###

n = int(input())
cnt = {}
mx = 0
for i in range(n):
  s = input()
  if s not in cnt:
    cnt[s] = 0
  cnt[s] += 1
  mx = max(mx,cnt[s])
ans = []
for s in cnt:
  if cnt[s] == mx:
    ans.append(s)
ans.sort()
for i in ans:
  print(i)
### BUGGY CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
### BUGGY CODE ###

def solve(p, t):
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return False
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    return True
  else:
    return solve(p + 1, t - A[p])

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

for t in M:
  if solve(0, t): print("yes")
  else: print("no")

### FIXED CODE ###

memo = {}
def solve(p, t):
  key = "{}:{}".format(p, t)
  if key in memo: return memo[key]
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return False
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    memo["{}:{}".format(p + 1, t)] = True
    return True
  else:
    memo["{}:{}".format(p + 1, t)] = False
    return solve(p + 1, t - A[p])

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

for t in M:
  if solve(0, t): print("yes")
  else: print("no")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 + 1
    dp = [0] + [INF] * MAX_LEN
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h+1):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    ans = min(dp[h:])
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int, input().split())

uf = UnionFind(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)

ans = 0
for k, v in uf.all_group_members().items():
    ans = max(ans, uf.size(k))

print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


n, m = map(int, input().split())
uf = UnionFind(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a,b)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))

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

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

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

A.sort(key=lambda x:x[0])

money = 0
cnt = 0
for i in range(N):
    for j in range(A[i][1]):
        money += A[i][0]
        cnt += 1
        if cnt == M:
            print(money)
            break

### FIXED CODE ###

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

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

A.sort(key=lambda x:x[0])

money = 0
cnt = 0
for i in range(N):
    if cnt + A[i][1] < M: 
        money += A[i][0]*A[i][1]
        cnt += A[i][1]
    else: 
        money += A[i][0]*(M-cnt)
        print(money)
        break
### BUGGY CODE ###

#B
N=int(input())
ans=1
for x in input().split():
    ans*=int(x)

if ans>10**18:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

#B
N=int(input())
ans=1
flag=True
A=[]
for x in input().split():
    A.append(int(x))
    if int(x)==0:
        ans=0

for i in range(N):
    x=A[i]
    ans*=x
    if ans>pow(10,18):
        flag=False
        break

if flag:
    print(ans)
else:
    print("-1")
### BUGGY CODE ###

n, m, d = map(int, input().split())
K = n**m
if d == 0:
    print((m - 1) / n)
else:
    print(2 * (n - d) * (m - 1) / n**2)

### FIXED CODE ###

n, m, d = map(int, input().split())

if d == 0:
    print((m - 1) / n)
else:
    print(2 * (n - d) / n  * (m - 1) / n)
### BUGGY CODE ###

N = input()
num = len(N)
mod_sum = [0 for i in range(2019)]
ans = 0
for i in range(num):
  a = int(N[i:])
  mod = a%2019
  mod_sum[mod] += 1
  if mod == 0:
    ans += 1
for i in mod_sum:
  ans += i*(i-1)/2
print(int(ans))

### FIXED CODE ###

N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
d = 1
for i in range(num):
  a = (a + int(N[-i-1])*d)%2019
  d = (d*10)%2019
  mod_sum[a] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
tTotal = sum(t)*2
speed = [min(i/2,(tTotal-i)/2) for i in range(tTotal+1)]
#?

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)

### FIXED CODE ###

n = int(input())
t = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
tTotal = sum(t)*2
speed = [min(i/2,(tTotal-i)/2) for i in range(tTotal+1)]
#?

start=0
end=0
#iter through segments
for i in range(n):
    end += t[i]*2
    for j in range(tTotal+1):
        speed[j] = min(speed[j], v[i] + max(0, -(j-start)/2, (j-end)/2))
    start = end

print(sum(speed)/2)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import dijkstra as shortest_path
n = int(input())
Sides = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    Sides[u][v] = w
    Sides[v][u] = w

Path_from_0 = shortest_path(np.array(Sides), indices=0)
for i in range(n):
    print(int(Path_from_0[i]) % 2)


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path
import heapq
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edge[u].append([w, v])
    edge[v].append([w, u])

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

Path_from_0 = dijkstra_heap(0)
for i in range(n):
    print(Path_from_0[i] % 2)
### BUGGY CODE ###

#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#import fractions
#import math
#lis=list(input().split())
#lis=list(map(float,input().split()))
#n=int(input())
#S=input()
import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))%((10**9)+7)
    ans=(ans*tmp)%((10**9)+7)
print(ans)


### FIXED CODE ###

lis=list(map(int,input().split()))
alist=[0]*(lis[0]+1)
for i in range(lis[1]):
    a=int(input())
    alist[a]=1
steps=[0]*(lis[0]+2)
steps[1]=1
mod=(10**9)+7
for i in range(2,lis[0]+2):
    if alist[i-1]==0:
        steps[i]=(steps[i-1]+steps[i-2])%mod
ans=steps[-1]
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n = get_int()
    a = get_li()
    ans = 1
    for i in range(len(a)):
        ans = max(ans, reduce(gcd, a[:i] + a[i+1:]))
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N = 0
A = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    forward = [A[0]]
    for a in A[1:]:
        forward.append(gcd(forward[-1], a))
    backward = [A[-1]]
    for a in reversed(A[:-1]):
        backward.append(gcd(backward[-1], a))
    backward.reverse()
    ans = max(forward[-2], backward[1])
    for i in range(1, len(A)-1):
        ans = max(ans, gcd(forward[i-1], backward[i+1]))
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


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

import math

input = str(input()).split(" ")
for index in range(len(input)):
    input[index] = int(input[index])
x = input[0]
y = input[1]


def test(x, y):
    for index in range(1, abs(y) + 1):
        if (x * index % y != 0 and abs(x * index) <= 10**(18)):
            return x * index
    return -1
print(test(x,y))

### FIXED CODE ###

b=[]
b = input().strip().split()
b[0]=int(b[0])
b[1]=int(b[1])
if b[0]%b[1]==0:
	print("-1")
else:
	print(b[0])
### BUGGY CODE ###

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

N,M,P = map(int,input().split())
edge = []
for i in range(M):
    A,B,C = map(int,input().split())
    edge.append([A-1,B-1,P-C])

def Bellman_Ford(edges, start, N):
    inf = float("inf")
    # dist[i]: 頂点iまでの最短距離
    dist = [inf for i in range(N)]
    dist[start] = 0

    for i in range(N+N):
        for a,b,c in edges:
            if a != inf and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                # startからgoalまでに負閉路がある場合
                if i >= N:
                    dist[b] = -inf
        # 一回目のベルマンフォード法の結果
        if i == N-1:
            first_time = dist[-1]
    # (一回目,二回目)
    return first_time, dist[-1]

first,second = Bellman_Ford(edge, 0, N)
if first != second:
    answer = -1
else:
    answer = max(0,-second)

print(answer)

### FIXED CODE ###

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

N,M,P = map(int,input().split())
edge = []
for i in range(M):
    A,B,C = map(int,input().split())
    edge.append([A-1,B-1,P-C])

def Bellman_Ford(edges, start, N):
    inf = float("inf")
    # dist[i]: 頂点iまでの最短距離
    dist = [inf for i in range(N)]
    dist[start] = 0

    for i in range(N+N):
        for a,b,c in edges:
            if a != inf and dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                # startからgoalまでに負閉路がある場合
                if i >= N:
                    dist[b] = -inf
        # 一回目のベルマンフォード法の結果
        if i == N-1:
            first_time = dist[-1]
    # (一回目,二回目)
    return first_time, dist[-1]

first,second = Bellman_Ford(edge, 0, N)
if first != second:
    answer = -1
else:
    answer = max(0,-second)

print(answer)
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))

ans = 0
for bit in range(1 << n):
    tmp = 0
    for i in range(n):
        if bit >> i & 1:
            tmp += v[i] - c[i]
    ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))

ans = 0
for i in range(n):
    ans += max(0, v[i] - c[i])
print(ans)
### BUGGY CODE ###

s = input()[::-1]
MOD = 10**9 + 7
n = len(s)

data = [0 for i in range(n+2)] #10**iを13で割ったあまり
data[0] = 1
for i in range(1,n+2):
    data[i] = (data[i-1]*10)%13


dp = [[0 for i in range(13)] for j in range(10**5+100)]

if s[0] ==  '?':
    for i in range(10):
        dp[0][i] = 1
else:
    i = int(s[0])
    dp[0][i] = 1


for i in range(1,n):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i][(k*data[i] + j)%13] += dp[i-1][j]
        else:
            num = int(s[i])
            dp[i][(num*data[i]+j)%13] += dp[i-1][j]
    for j in range(13):
        dp[i][j] %=MOD

print(dp[n-1][5])


### FIXED CODE ###

s = input()[::-1]
MOD = 10**9 + 7
n = len(s)

data = [0 for i in range(n+2)] #10**iを13で割ったあまり
data[0] = 1
for i in range(1,n+2):
    data[i] = (data[i-1]*10)%13


dp = [[0 for i in range(13)] for j in range(10**5+100)]

if s[0] ==  '?':
    for i in range(10):
        dp[0][i] = 1
else:
    i = int(s[0])
    dp[0][i] = 1


for i in range(1,n):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i][(k*data[i] + j)%13] += dp[i-1][j]
        else:
            num = int(s[i])
            dp[i][(num*data[i]+j)%13] += dp[i-1][j]
    for j in range(13):
        dp[i][j] %=MOD

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

MAX = 999999

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

def prime_list(n):
  result = 0
  if n >= 2:result+=1
  for i in range(3,n+1,2):
    if is_prime(i):result+=1
  return result

while 1:
  print(prime_list(int(input())))

### FIXED CODE ###

import sys
import time

MAX = 999999

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

def prime_list(n):
  return ([2] if n > 1 else []) + [i for i in range(3,n+1,2) if is_prime(i)]

L = prime_list(int(MAX**0.5))

def is_prime_2(n):
  a = int(n ** 0.5)
  for i in L:
    if i > a:return True
    if n % i == 0:return False
  return True

def prime_count(n):
  result = 0
  if n >= 2:result+=1
  for i in range(3,n+1,2):
    if is_prime_2(i):result+=1
  return result

def prime_list2(n):
  return ([2] if n > 1 else []) + [i for i in range(3,n+1,2) if is_prime_2(i)]

L2 = prime_list2(MAX)

def prime_count_2(n):
  for i,v in enumerate(L2):
    if v > n:return i
  return len(L2)

for n in sys.stdin:
  print(prime_count_2(int(n)))