rectpath

#include <iostream>
#include <stdio.h>
using namespace std;
const long long Mod = 1000000007;
#define LL long long
LL Table[800005] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063, 72847302, 602640637, 860734560, 657629300, 440732388, 459042011, 394134213, 35757887, 36978716, 109361473, 390205642, 486580460, 57155068, 943272305, 14530444, 523095984, 354551275, 472948359, 444985875, 799434881, 776829897, 626855450, 954784168, 10503098, 472639410, 741412713, 846397273, 627068824, 726372166, 318608048, 249010336, 948537388, 272481214, 713985458, 269199917, 75195247, 286129051, 595484846, 133605669, 16340084, 996745124, 798197261, 286427093, 331333826, 536698543, 422103593, 280940535, 103956247, 172980994, 108669496, 715534167, 518459667, 847555432, 719101534, 932614679, 878715114, 661063309, 562937745, 472081547, 766523501, 88403147, 249058005, 671814275, 432398708, 753889928, 834533360, 604401816, 187359437, 674989781, 749079870, 166267694, 296627743, 586379910, 119711155, 372559648, 765725963, 275417893, 990953332, 104379182, 437918130, 229730822, 432543683, 551999041, 407899865, 829485531, 925465677, 24826746, 681288554, 260451868, 649705284, 117286020, 136034149, 371858732, 391895154, 67942395, 881317771, 114178486, 473061257, 294289191, 314702675, 79023409, 640855835, 825267159, 333127002, 640874963, 750244778, 281086141, 979025803, 294327705, 262601384, 400781066, 903100348, 112345444, 54289391, 329067736, 753211788, 190014235, 221964248, 853030262, 424235847, 817254014, 50069176, 159892119, 24464975, 547421354, 923517131, 757017312, 38561392, 745647373, 847105173, 912880234, 757794602, 942573301, 156287339, 224537377, 27830567, 369398991, 365040172, 41386942, 621910678, 127618458, 674190056, 892978365, 448450838, 994387759, 68366839, 417262036, 100021558, 903643190, 619341229, 907349424, 64099836, 89271551, 533249769, 318708924, 92770232, 420330952, 818908938, 584698880, 245797665, 489377057, 66623751, 192146349, 354927971, 661674180, 71396619, 351167662, 19519994, 689278845, 962979640, 929109959, 389110882, 98399701, 89541861, 460662776, 289903466, 110982403, 974515647, 928612402, 722479105, 218299090, 96415872, 572421883, 774063320, 682979494, 693774784, 611379287, 166890807, 880178425, 837467962, 705738750, 616613957, 338771924, 497191232, 896114138, 560652457, 661582322, 224945188, 262995829, 859081981, 857116478, 279856786, 408062844, 406076419, 367193638, 985761614, 767884817, 77737051, 801784560, 410447512, 813374614, 702909132, 777826615, 11426636, 685259446, 721228129, 931065383, 593559607, 860745086, 578819198, 495425745, 893029457, 6156532, 502193801, 37480384, 220174401, 383076669, 3013247, 750298503, 574624441, 230733683, 144887710, 656590378, 773954850, 358485371, 772254339, 469363737, 95843299, 823414273, 87709482, 892174648, 749756145, 185864756, 68295241, 98238739, 131504392, 111672419, 928208089, 687974198, 753032165, 71715287, 506557931, 290314197, 546089425, 174590825, 187067364, 817659471, 309331349, 303445769, 964814732, 112937795, 848457973, 113604679, 263728612, 162653895, 519013648, 956915940, 591788795, 26960558, 818561771, 201473695, 830318534, 283328761, 298655153, 103269519, 567777414, 629890782, 707451727, 528064896, 419467694, 259775012, 452053078, 972081682, 512829263, 412924123, 354780756, 917691336, 648929514, 519218426, 957710940, 848100261, 607279584, 78508462, 651656900, 271922065, 927371945, 976904514, 655633282, 147015495, 44958071, 431540693, 956102180, 821001984, 4640954, 508310043, 709072863, 866824584, 318461564, 773853828, 371761455, 53040744, 609526889, 972452623, 799173814, 723225821, 3874155, 305590228, 289496343, 139259591, 348260611, 756867525, 848691744, 101266155, 835557082, 267191274, 448180160, 518514435, 443022120, 614718802, 151579195, 204297074, 912569551, 137049249, 515433810, 979001276, 524451820, 229298431, 88837724, 892742699, 387369393, 840349900, 206661672, 18186411, 619853562, 246548548, 236767938, 893832644, 930410696, 321544423, 971435684, 402636244, 780681725, 194281388, 661238608, 964476271, 643075362, 439409780, 96895678, 723461710, 915447882, 785640606, 114709392, 933696835, 539582134, 739120141, 300372431, 244129985, 722433522, 26638091, 388855420, 42468156, 647517040, 474194942, 832805846, 958306874, 489519451, 339220689, 9833277, 923477502, 390998217, 790283925, 694135631, 736657340, 609563281, 873127083, 489593220, 264439147, 891171227, 489029295, 502009550, 325923608, 280525558, 857054649, 820622208, 558213940, 216997416, 487921842, 951328535, 606653379, 794417402, 449723904, 783486165, 414645478, 809681447, 114612567, 824953206, 255016498, 147060381, 88903008, 228293174, 394357308, 362355866, 900088886, 638573794, 779598451, 904922263, 451026166, 549459329, 212643744, 563246709, 391796933, 174243175, 189725986, 238337196, 60051478, 782959006, 982673239, 237607992, 685987666, 694447544, 195840153, 519748540, 446086975, 523485236, 185780714, 716004996, 214280883, 140643728, 555470704, 516522055, 116665689, 899547947, 490696549, 683197147, 686671136, 988747143, 744912554, 619072836, 345158054, 224284246, 637879131, 78947725, 342273666, 237716550, 915360466, 711578771, 423071394, 228124918, 271834959, 480779410, 254894593, 859192972, 990202578, 258044399, 151532640, 644862529, 48049425, 448119239, 130306338, 850105179, 401639970, 606863861, 183881380, 837401090, 513536652, 714177614, 946271680, 243293343, 403377310, 688653593, 15447678, 754734307, 631353768, 202296846, 159906516, 912696536, 737140518, 467380526, 896686075, 309895051, 356369955, 461415686, 706245266, 10064183, 183054210, 455971702, 737368289, 956771035, 564163693, 365118309, 226637659, 304857172, 440299843, 717116122, 485961418, 615704083, 476049473, 354119987, 329471814, 620060202, 251964959, 45357250, 175414082, 671119137, 48735782, 122378970, 717506435, 18459328, 949577729, 771970076, 635808197, 608040366, 165916428, 258536202, 902229110, 617090616, 548564593, 613394864, 753777984, 577888302, 416452176, 881599549, 524547188, 599140122, 522765386, 657552586, 256787840, 287613719, 776067801, 597965522, 458655497, 764387515, 350167935, 494713961, 513386012, 576480762, 864589772, 86987059, 495636228, 512647986, 721997962, 982831380, 162376799, 204281975, 462134806, 189646394, 425968575, 209834628, 494248765, 664281698, 947663843, 540352769, 25662122, 986679150, 207298711, 477043799, 24708053, 528335066, 189351697, 717500453, 42764755, 316734785, 823726196, 293357001, 547414377, 258966410, 602945692, 561521296, 351253952, 752369730, 174204566, 871148004, 302242737, 554611874, 540181425, 349941261, 414343943, 921115587, 959388563, 227019335, 708812719, 793380997, 342547759, 324322556, 458370547, 356254978, 809319893, 159690374, 848340820, 971304725, 180230004, 103061704, 207441144, 443272953, 45593686, 541647240, 612817107, 849140508, 109375794, 906749744, 159084460, 541378020, 692284266, 908221578, 720697998, 363923522, 819281897, 701846632, 479994712, 196613531, 29272489, 792937812, 859009553, 202148261, 385627435, 115321267, 612859231, 132778909, 173511339, 782369566, 322583903, 324703286, 31244274, 433755056, 109559692, 871157455, 350443931, 592104988, 197184362, 141678010, 649163959, 746537855, 954594407, 850681817, 703404350, 467293824, 684978431, 565588709, 378843675, 825260479, 749777538, 850502015, 387852091, 412307507, 307565279, 914127155, 864079609, 845970807, 414173935, 638273833, 664477235, 173471099, 480759791, 839694748, 190898355, 956270620, 957911348, 43002811, 628936576, 966234409, 667971950, 236586166, 954211897, 223051884, 21058295, 656573222, 631532535, 809706350, 984734695, 314281677, 311454037, 640732448, 434907794, 175084834, 434807109, 973816812, 488481268, 844735329, 917344075, 314288693, 459259162, 992521062, 667512257, 603748166, 679935673, 833938466, 933875943, 522922384, 981191471, 457854178, 112860028, 484939649, 611363777, 627371454, 844300972, 962501388, 738504183, 631041465, 29224765, 334078303, 211237785, 626057542, 900175080, 728504100, 450509755, 575177363, 905713570, 416609984, 874776027, 334255451, 683287462, 999293262, 474888472, 317020697, 180417613, 591538360, 879151833, 605566485, 569294094, 970567518, 896200922, 943088633, 145735679, 884701203, 949403596, 749113557, 78958680, 850679027, 665376978, 686499745, 426302291, 842343474, 708066168, 962548572, 349652428, 833757979, 492365420, 136639914, 76093131, 591710464, 208764552, 166233017, 498121245, 545840935, 26721664, 736011124, 880639351, 137410283, 42609708, 235572009, 981737748, 718913567, 909319027, 906112184, 298059463, 274736280, 217450848, 351267027, 149682364, 249066734, 11785215, 333890217, 774940233, 302540697, 519852435, 802535369, 620684620, 306323295, 752310997, 848793393, 883503040, 569433124, 254795373, 855478464, 660158704, 87911700, 944741410, 351053939, 2634663, 134077016, 736459220, 4882454, 969435081, 120150411, 922584286, 828772112, 106810765, 371205161, 17024731, 960279329, 389323593, 23991206, 744762405, 684217429, 479374977, 963728237, 3246420, 688035746, 381629444, 752436308, 274567573, 440219140, 702541058, 919238277, 563955926, 467150839, 5249506, 399086000, 833151662, 847391187, 655983283, 337920422, 866913758, 675206635, 549602585, 963783662, 324756002, 393087771, 731515248, 787956453, 550936813, 398161393, 631665856, 442637251, 454846959, 348994181, 88011024, 513458067, 60476466, 9760396, 403700900, 990173371, 519613195, 945797344, 114696834, 327457551, 905694736, 143025346, 289024806, 451579463, 325709522, 18701196, 326143996, 49850509, 619195074, 414881030, 850660769, 880149960, 651809429, 592293509, 810577782, 929598726, 835669318, 731671946, 529667681, 285562083, 293565850, 686472980, 274474950, 282703792, 889076915, 56602629, 546147347, 255724802, 873696194, 831784350, 110556728, 279941051, 667003092, 302778600, 803516696, 772054724, 165410893, 531446229, 958833885, 703493734, 68812272, 481542542, 722167619, 172528691, 173636402, 356397518, 390931659, 311533827, 53449710, 959934024, 259493848, 215350798, 907381983, 791418522, 896453666, 530274270, 443147787, 468552325, 410897594, 491169384, 314015783, 406644587, 772818684, 721371094, 596483817, 922913559, 78344520, 173781169, 485391881, 326797438, 209197264, 227032260, 183290649, 293208856, 909531571, 778733890, 346053132, 674154326, 75833611, 738595509, 449942130, 545136258, 334305223, 589959631, 51605154, 128106265, 85269691, 347284647, 656835568, 934798619, 602272125, 976691718, 647351010, 456965253, 143605060, 148066754, 588283108, 104912143, 240217288, 49898584, 251930392, 868617755, 690598708, 880742077, 200550782, 935358746, 104053488, 348096605, 394187502, 726999264, 278275958, 153885020, 653433530, 364854920, 922674021, 65882280, 762280792, 84294078, 29666249, 250921311, 659332228, 420236707, 614100318, 959310571, 676769211, 355052615, 567244231, 840761673, 557858783, 627343983, 461946676, 22779421, 756641425, 641419708, 61123214, 245460001, 196379281, 164796745, 620727570, 451931052, 94566179, 322707767, 612134628, 255969954, 785621688, 49142691, 781545640, 487273416, 582513782, 833998375, 176341439, 515583649, 379734656, 329346411, 262683279, 462309262, 942371722, 988636580, 352487409, 652079107, 685238206, 424870840, 192091301, 854038651, 513843021, 285993962, 431760681, 440541032, 959964935, 523665702, 41329173, 899681280, 768843382, 597111687, 593261820, 178812114, 501033600, 79074739, 633101681, 224353692, 898313886, 432945941, 160288931, 303376374, 848566848, 692317852, 10693053, 270477785, 354061180, 888603469, 253860160, 584047404, 506196510, 568296848, 962951514, 654500714, 734254117, 246375021, 389395531, 95633141, 40560733, 318862543, 864056087, 540006622, 347088116, 78457748, 185163016, 865077798, 958626347, 481942155, 51697302, 729691171, 336768000, 709437459, 901887817, 842611169, 547889643, 912368861, 920207262, 345079539, 101456268, 384418814, 632085520, 973211984, 774267117, 499685849, 156629135, 352272493, 738377140, 261339777, 689733367, 327231667, 627599520, 359467170, 773351405, 233242346, 266305839, 1644198, 816838783, 423687677, 22255156, 658712680, 512357010, 716277124, 783879199, 673663191, 787126340, 858736628, 491333521, 328205600, 605652638, 119644545, 882244924, 114307964, 139226748, 212410164, 536612506, 152452523, 509087178, 232158417, 642534132, 778495828, 921783666, 615535293, 170411511, 905829108, 304372182, 158051973, 388988102, 890480785, 476645461, 422530824, 262605169, 369890567, 45133993, 543019649, 671454467, 143904872, 771077292, 654570451, 792302047, 562743593, 592383835, 241405483, 857708994, 80754172, 109559665, 431852528, 789666354, 854298840, 423750964, 703612882, 487324533, 296454325, 183468917, 190880063, 993511722, 447636316, 496304493, 691034792, 437596622, 112850919, 922723394, 586363427, 631568215, 197942800, 186902776, 423857491, 32548439, 276963998, 986623371, 242322904, 698701821, 468143012, 876893308, 487882804, 165353093, 778060747, 1978741, 346786812, 635942967, 500239511, 784774421, 881554459, 931353326, 173156822, 576087204, 848116767, 499529474, 437246725, 384326164, 422741252, 866757606, 109119920, 53023003, 733649165, 579939321, 246937598, 559803511, 123029541, 496654951, 959176615, 644519422, 868495167, 747639880, 139528218, 247727251, 740880614, 169939710, 646685918, 16756697, 409656806, 371643021, 404482449, 873066778, 887595254, 528988047, 481364999, 672119652, 18687584, 929665414, 629120405, 188972334, 435969196, 678076524, 390271723, 205031092, 8365757, 331709825, 993340837, 762606773, 107178366, 793994550, 553235112, 564769190, 443329073, 58033882, 194148704, 715134793, 57945841, 258463223, 562100050, 62957536, 696919454, 846230857, 481025551, 725011189, 164024643, 850925530, 762458204, 409955722, 724294671, 886984412, 600351301, 42985262, 247400266, 466533774, 698686213, 838053264, 975424804, 863218023, 560445506, 205342137, 784512170, 114961091, 230506730, 435065239, 273110608, 216022764, 645044939, 722381342, 203348615, 82876765, 82258458, 373083963, 293637220, 736550628, 730999737, 334655472, 366933982, 244031530, 312608442, 952278924, 439803364, 786138955, 691522755, 138915957, 757247105, 634994115, 952367286, 220361297, 28961504, 620993437, 291462451, 192646098, 825217846, 258845813, 534937793, 93814979, 522361720, 726763266, 606345278, 705963351, 811983342, 510153914, 321930485, 694723851, 867133830, 280978470, 767663937, 13397952, 658500617, 562307747, 246220846, 257735291, 726052322, 567215286, 993033414, 769264345, 44514330, 70515497, 644579365, 645970093, 140217677, 629726785, 796071754, 163640655, 296632244, 4042968, 401405213, 678766029, 188940446, 991255430, 282266904, 519915618, 726754477, 31255779, 7766682, 446187220, 567993920, 87804885, 360984154, 967620344, 287455258, 352050842, 972735059, 110525615, 651681667, 28652604, 852930758, 427030507, 907424453, 189822996, 159272754, 770216682, 35113541, 859756054, 707249452, 395495225, 246473570, 929367838, 375193487, 639880112, 635747308, 609553171, 306944760, 435152533, 899576163, 917215473, 88482014, 839732431, 151281819, 617626945, 325178136, 71002673, 125693400, 833970989, 215840698, 939364644, 959387477, 670421289, 544742622, 647496666, 20359440, 319980844, 413331733, 771100044, 913453818, 268067192, 221797414, 850985195, 677294287, 534700884, 581232364, 306536266, 763841929, 670218890, 987314980, 177537191, 617288803, 525339745, 678355787, 803297198, 649041256, 797205811, 654597257, 945917673, 527580263, 526066923, 910757760, 543736890, 18904623, 825659855, 436985896, 956953876, 788402152, 896254449, 266326444, 515180047, 646741884, 900662014, 145346990, 700847261, 211576216, 765562982, 286182552, 99594146, 818004370, 836262739, 873284804, 910254570, 946062504, 383933729, 864565896, 839447421, 483172612, 218074237, 899196030, 338254257, 115652199, 348730784, 962171704, 186789338, 844538210, 424934135, 4359701, 334645511, 574569592, 998750515, 180739662, 337685693, 345736950, 430206522, 101517724, 317393728, 29627088, 344429443, 244701024, 486997654, 938555773, 861309359, 402130164, 729206786, 933967923, 866805122, 937130659, 393451047, 946839225, 587847103, 662317959, 243618597, 68283846, 991807534, 875140051, 82406459, 126371384, 408761163, 601561650, 319043999, 99379196, 776863423, 972765339, 447579635, 893651488, 434359284, 64047192, 622456991, 950738051, 353376298, 650938112, 454346846, 611570548, 744245040, 367552188, 695830331, 137149847, 136218599, 872771468, 521050149, 701518906, 188983943, 987784056, 566130074, 856405762, 29097324, 995153587, 667366596, 393019274, 424195945, 81048119, 949995669, 93415448, 898064525, 58068445, 322104229, 242633108, 530220901, 56647468, 387388098, 154233411, 514416952, 29097154, 489548158, 8676497, 283716816, 654159074, 825853428, 859149690, 794764924, 758914724, 451922626, 56993923, 713646888, 16199827, 963933239, 385044136, 123097690, 62832030, 75485671, 700846554, 209611450, 478522332, 231087081, 184973044, 893189242, 229693882, 714596254, 482570946, 397815780, 1349347, 100933265, 254025771, 26174217, 831778240, 405823554, 896386917, 52741464, 487649122, 170870589, 583340505, 94564937, 277820180, 899859375, 779208866, 137119918, 552509591, 97580560, 591800369, 85574651, 865649038, 128523371, 809878024, 797390950, 877692187, 631337938, 776610930, 375093587, 148237650, 956673612, 284338013, 244423474, 144473996, 569178041, 993078862, 988458389, 625744277, 810626289, 138295622, 581515550, 98811304, 801651389, 38910655, 218136911, 19055157, 507306147, 704441810, 220213527, 222494837, 104210886, 362681747, 829563355, 937865509, 25593418, 205402693, 903736113, 822603964, 860184650, 338015384, 894841345, 63603398, 846693852, 950642953, 90930134, 306816051, 348815192, 778237469, 79403346, 951033008, 428627185, 947797938, 67234332, 457491733, 254027842, 65379562, 634064880, 793876922, 401004554, 241436651, 748921627, 235773197, 960720794, 660649561, 804622905, 581554967, 331694169, 641821690, 513029292, 420150147, 146986978, 940564101, 109063504, 736653339, 741347513, 223387889, 813402163, 740363875, 821476814, 722640850, 970598385, 310914311, 185009722, 746116934, 807984847, 254836633, 283644452, 417075927, 597261750, 843545049, 502496757, 159591303, 38700239, 551998204, 284996029, 943365105, 363079423, 68791007, 87353906, 230437622, 983014155, 531712251, 681438690, 454113819, 457096767, 922563191, 828713221, 895627971, 341864644, 700056471, 595145382, 415107031, 285556397, 19194762, 419952794, 720216897, 886764308, 405198636, 1285946, 178392510, 375302336, 512757404, 149308498, 525827833, 381482016, 519422664, 537945283, 582865261, 619532539, 683439071, 263607900, 715074257, 631748159, 25848019, 174264163, 991716651, 827177989, 128707256, 475527988, 54965727, 266221147, 835485060, 527837982, 825646734, 286725813, 168394909, 807636366, 749812522, 926966369, 90008970, 265472165, 204953584, 954837097, 958492073, 232782618, 713926326, 806461661, 791587080, 820400043, 573664608, 308087915, 840616702, 151201154, 787603818, 643029919, 872051234, 241187768, 149088916, 861978775, 290973079, 748019306, 41699134, 848386594, 979755938, 593123571, 966241991, 889714404, 779624902, 682443644, 6143197, 781310665, 981518143, 527365183, 107985225, 946009452, 976623872, 834626559, 611986668, 932488138, 909063924, 497814632, 140633959, 500203817, 360342268, 445467633, 477704894, 15361352, 220315555, 619476285, 950921904, 886367791, 189185798, 183160694, 659711657, 627029592, 112665948, 658051988, 648634412, 515148504, 24924703, 490594547, 201854810, 714542950, 602785661, 383539983, 536564768, 987492768, 587027873, 540968925, 498244660, 349158442, 88557443, 137723958, 627674755, 186876342, 377413248, 721254895, 701311697, 464980843, 825434906, 909994907, 450790541, 578501889, 931407997, 917054785, 869149237, 29257189, 14026097, 429313686, 775020958, 663028928, 60524820, 973597177, 999655403, 373165331, 160897667, 994649563, 251491102, 468275740, 134943782, 272400428, 403178049, 606290371, 298790432, 487696306, 484233736, 631964414, 758798349, 877363987, 85540895, 967541233, 405691356, 255015757, 718958090, 163918256, 609588933, 253217799, 427182496, 297334619, 285033600, 886988325, 380436491, 666193963, 126435007, 778326312, 903667127, 687840373, 880361885, 310561488, 780994727, 745208449, 106871663, 460676805, 937497705, 808221401, 291795339, 31122078, 949308837, 562350955, 222172784, 352239262, 278458293, 881629398, 883703942, 642656041, 766788263, 660830035, 73816861, 258979687, 327930043, 868826327, 918178049, 420185912, 109137213, 68821792, 384968057, 124910149, 80898773, 332388495, 219920198, 549570332, 489638900, 948597839, 952707502, 664458685, 826905865, 678979774, 629723420, 66425716, 810305229, 528398210, 842999153, 169382048, 487124857, 50096968, 184238535, 237452585, 634813513, 50106783, 403314167, 313482759, 498134475, 942437182, 170130670, 779446762, 743305004, 455852704, 590363951, 366230360, 964904140, 791415171, 351457024, 743110297, 285539671, 950624820, 199641625, 511558944, 216283487, 913142596, 886342412, 209131158, 786607494, 792630333, 191271328, 962389136, 411019481, 678612260, 78877143, 469516355, 44624214, 347853488, 444348057, 702180389, 825584362, 808066718, 649421951, 527998071, 372246707, 275346640, 273864415, 666283451, 587586574, 31051570, 488457940, 4518396, 810872144, 11541870, 529730086, 562850720, 810299187, 134899497, 863414291, 701755664, 37580494, 620187235, 566972095, 832270518, 914744892, 644210431, 229277629, 530537835, 37376309, 519199292, 784199509, 88822413, 980152392, 880351115, 52386628, 358816323, 303416646, 247871657, 794390809, 510618403, 3194064, 321052614, 684171275, 343286290, 393422020, 155860200, 226634637, 869751302, 326073683, 908403592, 906328261, 686898515, 928035288, 718245479, 744984158, 753416506, 312502450, 442383389, 997238270, 484811253, 652876718, 100550147, 100292593, 685477193, 325330782, 637551789, 653776217, 821305915, 539653961, 85492146, 668227971, 469984345, 668526842, 407469854, 829340515, 462445012, 364247651, 959011634, 367440613, 127711234, 721268413, 240915655, 649619698, 881400474, 191745954, 902062233, 773946817, 242293456, 886538426, 13376923, 128399655, 522898175, 483287823, 557561646, 965256748, 366954950, 386363078, 248858228, 675348666, 685223017, 484498874, 893197177, 122228326, 468011623, 679727481, 683233967, 530218776, 297389332, 458569016, 690769186, 695283030, 634918502, 582919993, 568897278, 377206287, 404501793, 846677012, 921247487, 84820014, 474767580, 71672801, 574296230, 50225519, 514793938, 505092729, 6292633, 987994428, 208479540, 718726630, 607933815, 207120621, 532561853, 403027996, 670973878, 257865486, 555148740, 378478703, 343303230, 697500496, 708520056, 304666064, 400742625, 544654169, 425317758, 511565961, 591889308, 497309241, 889760233, 39833046, 131566421, 710685130, 621226182, 362711294, 429310448, 117450930, 824794775, 120246761, 916962538, 953466201, 418609504, 242733246, 497079791, 867553799, 730518945, 550811645, 356881329, 878310966, 844570494, 665447918, 98753412, 172191040, 150900819, 400725864, 932292989, 2778985, 871995270, 397987879, 744358198, 61935943, 118390414, 750895102, 146710001, 25199943, 449078732, 945062640, 367970678, 569714605, 643527155, 138721954, 61594093, 72228987, 775512252, 841085203, 352555049, 647359211, 817187403, 877905801, 328872017, 470623398, 722194491, 51810950, 823621280, 549526866, 537011874, 279426058, 810038108, 721691400, 28042164, 178483524, 204123347, 456946290, 977570343, 776222743, 655108510, 793503657, 413361565, 380804780, 634295160, 540355391, 546570232, 498552403, 374630545, 201971537, 460488405, 575924645, 724998420, 896569904, 73828573, 912688005, 794892996, 328003267, 439081146, 806080156, 6426, 13957272, 329151846, 576108199, 35324054, 865140972, 411882863, 80869335, 214279733, 129814671, 125795470, 485713622, 312829406, 219417923, 428158402, 954260227, 967101847, 18826424, 211041849, 181646076, 986549737, 517008370, 799347479, 768356655, 542845923, 89638564, 935923736, 160357329, 625764007, 680805768, 453484882, 573703178, 868092293, 275400381, 257835856, 785894360, 468840382, 199556211, 819667019, 464099313, 123573861, 345378621, 322882925, 862790952, 81945303, 590790181, 781822114, 81436714, 708067106, 908964323, 809747257, 258392461, 406436785, 915403519, 772815523, 287342158, 910981393, 666529401, 694024434, 674476991, 758156393, 205057332, 893019157, 4782773, 689497585, 716589273, 10192480, 810770086, 314209849, 830056839, 157363179, 808244854, 893194838, 329202444, 59481607, 595688391, 511805211, 538106278, 201010752, 274188836, 199065517, 295541148, 854201789, 370818931, 196683553, 718092467, 734686679, 922509576, 949117603, 5767765, 40916574, 553289744, 94681908, 359838214, 33549005, 22044798, 975556723, 562632280, 612634388, 680051030, 395878322, 435541291, 985347520, 680244800, 556909171, 525264327, 26864207, 196663119, 195245065, 158745085, 97536351, 577951428, 463100891, 722427645, 747157275, 1518694, 473253157, 803215642, 560591672, 754919899, 521476506, 224143387, 960782800, 35727772, 995236173, 62237213, 958877267, 499944145, 371581312, 637011622, 763731967, 110975728, 577099799, 637927593, 423091575, 649165125, 623932896, 37113888, 695966797, 683289821, 82765278, 353321399, 232390168, 750844993, 206146629, 435589425, 260690662, 280950288, 523713315, 14882295, 541806457, 74584348, 259439193, 936680318, 781724111, 290269460, 457028695, 962794519, 348419057, 816397133, 21703702, 613032714, 205311752, 197625815, 456274798, 857920673, 960598773, 879915559, 122478095, 598740298, 651027811, 707122694, 788460450, 151281864, 755968602, 502327881, 963528461, 364810594, 940079314, 186372437, 161596321, 74544332, 402811971, 219373098, 623642178, 300961085, 365272382, 312270729, 646644559, 81148558, 591744101, 699556783, 52666658, 503978644, 909484723, 840839561, 267226957, 793429752, 635069335, 114313415, 37105068, 13220680, 372673423, 726700014, 912521175, 150296624, 255072749, 562992880, 360052147, 924103868, 291294308, 863036805, 616691923, 193534142, 578925443, 316097331, 524323819, 85271008, 712436691, 723679576, 317854106, 307016232, 689838038, 472251415, 42131008, 945894468, 309023927, 39371759, 452849183, 838031598, 113852714, 474217117, 543724178, 112914763, 560003118, 367492479, 554390765, 972952782, 843235437, 197388946, 904745481, 246084898, 802854723, 91287756, 459929200, 188939423, 666582199, 795745905, 909330727, 580343940, 12668905, 684087700, 544485501, 832845191, 649574042, 866614867, 274267488, 921456209, 217115995, 591864161, 821765325, 533256414, 412846183, 867602394, 611814606, 380369786, 961162000, 312939599, 259676620, 610948369, 324958292, 548143513, 114592886, 65011424, 952930574, 868167694, 406332350, 701585842, 183715032, 101825250, 573686007, 678079322, 328565225, 299056508, 183722002, 221233755, 571332234, 334621344, 833879142, 342674963, 323078042, 418133839, 863638254, 4642960, 444896323, 114324839, 39375839, 179569973, 358260236, 902776732, 761289162, 906795297, 504753787, 760860302, 129234269, 984047811, 486410788, 325924229, 966158042, 71927388, 451848382, 487676277, 900187321, 65289712, 244933186, 903896140, 989684451, 334896854, 558263775, 76790020, 283938483, 574694687, 713844667, 328587038, 824654077, 336561786, 394773762, 144850574, 981581899, 954730329, 780536120, 901358576, 100499936, 651837987, 854146011, 489888586, 150676506, 896674409, 756076438, 751846101, 885546402, 492546256, 768732669, 593916342, 699589679, 167620044, 899647801, 313147063, 817446181, 964361707, 155846330, 44441509, 125926423, 838289433, 680803513, 709661805, 315368684, 252027573, 377727658, 650968055, 600135676, 543520999, 738680835, 817222793, 659765758, 165950577, 16610902, 158468982, 352742484, 965903095, 359747217, 477419216, 77057790, 35016388, 116706837, 135604923, 385736466, 856508494, 240135925, 346604466, 187986578, 741743703, 671660508, 420925427, 464458460, 155815451, 420105421, 629659400, 298393323, 886901539, 354825482, 62878521, 157648196, 209971716, 577447774, 730977717, 419786407, 11485630, 506583267, 918987083, 715773859, 970352468, 716882692, 256036293, 293449862, 926839227, 464671263, 922507635, 147174012, 708948307, 795567564, 155435870, 490849403, 354848476, 283304041, 624244902, 921550176, 971838800, 90635588, 746171282, 329778131, 784909574, 270511137, 705884471, 770189428, 411741095, 291616232, 618965437, 691159507, 14705621, 249319955, 730518374, 539314215, 374206032, 806706542, 277233738, 748349912, 696556839, 316780232, 796399738, 399701365, 19958072, 150441772, 254789257, 273902393, 528655076, 490324211, 668775417, 522804866, 748739337, 445788543, 857551570, 357752367, 742204442, 286646614, 734003100, 226130204, 270171954, 282062096, 823307293, 121472721, 716199439, 753109692, 690914847, 560609105, 765590441, 861978791, 900034747, 191680708, 37065578, 890190819, 884127341, 748545911, 155374831, 966425125, 160862851, 803963622, 895656160, 593151236, 850764403, 376416568, 256731350, 108266783, 340040073, 806387501, 765187669, 103622302, 428076791, 256179303, 436941213, 700559659, 889799210, 535279647, 984969633, 944053577, 846818670, 465377084, 626051425, 931241635, 415148048, 860428452, 64807651, 230849912, 292660369, 866481601, 704748050, 610516648, 963571906, 409118107, 436519088, 307666738, 162185541, 143803458, 968478577, 364961045, 285360010, 762341508, 173959161, 776180660, 925960791, 760471144, 188305319, 106220518, 158073490, 8052568, 709723181, 123405759, 948735458, 636983222, 854687367, 510562111, 538814269, 414958915, 48898306, 269916806, 394871926, 918296206, 746108446, 207766067, 46037629, 808011351, 326768575, 523137773, 795905989, 884745015, 967443926, 545128546, 659377661, 847847715, 145768658, 636515646, 595576288, 754220877, 497654570, 108693758, 299182236, 869951867, 228676565, 58341517, 272340297, 761345906, 997000639, 802727319, 656474788, 458532615, 545225862, 283173850, 329995875, 858695304, 825116496, 644299709, 669789716, 233178129, 840781503, 945209586, 545504991, 502199791, 45016008, 749005131, 764095837, 27632873, 45665964, 718398017, 468124972, 684288837, 900021577, 359470422, 419416939, 171326602, 861418216, 375677730, 621883001, 262719737, 157347986, 67178245, 815024375, 172429840, 285793781, 362974052, 438117005, 22212357, 572653177, 967248712, 147908307, 445549055, 844168028, 254597348, 271427795, 297837027, 986929271, 650283443, 88525763, 367196707, 275625134, 615992821, 155987294, 736585340, 599913549, 158876450, 265292399, 431080429, 576549347, 302314901, 667827486, 577810308, 557609863, 634775898, 102950172, 157529412, 82350513, 663785303, 926405993, 715980207, 608486379, 804281153, 812899526, 808953515, 541454223, 944901767, 173946685, 964128119, 128251651, 771891743, 103349598, 929116340, 391595128, 123467855, 932412961, 472118663, 374620343, 803980211, 832139566, 129978375, 58928431, 472816413, 179173786, 524289480, 690639066, 817904043, 668425492, 312554608, 154643661, 105488547, 954540112, 121198578, 719164807, 270543179, 801536633, 562485162, 457848901, 748718641, 858362833, 325517139, 770736841, 746297301, 962103785, 109456722, 732742079, 582168462, 180105087, 479599446, 817610423, 642520495, 753479899, 185096588, 635851632, 628099912, 109535931, 163224538, 822175418, 243854434, 911385229, 295892364, 435724567, 350875719, 609803619, 306963437, 371131156, 775279116, 51047345, 556926473, 492819263, 869732694, 611745063, 767043819, 18008002, 809021397, 363564270, 701526008, 394888900, 674912941, 99082347, 654404406, 302293695, 117303971, 539257940, 837661888, 167515611, 952596798, 4726949, 665609468, 942567988, 849170202, 498547389, 294681054, 396326413, 157610425, 755008458, 769504426, 562819783, 740179059, 999614189, 879970360, 433907555, 501438455, 180140031, 667066456, 829240475, 260524891, 127427504, 941461554, 536026061, 443904766, 538479073, 666486812, 475530191, 121557438, 704601606, 732073522, 654669281, 288956417, 330644566, 474059656, 150424442, 991489777, 99067195, 969677742, 216408703, 861086656, 983884426, 765232425, 661454399, 45738687, 197306720, 95219147, 563413639, 745846165, 296017433, 995229504, 974721285, 655279123, 831166377, 122630389, 23862689, 275618615, 972434113, 763310956, 240682538, 772799599, 758801097, 222021574, 407681863, 884533018, 910516888, 577385210, 750668818, 727679293, 475333630, 512201328, 115920268, 239911147, 616812444, 615258783, 627020051, 114438202, 423704759, 132011154, 809102335, 224815801, 702924301, 388083655, 384614589, 459165096, 556985949, 33186676, 763547090, 79671019, 260292923, 412612192, 584323557, 868511230, 900469737, 101206669, 698182, 84073256, 42740659, 666347544, 46447535, 831681149, 726618108, 314745817, 719477877, 397270790, 428736937, 67117327, 83510285, 280322395, 406534330, 196447137, 341406877, 562030709, 216176609, 178352284, 770257391, 623443757, 71920424, 264713456, 258070076, 532853252, 888277299, 602928571, 20843140, 800380386, 346466520, 596550492, 196271279, 150444599, 41796604, 183946594, 518709995, 22883926, 155223889, 241813164, 243002819, 83522330, 738568816, 647790387, 509278109, 603381367, 245529214, 199042426, 496631411, 283059021, 801063708, 228336763, 230407617, 747927936, 205053664, 158080535, 564823040, 626852621, 885659740, 62569955, 462941690, 657436187, 550611588, 713496897, 738526838, 768313305, 355563849, 825295711, 802492346, 9115188, 837783963, 429989052, 46533714, 253562704, 394743407, 520073564, 425094703, 214876776, 952683513, 69579893, 192790661, 903371835, 738026727, 527955868, 768591691, 807883173, 201323750, 265231924, 792464830, 244405545, 302640073, 618217965, 638447033, 501506793, 637898053, 88091439, 321630223, 942710133, 432609571, 735298062, 659207339, 654626584, 177624084, 325543472, 278234501, 466367576, 75799753, 297034885, 431857994, 736766097, 554288165, 521858670, 674431015, 712838839, 374707766, 219358707, 11986940, 171500681, 995108745, 822414126, 773429240, 497773393, 84147836, 447324625, 284924770, 831103735, 732597762, 111621629, 366507019, 936342167, 769487633, 953960023, 539410864, 343651321, 504811381, 506686321, 861310460, 149926844, 71603692, 618328555, 658392303, 475932476, 764909567, 872199272, 239303720, 781334644, 577418605, 897639606, 407226315, 840035970, 672711556, 950713304, 436900477, 556786759, 196837513, 872948988, 59803133, 841639444, 431114540, 992989742, 959727001, 341397019, 35014256, 189862862, 688285397, 410699984, 704940549, 267654352, 646511603, 451069993, 674747968, 829824144, 924980138, 162275226, 465160124, 440821433, 995718536, 466270267, 346573936, 213351896, 45394219, 672702134, 774941341, 239209769, 816542893, 624409808, 379077507, 54766283, 718648465, 271563485, 942495363, 422756581, 674891862, 131430566, 686335829, 861585124, 840675147, 187623889, 19210619, 147399850, 321119117, 764380491, 316227281, 816337498, 483925410, 238121689, 608182597, 710653447, 405786948, 677715899, 624566258, 489180345, 420371679, 928248362, 538240900, 832627053, 406550952, 369588245, 421552209, 231715977, 417985114, 642280997, 152861969, 228331153, 486333700, 644832380, 911925317, 192172391, 257715573, 40130253, 978632246, 302648868, 318752677, 427354734, 227524387, 400996629, 209136343, 628156092, 918914263, 660648922, 932109625, 53519583, 654173554, 18043981, 245970262, 237970440, 644515824, 430612770, 740462903, 916548648, 118306884, 722767066, 874209210, 815192967, 594808673, 585278365, 301889328, 423305202, 355455280, 741464976, 312365309, 625420614, 115298834, 375311380, 11353707, 888193791, 629800548, 481567219, 56585226, 71738890, 438346429, 817616413, 159022094, 934956539, 88382740, 39347644, 273318544, 291765747, 739860057, 163349093, 171435821, 737951652, 150078562, 306658624, 160376218, 269852974, 419218806, 264704829, 114194426, 758353687, 849953864, 598885119, 947636117, 403533674, 783374118, 683714946, 585007186, 408563833, 906490526, 8376026, 506869195, 65293920, 555819622, 979084732, 230576283, 365389481, 131384076, 384991092, 390665995, 463112533, 492673027, 357612604, 691134538, 670555840, 493144843, 884825675, 924707067, 458006803, 338452922, 909993547, 618658246, 665488722, 105699532, 548349881, 941393657, 71589208, 960276828, 476555255, 350993514, 841503748, 743401356, 375477892, 84681157, 887395809, 379273654, 809248820, 706063598, 837192550, 153631633, 517912889, 542430989, 583025804, 143810531, 457633291, 3581787, 923768846, 150235648, 434939988, 220029873, 359561578, 778292666, 606022945, 692530373, 973838531, 672993728, 126042063, 980487480, 808647755, 500778296, 101831810, 525570260, 32507394, 769739568, 318316064, 722174817, 563445207, 541430241, 332724893, 293833531, 223822548, 700820742, 253572953, 990824318, 197212244, 238710718, 829296155, 435061298, 241012344, 283494858, 393200783, 727424758, 784293541, 932040533, 180452645, 764504111, 614331934, 298603090, 591009348, 883507512, 70817116, 936947718, 198526116, 224162926, 998195810, 905422583, 422886544, 356508717, 355963742, 869367023, 68618222, 204061624, 748592410, 733882522, 660084619, 366673520, 656550586, 706470965, 643025550, 142650333, 12576481, 684576220, 136250632, 707143038, 164883272, 273354336, 131381561, 697304278, 531832881, 295448499, 411235062, 844141255, 300953157, 46445567, 240045663, 75613778, 767367403, 722825918, 559189043, 953001367, 593642807, 696528916, 646231494, 526768055, 966431342, 262303835, 816805593, 475108509, 346197914, 689253420, 314440147, 643055796, 466085886, 810234264, 672803296, 369682546, 641441365, 143866550, 606129599, 236769208, 828685380, 705575005, 650125214, 830219673, 464996130, 656683754, 335414200, 824839929, 274175823, 713176165, 465518910, 247114819, 310545498, 139778618, 816892879, 646627080, 216783310, 902414271, 231627423, 577858603, 345742194, 193529718, 645171014, 711008781, 957338718, 477263674, 855036816, 427362654, 102135141, 591855671, 596174330, 147864665, 351060641, 776173194, 992444768, 798431337, 758288670, 261666483, 244356137, 404501728, 834491516, 23506291, 684360658, 837630562, 441443690, 341143075, 836749623, 888667663, 452113252, 258332446, 771903125, 310468677, 983331778, 894554119, 310191120, 946618993, 753643463, 215667460, 895097596, 680783357, 976249362, 15246951, 288093374, 174428455, 976302872, 107422351, 870803524, 812312671, 906641270, 57705315, 141717031, 576473152, 538383620, 572958511, 365484014, 117912138, 753689351, 449603495, 557859899, 203951575, 481877963, 319150131, 812702618, 462384889, 207643231, 488881548, 374155372, 26900221, 715677483, 616077486, 440967988, 971178841, 405390564, 407118661, 907507302, 685739049, 973086988, 997043602, 560934022, 218951837, 556834710, 853851371, 364575359, 138460401, 734434914, 430707546, 273994626, 940969257, 972115720, 233856139, 552294681, 332335765, 130278679, 968192507, 178798291, 376332030, 602365125, 396178784, 830852142, 186787727, 656789390, 229475722, 786186005, 677414215, 562345892, 826669736, 117569830, 548591874, 535649643, 984015017, 45481029, 94386222, 486879078, 210779996, 852240475, 793993520, 762853049, 385365869, 141508567, 468597789, 299888379, 801059049, 786080134, 22539507, 623815979, 13557238, 521354466, 448975218, 780244409, 835453480, 429797889, 395623396, 309864734, 174928347, 467976300, 98952647, 141047598, 360873278, 895932233, 188558410, 490362391, 362420920, 903198286, 901013727, 946353339, 979289894, 464303838, 493805103, 192163457, 172767270, 480469456, 611907307, 925826300, 529614434, 319250068, 854237287, 942347209, 873400683, 849844242, 637380621, 856167559, 189536568, 174688525, 673701983, 780055459, 240630908, 843249962, 564841076, 289521881, 648245646, 593959022, 507480664, 617394127, 671088836, 39191134, 185433158, 936925678, 40187333, 920205108, 184928862, 846550949, 366127134, 872122780, 38405883, 682195498, 827204357, 196634053, 747947915, 278339454, 712284377, 851967253, 568648204, 722689076, 924352658, 114120129, 310227680, 20796396, 906844875, 890615455, 527618896, 391813599, 686880729, 549046925, 315543751, 943489336, 283966931, 34993256, 75316064, 732108379, 980865138, 908975350, 485659090, 940552397, 65063266, 586994756, 96749937, 975516375, 145071190, 556334766, 861246458, 358218093, 93264470, 746924856, 695751441, 278030651, 596727224, 359441731, 745560826, 409381298, 341928687, 323345408, 204474735, 489393204, 903337323, 604686591, 84131998, 362938452, 242878507, 464563065, 166823975, 80935363, 975228836, 470523799, 55948931, 843196465, 140505744, 730743423, 750646179, 141489033, 792396505, 244237477, 655608480, 29401397, 961576526, 564156934, 893896635, 462596010, 231185088, 927855569, 199848020, 35693066, 564046200, 431618335, 893721639, 963308916, 582524621, 409050337, 667242993, 811159579, 135931905, 74478773, 358948713, 83946566, 784902732, 332461689, 417167919, 619159066, 463300017, 572351331, 15152340, 563684828, 799133024, 761823752, 173517550, 435079814, 328333350, 638387061, 567591431, 359528510, 355675005, 291534398, 504778475, 395375645, 77155803, 102791818, 263731169, 728145665, 546224640, 888610304, 65837270, 87272581, 621266785, 856761351, 995611837, 513645429, 279508672, 673090698, 821006770, 806440361, 828616851, 85188487, 649462828, 227530305, 879122638, 654954169, 867291523, 821727311, 911940791, 928698795, 51830219, 555414922, 135900956, 26105309, 573646098, 661296984, 379988066, 974891369, 89349025, 828661166, 996507881, 789287440, 663652058, 923021953, 561089600, 846300332, 785635181, 771679977, 667092362, 947126646, 504216495, 493152151, 19247797, 45389104, 297037580, 851683371, 693420420, 304157142, 797131515, 896867312, 889496361, 754637209, 639922946, 906792492, 252200395, 126897045, 223943979, 2610040, 944252337, 545631121, 945818699, 406674045, 54796773, 49687532, 607620789, 288535380, 628073133, 611278141, 82482275, 164770570, 753114137, 155325598, 965082601, 440922988, 971340286, 319248503, 83260930, 806098744, 358167911, 141257437, 298494797, 130548893, 524452262, 274410693, 639410984, 419928437, 685329929, 981579021, 263414257, 774154060, 299877702, 430000722, 922763804, 26801544, 78737503, 903171927, 405550771, 964906659, 890611152, 743522349, 48068300, 207158605, 389258084, 589903320, 667186002, 336391703, 799181095, 39824017, 720704549, 640244215, 623141026, 193766589, 714094660, 975841587, 603548938, 923726915, 975682216, 914467286, 988372054, 988194259, 288144066, 981959813, 112288934, 119616205, 632407339, 843236146, 69751298, 565283052, 298226409, 416685230, 572051541, 276118156, 442910400, 706891960, 982137338, 567806087, 630050807, 267571273, 852244690, 84065578, 183227287, 303823300, 87921919, 455872111, 77732024, 921695414, 768698628, 155929593, 125408444, 218336621, 949489185, 856263120, 851197086, 924597569, 478079237, 855565890, 551474719, 714661486, 326390702, 514026590, 872006010, 159493246, 256560476, 434256512, 548489092, 431758328, 629117267, 510552118, 364288553, 375406317, 343564970, 805367881, 263542924, 405969462, 836096661, 351564766, 946391188, 370951626, 839879981, 568182204, 92410490, 450454629, 88498082, 239950234, 444114416, 478443556, 110710340, 88026208, 823257098, 456200510, 342397834, 74650012, 419645270, 500578565, 283003665, 15457936, 27930901, 299127279, 552743783, 890671352, 933158471, 775410047, 971304383, 508807878, 843951284, 515207415, 190934297, 908876538, 151065287, 369597621, 345764154, 263332712, 850863067, 672037044, 298897849, 727758688, 746453775, 675012241, 798578017, 153283310, 841303064, 497049878, 276201347, 900346646, 778239443, 58243146, 691233171, 416768159, 737261214, 36872389, 825851976, 368397385, 695171571, 258691045, 142498153, 140132035, 846551674, 894603954, 469751477, 778131589, 301281546, 17204757, 715798982, 616913077, 184638437, 999827530, 310436961, 437398352, 593395757, 176407139, 981365343, 405440533, 383882771, 450487096};
LL Invers[800005] ={0};
inline LL fast(LL a,LL b,LL p)
{
    LL s=1;
    while(b)
    {
        if(b&1)
        {
            s=(s*a);
            if (s > p)
            {
                s = s % p;
            }
            else if (s == p)
            {
                s = 0;
            }
        }
        b=b>>1;
        a=(a*a);
        if (a > p)
        {
            a = a % p;
        }
        else if (a == p)
        {
            a = 0;
        }
    }

    return s;
}

inline LL inv(LL a)
{
    Invers[a]=fast(a,Mod-2,Mod);
    return Invers[a];
}
inline LL fun(LL a,LL b,LL c,LL d)
{
    LL ans=1,a1,b1,c1,d1;
    if(Invers[a])
    a1=a;
    else
    a1=inv(a);
    if(Invers[b])
    b1=b;
    else
    b1=inv(b);
    if(Invers[c])
    c1=c;
    else
    c1=inv(c);
    if(Invers[d])
    d1=d;
    else
    d1=inv(d);
    ans=(((a1*b1)%Mod)*((c1*d1)%Mod))%Mod;
    return ans;
}
inline LL foo(LL a,LL b,LL c,LL d)
{
    LL ans=(Table[a+b]*Table[c+d])%Mod;
    ans = (ans*fun(a,b,c,d))%Mod;
    return ans;
}
int main()
{
    for (long index = 4005; index <= 800000; ++index)
    {
        Table[index] = Table[index-1]*index;
        Table[index] %= Mod;
    }
    int R;
    scanf("%d", &R);
    long long n, m, a, b;
    long long ans;
    while (R--)
    {
        scanf("%lld %lld %lld %lld", &n, &m, &a, &b);
        long long a2 = n - a;
        long long b2 = m - b;
        long long ans=0,comval;
        comval=foo(a2,b,a,b2);
        if(a2<b2)
        for(;a2!=0;a2--,b++,a++,b2--)
        {ans+=fun(a2,b,a,b2);ans%=Mod;}
        else
        for(;b2!=0;a2--,b++,a++,b2--)
        {ans+=fun(a2,b,a,b2);ans%=Mod;}
        ans=(1+(comval*ans))%Mod;
        printf("%lld\n", ans);
    }

    return 0;
}