Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    x, y = x//g, y//g
    if x == 0 and y == 0:
        Empty += 1
    else:
        if y < 0 or (y==0 and x < 0):
            y = -y
        if (x, y) in As:
            As[(x, y)] += 1
        else:
            As[(x, y)] = 1

M = N - Empty
ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        if x > 0:
            ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1)%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    if g == 0:
        Empty += 1
        continue
    x, y = x//g, y//g
    if y < 0 or (y==0 and x < 0):
        y = -y
        x = -x
    if (x, y) in As:
        As[(x, y)] += 1
    else:
        As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1+Empty)%mod)
x=int(input())
x=1000-x%1000
if(x==1000):
    x=0
return(x)

### FIXED CODE ###

x=int(input())
x=1000-x%1000
if(x==1000):
    x=0
print(x)
from sympy import isprime
X = int(input())
ans = 0
for i in range(X, 10 ** 5 + 1):
    if isprime(i):
        ans = i
        break

print(i)

### FIXED CODE ###

import math
def isPrime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
    # ２ではない偶数は素数ではない
        return False
  
  # nの半分まで計算する範囲を絞る
    m = math.floor(n / 2) + 1
    for p in range(3, m, 2): # 奇数だけ計算する
        if n % p == 0:
            return False
    return True
# def isPrime(n):
#     if n < 2:
#     # 2未満は素数でない
#         return False
#     if n == 2:
#     # 2は素数
#         return True
#     for p in range(2, n):
#         if n % p == 0:
#         # nまでの数で割り切れたら素数ではない
#             return False
#   # nまでの数で割り切れなかったら素数
#     return True
X = int(input())
ans = 0
for i in range(X, 10 ** 10):
    if isPrime(i):
        ans = i
        break

print(ans)
a=

### FIXED CODE ###

a = int(input())
s = input()
print(s if a >= 3200 else 'red')
N,K = list(map(int,input().split()))
D = list(map(int,input().split()))

D_ = [_ for _ in range(10) if _ not in D]
D_.sort()

N_=N+1
break_flag=False
for s_ in D_:
    if break_flag:
        break
    elif s_ == 0:
        continue
    for p in product(D_,repeat=len(str(N_))-1):
        ans=int(str(s_)+''.join(map(str,p)))
        if N+1 <= ans:
            print(ans)
            break_flag=True
            break

### FIXED CODE ###

from itertools import product
N,K = list(map(int,input().split()))
D = list(map(int,input().split()))

D_ = [_ for _ in range(10) if _ not in D]
D_.sort()

break_flag=False
for s_ in D_:
    if break_flag:
        break
    elif s_ == 0:
        continue
    for p in product(D_,repeat=len(str(N))-1):
        ans=int(str(s_)+''.join(map(str,p)))
        if N <= ans:
            print(ans)
            break_flag=True
            break
            
if break_flag==False:
    for s_ in D_:
        if break_flag:
            break
        elif s_ == 0:
            continue
        for p in product(D_,repeat=len(str(N))):
            ans=int(str(s_)+''.join(map(str,p)))
            if N <= ans:
                print(ans)
                break_flag=True
                break
S = int(input())
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
    print('Bad')
else:
    print('Good')

### FIXED CODE ###

S = input()

if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print('Bad')
else:
    print('Good')
import bisect

N, K =map(int,input().split())
X = [int(x) for x in input().split()]

l = []
r = []
for x in X:
  if x<0:
    l.append(-x)
  else:
    r.append(x)
l = l[::-1]


sl = 2*10**8
sr = 2*10**8
sa = 2*10**8

if len(l)>=K:
  sl = l[K-1]
if len(r)>=K:
  sr = r[K-1]

if len(l)!=0 and len(r)!=0:
  il = 0
  ir = 0
  while not(il+ir+2>=K):
    if il>=len(l)-1:
      ir += 1
    elif ir>=len(r)-1:
      il += 1
    else:
      if l[il+1]<l[ir+1]:
        il+=1
      else:
        ir+=1
  sa = l[il] + r[ir] +min(l[il],r[ir])

print(min([sl, sr, sa]))


### FIXED CODE ###

N, K = map(int,input().split())
A = [int(x) for x in input().split()]

ans = 3*10**8 + 1
for i in range(N-K+1):
  l = A[i]
  r = A[i+K-1]
  a = abs(l) + r-l
  b = abs(r) + r-l
  ans = min(ans, min(a,b))
print(ans)
def main():
    n, m = map(int, input().split())
    left = 1
    right = n
    is_shift = False
    ans = []
    while left < right:
        if right - left <= n // 2 and not is_shift:
            left += 1
        ans.append([left, right])
        left += 1
        right -= 1

    print(f"{ans = }")
    for l in range(m):
        print(*ans[l])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    left = 1
    right = n
    is_shift = False
    ans = []
    while left < right:
        if right - left <= n // 2 and not is_shift and n % 2 == 0:
            left += 1
            is_shift = True
        ans.append([left, right])
        left += 1
        right -= 1

    for l in range(m):
        print(*ans[l])


if __name__ == "__main__":
    main()
s = int(input())
w = int(input())
if ( w >= s ):
	print("unsafe")
else:
	print("safe")

### FIXED CODE ###

s, w = map(int, input().split())
if ( w >= s ):
    print("unsafe")
else:
    print("safe")
import sys
n = int( sys.stdin.readline( ) )
A = [ int( val ) for val in sys.stdin.readline( ).split( ' ' ) ]
q = int( sys.stdin.readline( ) )
z = [ int( val ) for val in sys.stdin.readline( ).split( ' ' ) ]
for i in range( 0, q ):
	print( "yes" )

### FIXED CODE ###

def solve( p, t ):
	global isExist, n, A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( input() )
A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int( input() )
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )
n,k = map(int,input().split())
D = list(map(int,input().split()))
while True:
  dis = False
  for d in D:
    if d in str(n):
      dis = True
      break
  if not dis:
    break
  n += 1
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
D = list(map(int,input().split()))
while True:
  dis = False
  for d in D:
    if str(d) in str(n):
      dis = True
      break
  if not dis:
    break
  n += 1
print(n)
S,T = str(stdin.readline().rstrip()).lower()
S = S[::-1]
if S == T:
  print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input().lower()
T = input().lower()
for i in range(len(S)):
  S = S[len(S)-1:len(S)] + S[0:len(S)-1]
  if S == T:
    break
if S == T:
  print("Yes")
else:
  print("No")
# ABC122A - Double Helix
# a-t, c-g
data = {'a': 't', 't': 'a', 'c': 'g', 'g': 'c'}

print(data[input()])

### FIXED CODE ###

# ABC122A - Double Helix
# a-t, c-g
data = {"A": "T", "T": "A", "C": "G", "G": "C"}

print(data[input()])
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

A = [0 for _ in range(N)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
answer = [[] for _ in range(N)]

for a, b in AB:
  friend[a-1].append(b)
  friend[b-1].append(a)

for c, d in CD:
  block[c-1].append(d)
  block[d-1].append(c)

def search(root, fs, check):
  for f in fs:
    if check[f-1] != 0 or f == root:
      continue
    else:
      check[f-1] = 1
    search(root, friend[f-1], check)
    if f not in block[root-1] and f not in friend[root-1] and f != root:
      if f not in answer[root-1]:
        answer[root-1].append(f)

for i in range(N):
  search(i+1, friend[i], [0 for _ in range(N)])

for i in range(N):
  A[i] = len(answer[i])

print(' '.join(map(str, A)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

par = [n+1 for n in range(N)]
rank = [0 for _ in range(N)]
size = [1 for _ in range(N)]

# 木の根を求める
def find(x):
  if par[x-1] != x:
    par[x-1] = find(par[x-1])
  return par[x-1]
# x, y の属する集合を併合
def unite(x, y):
  rx = find(x)
  ry = find(y)
  if rx == ry:
    return
  if rank[rx-1] < rank[ry-1]:
    rx, ry = ry, rx
  par[ry-1] = rx
  size[rx-1] += size[ry-1]
  if rank[rx-1] == rank[ry-1]:
    rank[rx-1] += 1
# x, y が同じ集合に属するか否か
def same(x, y):
  return find(x) == find(y)
def getsize(x):
  return size[find(x)-1]

friends = [0 for _ in range(N)]
for A, B in AB:
  unite(A, B)
  friends[A-1] += 1
  friends[B-1] += 1

ans = [0 for _ in range(N)]

for n in range(N):
  ans[n] = getsize(n+1) - friends[n] -1

for C, D in CD:
  if same(C, D):
    ans[C-1] -= 1
    ans[D-1] -= 1
print(' '.join(map(str, ans)))
while True:
    r, c = input(),input()
    if not r: break
    print "yes" if not r*c%2 else "no"

### FIXED CODE ###

while 1:
    r,c=map(int,raw_input().split())
    if r==0:break
    print "yes" if r*c%2==0 else "no"
from math import factorial
from operator import mul
from functools import reduce
from math import sqrt

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1+sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
broken.sort()
broken += [0] * (n-m)
index = 0
mod = 10**9 + 7
for i in range(1,n+1):
  if i==1:
    if i != broken[index]:
      a=1
      b=1
    else:
      a=1
      b=0
      index += 1
  else:
    if i == broken[index]:
      a,b=b,0
      index += 1
    else:
      a,b=b,(a+b)%mod
print(b)
n=int(input())
lista=list(map(int,input().split()))
count=0
for a in lista:
  count+=1/a
print(i/count)

### FIXED CODE ###

n=int(input())
lista=list(map(int,input().split()))
count=0
for a in lista:
  count+=1/a
print(1/count)
sys.setrecursionlimit(200000000000)
t=input()
x=0
tl=list(t)
while x != -1:
    x=t.find("?")
    if tl[x+1]=="D":
        tl[x]="P"
    elif tl[x+1]=="?":
        tl[x]="P"
    else:
        tl[x]="D"
    t="".join(tl)
    x=t.find("?")
print(t)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
t=input()
tl=list(t)
tln=len(t)
x=0
for x in range(tln):
    if tl[x] == "?":
        if x == tln-1:
            tl[x]="D"
            break
        elif x==0:
            if tl[x+1]=="?":
                tl[x]="P"
                tl[x+1]="D"
            else:
                tl[x]="D"
        elif tl[x-1]=="P":
            tl[x]="D"
        elif tl[x+1]=="?":
            tl[x]="P"
            tl[x+1]="D"
        elif tl[x+1]=="D":
            tl[x]="P"
        else:
            tl[x]="D"
t="".join(tl)
print(t)
import math
a,b,c,d=map(int,input().split())
x=c*d//math.gcd(c,d)
print(b-~-a-(b//c-~-a//c)-(b//d-~-a//d)+b//x-~-a//x)

### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
x=c*d//fractions.gcd(c,d)
print(b-~-a-(b//c-~-a//c)-(b//d-~-a//d)+b//x-~-a//x)
a = sorted([int(x) for x in input().split()])
print(sum[:2])

### FIXED CODE ###

a = sorted([int(x) for x in input().split()])
print(sum(a[:2]))
def resolve():
    a,b,k=map(int, input().split())
    turn=0
    for i in range(k):
        if turn==0:
            if a%2!=0:
                a-=1
            b+=a//2
            a=a//2
            turn=1
        else:
            if b%2!=0:
                b-=1
            a+=b//2
            b=b//2
            turn=0
    print(a,b)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    s=input()
    if len(s)==2:
        print(s)
    else:
        print(s[2]+s[1]+s[0])
resolve()
def up(x):
	return x+10*(x%10!=0)-x%10



A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())

l=[A,B,C,D,E]

m=np.array([i%10+10*(i%10==0) for i in l])
a=np.argmin(m)
out=0
for i in range(5):
	if(i==a):
		out+=l[i]
	else:
		out+=up(l[i])	

print(out)

### FIXED CODE ###

import numpy as np







def up(x):
	return x+10*(x%10!=0)-x%10



A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())

l=[A,B,C,D,E]

m=np.array([i%10+10*(i%10==0) for i in l])
a=np.argmin(m)
out=0
for i in range(5):
	if(i==a):
		out+=l[i]
	else:
		out+=up(l[i])	

print(out)
import heapq as hp

n,m =[int(i) for i in input().split()]
lists = [[] for i in range(m)]

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  if len(h)>0:
    ans -= hp.heappop(h)
print(ans)
  

### FIXED CODE ###

import heapq as hp

n,m =[int(i) for i in input().split()]
lists = [[] for i in range(m)]

for _ in range(n):
  a,b = [int(i) for i in input().split()]
  if a<=m:
  	lists[a-1].append(b)
  
h = []
ans = 0
for day in range(m):
  for v in lists[day]:
    hp.heappush(h, -v)
  if len(h)>0:
    ans -= hp.heappop(h)
print(ans)
n=input()
a=[]
m=[]

for i in range(int(n)):
    a.append(input())
for i in range(int(n)):
    c=0
    for j in range(int(n)):
        if(a[i]>a[j]):
            c+=1
        else:
            break
    m.append(c)

print(max(m)) 

### FIXED CODE ###

n = int(input())

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

x = 0
y = 0

for i in range(1, n):
    if(a[i] <= a[i-1]):
        y +=1
    else:
        x = max(x,y)
        y = 0

print(max(x,y))
a,b,c = map(int,input().split())
l =[]
for i in range(1,max(a,b)):
  if max(a,b)%i==0:
    l.append(i)

print(l[c-1])



### FIXED CODE ###

a,b,c = map(int,input().split())
l,x,y = [],min(a,b),max(a,b)
for i in range(1,x+1):
  if x%i==0 and y%i==0: 
    l.append(i)
l = l[::-1]
#print(l)
print(l[c-1])
a,b=map(int,input().split())
if a%2 != b%2:
	print('IMPOSSIBLE')
else:
	int k=(a+b)/2
	print(k)

### FIXED CODE ###

a,b=map(int,input().split())
if a%2 != b%2:
	print("IMPOSSIBLE")
else:
	k=(a+b)//2
	print(k)
W, H, x, y = [int(i) for i in input().split()] 

if W/x == 2 and H/y == 2:
    print(W*H/2, 1)
else:
    print(W*H/2, 0)

### FIXED CODE ###

W, H, x, y = [int(i) for i in input().split()] 

if W/2 == x and H/2 == y:
    print(W*H/2, 1)
else:
    print(W*H/2, 0)
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
INL=list(map(float, LS()))
DP=[0.0]*(N+1)
DP[0]=1.0

for p in INL:
    for i in reversed(range(N)):
        DP[i+1] = DP[i+1]*(1.0-p) + DP[i]*p

# print(DP)
print(sum(DP[N//2+1]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
INL=list(map(float, LS()))
DP=[0.0]*(N+1)
DP[0]=1.0

for p in INL:
    for i in reversed(range(N)):
        DP[i+1] = DP[i+1]*(1.0-p) + DP[i]*p

# print(DP)
print(DP[N//2+1])
n,x=map(int,input().split())
X=[0,1,2,3,3]
a=0
print
if n==1:
  print(0)
if n >1:
  if x %2 ==0:
    tmp=int(x/2**(n-1))
    if tmp>=len(X):
      print((X[tmp-1]+1)*(2**(n-1))-1)
    else:
      print(X[tmp]*(2**(n-1))-1)
  else:
    tmp=int(x/2**(n-1))
    print(X[tmp]*(2**(n-1))+1)

### 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,x))
vn = int(input())
cnt = 1
seven = 7

while cnt<n:
  if seven==0:
    print(cnt)
    exit()
  seven = (seven*10+7)%n
  cnt += 1
print(-1)

### FIXED CODE ###

k = int(input())

if k%2==0 or k%5==0:
  print(-1)
  exit()

mod = 7
cnt = 1
while True:
  if mod%k==0:
    print(cnt)
    exit()
    
  mod *= 10
  mod += 7
  cnt += 1
  mod %= k
n,k=map(int,input().split())
a=list(map(int,input().split()))
if k>max(a):
    print("IMPOSSIBLE")
    exit()
    
sa=float("inf")
a.sort()
b=[abs(a[0]-k)]
for i in range(1,n):
    sa=min(sa,abs(a[i]-a[i-1]))
    b.append(abs(a[i]-k))
f=0
for i in range(n):
    if b[i]%sa==0:
        f=1
print("POSSIBLE" if f else "IMPOSSIBLE")


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

if n==1:
    if k==a[0]:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    exit()
g=gcd(a[0],a[1])
for i in range(2,n):
    g=gcd(g,a[i])
if k%g==0 and k<=max(a):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
A, B = map(int, input().split())

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

num = gcd(A, B)

if num < 2:
    print(1)
    quit()

length = int(num ** 0.5) + 2
isPrime = [True for i in range(length)]
isPrime[2] = True
for i in range(2, length):
    if isPrime[i]:
        for j in range(2 * i, length, i):
            isPrime[j] = False

count = 1

cur = 2
while num != 1:
    if isPrime[cur] and num % cur == 0:
        while num % cur == 0:
            num //= cur
        count += 1
    cur += 1

print(count)


### FIXED CODE ###

A, B = map(int, input().split())

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

num = gcd(A, B)

if num < 2:
    print(1)
    quit()

length = int(num ** 0.5) + 2
isPrime = [True for i in range(length)]
isPrime[2] = True
for i in range(2, length):
    if isPrime[i]:
        for j in range(2 * i, length, i):
            isPrime[j] = False

count = 1

cur = 2
while num != 1 and cur < length:
    if isPrime[cur] and num % cur == 0:
        while num % cur == 0:
            num //= cur
        count += 1
    cur += 1

print(count + (num != 1))
A = int(input())
print(a + a**2 + a ** 3)

### FIXED CODE ###

a = int(input())
print(a + a**2 + a ** 3)
x=input()
xx=x.split()
A=xx[0]
P=xx[1]
a=(A*3+P)/2
print(a)

### FIXED CODE ###

x=input()
xx=x.split()
A=int(xx[0])
P=int(xx[1])
a=(A*3+P)/2
print(int(a))
def Fib(n):    
    if n == 2 or n == 3:
        return 1
    else:
        return Fib(n - 1) + Fib(n - 2)
    
N, M = map(int, input().split())
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *= Fib(x)
print(num % 1000000007)

### FIXED CODE ###

def fib(n):
    if n <= 1:
        return n
    result = [1, 0, 0, 1]
    matrix = [1, 1, 1, 0]
    while n > 0:
        if n % 2:
            result = mul(matrix, result)
        matrix = mul(matrix, matrix)
        n //= 2
    return result[2]

def mul(a, b):
    return [a[0]*b[0] + a[1]*b[2],
            a[0]*b[1] + a[1]*b[3],
            a[2]*b[0] + a[3]*b[2],
            a[2]*b[1] + a[3]*b[3]]
    
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
S = [-1]
for i in range(M):
    S.append(int(input()))
S.append(N + 1)
S = [S[i + 1] - S[i] for i in range(M + 1)]
if any([x == 1 for x in S]):
    print(0)
    exit()
num = 1
for x in S:
    num *=  fib(x - 1)
    num = num % 1000000007
print(num)
from math import cos, sin, sqrt, radians
short = int(input())
long = int(input())
hour = int(input())
minit = int(input())

short_kaku = 90 - (30 * hour + 0.5 * minit)
short_x = short * cos(radians(short_kaku))
short_y = short * sin(radians(short_kaku))

long_kaku = 90 - 6 * minit
long_x = long * cos(radians(long_kaku))
long_y = long * sin(radians(long_kaku))

distance = sqrt((short_x - long_x) ** 2 + (short_y - long_y) ** 2)

print('{:.20f}'.format(distance))

### FIXED CODE ###

from math import cos, sin, sqrt, radians
short, long, hour,minit = map(int,input().split())

short_kaku = 90 - (30 * hour + 0.5 * minit)
short_x = short * cos(radians(short_kaku))
short_y = short * sin(radians(short_kaku))

long_kaku = 90 - 6 * minit
long_x = long * cos(radians(long_kaku))
long_y = long * sin(radians(long_kaku))

distance = sqrt((short_x - long_x) ** 2 + (short_y - long_y) ** 2)

print(distance)
#43 ABC134D
n=int(input())
a=list(map(int,input().split()))
x=[0 for _ in range(n)]
for i in range(n,0,-1):
	x[i-1]=sum([a[j] for j in range(i-1,n,i)])%2
j=True
for i in range(a):
	if a[i]!=sum([a[j] for j in range(i,n,i+1)])%2:
		j=False
if j:
	print(sum(x))
	if sum(x)!=0:
		res=[]
		for i,t in enumerate(x):
			if t==1:
				res.append(str(i+1))
		print(" ".join(res))
else:
	print(-1)

### FIXED CODE ###

#43 ABC134D
n=int(input())
a=list(map(int,input().split()))
x=[0 for _ in range(n)]
for i in range(n,0,-1):
	x[i-1]=1 if a[i-1]!=sum([x[j] for j in range(i-1,n,i)])%2 else 0
#print(x)
j=True
for i in range(n):
	if a[i]!=sum([x[j] for j in range(i,n,i+1)])%2:
		j=False
if j:
	print(sum(x))
	if sum(x)!=0:
		res=[]
		for i,t in enumerate(x):
			if t==1:
				res.append(str(i+1))
		print(" ".join(res))
else:
	print(-1)
import math
import sympy
#from sympy import sieve

N = int(input())
'''
lenN = math.floor(math.log(N,10)) + 1
# lenN = Nの桁数
rootN = math.floor(math.sqrt(N))
#rootN = floor( N ^ 1/2 )
Primes = list(sieve.primerange(1,rootN))
'''

Divisors = list(sympy.divisors(N))
Len_d = len(Divisors)

Ans = Divisors[ Len_d // 2 ]
print(math.floor(math.log(Ans,10))+1)

### FIXED CODE ###

import math

def make_divisors(n):
    lo_d , up_d = [] , []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lo_d.append(i)
            if i != n // i:
                up_d.append( n // i )
        i += 1
    return lo_d + up_d[::-1]

N = int(input())
List = make_divisors(N)
len_a = len(List)
ans = List[ len_a // 2 ]
print( math.floor(math.log(ans , 10)) + 1 )