Harryxun/stf_run huggingface dataset:
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))


def BFS():  # 幅優先探索
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        if p == (H, W):  # ゴールを訪問したら全部終わってなくても打ち切る
            return white_num - D[H][W]
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))


def BFS():  # 幅優先探索
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and D[e[0]][e[1]] == inf:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
                if e == (H, W):
                    return white_num - D[H][W]
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))
now=False
lst=[]
N=int(input())
for k in range(N):
    lst=lst.append(input())
M=int(input())
for t in range(M):
    ID=input()
    if ID in lst:
        now=not(now)
        if now:
            print("Opened by",ID)
        else:
            print("Closed by",ID)
    else:
        print("Unknown",ID)

### FIXED CODE ###

now=False
lst=[]
N=int(input())
for k in range(N):lst.append(input())
M=int(input())
for t in range(M):
    ID=input()
    if ID in lst:
        now=not(now)
        if now:
            print("Opened by",ID)
        else:
            print("Closed by",ID)
    else:
        print("Unknown",ID)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

s = input()

i = 0

while i <= len(s):
	print(s[i], end="")
	i += 2

print()

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

s = input()
 
i = 0
 
while i <= len(s)-1:
	print(s[i], end="")
	i += 2
 
print()
# -*- coding:utf-8 -*-

n = int(raw_input())
numlist = (raw_input()).split(' ')

sumlist = [int(numlist[0])]
count = 0

for i in range(1, n):
  sumlist.append(sumlist[i-1] + int(numlist[i]))
  while (True):
    if (sumlist[i-1] > 0 and sumlist[i] > 1):  #i-1,i番目までのsumがともに正
      numlist[i] = int(numlist[i]) - 1
      sumlist[i] -= 1
      count += 1
    elif (sumlist[i-1] < 0 and sumlist[i] < 0):  #i-1,i番目までのsumがともに負
      numlist[i] = int(numlist[i]) + 1
      sumlist[i] += 1
      count += 1
    elif (sumlist[i] == 0):  #i番目までのsum=0
      if (sumlist[i-1] > 0):
        numlist[i] = int(numlist[i]) - 1
        sumlist[i] -= 1
      if (sumlist[i-1] < 0):
        numlist[i] = int(numlist[i]) + 1
        sumlist[i] += 1
      count += 1
    else:
      break

print count


### FIXED CODE ###

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

fullstr = raw_input()

sf = ['','','']

sf[0] = fullstr[0]
num = 1

for i in range(len(fullstr)):
  if (fullstr[i] == ' '):
    sf[num] = fullstr[i+1]
    num += 1

print '%s%s%s' % (sf[0].upper(), sf[1].upper(), sf[2].upper())
a,b = map(int,input().split())
from math import gcd
c = math.gcd(a,b)
answer = a*b/c
print(int(answer))

### FIXED CODE ###

a,b = map(int,input().split())
from fractions import gcd
c = gcd(a,b)
answer = a*b/c
print(int(answer))
import sys
def main():
    tmp = sys.stdin.readline().split(" ")
    while 1:
        if a > b:
            c = a
            d = b
        else:
            c = b
            d = a

        

        tmp = sys.stdin.readline()
        if len(tmp) == 1:
            break
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

#最大公約数
def gcd(x, y):
    s = x / y
    r = x % y
    if r == 0:
        return y
    else:
        return gcd(y, r)

#最小公倍数
def lcm(x, y):
    return x*y/gcd(x, y)

def main():
    #print ("a")
    for line in iter(sys.stdin.readline, ""):
        #print (line)
        #tmp = sys.stdin.readline().split(" ")
        #print ("b")
        tmp = line.split(" ")
    
        a = int(tmp[0])
        b = int(tmp[1])
        #print ("a="+str(a))
        #print ("b="+str(b))
        #b = sys.stdin.readline()
        #print ("d")
        if a > b:
            c = a
            d = b
        else:
            c = b
            d = a

        print (str(gcd(c, d)) + " " + str(int(lcm(c,d))))

        #tmp = sys.stdin.readline()
        #if len(tmp) == 1:
        #    break
        #else:
        #    tmp = tmp.split(" ")

    #print ("exit")
     
if __name__ == "__main__":
    main()
a = [int(i) for i in input().split()]
n = a[0]
l = a[1]

sum_ = 0
for i in range(n-1):
    sum_ = sum_ + (l + i - 1)

taste = [] 

for i in range(n):
    taste = sum_ - (l + i - 1)

min_sa = 0
sa = 0

for i in range(n):
    sa = sum_ - teste[i]
    if sa < min_sa:
        min_sa = sa

for i in range(n):
    if (sum_ - taste[i]) == min_sa:
        print(taste[i])
        break

### FIXED CODE ###

num = input()
#num = str(code)

if num[0] == num[1] or num[1] == num[2] or num[2] == num[3]:
    print('Bad')
else:
    print('Good')
import sys
 
if __name__ == '__manin__':
  
    r=sys.argv[1]
    pie=3.14
    
    area = r^2 * pie
    base_area = 1^1 * pie  
    
    print(int(area/base_area)(

### FIXED CODE ###

if __name__ == '__main__':
   r = int(input())
   print(pow(r,2))
import bisect

n = int(input())
c = []

for i in range(n):
    c.append(int(input()))

c.reverse()

for i in range(1,n):
    if c[i] == c[i-1]:
        c[i] += 1
        
INF = 100000000
dp = [INF] * n

for i in range(n):
    dp[bisect.bisect_left(dp,c[i])] = c[i]

print(bisect.bisect_left(dp,INF))

### FIXED CODE ###

import bisect

INF = 10000000000

n = int(input())
a = [0] * n

for i in range(n):
    a[i] = int(input())
    a[i] = - a[i]

dp = [INF] * n

for i in range(n):
    dp[bisect.bisect_right(dp,a[i])] = a[i]
    
print(bisect.bisect_left(dp,INF))
from intertools import chain
from collections import deque
H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
dhw = [[0,1],[0,-1],[1,0],[-1,0]]

ans = 0
for h in range(H):
  for w in range(W):
    d = deque([h,w])
    maze = [[-1] * W for _ in range(H)]
    if S[h][w] == '#':
      continue
    maze[h][w] = 0
    while d:
      ht , wt = d.popleft()
      for dh, dw in dhw:
        nh = ht + dh
        nw = wt + dw
        if 0 <= nh < H and 0 <= nw < W:
          if maze[nh][nw] == -1 and S[nh][nw] == '.':
            d.append([nh,nw])
            maze[nh][nw] = maze[ht][wt] + 1
    ans = max(ans,max(chain(*maze))
print(ans)


### FIXED CODE ###

from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in directions:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '#':
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()
import numpy as np
N,M = map(int,input().split())
A = np.array(map(int,input().split()))
C = np.array(A)
for i in range(M):
  p = np.argmax(C)
  C[p] = int(C[p]/2)
print(sum(C))

### FIXED CODE ###

S = input()
if S == 'Sunny':
  print('Cloudy')
elif S == 'Cloudy':
  print('Rainy')
else:
  print('Sunny')
while True:
  x, y = map(int, raw_input.split())
  if x < y:
     print 'x y'
  elif x > y :
     print 'y x'
  elif x == y:
     print 'x y'
  if x == y == 0:
     break

 

### FIXED CODE ###




while 1:
  x, y = map(int, raw_input().split())
  if x == y == 0:
     break


  if x < y:
     print '%d %d' %(x, y)
  elif x > y :
     print '%d %d' %(y, x)
  elif x == y:
     print '%d %d' %(x, y)
# import fractions
import math as fractions
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
mod = 10**9+7
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
print(ans)
sum = 0
for i in range(n):
    sum += ans//a[i]
    sum %= mod
print(sum)


### FIXED CODE ###

import fractions
# import math as fractions
mod = 10**9+7
n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(1)
    exit()

g = fractions.gcd(a[0], a[1])
f = a[0]*a[1]//g
ans = a[0]//g+a[1]//g

for i in range(2, n):
    # print(ans, g, f)
    h = fractions.gcd(f, a[i])
    g = a[i] // h
    f = f*a[i]// h
    ans *= g
    ans += f // a[i]
    ans %= mod
print(ans%mod)
from datetime import datetime as dt
d1=dt.fromisoformat('2019/04/30'.replace('/', '-'))
d2=dt.fromisoformat(input().replace('/', '-'))
delta=d1-d2
print('Heisei' if delta.days >= 0 else 'TBD')

### FIXED CODE ###

print('Heisei' if input()<='2019/04/30' else 'TBD')
n=int(input())
a=[]
for _ in range(n):
    s=list(map(int,input().split()))
    if s[2] != 0:
        a.append(s)
for i in range(101):
    for j in range(101):
        h=a[0][2]+abs(a[0][0]-i)+abs(a[0][1]-j)
        d=True

        for l in range(n):
            if a[l][2] > 0 and h != a[l][2]+abs(a[l][0]-i)+abs(a[l][1]-j):
                d=False
            elif a[l][2]==0 and h>abs(a[l][0]-i)+abs(a[l][1]-j):
                d=False
            
        if d:
            x,y,h = i,j,h
            print(x,y,h)
            

### FIXED CODE ###

n=int(input())
xyh=[]

x,y,h=-1,-1,-1
nonzero=-1

for i in range(n):
    xyh.append(list(map(int,input().split())))
    if xyh[i][2] != 0:
        nonzero = i

for px in range(101):
    for py in range(101):
        nh = xyh[nonzero][2]+abs(xyh[nonzero][0]-px)+abs(xyh[nonzero][1]-py)
        ok = True

        for nn in range(n):
            if xyh[nn][2] > 0 and nh != xyh[nn][2]+abs(xyh[nn][0]-px) + abs(xyh[nn][1]-py):
                ok=False
            if xyh[nn][2] == 0 and nh > abs(xyh[nn][0]-px) +abs(xyh[nn][1]-py):
                ok=False
        
        if ok:
            x,y,h = px,py,nh
            print(x,y,h)
            exit()
import math
A,B,H,M = map(int,input().split())
H_pos = H/12 + M/720
M_pos = M/60
print("{:.9f}".format((A**2+B**2-2*A*B*math.cos(math.radians(360*(H_pos-M_pos)))))**0.5)

### FIXED CODE ###

import math
A,B,H,M = map(int,input().split())
H_pos = H/12 + M/720
M_pos = M/60
deg = 360*(H_pos-M_pos)
if deg > 180: deg = 360-deg
rad = math.radians(deg)
co = math.cos(rad)
print("{:.9f}".format(math.sqrt(A**2+B**2-2*A*B*co)))
p, q = map(int, input().split())
import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

print(lcm(p, q))

### FIXED CODE ###

p, q = map(int, input().split())
import fractions
 
def lcm(a, b):
    return (a * b) // fractions.gcd(a, b)

print(lcm(p, q))
row1=list(map(int,input().split()))
row2=list(map(int,input().split()))
row3=list(map(int,input().split()))
bingo=row1+row2+row3
num=int(input())
num_list=set()
for i in range(num):
  num_list.add(int(input()))

bingo_list=[[0,3,6],[1,4,7],[2,5,8],[0,1,2],[3,4,5],[6,7,8],[0,4,8],[2,4,6]]
num_list=list(num_list)
for i in num_list:
  if i in bingo:
    bingo[bingo.index(i)] = True

for i in bingo_list:
  if bingo[i[0]] ==True and bingo[i[1]] == True and bingo[i[2]] == True:
    print('Yes')
    return 0

print('No')

### FIXED CODE ###

row1=list(map(int,input().split()))
row2=list(map(int,input().split()))
row3=list(map(int,input().split()))
bingo=row1+row2+row3
num=int(input())
num_list=set()
for i in range(num):
  num_list.add(int(input()))

bingo_list=[[0,3,6],[1,4,7],[2,5,8],[0,1,2],[3,4,5],[6,7,8],[0,4,8],[2,4,6]]
num_list=list(num_list)
for i in num_list:
  if i in bingo:
    bingo[bingo.index(i)] = True

for i in bingo_list:
  if bingo[i[0]] ==True and bingo[i[1]] == True and bingo[i[2]] == True:
    print('Yes')
    break
  if i == [2,4,6]:
    print('No')
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if k >= sum(a) + sum(b):
    print(n + m)
    exit()
ans = -1
total_time = 0
a_cnt = 0
b_cnt = 0
while total_time <= k:
    read_time = min(a[a_cnt], b[b_cnt])
    if read_time == a[a_cnt]:
        if a_cnt < len(a) - 1:
            a_cnt += 1
        else:
            b_cnt += 1
    else:
        if b_cnt < len(b) - 1:
            b_cnt += 1
        else:
            a_cnt += 1
    total_time += read_time
    ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
from bisect import bisect_right

n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
a = np.cumsum(a)
b = np.cumsum(b)

ans = 0
for a_num, time in enumerate(a):
    if time > k:
        continue
    b_num = bisect_right(b, k - time)
    num = a_num + b_num - 1
    if num > ans:
        ans = num
print(ans)
if __name__ == "__main__":
  int a = input()
  print(a*a)
  

### FIXED CODE ###

a = int(input())
print(a*a)
a,b = map(int,input().split())
print(6-a-b)

### FIXED CODE ###

a = int(input())
b = int(input())
print(6-a-b)
from dateutil.relativedelta import relativedelta
import datetime
S = str(input())
date_format = datetime.datetime.strptime(S,'%Y/%m/%d')
date_format = date_format+ relativedelta(years=1)
print(date_format.strftime("%Y/%m/%d"))

### FIXED CODE ###

import datetime
S = str(input())
date_format = datetime.datetime.strptime(S,'%Y/%m/%d')
print('2018/'+str(date_format.strftime("%m/%d")))
N, K = map(int, input().split())
pn = list(map(int, input().split()))

l = sum(pn[:K])
for i in range(N-K+1):
    l = max(l, l+pn[K+1+i]-pn[i])
ans = (l+K)/2
print(ans)


### FIXED CODE ###

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)
a = int(input())
b = int(input())
c = int(input())

if a > b:
 print('a > b')
 
if a < b:
 print('a < b')

if a == b:
 print('a == b')

else:
 print('none')

### FIXED CODE ###

a, b = map(int, input().split())
if a < b:
    print('a < b')
elif a > b:
    print('a > b')
else:
    print('a == b')
def calc_Stairs_Patterns(num):
    if num >= 2:
        return calc_Stairs_Patterns(num - 1) + calc_Stairs_Patterns(num - 2)
    elif num == -1:
        print(0)
        exit()
    else:
        return 0
N, M = map(int,input().split())
data = []
for i in range(M):
    data.append(int(input()))
ans = 1
stair = 0
for i in data:
    ans *= calc_Stairs_Patterns(i  - 1 - stair)
    stair = i + 1
ans *= calc_Stairs_Patterns(N - stair)
print(ans % 1000000007)

### FIXED CODE ###

N, M = map(int,input().split())
data = []
dp = ['.' for i in range(N + 1)]
dp[0] = 1
dp[1] = 1
for i in range(M):
    k = int(input())
    data.append(k)
    dp[k] = 0
mod = 10**9 + 7
for i in range(2,N + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[N] % mod)
from collections import defaultdict
n = int(input())
a = list(map(int,input().rstrip().split()))
dic = defaultdict(int)
for x in a:
  dic[x-1]+=1
  dic[x]+=1
  dic[x+1]+=1

k=0
m=0
for key,item in dic.item():
  if(item>m):
    m=item
    k=key
    
print(k)
  

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().rstrip().split()))
dic = defaultdict(int)
for x in a:
  dic[x-1]+=1
  dic[x]+=1
  dic[x+1]+=1
m=0
for v in dic.values():
  m = max(m,v)   
print(m)
S = int(input())


def prime_factorize(n):
    a = 1
    if n <= 10 ** 9:
        return n

    while n % 2 == 0:
        n //= 2
        a *= 2

    if n <= 10 ** 9:
        return n
    f = 3
    while f * f <= n:
        if n // a <= 10 ** 9:
            return a
        if n % f == 0:
            n //= f
            a *= f
        else:
            f += 2


if S <= 10 ** 9:
    print(0, 0, 1, 0, 0, S)
else:
    x = prime_factorize(S)
    y = S // x
    print(0, 0, x, 0, 0, y)

### FIXED CODE ###

S = int(input())

if S != 10 ** 18:
    q = S // 10 ** 9 + 1
    r = 10 ** 9 * q - S
else:
    q = S // 10 ** 9
    r = 10 ** 9 * q - S

print(0, 0, q, r, 1, 10 ** 9)
import numpy as np

N = int(input())
x_list = np.array(list(map(int, input().split())), reverse=True)

count = 0
for xi in x_list:
  if np.sum(xi%x_list==0) == 1:
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
a_list = sorted(list(map(int, input().split())))
a_max = a_list[-1]

count = [0] * (a_max+1)

for a in a_list:
  for j in range(a, a_max+1, a):
    count[j] += 1
  
ans = 0
for a in a_list:
  if count[a] == 1:
    ans += 1
print(ans)
A,B = int(input())
if A<B:
    if A == 1:
        print('Alice')
    else:
        print('Bob')
elif A == B:
    print('Draw')
else:
    if B == 1:
        print('Bob')
    else:
        print('Alice')


### FIXED CODE ###

A,B = map(int,input().split())
if A<B:
    if A == 1:
        print('Alice')
    else:
        print('Bob')
elif A == B:
    print('Draw')
else:
    if B == 1:
        print('Bob')
    else:
        print('Alice')
a,b,c=map(int, input.split())
printstr((z x y))

### FIXED CODE ###

x,y,z=map(int,input().split())
print(str(z)+" "+str(x)+" "+str(y))
N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    N,M = map(int,input().split())
A = []

#フィボナッチ数列
from functools import lru_cache
@lru_cache(maxsize=None)
def Fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return Fib(n-1) + Fib(n-2)

      
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り



ans = 0
for i in range(M+1):
  if(i == 0):
    n = (A[i]-1) - 0
    #print(0,(A[i]-1))  
  elif(i == M):
    n = N-(A[M-1]+1)
    #print(N,A[M-1]+1)
  else:
    n = (A[i]-1)-(A[i-1]+1)
    #print((A[i]-1),(A[i-1]+1))
    
  if(n < 0):
    ans = 0
    break
    
  if(n != 0):
   if(ans == 0): ans += (Fib(n+1))%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)
    
    
  
  if(n != 0):
   if(ans == 0): ans += Fib(n+1)%(10**9+7)
   else: ans = (ans*Fib(n+1))%(10**9+7)
print(ans)
    
    
  

### FIXED CODE ###

N,M = map(int,input().split())
A = []

#フィボナッチ数列
def Fib(n):
    a, b = 1, 1
    if n == 0:
        return 0
    elif n== 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b
 
for i in range(M):
  a = int(input())
  A.append(a)
#ans = {0~a1-1 a1+1~a2-1 ... a(M-1)+1~aM-1 の行き方の積}
#各a(i)+1~a(i+1)-1への行き方は1通り
#i ~ i+Nへの行き方 Fib(N+1)通り

#REになっていた理由:
#・Fib(0)が定義されていなかったから
#・フィボナッチ数列を再帰的(=Fib(n-1)+Fib(n-2))で定義していると、
#Nが大きい(100000とか）のときに深く潜りすぎるのでRE

if(N == 1): 
 ans = 1
elif(M == 0): 
 ans = Fib(N+1)
else: 
 ans = 0
 for i in range(M):  
    if(i == 0): #0~ a1-1 // ai+1 = A[i]
      n = (A[i]-1)-0
      #print(0,A[i]-1)
    else:
      n = (A[i]-1)-(A[i-1]+1) 
      #print(A[i-1]+1,A[i]-1)
      
    if(i != 0): #「渡れない箇所が二連続」が存在するなら0通り
     dif = A[i]-A[i-1]
     if(dif == 1):
       ans = 0
       break
          
    if(ans == 0): ans += (Fib(n+1)%(10**9 + 7))
    else: ans = ans*(Fib(n+1)%(10**9 + 7))

 n = N - (A[M-1]+1)#最後にaM + 1 ~ N のルートも考慮する
 ans = ans*(Fib(n+1)%(10**9 + 7))
 #print(A[M-1]+1,N)
            
ans = ans%(10**9 + 7)
print(ans)
while True:
        a,op,b=input().split()
        a=int(a)
        b=int(b)
            
        if op=('+'):
                print(a+b)
        elif op=('-'):
                print(a-b)
        elif op=('*'):
                print(a*b)
        elif op=('/'):
                print(a/b)
        elif op=('?'):
                break


### FIXED CODE ###



while 1:
     s=input()
     if '?' in s: break
     print(int(eval(s)))
import math


def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, math.sqrt(n) + 1, 2):
        if n % i == 0:
            return False
    return True


N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))



### FIXED CODE ###

import math

def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))
s = input()
 
ans = 0
for i in range(0, 3):
	if s[i] == 'R':
    	ans += 1
      
if ans == 2 and s[1] == 'S':
  	ans -= 1
    
print(ans)

### FIXED CODE ###

s = input()
 
ans = 0
for i in range(0, 3):
	if s[i] == 'R':
			ans += 1
      
if ans == 2 and s[1] == 'S':
  	ans -= 1
    
print(ans)