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

import math


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


n, k = map(int, input().split())
A = sorted(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7
for i, Ma in enumerate(A[::-1]):
    i = n - i
    for j, ma in enumerate(A):
        if ma == Ma or i - j < k:
            break
        ans += (combinations_count(i - j - 2, k - 2) * (Ma - ma)) % mod
        ans %= mod
print(ans)


### FIXED CODE ###

from functools import lru_cache
n, k = map(int, input().split())
A = sorted(map(int, input().split()))
mod = 10 ** 9 + 7
# 階乗とその逆元の計算
factrial = [0 for _ in range(n + 1)]
factrial[0] = 1
for i in range(1, n + 1):
    factrial[i] = (factrial[i - 1] * i) % mod
inverse_factrial = list()
for f in factrial:
    inverse_factrial.append(pow(f, -1, mod))


@lru_cache(maxsize=None)
def nCr(n, r):
    return (factrial[n] * inverse_factrial[r] * inverse_factrial[n - r]) % mod


ans = 0
# 最大値の和
for i, a in enumerate(A[k - 1:], k - 1):
    ans += ((a % mod) * nCr(i, k-1)) % mod
    ans %= mod
# 最小値の和
A.reverse()
for i, a in enumerate(A[k - 1:], k - 1):
    ans -= ((a % mod) * nCr(i, k-1)) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###



import sys
sys.setrecursionlimit(10000)

n, k = map(int,input().split())
nck = {}

def c(n,k):
    if k == 0 or n==k:
        return 1
    elif n<k:
        return 0
    elif k == 1:
        return n  
    elif (n,k) in nck:
        return nck[(n,k)]
    else:
        nck[n,k] = c(n-1,k-1)+c(n-1,k)
        return nck[n,k]

for j in range(1,k+1):
    r = (c(n-k+1,j)*c(k-1,j-1))%(10**9+7)
    print(r)

### FIXED CODE ###



import sys
sys.setrecursionlimit(10000)

n, k = map(int,input().split())
nck = {}

def c(n, r):
    
    if n<r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

for j in range(1,k+1):
    r = (c(n-k+1,j)*c(k-1,j-1))%(10**9+7)
    print(r)
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
    P[i] = (1+P[i])/2
A = 0
for i in range(N-K+1):
    B = 0
    for j in range(i,i+K):
        B = B+P[j]
    if A < B:
        A = B
print(A)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
    P[i] = (1+P[i])/2
A = 0
for i in range(K):
    A = A+P[i]
    B = A
for i in range(1,N-K+1):
    B = B-P[i-1]+P[i+K-1]
    if A < B:
        A = B
print(A)
### BUGGY CODE ###

L,R = map(int,input().split())

j_cnt = 0
i_cnt = 0
i = L
j = L+1
min_num = 2020
while i <= R and i_cnt <= 2019:
    j = i+1
    while j <= R and j_cnt <= 2019:
        min_num = min(min_num,((i%2019)*j)%2019)
        j += 1
        j_cnt += 1
    i += 1
    i_cnt += 1
    j_cnt = 0
print(min_num)

### FIXED CODE ###

L,R = map(int,input().split())
 
cnt = 0
i = L
j = L+1
min_num = 2020
while i <= R and cnt <= 2019:
    j = i+1
    while j <= R:
        min_num = min(min_num,(i*j)%2019)
        if not min_num:
            break
        j += 1
    i += 1
    cnt += 1
print(min_num)
### BUGGY CODE ###

A, B = (int(x) for x in input().split())

binary = [False]*40
count = 0

for i in range(A, B+1):
    for j in range(39, -1, -1):
        if i >= 2 ** j:
            binary[j] = not(binary[j])
            i -= 2 ** j

#print(binary)

for i in range(len(binary)):
    if binary[i]:
        count += 2 ** i
        
print(count)


### FIXED CODE ###

A, B = (int(x) for x in input().split())

if A>0:
    A -= 1
    
count = 0

binary_a = [False]*40
binary_b = [False]*40

for i in range(1,40):
    if int((A / (2 ** i))) % 2 == 1:
        if A % 2 == 0:
            binary_a[i] = True
    if int((B / (2 ** i))) % 2 == 1:
        if B % 2 == 0:
            binary_b[i] = True
            
if A%4 == 1 or A%4 ==2:
    binary_a[0] = True
if B%4 == 1 or B%4 ==2:
    binary_b[0] = True
    
#print(binary_a)
#print(binary_b)

for i in range(40):
    if not(binary_a[i] == binary_b[i]):
        count += 2 ** i
        
print(count)
### BUGGY CODE ###

from fractions import gcd
K = int(input())
sum = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            sum += gcd(a, gcd(b, c))

print(sum)

### FIXED CODE ###

from math import gcd
K = int(input())
sum = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            sum += gcd(a, gcd(b, c))

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

n = int(input())
a = [int(x) for x in input().split()]
prod = 1
a.sort()
for i in range(n):
	if a[i] == 0:
		prod = 0
		break
	else:
		prod *= a[i]
if prod > int(1e18):
	print(-1)
else:
	print (prod)

### FIXED CODE ###

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

k = 1
if 0 in A:
	print(0)
else:
	for i in A:
		k = k * i
		if k > 10 ** 18:
			print(-1)
			break
	if k <= 10 ** 18:
		print(k)
### BUGGY CODE ###

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


maxv = -float("inf")
for i in range(N, 2*N+1):
    tmp = sum(sorted(a[:i], reverse=True)[:N]) - sum(sorted(a[i:])[:N])
    if tmp > maxv:
        maxv = tmp
print(maxv)

### FIXED CODE ###

import heapq

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

q = a[:N]
heapq.heapify(q)
x = [sum(q)]

for k in range(N, 2*N):
    ## in : a[k], out : v
    out = heapq.heappushpop(q, a[k])
    x.append(x[-1]+a[k]-out)
    
a = a[::-1]    
q = [-v for v in a[:N]]
heapq.heapify(q)
y = [-sum(q)]
for k in range(N, 2*N):
    out = -heapq.heappushpop(q, -a[k])
    y.append(y[-1]+a[k]-out)
    
print(max(v-w for v,w in zip(x, y[::-1])))
### BUGGY CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = tuple(read().split())


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        visited[x][y]=True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp

print(answer)


### FIXED CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = [list(input()) for i in range(H)]


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)
### BUGGY CODE ###

mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

    for i in range(13):
        dp[i] = nextdp[i] % mod


print(dp[5])

### FIXED CODE ###

mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

    dp = [nextdp[i] % mod for i in range(13)]

    # for i in range(13):
    #     dp[i] = nextdp[i] % mod

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

from numba import jit,njit
import numpy as np
from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

N,M = map(int,input().split())
length = N

@jit
def resieveInput(M):
    i = [] #頂点(始点)
    j = [] #頂点(終点)
    d = [] #頂点間の距離
    for _ in range(M):
        A,B = map(int,input().split())
        i.append(A-1)
        j.append(B-1)
        d.append(1)
    return i,j,d

i,j,d = resieveInput(M)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)
print("Yes")
print(*(pred[1:]+1),sep="\n")


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

def main():
    import sys
    import heapq
    from copy import deepcopy
    from collections import deque
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    _N, K = [int(x) for x in input().strip().split()]
    V = deque([int(x) for x in input().strip().split()])
    max_ans = sum([v for v in V if v > 0])

    def dfs(ans, q, V, k):
        # print(k, q, V)
        ans = max(ans, sum(q))
        if ans == max_ans:
            print(ans)
            exit()
        if k == K:
            return ans
        if q:
            t = heapq.heappop(q)
            if t < 0:
                V.appendleft(t)
                ans = max(ans, dfs(ans, q[:], V, k+1))
                V.popleft()
                V.append(t)
                ans = max(ans, dfs(ans, q, V, k+1))
                V.pop()
            heapq.heappush(q, t)
        if V:
            q_l = q[:]
            q_r = q[:]
            t = V.popleft()
            heapq.heappush(q_l, t)
            ans = max(ans, dfs(ans, q_l[:], V, k+1))
            V.appendleft(t)
            t = V.pop()
            heapq.heappush(q_r, t)
            ans = max(ans, dfs(ans, q_r[:], V, k+1))
            V.append(t)
            
        return ans
    print(dfs(-float('inf'), [], V, 0))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import heapq
    from copy import deepcopy
    from collections import deque
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    V = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    for l in range(min(N, K)+1):
        for r in range(min(N, K)-l+1):
            vt = sorted(V[:l] + V[N-r:])
            c = 0
            i = 0
            for i in range(len(vt)):
                if c == (K-l-r):
                    break
                if vt[i] < 0:
                    vt[i] = 0
                    c += 1
                else:
                    break
            ans = max(ans, sum(vt))

    print(ans)

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

# ABC077C

import bisect

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

bC=[0 for i in range(N)]
for i in range(N):
    bC[i]=N-bisect.bisect(C,B[i])
    
ans=0
for i in range(N):
    x=bisect.bisect(B,A[i])
    for j in range(x,N):
        ans+=bC[j]
        
print(ans)

### FIXED CODE ###

# ABC077C

import bisect

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

bC=[0 for i in range(N)]
for i in range(N):
    bC[i]=N-bisect.bisect(C,B[i])
    
bCS=[0]*(N+1)
for i in range(N):
    bCS[i+1] = bCS[i]+bC[i]
    
ans=0
for i in range(N):
    x=bisect.bisect(B,A[i])
    ans+=bCS[N]-bCS[x]
        
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict,deque
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

graph = defaultdict(lambda: defaultdict(int))

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v,g):
    que = deque()
    que.append([v,0])
    while len(que) > 0:
        i,dist = que.pop()  # 深さ優先探索        
        # i = que.popleft() #幅優先探索
        if i == g:
            return dist
        visited[i] = True
        for n, val in graph[i].items():
            if visited[n] == False:
                que.append([n,dist+val])

    return -1

for x,y in xy:
    visited = defaultdict(bool)
    d1 = xfs(x-1, K-1)
    visited = defaultdict(bool)
    d2 = xfs(K-1, y-1)
    print(d1 + d2)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict,deque
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N-1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

# graph = defaultdict(lambda: defaultdict(int))
graph = [defaultdict(int) for _ in range(N)]

for a,b,c in abc:
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def xfs(v):
    dist = [-1 for _ in range(N)]
    dist[v] = 0
    que = deque()
    que.append(v)
    while len(que) > 0:
        i = que.pop()  # 深さ優先探索        
        # i = que.popleft() #幅優先探索
        for n, val in graph[i].items():
            if dist[n] == -1:
                dist[n] = dist[i] + val
                que.append(n)
    return dist

dist = xfs(K-1)

for x,y in xy:
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

N=int(input())
S=input()
cnt=0
for i in range(1000):
    c=[i//100,(i//10)%10,i%10]
    f=0
    for j in range(N):
        if S[j]==str(c[f]):
            f+=1
        if (f==3):
            break
    if f==3:
        cnt+=1
print(cnt)    

### FIXED CODE ###

N=int(input())
S=input()
cnt=0
for i in range(1000):
    c=[i//100,(i//10)%10,i%10]
    f=0
    for j in range(N):
        if S[j]==str(c[f]):
            f+=1
        if (f==3):
            break
    if f==3:
        cnt+=1
print(cnt)
### BUGGY CODE ###

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

ans_list = []
for i in range(n):
    f = True
    for j in range(n):
        if i == j:
            continue

        if data[i] % data[j] == 0:
            f = False
            break

    if f:
        ans_list.append(data[i])

print(len(ans_list))


### FIXED CODE ###

from collections import Counter

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

max_ = 10 ** 6 + 1
b = [True] * (max_ + 1)
data.sort()
c = Counter(data)

ans = 0
for d in data:
    if b[d]:
        for j in range(d, max_, d):
            b[j] = False
        # 複数存在
        if c[d] > 1:
            continue
        else:
            ans += 1

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

s = int(input())

x1, y1 = 0, 0
x2, y2, x3, y3 = 0, 0, 0, 0

while True:
    if s >= 10e9:
        for i in range(min(int(s**0.5), 10e9), 0, -1):
            if s % i == 0 and s / i <= 10e9:
                x2 = i
                y3 = s//i
                break
    else:
        for i in range(1, int(s**0.5) + 1):
            if s % i == 0 and s / i <= 10e9:
                x2 = i - x1
                y3 = s//i
                break

    if x2 == 0 and y3 == 0:
        y2 = -1
        x3 += 1
        s -= x3
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

from collections import defaultdict
s = input()
n = len(s)
d = defaultdict(int)
d[0] = 1
total = 0

for i in range(n):
  buf = s[n-i-1:n]
  l = (int(buf))%2019
  d[l] += 1
  total += d[l] - 1
  #print(int(buf),l)
  
print(total)

### FIXED CODE ###

S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019
print(ans)
### BUGGY CODE ###

import sys
INPUT = sys.stdin.readline
S = list(input())
S.reverse()
L = len(S)
A, B, C = 'A', 'B', 'C'

followingAs = 0
searchABC = 0
ans = 0

while S:

    last = S.pop()

    if last == A:
        if searchABC == 0:
            searchABC = 1
            followingAs += 1
            continue
        
        elif searchABC == 1:
            followingAs += 1
            continue
        
        else: #searchABC == 2:
            searchABC = 1
            followingAs = 1
            continue
    
    elif last == B:
        if searchABC == 0:
            continue

        elif searchABC == 1:
            searchABC += 1
            continue

        else: # searchABC == 2:
            searchABC = 0
            followingAs = 0
            continue

    else: # last == C

        if searchABC == 0:
            continue

        elif searchABC == 1:
            followingAs = 0
            searchABC = 0
            continue

        else:
            ans += followingAs
            S += ['A' for _ in range(followingAs)]
            followingAs = 0
            searchABC = 0
            continue

print(ans)

### FIXED CODE ###

import sys
INPUT = sys.stdin.readline
S = list(input())
S.reverse()
L = len(S)
A, B, C = 'A', 'B', 'C'

followingAs = 0
searchABC = 0
ans = 0

while S:

    last = S.pop()

    if last == A:
        if searchABC == 0:
            searchABC = 1
            followingAs += 1
            continue
        
        elif searchABC == 1:
            followingAs += 1
            continue
        
        else: #searchABC == 2:
            searchABC = 1
            followingAs = 1
            continue
    
    elif last == B:
        if searchABC == 0:
            continue

        elif searchABC == 1:
            searchABC += 1
            continue

        else: # searchABC == 2:
            searchABC = 0
            followingAs = 0
            continue

    else: # last == C

        if searchABC == 0:
            continue

        elif searchABC == 1:
            followingAs = 0
            searchABC = 0
            continue

        else:
            ans += followingAs
            searchABC = 1
            continue

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

from math import prod

def factorize(n):
    out=[]
    i = 2
    while 1:
        if n%i==0:
            out.append(i)
            n //= i
        else:
            i += 1
        if n == 1:break
        if i > int(n**.5+3):
            out.append(n)
            break
    
    return out
  
N = int(input())
if N == 1:
  print(1)
  exit()
elif N == 2:
  print(3)
  exit()
f = factorize(N)
if set(f)=={2}:
  f_ = prod(f)
else:
  f_ = f[-1]
for i in range(1,10**7):
  if (f_*i-1)*(f_*i)%(2*N)==0:
    print(f_*i-1)
    exit()
  elif (f_*i)*(f_*i+1)%(2*N)==0:
    print(f_*i)
    exit()

### FIXED CODE ###

import typing

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
# https://github.com/not522/ac-library-python/blob/master/atcoder/math.py
def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
    assert len(r) == len(m)

    n = len(r)

    # Contracts: 0 <= r0 < m0
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1 <= m[i]
        r1 = r[i] % m[i]
        m1 = m[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue

        # assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        '''
        (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        r2 % m0 = r0
        r2 % m1 = r1
        -> (r0 + x*m0) % m1 = r1
        -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        -> x = (r1 - r0) / g * inv(u0) (mod u1)
        '''

        # im = inv(u0) (mod u1) (0 <= im < u1)
        g, im = _inv_gcd(m0, m1)

        u1 = m1 // g
        # |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g:
            return (0, 0)

        # u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        x = (r1 - r0) // g % u1 * im % u1

        '''
        |r0| + |m0 * x|
        < m0 + m0 * (u1 - 1)
        = m0 + m0 * m1 / g - m0
        = lcm(m0, m1)
        '''

        r0 += x * m0
        m0 *= u1  # -> lcm(m0, m1)
        if r0 < 0:
            r0 += m0

    return (r0, m0)

def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)
  
N=int(input())
F = make_divisors(2*N)

ans = 10**20
for x in F:
  y = 2*N//x
  res,_ = crt([0,-1],[x,y])
  if res != 0:
    ans = min(ans,res)
  
print(ans)