One day, $n$ people ($n$ is an even number) met on a plaza and made two round dances, each round dance consists of exactly $\frac{n}{2}$ people. Your task is to find the number of ways $n$ people can make two round dances if each round dance consists of exactly $\frac{n}{2}$ people. Each person should belong to exactly one of these two round dances.

Round dance is a dance circle consisting of $1$ or more people. Two round dances are indistinguishable (equal) if one can be transformed to another by choosing the first participant. For example, round dances $[1, 3, 4, 2]$, $[4, 2, 1, 3]$ and $[2, 1, 3, 4]$ are indistinguishable.

For example, if $n=2$ then the number of ways is $1$: one round dance consists of the first person and the second one of the second person.

For example, if $n=4$ then the number of ways is $3$. Possible options:  one round dance — $[1,2]$, another — $[3,4]$;  one round dance — $[2,4]$, another — $[3,1]$;  one round dance — $[4,1]$, another — $[3,2]$. 

Your task is to find the number of ways $n$ people can make two round dances if each round dance consists of exactly $\frac{n}{2}$ people.


-----Input-----

The input contains one integer $n$ ($2 \le n \le 20$), $n$ is an even number.


-----Output-----

Print one integer — the number of ways to make two round dances. It is guaranteed that the answer fits in the $64$-bit integer data type.


-----Examples-----
Input
2

Output
1

Input
4

Output
3

Input
8

Output
1260

Input
20

Output
12164510040883200

Difficulty: introductory

Starter code:

Solutions:
from math import *

n = int(input())
print(factorial(n) // (factorial(n // 2) ** 2) * factorial(n//2-1) ** 2 // 2)


def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n-1)


n = int(input())

m = n // 2

ans = fac(n)//(2*m**2)

print(ans)


def cal(k):
    ans = 1
    for i in range(k+1, 2*k):
        ans *= i
    for i in range(1, k):
        ans //= i
    # print(ans)
    t = 1
    for i in range(1, k):
        t *= i
    # print(t)
    ans *= t*t
    return ans


print(cal(int(input())//2))


import sys
input = sys.stdin.readline

def main():
    n = int(input())
    ans = 1
    for i in range(2, n):
        ans *= i
    
    print(ans // (n // 2))
    
    
main()

n = int(input())
ans = 1
for i in range(1, n):
    ans *= i
ans //= (n // 2)
print(ans)

n=int(input())
p=2
for i in range(1,n):
	p=p*i
print(p//n)

n = int(input())
ans = 1
for i in range(1, n+1):
    ans *= i
print(ans//(n*n//2))

n=int(input())

res=1
for i in range(n-1):
	res*=(i+1)

res//=(n//2)
print(res)

from math import factorial

n = int(input())
kek = factorial(n) // factorial(n // 2) // factorial(n // 2) // 2
print(kek * factorial(n // 2) * factorial(n // 2) // (n // 2) // (n // 2))

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key, lru_cache


import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


@lru_cache(None)
def fact(n):
    ans = 1
    if n == 0:return 1
    for i in range(1, n + 1):ans *= i
    return ans

def ncr(n, r):
    return fact(n) / (fact(r) * fact(n - r))
    



n = val()


print(int((ncr(n, n // 2) * (fact((n // 2) - 1) ** 2)) // 2))

def f(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

n = int(input())

if n == 2:
	print(1)
elif n == 4:
	print(3)
else:
	ans = f(n) // (2 * n * n)
	print(ans * 4)


from math import factorial as f

n = int(input())
print(f(n) // 2 // (n // 2) // (n // 2))



n=int(input())
ans=1
for i in range(1,n+1):
    ans=ans*i
ans=ans//(n//2)
ans=ans//(n//2)
ans=ans//2
print(ans)

def solve():
	n = int(input())
	n -= 2
	num = 2
	for i in range(1,n+2):
		num *= i
	num = num // (n+2)
	return num

#main
print(solve())

def fact(n):
	ft=1
	while n>0:
		ft=ft*n
		n=n-1
	return ft
n=int(input())
q=2*fact(n)//(n*n)
print(q)


def opt1(n):
    k = n // 2
    res = 1
    for i in range(k + 1, n + 1):
        res *= i
    for i in range(2, k + 1):
        res //= i
    return res
def opt2(n):
    res = 1
    for i in range(1, n + 1):
        res *= i
    if n == 1:
        return 1
    if n == 2:
        return 1
    return res // n
n = int(input())
print(opt1(n) * opt2(n // 2) * opt2(n // 2) // 2)

n=int(input())
f=1
for i in range(1,n):
    f=f*i
k=n//2
ans=f//k
print(ans)



import sys,math,itertools
from collections import Counter,deque,defaultdict
from bisect import bisect_left,bisect_right 
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
n //= 2;n-=1

print(math.factorial(2*n+1)//(n+1))

n = int(input())
ans = 1
for i in range(n):
    ans *= i + 1
for i in range(n // 2):
    ans //= i + 1
    ans //= i + 1
gg = 1
for i in range(n//2 - 1):
    gg *= i + 1
ans *= gg * gg
ans//= 2
print(ans)


from math import factorial

n = int(input())
a = [0, 1, 3, 40, 1260, 72576, 6652800, 889574400, 163459296000, 39520825344000, 12164510040883200]
print(a[n // 2])


n = int(input())
f = [1]
for i in range(1, 21):
    f.append(f[-1]*i)
print((f[n]*f[n//2 - 1]**2)//(2*f[n//2]**2))


def fact(n):
    ans = 1
    for i in range(1, n + 1):
        ans *= i
    return ans

a = int(input())
ans = fact(a)//( fact(a//2) * fact(a//2)  )
ans *= fact(a//2 - 1)
ans *= fact(a//2 - 1)
print(ans//2)

def fact(a):
    if a == 1:
        return 1
    else:
        return fact(a - 1) * a
n = int(input())
print(fact(n) // fact(n // 2) // (n // 2) * (fact(n // 2) // (n // 2)) // 2)

def fact(n) :
    ans = 1
    for i in range(2,n+1) : ans *= i
    return ans
n = int(input())//2 - 1
print(fact(2*n + 1)//(n + 1))



import math
n = int(input())
print(math.factorial(n) // n // (n // 2))


import math

def binom(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)


tt = int(input())

print(binom(tt,tt//2)*math.factorial(tt//2-1)*math.factorial(tt//2-1)//2)

n = int(input())
n = n // 2 - 1
ans = 1
for x in range(1, 2 * n + 2):
    ans = ans * x
print(ans // (n + 1))


n = int(input())

f = 1
for i in range(1, n):
    f *= i

print(f // (n // 2))


n=int(input())
t=1
for i in range(n):
    t*=(i+1)
print(t//((n*n)//2))

n=int(input())
def fact(n):
    res=1
    for i in range(2,n+1):
        res*=i
    return res;

z=n//2
ans=fact(n);
p=fact(z-1);

ans*=p*p;
ans/= fact(z);
ans/=fact(z);
ans/=2;
print(int(ans))

n = int(input())
res = [1, 3, 40, 1260, 72576, 6652800, 889574400, 163459296000, 39520825344000, 12164510040883200]
print(res[n//2-1])


def factorial(n):
    if n < 0:
        return 0
    if n <= 1:
        return 1
    return n*factorial(n-1)
def ncr(n,r):
    if n < 0 or r < 0 or n < r:
        return 0
    return factorial(n)//factorial(r)//factorial(n-r)

n = int(input())
left_choice = ncr(n,n//2)//2
left = factorial(n//2)
right = left
left = left//(n//2)
right = right//(n//2)
# print(left_choice,left,right)
print(left_choice*left*right)

import sys
input = sys.stdin.readline

ret = [1, 1, 1, 1, 3, 8, 40, 180, 1260, 8064, 72576, 604800, 6652800, 68428800, 889574400, 10897286400, 163459296000, 2324754432000, 39520825344000, 640237370572800, 12164510040883200]
print(ret[int(input())])


def ncr(n,r):
    return fact[n]//(fact[r]*fact[n-r])
n=int(input())
fact=[1 for i in range(25)]
for i in range(2,25):
    fact[i]=fact[i-1]*i
if(n==2):
    print(1)
    quit()
if(n==4):
    print(3)
    quit()
z=(ncr(n,n//2))//2
z=z*(fact[(n//2)-1]*fact[(n//2)-1])
print(z)


from math import factorial
n = int(input())
ans = factorial(n//2 - 1) ** 2
ans *= ((factorial(n) // (factorial(n//2) ** 2))//2)
print(ans)

import math
n=int(input())
print(int(2*math.factorial(n-1)/n))

from math import factorial as f
n=int(input())
ans=f(n)//(n-n//2)//f(n//2)//2*(f(n//2-1))
print(ans)

n = int(input())
ncr = 1
for i in range(n//2+1, n+1):
    ncr = ncr * i
for i in range(1, n//2+1):
    ncr = ncr//i
ans = ncr//2
fmul = 1
for i in range(1, n//2):
    fmul = fmul*i
ans = ans*fmul
ans = ans*fmul
ans = int(ans)
print(ans)


from math import factorial
n = int(input())
print(factorial(n)*factorial(n//2-1)**2//factorial(n//2)**2//2)


a = int(input())
fact = 1
for i in range(1, a):
  fact *= i
print(int(fact / (a/2)))

import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

def fact(n):
	if n<=1:
		return 1
	return n*fact(n-1)

n,=I()
print(fact(n-1)//(n//2))

import math
a=int(input())
print (int(math.factorial(a-1)/(a/2)))