Problem E

#define _CRT_SECURE_NO_DEPRECATE
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#include <cstring>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 3.1415926535897932384626433832795028841971
#define mp make_pair
#define x first
#define y second
#define pii pair<int,int>
//#define pdd pair<double,double>
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).size())
#define C(a) memset((a),0,sizeof(a))
#define VI vector <int>
#define ll long long
#define problem "factorial"

struct pdd {
    double x, y;
    pdd() : x(0), y(0) {}
    pdd(double _x, double _y) : x(_x), y(_y) {}
};
inline pdd operator -(const pdd &a, const pdd &b) {
    return pdd(a.x - b.x, a.y - b.y);
}
inline pdd operator +(const pdd &a, const pdd &b) {
    return pdd(a.x + b.x, a.y + b.y);
}
inline pdd operator *(const pdd &a, const pdd &b) {
    return pdd(a.x * b.x - a.y * b.y, a.x * b.y + b.x * a.y);
}
const int N = 1 << 17;
int a,b,c,d,i,j,n,m,k;
int rv[20][N + 1];

pdd root1[N + 1], root2[N + 1];
pdd ta[N + 1], tb[N + 1];

const int MOD = 1000;
void fft(pdd *a, int n, pdd * root) {
    int l = 0;
    while ((1 << l) < n) ++l;
    rept(i, n) {
        if (rv[l][i] < i) swap(a[i], a[rv[l][i]]);
    }

    int mul = N / n;
    for (int cur = 2; cur <= n; cur *= 2) {
        int d = (n / cur) * mul;
        int half = cur / 2;
        for (int pos = 0; pos < n; pos += cur) {
            rept(i, half) {
                pdd v1 = a[pos + i], v2 = root[i * d] * a[pos + i + half];
                a[pos + i] = v1 + v2;
                a[pos + i + half] = v1 - v2;
            }
        }
    }

    if (root == root2) {
        rept(i, n) {
            a[i].x /= n;
            a[i].y /= n;
        }
    }
}

inline void normalize(VI &res) {
    rept(i, L(res)) {
        if (res[i] >= MOD && i + 1 >= L(res)) res.pb(0);
        if (res[i] >= MOD) {
            res[i + 1] += res[i] / MOD;
            res[i] %= MOD;
        }
    }
    while (L(res) > 1 && res.back() == 0) res.ppb();
}

inline void normalize(vector<ll> &res) {
    rept(i, L(res)) {
        if (res[i] >= MOD && i + 1 >= L(res)) res.pb(0);
        if (res[i] >= MOD) {
            res[i + 1] += res[i] / MOD;
            res[i] %= MOD;
        }
    }
    while (L(res) > 1 && res.back() == 0) res.ppb();
}

vector<ll> tmp;
inline void mul(const VI &a, const VI &b, VI &res) {
    if (L(a) <= 8 && L(b) <= 8) {
        res.resize(L(a) + L(b));
        rept(i, L(a)) {
            rept(j, L(b)) {
                res[i + j] += a[i] * b[j];
            }
        }

        normalize(res);
        return;
    }

    int t = 1;
    while (t < L(a) || t < L(b)) t *= 2;
    t *= 2;
    rept(i, t) {
        if (i >= L(a)) ta[i] = pdd(0, 0); else
        ta[i] = pdd(a[i], 0);
        if (i >= L(b)) tb[i] = pdd(0, 0); else
        tb[i] = pdd(b[i], 0);
    }

    fft(ta, t, root1);
    fft(tb, t, root1);

    rept(i, t) ta[i] = ta[i] * tb[i];

    fft(ta, t, root2);
    tmp.resize(t);
    rept(i, t) {
        tmp[i] = (ll)(ta[i].x + 0.5);
    }
    normalize(tmp);
    res.resize(L(tmp));
    rept(i, L(tmp)) res[i] = tmp[i];
}
void calc(VI coef, VI &ans) {
    if (coef.empty()) {
        ans.resize(1);
        ans[0] = 1;
        return;
    }
    if (L(coef) == 1) {
        ans.resize(1);
        ans[0] = coef[0];
        return;
    }

    VI c1, c2;
    c1.resize((L(coef) + 1) / 2);
    c2.resize(L(coef) / 2);
    rept(i, L(coef)) {
        if (i % 2) c2[i / 2] = coef[i]; else
        c1[i / 2] = coef[i];
    }

    VI a1, a2;
    calc(c1, a1);
    calc(c2, a2);

    mul(a1, a2, ans);
}
int main() {
    rv[0][0] = 0;
    rept(i, 17) {
        rept(j, 1 << i) {
            rv[i + 1][j | 1 << i] = rv[i][j] * 2 + 1;
            rv[i + 1][j] = rv[i][j] * 2;
        }
    }
    rept(i, N) {
        root1[i] = pdd(cos(2.0 * pi * i / N), sin(2.0 * pi * i / N));
        root2[i] = pdd(cos(2.0 * pi * i / N), -sin(2.0 * pi * i / N));
    }
    freopen(problem ".in","r",stdin);
    freopen(problem ".out","w",stdout);
    VI ans, coef;
    scanf("%d", &n);
    rep(i, n) coef.pb(i);

    calc(coef, ans);
    FORD(i, L(ans) - 1, 0) {
        if (i == L(ans) - 1) printf("%d", ans[i]); else
        printf("%03d", ans[i]);
    }
    printf("\n");
}