СПБГУ_J_visual

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
using namespace std;
using ll = long long;
using ld = long double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

ll n=3;
ll ans = 0;
ll inf = 1e9 + 7;
string two(ll x){
    string r = "";
    while (x > 0){
        r += x % 2 + 48;
        x /= 2;
    }
    reverse(r.begin(), r.end());
    while (r.size() < n){
        r = '0' + r;
    }
    return r;
}

ll zer(ll x, ll id){
    string s = two(x);
    //cout<<"s = "<<s<<'\n';
    id = n - id - 1;
    //cout<<"id = "<<id<<'\n';
    ll r = 0;
    for (int i = 0; i < id;++i){//cout<<"i = "<<i<<' ';
        if (s[i] == '0')r++;
    }//cout<<'\n';
    return r;
}

void cs(string s){
    for (int i = 0;i<n;++i){
        for (int j=0;j< n;++j){
            cout<<s[i*n + j];
        }cout<<"\n";
    }cout<<"\n";
}

void cvs(vector <string> v){
    for (auto x: v)cout<<x<<"\n";
    cout<<"\n";
}

ll zer_s(string s, ll id){
    //cout<<"s = "<<s<<'\n';
    id = n - id - 1;
    //cout<<"id = "<<id<<'\n';
    ll r = 0;
    for (int i = 0; i < id;++i){//cout<<"i = "<<i<<' ';
        if (s[i] == '0')r++;
    }//cout<<'\n';
    return r;
}


void vis(string s){
    int id = s[s.size() - 1] - 48;
    int z = zer_s(s, id);
    cout<<"n - "<<z+1<<"\n";
    //cout<<s<<"\n";
    //cout<<"id = "<<id<<"\n";
    //cout<<"z = "<<z<<"\n";
    //cout<<"\n";
    //cout<<"n "<<
}


void sh(vector <string> v){//последний символ каждой строки - индекс нового подарка, который мы добавляли -- по этому индексу и нужно расчитывать кол-во вариантов
    for (auto s: v){
        vis(s);
    }
    cout<<"\n";
}

ll pos=0;

ll var(ll msk, ll num, vector <string> s){
    num %= inf;
    //cout<<"msk = "<<two(msk)<<"\n";
    //cout<<"num = "<<num<<"\n";
    if (msk == (1 << n) - 1) {
        //cs(s);
        //cvs(s);
        pos++;
        //sh(s);
        return num;
    }
    ll pl=0, now,z, add;
    for (ll i = 0; i < n; ++i){
        //cout<<"i = "<<i<<'\n';
        if ( (msk & (1<<i)) != 0) {
                //cout<<"skip\n";
                continue;
        }
        z = zer(msk | (1<<i), i);
        //cout<<"z = "<<z<<"\n";
        now = pow(2, n - z - 1);
        now %= inf;
        //cout<<"now = "<<now<<"\n";
        //cout<<two(msk | (1 << i))<<"\n";
        vector <string> v = s;
        int ix = i;
        char l = ix + 48;
        v.push_back(two(msk | 1<<i) + l);
        add = var(msk | (1 << i), num * now, v ) % inf;
        add %= inf;
        pl += add;
        pl %= inf;
    }
    //cout<<"\n";
    return pl;
    //cout<<"\n";
}


int main()
{
    /*ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);*/
	cin>>n;
	vector <string> v;
	ll x = var(0, 1,v);
	cout<<"pos = "<<pos<<"\n";
	cout<<"res = "<<x<<"\n";
	//cout<<"x = "<<x<<"\n";
}