# HE April Circuits 2A - Bear and All Permutations ( Bigint )

https://www.hackerearth.com/april-circuits/algorithm/2a-bear-and-all-permutations-1/
We can simply simulate for each answer since n is only up to 12. However, it still takes a lot of time, and the number is extremely large, we will have to precompute locally. It takes really a lot of time, but since this is a long duration competition, guess this is it.
UPDATE: Seems that some bugs exist, and a workaround is to set everything into long long.

```#include <bits/stdc++.h>
using namespace std;
const int base = 1000000000;
const int base_digits = 9;

struct bigint {
vector<int> a;
int sign;

bigint() :
sign ( 1 ) {
}

bigint ( long long v ) {
*this = v;
}

bigint ( const string &s ) {
}

void operator= ( const bigint &v ) {
sign = v.sign;
a = v.a;
}

void operator= ( long long v ) {
sign = 1;
if ( v < 0 )
sign = -1, v = -v;
for ( ; v > 0; v = v / base )
a.push_back ( v % base );
}

bigint operator+ ( const bigint &v ) const {
if ( sign == v.sign ) {
bigint res = v;

for ( int i = 0, carry = 0; i < ( int ) max ( a.size(), v.a.size() ) || carry; ++i ) {
if ( i == ( int ) res.a.size() )
res.a.push_back ( 0 );
res.a[i] += carry + ( i < ( int ) a.size() ? a[i] : 0 );
carry = res.a[i] >= base;
if ( carry )
res.a[i] -= base;
}
return res;
}
return *this - ( -v );
}

bigint operator- ( const bigint &v ) const {
if ( sign == v.sign ) {
if ( abs() >= v.abs() ) {
bigint res = *this;
for ( int i = 0, carry = 0; i < ( int ) v.a.size() || carry; ++i ) {
res.a[i] -= carry + ( i < ( int ) v.a.size() ? v.a[i] : 0 );
carry = res.a[i] < 0;
if ( carry )
res.a[i] += base;
}
res.trim();
return res;
}
return - ( v - *this );
}
return *this + ( -v );
}

void operator*= ( int v ) {
if ( v < 0 )
sign = -sign, v = -v;
for ( int i = 0, carry = 0; i < ( int ) a.size() || carry; ++i ) {
if ( i == ( int ) a.size() )
a.push_back ( 0 );
long long cur = a[i] * ( long long ) v + carry;
carry = ( int ) ( cur / base );
a[i] = ( int ) ( cur % base );
//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
}
trim();
}

bigint operator* ( int v ) const {
bigint res = *this;
res *= v;
return res;
}

friend pair<bigint, bigint> divmod ( const bigint &a1, const bigint &b1 ) {
int norm = base / ( b1.a.back() + 1 );
bigint a = a1.abs() * norm;
bigint b = b1.abs() * norm;
bigint q, r;
q.a.resize ( a.a.size() );

for ( int i = a.a.size() - 1; i >= 0; i-- ) {
r *= base;
r += a.a[i];
int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
int d = ( ( long long ) base * s1 + s2 ) / b.a.back();
r -= b * d;
while ( r < 0 )
r += b, --d;
q.a[i] = d;
}

q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim();
r.trim();
return make_pair ( q, r / norm );
}

bigint operator/ ( const bigint &v ) const {
return divmod ( *this, v ).first;
}

bigint operator% ( const bigint &v ) const {
return divmod ( *this, v ).second;
}

void operator/= ( int v ) {
if ( v < 0 )
sign = -sign, v = -v;
for ( int i = ( int ) a.size() - 1, rem = 0; i >= 0; --i ) {
long long cur = a[i] + rem * ( long long ) base;
a[i] = ( int ) ( cur / v );
rem = ( int ) ( cur % v );
}
trim();
}

bigint operator/ ( int v ) const {
bigint res = *this;
res /= v;
return res;
}

int operator% ( int v ) const {
if ( v < 0 )
v = -v;
int m = 0;
for ( int i = a.size() - 1; i >= 0; --i )
m = ( a[i] + m * ( long long ) base ) % v;
return m * sign;
}

void operator+= ( const bigint &v ) {
*this = *this + v;
}
void operator-= ( const bigint &v ) {
*this = *this - v;
}
void operator*= ( const bigint &v ) {
*this = *this * v;
}
void operator/= ( const bigint &v ) {
*this = *this / v;
}

bool operator< ( const bigint &v ) const {
if ( sign != v.sign )
return sign < v.sign;
if ( a.size() != v.a.size() )
return a.size() * sign < v.a.size() * v.sign;
for ( int i = a.size() - 1; i >= 0; i-- )
if ( a[i] != v.a[i] )
return a[i] * sign < v.a[i] * sign;
return false;
}

bool operator> ( const bigint &v ) const {
return v < *this;
}
bool operator<= ( const bigint &v ) const {
return ! ( v < *this );
}
bool operator>= ( const bigint &v ) const {
return ! ( *this < v );
}
bool operator== ( const bigint &v ) const {
return ! ( *this < v ) && ! ( v < *this );
}
bool operator!= ( const bigint &v ) const {
return *this < v || v < *this;
}

void trim() {
while ( !a.empty() && !a.back() )
a.pop_back();
if ( a.empty() )
sign = 1;
}

bool isZero() const {
return a.empty() || ( a.size() == 1 && !a[0] );
}

bigint operator-() const {
bigint res = *this;
res.sign = -sign;
return res;
}

bigint abs() const {
bigint res = *this;
res.sign *= res.sign;
return res;
}

long long longValue() const {
long long res = 0;
for ( int i = a.size() - 1; i >= 0; i-- )
res = res * base + a[i];
return res * sign;
}

friend bigint gcd ( const bigint &a, const bigint &b ) {
return b.isZero() ? a : gcd ( b, a % b );
}
friend bigint lcm ( const bigint &a, const bigint &b ) {
return a / gcd ( a, b ) * b;
}

void read ( const string &s ) {
sign = 1;
a.clear();
int pos = 0;
while ( pos < ( int ) s.size() && ( s[pos] == '-' || s[pos] == '+' ) ) {
if ( s[pos] == '-' )
sign = -sign;
++pos;
}
for ( int i = s.size() - 1; i >= pos; i -= base_digits ) {
int x = 0;
for ( int j = max ( pos, i - base_digits + 1 ); j <= i; j++ )
x = x * 10 + s[j] - '0';
a.push_back ( x );
}
trim();
}

friend istream& operator>> ( istream &stream, bigint &v ) {
string s;
stream >> s;
return stream;
}

friend ostream& operator<< ( ostream &stream, const bigint &v ) {
if ( v.sign == -1 )
stream << '-';
stream << ( v.a.empty() ? 0 : v.a.back() );
for ( int i = ( int ) v.a.size() - 2; i >= 0; --i )
stream << setw ( base_digits ) << setfill ( '0' ) << v.a[i];
return stream;
}

static vector<int> convert_base ( const vector<int> &a, int old_digits, int new_digits ) {
vector<long long> p ( max ( old_digits, new_digits ) + 1 );
p[0] = 1;
for ( int i = 1; i < ( int ) p.size(); i++ )
p[i] = p[i - 1] * 10;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for ( int i = 0; i < ( int ) a.size(); i++ ) {
cur += a[i] * p[cur_digits];
cur_digits += old_digits;
while ( cur_digits >= new_digits ) {
res.push_back ( int ( cur % p[new_digits] ) );
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.push_back ( ( int ) cur );
while ( !res.empty() && !res.back() )
res.pop_back();
return res;
}

typedef vector<long long> vll;

static vll karatsubaMultiply ( const vll &a, const vll &b ) {
int n = a.size();
vll res ( n + n );
if ( n <= 32 ) {
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < n; j++ )
res[i + j] += a[i] * b[j];
return res;
}

int k = n >> 1;
vll a1 ( a.begin(), a.begin() + k );
vll a2 ( a.begin() + k, a.end() );
vll b1 ( b.begin(), b.begin() + k );
vll b2 ( b.begin() + k, b.end() );

vll a1b1 = karatsubaMultiply ( a1, b1 );
vll a2b2 = karatsubaMultiply ( a2, b2 );

for ( int i = 0; i < k; i++ )
a2[i] += a1[i];
for ( int i = 0; i < k; i++ )
b2[i] += b1[i];

vll r = karatsubaMultiply ( a2, b2 );
for ( int i = 0; i < ( int ) a1b1.size(); i++ )
r[i] -= a1b1[i];
for ( int i = 0; i < ( int ) a2b2.size(); i++ )
r[i] -= a2b2[i];

for ( int i = 0; i < ( int ) r.size(); i++ )
res[i + k] += r[i];
for ( int i = 0; i < ( int ) a1b1.size(); i++ )
res[i] += a1b1[i];
for ( int i = 0; i < ( int ) a2b2.size(); i++ )
res[i + n] += a2b2[i];
return res;
}

bigint operator* ( const bigint &v ) const {
vector<int> a6 = convert_base ( this->a, base_digits, 6 );
vector<int> b6 = convert_base ( v.a, base_digits, 6 );
vll a ( a6.begin(), a6.end() );
vll b ( b6.begin(), b6.end() );
while ( a.size() < b.size() )
a.push_back ( 0 );
while ( b.size() < a.size() )
b.push_back ( 0 );
while ( a.size() & ( a.size() - 1 ) )
a.push_back ( 0 ), b.push_back ( 0 );
vll c = karatsubaMultiply ( a, b );
bigint res;
res.sign = sign * v.sign;
for ( int i = 0, carry = 0; i < ( int ) c.size(); i++ ) {
long long cur = c[i] + carry;
res.a.push_back ( ( int ) ( cur % 1000000 ) );
carry = ( int ) ( cur / 1000000 );
}
res.a = convert_base ( res.a, 6, base_digits );
res.trim();
return res;
}
};
/* ----- template for bigint ----- */

typedef long long ll;
const int MOD = 1e9 + 7;

int pre_gcd[ 13 ][ 13 ];
vector< string > precomputed_ans = { "1","1","2","8","68","1504","127792","57140352","258023200384","10151395367145472","3673835865235792306176","13318668301694192513859649536","531680718673514734573555796872790016" };
bigint sol[ 13 ];

void preSolve(){
for( int i = 1; i <= 12; ++i ){
sol[ i ] = 0;
vector< int > vec;
for( int j = 1; j <= i; ++j )
vec.push_back( j );
do{
bigint prod = 1;
for( int j = 0; j < i; ++j )
for( int k = j + 1; k < i; ++k )
prod *= pre_gcd[ k - j ][ abs( vec[ k ] - vec[ j ] ) ];
sol[ i ] += prod;
} while( next_permutation( vec.begin(), vec.end() ) );
cout << "sol[ " << i << " ] = " << sol[ i ] << endl;
}
}

int main(){
for( int i = 1; i <= 12; ++i )
sol[ i ] = precomputed_ans[ i ];
int T; cin >> T;
while( T-- ){
int n, m; cin >> n >> m;
cout << sol[ n ] % m << "\n";
}
return 0;
// precomputed locally
for( int i = 1; i <= 12; ++i )
for( int j = 1; j <= 12; ++j )
pre_gcd[ i ][ j ] = __gcd( i, j );
preSolve();
return 0;
}
```