Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cassert>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- const ll MOD = 1000000007;
- ll modExp(ll base, ll exp, ll mod = MOD) {
- ll result = 1 % mod;
- base %= mod;
- while(exp > 0) {
- if(exp & 1) result = (result * base) % mod;
- base = (base * base) % mod;
- exp >>= 1;
- }
- return result;
- }
- class Factorials {
- public:
- vector<ll> fact, invFact;
- int n;
- Factorials(int n) : n(n) {
- fact.resize(n + 1);
- invFact.resize(n + 1);
- fact[0] = 1;
- for (int i = 1; i <= n; i++){
- fact[i] = (fact[i - 1] * i) % MOD;
- }
- invFact[n] = modExp(fact[n], MOD - 2, MOD);
- for (int i = n; i >= 1; i--){
- invFact[i - 1] = (invFact[i] * i) % MOD;
- }
- }
- ll binom(int a, int b) {
- if(b < 0 || b > a) return 0;
- return ((fact[a] * invFact[b]) % MOD * invFact[a - b]) % MOD;
- }
- };
- class GoodGraphsSolver {
- public:
- void solve() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int n;
- cin >> n;
- if(n == 1) {
- cout << 1 << "\n";
- return;
- }
- int m = n - 1;
- Factorials fact(m);
- ll F = 0;
- for (int r = 0; r <= m; r++) {
- int x = m - r;
- ll exponent = ((ll)x * (x - 1)) / 2;
- ll ways = modExp(2, exponent, MOD);
- ll term = (fact.binom(m, r) * ways) % MOD;
- if(r % 2 == 1) term = (MOD - term) % MOD;
- F = (F + term) % MOD;
- }
- ll ans = ( (ll)n * F ) % MOD;
- cout << ans << "\n";
- }
- };
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- GoodGraphsSolver solver;
- solver.solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
