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

import sys
import math

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def factorize(n):
    b = 2
    fct = set()
    while b ** 2 <= n:
        while n % b == 0:
            n //= b
            fct.add(b)
        b += 1
    if n > 1:
        fct.add(n)
    return fct


def main():

    N = in_n()
    A = sorted(in_nl())

    M = 10**6 + 1
    ok = [True] * M

    pf = True
    for i in range(N):
        prime = factorize(A[i])
        for p in prime:
            if not ok[p]:
                pf = False
                break
            else:
                ok[p] = False

    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])

    if pf:
        ans = "pairwise coprime"
    else:
        if g == 1:
            ans = "setwise coprime"
        else:
            ans = "not coprime"

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


# 素因数分解（複数回）
class Factorize(object):

    def __init__(self, maxnum):
        self.primes = self.__smallest_prime_factors(maxnum)

    # 素因数分解 O(logN)
    def factorize(self, n):
        fct = defaultdict(lambda: 0)
        while n != 1:
            fct[self.primes[n]] += 1
            n //= self.primes[n]
        return fct

    # n以下の最小の素因数を列挙する O(NlogN)
    def __smallest_prime_factors(self, n):

        prime = list(range(n + 1))

        for i in range(2, int(n**0.5) + 1):
            if prime[i] != i:
                continue
            for j in range(i * 2, n + 1, i):
                prime[j] = min(prime[j], i)
        return prime


def main():

    N = in_n()
    A = sorted(in_nl())

    M = 10**6 + 1
    ok = [True] * M

    fct = Factorize(M)

    pf = True
    for i in range(N):
        prime = fct.factorize(A[i])
        for p in prime.keys():
            if not ok[p]:
                pf = False
                break
            else:
                ok[p] = False

    g = A[0]
    for i in range(1, N):
        g = math.gcd(g, A[i])

    if pf:
        ans = "pairwise coprime"
    else:
        if g == 1:
            ans = "setwise coprime"
        else:
            ans = "not coprime"

    print(ans)


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

#!/usr/bin/env python3

# from numba import njit
import sys
sys.setrecursionlimit(10**9)
# input = stdin.readline

INF = 10**9

# @njit
def solve(n):
  def dp(i,x,acc=[]):
    # i番目までで和をちょうどxにできるか
    if i == 0:
      if x == 0:
        return acc
      else:
        return [INF]
    else:
      return min(dp(i-1,x-i,[i]+acc),dp(i-1,x,acc),key=lambda x: x[-1])
  

  return dp(n,n)



def main():
  N = int(input())
  # N,M = map(int,input().split())
  # a = list(map(int,input().split()))
  print(*solve(N),sep="\n")
  return

if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python3

# from numba import njit
import sys
sys.setrecursionlimit(10**9)
# input = stdin.readline

INF = 10**9

# @njit
def solve(n):
  s = 0
  l = []
  for i in range(n):
    s += i+1
    l += [i+1]
    if s > n:
      l.remove(s-n)
      return l
    elif s == n:
      return l

  return -1



def main():
  N = int(input())
  # N,M = map(int,input().split())
  # a = list(map(int,input().split()))
  print(*solve(N),sep="\n")
  return

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

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
sys.setrecursionlimit(int(1e+7))  # スタック上限

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    XY = ii2nnn(N)
    M = int(1e+5) + 5

    # 二部グラフ
    to = [[] for _ in range(M*2)]
    cnt = [0] * (M*2)
    visited = [False] * (M*2)

    # 二部グラフを構築
    for x, y in XY:
        y += M
        to[x].append(y)
        to[y].append(x)

    cnt = [0, 0]
    def dfs(i):
        visited[i] = True
        cnt[i // M] += 1
        for j in to[i]:
            if visited[j]:
                continue
            dfs(j)

    # 二部グラフを走査
    ans = 0
    for i in range(M*2):
        if visited[i]:
            continue
        cnt[0] = 0
        cnt[1] = 0
        dfs(i)
        ans += cnt[0] * cnt[1]
    
    ans -= N  # 既にある点は操作数に含まれない
    print(ans)

main()


### FIXED CODE ###

import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
sys.setrecursionlimit(int(1e+7))  # スタック上限

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    XY = ii2nnn(N)
    M = int(1e+5) + 5

    # 二部グラフ
    to = [[] for _ in range(M*2)]
    cnt = [0] * (M*2)
    visited = [False] * (M*2)

    # 二部グラフを構築
    for x, y in XY:
        y += M
        to[x].append(y)
        to[y].append(x)

    cnt = [0, 0]
    def bfs(n):
        q = deque()
        q.append(n)
        while q:
            i = q.popleft()
            if visited[i]:
                continue
            visited[i] = True
            cnt[i // M] += 1
            for j in to[i]:
                q.append(j)

    # 二部グラフを走査
    ans = 0
    for i in range(M*2):
        if visited[i]:
            continue
        cnt[0] = 0
        cnt[1] = 0
        bfs(i)
        ans += cnt[0] * cnt[1]
    
    ans -= N  # 既にある点は操作数に含まれない
    print(ans)

main()
### BUGGY CODE ###


def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	r = []
	for n in a[::-1]:
		if n not in r:
			r.append(n)
	for i in range(m):
		if (i+1) not in r:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

table = [-1] * (m+1)
for i in range(len(r)):
	table[r[i]] = i

for aa in a[::-1]:
	index = table[aa]
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = 0
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')



### FIXED CODE ###


def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split()))

def f(m, a):
	sa = set(a)
	seen = set()
	r = []
	for n in a[::-1]:
		if n not in seen:
			r.append(n)
			seen.add(n)
	for i in range(m):
		if (i+1) not in sa:
			r.append(i+1)
	return r

def isSorted(a):
	for i in range(1, len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n, m = reads()
q = read()
a = reads()

r = f(m, a)
count = [0] * (m+1)
count[0] = n

table = [-1] * (m+1)
for i in range(len(r)):
	table[r[i]] = i

for aa in a[::-1]:
	index = table[aa]
	if 0 < count[index]:
		count[index] -= 1
		count[index+1] += 1

to = m
for i in range(m):
	if 0 < count[i]:
		to = i
		break

if isSorted(r[to:]):
	print('Yes')
else:
	print('No')
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
res=[999999999]*n
res[0]=0
for i in range(1,n):
    mini=999999999
    for j in range(1,k+1):
        if i-j>=0:
            mini=min(abs(h[i-j]-h[i])+res[i-j],mini)
    res[i]=mini

print(res[-1])


### FIXED CODE ###

import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[sys.maxsize]*n
dp[0]=0
for i in range(n):
    for j in range(i+1,i+k+1):
        if j<n:
            dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]))
print(dp[n-1])
### BUGGY CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
for k in range(m):
  s, t = map(int,input().split())
  b = [t]*s
  a.extend(b)
ans = 0
a.sort(reverse=True)
for v in range(n):
  ans += a[v]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [list(map(int,input().split())) for p in [0]*m]
b.sort(key=lambda q: -q[1])
#print(a)
#print(b)

c = 0
for s in b:
	for t in [0]*s[0]:
		#print(s)
		if c + 1 > n:
			break
		if s[1] <= a[c]:
			break
		a[c] = s[1]
		c += 1
		#print(a)
	else:
		continue
	break
print(sum(a))
### BUGGY CODE ###

import collections
import copy
import math
from scipy.misc import comb

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
nums = [ int(s) for s in input().split() ]


for i in range(n):
    ans = 0

    cpl = copy.copy(nums)
    cpl.pop(i)
    ct = collections.Counter(cpl)

    for key, val in ct.items():
        if val > 1:
            ans += comb(val, 2, exact=True)
    
    print(ans)


### FIXED CODE ###




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

# counter
from collections import Counter
cntr = Counter(lst)

# combination
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

total = 0
# countSameNames
for value in cntr.values():
    if value > 1:
        total += combinations_count( value, 2 )


for l in lst:
    print(total - (cntr[l]-1))
### BUGGY CODE ###

from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    # dy = [1,-1,0,0]
    # dx = [0,0,1,-1]
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append([y,x-1])
            if x <w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append([y,x+1])
            if y >0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append([y-1,x])
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append([y+1,x])
            # for i in range(4):
            #     nh = h + dy[i]
            #     nw = w + dx[i]
            #     if (0<=nh<H) and (0<=nw<W):
            #         if field[nh][nw] == False:
            #             field[nh][nw] = True
            #             nqueue.append((nh,nw))
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

def main():
    n, k = map(int, input().split())
    p = list(map(lambda pi: (int(pi) + 1) / 2, input().split()))
    ex = 0
    for i in range(n - k + 1):
        ex = max(ex, sum(p[i:i + k]))
    print(ex)


if __name__ == '__main__':
    main()


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(lambda pi: (int(pi) + 1) / 2, input().split()))
ex = sum(p[:k])
mx = ex
for i in range(n - k):
    ex += p[i + k] - p[i]
    if mx < ex:
        mx = ex
print(mx)
### BUGGY CODE ###

from collections import deque
from functools import reduce
from operator import add

s = deque(list(input()))
q = int(input())

rev_cnt = 0
for i in range(q):
    query = input().split()
    if query[0] == '2':
        if (query[1] == '1' and rev_cnt % 2 == 0) or ((query[1] == '2' and rev_cnt % 2 == 1)):
            s.appendleft(query[2])
        else:
            s.append(query[2])
    else:
        rev_cnt += 1

res = reduce(add, s)
if rev_cnt % 2 == 1:
    res = res[::-1]

print(res)


### FIXED CODE ###

from collections import deque
import sys

input = lambda: sys.stdin.readline().rstrip()

s = deque(list(input()))
q = int(input())

rev_cnt = 0
for i in range(q):
    query = input().split()
    if query[0] == '2':
        if (query[1] == '1' and rev_cnt % 2 == 0) or ((query[1] == '2' and rev_cnt % 2 == 1)):
            s.appendleft(query[2])
        else:
            s.append(query[2])
    else:
        rev_cnt += 1

if rev_cnt % 2 == 1:
    print(''.join([s[len(s) - i - 1] for i in range(len(s))]))
else:
    print(''.join([c for c in s]))
### BUGGY CODE ###

import numpy as np

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

b = [0] * M
c = [0] * M
for i in range(M):
    b[i], c[i] = map(int, input().split())

lst = np.array([c, b]).T.tolist()
lst.sort(reverse=True)
c = np.array(lst).T.tolist()[0]
b = np.array(lst).T.tolist()[1]

judge = 0
for i in range(M):
    for j in range(b[i]):
        if A[j] < c[i]:
            A[j] = c[i]
        else:
            judge = 1
            break
    A.sort()
    if judge == 1:
        break

print(sum(A))

### FIXED CODE ###

import numpy as np

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

b = [0] * M
c = [0] * M
for i in range(M):
    b[i], c[i] = map(int, input().split())

lst = np.array([c, b]).T.tolist()
lst.sort(reverse=True)
c = np.array(lst).T.tolist()[0]
b = np.array(lst).T.tolist()[1]

k = 0
judge = 0
for i in range(M):
    if k+b[i]-1 < N:
        if A[k+b[i]-1] < c[i]:
            A[k:k+b[i]] = [c[i]] * b[i]
            k += b[i]
        else:
            for j in range(b[i]):
                if k < N:
                    if A[k] < c[i]:
                        A[k] = c[i]
                        k += 1
                    else:
                        judge = 1
                        break
            if judge == 1:
                break
    elif k < N:
        for j in range(b[i]):
            if k < N:
                if A[k] < c[i]:
                    A[k] = c[i]
                    k += 1
                else:
                    judge = 1
                    break
        if judge == 1:
            break
    else:
        break

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

n,m=map(int,input().split());a,b=[],[]
for i in range(m):
  aa,bb=map(int,input().split())
  a.append(aa);b.append(bb)
c=[]
for i in range(m):
  if a[i]==1:c.append(b[i])
for i in range(m):
  if b[i]==n:
    if a[i] in c:print("POSSIBLE");exit()
print("IMPOSSIBLE")

### FIXED CODE ###

n,m=map(int,input().split());a=[]
for i in range(m):
  aa,bb=map(int,input().split())
  if aa==1:a.append(bb)
  if bb==n:a.append(aa)
a.sort()
for i in range(len(a)-1):
  if a[i]==a[i+1]:print("POSSIBLE");exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)


### FIXED CODE ###

"""
重さと価値がそれぞれw_i,v_iであるようなn個の品物がある.
これらの品物の中から, 重さの総和がWを超えないように選んだ時の,
価値の総和の最大値を求めよ.
1<=n<=100, 1<=w_i<=10^7, 1<=v_i<=100, 1<=W<=10^9
"""
#-------------------------------------------------------------------------------

#入力
INF=2*10**9
n,W = map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    x,y = map(int, input().split())
    w[i] = x
    v[i] = y
max_v=max(v)
dp = [[INF for i in range(n*max_v+1)] for j in range(n+1)]

#ここからメイン
dp[0][0]=0
for i in range(n):
    for j in range(n*max_v+1):
        if j<v[i]:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])
ans=0
for i in range(n*max_v+1):
    if dp[n][i]<=W:
        ans=i
print(ans)
### BUGGY CODE ###

a,b,c=map(int,input().split())
e=0
f=[[1,1]]
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[12,8,8,5,10,6,9,6,10,5,8,8,12],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
else:
    d=k[b-2]
    for i in range(0,a):
        j=0
        l=len(f)
        while j<l:
            f.append([f[j][0],f[j][1]*d[2*(f[j][0]-1)]])
            if f[j][0]-1>0:
                f.append([f[j][0]-1,f[j][1]*d[1+2*(f[j][0]-2)]])
            if f[j][0]+1<=b:
                f.append([f[j][0]+1,f[j][1]*d[2*(f[j][0]-1)+1]])
            j+=1
        else:
            del f[:l]
    else:
        for i in range(0,len(f)):
            if f[i][0]==c:
                e+=f[i][1]
        print(e%(10**9+7))        

### FIXED CODE ###

a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
elif c-a>=2:
    print(0)    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
    print(s[a][c-1]%(10**9+7))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[0]
for i in range(1,n):
  wk=[]
  for j in range(1,min(i,k)+1):
    wk.append(cost[i-j]+abs(h[i]-h[i-j]))
  cost.append(min(wk))
print(cost[n-1])

### FIXED CODE ###

from numba import jit
n,k=map(int,input().split())
h=list(map(int,input().split()))
@jit
def jitcalc(n,k,h):
  cost=[0]
  for i in range(1,n):
    wk=[]
    for j in range(1,min(k,i)+1):
      wk.append(cost[i-j]+abs(h[i]-h[i-j]))
    cost.append(min(wk))
  print(cost[n-1])
jitcalc(n,k,h)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for x in range(m)]
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1 #0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

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

m = 0
mi = 0

for i in range(N - K + 1):
    s = sum(p[i:i+K])
    if m < s:
        m = s
        mi = i

ans = (m + K) / 2

print(ans)



### FIXED CODE ###

from collections import deque

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

# 累積和
sum_list = [0] * (N + 1)
sum_list[0] = 0
for i in range(1, N+1):
    sum_list[i] = sum_list[i-1] + P[i-1]

max_sum = 0
for i in range(N-K+1):
    s = sum_list[i+K] - sum_list[i]
    if max_sum < s:
        max_sum = s

ans = (max_sum + K) / 2

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

import numpy as np

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort()
a.append([np.inf, np.inf])
job = []
ans = 0
ind = 0
for i in range(1, M+1):
    while a[ind][0] <= i:
        job.append(a[ind][1])
        ind += 1
        if ind == N:
            break
    if job:
        job.sort()
        ans += job.pop(-1)
print(ans)

### FIXED CODE ###

import heapq as hq
import numpy as np

N, M = map(int, input().split())
job = [list(map(int, input().split())) for _ in range(N)]
ans = 0
job.sort()
job.append([np.inf, np.inf])
jobhq = []
index = 0
for day in range(1, M + 1):
    while day >= job[index][0]:
        hq.heappush(jobhq, - job[index][1])
        index += 1
    if jobhq:
        ans += - hq.heappop(jobhq)
print(ans)
### BUGGY CODE ###

n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
b = a[:]
ans = 10**12
for k in range(n):
    for i in range(n):
        b[i] = min(a[i-k],b[i])
    ans = min(ans,k*x+sum(b))
print ans

### FIXED CODE ###

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))
### BUGGY CODE ###

n=int(input())
mod=10**9+7
import math
v=math.factorial(n)
ans=[]
for i in range(1,v+1):
    if v%i==0:
        ans.append(i)
print(len(ans)%mod)

### FIXED CODE ###

n=int(input())
import math
fac=math.factorial(n)
mod=10**9+7
ans=[0]*(n+1)
ans[0]=ans[1]=1
i=2
while i*i<=n:
    j=2
    while i*j<=n and ans[i]==0:
        ans[i*j]=1
        j+=1
    i+=1
v=[]
for i in range(n+1):
    if ans[i]==0:
        v.append(i)
total=1
count=0
for i in v:
    while fac%i==0:
        count+=1
        fac//=i
    total*=count+1
    count=0
print(total%mod)