СПЬГУ_J_2

#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;
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;
}

ll var(ll msk, ll num){
    num %= inf;
    //cout<<"msk = "<<two(msk)<<"\n";
    //cout<<"num = "<<num<<"\n";
    if (msk == (1 << n) - 1) 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";
        add = var(msk | (1 << i), num * now) % 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;
    ans = var(0, 1) % inf;
    ans %= inf;
    //cout<<"ans = "<<ans<<"\n";
    cout<<ans<<'\n';
}