显示代码纯文本
#ifndef LOCAL_TEST
#include <bits/stdc++.h>
#else
#include "E:\Code\headers.h" // For faster compile
#endif
using namespace std;
// Options Start
// #define NETWORK_FLOW
// #define SEGMENT_TREE
#define FILE_IO
// #define MULTI_TESTS
// Options End
#ifdef LOCAL_TEST
bool __mem_begin;
#endif
#define int long long
#define mid ((l + r) >> 1)
#ifndef LOCAL_TEST
#define endl '\n'
#endif
#ifdef SEGMENT_TREE
#define lson (p << 1)
#define rson (p << 1 | 1)
#endif
#ifdef NETWORK_FLOW
#define rev(p) (p ^ 1)
#endif
const int mod = 10007, G = 3, MAXN = 1e6 + 5;
int n, a[MAXN], b[MAXN], fac[MAXN], inv[MAXN], facinv[MAXN];
int quickpow(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) ret = a * ret % mod;
a = a * a % mod; b >>= 1;
}
return ret;
}
namespace PolyInv {
#define ll long long
#define ull unsigned long long
#define RG register
#define MAX MAXN
#define MOD (10007)
const double Pi=acos(-1);
const int m=sqrt(MOD);
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int fpow(int a,int b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}
struct Complex{double a,b;}W[MAX],A[MAX],B[MAX],C[MAX],D[MAX];
Complex operator+(Complex a,Complex b){return (Complex){a.a+b.a,a.b+b.b};}
Complex operator-(Complex a,Complex b){return (Complex){a.a-b.a,a.b-b.b};}
Complex operator*(Complex a,Complex b){return (Complex){a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}
int r[MAX];
void FFT(Complex *P,int N,int opt)
{
for(int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);
for(int i=1;i<N;i<<=1)
for(int p=i<<1,j=0;j<N;j+=p)
for(int k=0;k<i;++k)
{
Complex w=(Complex){W[N/i*k].a,W[N/i*k].b*opt};
Complex X=P[j+k],Y=P[i+j+k]*w;
P[j+k]=X+Y;P[i+j+k]=X-Y;
}
if(opt==-1)for(int i=0;i<N;++i)P[i].a/=1.0*N;
}
void Multi(int *a,int *b,int len,int *ret)
{
for(int i=0;i<(len<<1);++i)A[i]=B[i]=C[i]=D[i]=(Complex){0,0};
for(int i=0;i<len;++i)
{
a[i]%=MOD;b[i]%=MOD;
A[i]=(Complex){(a[i]/m)*1.0,0};
B[i]=(Complex){(a[i]%m)*1.0,0};
C[i]=(Complex){(b[i]/m)*1.0,0};
D[i]=(Complex){(b[i]%m)*1.0,0};
}
int N,l=0;
for(N=1;N<=len;N<<=1)++l;
for(int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
for(int i=1;i<N;i<<=1)
for(int k=0;k<i;++k)W[N/i*k]=(Complex){cos(k*Pi/i),sin(k*Pi/i)};
FFT(A,N,1);FFT(B,N,1);FFT(C,N,1);FFT(D,N,1);
for(int i=0;i<N;++i)
{
Complex tmp=A[i]*C[i];
C[i]=B[i]*C[i],B[i]=B[i]*D[i],D[i]=D[i]*A[i];
A[i]=tmp;C[i]=C[i]+D[i];
}
FFT(A,N,-1);FFT(B,N,-1);FFT(C,N,-1);
for(int i=0;i<len;++i)
{
ret[i]=0;
ret[i]=(ret[i]+1ll*(ll)(A[i].a+0.5)%MOD*m%MOD*m%MOD)%MOD;
ret[i]=(ret[i]+1ll*(ll)(C[i].a+0.5)%MOD*m%MOD)%MOD;
ret[i]=(ret[i]+1ll*(ll)(B[i].a+0.5)%MOD)%MOD;
ret[i]=(ret[i]+MOD)%MOD;
}
}
int c[MAX],d[MAX];
void Inv(int *a,int *b,int len)
{
if(len==1){b[0]=fpow(a[0],MOD-2);return;}
Inv(a,b,len>>1);
Multi(a,b,len,c);
Multi(c,b,len,d);
for(int i=0;i<len;++i)b[i]=(b[i]+b[i])%MOD;
for(int i=0;i<len;++i)b[i]=(b[i]+MOD-d[i])%MOD;
}
#undef ll
#undef ull
#undef RG
#undef MAX
#undef MOD
}
void work() {
cin >> n;
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = (fac[i - 1] * i) % mod;
facinv[n] = quickpow(fac[n], mod - 2);
for (int i = n - 1; i >= 0; --i)
facinv[i] = facinv[i + 1] * (i + 1) % mod;
a[0] = 1;
// cerr << "3:" << mod - quickpow(quickpow(7366, 9) * 6 % mod, mod - 2) << endl;
// cerr << "=" << quickpow(6646, mod - 2) % mod << endl;
for (int i = 1, fl = -1; i <= n; ++i, fl = -fl)
a[i] = (facinv[i] * quickpow(quickpow(7366, i * i) % mod, mod - 2) % mod * fl % mod + mod) % mod;
// a[0] = 1;
// for (int i = 0; i <= n; ++i)
// cerr << a[i] << ' ';
// cerr << endl;
int N;
for (N = 1; N <= n; N <<= 1);
PolyInv::Inv(a, b, N);
// for (int i = 0; i <= n; ++i)
// cerr << b[i] << ' ';
// cerr << endl;
cout << b[n] * fac[n] % mod * quickpow(7366, n * n) % mod << endl;
}
#ifdef LOCAL_TEST
bool __mem_end;
#endif
signed main(void) {
ios::sync_with_stdio(false); cin.tie(NULL);
srand(time(nullptr));
#ifdef LOCAL_TEST
auto __time_begin = clock();
#endif
#ifdef FILE_IO
#ifndef LOCAL_TEST
freopen("DAG.in", "r", stdin);
freopen("DAG.out", "w", stdout);
#endif
#endif
#ifdef LOCAL_TEST
freopen("E:\\Code\\in.txt", "r", stdin);
freopen("E:\\Code\\out.txt", "w", stdout);
#endif
#ifdef MULTI_TESTS
int T = 1; cin >> T; T--;
while (T--) work();
#endif
work();
#ifdef LOCAL_TEST
auto __time_end = clock();
cerr << "Time: " << __time_end - __time_begin << "ms" << endl;
cerr << "Memory: " << (&__mem_end - &__mem_begin) / 1024 << "KiB" << endl;
#endif
return 0;
}
xiaoququ