Harryxun/stf_run huggingface dataset:
n=int(input())
ac, wa, tle, re=0, 0, 0, 0
for i in range(n):
  str=input(str())
  if str=='AC':
    ac++
  elif str=='WA':
    wa++
  elif str=='TLE':
    tle++
  elif str=='RE':
    re++

print('AC x ', ac)
print('WA x ', wa)
print('TLE x ', tle)
print('RE x ', re)

### FIXED CODE ###

n=int(input())
ac, wa, tle, re=0, 0, 0, 0
for i in range(n):
  s=input(str())
  if s=='AC':
    ac=ac+1
  elif s=='WA':
    wa=wa+1
  elif s=='TLE':
    tle=tle+1
  elif s=='RE':
    re=re+1

print('AC x ', ac)
print('WA x ', wa)
print('TLE x ', tle)
print('RE x ', re)
n=input()
b=map(int , input().slice())
c=1
for i in range(1,n):
  c=c*b[i]
  
print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split( )))
if 0 in a:
  print(0)
  
else:
    c=1
    for i in a:
        c= c*i
        if c> 10**18:
            c=-1
            break
    print(c)
import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
x = [0, *x]
 
# 状態リストを作成
m = np.zeros((S+1,3))
p = np.zeros((S+1,3))
p[0,0] = 1

# 前状態から次状態の場合数を計算
for i in range(1,N+1):
    
    # x[i] を加えない場合
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

    # x[i] を加える場合
    m[x[i]:,1] += p[:-x[i],0] + p[:-x[i],1]
    m[x[i]:,2] += p[:-x[i],0] + p[:-x[i],1]

    p[:,0] = m[:,0] % 998244353
    p[:,1] = m[:,1] % 998244353
    p[:,2] = m[:,2] % 998244353
            
print(int(p[S,2]))

### FIXED CODE ###

import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
 
# 状態リストを作成
m = np.zeros((S+1,3))
p = np.zeros((S+1,3))
p[0,0] = 1

# 前状態から次状態の場合数を計算
for i in range(1,N+1):
    
    # x[i] を加えない場合
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

    # x[i] を加える場合
    m[x[i-1]:,1] += p[:-x[i-1],0] + p[:-x[i-1],1]
    m[x[i-1]:,2] += p[:-x[i-1],0] + p[:-x[i-1],1]

    p[:,0] = m[:,0] % 998244353
    p[:,1] = m[:,1] % 998244353
    p[:,2] = m[:,2] % 998244353
            
print(int(p[S,2]))
n,k=map(int,input().split())
if (n-2)*(n-1)//2<k:
    print(-1)
else:
    print(n-1+(n-2)*(n-1)//2-k)
    for i in range(2,n+1):
        print(1,i)
    c=0
    for i in range(2,n+1):
        for j in range(2,n+1):
            if i<j:
                print(i,j)
                c+=1
                if c==(n-2)*(n-1)//2-k:
                    exit()

### FIXED CODE ###

s=list(input())
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
    print('Bad')
else:
    print('Good')
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans=[10*9]*n
if a[0]==1:
    ans[0]=0
else:
    ans[0]=1
if len(ans)>1:
    ans[1]=ans[0]+1
for i in range(m):
    ans[a[i]-1]=0
for j in range(n-2):
    if ans[j+2]==0:
        continue
    else:
        ans[j+2]=ans[j+1]+ans[j]
        ans[j+2]=ans[j+2]%(1000000007)
    #print(ans)
print(ans[n-1])
#print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans=[10*9]*n
ans[0]=1
for i in range(m):
    ans[a[i]-1]=0
if len(ans)>1 and ans[1]!=0:
    ans[1]=ans[0]+1
for j in range(n-2):
    if ans[j+2]==0:
        continue
    else:
        ans[j+2]=ans[j+1]+ans[j]
        ans[j+2]=ans[j+2]%(1000000007)
    #print(ans)
print(ans[n-1])
#print(ans)
n,k=map(int,input().split())
a = list(map(int,input().split()))
minus = [0]+[abs(a[i]) for i in range(n) if a[i] < 0][::-1]

plus = [0]+[a[i] for i in range(n) if a[i] >= 0]

min_ = 10**18

if len(plus) == 0:
  print(minus[k])
elif len(minus) == 0:
  print(plus[k])
elif len(plus) < len(minus):
  for i in range(min(k+1, len(plus))):
    min_ = min(min_, 2*plus[i]+minus[k-i], plus[i]+2*minus[k-i])
  print(min_)
else:
  for i in range(min(k+1, len(minus))):
    min_ = min(min_, 2*minus[i]+plus[k-i], minus[i]+2*plus[k-i])
  print(min_)  
  


### FIXED CODE ###

n,k=map(int,input().split())
a = list(map(int,input().split()))
minus = [0]+[abs(a[i]) for i in range(n) if a[i] < 0][::-1]

plus = [0]+[a[i] for i in range(n) if a[i] >= 0]

min_ = 10**18

if len(plus) == 1:
  print(minus[k])
elif len(minus) == 1:
  print(plus[k])
else:
  for i in range(min(k+1, len(plus))):
    if k-i < len(minus):
      min_ = min(min_, 2*plus[i]+minus[k-i], plus[i]+2*minus[k-i])
  print(min_)
from heapq import heappop,heappush
n = int(input())
A = sorted(list(map(int,input().split())))
P = []
M = []
if n == 2:
    print(A[1]-A[0])
    print(A[1],A[0])
    exit()
def move():
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
for a in A:
    if a>=0:
        P.append(a)
    else:
        M.append(a)

if A[-1]>=0 and A[0]<=0:
    print(sum(abs(a) for a in A))
elif A[0]>=0:
    print(sum(A)-min(A)*2)
    mm = heappop(P)
    pp = heappop(P)
    print(mm,pp)
    heappush(M,mm-pp)
else:
    print(sum(abs(a) for a in A)+max(A)*2)
    mm = M[-1]
    pp = M[-2]
    print(mm,pp)
    M = M[:-2]
    heappush(P,mm-pp)
move()

### FIXED CODE ###

from heapq import heappop,heappush
n = int(input())
A = sorted(list(map(int,input().split())))
P = []
M = []
if n == 2:
    print(A[1]-A[0])
    print(A[1],A[0])
    exit()
def move():
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
for a in A:
    if a>=0:
        P.append(a)
    else:
        M.append(a)

if A[-1]>=0 and A[0]<0:
    print(sum(abs(a) for a in A))
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
elif A[0]>=0:
    print(sum(A)-min(A)*2)
    mm = heappop(P)
    pp = heappop(P)
    print(mm,pp)
    heappush(M,mm-pp)
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
else:
    print(sum(abs(a) for a in A)+max(A)*2)
    mm = M[-1]
    pp = M[-2]
    print(mm,pp)
    M = M[:-2]
    heappush(P,mm-pp)
    while len(P)!= 1:
        mm = heappop(M)
        pp = heappop(P)
        print(mm,pp)
        heappush(M,mm-pp)
    while len(M) != 0:
        mm = heappop(M)
        pp = heappop(P)
        print(pp,mm)
        heappush(P,pp-mm)
def main():
  from sys import *
  from math import gcd
  n = int(stdin.readline())
  a = [int(z) for z in stdin.readline().split()]
  lcm = a[0]
  for i in range(1, n):
    lcm = lcm * a[i] / gcd(lcm, a[i])
  sm = 0
  for i in range(n):
    sm += lcm // a[i]
  print(sm)

### FIXED CODE ###

def main():
  from sys import stdin
  from fractions import gcd
  n = int(stdin.readline())
  a = [int(z) for z in stdin.readline().split()]
  lcm = a[0]
  for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
  sm = 0
  for i in range(n):
    sm += lcm // a[i]
  print(sm % (10**9 + 7))

main()
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
i_num = 0
two_0 = []
two_1 = []
for i in v:
    if i_num % 2 == 0:
        two_0.append(i)
    else:
        two_1.append(i)
    i_num += 1
two_1_counter = Counter(two_1)
t1_elem = two_1_counter.most_common()[0][0]
t1 = two_1_counter.most_common()[0][1]
two_0_counter = Counter(two_0)
if two_0_counter.most_common()[0][0] == t1_elem:
    if two_0_counter.most_common()[0][1] != len(two_0):
        if two_1_counter.most_common()[0][0] == len(two_1):
            if two_0_counter.most_common()[1][1] > two_1_counter.most_common()[1][1]:
                t0 = two_0_counter.most_common()[1][1]
            else:
                t1 = two_1_counter.most_common()[1][1]
        else:
            t1 = 0
    else:
        t0 = 0
else:
    t0 = two_0_counter.most_common()[0][1]
print(n - (t0+t1))


### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
gu, ki = [], []
for i in range(n):
	if i % 2 == 0:
		ki.append(v[i])
	else:
		gu.append(v[i])
ki_flag, gu_flag = False, False
kict = Counter(ki)
guct = Counter(gu)
kict_mc = kict.most_common()
guct_mc = guct.most_common()
if len(kict_mc) > 1:
	ki_flag = True
if len(guct_mc) > 1:
	gu_flag = True
ki_first = kict_mc[0][0]
if ki_flag:
	ki_second = kict_mc[1][0]
gu_first = guct_mc[0][0]
if gu_flag:
	gu_second = guct_mc[1][0]
if ki_flag & gu_flag:
	if ki_first == gu_first:
		print(min([n - kict_mc[0][1] - guct_mc[1][1], n - kict_mc[1][1] - guct_mc[0][1]]))
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
elif ki_flag:
	if ki_first == gu_first:
		print(n - kict_mc[1][1] - guct_mc[0][1])
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
elif gu_flag:
	if ki_first == gu_first:
		print(n - kict_mc[0][1] - guct_mc[1][1])
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
else:
	if ki_first == gu_first:
		print(int(n / 2))
	else:
		print(n - kict_mc[0][1] - guct_mc[0][1])
a, b, c = int(input().split())

if a == b == c:
    print(1)
elif a == b or a == c or b == c:
    print(2)
else:
    print(3)

### FIXED CODE ###

a, b, c = map(int, input().split())

if a == b == c:
    print(1)
elif a == b or a == c or b == c:
    print(2)
else:
    print(3)
n = int(input())

arr = []
for i in range(n):
	arr.append(raw_input())

count = 0

def dfs(rest_str,person_count,i):
	global count
	if person_count == 3:
		count += 1

	elif i < n:
		if arr[i][0] in rest_str :
			dfs(rest_str.replace(arr[i][0],''),person_count+1,i+1)

		dfs(rest_str,person_count,i+1)

dfs('MARCH',0,0)
print count


### FIXED CODE ###

import itertools
n = int(raw_input())

d = {'M':0,'A':0,'R':0,'C':0,'H':0}

for i in range(n):
	s = raw_input()
	if d.has_key(s[0]):
		d[s[0]] += 1

count = 0

for comb in list(itertools.combinations(d.keys(),3)):
	count += d[comb[0]]* d[comb[1]]*d[comb[2]]

print count
N,M = map(int,input().split())
cntNode = [0]*N
for i in range(N):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    cntNode[a] += 1
    cntNode[b] += 1

flag = True
for i in range(N):
    if(cntNode[i] % 2 != 0):
        flag = False
        break
if(flag):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

N,M = map(int,input().split())
cntNode = [0]*N
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    cntNode[a] += 1
    cntNode[b] += 1

flag = True
for i in range(N):
    if(cntNode[i] % 2 != 0):
        flag = False
        break
if(flag):
    print('YES')
else:
    print('NO')
import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = {}
for i in range(m):
  a,b,c = map(int,input().split())
  cost[(a,b)] = c

ans = 1000000
for p in itertools.permutations(r):
  c = 0
  for i in range(len(r)-1):
    c += cost[(p[i], p[i+1])]
  ans = min(c, ans)
print(ans)

### FIXED CODE ###

import itertools
n,m,R = map(int,input().split())
r = list(map(int,input().split()))
cost = [[-1]*n for i in range(n)]
for i in range(m):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if k == i or k == j or cost[i][k] == -1 or cost[k][j] == -1:
                continue
            if cost[i][j] == -1:
                cost[i][j] = cost[i][k]+cost[k][j]
            else:
                cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = -1
for p in itertools.permutations(r):
    c = 0
    for i in range(R-1):
        c += cost[p[i]-1][p[i+1]-1]
    if ans == -1:
        ans = c
    else:
        ans = min(c, ans)
print(ans)
h,w,m=map(int,input().split())
bomb=[]
x=[0]*(h+1)
y=[0]*(w+1)
for i in range(m):
    h1,w1=map(int,input().split())
    x[h1]+=1
    y[w1]+=1
    bomb.append((h1,w1))
maxx=max(x)
maxy=max(y)
r=[]
c=[]
for i in range(1,h+1):
    if x[i]==maxx:
        r.append(i)
for j in range(1,w+1):
    if y[i]==maxy:
        c.append(i)
for j in r:
    for k in c:
        if (j,k) not in bomb:
            print(maxx+maxy)
            exit()
print(maxx+maxy-1)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ng=0
ok=max(a)+1
while ok-ng>1:
    mid=(ng+ok)//2
    count=0
    for i in range(n):
        if a[i]%mid==0:
            count+=((a[i]//mid)-1)
        else:
            count+=(a[i]//mid)
    if count>k:
        ng=mid
    else:
        ok=mid
print(ok)
n, *l = map(int, open(0).read().split())
sl = sorted(l,reverse=True)
ans = 0
for i in range (n):
  for j in range (i+1,n):
    for k in range(j+1,n):
      if sl[i]-sl[j] < sl[j] and sl[i]<sl[j]+sl[k]:
        ans = ans + 1
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
ans = max (0, a - b*2)
print(ans)
def valid(i,j):
    if i>=0 and i<h and j>=0 and j<w:
        return 1
    return 0
def paths(i,j):

    if valid(i,j)==0 or  a[i][0][j]=='#':
        return 0
    if i==h-1 and j==w-1:
        return 1

    if dp[i][j]==-1:
           a=0
           a+=paths(i+1,j)%m
           a+=paths(i,j+1)%m
           dp[i][j]=a%m
           return dp[i][j]
    else:
            return dp[i][j]



h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(1000)]for _ in range(1000)]
print(paths(0,0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '#':
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)
n, x = map(int, input().split())
a, p = [1], [1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X - 2 - a[N-1])


print(f(N, X))


### FIXED CODE ###

n, x = map(int, input().split())
a, p = [1], [1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X - 2 - a[N-1])


print(f(N=n, X=x))
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()

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 unite(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 main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    roots = uf.roots()
    cnt = []
    for r in roots:
        cnt.append(uf.size(r))
    print(max(cnt))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()

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 unite(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 main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    roots = uf.roots()
    cnt = []
    for r in roots:
        cnt.append(uf.size(r))
    print(max(cnt))

if __name__ == '__main__':
    main()
import sys

sys.setrecursionlimit(10 ** 9)


def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


def dfs(y, x, k):
    global need_len
    if b[y][x]: return
    b[y][x] = True
    if not (0 <= y < H and 0 <= x < W): return
    if a[y][x] == '#': return
    need_len = min(need_len, shortest_len(y, x))
    if k == 0: return
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        dfs(y + dy, x + dx, k - 1)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
b = [[False for _ in range(W)] for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)
dfs(sy, sx, K)

print(1 + (need_len + K - 1) // K)

'''
最初の魔法で、K回移動で到達できる範囲で、最も壁に近い場所まで移動する
以後、魔法を使用する毎に壁までの最短距離をKずつ移動する
壁に到達したら終了
'''


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                visited[nr][nc] = True
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()
def fib_memo(n):
    """メモ化フィボナッチ"""
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


### FIXED CODE ###

N, M = map(int, input().split())
A = [True] * (N+1)
for _ in range(M):
  idx = int(input())
  A[idx] = False

step = [0] * (N+1)
step[0] = 1
for i in range(1, N+1):
  if A[i]:
    step[i] = step[i-1] + step[i-2]
  else:
    step[i] = 0
print(step[N]%(10**9+7))
N, K = map(int, input().split())
p = list(map(int, input().split()))
p.sort()

print(sum(p[0:K])

### FIXED CODE ###

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

print(sum(p[0:K]))
N=int(input())
x=0
y=0
for i in range(N):
    a,b=input().split()
    if a<b:
        y+=3
    elif a==b:
        x+=1
        y+=1
    else:
        x+=3
print(x,y)


### FIXED CODE ###

n = int(input())
x, y = 0, 0
for i in range(n):
    a, b = input().split()
    if a < b:
        y +=  3
    elif a == b:
        x += 1
        y += 1
    else:
        x += 3
print(x, y)
a,b,v,w,t=int(input().split())

if a<b:
  if b+wt<=a+vt:
    print('YES')
  else:
    print('NO')

if a>b:
  if a-vt<=b-wt:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

a,v=map(int, input().split())
b,w=map(int, input().split())
t=int(input())
 
if a<b:
  if b+w*t<=a+v*t:
    print('YES')
  else:
    print('NO')
if a>b:
  if a-v*t<=b-w*t:
    print('YES')
  else:
    print('NO')
#1+2+2+2=7
K=input()
keta=len(K)
#print(K,keta)

for i in range(1<<(keta-1)):#探索数
  ANS=K[0]
  for j in range(keta-1):#調査桁数
    if (i>>j) &1 == 1:#bitがある、つまりプラスが入る場合
      ANS+="+"
    ANS+=K[j+1]
#  print(ANS)
  if eval(ANS)==7:
    print(ANS+"=7")
    break
  

### FIXED CODE ###

#1+2+2+2=7
K=input()
keta=len(K)
#print(K,keta)

for i in range(1<<(keta-1)):#探索数
  ANS=K[0]
  for j in range(keta-1):#調査桁数
    if (i>>j) &1 == 1:#bitがある、つまりプラスが入る場合
      ANS+="+"
    else:
      ANS+="-"
    ANS+=K[j+1]
#  print(ANS)
  if eval(ANS)==7:
    print(ANS+"=7")
    break
= map(int, input().split())
for i in range(n + 1):
  for ii in range(n - i + 1):
    if 10000 * i + 5000 * ii + 1000 * (n - i - ii) == y:
      print('{} {} {}'.format(i, ii, n - i - ii))
      exit()
print('-1 -1 -1')

### FIXED CODE ###

n, y = map(int, input().split())
for i in range(n + 1):
  for ii in range(n - i + 1):
    if 10000 * i + 5000 * ii + 1000 * (n - i - ii) == y:
      print('{} {} {}'.format(i, ii, n - i - ii))
      exit()
print('-1 -1 -1')
a,b = [int(i) for i in input().split()]
n = b-a-1
print(int(n*(n+1)/2-a))

### FIXED CODE ###

N = int(input())
if N < 1000:
    print('ABC')
elif N >= 1000:
    print('ABD')