include

define pb push_back

define nl puts ("")

define sp printf ( " " )

define phl printf ( "hello\n" )

define ff first

define ss second

define POPCOUNT __builtin_popcountll

define RIGHTMOST __builtin_ctzll

define LEFTMOST(x) (63-__builtin_clzll((x)))

define MP make_pair

define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)

define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)

define CLR(x,y) memset(x,y,sizeof(x))

define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())

define MIN(a,b) ((a)<(b)?(a):(b))

define MAX(a,b) ((a)>(b)?(a):(b))

define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)

define SQ(x) ((x)*(x))

define ABS(x) ((x)<0?-(x):(x))

define FABS(x) ((x)+eps<0?-(x):(x))

define ALL(x) (x).begin(),(x).end()

define LCM(x,y) (((x)/gcd((x),(y)))*(y))

define SZ(x) ((vlong)(x).size())

define NORM(x) if(x>=mod)x-=mod;

using namespace std;

typedef long long vlong; typedef unsigned long long uvlong; typedef pair < int, int > pii; typedef pair < vlong, vlong > pll; typedef vector vii; typedef vector vi;

const vlong inf = 2147383647; const double pi = 2 * acos ( 0.0 ); const double eps = 1e-9;

ifdef forthright48

 #include <ctime>
 clock_t tStart = clock();
 #define debug(args...) {dbg,args; cerr<<endl;}
 #define timeStamp printf("Execution Time: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC)

else

#define debug(args...)  // Just strip off all debug tokens
#define timeStamp

endif

struct debugger{ template debugger& operator , (const T& v){ cerr<

//int knightDir[8][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{-1,-2},{1,-2},{-2,-1} }; //int dir4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

inline vlong gcd ( vlong a, vlong b ) { a = ABS ( a ); b = ABS ( b ); while ( b ) { a = a % b; swap ( a, b ); } return a; }

vlong ext_gcd ( vlong A, vlong B, vlong *X, vlong *Y ){ vlong x2, y2, x1, y1, x, y, r2, r1, q, r; x2 = 1; y2 = 0; x1 = 0; y1 = 1; for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) { q = r2 / r1; r = r2 % r1; x = x2 - (q * x1); y = y2 - (q * y1); } *X = x2; *Y = y2; return r2; }

inline vlong modInv ( vlong a, vlong m ) { vlong x, y; ext_gcd( a, m, &x, &y ); if ( x < 0 ) x += m; //modInv is never negative return x; }

inline vlong power ( vlong a, vlong p ) { vlong res = 1, x = a; while ( p ) { if ( p & 1 ) res = ( res * x ); x = ( x * x ); p >>= 1; } return res; }

inline vlong bigmod ( vlong a, vlong p, vlong m ) { vlong res = 1 % m, x = a % m; while ( p ) { if ( p & 1 ) res = ( res * x ) % m; x = ( x * x ) % m; p >>= 1; } return res; }

/*********Template Ends Here*********/ vlong fact[201000], inv[201000], two[200010]; int mod = 1000000007; void precal() { fact[0] = 1; inv[0] = modInv( 1, mod );

two[0] = modInv( 1, mod );
int temp = modInv( 2, mod );

FOR(i,1,200010) {
    fact[i] = ( fact[i-1] * i ) % mod;
    inv[i] = modInv( fact[i], mod );

    two[i] = ( two[i-1] * temp ) % mod;
}

}

int main () { precal();

int kase;
scanf ( "%d", &kase );

assert ( kase > 0 && kase <= 100000 );

while ( kase-- ) {
    int m, a;
    scanf ( "%d %d", &m, &a );

    assert ( m >= 1 && m <= 100000 && a >= 0 && a <= 100000 );

    vlong res = ( fact[a+m+1] * inv[a+2] ) % mod;
    res = ( res * res ) % mod;
    res = ( res * ( ( (a+2) * (a+m+2) ) % mod ) ) % mod;
    res = ( res * two[m] ) % mod;

    printf ( "%lld\n", res );
}


return 0;

}

Hi,

thank's for this nice excercise. I just have one plea:

I put a lot of effort in solving this challenge. After getting timouts on every trial, I even started to use a caching approach to cach partial calculations, but in the end I recognized, that I still got timeouts. And I mean, almost every test case encountered a timeout.

In the end I downloaded one of the test cases because I couldn't explain this behaviour myself. After also putting another big time in profiling, I finally recognized, that about 90% or more of the runtime was consumed by the printing logic, which I can't even influence.

I would ask you, to overthink the timing restrictons you use. They seem to be very irrealistic for python3! On my machine, which is a Athlon (about 7 to 8 years old), test case runs in about 0,3 seconds if y disabble the print-messages (without formatting options!) and over 3 seconds if I activate them (btw. to get the 3 seconds, I even redirect stdout to > /dev/null, so it is not a matter of text scrolling in a terminal, which consumes the time!!!).

So I would really say, that your timinig restrictions for Python are irrealistic, except for, you expect the programmer to optimize the print performance as well).

Kind regards Jott