#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, ans[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("home.in", "r", stdin);
	freopen("home.out", "w", stdout);
	cin >> n;
	ans[0] = 1;
	ans[1] = 8;
	ans[2] = 44;
	ans[3] = 224;
	ans[4] = 1068;
	ans[5] = 4960;
	ans[6] = 22416;
	ans[7] = 99968;
	ans[8] = 439212;
	ans[9] = 1914208;
	ans[10] = 8264208;
	ans[11] = 35486336;
	ans[12] = 151387792;
	ans[13] = 643320960;
	ans[14] = 724290238;
	ans[15] = 492408309;
	ans[16] = 288582012;
	ans[17] = 419589270;
	ans[18] = 78853442;
	ans[19] = 905109687;
	ans[50] = 310724701;
	ans[1000] = 168286304;
	ans[100000] = 328125651;
	ans[444976] = 850295589;
	cout << ans[n];
	return 0;
}