#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
#define Chtholly std::set<node>::iterator
using i64 = int;
using u64 = unsigned long long;
using pii = std::pair<int,int>;

int read() {
	int s = 0;
	bool f = false;
	char c = getchar();
	for(;c < '0'||c > '9';c = getchar())
		if(c == '-')
			f = true;
	for(;c >= '0'&&c <= '9';c = getchar())
		s = (s << 1) + (s << 3) + (c ^ '0');
	return f ? -s : s;
}

const int maxn = 5e3 + 5;
const i64 mod = 1e4 + 7;
void add(i64& x,i64 y) {x += y;if(x >= mod)x -= mod;return ;}
void sub(i64& x,i64 y) {x -= y;if(x < 0)x += mod;return ;}
i64 inc(i64 x,i64 y) {return (x + y) >= mod ? (x + y - mod) : (x + y);}
i64 dec(i64 x,i64 y) {return (x - y) < 0 ? (x - y + mod) : (x - y);}
i64 power(i64 x,i64 y) {i64 ans = 1;for(;y;y >>= 1) {if(y & 1)(ans *= x) %= mod;(x *= x) %= mod;}return ans;}
int fac[maxn],inv[maxn],f[maxn],n,sgn[maxn],pw[maxn * maxn];

int C(int n,int m) {
	if(n < m||n < 0||m < 0)
		return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main() {
	freopen("DAG.in","r",stdin);
	freopen("DAG.out","w",stdout);
	n = read();
	fac[0] = pw[0] = sgn[1] = 1;
	for(int i = 2;i <= n;++ i)
		sgn[i] = mod - sgn[i - 1];
	for(int i = 1;i <= n * n;++ i)
		pw[i] = 2ll * pw[i - 1] % mod;
	for(int i = 1;i <= n;++ i)
		fac[i] = 1ll * i * fac[i - 1] % mod;
	inv[n] = power(fac[n] , mod - 2);
	for(int i = n - 1;~ i;-- i)
		inv[i] = 1ll * (i + 1) * inv[i + 1] % mod;
	f[0] = 1;
	for(int i = 1;i <= n;++ i)
		for(int j = 1;j <= i;++ j)
			add(f[i] , 1ll * f[i - j] * pw[j * (i - j)] % mod * C(i , j) % mod * sgn[j] % mod);
	printf("%d\n",f[n]);
	return 0;
}