Day4. A (N^2logK)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")

constexpr long long INF = (long long)4e9;
constexpr int N = (int)5e5 + 111;
constexpr int md = (int)1e9 + 7;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr int P = (int)998244343;

//typedef __int128 _uint;
typedef long long ll;

mt19937_64 rnd(time(nullptr));

void add(int& a,int b){
    a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b; while(a < 0) a += md;
}

int bpow(int a,int b){
    if(b == 0)
        return 1;
    if(b % 2 == 0){
        int t = bpow(a,b>>1);
        return 1ll*t*t%md;
    }
    return 1ll * a*bpow(a,b-1) % md;
}

int inv(int a){
    return bpow(a,md-2);
}

//int fac[N],invfac[N];
//
//void init(){
//    fac[0] = 1;
//    for(int i = 1; i < N; i++){
//        fac[i] = (fac[i-1] * i) % md;
//    }
//    invfac[N-1] = inv(fac[N-1]);
//    for(int i = N-2; i >= 0; i--){
//        invfac[i] = (invfac[i+1] * (i+1))%md;
//    }
//    return;
//}
//
//int C(int n,int k){
//    if(k > n)
//        return 0;
//    return fac[n] * invfac[k] % md * invfac[n-k] % md;
//}
//
//int A(int n,int k){
//    if(k > n)
//        return 0;
//    return fac[n] * invfac[n-k] % md;
//}

struct DSU{ /// currently there is dsu on array
    vector<int> parent;
    vector<int> sz;
    vector<int> deep;
    DSU(){}
    DSU(int n){
        n = n+10;
        parent.resize(n);
        sz.resize(n);
        deep.resize(n);
        for(int i = 0; i < n; i++)
            parent[i] = i, sz[i] = 1,deep[i] = 0;
    }
    int get(int x){
        return parent[x] == x ? x : parent[x] = get(parent[x]);
    }
    void union_sets(int a,int b){
        a = get(a), b = get(b);
        if(a == b)
            return;
//        #warning DSU is written badly
        if(deep[b] > deep[a])
            swap(a,b);
        parent[a] = b;
        deep[b] = max(deep[b],deep[a]+1);
        sz[b] += sz[a];
        return;
    }
    bool connected(int a,int b){
        return get(a) == get(b);
    }
};

vector<vector<int>> subMatrix(int x1,int y1,int x2,int y2,vector<vector<int>>& gr){
    vector<vector<int>> ans;
    if(y1 > y2)
        swap(y1,y2);
    if(x1 > x2)
        swap(x1,x2);
    for(int i = x1; i <= x2; i++){
        ans.pb(vector<int>());
        for(int j = y1; j <= y2; j++){
            ans.back().pb(gr[i][j]);
        }
    }
    return ans;
}

bool ok(vector<vector<int>> gr){
    int n = gr.size();
//    cerr << "n = " << n << "\n";
//    for(auto& x : gr){
//        for(auto& y : x)
//            cout << y << " ";
//        cout << "\n";
//    }
    if(n == 1)
        return true;
//    cerr << "+ok\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            assert(n-1-i >= 0);
            assert(n-1-j >= 0);
            assert(n-1-j < n);
            assert(n-1-i < n);
            if(gr[i][j] != gr[j][i])
                return false;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n-i; j++){
            if(gr[i][j] != gr[n-j-1][n-i-1])
                return false;
        }
    }
    int d = (n+1)/2;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n/2; j++){
            if(gr[i][j] != gr[i][j+d])
                return false;
        }
    }
    for(int i = 0; i < n/2; i++){
        for(int j = 0; j < n; j++){
            if(gr[i][j] != gr[i+d][j])
                return false;
        }
    }
    d = n/2;
//    cerr << "-ok\n";
    auto g1 = subMatrix(0,0,d-1,d-1,gr);
    if(!ok(g1))
        return false;
    auto g2 = subMatrix(n-1-d+1,n-d,n-1,n-1,gr);
    if(!ok(g2))
        return false;
    auto g3 = subMatrix(0,n-1,d-1,n-d,gr);
    if(!ok(g3))
        return false;
    auto g4 = subMatrix(n-1,0,n-d,d-1,gr);
    if(!ok(g4))
        return false;
    assert(g1 == g2 && g2 == g3 && g3 == g4);
    return true;
}
int n;
int g[30][30];

int val(vector<vector<int>>& gr){
    int ans = 0;
    for(int i = 0; i < gr.size(); i++){
        for(int j = 0; j < gr[i].size(); j++){
            ans = (ans << 1) + gr[i][j];
            ans %= md;
        }
    }
    return ans;
}

vector<int> v;

void rec(int x,int y){
    if(y == n){
        y = 0;
        x++;
    }
    if(x == n){
        vector<vector<int>> gr;
        for(int i = 0; i < n; i++){
            gr.pb(vector<int>());
            for(int j = 0; j < n; j++){
                gr.back().pb(g[i][j]);
            }
        }
        if(ok(gr)){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    cout << g[i][j] << " ";
                }
                cout << "\n";
            }
            cout << "val = " << val(gr) << "\n";
            cout << "\n";
            v.pb(val(gr));
        }
        return;
    }
    g[x][y] = 0;
    rec(x,y+1);
    g[x][y] = 1;
    rec(x,y+1);
    return;
}

//int n,m;
//vector<int> inc(vector<int> A,int d){
//    for(auto& x : A)
//        x = (x + d) % m;
//    return A;
//}
//
//vector<int> arr(int k){
//    if(k == 0)
//        return vector<int>{0};
//    vector<int> A = arr(k-1);
//    vector<int> ans;
//    for(int i = 0; i < m; i++){
//        auto t = inc(A,i);
//        for(auto& x : t)
//            ans.pb(x);
//    }
//    return ans;
//}

string divide8(string& s){
    for(int i = 0; i < 2 && !s.empty(); i++){
        s.pop_back();
    }
    if(s == "")
        s = "0";
    return s;
}

int getRem8(string& s){
    int r = 0;
    int n = s.size();
    for(int i = 1; i >= 0; i--){
        r = 2*r;
        if(n - 1 - i >= 0)
            r += s[n-1-i] - '0';
    }
    return r;
}

vector<vector<int>> make(vector<vector<int>>& t){
    vector<vector<int>> ans;
    int n = t.size();
    ans = t;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ans[i].pb(ans[i][j]);
        }
    }
    for(int i = 0; i < n; i++){
        ans.pb(ans[i]);
    }
    return ans;
}

vector<vector<int>> get(int n,string s){
//    cerr << "n = " << n << ", k = " << s << "\n";;
    if(n == 1){
        if(s == "1")
            return vector<vector<int>>{{1}};
        else
            return vector<vector<int>>{{0}};
    }
    if(n % 2 == 0){
//        cerr << "ok2+ " << n << "\n";
        auto t = get(n>>1,s);
//        cerr << "ok2- " << n << "\n";
        return make(t);
    }
    int r = getRem8(s);
    r %= 4;
//    cerr << "ok+ " << n << "\n";
    auto t = get(n>>1,divide8(s));
//    cerr << "ok- " << n << "\n";
//    cerr << "r = " << r << "\n";
    if(r == 0){
        vector<vector<int>> ans;
        int nn = t.size();
        ans = t;
        for(int i = 0; i < nn; i++){
            ans[i].pb(0);
            for(int j = 0; j < nn; j++){
                ans[i].pb(ans[i][j]);
            }
        }
        ans.pb(vector<int>(n,0));
        for(int i = 0; i < nn; i++){
            ans.pb(ans[i]);
        }
        return ans;
    }
    if(r == 1){
        vector<vector<int>> ans;
        int nn = t.size();
        ans = t;
        for(int i = 0; i < nn; i++){
            ans[i].pb(0);
            for(int j = 0; j < nn; j++){
                ans[i].pb(ans[i][j]);
            }
        }
        ans.pb(vector<int>(n,0));
        for(int i = 0; i < nn; i++){
            ans.pb(ans[i]);
        }
        ans[nn][nn] = 1;
//        cerr << "o!\n";
        return ans;
    }
    if(r == 2){
        vector<vector<int>> ans;
        int nn = t.size();
        ans = t;
        for(int i = 0; i < nn; i++){
            ans[i].pb(1);
            for(int j = 0; j < nn; j++){
                ans[i].pb(ans[i][j]);
            }
        }
        ans.pb(vector<int>(n,1));
        for(int i = 0; i < nn; i++){
            ans.pb(ans[i]);
        }
        ans[nn][nn] = 0;
        return ans;
    }
    if(r == 3){
        vector<vector<int>> ans;
        int nn = t.size();
        ans = t;
        for(int i = 0; i < nn; i++){
            ans[i].pb(1);
            for(int j = 0; j < nn; j++){
                ans[i].pb(ans[i][j]);
            }
        }
        ans.pb(vector<int>(n,1));
        for(int i = 0; i < nn; i++){
            ans.pb(ans[i]);
        }
        return ans;
    }
    assert(false);
    return {};
}

void decrease1(string& s){
    for(int i = s.size()-1; i >= 0; i--){
        if(s[i] == '0'){
            s[i] = '1';
            continue;
        } else {
            s[i] = '0';
            break;
        }
    }
    if(s[0] == '0')
        s.erase(0,1);
    if(s == "")
        s = "0";
    return;
}

void solve(){
//    cin >> n >> m;
//
//    auto v = arr(n);
//
//    for(auto& x : v){
//        cout << x << " ";
//    }
//    cout << "\n";

    string k;
    cin >> n;
    rec(0,0);
    sort(v.begin(),v.end());
    for(auto& x : v)
        cout << x << " ";
    cout << "\n";
    return;
//    cin >> k;
    decrease1(k);

    auto gr = get(n,k);
    int ans = 0;
    assert(gr.size() == n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
//            cout << gr[i][j] << " ";
            ans = 2 * ans + gr[i][j];
            ans %= md;
        }
//        cout << "\n";
    }
    cout << ans << "\n";
    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
//        cerr << "test = " << test << "\n";
        solve();
    }
    return 0;
}
/**
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
val = 0

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
val = 4096

0 0 1 0 0
0 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
val = 4353156

0 0 1 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 0 0
0 0 1 0 0
val = 4357252

1 1 0 1 1
1 1 0 1 1
0 0 0 0 0
1 1 0 1 1
1 1 0 1 1
val = 29197179

1 1 0 1 1
1 1 0 1 1
0 0 1 0 0
1 1 0 1 1
1 1 0 1 1
val = 29201275

1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
val = 33550335

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
val = 33554431

0 4096 4353156 4357252 29197179 29201275 33550335 33554431
**/