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

import copy
n = int(input())
A = list(map(int,input().split()))
while True:
    if A.count(0) == n - 1:
        print(max(A))
        exit()
    else:
        B = [ _  for _ in A if _ != 0  ]
        attack = min(B)
        sn = A.index(attack)
        
        for i in range(n):
            if A[i] == 0:
                pass
            else:
                if i != sn:
                    A[i] = A[i] - attack
                else:
                    pass


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
while True:
    if A.count(0) == n - 1:
        print(max(A))
        exit()
    else:
        B = [ _  for _ in A if _ != 0  ]
        attack = min(B)
        sn = A.index(attack)
        
        for i in range(n):
            if A[i] == 0:
                pass
            else:
                if i != sn:
                    A[i] = A[i] % attack
                else:
                    pass
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A = A + A
# all_neg = sum(A)

res = ""
for i in range(N):
    res_tmp = 0
    for j, a in enumerate(A[i:i+N]):
        res_tmp += a if j % 2 == 0 else -a
    # res.append(res_tmp)
    res += (str(res_tmp) + " ")
    # print(res_tmp, end=" ")
print(res[:-1])


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
res = ""
res_tmp = 0
for j, a in enumerate(A):
    res_tmp += a if j % 2 == 0 else -a
res += (str(res_tmp) + " ")

for i, a in enumerate(A[:-1]):
    res_tmp = -res_tmp + a*2
    res += (str(res_tmp) + " ")
print(res[:-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = set()

    for i in range(n):

        a = {int(input())}
        s = s ^ a

    print(len(s))


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

def main():
    n = int(input())
    s = []

    for i in range(n):
        a = int(input())
        i = bisect.bisect_left(s, a)
        if len(s) > i and s[i] == a:
            s.remove(a)
        else:
            s.insert(i, a)


    print(len(s))


main()
### BUGGY CODE ###

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
def lcma(a,b):
  return a*b//gcd(a,b)
n=int(input())
import fractions
a = list(map(int, input().split()))
lcm = a[0]
for i in a[1:]:
  lcm=lcma(lcm,i)
for i,s in enumerate(a):
  a[i]=lcm//s
ans=sum(a)%(10**9+7)
print(ans)

### FIXED CODE ###

n=int(input())
import fractions
a = list(map(int, input().split()))
lcm = a[0]
for i in a:
  lcm = lcm * i // fractions.gcd(lcm, i)
b=[]
for i in a:
  b.append(lcm//i)
ans=sum(b)%(10**9+7)
print(ans)
### BUGGY CODE ###

# https://qiita.com/kazukazukazukazu/items/e5db00a3aefb1f5ed72f
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]

N, M = map(int, input().split())
# AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = Dijkstra()

for _ in range(M):
    a, b = map(int, input().split())
    graph.add(a, b, 1)

# for a, b in AB:
#     graph.add(a, b, 1)

ans = []
flg = False
for i in range(2, N+1):
    result = graph.getDijkstraShortestPath(i, 1)
    if result[1]==float('inf'):
        flg = True
        break
    ans.append(result[1])
#     print(result[1])

if flg:
    print('No')
else:
    print('Yes')
    for a in ans:
        print(a)
    
    

### FIXED CODE ###

import collections
N, M = map(int, input().split())
G = collections.defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
    
dist = [-1] * (N + 1)
que = collections.deque()

dist[1] = 0
que.append(1)

while len(que):
    v = que.popleft()
    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv] = dist[v] + 1
        que.append(nv)

memo = collections.defaultdict(int)
memo[0] = 1

print('Yes')
for i in range(2, N+1):
    memo[dist[i]] = i
for dis in dist[2:]:
    print(memo[dis-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int,readline().split())
*a, = map(int,readline().split())
*b, = map(int,readline().split())

from collections import Counter
d = Counter(a+b)
if max(d.values()) > n:
    print("No")
    exit()

same = set(i for i in range(n) if a[i]==b[i])
from random import randrange
while same:
    i = same.pop()
    while True:
        j = randrange(0,n)
        if a[j] != b[i] and a[i] != b[j]:
            b[i],b[j] = b[j],b[i]
            same.discard(j)
            break

print("Yes")
print(*b)


### FIXED CODE ###


class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n, = map(int,readline().split())
*a, = map(int,readline().split())
*b, = map(int,readline().split())

ca = [0]*(n+1)
cb = [0]*(n+1)

for i in a: ca[i] += 1
for i in b: cb[i] += 1


from heapq import *

qc = [0]*(n+1)
for i,(x,y) in enumerate(zip(ca,cb)):
    if x+y > n:
        print("No")
        exit()
    elif i==0 or x+y==0:
        continue
    else:
        qc[i] = x+y


def op(a,b):
    if qc[a] <= qc[b]: return b
    else: return a

s = segment_tree(n+1,op,0)
s.build(list(range(n+1)))

sa = set(a)
sb = set(b)

def dela(j):
    ca[j] -= 1
    if ca[j]==0:
        sa.remove(j)
    
def delb(j):
    cb[j] -= 1
    if cb[j]==0:
        sb.remove(j)

ans = [None]*n
for i in range(n):
    j = s.dat[1]
    #print(i,sa,sb,v,j)
    #print(j,qc,s.dat)
    if ca[j]:
        dela(j)

        for k in sb:
            if k != j: break
        delb(k)
        ans[i] = (j,k)

    else:
        delb(j)
        
        for k in sa:
            if k != j: break
        dela(k)
        ans[i] = (k,j)
    
    qc[j] -= 1
    qc[k] -= 1
    s.update(j,j)
    s.update(k,k)

from operator import itemgetter
ans.sort(key=itemgetter(0))

print("Yes")
ans = [y for x,y in ans]
print(*ans)
### BUGGY CODE ###

N,T = map(int,input().split())
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)

### FIXED CODE ###

N,T = map(int,input().split())
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)
### BUGGY CODE ###

S=input()
l=len(S)
t=0
p=0
mm=[[0] * l for i in range(10)]

for i in range(10):
    for j in range(l):
        mm[i][j]=i*(10**j)%2019




for i in range(l-1,2,-1):

    p=0
    for j in range(i+1):


        p=(p+mm[int(S[i-j])][j])%2019

        if p==0:

            t+=1

print(t)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
q=int(input())
x=[0]*q;y=[0]*q
for i in range(q):
    x[i],y[i]=map(int,input().split())
l=[]
for i in range(min(x),max(y)+1,2):
    d=prime_factorize(i)
    e=prime_factorize((i+1)//2)
    #print(d)
    if d==[i] and e==[(i+1)//2]:
        l.append(i)
#print(l)
for i in range(q):
    ans=0
    for j in range(len(l)):
        if x[i]<=l[j]<=y[i]:
            ans+=1
    print(ans)

### FIXED CODE ###

import sys
imput=sys.stdin.readline
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
q=int(input())
x=[0]*q;y=[0]*q
for i in range(q):
    x[i],y[i]=map(int,input().split())
l=[]
for i in range(min(x),max(y)+1,2):
    d=prime_factorize(i)
    e=prime_factorize((i+1)//2)
    #print(d)
    if d==[i] and e==[(i+1)//2]:
        l.append(i)
#print(l)
for i in range(q):
    ans=0
    for j in range(len(l)):
        if x[i]<=l[j]<=y[i]:
            ans+=1
    print(ans)
### BUGGY CODE ###

nums = list(map(int, input().split()))
n = nums[0]
m = nums[1]

codes = []
prefectures = []


class Prefecture:
    def __init__(self, id, list):
        self.id = id
        self.list = list


for i in range(m):
    codes.append(list(map(int, input().split())))

for code in codes:
    exist = False
    for prefecture in prefectures:
        if code[0] == prefecture.id:
            prefecture.list.append(code[1])
            exist = True
            break
    if not exist:
        prefectures.append(Prefecture(code[0], [code[1]]))

for prefecture in prefectures:
    prefecture.list = sorted(prefecture.list)

for code in codes:
    for prefecture in prefectures:
        if code[0] == prefecture.id:
            for i in range(len(prefecture.list)):
                if code[1] == prefecture.list[i]:
                    print(str(code[0]).zfill(6) + str(i+1).zfill(6))
                    break
            break

### FIXED CODE ###

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

prefectures = []

i = 0
while i < m:
    p, y = map(int, input().split())
    prefectures.append((i, p, y))
    i += 1
prefectures.sort(key=lambda x: x[2])

answers = []
ranks = [1 for i in range(n + 1)]
for i, p, y in prefectures:
    answers.append((i, str(p).zfill(6) + str(ranks[p]).zfill(6)))
    ranks[p] += 1

answers.sort()

for i, answer in answers:
    print(answer)
### BUGGY CODE ###

# encoding: utf-8
import math

N = int(input())
A = [int(input()) for i in range(N)]

A_up = sorted(A)
A_down = list(A_up[::-1])

rslt = []
idx_up = 0
idx_down = 0
for i in range(N):
    if i % 4 == 0:
        rslt = [A_up[idx_up]] + rslt
        idx_up += 1
    elif i % 4 == 1:
        rslt = rslt + [A_down[idx_down]]
        idx_down += 1
    elif i % 4 == 2:
        rslt = rslt + [A_up[idx_up]]
        idx_up += 1
    else:
        rslt = [A_down[idx_down]] + rslt
        idx_down += 1

# exception (N == 3, may be related with perfect graph ?)
if N == 3:
    if A_up[1] - A_up[0] > A_up[2] - A_up[1]:
        rslt = [A_up[1], A_up[0], A_up[2]]
    else:
        rslt = [A_up[1], A_up[2], A_up[0]]
        
ans = 0
prev = rslt[0]
for val in rslt[1:]:
    ans += (val - prev) if (val - prev) > 0 else (prev - val)
    prev = val

# print(rslt)
print(ans)

### FIXED CODE ###

# encoding: utf-8
import math, sys

N = int(input())
A = [int(input()) for i in range(N)]

A_up = sorted(A)
A_down = list(A_up[::-1])

# magic-hand-like order
# 1 2 3
# |X X  4 <- this node is taken last
# 7 6 5

ans = 0
for i in range(N // 2):
    if i == 0:
        ans += (A_down[0] - A_up[0])
    else:
        ans += (A_down[i - 1] - A_up[i])
        ans += (A_down[i] - A_up[i - 1])

if N % 2:
    ans += max((A_down[N // 2 - 1] - A_down[N // 2], A_up[N // 2] - A_up[N // 2 - 1]))

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

def is_good(mid, key):
    return sum(count_cuts(a, mid) for a in A) <= key


def binary_search(key):
    bad, good = 0, 10 ** 18
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


def count_cuts(a, unit):
    return (a + unit - 1) // unit - 1


N, K, *A = map(int, open(0).read().split())
print(binary_search(K))


### FIXED CODE ###

def is_good(mid, key):
    return sum(count_cuts(a, mid) for a in A) <= key


def binary_search(key):
    bad, good = 0, 2 * 10 ** 14 + 1
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


def count_cuts(a, unit):
    return (a + unit - 1) // unit - 1


N, K, *A = map(int, open(0).read().split())
print(binary_search(K))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist,pre):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
        pre[vertex] = v
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist,pre)
N,M = map(int,input().split())
dist = [-1] * N
seen = [False] * N
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
pre = [0] * N
bfs(0,G,queue,dist,pre)
print("Yes")
for v in range(1,N): 
    print(pre[v]+1)


### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S=input()
Q=int(input())
ans=S
cnt=0
for _ in range(Q):
    i=(input().split())
    if(int(i[0]) == 1):
        cnt= (cnt+1) % 2
    elif((cnt== 0 and i[1]=='1') or (cnt == 1 and i[1]=='2')):
        ans= i[2] + ans
    else:
        ans=''.join([ans,i[2]])
print(ans[::-1]) if(cnt % 2 == 1) else print(ans)


### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
ans=deque(S)
cnt=0
for _ in range(Q):
    i=(input().split())
    if(int(i[0]) == 1):
        cnt= (cnt+1) % 2
    elif((cnt== 0 and i[1]=='1') or (cnt == 1 and i[1]=='2')):
        ans.appendleft(i[2])
    else:
        ans.append(i[2])
ans=''.join(ans)
print(ans[::-1]) if(cnt % 2 == 1) else print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
N,K=map(int,input().split())
S=input()

#N=14
#K=2
#S="11101010110011"

LIST=[[[0] for j in range (2)]for i in range(N)]

t=S[0]
c=0
k=0
for i in range(N):
    if(t!=S[i]):
        LIST[k][0]=c
        LIST[k][1]=t
        t=S[i]
        k+=1
        c=0
    c+=1

LIST[k][0]=c
LIST[k][1]=t
LIST=LIST[0:k+1]
MAX=0

def calc(i,s,K):
    global MAX
    MAX=max(MAX,s)
    if(i==len(LIST)):
        return

    if(LIST[i][1]=="1"):
        s+=LIST[i][0]
        MAX=max(MAX,s)
        i+=1
        if(i==len(LIST)):
            return
    
    if(K>=1):
        calc(i+1,s+LIST[i][0],K-1)
    calc(i+1,0,K)

calc(0,0,K)
print(MAX)


### FIXED CODE ###

N,K=map(int,input().split())
S=input()

#K=1
#S="01100"
#N=len(S)

LIST=[[[0] for j in range (2)]for i in range(N)]

t=S[0]
c=0
k=0
for i in range(N):
    if(t!=S[i]):
        LIST[k][0]=c
        LIST[k][1]=t
        t=S[i]
        k+=1
        c=0
    c+=1

LIST[k][0]=c
LIST[k][1]=t
LIST=LIST[0:k+1]
MAX=0

s=0
l=0
r=0

if(LIST[r][1]=="1"):
    s+=LIST[r][0]
    r+=1
x=0
while(K>0 and len(LIST)>r):
    s+=LIST[r][0]
    K-=1
    if(len(LIST)-1==r):
        x=1
        break
    r+=1
    s+=LIST[r][0]
    if(len(LIST)-1==r):
        x=1
        break
    r+=1

MAX=max(s,MAX)

f=0
if(x==0):
    while(r<len(LIST)):
        if(l< len(LIST)-1):
            s-=LIST[l][0]
            l+=1
            f=1
        if(l<len(LIST)-1 and LIST[l][1]=="0"):
            s-=LIST[l][0]
            l+=1

        if(f==0):
            break
        

        s+=LIST[r][0]
        MAX=max(s,MAX)
        r+=1
        if(len(LIST)==r):
            break
        
        s+=LIST[r][0]
        MAX=max(s,MAX)
        r+=1
        if(len(LIST)==r):
            break

print(MAX)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sumlist = []
for i in range(1,n):
  sumlist.append(sum(a[i:n]))

result= 0

for j in range(0,len(sumlist)):
  result += a[j]*sumlist[j]

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

### FIXED CODE ###

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

result= 0
asum = sum(a)
for j in range(0,n):
  asum -= a[j]
  result += a[j]*(asum)

print(result%(10**9+7))
### BUGGY CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if C == 0:
    print(A)
else:
    resultList = [ A - c for c in range(C + 1 // 2) if c == K - A - B]
    print(max(resultList))


### FIXED CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if (A >= K):
    print(K)
else:
    if (B >= (K - A)):
        print(A)
    else:
        print(2*A + B - K)
### BUGGY CODE ###

N = int(input())

ans = [0] * (N + 1)
for x in range(1, N + 1):
    for y in range(1, N + 1):
        for z in range(1, N + 1):
            v = x * x + y * y + z * z + x * y + y * z + z * x
            if v <= N:
                ans[v] += 1

for i in range(1, N + 1):
    print(ans[i])

### FIXED CODE ###

N = int(input())

ans = [0] * (N + 1)
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            v = x * x + y * y + z * z + x * y + y * z + z * x
            if v <= N:
                ans[v] += 1

for i in range(1, N + 1):
    print(ans[i])
### BUGGY CODE ###

import math
from collections import deque
memo = deque([1])
mcnt = 1
def fact(x):
    global memo,mcnt
    if x == 0: return 1
    while x > mcnt:
        memo.append(memo[-1] * (mcnt + 1))
        mcnt += 1
    return memo[x-1]

CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    way = 0
    for two in range(v//2+1):
        one = v - two * 2
        comb = (fact(one+two) // (fact(one) * fact(two))) % CONST
        way = (way + comb) % CONST
    ans = (ans * way) % CONST
print(ans)



### FIXED CODE ###

import math
from collections import deque

memo = deque([1, 2])
floor = 1
def search(x):
    global memo, floor
    while x > floor:
        memo.append(memo[-1] + memo[-2])
        floor += 1
    return memo[x-1]

CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    ans = (ans * search(v)) % CONST
print(ans)
### BUGGY CODE ###


from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q = deque()
q.append((C_h - 1, C_w - 1))


while q:
    u, v = q.popleft()
    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if (0 <= u + i < H and 0 <= v + j < W
                and X[u + i][v + j] == "."
                and dist[u + i][v + j] > dist[u][v]):
            dist[u + i][v + j] = dist[u][v]
            q.append((u + i, v + j))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v] + 1):
                dist[u + i][v + j] = dist[u][v] + 1
                q.appendleft((u + i, v + j))

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 1])
else:
    print(-1)


### FIXED CODE ###


from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q1 = deque()
q1.append((C_h - 1, C_w - 1))
q2 = deque()


def bfs_1():
    while q1:
        u, v = q1.popleft()
        q2.append((u, v))
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v]):
                dist[u + i][v + j] = dist[u][v]
                q1.append((u + i, v + j))
                q2.append((u + i, v + j))


def bfs_2():
    while q2:
        u, v = q2.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (0 <= u + i < H and 0 <= v + j < W
                        and X[u + i][v + j] == "."
                        and dist[u + i][v + j] > dist[u][v] + 1):
                    dist[u + i][v + j] = dist[u][v] + 1
                    q1.append((u + i, v + j))


while q1 or q2:
    bfs_1()
    bfs_2()

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 1])
else:
    print(-1)