#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-all-loops")
#pragma GCC target("sse4.2")
using namespace std;
ifstream in;
ofstream out;
const long long kk = 1000;
const long long ml = kk * kk;
const long long mod = ml * kk + 7;
const long long inf = ml * ml * ml + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long n;
vector<long long> v;
bool viv = false;
long long C(int n, int k) {
  long long res = 1;
  for (int i = n - k + 1; i <= n; i++) res *= i;
  for (int i = 1; i <= k; i++) res /= i;
  return res;
}
long long f(int n) {
  long long res = 1;
  for (int i = 1; i <= n; i++) res *= i;
  return res;
}
void solve() {
  cin >> n;
  long long ans = C(n, n / 2);
  ans *= f(n / 2 - 1);
  ans *= f(n / 2 - 1);
  ans /= 2;
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) solve();
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

One day, n people (n is an even number) met on a plaza and made two round dances, each round dance consists of exactly 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 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 n/2 people.

Input

The input contains one integer n (2 ≤ n ≤ 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-all-loops")
#pragma GCC target("sse4.2")
using namespace std;
ifstream in;
ofstream out;
const long long kk = 1000;
const long long ml = kk * kk;
const long long mod = ml * kk + 7;
const long long inf = ml * ml * ml + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long n;
vector<long long> v;
bool viv = false;
long long C(int n, int k) {
  long long res = 1;
  for (int i = n - k + 1; i <= n; i++) res *= i;
  for (int i = 1; i <= k; i++) res /= i;
  return res;
}
long long f(int n) {
  long long res = 1;
  for (int i = 1; i <= n; i++) res *= i;
  return res;
}
void solve() {
  cin >> n;
  long long ans = C(n, n / 2);
  ans *= f(n / 2 - 1);
  ans *= f(n / 2 - 1);
  ans /= 2;
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) solve();
  return 0;
}

```