import core.thread;
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex;

//	Input
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { tokens = readln.split; if (tokens.empty && stdin.eof) throw new EOFException; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return to!int(readToken); }
long readLong() { return to!long(readToken); }
real readReal() { return to!real(readToken); }

//	chmin/chmax
void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

//	Pair
struct Pair(S, T) {
	S x; T y;
	int opCmp(    const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	int opCmp(ref const Pair p) const { return (x < p.x) ? -1 : (x > p.x) ? +1 : (y < p.y) ? -1 : (y > p.y) ? +1 : 0; }
	string toString() const { return "(" ~ to!string(x) ~ ", " ~ to!string(y) ~ ")"; }
}
auto pair(S, T)(inout(S) x, inout(T) y) { return Pair!(S, T)(x, y); }

//	Array
int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = as.length; for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <  val); }); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) { return (a <= val); }); }
T[] unique(T)(in T[] as) { T[] bs; foreach (a; as) if (bs.empty || bs[$ - 1] != a) bs ~= a; return bs; }


immutable long MO = 10^^9 + 7;

immutable STEP = 10^^6;
long[] FACS = 
[1, 641102369, 578095319, 5832229, 259081142, 974067448, 316220877, 690120224, 251368199, 980250487, 682498929, 134623568, 95936601, 933097914, 167332441, 598816162, 336060741, 248744620, 626497524, 288843364, 491101308, 245341950, 565768255, 246899319, 968999, 586350670, 638587686, 881746146, 19426633, 850500036, 76479948, 268124147, 842267748, 886294336, 485348706, 463847391, 544075857, 898187927, 798967520, 82926604, 723816384, 156530778, 721996174, 299085602, 323604647, 172827403, 398699886, 530389102, 294587621, 813805606, 67347853, 497478507, 196447201, 722054885, 228338256, 407719831, 762479457, 746536789, 811667359, 778773518, 27368307, 438371670, 59469516, 5974669, 766196482, 606322308, 86609485, 889750731, 340941507, 371263376, 625544428, 788878910, 808412394, 996952918, 585237443, 1669644, 361786913, 480748381, 595143852, 837229828, 199888908, 526807168, 579691190, 145404005, 459188207, 534491822, 439729802, 840398449, 899297830, 235861787, 888050723, 656116726, 736550105, 440902696, 85990869, 884343068, 56305184, 973478770, 168891766, 804805577, 927880474, 876297919, 934814019, 676405347, 567277637, 112249297, 44930135, 39417871, 47401357, 108819476, 281863274, 60168088, 692636218, 432775082, 14235602, 770511792, 400295761, 697066277, 421835306, 220108638, 661224977, 261799937, 168203998, 802214249, 544064410, 935080803, 583967898, 211768084, 751231582, 972424306, 623534362, 335160196, 243276029, 554749550, 60050552, 797848181, 395891998, 172428290, 159554990, 887420150, 970055531, 250388809, 487998999, 856259313, 82104855, 232253360, 513365505, 244109365, 1559745, 695345956, 261384175, 849009131, 323214113, 747664143, 444090941, 659224434, 80729842, 570033864, 664989237, 827348878, 195888993, 576798521, 457882808, 731551699, 212938473, 509096183, 827544702, 678320208, 677711203, 289752035, 66404266, 555972231, 195290384, 97136305, 349551356, 785113347, 83489485, 66247239, 52167191, 307390891, 547665832, 143066173, 350016754, 917404120, 296269301, 996122673, 23015220, 602139210, 748566338, 187348575, 109838563, 574053420, 105574531, 304173654, 542432219, 34538816, 325636655, 437843114, 630621321, 26853683, 933245637, 616368450, 238971581, 511371690, 557301633, 911398531, 848952161, 958992544, 925152039, 914456118, 724691727, 636817583, 238087006, 946237212, 910291942, 114985663, 492237273, 450387329, 834860913, 763017204, 368925948, 475812562, 740594930, 45060610, 806047532, 464456846, 172115341, 75307702, 116261993, 562519302, 268838846, 173784895, 243624360, 61570384, 481661251, 938269070, 95182730, 91068149, 115435332, 495022305, 136026497, 506496856, 710729672, 113570024, 366384665, 564758715, 270239666, 277118392, 79874094, 702807165, 112390913, 730341625, 103056890, 677948390, 339464594, 167240465, 108312174, 839079953, 479334442, 271788964, 135498044, 277717575, 591048681, 811637561, 353339603, 889410460, 839849206, 192345193, 736265527, 316439118, 217544623, 788132977, 618898635, 183011467, 380858207, 996097969, 898554793, 335353644, 54062950, 611251733, 419363534, 965429853, 160398980, 151319402, 990918946, 607730875, 450718279, 173539388, 648991369, 970937898, 500780548, 780122909, 39052406, 276894233, 460373282, 651081062, 461415770, 358700839, 643638805, 560006119, 668123525, 686692315, 673464765, 957633609, 199866123, 563432246, 841799766, 385330357, 504962686, 954061253, 128487469, 685707545, 299172297, 717975101, 577786541, 318951960, 773206631, 306832604, 204355779, 573592106, 30977140, 450398100, 363172638, 258379324, 472935553, 93940075, 587220627, 776264326, 793270300, 291733496, 522049725, 579995261, 335416359, 142946099, 472012302, 559947225, 332139472, 499377092, 464599136, 164752359, 309058615, 86117128, 580204973, 563781682, 954840109, 624577416, 895609896, 888287558, 836813268, 926036911, 386027524, 184419613, 724205533, 403351886, 715247054, 716986954, 830567832, 383388563, 68409439, 6734065, 189239124, 68322490, 943653305, 405755338, 811056092, 179518046, 825132993, 343807435, 985084650, 868553027, 148528617, 160684257, 882148737, 591915968, 701445829, 529726489, 302177126, 974886682, 241107368, 798830099, 940567523, 11633075, 325334066, 346091869, 115312728, 473718967, 218129285, 878471898, 180002392, 699739374, 917084264, 856859395, 435327356, 808651347, 421623838, 105419548, 59883031, 322487421, 79716267, 715317963, 429277690, 398078032, 316486674, 384843585, 940338439, 937409008, 940524812, 947549662, 833550543, 593524514, 996164327, 987314628, 697611981, 636177449, 274192146, 418537348, 925347821, 952831975, 893732627, 1277567, 358655417, 141866945, 581830879, 987597705, 347046911, 775305697, 125354499, 951540811, 247662371, 343043237, 568392357, 997474832, 209244402, 380480118, 149586983, 392838702, 309134554, 990779998, 263053337, 325362513, 780072518, 551028176, 990826116, 989944961, 155569943, 596737944, 711553356, 268844715, 451373308, 379404150, 462639908, 961812918, 654611901, 382776490, 41815820, 843321396, 675258797, 845583555, 934281721, 741114145, 275105629, 666247477, 325912072, 526131620, 252551589, 432030917, 554917439, 818036959, 754363835, 795190182, 909210595, 278704903, 719566487, 628514947, 424989675, 321685608, 50590510, 832069712, 198768464, 702004730, 99199382, 707469729, 747407118, 302020341, 497196934, 5003231, 726997875, 382617671, 296229203, 183888367, 703397904, 552133875, 732868367, 350095207, 26031303, 863250534, 216665960, 561745549, 352946234, 784139777, 733333339, 503105966, 459878625, 803187381, 16634739, 180898306, 68718097, 985594252, 404206040, 749724532, 97830135, 611751357, 31131935, 662741752, 864326453, 864869025, 167831173, 559214642, 718498895, 91352335, 608823837, 473379392, 385388084, 152267158, 681756977, 46819124, 313132653, 56547945, 442795120, 796616594, 256141983, 152028387, 636578562, 385377759, 553033642, 491415383, 919273670, 996049638, 326686486, 160150665, 141827977, 540818053, 693305776, 593938674, 186576440, 688809790, 565456578, 749296077, 519397500, 551096742, 696628828, 775025061, 370732451, 164246193, 915265013, 457469634, 923043932, 912368644, 777901604, 464118005, 637939935, 956856710, 490676632, 453019482, 462528877, 502297454, 798895521, 100498586, 699767918, 849974789, 811575797, 438952959, 606870929, 907720182, 179111720, 48053248, 508038818, 811944661, 752550134, 401382061, 848924691, 764368449, 34629406, 529840945, 435904287, 26011548, 208184231, 446477394, 206330671, 366033520, 131772368, 185646898, 648711554, 472759660, 523696723, 271198437, 25058942, 859369491, 817928963, 330711333, 724464507, 437605233, 701453022, 626663115, 281230685, 510650790, 596949867, 295726547, 303076380, 465070856, 272814771, 538771609, 48824684, 951279549, 939889684, 564188856, 48527183, 201307702, 484458461, 861754542, 326159309, 181594759, 668422905, 286273596, 965656187, 44135644, 359960756, 936229527, 407934361, 267193060, 456152084, 459116722, 124804049, 262322489, 920251227, 816929577, 483924582, 151834896, 167087470, 490222511, 903466878, 361583925, 368114731, 339383292, 388728584, 218107212, 249153339, 909458706, 322908524, 202649964, 92255682, 573074791, 15570863, 94331513, 744158074, 196345098, 334326205, 9416035, 98349682, 882121662, 769795511, 231988936, 888146074, 137603545, 582627184, 407518072, 919419361, 909433461, 986708498, 310317874, 373745190, 263645931, 256853930, 876379959, 702823274, 147050765, 308186532, 175504139, 180350107, 797736554, 606241871, 384547635, 273712630, 586444655, 682189174, 666493603, 946867127, 819114541, 502371023, 261970285, 825871994, 126925175, 701506133, 314738056, 341779962, 561011609, 815463367, 46765164, 49187570, 188054995, 957939114, 64814326, 933376898, 329837066, 338121343, 765215899, 869630152, 978119194, 632627667, 975266085, 435887178, 282092463, 129621197, 758245605, 827722926, 201339230, 918513230, 322096036, 547838438, 985546115, 852304035, 593090119, 689189630, 555842733, 567033437, 469928208, 212842957, 117842065, 404149413, 155133422, 663307737, 208761293, 206282795, 717946122, 488906585, 414236650, 280700600, 962670136, 534279149, 214569244, 375297772, 811053196, 922377372, 289594327, 219932130, 211487466, 701050258, 398782410, 863002719, 27236531, 217598709, 375472836, 810551911, 178598958, 247844667, 676526196, 812283640, 863066876, 857241854, 113917835, 624148346, 726089763, 564827277, 826300950, 478982047, 439411911, 454039189, 633292726, 48562889, 802100365, 671734977, 945204804, 508831870, 398781902, 897162044, 644050694, 892168027, 828883117, 277714559, 713448377, 624500515, 590098114, 808691930, 514359662, 895205045, 715264908, 628829100, 484492064, 919717789, 513196123, 748510389, 403652653, 574455974, 77123823, 172096141, 819801784, 581418893, 15655126, 15391652, 875641535, 203191898, 264582598, 880691101, 907800444, 986598821, 340030191, 264688936, 369832433, 785804644, 842065079, 423951674, 663560047, 696623384, 496709826, 161960209, 331910086, 541120825, 951524114, 841656666, 162683802, 629786193, 190395535, 269571439, 832671304, 76770272, 341080135, 421943723, 494210290, 751040886, 317076664, 672850561, 72482816, 493689107, 135625240, 100228913, 684748812, 639655136, 906233141, 929893103, 277813439, 814362881, 562608724, 406024012, 885537778, 10065330, 60625018, 983737173, 60517502, 551060742, 804930491, 823845496, 727416538, 946421040, 678171399, 842203531, 175638827, 894247956, 538609927, 885362182, 946464959, 116667533, 749816133, 241427979, 871117927, 281804989, 163928347, 563796647, 640266394, 774625892, 59342705, 256473217, 674115061, 918860977, 322633051, 753513874, 393556719, 304644842, 767372800, 161362528, 754787150, 627655552, 677395736, 799289297, 846650652, 816701166, 687265514, 787113234, 358757251, 701220427, 607715125, 245795606, 600624983, 10475577, 728620948, 759404319, 36292292, 491466901, 22556579, 114495791, 647630109, 586445753, 482254337, 718623833, 763514207, 66547751, 953634340, 351472920, 308474522, 494166907, 634359666, 172114298, 865440961, 364380585, 921648059, 965683742, 260466949, 117483873, 962540888, 237120480, 620531822, 193781724, 213092254, 107141741, 602742426, 793307102, 756154604, 236455213, 362928234, 14162538, 753042874, 778983779, 25977209, 49389215, 698308420, 859637374, 49031023, 713258160, 737331920, 923333660, 804861409, 83868974, 682873215, 217298111, 883278906, 176966527, 954913, 105359006, 390019735, 10430738, 706334445, 315103615, 567473423, 708233401, 48160594, 946149627, 346966053, 281329488, 462880311, 31503476, 185438078, 965785236, 992656683, 916291845, 881482632, 899946391, 321900901, 512634493, 303338827, 121000338, 967284733, 492741665, 152233223, 165393390, 680128316, 917041303, 532702135, 741626808, 496442755, 536841269, 131384366, 377329025, 301196854, 859917803, 676511002, 373451745, 847645126, 823495900, 576368335, 73146164, 954958912, 847549272, 241289571, 646654592, 216046746, 205951465, 3258987, 780882948, 822439091, 598245292, 869544707, 698611116]
;
long[] FACINVS = 
[1, 397802501, 407182070, 595906132, 647658926, 255895843, 409881587, 748897706, 681174448, 483451905, 979208068, 196993094, 112271875, 633213064, 802923624, 463505190, 712513461, 392362326, 76168201, 452927234, 278462671, 956747750, 170616541, 331831274, 366901310, 258153927, 815185742, 24033837, 127468101, 238763252, 906890908, 833223065, 274718346, 504985265, 506581622, 977200631, 756778283, 403458836, 743855997, 132875441, 24291875, 394859645, 693171649, 823391648, 579059717, 908866808, 531546554, 384186605, 302328602, 246257267, 691630620, 667373725, 99702928, 428174659, 974221729, 956585025, 949208793, 641860154, 858967799, 869462903, 714904365, 812042392, 542604403, 948589962, 839035230, 354171436, 312390637, 238692390, 843714400, 521210997, 847953656, 508862152, 211377712, 523500630, 15116415, 18004437, 124047379, 836753012, 372791119, 123564066, 236012222, 649431428, 412008381, 503553341, 613022026, 29924314, 302123739, 905367578, 500609181, 592451201, 849551192, 403359976, 722539583, 726233861, 442737871, 434949306, 564703833, 716422282, 415904275, 794609529, 16012583, 253955222, 73245174, 505287461, 91801617, 59794121, 639050655, 705814837, 492783132, 272700828, 94731310, 799296420, 281621283, 948135119, 584532713, 754845643, 640337280, 539752685, 981755140, 399439933, 810320480, 500933176, 536537102, 431344362, 72429434, 426545883, 711679360, 898545025, 166145757, 254749464, 524254343, 31714521, 511973524, 705728846, 879019020, 695803371, 86074827, 322873627, 780293226, 382219639, 799307731, 421895428, 729156052, 145813538, 458706763, 763423781, 789770857, 841663770, 457800477, 628223077, 858843247, 692730253, 356955517, 116733875, 828632761, 92136317, 325817895, 154704917, 186328408, 218821930, 990830140, 976189417, 217189534, 49236187, 533377671, 313469190, 454213708, 574413923, 803159035, 275297851, 937136711, 925154218, 827779222, 119141675, 630118999, 867603714, 333280858, 123659962, 339857481, 618796236, 533485381, 310061347, 241855233, 85501183, 686755505, 581131008, 682060702, 885648222, 499316529, 837015617, 304303264, 562337246, 816404125, 76036313, 30531920, 794222280, 854012961, 902161206, 97064494, 15134237, 880818041, 970014301, 347351594, 911238634, 401461326, 873818124, 664285737, 439886811, 581626041, 359677536, 561088479, 483925269, 116726140, 745440937, 592983567, 160001131, 363083263, 465050038, 885470463, 676239065, 735508002, 321538413, 827365050, 876612795, 811080880, 854570622, 611417420, 487053811, 223021888, 455635122, 512435513, 333274980, 202767315, 74827031, 566773998, 10555615, 632449578, 518565622, 745206135, 920233524, 135448729, 131618273, 626006705, 150849322, 511896338, 727964242, 463901461, 950241725, 380365569, 50717699, 897230826, 157886534, 631446063, 189134866, 559471673, 395256689, 775076988, 440381169, 911242510, 644445336, 473022160, 236147037, 964343580, 395040047, 468643596, 377859666, 100267985, 635818270, 849902768, 130005429, 222525690, 765225548, 959600244, 280728668, 973419251, 829066509, 27564997, 810350076, 777201527, 912036866, 477119311, 400480342, 101399754, 597677723, 490656767, 788022100, 362457337, 869685665, 972768714, 738064679, 186000287, 882706558, 516649682, 973833875, 849570453, 249156788, 514654882, 94910024, 468124384, 297147382, 741191811, 573159858, 838634425, 11836810, 652154497, 141859750, 776775946, 3957887, 905431595, 334704052, 375502216, 588052170, 873065546, 218698938, 431217545, 556387922, 454486606, 222993895, 469576090, 853113178, 290058316, 29532889, 740303004, 646967395, 802911042, 941264765, 205576702, 193724010, 401233929, 818295924, 981768280, 670647224, 540048523, 682429030, 443432380, 681368248, 69495652, 93583118, 743601924, 536201625, 824254887, 148481230, 132435286, 654410197, 141490511, 28985949, 591345807, 594369330, 899123997, 163332469, 125361966, 211208844, 611838438, 691977637, 305247186, 330841142, 401644897, 142370020, 334621998, 323925744, 236653734, 899251146, 41218615, 131632751, 166531207, 875781837, 45209230, 645755926, 21879396, 839780296, 553481775, 962728745, 598160321, 723987436, 281321153, 251029206, 198526461, 920740012, 312640141, 189922855, 837247781, 985262459, 4027076, 779602964, 112617725, 37365783, 727440807, 438952361, 423659623, 339891013, 924777066, 339016682, 66438915, 340804077, 974350653, 251970623, 846183393, 669829511, 810556501, 378262971, 334384482, 20867851, 110323322, 999059864, 703984570, 868161385, 251011167, 168781503, 635653304, 142180681, 34419712, 493765779, 113300165, 828414007, 611793221, 287196434, 857948506, 579099149, 453782368, 48546965, 808286473, 353877694, 750700815, 829305646, 674662552, 357695500, 153407371, 46842028, 881155210, 704930031, 786095764, 822385781, 885909905, 119355654, 689780512, 160496960, 37168731, 390034763, 949553321, 675109617, 712114351, 878765104, 252898363, 128950679, 576671418, 390772742, 43706644, 761445407, 440465971, 299708524, 100666874, 817552975, 547487719, 146101103, 460155442, 933950072, 809276577, 234453381, 495985900, 933889525, 663725664, 595927271, 504902740, 975468459, 140277685, 918690763, 530502953, 881359693, 690868559, 634406181, 244916920, 264827363, 701617497, 463749536, 759938425, 966353444, 416101501, 948674741, 562988834, 809178082, 845038849, 352162581, 690451354, 633091512, 798403149, 244346505, 872392662, 571652859, 471198270, 834862284, 170092986, 578162514, 457577185, 953292155, 421789185, 544425239, 98138430, 294420585, 370799202, 886992543, 875000008, 50984840, 438317520, 686243991, 398616777, 720293566, 465331079, 831577247, 733906448, 610816118, 755353067, 138000334, 288524856, 549897420, 371752017, 230083085, 394631714, 688930530, 625949585, 672233692, 912887499, 200321846, 445423160, 180257526, 911535706, 312227480, 880865369, 161472571, 471487171, 395025840, 323122651, 512762380, 56668555, 562954658, 972226078, 865542286, 918431856, 84561215, 262086818, 418316324, 872242991, 179152131, 20085973, 885424694, 366859918, 874239928, 874166802, 371545327, 372393703, 981177328, 697397967, 387042607, 940963521, 443313846, 587197768, 295788227, 471818414, 74199417, 166868423, 103554531, 619904999, 135440183, 438161992, 573102114, 516967181, 180761676, 364623828, 446479071, 136236471, 111772043, 303340921, 158281513, 591046991, 218445561, 662053035, 802908167, 383086464, 15966773, 661380631, 160573702, 93713940, 298346996, 677677150, 183928816, 441154889, 96071830, 111136790, 636050700, 885131936, 149271076, 864224234, 376569435, 174010133, 747340159, 455170644, 565156694, 816229398, 472598959, 758319527, 990763937, 17637085, 7719405, 224179951, 91175986, 299548812, 979349607, 680447363, 356899669, 42533559, 581843234, 573641506, 979886473, 87789386, 682425014, 654074447, 791468345, 223400853, 812204573, 989785802, 736627156, 280095095, 333927938, 360014359, 130273926, 321913610, 599151316, 507182806, 139542043, 541534844, 424186084, 8888643, 649260950, 438209640, 596965280, 456065701, 979289961, 877905727, 436776915, 572845993, 705254752, 211541865, 734430973, 24569256, 492468186, 773031507, 841806507, 214541742, 495405244, 815827342, 296108483, 524057362, 431529236, 156028026, 554028656, 379342536, 48624596, 384720315, 269549446, 655298463, 539703314, 408513410, 626071521, 817959317, 669512240, 525083847, 662197820, 576697205, 774007231, 105697405, 751924295, 443947461, 731401716, 686221224, 73334570, 57446207, 118189947, 871052233, 837409829, 96964135, 833407621, 815294334, 384884991, 633148599, 688217893, 481225475, 703140383, 479274287, 317475885, 469031363, 534234438, 959711762, 756844792, 368954144, 998378090, 428278449, 974512274, 38474869, 542917484, 911399919, 570129912, 213451675, 123256563, 567650592, 280467689, 59969903, 131799735, 417609066, 761942169, 746339599, 426798349, 324109084, 329022157, 302910999, 989138153, 629698548, 298780061, 142222217, 156720244, 446989254, 231319220, 113256407, 319970499, 967795934, 407917089, 520584452, 830427740, 5705587, 684842442, 421566133, 537663158, 716796096, 609557869, 393700442, 170557386, 180045494, 886573314, 480868434, 345347191, 846911855, 95582073, 610034196, 635817388, 852107294, 829124490, 121303864, 238128927, 126232430, 345748269, 559826378, 753036653, 358443085, 547399233, 255928206, 588089611, 683418091, 20005258, 788533943, 57899677, 518707359, 628483525, 8156146, 904089738, 189379476, 826794598, 935736623, 531496568, 956919221, 939135052, 372744919, 606090181, 70475229, 113253400, 22445935, 449561977, 787207362, 674986134, 429788856, 929222791, 564673331, 96489813, 524064955, 534016408, 623656119, 655204862, 340177701, 297671646, 331581758, 582530101, 989914025, 428975847, 888538749, 803585030, 664873005, 209424332, 736593663, 336454924, 251963006, 739337587, 651468281, 981142321, 240956366, 880658140, 590602880, 827285749, 654079054, 939578563, 300760624, 88309938, 162504280, 78906669, 489277904, 708556334, 316850200, 179773129, 295332944, 8688567, 919777132, 655029980, 212752971, 413737180, 162605168, 592085932, 505845365, 993251876, 319086966, 951536680, 729952805, 599583386, 52295136, 746256983, 575763403, 129733716, 652331888, 74288658, 840026077, 480432593, 836910239, 341319387, 526135675, 381945172, 530392017, 528944466, 109117530, 326808071, 159906035, 469933505, 970748832, 365794364, 980544687, 470457699, 398885127, 950475459, 670760977, 123514760, 756023245, 76752187, 388766231, 689694987, 820173609, 588424675, 309699411, 186176817, 13232087, 985781917, 912579833, 840616016, 702505788, 852126471, 458273186, 28617452, 225163957, 786508803, 884677368, 888123263, 773214927, 763700434, 533072909, 683296125, 717766307, 253023529, 569293974, 722674588, 661615187, 946692368, 385348113, 349250093, 511553805, 99037369, 313457043, 386900620, 805028469, 857340767, 590026501, 354471421, 304943651, 131757152, 761495370, 816577289, 191178374, 461202671, 530531635, 531677329, 161457634, 515204481, 657050744, 472284377, 843341271, 370457142, 268190919, 834190900, 959487620, 6399384, 267205627, 512276214, 546530869, 742048003, 907161528, 401285922, 676982343, 512407132, 201142009, 867210848, 216704507, 680476655, 87287288, 3291360, 170952409, 34865987, 552758203, 796214351, 393273998, 508154517, 955563119, 409893352, 498191862, 344511048, 901802822, 960731148, 713827677, 580291654, 688083312, 245215458, 441580105, 320289493, 813023776, 21742295, 239571140, 373303733, 517590897, 676596694, 454917323, 578660924, 259709528, 249788636, 174438566, 682942036, 627724294, 727424350, 725648597, 563172531, 774895240, 454561861, 180625697, 628182311, 821140613, 423382698, 390767473, 661351428, 44427901, 366453085, 271775836, 755243097, 164594348, 235052831, 233212601, 309088555, 683827649, 189962693, 462883139, 228171495, 333345501, 13456970, 266096065, 109095449, 430411011, 585503694, 92982075, 771647596, 415929962, 203144885, 9212832, 818057712, 242778355, 513838555, 336901500, 118614466, 4232733, 713358135, 635175619, 136721491, 999999287]
;

long inv(long x) {
	long ret = 1;
	for (long e = MO - 2; e; e >>= 1, (x *= x) %= MO) if (e & 1) {
		(ret *= x) %= MO;
	}
	return ret;
}

long fac(int n) {
	/*
	long ret = 1;
	for (int k = 1; k <= n; ++k) {
		(ret *= k) %= MO;
	}
	return ret;
	*/
	long ret = FACS[n / STEP];
	long now = 1;
	for (int k = n / STEP * STEP + 1; k <= n; ++k) {
		(now *= k) %= MO;
	}
	(ret *= now) %= MO;
	return ret;
}
long facInv(int n) {
	/*
	return inv(fac(n));
	*/
	long ret = FACINVS[n / STEP];
	long now = 1;
	for (int k = n / STEP * STEP + 1; k <= n; ++k) {
		(now *= k) %= MO;
	}
	(ret *= inv(now)) %= MO;
	return ret;
}

long binom(BigInt n, BigInt k) {
debug{
writeln("binom ",n," ",k);
}
	long ret = 1;
	for (; k > 0; n /= MO, k /= MO) {
		const nn = n % cast(int)(MO);
		const kk = k % cast(int)(MO);
		if (nn < kk) {
			return 0;
		}
		(ret *= fac(nn)) %= MO;
		(ret *= facInv(kk)) %= MO;
		(ret *= facInv(nn - kk)) %= MO;
	}
	return ret;
}

BigInt C, P;

void main(string[] args) {
	/*
	long[] facs, facInvs;
	facs ~= 1;
	facInvs ~= 1;
	long now = 1;
	for (long k = 1; k <= MO; ++k) {
		(now *= k) %= MO;
		if (k % STEP == 0) {
			facs ~= now;
			facInvs ~= inv(now);
		}
	}
	writeln(facs);
	writeln(facInvs);
	return;
	*/
	
	try {
	for (; ; ) {
		foreach (tc; 0 .. readInt) {
			C = readToken.to!BigInt;
			P = readToken.to!BigInt;
			
			const c = C + 1 - P * 2;
			const ans = (c >= 0) ? binom(P + c, P) : 0;
			writeln(ans);
			
		}
	}
	} catch (EOFException) {}
}