#include #include #include #include #include #include #include #define pii pair #define INF 100000000 using namespace std; int n, sol; set S; unordered_map viz; inline void Verif() { int minX = INF, minY = INF; set ::iterator it; for(it = S.begin(); it != S.end(); ++it) { minX = min(minX, (*it).first); minY = min(minY, (*it).second); } vector v; v.clear(); for(it = S.begin(); it != S.end(); ++it) v.push_back(make_pair((*it).first - minX, (*it).second - minY)); sort(v.begin(), v.end()); string conf; conf.clear(); for(int i = 0; i < v.size(); ++i) { conf += (char)(v[i].first + 1); conf += (char)(v[i].second + 1); } if(viz[conf] == true) return; viz[conf] = true; sol++; } inline void Back(int pas, int x, int y) { if(S.find(make_pair(x, y)) != S.end()) return; S.insert(make_pair(x, y)); if(pas == n) Verif(); else { Back(pas + 1, x + 1, y); Back(pas + 1, x, y + 1); Back(pas + 1, x - 1, y); Back(pas + 1, x, y - 1); } S.erase(make_pair(x, y)); } int main() { std::ios_base::sync_with_stdio(false); cin >> n; Back(1, 0, 0); cout << sol << "\n"; return 0; }