-
Notifications
You must be signed in to change notification settings - Fork 0
/
B_Cats_like_permutations.cpp
52 lines (49 loc) · 1.36 KB
/
B_Cats_like_permutations.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
const long double EPS = 1e-14;
const int maxn = 100500;
const int mod = 1e9 + 7;
struct Math{
private: long long f[maxn];
public:
Math(){f[0] = 0;};
long long add(long long x, long long y) {
x += y;
if(x >= mod) x -= mod;
if(x < 0) x += mod;
return x;
}
long long mul(long long x, long long y) { return (add(x, mod) * add(y, mod)) % mod; }
long long fast_pow(long long n, long long k){
if(k == 0) return 1LL;
long long ans = fast_pow(n, k >> 1);
ans = mul(ans, ans);
if(k & 1) ans = mul(n, ans);
return ans;
}
long long inv(long long x) { return fast_pow(x, mod - 2); }
void init_fact(){
f[0] = 1LL;
for(int i = 1 ; i < maxn ; ++i)
f[i] = mul(i, f[i - 1]);
}
long long fact(int x){
assert(x >= 0 && x < maxn);
if(!f[0]) init_fact();
return f[x];
};
}math;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
int od = n / 2, ev = n / 2 + (n & 1);
long long ans = math.mul(math.fact(od), math.fact(ev));
cout << math.mul(2, ans) << ' ';
if(n & 1) cout << ans << '\n';
else cout << math.mul(2, ans) << '\n';
return 0;
}