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

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

for i in range(n):
    ans = [0 for i in range(n+1)]
    for j in range(0,n+1):
        if j == 0:
            ans[0] = dp[0]*(1-a[i])
        elif j == n:
            ans[-1] = dp[-2]*a[i]
        else:
            ans[j] = dp[j-1]*a[i] + dp[j]*(1-a[i])
    dp = copy.deepcopy(ans)
    

print(sum(dp[(n+1)//2:]))





### FIXED CODE ###

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

for i in range(n):
    for j in range(0,n+1):
        if j == 0:
            dp[i+1][0] = dp[i][0]*(1-a[i])
        elif j == n:
            dp[i+1][-1] = dp[i][-2]*a[i]
        else:
            dp[i+1][j] = dp[i][j-1]*a[i] + dp[i][j]*(1-a[i])
    

print(sum(dp[-1][(n+1)//2:]))
### BUGGY CODE ###

import math
from itertools import product

N = int(input())

for n in range(1, N + 1):
    count = 0
    for x, y, z in product(range(1, int(math.sqrt(N)) + 1), repeat=3):
        if x * x + y * y + z * z + x * y + y * z + z * x == n:
            count += 1
    print(count)


### FIXED CODE ###

import math

N = int(input())

for n in range(1, N + 1):
    count = 0
    ub = int(math.sqrt(n))
    for x in range(1, ub + 1):
        for y in range(x, ub + 1):
            r = 4 * n - 3 * x * x - 2 * x * y - 3 * y * y
            if r < 0:
                break
            z = (math.sqrt(r) - x - y) / 2
            if z - int(z) < 1e-9:
                z = int(z)
            elif z - int(z + 1) < 1e-9:
                z = int(z + 1)
            else:
                break

            if y > z or z > ub:
                break
            if abs(x * x + y * y + z * z + x * y + y * z + z * x - n) < 1e-9:
                #print(x, y, round(z), z)
                s = len(set([x, y, round(z)]))
                if s == 1:
                    count += 1
                elif s == 2:
                    count += 3
                else:
                    count += 6

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

N=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)
t=0
for i in range(N-2):
    for j in range(i+1,N-1):
        if L[i]<L[j]+L[N-1]:
            t+=N-1-j
        elif L[i]>=L[j]+L[j+1]:
            t+=0
        else:
            l=j+1
            h=N-1
            c=int((l+h)/2)
            while L[i]>L[j]+L[c] or L[i]<L[j]+L[c+1]:
                if L[i]>=L[j]+L[c]:
                    h=c
                    c=int((c+l)/2)
                elif L[i]<=L[j]+L[c+1]:
                    l=c
                    c=int((h+c)/2)
                print(c)
            t+=N-1-c

print(t)


### FIXED CODE ###

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        l=L[i]+L[j]
        c=bisect_left(L,l)
        ans+=max(0,c-j-1)
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    P = tuple(map(int,input().split()))
    a = 0
    for i in range(N):
        hantei = 0
        for j in range(i):
            if P[i] > P[j]:
                hantei = 1
                break
        if hantei == 0:
            a += 1
    print(a)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    P = tuple(map(int,input().split()))
    a = 1
    minP = P[0]
    for i in range(1, N):
        if minP < P[i]:
            pass
        else:
            minP = P[i]
            a += 1
    print(a)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
mod=10**9+7
b=1
for i in a:
    b*=i//gcd(b,i)
print(sum(b//i%mod for i in a)%mod) 


### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

N = int(input())
List = list(map(int,input().split()))
ans = 1
for item in List:
  ans *= item
if ans > 10 **18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
List = list(map(int,input().split()))
ans = 1
for item in List:
  ans *= item
  if ans > 10 **18 or ans <= -1:
    ans = -1
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = [[] for _ in range(N+1)]
cnt = [0 for _ in range(N+1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

dfs(1, -1)

print(*cnt[1:])

### FIXED CODE ###

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


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = {i:[] for i in range(N+1)}
cnt = {i:0 for i in range(N+1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

dfs(1, -1)

print(*list(cnt.values())[1:])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    h,w = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    for j in range(w-1):
        w = [[0 for _ in range(h+1)] for _ in range(h+1)]
        for x in range(h+1):
            for z in range(h-x):
                if c[x+z][j] == c[z][j+1]:
                    w[0][x] += 1
        for x in range(1,h+1):
            for z in range(h-x):
                if c[z][j] == c[x+z][j+1]:
                    w[x][0] += 1
        for x in range(1,h+1):
            for y in range(1,h+1):
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
        dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
        dp[0][0] = 0
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [-1] * m
c = [-1] * m
a.sort()
for j in range(m):
    b[j], c[j] = map(int, input().split())
    index = n
    for i in range(n):
        if c[j] < a[i]:
            index = i
            break
    for i in range(b[j]):
        a.insert(index, c[j])
    for i in range(b[j]):
        del a[0]

print(sum(a))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [tuple(map(int, input().split())) for _ in range(m)]
bc.sort(key=lambda t: t[1], reverse=True)

index = 0
count = [0] * m
for i in range(n):
    if index >= m or a[i] >= bc[index][1]:
        break
    a[i] = bc[index][1]
    count[index] += 1
    if count[index] >= bc[index][0]:
        index += 1

print(sum(a))
### BUGGY CODE ###

K, N = tuple(int(v) for v in input().split())

A_list = tuple(int(a) for a in input().split())

# 各点の距離
x_iter = iter(A_list)
y_iter = iter(A_list)
next(y_iter)

d_list = [y - x for x, y in zip(x_iter, y_iter)]
d_list.append(K - A_list[-1] + A_list[0])
d_list += d_list

l = len(d_list) // 2
sum_d = [sum(d_list[i:i+l-1]) for i in range(l)]

print(min(sum_d))


### FIXED CODE ###

K, N = tuple(int(v) for v in input().split())

A_list = list(int(a) for a in input().split())

# # 各点の距離
# x_iter = iter(A_list)
# y_iter = iter(A_list)
# next(y_iter)
# 
# d_list = [y - x for x, y in zip(x_iter, y_iter)]
# d_list.append(K - A_list[-1] + A_list[0])
# d_list += d_list
# 
# l = len(d_list) // 2
# # sum_d = [sum(d_list[i:i+l-1]) for i in range(l)]
# min_d = min(sum(d_list[i:i+l-1]) for i in range(l))
# 
# print(min_d)

A_list += [a + K for a in A_list[:-1]]
print(min(A_list[i+N-1] - A_list[i] for i in range(N)))
### BUGGY CODE ###

X = int(input())
 
ans = None
 
while ans is None:
  for i in range(119):
    for j in range(119):
      if i ** 5 - j ** 5 == X:
        ans = (i, j)
      elif (i*-1) ** 5 - j ** 5 == X:
        ans = (-i, j)
      elif i ** 5 - (j*-1) ** 5 == X:
        ans = (i, -j)
print(ans[0],ans[1])

### FIXED CODE ###

X = int(input())
 
ans = None
 
for i in range(120):
  for j in range(120):
    if i ** 5 - j ** 5 == X:
      ans = (i, j)
    elif (i*-1) ** 5 - j ** 5 == X:
      ans = (-i, j)
    elif i ** 5 - (j*-1) ** 5 == X:
      ans = (i, -j)
print(ans[0],ans[1])
### BUGGY CODE ###

INF = 10 ** 9
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [INF] * N
dp[0] = 0
for i in range(1, N):
    for j in range(K):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i - 1] + abs(h[i - 1] - h[i + j]))

print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
hList = list(map(int, input().split()))
ans = 0
dp = [0] * N
dp[0] = 0

for i in range(1, N):
    minT = 1000000000
    for j in range(i - 1, i - K - 1, -1):
        tmp = dp[j] + abs(hList[j] - hList[i])
        minT = min(minT, tmp)
        if j == 0:
            break
    dp[i] = minT

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

n = int(input())
s = str(input())
left = s[0]
ans = 10**6
for i in range(1,n):
    right = s[i:]
    count_w = 0
    for j in range(i-1):
        if s[j]=='W':
            count_w += 1
    count_e = 0
    for j in range(len(right)):
        if right[j]=='E':
            count_e += 1
    #print(i,count_w,count_e)
    ans = min(ans,count_w+count_e)

print(ans)

### FIXED CODE ###

n = int(input())
s = str(input())
left = s[0]
ans = 10**6
left = {}
left.setdefault('W',0)
left.setdefault('E',0)
right = {}
right.setdefault('E',0)
right.setdefault('W',0)
for i in range(n):
    right[s[i]] += 1
ans = 10**6
for i in range(n):
    right[s[i]] -= 1
    ans = min(ans,left['W']+right['E'])
    #print(left,right)
    left[s[i]] += 1
print(ans)
### BUGGY CODE ###

#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]//700))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
### BUGGY CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    p1 = []
    p0 = []
    for i, ss in enumerate(s):
        p1.append(a[i]) if ss == "1" else p0.append(a[i])
    p11 = set()
    p00 = set()
    
    def make_set(data, ans):
        res = 0
        for i in range(1 << len(data)):
            for j in range(len(data)):
                if (i >> j) & 1 == 1:
                    res ^= data[j]
                ans.add(res)

    make_set(p1, p11)
    make_set(p0, p00)
    print(0 if p00 == p11 else 1)


### FIXED CODE ###

# ref https://black-thunder.hatenablog.com/entry/20200610/1591774050

def solve():
    base = []
    for a, s in zip(A[::-1], map(int, S[::-1])):
        x = a
        for b in base:
            x = min(x, x ^ b)
        if x:
            if s ^ 1:
                base.append(x)
            else:
                return 1
    return 0


t = int(input())
for _ in range(t):
    n = int(input())
    A = list(map(int, input().split()))
    S = input()
    print(solve())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = [-1] + [0]*N
    pvs = set()
    while stack:
        v, dpd = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append((u, dpd))

    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [(i+1, 0)] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
vs = set()
def dfs_w(d, stack):
    depth = defaultdict(int)
    pvs = set()
    while stack:
        v = stack.pop()
        vs.add(v)
        pvs.add(v)
        for u, dpd in d[v]:
            if u in pvs:
                if depth[u] != depth[v] + dpd:
                    return False
            if u in vs:
                continue
            depth[u] = depth[v] + dpd
            stack.append(u)
    return True

if __name__ == '__main__':
    from collections import defaultdict
    N, M = map(int, input().split())
    G = defaultdict(set)
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a].add((b,c))
        G[b].add((a,-c))
    for i in range(N):
        if i+1 in vs:
            continue
        stack = [i+1] 
        r =  dfs_w(G, stack)
        if not r:
            break
    if r:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def csum(c):
  r = 0
  for index, item in enumerate(c):
    r += index * item
  return r

n = int(input())
l= list(map(int,input().split()))
c = [0] * 100001
for i in l:
  c[i] += 1
n = int(input())
for i in range(0, n):
  be,af = map(int,input().split())
  c[af] += c[be]
  c[be] = 0
  print(csum(c))

### FIXED CODE ###

N = int(input())
A= list(map(int,input().split()))
Q = int(input())
heavy = [0] * (10 ** 5 + 1)
for i in A:
  heavy[i] += 1
s = sum(A)
for i in range(Q):
  be,af = map(int,input().split())
  s -= be * heavy[be]
  s += af * heavy[be]
  heavy[af] += heavy[be]
  heavy[be] = 0
  print(s)
### BUGGY CODE ###

import collections

N, K = map(int,input().split())
A = list(map(int,input().split()))

cA = collections.Counter(A)

ans = 0
if len(cA) > K:
  for x in range(len(cA)-K):
    ans += list(reversed(cA.most_common()))[x][1]
else:
  ans = 0
print(ans)

### FIXED CODE ###

import collections

N, K = map(int,input().split())
A = list(map(int,input().split()))

cA = collections.Counter(A)

ans = 0
if len(cA) > K:
  _, counts = zip(*cA.most_common()[::-1])
  ans =sum(counts[:len(cA)-K])
else:
  ans = 0
print(ans)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b=[]
for j in range(len(a)):
  b.append(a.count(a[j]))
c=int(b.count(max(b))/max(b))
d=[]
for k in range(c):
  d.append(a[b.index(max(b))])
  a.remove(d[k])
for l in range(len(d)):
  print(min(d))
  d.remove(min(d))

### FIXED CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b={}
for j in range(len(a)):
  if a[j] in b:
    b[a[j]]+=1
  else:
    b[a[j]]=1
max_b=max(b.values())
c=[]
for k,l in b.items():
  if l==max_b:
    c.append(k)
c.sort()
for m in c:
  print(m)
### BUGGY CODE ###

def main():
    from copy import copy
    s = input()
    mod = 10 ** 9 + 7
    table1 = {i: 0 for i in range(13)}
    table2 = {i: 0 for i in range(13)}
    table3 = {i: 0 for i in range(13)}
    table1[0] = 1
    pre = {i: {j: ((10 * i + j) % 13) for j in range(10)} for i in range(13)}

    for l in s:
        if l == '?':
            for i in range(13):
                q = table1[i]
                for k in pre[i].values():
                    table2[k] += q
        else:
            for i in range(13):
                q = table1[i]
                k = pre[i][int(l)]
                table2[k] += q

        table1 = table2
        table2 = table3.copy()

    print(table1[5] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[((10 * i + j) % 13) for j in range(10)] for i in range(13)]

    for l in s:
        for i in range(13):
            q = table1[i] % mod
            if q == 0:
                continue
            if l == '?':
                for k in pre[i]:
                    table2[k] += q
            else:
                k = (10 * i + int(l)) % 13
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


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

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
dp = [0 for i in range(n+1)]


for i in range(1,n+1):
        if i in a:
                dp[i] = 0
                continue
        if i == 1:
                dp[i] = 1
                continue
        if i == 2:
                if dp[i-1] == 0:
                        dp[i] = 1
                else:
                        dp[i] = 2
                continue
        if dp[i-1] == 0:
                dp[i] = dp[i-2]
                continue
        if dp[i-2] == 0:
                dp[i] = dp[i-1]
                continue
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
        #print (dp[i])
print (dp[-1]%(10**9+7))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
dp = [10**5 for i in range(n+1)]
for i in a:
        dp[i] = 0

a.sort()
for i in range(1,n+1):
        if dp[i] == 0:
                continue
        if i == 1:
                dp[i] = 1
                continue
        if i == 2:
                if dp[i-1] == 0:
                        dp[i] = 1
                else:
                        dp[i] = 2
                continue
        if dp[i-1] == 0:
                dp[i] = dp[i-2]
                continue
        if dp[i-2] == 0:
                dp[i] = dp[i-1]
                continue
        dp[i] = (dp[i-1]+dp[i-2])%(10**9+7)
        #print (dp[i])
print (dp[-1]%(10**9+7))