#14245 (C++11) No.148 試験監督（3）

• 問題: No.148 試験監督（3）
• ユーザー: __math
• 提出日時: 2015-02-28 02:01:07
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 56,904 bytes
• コンパイル時間: 887 ms
• コンパイル使用メモリ: 98,076 KB
• 実行使用メモリ: 42,908 KB
• 最終ジャッジ日時: 2024-06-23 22:45:45
• 合計ジャッジ時間: 2,771 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	77 ms; 42,624 KB
testcase_10	AC	76 ms; 42,624 KB
testcase_11	AC	74 ms; 42,688 KB

コンパイルメッセージ

main.cpp: In function ‘int solve()’:
main.cpp:99:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   99 |         scanf("%s%s", sc, sp);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

const int MOD = ten(9) + 7;

const int N = ten(7);
const int C = ten(5) * 2;
int fact[N];
void init(){
	fact[0] = fact[1] = 1;
	for (int i = 2; i < N; i++) fact[i] = fact[i - 1] * ll(i) % MOD;

	//fprintf(stderr, "start\n");
	//int cur = 1;
	//for(int i = 1; i < MOD; i++){
	//	cur = cur * ll(i) % MOD;
	//	if (i % C == 0) {
	//		printf("%d,",cur);
	//	}
	//}
	//fprintf(stderr,"OK\n");
}
template<class T> T extgcd(T a, T b, T& x, T& y){
	for (T u = y = 1, v = x = 0; a;) {
		T q = b / a;
		swap(x -= q * u, u);
		swap(y -= q * v, v);
		swap(b -= q * a, a);
	}
	return b;
}
template<class T> T md_inverse(T a, T m){
	//mod_powの方が速い場合がある
	T x, y;
	extgcd(a, m, x, y);
	return (m + x % m) % m;
}

int tbl[] = { 107146451, 559805077, 679209364, 644158465, 641102369, 363599536, 539157852, 309854856, 663484182, 578095319, 765808214, 585806050, 579773866, 861745250, 5832229, 242744764, 899032987, 150478174, 627860803, 259081142, 544918953, 907400235, 421968194, 278955367, 974067448, 996965954, 473966292, 479920311, 752161465, 316220877, 1575312, 620898940, 405577532, 956413299, 690120224, 24521750, 576078970, 929871923, 14422365, 251368199, 582439362, 220087090, 98361446, 763414075, 980250487, 618104354, 398723029, 764421236, 476998749, 682498929, 152611299, 345470378, 403024660, 140864216, 134623568, 373126171, 461157687, 363224613, 526497651, 95936601, 19447777, 584319463, 569582206, 9045328, 933097914, 959173997, 559096347, 12442609, 508362944, 167332441, 75538458, 275742306, 137855279, 60332461, 598816162, 31223863, 767213175, 564190300, 222078457, 336060741, 632048012, 895642779, 171183381, 851161246, 248744620, 635103992, 605016577, 853414712, 546047842, 626497524, 867430659, 904851726, 475501650, 298693437, 288843364, 52298443, 743602491, 479708090, 125625755, 491101308, 662967999, 385457627, 482257159, 393222011, 245341950, 474567292, 196002818, 754437203, 542706821, 565768255, 524308015, 545648343, 58680787, 792180189, 246899319, 99934426, 788944266, 676012445, 610686655, 968999, 595032530, 244819707, 511710008, 902492598, 586350670, 979137619, 980655027, 474700377, 30153596, 638587686, 420932107, 353049206, 281562548, 921459833, 881746146, 850268753, 711117420, 919203761, 831442297, 19426633, 910061172, 862345480, 293462255, 542955556, 850500036, 181909169, 496532173, 582702682, 168757859, 76479948, 477639087, 930180103, 941723214, 28581913, 268124147, 685075984, 53790970, 672818243, 581968000, 842267748, 947532066, 451116854, 333707614, 650009312, 886294336, 868829344, 613566917, 695702195, 853242582, 485348706, 229827108, 827117592, 492711911, 296974594, 463847391, 649090736, 204857297, 760019200, 942731826, 544075857, 185735387, 550588097, 632593345, 706629399, 898187927, 854821744, 297803207, 596729075, 466541843, 798967520, 743420839, 198998756, 526623452, 952046139, 82926604, 924044367, 23777891, 924258126, 450837733, 723816384, 535478979, 53975412, 517436639, 63932312, 156530778, 807928028, 305569485, 545662462, 29493652, 721996174, 49456224, 480391065, 526281212, 151117811, 299085602, 522961673, 374481484, 489252071, 589831644, 323604647, 153393495, 268164416, 48301315, 90383486, 172827403, 800588969, 757146415, 169338716, 192601723, 398699886, 675113999, 139831846, 135840345, 475501867, 530389102, 499294891, 415376, 114785958, 576550918, 294587621, 714006296, 457685563, 875018827, 254653019, 813805606, 172340144, 498342367, 258170000, 43217172, 67347853, 909565792, 16783532, 495844744, 402811155, 497478507, 110424728, 441813281, 581794056, 561458723, 196447201, 404666335, 118379156, 910698506, 850677980, 722054885, 777969547, 12568481, 748065817, 60153582, 228338256, 433273104, 521949545, 52378412, 701779420, 407719831, 445935909, 752708852, 15212588, 650765251, 762479457, 398970308, 808076198, 39427394, 8600742, 746536789, 586283387, 655840660, 152366450, 741393509, 811667359, 415355660, 386594397, 97783708, 333236625, 778773518, 205743536, 570866962, 242211856, 218690396, 27368307, 562235036, 987935647, 849148138, 692637504, 438371670, 422227498, 845152439, 883281454, 243833737, 59469516, 765962345, 89372661, 972779460, 599040453, 5974669, 324069108, 180699112, 833342486, 793755411, 766196482, 468608739, 812248718, 494936006, 59143878, 606322308, 732001446, 635032673, 759041389, 554416265, 86609485, 559966857, 658825730, 586359929, 562500933, 889750731, 724008021, 806898745, 995252950, 135711291, 340941507, 700915958, 324648749, 722436788, 59758328, 371263376, 265906250, 850300987, 61732363, 887464462, 625544428, 279914778, 644000584, 180090545, 9409022, 788878910, 631046702, 358050946, 714475801, 883906209, 808412394, 528517448, 316094660, 724209709, 544375689, 996952918, 79329551, 136597179, 64972739, 930161980, 585237443, 422015194, 62785084, 374220150, 44615465, 1669644, 42241449, 58647723, 929666976, 307936472, 361786913, 974936549, 107912795, 225369475, 703087658, 480748381, 2295485, 880634238, 805196528, 188324947, 595143852, 926866806, 742851567, 666743467, 973671409, 837229828, 243910108, 697054929, 57085695, 469594245, 199888908, 649491763, 274161939, 558233225, 470545797, 526807168, 244714186, 411969385, 54080847, 427233799, 579691190, 754963083, 169559902, 270720182, 588618211, 145404005, 478716222, 293401592, 614571924, 321950925, 459188207, 805552722, 508829534, 304228537, 355209596, 534491822, 947251800, 225966128, 986142683, 701643375, 439729802, 759944655, 349343101, 48980788, 212468510, 840398449, 259450229, 983563606, 704289349, 442694685, 899297830, 121102289, 405640886, 513670887, 961729079, 235861787, 281870391, 270409779, 798401543, 369530217, 888050723, 920492865, 298494436, 756462483, 628273353, 656116726, 247544137, 294651705, 412762822, 489872437, 736550105, 461990959, 534030848, 365932794, 610954403, 440902696, 253238972, 682492613, 522303856, 839296517, 85990869, 288079694, 617973869, 825208191, 111668651, 884343068, 125800325, 805525713, 184783824, 425093556, 56305184, 939279559, 912326839, 855064933, 756764497, 973478770, 706513987, 632521245, 897480658, 888874515, 168891766, 413551441, 450119928, 687166876, 349851104, 804805577, 160016093, 64401654, 546799298, 304104093, 927880474, 870230497, 673373340, 543880181, 83687737, 876297919, 298117414, 660162137, 753032322, 989583729, 934814019, 759023037, 546967731, 400707264, 26634340, 676405347, 30684171, 990757848, 981776332, 122464431, 567277637, 737511882, 888156482, 936882737, 350634174, 112249297, 998807506, 945210513, 324630241, 966957906, 44930135, 726576875, 856312450, 61329065, 987095152, 39417871, 816679377, 984659637, 375956346, 152201272, 47401357, 573877927, 322199735, 112861607, 382991165, 108819476, 497956225, 939019242, 259568406, 40151094, 281863274, 720198656, 414608027, 139227607, 963111262, 60168088, 597743038, 797673080, 516804319, 956903770, 692636218, 376501201, 283454561, 168830642, 79852813, 432775082, 378591066, 168948455, 879838297, 365353075, 14235602, 936696483, 603752857, 218851785, 790227812, 770511792, 191651583, 37130006, 277138066, 784685853, 400295761, 962694684, 212661821, 487912147, 674932318, 697066277, 245419396, 330984733, 721056741, 367606436, 421835306, 560478118, 620682731, 704015358, 859346814, 220108638, 929629213, 258032745, 483594161, 744178841, 661224977, 362005376, 792431280, 610644835, 107880912, 261799937, 925041977, 331286268, 995422447, 376285455, 168203998, 63915001, 731950688, 346917761, 851595228, 802214249, 771727692, 921586643, 310280612, 551069866, 544064410, 6811130, 792676030, 441236680, 500440019, 935080803, 199237620, 124878394, 238096591, 732880514, 583967898, 393771071, 423889038, 567003562, 740304600, 211768084, 89921218, 147206837, 187655305, 873138566, 751231582, 107228569, 787539126, 653478705, 710576505, 972424306, 275525858, 711211981, 682495521, 379750380, 623534362, 834892236, 332606953, 89816323, 714130414, 335160196, 17823426, 465697749, 447817657, 728285308, 243276029, 532995050, 545163218, 716734025, 688099880, 554749550, 787117889, 502618954, 543915886, 907685793, 60050552, 998579767, 731397402, 350274220, 838528120, 797848181, 198635873, 187586151, 515174333, 126672033, 395891998, 455781723, 586419431, 647132471, 935521357, 172428290, 780740034, 447063192, 265212968, 406468142, 159554990, 833317992, 520653845, 802837814, 332814802, 887420150, 14211262, 605911169, 423078378, 577063899, 970055531, 513206217, 40607687, 351001772, 829605980, 250388809, 148577573, 449800991, 727934933, 735023078, 487998999, 737738750, 634045080, 744227785, 585552623, 856259313, 386799500, 296457528, 441140793, 343416042, 82104855, 840750201, 528005624, 761748690, 959757496, 232253360, 190349508, 363157570, 175671239, 862776555, 513365505, 713750699, 803726808, 128024882, 881788966, 244109365, 136906899, 372302392, 155570288, 249305450, 1559745, 397066469, 25720042, 626251836, 177573201, 695345956, 677752342, 793806704, 581977030, 646625129, 261384175, 253117073, 245535187, 757717391, 80513018, 849009131, 439520189, 712872275, 92973848, 64851034, 323214113, 664011932, 298352021, 255712655, 946042845, 747664143, 711816007, 691151364, 285806889, 395396851, 444090941, 95039844, 522655892, 377908620, 257703472, 659224434, 26301094, 83002883, 862614058, 475057494, 80729842, 339308141, 907519187, 223545290, 614010914, 570033864, 279454856, 793767325, 430035302, 143966252, 664989237, 213302213, 512045319, 735382383, 661411739, 827348878, 814721633, 531511759, 271003610, 642932826, 195888993, 54530329, 8792644, 141282580, 142207463, 576798521, 540842540, 369088993, 10438986, 881336900, 457882808, 448656552, 620851842, 352488342, 286398811, 731551699, 397201286, 352032421, 424438049, 690333383, 212938473, 170367135, 348384180, 900118182, 545454871, 509096183, 557219900, 269119299, 71735354, 971188122, 827544702, 143313131, 674471405, 617909056, 356557690, 678320208, 72413193, 727559899, 538479815, 137232509, 677711203, 245038045, 533035983, 252381793, 579001093, 289752035, 908061115, 81830860, 927327790, 717194510, 66404266, 587040263, 864886893, 930123178, 168706834, 555972231, 346540153, 726092354, 865071734, 691794731, 195290384, 505039565, 105369595, 318094322, 251055417, 97136305, 259423383, 615768075, 48226379, 49055565, 349551356, 439547835, 441914739, 783331349, 14415592, 785113347, 698578769, 256348629, 627785281, 437879870, 83489485, 444939632, 669721484, 951712820, 16691404, 66247239, 109670626, 964858552, 811793940, 43692008, 52167191, 817865822, 989876896, 873199303, 943421142, 307390891, 26423599, 908425681, 568639586, 763827725, 547665832, 705468334, 515674128, 103148840, 867962375, 143066173, 65688464, 288586996, 993416534, 27059824, 350016754, 249679480, 483800403, 620632962, 182282878, 917404120, 735051019, 613755669, 699187663, 778614746, 296269301, 172717571, 946428264, 64227251, 302130199, 996122673, 29653283, 566743853, 675135087, 125757468, 23015220, 69144282, 91963875, 747064884, 707518700, 602139210, 865946552, 304609790, 315792222, 79909943, 748566338, 444243246, 677793008, 71369280, 316009903, 187348575, 698438828, 588943683, 653637010, 262263266, 109838563, 579202306, 976768405, 653611079, 743379209, 574053420, 621976669, 644544622, 669880848, 656217362, 105574531, 29530499, 61251444, 703406898, 452293734, 304173654, 962272195, 443273892, 902817853, 965863401, 542432219, 57871728, 483381085, 862802054, 146817944, 34538816, 601045763, 654297097, 974686011, 488641593, 325636655, 196493142, 837122513, 261912790, 498769510, 437843114, 616745496, 177043432, 781045243, 215203239, 630621321, 267772361, 828224642, 815108093, 243906544, 26853683, 950098683, 950937270, 24585059, 910131508, 933245637, 398417914, 613395893, 668061275, 31373935, 616368450, 776087191, 791289062, 194702413, 284301461, 238971581, 914259332, 376484863, 937988951, 643201093, 511371690, 217011832, 248828832, 214825867, 813678395, 557301633, 85036725, 73710858, 408261121, 231162188, 911398531, 312744814, 631096421, 372821319, 894005672, 848952161, 365531126, 407261940, 835498847, 61879608, 958992544, 821785476, 580068092, 825545235, 489515035, 925152039, 139924045, 837893999, 981726228, 974145698, 914456118, 62506502, 599381336, 671342714, 253502443, 724691727, 493000568, 796455047, 379569031, 454499514, 636817583, 671808625, 133580252, 332617055, 48407083, 238087006, 288453502, 584070283, 525709741, 463044231, 946237212, 266574253, 665038715, 345406040, 342052927, 910291942, 639275237, 666894368, 197517090, 800533801, 114985663, 683569260, 727416461, 447668677, 845963889, 492237273, 48958052, 14863281, 982399964, 84066292, 450387329, 521347279, 581318867, 504201844, 817001543, 834860913, 452479777, 797624286, 393997958, 662570964, 763017204, 710524918, 573783638, 722384751, 93189280, 368925948, 774578782, 128141880, 57577699, 672475624, 475812562, 780444992, 956113007, 31158979, 338903704, 740594930, 30327041, 196133374, 639667205, 784067427, 45060610, 205489214, 609897705, 890030947, 707609521, 806047532, 51697523, 751385829, 784074598, 879021109, 464456846, 224012738, 206786423, 16481395, 757595751, 172115341, 115439068, 395201336, 543890274, 677667796, 75307702, 472939116, 282517784, 220670562, 746611934, 116261993, 691436204, 991857982, 73185230, 836720967, 562519302, 557278802, 856268751, 803489706, 379589733, 268838846, 704823268, 422027886, 447984334, 638736741, 173784895, 936274462, 513000960, 600569863, 903630901, 243624360, 10215879, 299332708, 745649909, 835492163, 61570384, 250649611, 471338418, 656946705, 762291053, 481661251, 964221559, 163315222, 376190954, 77886816, 938269070, 170095245, 961258156, 463372147, 647118969, 95182730, 521051639, 928132071, 357479404, 440006366, 91068149, 596682713, 502285607, 27842076, 814435597, 115435332, 659725221, 566804955, 555863276, 954436899, 495022305, 621840415, 419016530, 187930450, 950614205, 136026497, 650427674, 588220375, 99515953, 19179738, 506496856, 355847369, 474430173, 141544165, 29368029, 710729672, 194678932, 233454730, 232785168, 981331732, 113570024, 269240725, 771211236, 968217984, 482504225, 366384665, 18878032, 859670660, 908756610, 904676787, 564758715, 757490458, 789798345, 196234471, 877873054, 270239666, 83412859, 39852073, 759243154, 994645885, 277118392, 91658702, 565097382, 791195765, 337945304, 79874094, 26070851, 613650278, 370886950, 678481982, 702807165, 595881374, 969808707, 593441490, 845233368, 112390913, 287199918, 199287301, 73194471, 12722112, 730341625, 143352852, 898432986, 960245410, 96688732, 103056890, 357128875, 220909560, 926269464, 275050620, 677948390, 667314832, 671563881, 59546001, 781014065, 339464594, 886951140, 956300519, 267189882, 483334477, 167240465, 469826147, 242791773, 982787195, 897053425, 108312174, 404419260, 213495567, 329493881, 194495711, 839079953, 744394023, 799886608, 324061977, 4828968, 479334442, 64540172, 237622412, 57802491, 75307485, 271788964, 367246992, 449337229, 750924279, 27562780, 135498044, 172547388, 796874733, 559021338, 381261137, 277717575, 6508639, 182579383, 649588249, 369091773, 591048681, 547541822, 203770813, 237482332, 884448724, 811637561, 913670594, 171861798, 660521215, 594481480, 353339603, 705462701, 578624825, 200578945, 53887029, 889410460, 65382100, 119754265, 444667960, 858172947, 839849206, 727527500, 363876491, 453708370, 448553303, 192345193, 874653794, 516251793, 655083733, 579917597, 736265527, 943565520, 114354987, 322697676, 84996211, 316439118, 321767973, 622243748, 33541892, 336307844, 217544623, 765527479, 488571552, 901558026, 224426443, 788132977, 891740370, 79799739, 285783983, 495353045, 618898635, 566290786, 876944194, 893419849, 337227397, 183011467, 200502210, 119584347, 75044998, 654322415, 380858207, 41105587, 779716363, 537171634, 416296106, 996097969, 117632702, 744653725, 665991924, 776830268, 898554793, 98150112, 649498583, 617376992, 914289783, 335353644, 535714239, 57011781, 176088357, 130970069, 54062950, 581932933, 197823988, 104193664, 920088375, 611251733, 281925319, 603541468, 520167099, 54329101, 419363534, 999882733, 609974294, 144428843, 787976961, 965429853, 188902380, 663077658, 21156992, 264583298, 160398980, 117346006, 365477695, 907509168, 141023870, 151319402, 432853212, 972573872, 422341486, 932154665, 990918946, 469793622, 548515509, 584499542, 384832279, 607730875, 686042136, 568889025, 252498130, 728066225, 450718279, 139074490, 414985236, 309143522, 28035029, 173539388, 341441066, 210189977, 651481497, 526650954, 648991369, 298136906, 324582904, 271280653, 28215403, 970937898, 73200626, 438582079, 732533504, 26734774, 500780548, 898813354, 834047892, 393478502, 439473227, 780122909, 623210256, 719920686, 558066773, 653072279, 39052406, 322961340, 98850072, 690363849, 760185403, 276894233, 820701420, 754656474, 521509517, 940004978, 460373282, 579784574, 709826006, 591327786, 213095340, 651081062, 631039161, 799429582, 205619551, 333519690, 461415770, 199901656, 45606936, 665103395, 648597040, 358700839, 367292711, 650317594, 951097561, 305315917, 643638805, 42107699, 624444413, 490712755, 576235495, 560006119, 745174361, 896387115, 789998567, 706156005, 668123525, 258950395, 585694480, 810258572, 132735686, 686692315, 189425696, 256948933, 412101608, 131741634, 673464765, 987323284, 209922927, 981063997, 739667609, 957633609, 959034974, 387371507, 337587116, 442266621, 199866123, 329784980, 357758924, 50074863, 837041881, 563432246, 240113750, 732795600, 753526942, 479299281, 841799766, 332678303, 670276685, 947815394, 2842216, 385330357, 966879926, 581434438, 886495348, 397040122, 504962686, 123693376, 698358362, 91552734, 99282640, 954061253, 296490792, 696199419, 162053428, 511951052, 128487469, 663044112, 325243771, 452579108, 328827203, 685707545, 30429569, 19400253, 264145497, 59586779, 299172297, 835433918, 464938358, 127134110, 33971220, 717975101, 802237942, 394125648, 401098691, 27389706, 577786541, 35368452, 303960799, 20954810, 587564278, 318951960, 349654693, 221376767, 443006185, 985325842, 773206631, 834645521, 856250990, 554999881, 146299241, 306832604, 405462479, 940588421, 942749789, 512117445, 204355779, 680164492, 76508631, 896673698, 126132194, 573592106, 251680833, 586600424, 763512297, 851729659, 30977140, 117294271, 872687840, 705027494, 155345351, 450398100, 658259464, 511653547, 122784513, 563821816, 363172638, 614886666, 349541490, 249358677, 136993731, 258379324, 54999362, 20843784, 278558807, 628533988, 472935553, 877990835, 873758230, 240566962, 845984324, 93940075, 717953996, 131626578, 765533635, 627506214, 587220627, 460004468, 187037910, 443040223, 42987704, 776264326, 512808433, 698604673, 930975319, 652206838, 793270300, 599178777, 113754130, 344159107, 911620065, 291733496, 185579598, 867809325, 297187956, 599561924, 522049725, 566288467, 481989863, 930168992, 53992733, 579995261, 744715706, 193329709, 125738917, 322096840, 335416359, 468232116, 550810519, 930373681, 80674155, 142946099, 347339841, 3679394, 262877922, 216214183, 472012302, 760519986, 609913278, 570074267, 408626290, 559947225, 603988527, 694873679, 271596392, 702278033, 332139472, 847209705, 139873662, 307320859, 508029503, 499377092, 499571407, 213218151, 444800132, 584953303, 464599136, 287080720, 381815654, 328840505, 613227212, 164752359, 62870178, 338612335, 847305694, 231214901, 309058615, 923056570, 741114654, 679474509, 943963703, 86117128, 173607295, 192205742, 854546438, 465304689, 580204973, 693571936, 221722420, 743803583, 910097241, 563781682, 113007508, 366759417, 729430386, 734084885, 954840109, 87536532, 821577890, 612067620, 616023889, 624577416, 183378516, 712232206, 937341831, 929688418, 895609896, 948536557, 932074667, 491512730, 333962357, 888287558, 909434502, 622456324, 313577942, 396397359, 836813268, 73963271, 203528675, 284627321, 978490631, 926036911, 928078729, 966538801, 718446896, 676092053, 386027524, 769016475, 417881441, 419449519, 6622174, 184419613, 428377643, 862478095, 616873080, 68030466, 724205533, 771316604, 111897624, 100980417, 487626661, 403351886, 197681757, 403508109, 851600426, 132801672, 715247054, 701593595, 651667233, 770437268, 24911986, 716986954, 780721596, 635845774, 587942632, 428368450, 830567832, 371306896, 637985919, 36335795, 703224736, 383388563, 990426067, 701055524, 398619836, 291291997, 68409439, 772410939, 967445876, 510553855, 661249755, 6734065, 437410655, 176021640, 130382065, 684750143, 189239124, 293020859, 437611321, 526519406, 471149790, 68322490, 764804584, 212032037, 199007164, 671683885, 943653305, 279901097, 724153585, 600497805, 559782639, 405755338, 470411531, 230505529, 567659902, 486245922, 811056092, 369665871, 228127265, 234484080, 411331165, 179518046, 608693296, 734959327, 48314078, 490903812, 825132993, 918581297, 479627509, 846464473, 761918447, 343807435, 436552374, 224163026, 497516166, 479946500, 985084650, 17287926, 447018815, 299183050, 145906122, 868553027, 193468566, 881713809, 786976399, 309455313, 148528617, 246026996, 191267209, 430464002, 100931272, 160684257, 596093059, 338146211, 265187723, 448465137, 882148737, 629532985, 248528148, 654572396, 897437810, 591915968, 319640243, 696312467, 611578390, 372312361, 701445829, 962818755, 860362535, 718311808, 76142147, 529726489, 24241426, 414119827, 320111308, 336720842, 302177126, 126491704, 613897160, 924335797, 816787370, 974886682, 191656767, 682815119, 567920383, 793851258, 241107368, 761444952, 194742388, 621889419, 454022261, 798830099, 690972016, 903969041, 210305537, 522929419, 940567523, 11723489, 838405179, 150961869, 157588295, 11633075, 230720777, 968795345, 540124639, 447156284, 325334066, 204842030, 830679914, 741295810, 743716196, 346091869, 538017325, 459776558, 315284618, 55047278, 115312728, 4692025, 318753931, 991445447, 508133625, 473718967, 216198217, 433344718, 294829425, 131899998, 218129285, 677013556, 932843935, 639354624, 341598119, 878471898, 169501510, 855998453, 587573660, 499944270, 180002392, 490957526, 302311490, 791145434, 189039628, 699739374, 311881126, 121266080, 146729215, 92544232, 917084264, 391859035, 4794797, 798890367, 453362362, 856859395, 545480202, 971496521, 814906938, 379109076, 435327356, 193135182, 922714159, 265682709, 552348113, 808651347, 468099850, 257109020, 480752775, 193708013, 421623838, 139413479, 820519069, 795354000, 273532342, 105419548, 184110060, 246087982, 593253319, 79521617, 59883031, 528910967, 598142207, 423151147, 32072083, 322487421, 288750955, 199843514, 5095624, 809668786, 79716267, 472022598, 192830460, 995747483, 756147480, 715317963, 366214156, 540894424, 310763081, 436700379, 429277690, 667079481, 311514806, 748464103, 315334936, 398078032, 573147130, 187438671, 99630959, 103129190, 316486674, 912169002, 714885313, 244169574, 997082517, 384843585, 120666598, 868729680, 132813978, 807137265, 940338439, 941886088, 353502954, 454920772, 193798014, 937409008, 137818624, 755771078, 481544618, 459710496, 940524812, 958128854, 498645632, 515132481, 324273785, 947549662, 542143734, 518804963, 153647676, 593471448, 833550543, 250090645, 89990507, 579250879, 2388484, 593524514, 752057652, 291568668, 811327365, 365422560, 996164327, 37557960, 321244755, 262105390, 926249712, 987314628, 168966149, 3657915, 492562803, 137774364, 697611981, 709427437, 708146737, 319186712, 448070840, 636177449, 563983446, 776902713, 50890241, 801871097, 274192146, 436916208, 413045253, 567482968, 743405594, 418537348, 102670030, 210729521, 451751420, 208016240, 925347821, 921491439, 986220607, 647024460, 677344487, 952831975, 821240174, 499236336, 623193347, 70121843, 893732627, 252978558, 473981189, 718775566, 215948550, 1277567, 749948197, 253263870, 599092339, 348350896, 358655417, 92457810, 583160135, 822890688, 340690733, 141866945, 528735091, 153014838, 293503505, 792770688, 581830879, 902909023, 509586056, 47211054, 689449821, 987597705, 864507704, 95792164, 994038437, 644755481, 347046911, 734275360, 752213561, 108087469, 106265119, 775305697, 810184598, 512236469, 843924853, 586524553, 125354499, 155500407, 365421825, 457419472, 231048116, 951540811, 193960834, 586696485, 6035002, 843801012, 247662371, 807684222, 947743059, 607924966, 363840458, 343043237, 31628362, 674647619, 957418529, 208983731, 568392357, 592453528, 983211324, 191642900, 83735188, 997474832, 893327224, 648755177, 763538123, 722834776, 209244402, 455804196, 716850596, 629666477, 97587647, 380480118, 793797606, 31462446, 434078209, 722262801, 149586983, 891829033, 303751319, 405670141, 400254261, 392838702, 516564199, 797177914, 783203950, 795179413, 309134554, 855159619, 296824558, 839617203, 811476109, 990779998, 488334472, 47902070, 880648014, 85060063, 263053337, 117412078, 985650598, 946752311, 419136857, 325362513, 588444116, 116725054, 942971003, 984807268, 780072518, 945288110, 469073466, 792003268, 906534263, 551028176, 238082550, 689363231, 988770034, 288035303, 990826116, 115203345, 199204020, 5871750, 443563763, 989944961, 717903632, 211188289, 797385788, 754047147, 155569943, 525310983, 146598405, 879917958, 867292155, 596737944, 111145334, 116814362, 130359475, 65516896, 711553356, 257272757, 800639067, 748822937, 876432387, 268844715, 285754648, 914012338, 337234235, 878473104, 451373308, 773873624, 327120461, 473672652, 439847431, 379404150, 358541327, 432529045, 113595532, 85317496, 462639908, 252730810, 632738698, 920756860, 54745397, 961812918, 26499318, 685511993, 296301818, 459642445, 654611901, 545213692, 318351795, 951490591, 845395490, 382776490, 877658697, 273404439, 487989369, 256635012, 41815820, 427826292, 370999052, 308084349, 715657404, 843321396, 424629988, 138829244, 971901418, 439397708, 675258797, 190324601, 949238642, 867463339, 89183561, 845583555, 285201003, 54718463, 68493027, 918908541, 934281721, 65952114, 115836197, 438675673, 329796660, 741114145, 170688640, 613839978, 246971298, 368915438, 275105629, 927129495, 44673585, 522626370, 151904385, 666247477, 11034295, 553115973, 736481265, 430792893, 325912072, 163644615, 312363713, 28447959, 708382039, 526131620, 337778689, 643205214, 267512809, 566782883, 252551589, 514003160, 956613828, 330419454, 497985400, 432030917, 409094906, 932710247, 320060926, 55291696, 554917439, 919398906, 250993499, 687801469, 749521773, 818036959, 853329772, 517363885, 754948228, 124331004, 754363835, 289925139, 324458366, 647362373, 199336973, 795190182, 759415866, 30954813, 375598506, 414771343, 909210595, 119812483, 700755004, 13265271, 907013091, 278704903, 878065545, 350477813, 394359162, 40070120, 719566487, 194044866, 19360802, 644419646, 538410830, 628514947, 782386712, 805940809, 568881907, 72505010, 424989675, 523809523, 560500372, 628422087, 830324646, 321685608, 501026094, 871108711, 268675400, 141938430, 50590510, 96029674, 930059515, 760581888, 932297089, 832069712, 747776616, 317413783, 229386209, 937289943, 198768464, 107918293, 241822340, 154527893, 515625587, 702004730, 789870803, 968162638, 861828251, 410971868, 99199382, 218733931, 811051461, 108157516, 739303690, 707469729, 338230961, 281950342, 474683954, 478806302, 747407118, 548042577, 363810556, 951545265, 938222670, 302020341, 393708383, 500083903, 396133072, 916317352, 497196934, 870850657, 806683867, 232222235, 927957338, 5003231, 294813632, 836484636, 795382466, 789372556, 726997875, 766119778, 569565538, 396201245, 59049178, 382617671, 477072797, 369721783, 342634621, 911128874, 296229203, 86301351, 609696820, 14572600, 621340527, 183888367, 469448617, 630735799, 477527263, 685432978, 703397904, 407218934, 48845205, 71614944, 140231825, 552133875, 961921035, 958236143, 612842106, 903284998, 732868367, 508543739, 376263315, 828871132, 415616232, 350095207, 942401605, 155864979, 800362473, 360070086, 26031303, 393412897, 48755035, 347115769, 632078189, 863250534, 150230048, 763864011, 802627671, 559518219, 216665960, 834544566, 908760486, 355456809, 701253820, 561745549, 106460787, 744954999, 341934027, 85883684, 352946234, 569536822, 814053802, 496278313, 765506212, 784139777, 982076387, 56103640, 965931947, 279881729, 733333339, 934237219, 432445966, 747541026, 847302953, 503105966, 270177936, 28109541, 563443841, 312319329, 459878625, 512506831, 208372493, 214314837, 748932782, 803187381, 183753738, 632548969, 62568726, 452864462, 16634739, 626492653, 818220387, 123301859, 361648749, 180898306, 268151658, 493448019, 298852345, 278798734, 68718097, 459948721, 294891752, 765504766, 315170969, 985594252, 53792521, 770351508, 827351663, 279524210, 404206040, 484050433, 793946555, 793118341, 404917720, 749724532, 321673283, 822303356, 184607674, 92441916, 97830135, 358933626, 545104222, 93052080, 378307888, 611751357, 206861090, 911268409, 989655902, 457564227, 31131935, 947436015, 602293534, 304598573, 389038888, 662741752, 699689146, 573188485, 316227381, 903947795, 864326453, 704204620, 96158832, 546842147, 958542649, 864869025, 170961663, 774999229, 530328239, 349055793, 167831173, 659394668, 753712331, 582032345, 817219959, 559214642, 229070827, 934331767, 628303842, 865023876, 718498895, 528184248, 559961787, 746668480, 707233111, 91352335, 657496548, 251818074, 288199605, 555189268, 608823837, 964833819, 249236264, 297020805, 262774210, 473379392, 229265100, 634556946, 243591881, 453510559, 385388084, 542366534, 9582985, 862206727, 20303770, 152267158, 562008185, 830691740, 636134163, 226087354, 681756977, 115792198, 565417478, 132026969, 657564216, 46819124, 53730313, 105764429, 578460779, 671247758, 313132653, 83676143, 781307067, 310247089, 379008804, 56547945, 282185454, 977489767, 263223296, 94974805, 442795120, 21788247, 632289515, 888860570, 457210799, 796616594, 976656728, 650167037, 636009706, 462320111, 256141983, 876216454, 268795108, 219963869, 452130570, 152028387, 620695667, 469042034, 186801565, 526335076, 636578562, 479037032, 366772204, 732408654, 859354557, 385377759, 191659036, 179536173, 18081311, 336074035, 553033642, 875352353, 863225538, 101577474, 555731982, 491415383, 553084997, 53408588, 829373573, 410724146, 919273670, 143357390, 9051229, 486728022, 809437256, 996049638, 903263782, 586611710, 34185477, 823981167, 326686486, 917134440, 94825580, 312828689, 231310558, 160150665, 379278321, 469906415, 482926441, 893068324, 141827977, 882700651, 365864597, 519560661, 111873860, 540818053, 123637707, 859622353, 176377554, 229743519, 693305776, 781825138, 540005807, 766981391, 292411226, 593938674, 898227295, 253992928, 950055170, 981759737, 186576440, 766465400, 50118951, 694821975, 259165544, 688809790, 650817063, 897965492, 96594580, 520491355, 565456578, 748710556, 296527297, 410239606, 220797542, 749296077, 813409093, 422638517, 26724420, 152783894, 519397500, 46038513, 181681081, 652904189, 701572379, 551096742, 663329044, 176317974, 362041517, 288669565, 696628828, 790276532, 795808108, 546877617, 796426218, 775025061, 587068363, 699871484, 148505764, 200607928, 370732451, 146822913, 278185962, 972809991, 573509777, 164246193, 277209248, 965149774, 514994610, 754091823, 915265013, 760823221, 501404039, 130530532, 681242817, 457469634, 745638450, 793706054, 105200925, 523362944, 923043932, 862254647, 407356104, 105380350, 763025936, 912368644, 2989898, 522910736, 394923655, 42117338, 777901604, 849570319, 488630304, 566449613, 243034420, 464118005, 89120113, 424450934, 800607974, 871326267, 637939935, 545097159, 395358411, 726030473, 907816292, 956856710, 982937783, 994287728, 719072900, 744016775, 490676632, 990350617, 471929788, 753260140, 621887590, 453019482, 292909707, 891034371, 238296988, 542620395, 462528877, 184312310, 369525491, 313528213, 38124644, 502297454, 808722011, 738422572, 428387930, 330318264, 798895521, 631613615, 75853166, 862028984, 508267768, 100498586, 641108112, 530247647, 761776308, 443954530, 699767918, 537835749, 525486772, 134571498, 696896168, 849974789, 449939558, 805638970, 149268478, 916915977, 811575797, 22241923, 512277222, 23466885, 112891394, 438952959, 665736716, 698047673, 168631060, 250474300, 606870929, 43931879, 463528680, 355095535, 154281667, 907720182, 785149129, 486362776, 151054828, 85020958, 179111720, 534189446, 237769647, 299744674, 593926876, 48053248, 482335897, 892619781, 993649414, 439741182, 508038818, 270183465, 771818046, 930425199, 83264202, 811944661, 723407599, 16542261, 812668005, 419096046, 752550134, 154860541, 883929124, 986844192, 988557002, 401382061, 67620895, 115042726, 121061403, 939190858, 848924691, 826073768, 319954157, 581071621, 871705611, 764368449, 427351467, 242254724, 152373822, 411505939, 34629406, 631379183, 491671763, 953240917, 254524151, 529840945, 570308920, 428877877, 544811678, 720519967, 435904287, 697606803, 849489362, 541576570, 589672369, 26011548, 847509284, 280555847, 548430222, 935250524, 208184231, 430115071, 181134117, 354176562, 874464388, 446477394, 200377679, 767434657, 767288966, 288749667, 206330671, 191275474, 596844380, 646861175, 752825233, 366033520, 753134199, 329972696, 539562642, 156178713, 131772368, 772199894, 544099511, 155855128, 194916555, 185646898, 256255312, 473139604, 146162018, 979226446, 648711554, 340238509, 584495484, 454007135, 197533041, 472759660, 687257851, 927330853, 360777215, 912609549, 523696723, 401421644, 792476159, 446012138, 246329273, 271198437, 8300915, 538044438, 295294842, 713419072, 25058942, 598597720, 865177945, 848310765, 486033494, 859369491, 304038136, 5377959, 845991325, 810252842, 817928963, 866042171, 152438502, 670564895, 461763427, 330711333, 235481106, 77363677, 837898265, 173414914, 724464507, 402525386, 835830978, 397980952, 551315810, 437605233, 697617046, 620721450, 921015986, 866066508, 701453022, 784352983, 721919690, 987404851, 490065418, 626663115, 154495299, 303822193, 72509488, 784853613, 281230685, 172493030, 510446188, 951188269, 181224475, 510650790, 521329716, 79363961, 607307402, 742957071, 596949867, 130653048, 498928970, 448224525, 145135624, 295726547, 930570143, 99791277, 467192613, 954448365, 303076380, 191370134, 366069684, 524956976, 677309335, 465070856, 771759239, 644286393, 936868840, 608014758, 272814771, 698130352, 17704676, 136535933, 670999343, 538771609, 993602760, 734992736, 193370243, 32006662, 48824684, 265858359, 757819171, 149716490, 880826935, 951279549, 955098935, 701664398, 450039887, 967888856, 939889684, 420720352, 443114259, 109235125, 886867149, 564188856, 759427018, 22399833, 955654747, 816730090, 48527183, 944169450, 445129483, 427071593, 188875807, 201307702, 715555451, 577760366, 365537558, 553903473, 484458461, 562364570, 580929149, 697013456, 232629505, 861754542, 529700323, 959507688, 673032615, 355168380, 326159309, 599517082, 313027690, 626605289, 425343432, 181594759, 455315503, 360804087, 60511994, 356790137, 668422905, 742513075, 750208636, 410204618, 210143574, 286273596, 810028347, 612515537, 477169522, 67530822, 965656187, 17723383, 369499175, 994745941, 801756649, 44135644, 590906591, 550034231, 226784434, 413157808, 359960756, 485740665, 729604909, 347687933, 251867424, 936229527, 65822009, 132771262, 222489048, 60427024, 407934361, 134437749, 120587974, 450883789, 460076831, 267193060, 595916891, 530947917, 50253054, 160781137, 456152084, 65065312, 694188722, 676379162, 207214810, 459116722, 895560303, 329795333, 891996014, 368422050, 124804049, 692229472, 751677875, 387549818, 107094470, 262322489, 168655116, 127414221, 127290321, 696929170, 920251227, 870911553, 10679073, 523551656, 323940868, 816929577, 817279053, 947070975, 424610493, 555285442, 483924582, 885053740, 984402270, 275356603, 807755216, 151834896, 248636352, 834783869, 342008720, 397154977, 167087470, 96154360, 873784528, 992692236, 157167077, 490222511, 574400690, 931065936, 989612191, 879229923, 903466878, 473549421, 558765053, 781375314, 279153607, 361583925, 849646812, 530908116, 11779782, 181929013, 368114731, 384117784, 614562174, 31016465, 192200875, 339383292, 432824950, 278928724, 588320903, 606224169, 388728584, 767789944, 605240, 381205283, 22602811, 218107212, 337060250, 770468270, 36228319, 508228531, 249153339, 654931776, 960535678, 203521321, 87626727, 909458706, 493952635, 894601453, 307920342, 463556792, 322908524, 63753880, 242283503, 585065543, 877718665, 202649964, 466501375, 112078552, 658442906, 697450276, 92255682, 419292187, 169999754, 59952286, 930731151, 573074791, 454538013, 476751412, 931433486, 169931105, 15570863, 656835361, 930762614, 352110687, 564730215, 94331513, 243133049, 655471890, 782066883, 242612658, 744158074, 384595922, 796850043, 760217410, 526627922, 196345098, 306534040, 945578836, 920947137, 974375849, 334326205, 445900278, 849929912, 385444375, 239473327, 9416035, 483405622, 191214699, 334547062, 997233464, 98349682, 570901172, 262989398, 327192258, 184790555, 882121662, 958445403, 858663278, 783054273, 490312790, 769795511, 447164962, 820483088, 529172551, 909017757, 231988936, 932616287, 907485902, 768208088, 361441946, 888146074, 387636812, 362567344, 35494306, 732526251, 137603545, 548032144, 196039409, 931021597, 987451457, 582627184, 52369532, 971149798, 958090664, 880462874, 407518072, 912118240, 964153946, 644572432, 426586939, 919419361, 157418739, 371739314, 615861761, 370692399, 909433461, 222125557, 541985758, 944154377, 547463294, 986708498, 536995755, 835585917, 410822698, 30384659, 310317874, 940526817, 80932302, 648517190, 663213991, 373745190, 2978881, 629489405, 66951748, 113312623, 263645931, 834203858, 967945295, 116940940, 416532285, 256853930, 29483105, 423574692, 844148073, 162638132, 876379959, 526240263, 918251537, 121163959, 411749850, 702823274, 598995963, 250642319, 80761335, 494063841, 147050765, 489134659, 454479158, 129015470, 889479102, 308186532, 980899070, 351359004, 516851727, 690998709, 175504139, 37542184, 5571621, 75147725, 197559076, 180350107, 478177973, 612015056, 527651943, 552162842, 797736554, 593443248, 839987038, 823246366, 395773110, 606241871, 45671355, 897002443, 90725391, 94230023, 384547635, 21430807, 581357661, 618924870, 494118647, 273712630, 801781337, 25534662, 85981391, 366267355, 586444655, 442310407, 651528902, 661225829, 815109260, 682189174, 869601706, 787940705, 633021147, 64685867, 666493603, 337651405, 126747959, 988034294, 167057106, 946867127, 310079669, 655392623, 808701401, 921736853, 819114541, 638544222, 471631442, 100107979, 424618143, 502371023, 122511053, 905845514, 584314137, 790485759, 261970285, 413972507, 944112951, 257426299, 785429551, 825871994, 51773862, 848886378, 396267526, 756445317, 126925175, 972951283, 716569526, 60331080, 738079754, 701506133, 219886595, 96436642, 271834916, 177546793, 314738056, 494271604, 435886744, 885681419, 341126370, 341779962, 746328981, 799261956, 800822574, 848518926, 561011609, 24345594, 558751647, 488335568, 228329908, 815463367, 866378998, 869492348, 887264865, 649106694, 46765164, 607061640, 178904848, 124722795, 425675181, 49187570, 603834304, 446331630, 932575078, 454804469, 188054995, 928529467, 470209383, 494966152, 231504971, 957939114, 122078198, 337515306, 558492354, 351235669, 64814326, 880615277, 72298073, 828744337, 163025077, 933376898, 149038120, 989183409, 52844822, 985593892, 329837066, 725055952, 4528059, 837168087, 884406233, 338121343, 133248309, 147503783, 628460938, 364396002, 765215899, 886677604, 529664065, 719537828, 63239925, 869630152, 357875411, 426305490, 637983821, 458037451, 978119194, 412687469, 498194123, 685092513, 210721601, 632627667, 3961459, 317246521, 959262804, 807947426, 975266085, 20121898, 89185325, 825283988, 468444339, 435887178, 686721323, 500860184, 228374231, 510020354, 282092463, 982966892, 829543369, 146168758, 12050683, 129621197, 481987595, 405196353, 607291665, 973851619, 758245605, 164164627, 370795847, 76050898, 735643780, 827722926, 154108068, 868946348, 208205431, 800461354, 201339230, 761123504, 289985936, 299417930, 912554918, 918513230, 384531928, 527015648, 517549615, 868169900, 322096036, 988894879, 132276805, 884369503, 111743408, 547838438, 247310262, 914861719, 609673656, 174368041, 985546115, 217650875, 782340764, 724929305, 966322010, 852304035, 449473513, 783630094, 587360154, 750642922, 593090119, 262218995, 744911735, 581282403, 105182284, 689189630, 481737612, 664079643, 672675152, 363994545, 555842733, 626539241, 271517055, 810853769, 973391629, 567033437, 94400535, 130223610, 310769264, 380766745, 469928208, 145628232, 534748128, 660389112, 382964872, 212842957, 752708555, 59476749, 296509592, 616831860, 117842065, 378430921, 309829395, 350285832, 88374104, 404149413, 309066078, 558661806, 492836583, 423750826, 155133422, 202330828, 145364504, 620676040, 342138996, 663307737, 820398475, 808454200, 981899817, 546696895, 208761293, 963774716, 968375295, 965328448, 936102439, 206282795, 295627629, 996017320, 3811515, 330624860, 717946122, 16741224, 398260081, 580069277, 908353133, 488906585, 110521739, 30569161, 234964291, 80281513, 414236650, 336908710, 454358793, 450727414, 513021593, 280700600, 609679705, 96079152, 108916243, 107971406, 962670136, 34566831, 725889057, 411765386, 149130988, 534279149, 609799053, 830184839, 469970550, 56838370, 214569244, 826025098, 102488577, 401776532, 483937604, 375297772, 489310502, 517845614, 973417700, 148428940, 811053196, 649876656, 319261078, 979071936, 468642345, 922377372, 713607339, 474115783, 946802154, 310792516, 289594327, 156910777, 722424997, 749805383, 277985222, 219932130, 487075978, 136961239, 895001126, 205625235, 211487466, 200048852, 11849047, 73943059, 630135090, 701050258, 978125206, 684265803, 536375628, 552965451, 398782410, 206241913, 889674027, 692292858, 56967115, 863002719, 771926344, 812982323, 437913038, 790641838, 27236531, 201252328, 378698060, 352817240, 302631882, 217598709, 868168063, 480698499, 474773010, 876412019, 375472836, 442413206, 937210795, 832120781, 915529697, 810551911, 536944220, 767557384, 418758727, 361003283, 178598958, 709545031, 578519730, 448564967, 89010120, 247844667, 731467618, 432551669, 809944745, 854684600, 676526196, 232511639, 962090950, 390009248, 975808258, 812283640, 403888976, 595405397, 34221133, 770779245, 863066876, 594845000, 134120574, 374647549, 531245275, 857241854, 857265904, 567393268, 849122672, 789013621, 113917835, 828454750, 642648400, 62553593, 432213197, 624148346, 654844001, 621725636, 83203491, 621143544, 726089763, 741504235, 262034566, 98533460, 597019590, 564827277, 36869004, 652975242, 571007758, 977482822, 826300950, 934007482, 211854468, 905426828, 46276857, 478982047, 684574590, 229040223, 293838397, 409534564, 439411911, 834121669, 634939692, 133770918, 620956265, 454039189, 688948972, 63767449, 175327679, 110933513, 633292726, 117263578, 979744007, 544744689, 528557247, 48562889, 989729668, 472970036, 581888270, 276850119, 802100365, 492337064, 401805356, 856718199, 88810754, 671734977, 108496295, 75057840, 275791943, 664888764, 945204804, 809192204, 861484281, 419328516, 787873321, 508831870, 416208822, 410260274, 988955152, 361191448, 398781902, 677880815, 142990728, 314836111, 699605137, 897162044, 536271973, 636998925, 221811480, 886004348, 644050694, 653085093, 393470607, 120855817, 768884051, 892168027, 262288506, 488676042, 836225870, 831017977, 828883117, 981671640, 586828879, 927715727, 715108783, 277714559, 988063869, 694383920, 807762455, 287466494, 713448377, 902649100, 535116329, 921742704, 429126605, 624500515, 428113849, 494570163, 270145350, 556926990, 590098114, 363293787, 642171590, 216856467, 175657516, 808691930, 358283154, 67853838, 479719850, 825214384, 514359662, 996283144, 430538405, 205394803, 19332138, 895205045, 710192688, 523665938, 932133547, 517718457, 715264908, 818574611, 492549025, 427084870, 187800811, 628829100, 188215106, 143380801, 709026752, 759002288, 484492064, 364455291, 966707479, 837453770, 482764258, 919717789, 297041414, 727771800, 375730434, 140909847, 513196123, 15369004, 742784839, 966548302, 999738618, 748510389, 748342116, 699766608, 30305086, 130016019, 403652653, 594901690, 645584198, 661412735, 859898679, 574455974, 426349074, 452410737, 654581682, 28726649, 77123823, 368429004, 601475460, 431184348, 832473701, 172096141, 80383086, 316340630, 666861325, 33107859, 819801784, 865506733, 615250929, 876108626, 182045350, 581418893, 96311593, 523597876, 17622588, 797757269, 15655126, 793616977, 668246370, 160630660, 964118631, 15391652, 56150668, 815626120, 221842546, 393720508, 875641535, 412237041, 478199454, 241071717, 767714339, 203191898, 978601387, 552822041, 138549377, 417942539, 264582598, 81856390, 234947456, 277650223, 581708983, 880691101, 467598076, 625278603, 299893553, 197666986, 907800444, 501938887, 725559962, 569600455, 859921080, 986598821, 893600713, 607363865, 861338050, 870740081, 340030191, 481923877, 945358400, 214956689, 71038724, 264688936, 398444349, 449958460, 771097082, 41076631, 369832433, 770162507, 905924748, 183658929, 896884790, 785804644, 912354528, 954270606, 598778643, 604867835, 842065079, 495838143, 286875008, 219425152, 799254294, 423951674, 624114280, 119813352, 714874414, 268343768, 663560047, 923820379, 366223170, 341205900, 975896867, 696623384, 184827796, 830126743, 823399038, 286246546, 496709826, 934953895, 572785751, 183229029, 921075273, 161960209, 538244672, 910171678, 151945652, 326083992, 331910086, 908732533, 188622572, 13527023, 484862577, 541120825, 432047901, 941211285, 287777481, 31728844, 951524114, 832712633, 56287048, 142493387, 652822305, 841656666, 610289231, 282938781, 503140662, 540979506, 162683802, 169823238, 881334012, 961773117, 72128915, 629786193, 979670619, 230477028, 402106077, 794471639, 190395535, 50055621, 91198469, 221210182, 481161431, 269571439, 609396366, 587183657, 279364087, 513958026, 832671304, 565647910, 320001298, 831650763, 371926819, 76770272, 671672880, 199774070, 377865541, 302464254, 341080135, 644042531, 160849952, 365500410, 921838917, 421943723, 170960052, 549348080, 52995235, 655814211, 494210290, 397780223, 104494341, 825689399, 87076222, 751040886, 717668287, 55212870, 119004660, 580413046, 317076664, 633010409, 884945562, 895966774, 114495223, 672850561, 431200610, 671006344, 679872740, 713879575, 72482816, 283738625, 888938507, 218139373, 954440108, 493689107, 974044014, 321889979, 158471181, 214217407, 135625240, 919788603, 497813276, 79499595, 97784562, 100228913, 597790155, 810904041, 480381639, 162490176, 684748812, 957200574, 909426167, 683285538, 585281399, 639655136, 84632985, 181994733, 826696971, 960676473, 906233141, 21121378, 901451856, 823154790, 2902192, 929893103, 670105278, 642380089, 264686798, 941348051, 277813439, 445446563, 752635906, 902980332, 105074578, 814362881, 467920076, 427675611, 8521003, 314431839, 562608724, 345167956, 515767294, 617304201, 321587328, 406024012, 132278719, 726229501, 600233962, 472901360, 885537778, 249429164, 785456666, 674533527, 888167735, 10065330, 309461521, 196741756, 210767592, 753152516, 60625018, 849578441, 841629667, 468928447, 640885103, 983737173, 73330961, 915099068, 624377709, 849525756, 60517502, 114886454, 163038122, 430048364, 141596507, 551060742, 583216446, 143407998, 918542696, 179435628, 804930491, 539765360, 315266469, 494268880, 391413644, 823845496, 161083658, 428887477, 973849550, 240477416, 727416538, 313294171, 881769105, 193434473, 147301263, 946421040, 917891624, 63641538, 770955505, 394899231, 678171399, 434031342, 451079175, 443618781, 634121148, 842203531, 1807425, 95905616, 272168573, 353782904, 175638827, 996380924, 141522222, 653867289, 46910641, 894247956, 905754479, 823173026, 113252848, 267728794, 538609927, 862941821, 992194188, 975226699, 831449564, 885362182, 49790705, 411820693, 663971804, 983946932, 946464959, 864162465, 70298830, 978954289, 680922328, 116667533, 665516103, 791371507, 44771880, 484444661, 749816133, 894838313, 933305518, 616418505, 704840030, 241427979, 659692538, 961319002, 995710133, 273943424, 871117927, 704279434, 510693796, 329834703, 690369886, 281804989, 799146252, 220356705, 341717691, 55398199, 163928347, 450861796, 667020392, 118238106, 341968649, 563796647, 999853565, 630585326, 996135761, 75201573, 640266394, 294139525, 193170365, 626642230, 638428173, 774625892, 53533202, 768834255, 295470685, 146628973, 59342705, 182299808, 503912861, 116225473, 176366171, 256473217, 612860517, 702144552, 351908785, 795985707, 674115061, 641863188, 966269658, 969473023, 68213963, 918860977, 198797634, 2947098, 566144751, 745744394, 322633051, 505255660, 106954728, 325145582, 950334087, 753513874, 419792036, 406578925, 757329093, 471703615, 393556719, 144571505, 375444447, 21686669, 874254764, 304644842, 141952086, 837580332, 530861561, 219698501, 767372800, 377516953, 397091747, 75061610, 749180338, 161362528, 288897720, 294206968, 60065457, 976521022, 754787150, 270285846, 380974020, 451709693, 426176420, 627655552, 32047028, 355876825, 452433811, 923770521, 677395736, 441274033, 311867912, 800849785, 661537637, 799289297, 556003302, 657258899, 927572137, 352886272, 846650652, 338657310, 988455813, 535099780, 607636771, 816701166, 44086947, 407896543, 490329417, 128635371, 687265514, 579659907, 759048941, 578690901, 291397055, 787113234, 252851400, 164950881, 677856415, 744064735, 358757251, 450562136, 617715754, 976366438, 249770937, 701220427, 609488927, 144453590, 795949633, 242444386, 607715125, 576861374, 773174605, 655829165, 750941512, 245795606, 575125687, 43209047, 691263483, 760649561, 600624983, 215263617, 911651761, 347049376, 16011198, 10475577, 434596327, 646820311, 43235933, 360639233, 728620948, 672056268, 170826012, 88327015, 193266837, 759404319, 811707189, 275928212, 724907442, 43792231, 36292292, 77927268, 912907331, 978578801, 82897702, 491466901, 743334671, 987488759, 762625463, 815053082, 22556579, 908499163, 723630413, 943554485, 933704825, 114495791, 680244574, 704711488, 111439262, 865233543, 647630109, 52347419, 968677027, 999091970, 556738299, 586445753, 39937116, 768945489, 917909484, 467351091, 482254337, 410651368, 7987297, 368295944, 481742019, 718623833, 576140617, 301479375, 755652757, 218494741, 763514207, 35795743, 992753778, 662334405, 898591105, 66547751, 644331470, 858133770, 383852204, 45194888, 953634340, 451790389, 35435573, 671164082, 176294484, 351472920, 782334083, 359808887, 681603913, 407003192, 308474522, 7603723, 590167637, 856523182, 820788033, 494166907, 43004507, 677692576, 390408896, 140475489, 634359666, 840570768, 149303483, 640321280, 992835875, 172114298, 818254617, 154345160, 196800449, 870605651, 865440961, 645545349, 327890704, 443215535, 852746349, 364380585, 568923977, 818312619, 63375050, 878161899, 921648059, 897560127, 418425432, 284440679, 542351792, 965683742, 752734606, 907002124, 875867413, 694688662, 260466949, 453026551, 251195555, 827102807, 503551288, 117483873, 880521254, 699952443, 892167407, 469449264, 962540888, 119067966, 52097767, 370019264, 822249634, 237120480, 771648639, 229619983, 680015907, 259773735, 620531822, 964404181, 958440491, 109152123, 333219547, 193781724, 685711127, 638406068, 670271563, 605076602, 213092254, 714457410, 205295329, 381785483, 281826390, 107141741, 387628955, 224849215, 6967754, 866444111, 602742426, 279355497, 508943810, 343331898, 979459326, 793307102, 455966229, 25469363, 826766689, 657738639, 756154604, 3624695, 470725288, 231276098, 312329365, 236455213, 601085495, 901161015, 894650449, 114049054, 362928234, 386979036, 997816103, 289805123, 737506189, 14162538, 62659548, 506228345, 54273740, 609048943, 753042874, 344492349, 989024750, 366746787, 394987571, 778983779, 851727632, 210337196, 315177422, 599368778, 25977209, 991853918, 994609967, 575349415, 973313674, 49389215, 466403812, 82441236, 289991756, 855143395, 698308420, 188880105, 436428039, 492881183, 408723908, 859637374, 808369065, 505825384, 951452262, 500512522, 49031023, 260616058, 412675227, 29878651, 764975785, 713258160, 766707885, 905773713, 803331189, 371429170, 737331920, 445933418, 187935799, 780699748, 660234457, 923333660, 163125870, 3991476, 684624305, 80563352, 804861409, 757901773, 815797860, 364058973, 553952872, 83868974, 354103106, 817729704, 877658636, 359056292, 682873215, 293714317, 344608141, 872372077, 214537860, 217298111, 938420095, 302862755, 395850518, 113646516, 883278906, 19270208, 31342527, 844172795, 187697925, 176966527, 636560065, 258450659, 949978853, 129724336, 954913, 950540131, 90605325, 186631946, 226981711, 105359006, 181835443, 245338485, 686744811, 808138529, 390019735, 629602874, 437310030, 73691665, 970863349, 10430738, 300281827, 802245045, 96008232, 906169092, 706334445, 826784106, 937262209, 58085060, 304794421, 315103615, 975683542, 282183879, 301612312, 300834556, 567473423, 937290323, 801586457, 832860641, 714013813, 708233401, 816547758, 311568885, 962305199, 636346220, 48160594, 525040405, 790758484, 407154607, 342774550, 946149627, 156959265, 841250413, 792270972, 733904456, 346966053, 514349511, 99984366, 25454838, 104677203, 281329488, 32508648, 205004338, 319090865, 483562350, 462880311, 946781127, 911773159, 4283891, 717681997, 31503476, 458983926, 567255816, 851122915, 354893353, 185438078, 960458533, 716425891, 468399808, 609153670, 965785236, 789059759, 387255176, 108224705, 701918934, 992656683, 633400565, 719576024, 942140453, 790523771, 916291845, 60217575, 668677123, 513047302, 178909003, 881482632, 747296925, 548026212, 437155518, 918951065, 899946391, 36670825, 43744543, 957469762, 929269243, 321900901, 775543604, 528255018, 381350331, 169838765, 512634493, 262044551, 339271869, 186968777, 687740343, 303338827, 924265341, 327625657, 789825490, 296589615, 121000338, 217147361, 171989322, 867046994, 490484575, 967284733, 644960213, 838526218, 63126637, 819577801, 492741665, 812501999, 510950308, 370290353, 916660987, 152233223, 343799473, 246311854, 271361010, 852694071, 165393390, 21985433, 302780015, 483975089, 682610501, 680128316, 114644779, 321935156, 473979326, 53102426, 917041303, 95249276, 207172258, 877643222, 492897596, 532702135, 745391035, 478657069, 429707160, 344857140, 741626808, 779734593, 877891340, 305583444, 53635336, 496442755, 348421260, 116164597, 73903881, 226879956, 536841269, 709515651, 30514807, 630057303, 875410153, 131384366, 386541987, 307321014, 953786104, 627500870, 377329025, 613973085, 599685896, 708543683, 845486631, 301196854, 894553004, 309986645, 371930700, 416322416, 859917803, 767790141, 389995666, 766570439, 379943099, 676511002, 888140011, 824619763, 802932692, 619700091, 373451745, 487012980, 639054294, 752243809, 756614559, 847645126, 925139828, 23001875, 557583419, 860551136, 823495900, 95460945, 578471809, 12029751, 676216445, 576368335, 78835193, 960033065, 120815665, 961431677, 73146164, 119895268, 630786699, 612866870, 291993453, 954958912, 585347275, 206526983, 707764537, 245423562, 847549272, 954421367, 384826244, 374116154, 247001105, 241289571, 550507082, 249360270, 378750527, 976517503, 646654592, 958797332, 946033733, 883122906, 616017573, 216046746, 999340546, 575014853, 85104325, 219092361, 205951465, 877002932, 676290554, 989326738, 765080455, 3258987, 95568681, 894658473, 434360362, 330810163, 780882948, 163787210, 385914044, 74434897, 723091468, 822439091, 35784547, 118654619, 696559662, 973737505, 598245292, 895487487, 139066955, 915276325, 547380283, 869544707, 306032293, 59434732, 590393084, 267469129, 698611116};
int calc_fact(int n){
	if (n < N) return fact[n];
	int start = (n / C) * C;
	ll val = tbl[n / C];
	while (++start <= n) {
		val = val * start % MOD;
	}
	return (int)val;
}

int f(int n, int k){
	ll a = calc_fact(n);
	ll b = calc_fact(k);
	return a * md_inverse<ll>(b, MOD) % MOD;
}

int solve(){
	char sc[ten(4) + 1], sp[ten(4) + 1];
	scanf("%s%s", sc, sp);
	ll c = 0;
	for (int i = 0; sc[i]; i++) {
		int add = sc[i] - '0';
		c = c * 10 + add;
		if (c >= ten(6) * ll(ten(4))) return 0;
	}
	ll p = 0;
	for (int i = 0; sp[i]; i++) {
		int add = sp[i] - '0';
		p = p* 10 + add;
		if (p >= MOD) return 0;
	}

	ll n = c - p * 2 + 1;
	ll k = p;
	if (n < 0) return 0;
	if (n + k >= MOD) return 0;

	// printf("%d %d\n",(int)n + k,(int)n);

	return f((int)(n + k), (int)n);
}

int main(){
	init();
	int n; cin >> n;
	ll ans = 1;
	while (n--) {
		int ans = solve();
		printf("%d\n",ans);
	}
}