جدول های پیچ پیچ کامل

//Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
void debug(int out){ cerr << out << endl; }

#define int long long
#define loop(i , l , r) for (int i = l; i <= r; i++)
#define arc(i , r , l) for (int i = r; i >= l; i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define Turbo ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sep " "
//#define endl "\n"

const int Delta = 1e4+729;
int pw (int base , int e)
{ return e? pw(base*base%Delta,e>>1)*(e&1 ? base:1)%Delta:1; }
int Mod (int base)
{ return (base%Delta + Delta)%Delta; }

void Engine ()
{
    int N; cin >> N;
    int out = Mod(N*pw(2,N*N-(2*N-1)));
    loop(i,0,N-2){
        int way = N-i-1;
        int Not = pw(pw(2,N-2)-1,i);
        int others = pw(2, N*N - ((i+2)*(N-1)+N));
        out = Mod(out - Mod(way*Not*others));
    } cout << out << endl;
}

signed main()
{
    Turbo
    int Tc = 1; //cin >> Tc;
    while (Tc--){ Engine(); }
}