记录编号	373178	评测结果	AAAAAAAAAA
题目名称	欧拉图	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.527 s
提交时间	2017-02-20 11:54:48	内存使用	30.87 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <vector>
using namespace std;
#define MAXN 2001
#define MOD 1000000007
typedef long long LL;
LL C[MAXN][MAXN];
LL f[MAXN], g[MAXN];
void pre(int n){
  for(int i = 0; i <= n; i++){
     C[i][0] = 1;
     for(int j = 1; j <= i; j++)
       C[i][j] = (C[i-1][j]+C[i-1][j-1])%MOD;
  }
}
LL pow_mod(LL a, LL x){
  LL r = 1;
  for(a%=MOD; x; x>>=1, a=a*a%MOD)if(x&1)r=r*a%MOD;
  return r;
}
int main(){
  freopen("euler.in", "r", stdin);
  freopen("euler.out", "w", stdout);
  int n; scanf("%d", &n);
  pre(n);
  for(int i = 1; i <= n; i++)f[i] = pow_mod(2, (i-2)*(i-1)/2);
  for(int i = 1; i <= n; i++){
    g[i] = f[i];
    for(int j = 1; j < i; j++)
      g[i] = (((g[i]-C[i-1][j-1]*g[j]%MOD*f[i-j])%MOD)+MOD)%MOD; //√  
  }
  printf("%lld\n", g[n]*(n*(n-1)/2+1)%MOD); //...
  return 0;
}