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

mod = 10**9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm-1)
inv = [1] * (nm-1)
inv_fact = [1] * (nm-1)
for i in range(2, nm-1):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(mod // i) * inv[mod % i] % mod
  inv_fact[i] = inv_fact[i-1] * inv[i]
comb = fact[nm-2] * inv_fact[k-2] * inv_fact[nm-k] % mod
cost_x = (n-1) * n * (n+1) // 6 * m * m % mod
cost_y = (m-1) * m * (m+1) // 6 * n * n % mod
print(comb * (cost_x + cost_y) % mod)

### FIXED CODE ###

mod = 10**9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm-1)
inv = [1] * (nm-1)
inv_fact = [1] * (nm-1)
for i in range(2, nm-1):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(mod // i) * inv[mod % i] % mod
  inv_fact[i] = inv_fact[i-1] * inv[i] % mod
comb = fact[nm-2] * inv_fact[k-2] * inv_fact[nm-k] % mod
cost_x = (n-1) * nm * (n+1) // 6 * m % mod
cost_y = (m-1) * nm * (m+1) // 6 * n % mod
print(comb * (cost_x + cost_y) % mod)
### BUGGY CODE ###

from fractions import gcd
mod = pow(10, 9)+7
def main():
  n = int(input())
  A = list(map(int, input().split()))
  m = A[0]
  for i in range(1, n):
    m = m // gcd(m, A[i]) * A[i]
  ans = 0
  for i in A:
    ans += m//i
  print(ans%mod)
if __name__ == "__main__":
  main()

### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1


ans = 0
for i in range(h):
    maze[i] = input()

INF = h*w
distance = [[INF for i in range(w)] for j in range(h)]

queue0 = deque()
queue0.append((ch,cw))
distance[ch][cw] = 0

queue1 = deque()

while queue0 or queue1:

    if queue0:
        y, x = queue0.popleft()
    elif queue1:
        y, x = queue1.popleft()

    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if dy == dx == 0: continue
            elif abs(dy) + abs(dx) == 1:
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x]:
                            queue0.append((ny, nx))
                            distance[ny][nx] = distance[y][x]
            else:
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x]+1:
                            queue1.append((ny, nx))
                            distance[ny][nx] = distance[y][x]+1


ans = distance[dh][dw]
if ans == INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1


ans = 0
for i in range(h):
    maze[i] = input()

INF = h*w
distance = [[INF for i in range(w)] for j in range(h)]

queue0 = deque()
queue0.append((ch,cw))
distance[ch][cw] = 0

queue1 = deque()

while queue0 or queue1:

    if queue0:
        y, x = queue0.popleft()
    elif queue1:
        y, x = queue1.popleft()

    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if dy == dx == 0: continue
            elif abs(dy) + abs(dx) == 1:
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x]:
                            queue0.append((ny, nx))
                            distance[ny][nx] = distance[y][x]
            else:
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x]+1:
                            queue1.append((ny, nx))
                            distance[ny][nx] = distance[y][x]+1


ans = distance[dh][dw]
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    visited.append(next_p)
                    new_queue.append(next_p)
    queue = new_queue
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)
### BUGGY CODE ###

N = int(input())
l = [-1] * N

print(v1)
s = input()
if s=="Male":
    l[v1] = 0
elif s=="Female":
    l[v1] = 1
else:
    exit()

print(v2)
s = input()
if s=="Male":
    l[v2] = 0
elif s=="Female":
    l[v2] = 1
else:
    exit()

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit()

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left+1, m-1
    else:
        left, right = m+1, right-1


### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    pN = list(map(int, input().split()))

    ans = 0
    for i in range(N + 1 - K):
        ans = max(ans, sum(map(lambda x: 1 + x, pN[i:i + K])) / 2)

    print(ans)


main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())

    pN_ = []

    ans = 0
    total = 0
    for i, s in enumerate(input().split()):
        total += 1 + int(s)
        pN_.append(total)

        if i == K - 1:
            ans = max(ans, (total / 2))
        elif K <= i:
            ans = max(ans, (total - pN_[i - K]) / 2)

    print(ans)


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Dec 20 12:35:48 2017

"""
 
from collections import Counter

NKList = list(map(int,input().split()))
N = NKList[0]
K = NKList[1]

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

countDict = Counter(AList)
soretedList = sorted(countDict.items(),key=lambda x:x[1])

rewrite = 0

while len(soretedList) > K:
    head = soretedList.pop(0)
    rewrite += head[1]

print(rewrite)

    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Dec 20 12:35:48 2017

"""
 
from collections import Counter

NKList = list(map(int,input().split()))
N = NKList[0]
K = NKList[1]

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

countDict = Counter(AList)
soretedList = sorted(countDict.values())

l = len(soretedList)

if len(soretedList) <= K :
    print(0)
else:
    print(N - sum(soretedList[l-K:] ))
### BUGGY CODE ###

s = input()
qn = int(input())
q = []
rev = False

for i in range(qn):
    qi = input().split()
    if qi[0] == "1":
        rev = not rev
    else:
        if rev:
            if qi[1] == "1":
                qi[1] = "2"
            else:
                qi[1] = "1"
        q.append((2, (int(qi[1]), qi[2])))
if rev:
    q.append((1, ()))
for i in range(len(q)):
    if q[i][0] == 1:
        s = s[::-1]
    if q[i][0] == 2:
        if q[i][1][0] == 1:
            s = q[i][1][1] + s
        else:
            s = s + q[i][1][1]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
qn = int(input())
q = []
rev = False

for i in range(qn):
    qi = input().split()
    if qi[0] == "1":
        rev = not rev
    else:
        if rev:
            if qi[1] == "1":
                qi[1] = "2"
            else:
                qi[1] = "1"
        q.append((2, int(qi[1]), qi[2]))
for i in range(len(q)):
    if q[i][0] == 2:
        if q[i][1] == 1:
            s.appendleft(q[i][2])
        else:
            s.append(q[i][2])
if rev:
    s = list(s)[::-1]
print("".join(s))
### BUGGY CODE ###

slist = input()
tlist = input()
scounter = 0
slength=len(slist)
for tchar in tlist:
    Sstart=scounter%slength
    while True:
        # print(tchar,slist[scounter%slength],scounter)
        if tchar == slist[scounter%slength]:
            scounter += 1
            break
        scounter += 1
        if scounter%slength==Sstart:
            scounter=-1
            break
    if scounter==-1:
        break
print(scounter)

### FIXED CODE ###

slist = input()
tlist = input()
scounter = 0
slength=len(slist)
slist=slist+slist
preposition=-1
for tchar in tlist:
    preposition=slist.find(tchar, preposition+1)
    if preposition==-1:
        scounter=-1
        break
    elif preposition>=slength:
        scounter+=slength
        preposition-=slength
    # print(tchar, scounter, preposition)
if (scounter==-1):
    print(scounter)
else:
    print(scounter+preposition+1)
### BUGGY CODE ###

n=int(input())
s=input()
a = [str(c) for c in s]
ans=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if (k-j)==(j-i):
                continue
            elif a[i]!=a[j] and a[j]!=a[k] and a[k]!=a[i]:
                ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
a = [str(c) for c in s]
ans=0
r=0
g=0
b=0
er=0
for i in range(n):
    if a[i]=='R':
        r+=1
        ans=ans+g*b
    elif a[i]=='G':
        g+=1
        ans=ans+r*b
    else:
        b+=1
        ans=ans+g*r
for i in range(n-1):
    for j in range(i+1,n):
        k=j+(j-i)
        if k<n:
            if a[i]!=a[j] and a[j]!=a[k] and a[k]!=a[i]:
                er+=1
print(ans-er)
### BUGGY CODE ###

n=int(input())
li=[]
num=0
for i in range(n):
    x=input()
    if x not in li:
        li.append(x)
        num+=1
print(num)

### FIXED CODE ###

n=int(input())
li=[]
num=0
for i in range(n):
    li.append(input())
se=set(li)
lis=list(se)
print(len(lis))
### BUGGY CODE ###

#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = pow(2, n, mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X *= (n-i+1)
    for j in range(1, k+1):
        Y *= j
    result = X * (pow(Y, mod-2, mod))
    return result

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)

### FIXED CODE ###

#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = pow(2, n, mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)
### BUGGY CODE ###

N,Q = map(int,input().split(" "))
A = [[0,1,0]]
B = []
for i in range(N-1):
    A.append(list(map(int,input().split(" "))))
    A[i+1].append(0)
for j in range(Q):
    B.append(list(map(int,input().split(" "))))

for j in range(Q):
    tmp=[]
    for i in range(N):
        if A[i][1]==B[j][0] or A[i][0]==B[j][0] or A[i][0] in tmp:
            A[i][2]+=B[j][1]
            tmp.append(A[i][1])


for i in range(N):
    print(A[i][2],end=" ")


### FIXED CODE ###

N,Q = map(int,input().split(" "))
A = [0]*N

B = [0 for j in range(N)]
for i in range(N-1):
    a,b = map(int,input().split(" "))
    A[b-1] = a-1
    
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(1,N):
        B[i] += B[A[i]]
for i in range(N):
        print(B[i],end=" ")
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
ans = 0

for i in range(60):
    x = 0
    for j in range(N):
        if (A[j] >> i) & 1:
            x += 1
    buff = x * (N - x) % mod
    for j in range(i):
        buff = buff * 2 % mod
    ans += buff
    ans %= mod

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0
ni = 1

for i in range(60):
    x = sum([1 for j in range(N) if (A[j] >> i) & 1])
    buff = x * (N - x) * ni
    ans += buff
    ni = ni * 2

print(ans % mod)
### BUGGY CODE ###

import itertools

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

P = N-1
count = 0
for path in itertools.permutations(ab, P):
  flag = True
  prev = 1
  memo = [0]*N
  for i in range(P):
    memo[prev-1] += 1
    if flag == True:
      if path[i][0] == prev:
        prev = path[i][1]
      elif path[i][1] == prev:
        prev = path[i][0]
      else:
        flag = False
        continue
      if 0 < memo[prev-1]:
        flag = False
        continue
      if i == P-1:
        count += 1
        
print(count)


### FIXED CODE ###

import itertools

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

count = 0
for path in itertools.permutations([i for i in range(2, N+1)], N-1):
  flag = True
  if [1, path[0]] in ab or [path[0], 1] in ab:
    pass
  else:
    flag = False
    continue
  for i in range(1, N):
    if flag:
      if i == N-1:
        count += 1
        continue
      if [path[i-1], path[i]] in ab or [path[i], path[i-1]] in ab:
        continue
      else:
        flag = False
print(count)
### BUGGY CODE ###

S = list("xxx"+input()+"xxx")
N = len(S)

ans = 0
b = 0
while b<N:
    if S[b]=="A" and "".join(S[b:b+3])=="ABC":
        S[b]="B"
        S[b+1]="C"
        S[b+2]="A"
        b-=3
        ans+=1
    b+=1
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
X = []
x = 0
while x<N-1:
    if S[x]=="B" and S[x+1]=="C":
        X.append("D")
        x+=1
    else:
        X.append(S[x])
    x+=1
ans = 0
N = len(X)
a = 0
for i in range(N):
    if X[i]=="A":
        a+=1
    elif X[i]=="D":
        ans+=a
    else:
        a=0
print(ans)
### BUGGY CODE ###

K = int(input())

import fractions

A = []
sum = 0

for i in range(K):
    for j in range(K):
        A.append(fractions.gcd(i+1,j+1))

for g in A:
    for i in range(K):
        sum += fractions.gcd(g,i+1)

print(sum)


### FIXED CODE ###

K = int(input())

import fractions

A = {}
sum = 0

for i in range(K):
    for j in range(K):
        if fractions.gcd(i+1,j+1) in A:
            A[fractions.gcd(i+1,j+1)] += 1
        else:
            A[fractions.gcd(i+1,j+1)] = 1

for key in A:
    for i in range(K):
        sum += fractions.gcd(key,i+1)*A[key]

print(sum)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A = sorted(A)
F = sorted(F, reverse=True)
mul = [A[i]*F[i] for i in range(N)]
for k in range(K):
    idx = mul.index(max(mul))
    if mul[idx] == 0:
        break
    mul[idx] -= F[idx]
print(max(mul))


### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A = sorted(A)
F = sorted(F, reverse=True)
mul = [A[i]*F[i] for i in range(N)]

if K >= sum(A):
    print(0)
    exit()

ma = 2**40
mi = 0
while 1:
    tgt = mi + (ma - mi)//2
    num = 0
    for i in range(N):
        tmp = (mul[i] - tgt + F[i] - 1) // F[i]
        if tmp <= 0:
            continue
        num += tmp
    if ma == mi:
        print(ma)
        exit()
    if num <= K:
        ma = mi + (ma - mi)//2
    else:
        mi = mi + (ma - mi)//2+1
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
kind=[]
count=1
for i in range(len(a)-1):
  if(a[i]==a[i+1]):count+=1
  else:
    kind.append(count)
    count=1
kind.append(count)
kind.sort()
change=0
while(len(kind)>k):
  change+=kind.pop(0)
print(change)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
kind=[]
count=1
for i in range(len(a)-1):
  if(a[i]==a[i+1]):count+=1
  else:
    kind.append(count)
    count=1
kind.append(count)
kind.sort()
change=0
for i in range(k):
  if(len(kind)!=0):change+=kind.pop()
print(n-change)
### BUGGY CODE ###

n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 # lap count
    lap_sc = 0 # lap score
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    lap_sc = max(0, lap_sc)
    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break
        sum_sc += C[nx]
        score = sum_sc + lap_sc * ((k - kc) // lc)
        max_score = max(max_score, score)
        nx = P[nx]
        if nx == st: break

print(max_score)


### FIXED CODE ###

n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 # lap count
    lap_sc = 0 # lap score
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break

        sum_sc += C[nx]
        score = sum_sc + max(0, lap_sc) * ((k - kc) // lc)
        max_score = max(max_score, score)

        nx = P[nx]
        if nx == st: break

print(max_score)

# print('===')
# print(n,k)
# print(P)
# print(C,end='\n\n')
### BUGGY CODE ###

import numpy as np

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

ret = 0
p = np.array(p)
for i in range(len(p)):
    if (p[:i] > p[i]).all():
        ret +=1
print(ret)      

### FIXED CODE ###

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

ret = 0
c_min = 2e5

for i in p:
    if c_min >= i:
        c_min = i
        ret+=1
print(ret)
### BUGGY CODE ###

N = 13
S = "strangeorange"

#N = int(input())
#S = str(input())

N = int(input())
S = str(input())
#N = 13
#S = "strangeorange"
 
lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = []
    for i in range(N - 2*mid + 1):
        if not (S[i:mid+i] in s):
            s.append(S[i:mid+i])
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

### FIXED CODE ###

N = int(input())
S = str(input())
#N = 13
#S = "strangeorange"

lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = set()
    for i in range(N - 2*mid + 1):
        s.add(S[i:mid+i])
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)
### BUGGY CODE ###

import sys

def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v

# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))

# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]

# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))

# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])

# 3 output cnt
print(cnt)
# 4 output sorted a
for i in range(n):
    print(a[i])

### FIXED CODE ###

import sys
 
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
 
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
 
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
 
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
 
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
 
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))
### BUGGY CODE ###

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

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                cnt += 1

print(cnt)


### FIXED CODE ###

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

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        if (S-x-y) in range(K+1):
            cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
for i in range(n):
  x = a[:i] + a[i+1:]
  print(max(x))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
x = a.index(max(a))
a0 = sorted(a)
for i in range(n):
  if i != x:
    print(a0[n-1])
  else:
    y = a[:x] + a[x+1:]
    print(max(y))
### BUGGY CODE ###

import sys
x = int(input())
result = [1,1]
for i in range(10**8+1):
    for j in range(10**8+1):
        if x == pow(i, 5)+pow(j, 5):
            result = [i, -j]
            print(*result)
            sys.exit()
print(*result)

### FIXED CODE ###

import sys
x = int(input())
result = [1,1]
for i in range(-1000,1000):
    for j in range(-1000,1000):
        if x == pow(i, 5)-pow(j, 5):
            result = [i, j]
            print(*result)
            sys.exit()
print(*result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache


n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
mod = 10**9+7
memo={}
memo[1]=1
memo[0]=1

@lru_cache(maxsize=10000000)
def fib(n):
  if n in A:
  	memo[n]=0
  	return 0
  if n not in memo:
    memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

print(fib(n)%mod)

### FIXED CODE ###

n,m=map(int,input().split())
A = [int(input()) for i in range(m)]
ls =[-1]*(n+1)
ls[0]=ls[1]=1
mod = 10**9+7
for a in A:
	ls[a]= 0

for i in range(2,n+1):
	if ls[i]==-1:
		ls[i]= ls[i-1]+ls[i-2]
print(ls[-1]%mod)