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

from math import floor, ceil
N, M = [int(elem) for elem in input().split(' ')]

max_gcd = 1
upperbound = M // N
cand = M // N

# for cand in range(M // N, 1, -1):
#     rest = M - cand * N
#     if rest % cand == 0:
#         max_gcd = max(max_gcd, cand)
#         break
#     else:
#         continue
# print(max_gcd)


if M % N == 0:
    print(cand)
    exit(0)
else:
    coef = 1
    rest = M - upperbound * N
    while (cand > 1):
        num_moving = floor((coef * upperbound - rest) / (N + coef))
        cand = upperbound - num_moving
        if (num_moving * N + rest) % cand == 0:
            print(cand)
            exit(0)
        else:
            coef += 1
    print(1)


### FIXED CODE ###

from math import floor, ceil, sqrt
N, M = [int(elem) for elem in input().split(' ')]

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    try:
        b, e = fct.pop()  # base, exponent
    except:
        return []
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

M_divisors = divisorize(factorize(M))
threshold = M // N
max_possible_divisor = 1
for M_divisor in M_divisors:
    divisor = num(M_divisor)
    if divisor <= threshold:
        max_possible_divisor = max(max_possible_divisor, divisor)
print(max_possible_divisor)
### BUGGY CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
dp = [0 for i in range(len(s)+1)]
u = 1
for i in range(1,len(s)+1):
    k = len(s) - i
    dp[i] = (dp[i-1] + int(s[k])*u)%2019
    u *= 10
    mods[dp[i]] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

### FIXED CODE ###

mods = [0]*2019
mods[0] = 1
s = input()
t = 0
u = 1
for i in range(1,len(s)+1):
    t = (t + int(s[-i])*u)%2019
    u = u*10%2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))
### BUGGY CODE ###

import math

m=999999
l=[False]*m
l[1]=True
l[2]=True
for i in range(5,m+1):
    if i%2==0 or i%3==0:continue
    for e in range(2,int(math.sqrt(i)+1)):
        if i%e==0:
            break
    else:
        l[i-1]=True
    
while True:
    try:n=int(input())
    except:break
    print(len([i for i in l[:n:] if i]))

### FIXED CODE ###


import math

m=999999
s=int(math.sqrt(m)+1)
li=[0]*m
li[0]=1
for i in range(1,s):
    if li[i]==0:
        li[i*2+1::i+1]=[1 for e in range(len(li[i*2+1::i+1]))]
while True:
    try:n=int(input())
    except:break
    print(len([i for i in li[:n:] if i==0]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0

for i,num in enumerate(A):
    if i > 0 and A[i-1] == num:
        continue
    
    FLG = True
    for j in A[i+1:]:
        if num % j == 0:
            FLG = False
            break
    if FLG:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [True] * (A[-1]+1)

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    for j in range(2*num, A[-1]+1, num):
        dp[j] = False

print(len([i for i in A if dp[i]]))
### BUGGY CODE ###

N=int(input())
sisterN=[]
for n in range(N):
    _=int(input())
    if sisterN.count(_)==1:
        sisterN.remove(_)
    else:
        sisterN.append(_)
print(len(sisterN))

### FIXED CODE ###

N=int(input())
S=set()

for n in range(N):
    _=int(input())
    if _ in S:
        S.remove(_)
    else:
        S.add(_)

print(len(S))
### BUGGY CODE ###

n,x=int(input()),input()

g=int(x,2)
c=pow(2,n-1)
memo={}
for b in x:
    if b=="1":
        p=g-c
    else:
        p=g+c
    ret=0
    while p:
        q=bin(p).count("1")
        if p in memo:print(ret+memo[p]);break 
        p%=q
        ret+=1
    c//=2
    memo[p]=ret
    print(ret)

### FIXED CODE ###

n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])
### BUGGY CODE ###

import fractions

n = int(input())
As = list(map(int, input().split(" ")))

largest = 1

for i in range(n):
  gcd = 0
  for idx, j in enumerate(As):
    if idx == i:
      continue
    gcd = j if gcd==0 else fractions.gcd(gcd, j)
    if gcd <= largest:
      break
  if gcd > largest:
    largest = gcd

print(largest)



### FIXED CODE ###

def gcd(a, b):
  l = max(a, b)
  s = min(a, b)
  if s == 0:
    return l
  else:
    return gcd(s, l%s)

n = int(input())
A = [0] + list(map(int, input().split())) + [0]
largest = 0
L = [0 for _ in range(n+2)]
R = [0 for _ in range(n+2)]
for i in range(1, n+2):
  L[i] = gcd(A[i], L[i-1])
  R[n-i+1] = gcd(R[n-i+2], A[n-i+1])

print(max(gcd(L[i-1],R[i+1]) for i in range(1, n+1)))
### BUGGY CODE ###

#カエル
#各足場の1つ前と2つ前を考える

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = float('inf')
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(1, N):
        for j in range(1,K+1):
            if i>=j:
                dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
            else:
                continue
    print(dp[N-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#カエル
#各足場の1つ前と2つ前を考える

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = float('inf')
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(1, N):
        for j in range(1,K+1):
            if i>=j:
                dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
            else:
                continue
    print(dp[N-1])

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

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit, maxsize


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [(1, -maxsize)] * (n//100 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())
        a -= 1
        base[a] += v

        b = a - a % 100
        index = value = -maxsize
        for i, v in enumerate(base[b:b+100], b+1):
            if value < v:
                value = v
                index = i
        midway[b//100] = (index, value)

        index = value = -maxsize
        for i, v in midway:
            if value < v:
                value = v
                index = i
        print(index, value)
    exit()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def main(readline=stdin.readline):
    n, q = (int(s) for s in readline().split())

    base = [0] * n
    midway = [0] * (n//100 + 1)
    last = [0] * (n//10000 + 1)

    for _ in range(q):
        a, v = (int(s) for s in readline().split())

        a -= 1
        base[a] += v

        b = a - a % 100

        index = b
        value = base[b]
        end = b + 100 if b + 100 < n else n
        for i in range(b, end):
            if value < base[i]:
                value = base[i]
                index = i
        midway[b//100] = index

        c = a - a % 10000
        cc = c // 100

        index = c
        value = base[c]
        for i in midway[cc:cc+100]:
            if value < base[i]:
                value = base[i]
                index = i
        last[c//10000] = index

        index = last[0]
        value = base[index]
        for i in last:
            if value < base[i]:
                value = base[i]
                index = i

        print(index+1, value)
    exit()


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

#1:初期化
N, K = map(int,input().split())
h = [int(x) for x in input().split()] #こっちのほうが早い？
dp = [0]*(N)

#3:dp実行部(貰うDP)
for i in range(1,N):
    L = [dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i)]
    dp[i] = min(L)

#4:出力
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*- 
def cost(h,N,K):
    dp=[0]*N
    dp[1]=abs(h[0]-h[1])
    for i in range(2,N):
        tmp=[abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i)]
        dp[i]=min(tmp)
    return dp[-1]

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

print(cost(h,N,K))
### BUGGY CODE ###

def main():
    S = [input()]
    Q = int(input())
    is_turned = False

    for _ in range(Q):
        query = input()
        if query == "1":
            is_turned = not is_turned
        else:
            T, F, C = query.split()
            if is_turned ^ (F == "1"):
                S.insert(0, C)
            else:
                S.append(C)

    if (is_turned):
        print("".join(S)[::-1])
    else:
        print("".join(S))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    L = ""
    R = ""
    is_turned = False

    for _ in range(Q):
        Query = input().split()
        if Query[0] == "1":
            is_turned = not is_turned
        else:
            if is_turned ^ (Query[1] == "1"):
                # L.insert(0, Query[2])
                L = Query[2] + L
            else:
                # R.append(Query[2])
                R = R + Query[2]

    if (is_turned):
        print("".join(L + S + R)[::-1])
    else:
        print("".join(L + S + R))


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

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

p = int(p) + 1

dic = {}

def my(N,p,s=2):
    for i in range(s,p+1):
        if p % i == 0:
            # print('ok')
            dic[i] = dic.get(i,0) + 1
            # print(dic)
            p = p//i
            s = i
            if 2*i**N > P:
                p = 1
            break
    
    if p == 1:
        res = 1
        for j,k in dic.items():
            res *= j**(k//N)
        print(res)
        exit()
    else:
        my(N,p,s)

my(N,P)

### FIXED CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

lim = int(p) + 1

dic = {}

def my(N,newP):
    for i in range(2,lim+1):
        while newP % i == 0:
            dic[i] = dic.get(i,0) + 1
            newP = newP // i
        if newP < i or i == lim:
            res = 1
            for j,k in dic.items():
                res *= j**(k//N)
            print(res)
            exit()
my(N,P)
### BUGGY CODE ###

s=int(input())
a=[-12345]*1000000
for i in range(1000000):
    
    a[i]=s
    if s%2==1:
        s=s*3+1
    else:
        s=s/2

    if s in a:
        print(i+2)
        break

### FIXED CODE ###

s=int(input())
a=[-12345]*100000
for i in range(100000):
    
    a[i]=s
    if s%2==1:
        s=s*3+1
    else:
        s=s/2

    if s in a:
        print(i+2)
        break
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
a = np.array(list([int(x) for x in input().split()]))

for i in range(m):
    a[np.argmax(a)] = max(a)//2
print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = [-int(x) for x in input().split()]
heapq.heapify(a)

for i in range(m):
    l = -heapq.heappop(a)
    heapq.heappush(a, -(l//2))
    
print(-sum(a))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
for i in a:
    if a.count(i)>1:
        print('NO')
        exit()
        
print('YES')        
        

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=set(a)

if len(a)==len(b):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(input())

List = []
for i in range(N):
    temp = []
    for j in range(10):
        temp.append(A[i][j])
    temp.sort()
    List.append(temp)
    
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if List[i] == List[j]:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]

L = ["0"]*N
for i in range(N):
    temp = ["0"]*10
    for j in range(10):
        temp[j] = S[i][j]
    temp.sort()
    L[i] = temp
        
L.sort()
ans = 0
cnt = 1
temp = L[0]
for i in range(1, N):
    if temp == L[i]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        temp = L[i]
        
ans += cnt*(cnt-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

n = 10**5
#primes = set(range(3, n+1, 2))|set([2])
primes = set(range(3, n+1, 2)) #偶数は除く
for i in range(3, int(n**0.5+1)):
    primes.difference_update(range(i*3, n+1, i*2))
primes = list(primes)

Likes = [0] * (n+1)
cnt = 0
for i in primes:
    if (i+1)//2 in primes or (i+1)//2==2:
        Likes[i]=1
for i in range(1,n):
    Likes[i]+=Likes[i-1]

def main():
    Q = int(input())
    for q in range(Q):
        l,r = map(int,input().split())
        print(Likes[r]-Likes[l-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
N=100000
primes = set(range(3, N+1, 2))
for i in range(3, int(N**0.5+1)):
  primes.difference_update(range(i*3, N+1, i*2))
primes=set(primes)
primes.add(2)
FG=[0]*(N+1)
for i in range(1,N+1,2):
  FG[i-1]=FG[i-2]
  if i in primes and (i+1)//2 in primes:
    FG[i]=FG[i-1]+1
  else:
    FG[i]=FG[i-1]
for q in range(int(input())):
  l,r=map(int,input().split())
  print(FG[r]-FG[l-1])
### BUGGY CODE ###

import sys, heapq
input = sys.stdin.buffer.readline # 入出力高速化

def main():
    N, Q = map(int, input().split())
    tl = [] # イベントタイムライン
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    tl.sort()
    working = list() # 工事中
    todelete = list() # 削除用
    for t, c, x in tl:
        if c == 0: # erase
            heapq.heappush(todelete, x)
        elif c == 1: # insert
            heapq.heappush(working, x)
        else: # min
            while todelete and todelete[0] == working[0]:
                heapq.heappop(todelete)
                heapq.heappop(working)
            print(-1 if not working else working[0])
    return
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

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

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
### BUGGY CODE ###

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

for _ in range(Q):
    A.append(int(input()))

Count = []
for n in range(N):
    freq = A.count(n + 1)
    Count.append(freq)

for i in range(N):
    if K - Q + Count[i] <= 0:
        print('No')
    else:
        print('Yes')




### FIXED CODE ###

N, K, Q = map(int, input().split())
index_list = [int(input()) - 1 for i in range(Q)]

zero_list = [0 for n in range(N)]

ori = K - Q
for i in range(Q):
    zero_list[index_list[i]] += 1
for i in range(N):
    zero_list[i] += ori
for i in range(N):
    if zero_list[i] > 0:
        print('Yes')
    else:
        print('No')

# shakayamiさんのコードを参考にしました
# for文が入れ子になると遅くなるから，出来るだけそうしない
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
L = [0]*n
R = [0]*n
cnt=0
for i in range(n):
    L[i] = i+a[i]
    R[i] = i-a[i]
z1=dict(Counter(L))
z2=dict(Counter(R))
cnt=0
for k1,v1 in z1.items():
    for k2,v2 in z2.items():
        if k1 == k2:
            cnt += v1*v2
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
L = [0]*n
R = [0]*n
cnt=0
for i in range(n):
    L[i] = i+a[i]
    R[i] = i-a[i]
z1=Counter(L)
z2=Counter(R)
cnt=0
for k1,v1 in z1.items():
    v2 = z2[k1]
    cnt += v1*v2
print(cnt)
### BUGGY CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))


ans = 0
for j in range(n - k + 1):
    sums = 0
    for z in range(j,j + k):
        sums += sum([l for l in range(1, p[z] + 1)]) / p[z]
    ans = max(ans, sums)

print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
p = list(map(int, input().split()))

saikoro = [0] * 1001
for i in range(1, 1001):
    saikoro[i] = (saikoro[i-1] + i)

s = [0] * (n + 1)
for u in range(1,n + 1):
    s[u] = saikoro[p[u - 1]] / p[u - 1] + s[u - 1]

ans = 0
for j in range(k - 1,n):
    ans = max(ans, s[j + 1] - s[j + 1 - k])
 
print(ans)
### BUGGY CODE ###

N = int(input())
A = input().split()

result = 1

for num in range(N):
    result = result * int(A[num])

if result <= 10 ** 18:
    print(result)
else:
    print("-1")

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #配列を昇順ソートしておく(配列に0がある場合0が先頭に来るので、場合分けの必要がなくなる)
ans=1
for val in arr:
 ans*=val #Pythonは多倍長整数をサポートしているので単に積を求めれば十分
 if ans>10**18:
   print(-1)
   break
else:
 print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
b = 0
for i in range(N):
    if i == b:
        a = A.count(A[i])
        b = i + a
        if A[i] > a:
            ans += a
        elif A[i] < a:
            ans += a - A[i]
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
old = A[0]
ans = 0
a = 1
for i in range(1, N):
  if A[i] == old: 
    a += 1
  else:
    if old > a:
      ans += a
    elif old < a:
      ans += a - old
    old = A[i]
    a = 1
if old > a:
  ans += a
elif old < a:
  ans += a - old
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
  
array1 = []

for i in range(N):
  for j in range(ab[i][1]):
    array1.append(ab[i][0])
    
array1.sort()

print(array1[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort()

counter = 0
array1 = []

for i in range(N):
  counter += ab[i][1]
  if K <= counter:
    ans = ab[i][0]
    break

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

H, W = map(int, input().split())
A = [input() for _ in range(H)]

U = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]

for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            U[h][w] = 0
            L[h][w] = 0
        else:
            U[h][w] = 1 + (U[h - 1][w] if h > 0 else 0)
            L[h][w] = 1 + (L[h][w - 1] if w > 0 else 0)

        y = H - h - 1
        x = W - w - 1
        if A[y][x] == '#':
            D[y][x] = 0
            R[y][x] = 0
        else:
            D[y][x] = 1 + (D[y + 1][x] if y < H - 1 else 0)
            R[y][x] = 1 + (R[y][x + 1] if x < W - 1 else 0)

ans = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == '.':
            ans = max(ans, U[h][w] + D[h][w] + L[h][w] + R[h][w] - 3)
print(ans)


### FIXED CODE ###

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

s = [0] * H

for i in range(H) :
    s[i] = list(input())

# 端をゼロパディング
L = [[0 for _ in range(W+2)] for _ in range(H+2)]
R = [[0 for _ in range(W+2)] for _ in range(H+2)]
U = [[0 for _ in range(W+2)] for _ in range(H+2)]
D = [[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(1,H+1) :
    for j in range(1,W+1) :
        # 左上から
        if s[i-1][j-1] == '#' :
            L[i][j] = 0
            U[i][j] = 0
        else :
            L[i][j] = L[i][j-1] + 1
            U[i][j] = U[i-1][j] + 1
        # 右下から
        if s[-i][-j] == '#' :
            R[-i-1][-j-1] = 0
            D[-i-1][-j-1] = 0
        else :
            R[-i-1][-j-1] = R[-i-1][-j] + 1
            D[-i-1][-j-1] = D[-i][-j-1] + 1

ans = 0

for i in range(1,H+1) :
    for j in range(1,W+1) :
        point = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        if ans < point :
            ans = point

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

from operator import mul
from functools import reduce

mod = 10 ** 9 + 7
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def pat(n):
  cnt = 0
  for i in range(n//2 + 1):
    cnt += int(combinations_count(n - i, i))
  return cnt

n, m = map(int, input().split())
a = []
start = 0
cnt = 1
for i in range(m):
  ko = int(input())
  end = ko - 1
  cnt = cnt * pat(end - start)
  start = ko + 1
cnt = cnt * pat(n - start)

print(cnt % mod)

### FIXED CODE ###

n, m = map(int, input().split())
MOD = 1000000007

fact=[0,1]
fact_inv=[0]*(n+1)
for i in range(2,n+1):
  fact.append(fact[-1]*i % MOD)

fact_inv[n] = pow(fact[n],MOD-2,MOD)
for i in range(n-1,-1,-1):
  fact_inv[i] = fact_inv[i+1]*(i+1)%MOD

def comb(n,r):
  return fact[n]*fact_inv[r]*fact_inv[n-r]%MOD

def sigmaComb(dis):
  ans=0
  if dis == 1 or dis == 0:
    return 1
  end=dis//2+1
  for i in range(end):
    t=comb(dis-i,i)
    #print(dis-i,i,t)
    ans+=t
  return ans

hole=[0]
ans=1
for i in range(m):
  t = int(input())
  availLeft=hole[-1]
  availRight=t-1
  dis=availRight-availLeft
  if dis <0:
    ans=0
    break

  ans=ans*sigmaComb(dis)%MOD
  #print("dis=",dis,t,ans)
  hole.append(t+1)
else:
  availLeft=hole[-1]
  availRight=n
  dis=availRight-availLeft
  #print("dis=",dis,hole[-1],ans)
  ans=ans*sigmaComb(dis)%MOD

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

import time
import itertools

N = int(input())
def function(x,y,z):
    return pow(x,2) + pow(y,2) + pow(z,2) + (x * y) + (x * z ) + (y * z)

start = time.time()

p = list(itertools.product(range(1,30),repeat=3))
a = []

for p_in in p:
    a.append(function(p_in[0],p_in[1],p_in[2]))

for n in range(1,N + 1):
    print(a.count(n))

elapsed_time = time.time() - start
# print("elapsed_time:{0}".format(elapsed_time) + "[sec]")


### FIXED CODE ###

import time
import itertools
import collections

N = int(input())
start = time.time()
def function(x,y,z):
    return pow(x,2) + pow(y,2) + pow(z,2) + (x * y) + (x * z ) + (y * z)

p = list(itertools.product(range(1,100),repeat=3))
a = []

for p_in in p:
    a.append(function(p_in[0],p_in[1],p_in[2]))

dict = collections.Counter(a)

for n in range(1,N + 1):
    print(dict[n])