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

N = int(input())
A = list(map(int, input().split()))
a = 10**9+7

ans = 0

for i in range(N):
    b = 0
    for j in range(i+1,N):
        b += A[j]
    b = b % a
    ans += A[i]*b

ans = ans % a
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
a = 10**9+7
sumA = sum(A)

ans = 0

for i in range(N):
    sumA -= A[i]
    ans += A[i] * sumA
    ans %= a
    
print(ans)
### BUGGY CODE ###

S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    else:
      dp[j] = DP[j + 1] * (1 if S[i] == chr(65 + j) or S[i] == '?' else 0)
      dp[j] += DP[j] * (3 if S[i] == '?' else 1)
      dp[j] % p
  DP = [x for x in dp]
print(DP[0] % p)

### FIXED CODE ###

S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    elif S[i] == '?':
      dp[j] = (3 * DP[j] + DP[j + 1]) % p
    elif S[i] == chr(65 + j):
      dp[j] = (DP[j] + DP[j + 1]) % p
    else:
      dp[j] = DP[j]
  DP = [x for x in dp]
print(DP[0] % p)
### BUGGY CODE ###

n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      while(yen>=list[t-1]):
        yen-=list[t-1]
        stock+=1
      yen+=list[t]*stock
      stock=0
print(yen)

### FIXED CODE ###

n=int(input())
list=[[0]*n]
list=input().split()
for i in range(n):
  list[i]=int(list[i])

yen=1000
stock=0
keikou=0
for i in range(1,n):
  if list[i]-list[i-1]<=0:
    keikou+=1
if keikou!=n-1:
  for t in range(1,n):
    if list[t]-list[t-1]>=0:
      stock+=int(yen/list[t-1])
      yen-=list[t-1]*int(yen/list[t-1])
      yen+=list[t]*stock
      stock=0
print(yen)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = [int(input()) for i in range(N)]
temp = 0

for i in range(N):
	temp = A[i]
	del A[i]
	print(max(A))
	A.insert(i,temp)
	temp = 0

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = [int(input()) for i in range(N)]
Am = max(A)
Asm = sorted(A)[-2]

for i in range(N):
	if A[i] != Am:
		print(Am)
	else:
		print(Asm)
### BUGGY CODE ###

import itertools

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
B = list(map(int, input().split()))
B.sort(reverse=True)
C = list(map(int, input().split()))
C.sort(reverse=True)

AB = []
for p in itertools.product(A, B):
    AB.append(sum(p))
AB.sort(reverse=True)
AB = AB[:K]

l = []
for p in itertools.product(AB, C):
    l.append(sum(p))
l.sort(reverse=True)
for i in range(K):
    print(l[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import collections

s = input()
t = input()
s_counter = collections.Counter(s)
t_counter = collections.Counter(t)
check = [s_counter[k] for k in t_counter.keys()]
if 0 in check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		for j in range(s_size):
			if s[(ans + j) % s_size] == target:
				ans += j + 1
				break
print(ans)
	

### FIXED CODE ###

import collections
import bisect

s = input()
t = input()
s_index = {}
	
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		if cursor > s_index[target][-1]:
			find = False
		else:
			j = bisect.bisect_left(s_index[target], cursor)
			find = True
		diff = s_index[target][j] - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)
### BUGGY CODE ###

def solve():
    import sys
    input = sys.stdin.readline

    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)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = FenwickTree(N+1)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

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

    for l, r, idx in m:
        for i in range(right, r):
            x = pos[c[i]]
            if x:
                tree.add(x, -1)
            pos[c[i]] = i+1
            tree.add(i+1, 1)
        ans[idx] = tree.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


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

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] +=dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)

### FIXED CODE ###

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)
### BUGGY CODE ###

import sys

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

answer = 0
for i in range(N):
    flag = True;
    
    for j in range(i):
        if P[i] > P[j]:
            flag = False
    
    if flag:
        answer += 1

print (answer)

### FIXED CODE ###

import sys

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

answer = 0
prevMin = 2 ** 32
for i in range(N):
    if P[i] <= prevMin:
        answer += 1
        prevMin = P[i]

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

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

l = len(bin(max(a))[2:])

cumsums = [[0] for _ in range(l)]
for i in range(n):
    for j in range(l):
        if a[i] & (1 << j):
            cumsums[j].append(cumsums[j][-1] + 1)
        else:
            cumsums[j].append(cumsums[j][-1])

ans = 0
from bisect import bisect_left
for i in range(1, n+1):
    left = 0
    for j in range(l):
        idx = bisect_left(cumsums[j], cumsums[j][i] - 1)
        left = max(left, idx)
    ans += i - left
print(ans)


### FIXED CODE ###

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

l = len(bin(max(a))[2:])

cumsums = [[0] for _ in range(l)]
for i in range(n):
    for j in range(l):
        if a[i] & (1 << j):
            cumsums[j].append(cumsums[j][-1] + 1)
        else:
            cumsums[j].append(cumsums[j][-1])

ans = 0
left = 0
for i in range(1, n+1):
    while left < i:
        f = True
        for j in range(l):
            if cumsums[j][left] < cumsums[j][i] - 1:
                f = False

        if f:
            break
        else:
            left += 1

    ans += i - left
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for i in range(q)]

for x in a:
  print(s[x[0]-1:x[1]].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
a = [list(map(int, input().split())) for i in range(q)]

c = [0] * n
for i in range(1,n):
  c[i] = c[i-1] + (s[i-1]+s[i] == 'AC')

for x in a:
  print(c[x[1]-1]-c[x[0]-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import accumulate
def inpl(): return map(int, input().split())

N, K, Q = inpl()
A = " " + input()
S = sorted(map(int, A.split()))
ans = S[Q-1] - S[0]
S = S[::-1]

while S:
    s = S.pop()
    A = A.replace(" {} ".format(s), " x ")

    OK = 0
    Que = A.split("x")

    tmp = []
    for q in Que:
        tmp.extend(sorted([int(x) for x in q.split()])[::-1][K-1:])
    if len(tmp) < Q:
        break
    tmp = sorted(tmp)
    ans = min(ans, tmp[Q-1] - tmp[0])

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import accumulate
def inpl(): return map(int, input().split())

N, K, Q = inpl()
A = " " + input()
S = sorted(map(int, A.split()))
ans = S[Q-1] - S[0]
S = S[::-1]

while S:
    s = S.pop()
    A = A.replace(" {} ".format(s), " x ")

    OK = 0
    Que = A.split("x")

    tmp = []
    for q in Que:
        tmp.extend(sorted([int(x) for x in q.split()])[::-1][K-1:])
    if len(tmp) < Q:
        break
    tmp = sorted(tmp)
    ans = min(ans, tmp[Q-1] - tmp[0])

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

a,b = map(int,input().split())
tower = [1]
tower_kai = []
for i in range(2,999):
    tower.append(tower[i-2]+i)
for i in range(len(tower)-1):
    tower_kai.append([tower[i],tower[i+1]])
i = 0
while(True):
    ab_list = [a+i,b+i]
    if(ab_list in tower_kai):
        print(i)
        exit()
    i+=1


### FIXED CODE ###

a,b = map(int,input().split())
print(int((b-a)*(b-a+1)/2-b))
### BUGGY CODE ###

N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [[INF] * (max_v * N+1) for _ in range(N+1)]
max_sum = max_v*N
dp[0][0] = 0

for i in range(N):
    for j in range(max_v * N+1):
        if j+v[i] > max_sum:
            break
        dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(max_v * N + 1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)


### FIXED CODE ###

N, W = map(int, input().split())
w = []
v = []
max_v = 1000
for _ in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
INF = int(1e9)*(N+1)
dp = [[INF] * (max_v * N+1) for _ in range(N+1)]
max_sum = max_v*N
dp[0][0] = 0

for i in range(N):
    for j in range(max_v * N+1):
        if j+v[i] > max_sum:
            break
        dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for i in range(max_v * N + 1):
    if dp[N][i] <= W:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T

if sum(sum(s) for s in S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.array([0]*len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[i] for i in m) for m in M]
                if any(d > K for d in D):
                    ans = answer + 1
                    break

        answer = min(answer,ans)

    print(answer)

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for _ in range(N+1)]

    for i in range(1, N+1):
        w, v = map(int, input().split())
        dp_pre = dp[i-1]
        for j in range(w):
            dp[i][j] = dp_pre[j]
        for j in range(w, W+1):
            dp[i][j] = max(dp_pre[j-w] + v, dp_pre[j])

    print(max(dp[N]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, W = map(int, input().split())
    dp = [[0] * (W+1) for _ in range(N+1)]

    for i in range(1, N+1):
        w, v = map(int, input().split())
        dp_pre = dp[i-1]
        for j in range(w):
            dp[i][j] = dp_pre[j]
        for j in range(w, W+1):
            dp[i][j] = max(dp_pre[j-w] + v, dp_pre[j])

    print(max(dp[N]))


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

n,p= map(int,input().split())
res=1
if n==1:
    res=p
else:
    for i in range(int(p**(1/n))+2,1,-1):
        if p%i**n==0:
            res=i
            break
print(res)

### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[str]"):
    ans = 0
    for i in range(60):
        z = 0
        o = 0
        for a in A:
            if i + 1 > len(a):
                z += 1
            else:
                if a[len(a) - i - 1] == '0':
                    z += 1
                else:
                    o += 1
        ans += (z * o) * (2 ** i)
        ans %= MOD
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [bin(int(next(tokens)))[2:] for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[str]"):
    ans = 0
    for i in range(60):
        z = 0
        o = 0
        for a in A:
            if i + 1 > len(a):
                z += 1
            else:
                if a[len(a) - i - 1] == '0':
                    z += 1
                else:
                    o += 1
        ans += (z * o) * (2 ** i)
        ans %= MOD
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [bin(int(next(tokens)))[2:] for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

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

N = int(input())

a = []

for i in range(N):
    a.append(int(input()))

ans = 0
b_now = 1
loop = []

if 2 in a:
    for i in range(1, N + 1):
        loop.append(b_now)
        b_now = a[b_now - 1]
        ans += 1
        if b_now == 2:
            print(ans)
            exit()
        elif b_now in loop:
            print(-1)
            exit()
else:
    print(-1)

### FIXED CODE ###

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

N = int(input())

a = []

for i in range(N):
    a.append(int(input()))

ans = 0
b_now = 1
loop = []

for i in range(N):
    b_now = a[b_now - 1]
    ans += 1
    if b_now == 2:
        print(ans)
        exit()

print(-1)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

pc = True
gg = False
cnt = Counter()

fs = set()
fm = {}

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp in fs:
            arr += fm[temp]
            break
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    fm[n] = arr
    fs.add(n)
    return arr

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1
print(ans)


### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s - x - y <= k:
            ans += 1
            # print(x, y, s - x - y)
print(ans)
### BUGGY CODE ###

S=input()
Q=int(input())
lis=[]
for _ in range(Q):
    lis.append(input().split())
ans=S
cnt=0
for i in lis:
    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 ###

S = list(input())
q = int(input())
Q = [list(input().split()) for _ in range(q)]

for i in range(q):
    if len(Q[i]) == 1:
        S.reverse()
    elif Q[i][1] == "1":
        S = [Q[i][2]] + S
    else:
        S = S + [Q[i][2]]

for i in range(len(S)):
    print(S[i],end="")
print()


### FIXED CODE ###

from collections import deque

S = list(input())
s = deque(S)
q = int(input())
Q = [list(input().split()) for _ in range(q)]

rev = 0
for i in range(q):
    if len(Q[i]) == 1:
        rev += 1
        rev %= 2
    else:
        if rev == 0:
            if Q[i][1] == "1":
                s.appendleft(Q[i][2])
            else:
                s.append(Q[i][2])
        else:
            if Q[i][1] == "2":
                s.appendleft(Q[i][2])
            else:
                s.append(Q[i][2])

s = list(s)
if rev == 0:
    for i in range(len(s)):
        print(s[i],end="")
else:
    for i in reversed(range(len(s))):
        print(s[i],end="")
print()
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  c.append(c[i]+a[i])

d=[0]
for i in range(m):
  d.append(d[i]+b[i])

e=0
for i in range(n+1):
  for j in range(m+1):
    if c[i]+d[j]<=k and i+j>e:
      e=i+j
print(e)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
f=len(d)-1
for i in range(len(c)):
  for j in range(f,-1,-1):
    if c[i]+d[j]<=k:
      if i+j>e:
        e=i+j
      f=j
      break
print(e)
### BUGGY CODE ###

import numpy as np
import math
N,M = list(map(int,input().split()))
A = np.array([-1]+[int(input()) for _ in range(M)]+[N+1])
A = np.diff(A, n= 1)
cnt = 0
ans = 1
for d in A:
  d -= 2
  cnt = 0
  for j in range(d//2+1):
    cnt += math.factorial(d-j)//(math.factorial(d-j*2)*math.factorial(j))
  ans *= cnt
print(ans%1000000007)

### FIXED CODE ###

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A=[int(input()) for _ in range(M)]
B=[1]*(N+1)
for i in range(M):
    B[A[i]] = 0
for i in range(N):
    if i-1 >= 0:
        dp[i+1] = dp[i]*B[i]+dp[i-1]*B[i-1]
    else:
        dp[i+1] = dp[i]*B[i]
    dp[i+1] %= 10**9+7
print(dp[N])