#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
//#define p 2173412051LL
//#define sz 2

using namespace std;

template< typename T > void read( T &x ) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while( !isdigit( ch ) ) {
        if( ch == '-' )
        f *= -1;
        ch = getchar();
    }
    while( isdigit( ch ) ) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

struct custom_hash {
    static uint64_t splitmix64( uint64_t x ) {
        x += 0x9e3779b97f4a7c15;
        x = ( x ^ ( x >> 30 ) ) * 0xbf58476d1ce4e5b9;
        x = ( x ^ ( x >> 27 ) ) * 0x94d049bb133111eb;
        return x ^ ( x >> 31 );
    }

    size_t operator() ( uint64_t x ) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64( x + FIXED_RANDOM );
    }
};

const ll p = 1e9 + 7;

map< int, int > mp;

void init();
ll fac( ll );
ll inv( ll );
ll pow_mod( ll, ll );

int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 ), cout.tie( 0 );
    init();
    int t;
    cin >> t;
    while( t-- ) {
        string s;
        ll n;
        cin >> n >> s;
        n -= s.size();
        if( n & 1 ) {
            cout << 0 << '\n';
            continue;
        }
        cout << fac( n ) * inv( fac( n / 2 ) ) % p * inv( fac( n / 2 ) ) % p * inv( n / 2 + 1 ) % p * ( n + 1 ) % p << '\n';
    }
    return 0;
}

void init() {
mp[0]=1;
mp[1000000]=641102369;
mp[2000000]=578095319;
mp[3000000]=5832229;
mp[4000000]=259081142;
mp[5000000]=974067448;
mp[6000000]=316220877;
mp[7000000]=690120224;
mp[8000000]=251368199;
mp[9000000]=980250487;
mp[10000000]=682498929;
mp[11000000]=134623568;
mp[12000000]=95936601;
mp[13000000]=933097914;
mp[14000000]=167332441;
mp[15000000]=598816162;
mp[16000000]=336060741;
mp[17000000]=248744620;
mp[18000000]=626497524;
mp[19000000]=288843364;
mp[20000000]=491101308;
mp[21000000]=245341950;
mp[22000000]=565768255;
mp[23000000]=246899319;
mp[24000000]=968999;
mp[25000000]=586350670;
mp[26000000]=638587686;
mp[27000000]=881746146;
mp[28000000]=19426633;
mp[29000000]=850500036;
mp[30000000]=76479948;
mp[31000000]=268124147;
mp[32000000]=842267748;
mp[33000000]=886294336;
mp[34000000]=485348706;
mp[35000000]=463847391;
mp[36000000]=544075857;
mp[37000000]=898187927;
mp[38000000]=798967520;
mp[39000000]=82926604;
mp[40000000]=723816384;
mp[41000000]=156530778;
mp[42000000]=721996174;
mp[43000000]=299085602;
mp[44000000]=323604647;
mp[45000000]=172827403;
mp[46000000]=398699886;
mp[47000000]=530389102;
mp[48000000]=294587621;
mp[49000000]=813805606;
mp[50000000]=67347853;
mp[51000000]=497478507;
mp[52000000]=196447201;
mp[53000000]=722054885;
mp[54000000]=228338256;
mp[55000000]=407719831;
mp[56000000]=762479457;
mp[57000000]=746536789;
mp[58000000]=811667359;
mp[59000000]=778773518;
mp[60000000]=27368307;
mp[61000000]=438371670;
mp[62000000]=59469516;
mp[63000000]=5974669;
mp[64000000]=766196482;
mp[65000000]=606322308;
mp[66000000]=86609485;
mp[67000000]=889750731;
mp[68000000]=340941507;
mp[69000000]=371263376;
mp[70000000]=625544428;
mp[71000000]=788878910;
mp[72000000]=808412394;
mp[73000000]=996952918;
mp[74000000]=585237443;
mp[75000000]=1669644;
mp[76000000]=361786913;
mp[77000000]=480748381;
mp[78000000]=595143852;
mp[79000000]=837229828;
mp[80000000]=199888908;
mp[81000000]=526807168;
mp[82000000]=579691190;
mp[83000000]=145404005;
mp[84000000]=459188207;
mp[85000000]=534491822;
mp[86000000]=439729802;
mp[87000000]=840398449;
mp[88000000]=899297830;
mp[89000000]=235861787;
mp[90000000]=888050723;
mp[91000000]=656116726;
mp[92000000]=736550105;
mp[93000000]=440902696;
mp[94000000]=85990869;
mp[95000000]=884343068;
mp[96000000]=56305184;
mp[97000000]=973478770;
mp[98000000]=168891766;
mp[99000000]=804805577;
mp[100000000]=927880474;
mp[101000000]=876297919;
mp[102000000]=934814019;
mp[103000000]=676405347;
mp[104000000]=567277637;
mp[105000000]=112249297;
mp[106000000]=44930135;
mp[107000000]=39417871;
mp[108000000]=47401357;
mp[109000000]=108819476;
mp[110000000]=281863274;
mp[111000000]=60168088;
mp[112000000]=692636218;
mp[113000000]=432775082;
mp[114000000]=14235602;
mp[115000000]=770511792;
mp[116000000]=400295761;
mp[117000000]=697066277;
mp[118000000]=421835306;
mp[119000000]=220108638;
mp[120000000]=661224977;
mp[121000000]=261799937;
mp[122000000]=168203998;
mp[123000000]=802214249;
mp[124000000]=544064410;
mp[125000000]=935080803;
mp[126000000]=583967898;
mp[127000000]=211768084;
mp[128000000]=751231582;
mp[129000000]=972424306;
mp[130000000]=623534362;
mp[131000000]=335160196;
mp[132000000]=243276029;
mp[133000000]=554749550;
mp[134000000]=60050552;
mp[135000000]=797848181;
mp[136000000]=395891998;
mp[137000000]=172428290;
mp[138000000]=159554990;
mp[139000000]=887420150;
mp[140000000]=970055531;
mp[141000000]=250388809;
mp[142000000]=487998999;
mp[143000000]=856259313;
mp[144000000]=82104855;
mp[145000000]=232253360;
mp[146000000]=513365505;
mp[147000000]=244109365;
mp[148000000]=1559745;
mp[149000000]=695345956;
mp[150000000]=261384175;
mp[151000000]=849009131;
mp[152000000]=323214113;
mp[153000000]=747664143;
mp[154000000]=444090941;
mp[155000000]=659224434;
mp[156000000]=80729842;
mp[157000000]=570033864;
mp[158000000]=664989237;
mp[159000000]=827348878;
mp[160000000]=195888993;
mp[161000000]=576798521;
mp[162000000]=457882808;
mp[163000000]=731551699;
mp[164000000]=212938473;
mp[165000000]=509096183;
mp[166000000]=827544702;
mp[167000000]=678320208;
mp[168000000]=677711203;
mp[169000000]=289752035;
mp[170000000]=66404266;
mp[171000000]=555972231;
mp[172000000]=195290384;
mp[173000000]=97136305;
mp[174000000]=349551356;
mp[175000000]=785113347;
mp[176000000]=83489485;
mp[177000000]=66247239;
mp[178000000]=52167191;
mp[179000000]=307390891;
mp[180000000]=547665832;
mp[181000000]=143066173;
mp[182000000]=350016754;
mp[183000000]=917404120;
mp[184000000]=296269301;
mp[185000000]=996122673;
mp[186000000]=23015220;
mp[187000000]=602139210;
mp[188000000]=748566338;
mp[189000000]=187348575;
mp[190000000]=109838563;
mp[191000000]=574053420;
mp[192000000]=105574531;
mp[193000000]=304173654;
mp[194000000]=542432219;
mp[195000000]=34538816;
mp[196000000]=325636655;
mp[197000000]=437843114;
mp[198000000]=630621321;
mp[199000000]=26853683;
mp[200000000]=933245637;
mp[201000000]=616368450;
mp[202000000]=238971581;
mp[203000000]=511371690;
mp[204000000]=557301633;
mp[205000000]=911398531;
mp[206000000]=848952161;
mp[207000000]=958992544;
mp[208000000]=925152039;
mp[209000000]=914456118;
mp[210000000]=724691727;
mp[211000000]=636817583;
mp[212000000]=238087006;
mp[213000000]=946237212;
mp[214000000]=910291942;
mp[215000000]=114985663;
mp[216000000]=492237273;
mp[217000000]=450387329;
mp[218000000]=834860913;
mp[219000000]=763017204;
mp[220000000]=368925948;
mp[221000000]=475812562;
mp[222000000]=740594930;
mp[223000000]=45060610;
mp[224000000]=806047532;
mp[225000000]=464456846;
mp[226000000]=172115341;
mp[227000000]=75307702;
mp[228000000]=116261993;
mp[229000000]=562519302;
mp[230000000]=268838846;
mp[231000000]=173784895;
mp[232000000]=243624360;
mp[233000000]=61570384;
mp[234000000]=481661251;
mp[235000000]=938269070;
mp[236000000]=95182730;
mp[237000000]=91068149;
mp[238000000]=115435332;
mp[239000000]=495022305;
mp[240000000]=136026497;
mp[241000000]=506496856;
mp[242000000]=710729672;
mp[243000000]=113570024;
mp[244000000]=366384665;
mp[245000000]=564758715;
mp[246000000]=270239666;
mp[247000000]=277118392;
mp[248000000]=79874094;
mp[249000000]=702807165;
mp[250000000]=112390913;
mp[251000000]=730341625;
mp[252000000]=103056890;
mp[253000000]=677948390;
mp[254000000]=339464594;
mp[255000000]=167240465;
mp[256000000]=108312174;
mp[257000000]=839079953;
mp[258000000]=479334442;
mp[259000000]=271788964;
mp[260000000]=135498044;
mp[261000000]=277717575;
mp[262000000]=591048681;
mp[263000000]=811637561;
mp[264000000]=353339603;
mp[265000000]=889410460;
mp[266000000]=839849206;
mp[267000000]=192345193;
mp[268000000]=736265527;
mp[269000000]=316439118;
mp[270000000]=217544623;
mp[271000000]=788132977;
mp[272000000]=618898635;
mp[273000000]=183011467;
mp[274000000]=380858207;
mp[275000000]=996097969;
mp[276000000]=898554793;
mp[277000000]=335353644;
mp[278000000]=54062950;
mp[279000000]=611251733;
mp[280000000]=419363534;
mp[281000000]=965429853;
mp[282000000]=160398980;
mp[283000000]=151319402;
mp[284000000]=990918946;
mp[285000000]=607730875;
mp[286000000]=450718279;
mp[287000000]=173539388;
mp[288000000]=648991369;
mp[289000000]=970937898;
mp[290000000]=500780548;
mp[291000000]=780122909;
mp[292000000]=39052406;
mp[293000000]=276894233;
mp[294000000]=460373282;
mp[295000000]=651081062;
mp[296000000]=461415770;
mp[297000000]=358700839;
mp[298000000]=643638805;
mp[299000000]=560006119;
mp[300000000]=668123525;
mp[301000000]=686692315;
mp[302000000]=673464765;
mp[303000000]=957633609;
mp[304000000]=199866123;
mp[305000000]=563432246;
mp[306000000]=841799766;
mp[307000000]=385330357;
mp[308000000]=504962686;
mp[309000000]=954061253;
mp[310000000]=128487469;
mp[311000000]=685707545;
mp[312000000]=299172297;
mp[313000000]=717975101;
mp[314000000]=577786541;
mp[315000000]=318951960;
mp[316000000]=773206631;
mp[317000000]=306832604;
mp[318000000]=204355779;
mp[319000000]=573592106;
mp[320000000]=30977140;
mp[321000000]=450398100;
mp[322000000]=363172638;
mp[323000000]=258379324;
mp[324000000]=472935553;
mp[325000000]=93940075;
mp[326000000]=587220627;
mp[327000000]=776264326;
mp[328000000]=793270300;
mp[329000000]=291733496;
mp[330000000]=522049725;
mp[331000000]=579995261;
mp[332000000]=335416359;
mp[333000000]=142946099;
mp[334000000]=472012302;
mp[335000000]=559947225;
mp[336000000]=332139472;
mp[337000000]=499377092;
mp[338000000]=464599136;
mp[339000000]=164752359;
mp[340000000]=309058615;
mp[341000000]=86117128;
mp[342000000]=580204973;
mp[343000000]=563781682;
mp[344000000]=954840109;
mp[345000000]=624577416;
mp[346000000]=895609896;
mp[347000000]=888287558;
mp[348000000]=836813268;
mp[349000000]=926036911;
mp[350000000]=386027524;
mp[351000000]=184419613;
mp[352000000]=724205533;
mp[353000000]=403351886;
mp[354000000]=715247054;
mp[355000000]=716986954;
mp[356000000]=830567832;
mp[357000000]=383388563;
mp[358000000]=68409439;
mp[359000000]=6734065;
mp[360000000]=189239124;
mp[361000000]=68322490;
mp[362000000]=943653305;
mp[363000000]=405755338;
mp[364000000]=811056092;
mp[365000000]=179518046;
mp[366000000]=825132993;
mp[367000000]=343807435;
mp[368000000]=985084650;
mp[369000000]=868553027;
mp[370000000]=148528617;
mp[371000000]=160684257;
mp[372000000]=882148737;
mp[373000000]=591915968;
mp[374000000]=701445829;
mp[375000000]=529726489;
mp[376000000]=302177126;
mp[377000000]=974886682;
mp[378000000]=241107368;
mp[379000000]=798830099;
mp[380000000]=940567523;
mp[381000000]=11633075;
mp[382000000]=325334066;
mp[383000000]=346091869;
mp[384000000]=115312728;
mp[385000000]=473718967;
mp[386000000]=218129285;
mp[387000000]=878471898;
mp[388000000]=180002392;
mp[389000000]=699739374;
mp[390000000]=917084264;
mp[391000000]=856859395;
mp[392000000]=435327356;
mp[393000000]=808651347;
mp[394000000]=421623838;
mp[395000000]=105419548;
mp[396000000]=59883031;
mp[397000000]=322487421;
mp[398000000]=79716267;
mp[399000000]=715317963;
mp[400000000]=429277690;
mp[401000000]=398078032;
mp[402000000]=316486674;
mp[403000000]=384843585;
mp[404000000]=940338439;
mp[405000000]=937409008;
mp[406000000]=940524812;
mp[407000000]=947549662;
mp[408000000]=833550543;
mp[409000000]=593524514;
mp[410000000]=996164327;
mp[411000000]=987314628;
mp[412000000]=697611981;
mp[413000000]=636177449;
mp[414000000]=274192146;
mp[415000000]=418537348;
mp[416000000]=925347821;
mp[417000000]=952831975;
mp[418000000]=893732627;
mp[419000000]=1277567;
mp[420000000]=358655417;
mp[421000000]=141866945;
mp[422000000]=581830879;
mp[423000000]=987597705;
mp[424000000]=347046911;
mp[425000000]=775305697;
mp[426000000]=125354499;
mp[427000000]=951540811;
mp[428000000]=247662371;
mp[429000000]=343043237;
mp[430000000]=568392357;
mp[431000000]=997474832;
mp[432000000]=209244402;
mp[433000000]=380480118;
mp[434000000]=149586983;
mp[435000000]=392838702;
mp[436000000]=309134554;
mp[437000000]=990779998;
mp[438000000]=263053337;
mp[439000000]=325362513;
mp[440000000]=780072518;
mp[441000000]=551028176;
mp[442000000]=990826116;
mp[443000000]=989944961;
mp[444000000]=155569943;
mp[445000000]=596737944;
mp[446000000]=711553356;
mp[447000000]=268844715;
mp[448000000]=451373308;
mp[449000000]=379404150;
mp[450000000]=462639908;
mp[451000000]=961812918;
mp[452000000]=654611901;
mp[453000000]=382776490;
mp[454000000]=41815820;
mp[455000000]=843321396;
mp[456000000]=675258797;
mp[457000000]=845583555;
mp[458000000]=934281721;
mp[459000000]=741114145;
mp[460000000]=275105629;
mp[461000000]=666247477;
mp[462000000]=325912072;
mp[463000000]=526131620;
mp[464000000]=252551589;
mp[465000000]=432030917;
mp[466000000]=554917439;
mp[467000000]=818036959;
mp[468000000]=754363835;
mp[469000000]=795190182;
mp[470000000]=909210595;
mp[471000000]=278704903;
mp[472000000]=719566487;
mp[473000000]=628514947;
mp[474000000]=424989675;
mp[475000000]=321685608;
mp[476000000]=50590510;
mp[477000000]=832069712;
mp[478000000]=198768464;
mp[479000000]=702004730;
mp[480000000]=99199382;
mp[481000000]=707469729;
mp[482000000]=747407118;
mp[483000000]=302020341;
mp[484000000]=497196934;
mp[485000000]=5003231;
mp[486000000]=726997875;
mp[487000000]=382617671;
mp[488000000]=296229203;
mp[489000000]=183888367;
mp[490000000]=703397904;
mp[491000000]=552133875;
mp[492000000]=732868367;
mp[493000000]=350095207;
mp[494000000]=26031303;
mp[495000000]=863250534;
mp[496000000]=216665960;
mp[497000000]=561745549;
mp[498000000]=352946234;
mp[499000000]=784139777;
mp[500000000]=733333339;
mp[501000000]=503105966;
mp[502000000]=459878625;
mp[503000000]=803187381;
mp[504000000]=16634739;
mp[505000000]=180898306;
mp[506000000]=68718097;
mp[507000000]=985594252;
mp[508000000]=404206040;
mp[509000000]=749724532;
mp[510000000]=97830135;
mp[511000000]=611751357;
mp[512000000]=31131935;
mp[513000000]=662741752;
mp[514000000]=864326453;
mp[515000000]=864869025;
mp[516000000]=167831173;
mp[517000000]=559214642;
mp[518000000]=718498895;
mp[519000000]=91352335;
mp[520000000]=608823837;
mp[521000000]=473379392;
mp[522000000]=385388084;
mp[523000000]=152267158;
mp[524000000]=681756977;
mp[525000000]=46819124;
mp[526000000]=313132653;
mp[527000000]=56547945;
mp[528000000]=442795120;
mp[529000000]=796616594;
mp[530000000]=256141983;
mp[531000000]=152028387;
mp[532000000]=636578562;
mp[533000000]=385377759;
mp[534000000]=553033642;
mp[535000000]=491415383;
mp[536000000]=919273670;
mp[537000000]=996049638;
mp[538000000]=326686486;
mp[539000000]=160150665;
mp[540000000]=141827977;
mp[541000000]=540818053;
mp[542000000]=693305776;
mp[543000000]=593938674;
mp[544000000]=186576440;
mp[545000000]=688809790;
mp[546000000]=565456578;
mp[547000000]=749296077;
mp[548000000]=519397500;
mp[549000000]=551096742;
mp[550000000]=696628828;
mp[551000000]=775025061;
mp[552000000]=370732451;
mp[553000000]=164246193;
mp[554000000]=915265013;
mp[555000000]=457469634;
mp[556000000]=923043932;
mp[557000000]=912368644;
mp[558000000]=777901604;
mp[559000000]=464118005;
mp[560000000]=637939935;
mp[561000000]=956856710;
mp[562000000]=490676632;
mp[563000000]=453019482;
mp[564000000]=462528877;
mp[565000000]=502297454;
mp[566000000]=798895521;
mp[567000000]=100498586;
mp[568000000]=699767918;
mp[569000000]=849974789;
mp[570000000]=811575797;
mp[571000000]=438952959;
mp[572000000]=606870929;
mp[573000000]=907720182;
mp[574000000]=179111720;
mp[575000000]=48053248;
mp[576000000]=508038818;
mp[577000000]=811944661;
mp[578000000]=752550134;
mp[579000000]=401382061;
mp[580000000]=848924691;
mp[581000000]=764368449;
mp[582000000]=34629406;
mp[583000000]=529840945;
mp[584000000]=435904287;
mp[585000000]=26011548;
mp[586000000]=208184231;
mp[587000000]=446477394;
mp[588000000]=206330671;
mp[589000000]=366033520;
mp[590000000]=131772368;
mp[591000000]=185646898;
mp[592000000]=648711554;
mp[593000000]=472759660;
mp[594000000]=523696723;
mp[595000000]=271198437;
mp[596000000]=25058942;
mp[597000000]=859369491;
mp[598000000]=817928963;
mp[599000000]=330711333;
mp[600000000]=724464507;
mp[601000000]=437605233;
mp[602000000]=701453022;
mp[603000000]=626663115;
mp[604000000]=281230685;
mp[605000000]=510650790;
mp[606000000]=596949867;
mp[607000000]=295726547;
mp[608000000]=303076380;
mp[609000000]=465070856;
mp[610000000]=272814771;
mp[611000000]=538771609;
mp[612000000]=48824684;
mp[613000000]=951279549;
mp[614000000]=939889684;
mp[615000000]=564188856;
mp[616000000]=48527183;
mp[617000000]=201307702;
mp[618000000]=484458461;
mp[619000000]=861754542;
mp[620000000]=326159309;
mp[621000000]=181594759;
mp[622000000]=668422905;
mp[623000000]=286273596;
mp[624000000]=965656187;
mp[625000000]=44135644;
mp[626000000]=359960756;
mp[627000000]=936229527;
mp[628000000]=407934361;
mp[629000000]=267193060;
mp[630000000]=456152084;
mp[631000000]=459116722;
mp[632000000]=124804049;
mp[633000000]=262322489;
mp[634000000]=920251227;
mp[635000000]=816929577;
mp[636000000]=483924582;
mp[637000000]=151834896;
mp[638000000]=167087470;
mp[639000000]=490222511;
mp[640000000]=903466878;
mp[641000000]=361583925;
mp[642000000]=368114731;
mp[643000000]=339383292;
mp[644000000]=388728584;
mp[645000000]=218107212;
mp[646000000]=249153339;
mp[647000000]=909458706;
mp[648000000]=322908524;
mp[649000000]=202649964;
mp[650000000]=92255682;
mp[651000000]=573074791;
mp[652000000]=15570863;
mp[653000000]=94331513;
mp[654000000]=744158074;
mp[655000000]=196345098;
mp[656000000]=334326205;
mp[657000000]=9416035;
mp[658000000]=98349682;
mp[659000000]=882121662;
mp[660000000]=769795511;
mp[661000000]=231988936;
mp[662000000]=888146074;
mp[663000000]=137603545;
mp[664000000]=582627184;
mp[665000000]=407518072;
mp[666000000]=919419361;
mp[667000000]=909433461;
mp[668000000]=986708498;
mp[669000000]=310317874;
mp[670000000]=373745190;
mp[671000000]=263645931;
mp[672000000]=256853930;
mp[673000000]=876379959;
mp[674000000]=702823274;
mp[675000000]=147050765;
mp[676000000]=308186532;
mp[677000000]=175504139;
mp[678000000]=180350107;
mp[679000000]=797736554;
mp[680000000]=606241871;
mp[681000000]=384547635;
mp[682000000]=273712630;
mp[683000000]=586444655;
mp[684000000]=682189174;
mp[685000000]=666493603;
mp[686000000]=946867127;
mp[687000000]=819114541;
mp[688000000]=502371023;
mp[689000000]=261970285;
mp[690000000]=825871994;
mp[691000000]=126925175;
mp[692000000]=701506133;
mp[693000000]=314738056;
mp[694000000]=341779962;
mp[695000000]=561011609;
mp[696000000]=815463367;
mp[697000000]=46765164;
mp[698000000]=49187570;
mp[699000000]=188054995;
mp[700000000]=957939114;
mp[701000000]=64814326;
mp[702000000]=933376898;
mp[703000000]=329837066;
mp[704000000]=338121343;
mp[705000000]=765215899;
mp[706000000]=869630152;
mp[707000000]=978119194;
mp[708000000]=632627667;
mp[709000000]=975266085;
mp[710000000]=435887178;
mp[711000000]=282092463;
mp[712000000]=129621197;
mp[713000000]=758245605;
mp[714000000]=827722926;
mp[715000000]=201339230;
mp[716000000]=918513230;
mp[717000000]=322096036;
mp[718000000]=547838438;
mp[719000000]=985546115;
mp[720000000]=852304035;
mp[721000000]=593090119;
mp[722000000]=689189630;
mp[723000000]=555842733;
mp[724000000]=567033437;
mp[725000000]=469928208;
mp[726000000]=212842957;
mp[727000000]=117842065;
mp[728000000]=404149413;
mp[729000000]=155133422;
mp[730000000]=663307737;
mp[731000000]=208761293;
mp[732000000]=206282795;
mp[733000000]=717946122;
mp[734000000]=488906585;
mp[735000000]=414236650;
mp[736000000]=280700600;
mp[737000000]=962670136;
mp[738000000]=534279149;
mp[739000000]=214569244;
mp[740000000]=375297772;
mp[741000000]=811053196;
mp[742000000]=922377372;
mp[743000000]=289594327;
mp[744000000]=219932130;
mp[745000000]=211487466;
mp[746000000]=701050258;
mp[747000000]=398782410;
mp[748000000]=863002719;
mp[749000000]=27236531;
mp[750000000]=217598709;
mp[751000000]=375472836;
mp[752000000]=810551911;
mp[753000000]=178598958;
mp[754000000]=247844667;
mp[755000000]=676526196;
mp[756000000]=812283640;
mp[757000000]=863066876;
mp[758000000]=857241854;
mp[759000000]=113917835;
mp[760000000]=624148346;
mp[761000000]=726089763;
mp[762000000]=564827277;
mp[763000000]=826300950;
mp[764000000]=478982047;
mp[765000000]=439411911;
mp[766000000]=454039189;
mp[767000000]=633292726;
mp[768000000]=48562889;
mp[769000000]=802100365;
mp[770000000]=671734977;
mp[771000000]=945204804;
mp[772000000]=508831870;
mp[773000000]=398781902;
mp[774000000]=897162044;
mp[775000000]=644050694;
mp[776000000]=892168027;
mp[777000000]=828883117;
mp[778000000]=277714559;
mp[779000000]=713448377;
mp[780000000]=624500515;
mp[781000000]=590098114;
mp[782000000]=808691930;
mp[783000000]=514359662;
mp[784000000]=895205045;
mp[785000000]=715264908;
mp[786000000]=628829100;
mp[787000000]=484492064;
mp[788000000]=919717789;
mp[789000000]=513196123;
mp[790000000]=748510389;
mp[791000000]=403652653;
mp[792000000]=574455974;
mp[793000000]=77123823;
mp[794000000]=172096141;
mp[795000000]=819801784;
mp[796000000]=581418893;
mp[797000000]=15655126;
mp[798000000]=15391652;
mp[799000000]=875641535;
mp[800000000]=203191898;
mp[801000000]=264582598;
mp[802000000]=880691101;
mp[803000000]=907800444;
mp[804000000]=986598821;
mp[805000000]=340030191;
mp[806000000]=264688936;
mp[807000000]=369832433;
mp[808000000]=785804644;
mp[809000000]=842065079;
mp[810000000]=423951674;
mp[811000000]=663560047;
mp[812000000]=696623384;
mp[813000000]=496709826;
mp[814000000]=161960209;
mp[815000000]=331910086;
mp[816000000]=541120825;
mp[817000000]=951524114;
mp[818000000]=841656666;
mp[819000000]=162683802;
mp[820000000]=629786193;
mp[821000000]=190395535;
mp[822000000]=269571439;
mp[823000000]=832671304;
mp[824000000]=76770272;
mp[825000000]=341080135;
mp[826000000]=421943723;
mp[827000000]=494210290;
mp[828000000]=751040886;
mp[829000000]=317076664;
mp[830000000]=672850561;
mp[831000000]=72482816;
mp[832000000]=493689107;
mp[833000000]=135625240;
mp[834000000]=100228913;
mp[835000000]=684748812;
mp[836000000]=639655136;
mp[837000000]=906233141;
mp[838000000]=929893103;
mp[839000000]=277813439;
mp[840000000]=814362881;
mp[841000000]=562608724;
mp[842000000]=406024012;
mp[843000000]=885537778;
mp[844000000]=10065330;
mp[845000000]=60625018;
mp[846000000]=983737173;
mp[847000000]=60517502;
mp[848000000]=551060742;
mp[849000000]=804930491;
mp[850000000]=823845496;
mp[851000000]=727416538;
mp[852000000]=946421040;
mp[853000000]=678171399;
mp[854000000]=842203531;
mp[855000000]=175638827;
mp[856000000]=894247956;
mp[857000000]=538609927;
mp[858000000]=885362182;
mp[859000000]=946464959;
mp[860000000]=116667533;
mp[861000000]=749816133;
mp[862000000]=241427979;
mp[863000000]=871117927;
mp[864000000]=281804989;
mp[865000000]=163928347;
mp[866000000]=563796647;
mp[867000000]=640266394;
mp[868000000]=774625892;
mp[869000000]=59342705;
mp[870000000]=256473217;
mp[871000000]=674115061;
mp[872000000]=918860977;
mp[873000000]=322633051;
mp[874000000]=753513874;
mp[875000000]=393556719;
mp[876000000]=304644842;
mp[877000000]=767372800;
mp[878000000]=161362528;
mp[879000000]=754787150;
mp[880000000]=627655552;
mp[881000000]=677395736;
mp[882000000]=799289297;
mp[883000000]=846650652;
mp[884000000]=816701166;
mp[885000000]=687265514;
mp[886000000]=787113234;
mp[887000000]=358757251;
mp[888000000]=701220427;
mp[889000000]=607715125;
mp[890000000]=245795606;
mp[891000000]=600624983;
mp[892000000]=10475577;
mp[893000000]=728620948;
mp[894000000]=759404319;
mp[895000000]=36292292;
mp[896000000]=491466901;
mp[897000000]=22556579;
mp[898000000]=114495791;
mp[899000000]=647630109;
mp[900000000]=586445753;
mp[901000000]=482254337;
mp[902000000]=718623833;
mp[903000000]=763514207;
mp[904000000]=66547751;
mp[905000000]=953634340;
mp[906000000]=351472920;
mp[907000000]=308474522;
mp[908000000]=494166907;
mp[909000000]=634359666;
mp[910000000]=172114298;
mp[911000000]=865440961;
mp[912000000]=364380585;
mp[913000000]=921648059;
mp[914000000]=965683742;
mp[915000000]=260466949;
mp[916000000]=117483873;
mp[917000000]=962540888;
mp[918000000]=237120480;
mp[919000000]=620531822;
mp[920000000]=193781724;
mp[921000000]=213092254;
mp[922000000]=107141741;
mp[923000000]=602742426;
mp[924000000]=793307102;
mp[925000000]=756154604;
mp[926000000]=236455213;
mp[927000000]=362928234;
mp[928000000]=14162538;
mp[929000000]=753042874;
mp[930000000]=778983779;
mp[931000000]=25977209;
mp[932000000]=49389215;
mp[933000000]=698308420;
mp[934000000]=859637374;
mp[935000000]=49031023;
mp[936000000]=713258160;
mp[937000000]=737331920;
mp[938000000]=923333660;
mp[939000000]=804861409;
mp[940000000]=83868974;
mp[941000000]=682873215;
mp[942000000]=217298111;
mp[943000000]=883278906;
mp[944000000]=176966527;
mp[945000000]=954913;
mp[946000000]=105359006;
mp[947000000]=390019735;
mp[948000000]=10430738;
mp[949000000]=706334445;
mp[950000000]=315103615;
mp[951000000]=567473423;
mp[952000000]=708233401;
mp[953000000]=48160594;
mp[954000000]=946149627;
mp[955000000]=346966053;
mp[956000000]=281329488;
mp[957000000]=462880311;
mp[958000000]=31503476;
mp[959000000]=185438078;
mp[960000000]=965785236;
mp[961000000]=992656683;
mp[962000000]=916291845;
mp[963000000]=881482632;
mp[964000000]=899946391;
mp[965000000]=321900901;
mp[966000000]=512634493;
mp[967000000]=303338827;
mp[968000000]=121000338;
mp[969000000]=967284733;
mp[970000000]=492741665;
mp[971000000]=152233223;
mp[972000000]=165393390;
mp[973000000]=680128316;
mp[974000000]=917041303;
mp[975000000]=532702135;
mp[976000000]=741626808;
mp[977000000]=496442755;
mp[978000000]=536841269;
mp[979000000]=131384366;
mp[980000000]=377329025;
mp[981000000]=301196854;
mp[982000000]=859917803;
mp[983000000]=676511002;
mp[984000000]=373451745;
mp[985000000]=847645126;
mp[986000000]=823495900;
mp[987000000]=576368335;
mp[988000000]=73146164;
mp[989000000]=954958912;
mp[990000000]=847549272;
mp[991000000]=241289571;
mp[992000000]=646654592;
mp[993000000]=216046746;
mp[994000000]=205951465;
mp[995000000]=3258987;
mp[996000000]=780882948;
mp[997000000]=822439091;
mp[998000000]=598245292;
mp[999000000]=869544707;
mp[1000000000]=698611116;
}

ll fac( ll n ) {
    ll x = n / 1000000 * 1000000;
    ll res = mp[ x ];
    while( ++x <= n )
        res = res * x % p;
    return res;
}

ll inv( ll x ) {
    return pow_mod( x, p - 2 );
}

ll pow_mod( ll x, ll y ) {
    ll res = 1;
    while( y ) {
        if( y & 1 )
            res = res * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return res;
}