#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll invs[] = {1, 1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306, 272248460, 582309206, 460728163, 926941185, 865145106, 935854081, 939524097, 720954255, 105078353, 149736653, 617960790, 136124230, 217009642, 291154603, 319438193, 729486258, 480636170, 962592769, 481911067, 432572553, 128805723, 967049217, 756245722, 968884225, 370776474, 859599304, 242816194, 551661353, 486324172, 573990503, 97389693, 308980395, 510729669, 68062115, 288381702, 108504821, 191153174, 644699478, 692659347, 658841273, 313174699, 364743129, 828731161, 240318085, 54449692, 980418561, 700522353, 740077710, 727534020, 715408453, 654586461, 563525038, 205986930, 982646785, 890741115, 378122861, 432075914, 983564289, 405084665, 185388237, 702988981, 429799652, 382888245, 121408097, 771975633, 774952853, 894530654, 243162086, 404352143, 786117428, 825708292, 547817023, 60135202, 653612374, 387553690, 754487011, 493385140, 533153234, 392568004, 144190851, 65818309, 553374587, 42935241, 95576587, 819611153, 322349739, 699800165, 845451850, 584830025, 828542813, 889524671, 655709526, 38766771, 681493741, 123592158, 913487757, 802327237, 619281219, 622757945, 27224846, 413686849, 989331457, 150178354, 849383353, 243050799, 370038855, 494856175, 363767010, 989855745, 856826403, 24749860, 826415407, 32463231, 281762519, 862483121, 102993465, 322267862, 990445569, 170243223, 944492734, 922042494, 688183607, 728042874, 216037957, 96127234, 990904321, 276885295, 701664509, 854612072, 591816295, 729213960, 850616667, 404882325, 214899826, 296031084, 690566299, 230886449, 559826225, 442175351, 885109993, 323933598, 886598603, 437139684, 447265327, 824356627, 121581043, 953736643, 701298248, 608991838, 393058714, 601426722, 412854146, 202098550, 773030688, 350898015, 30067601, 436358310, 326806187, 572956818, 193776845, 233507451, 876365682, 957852963, 246692570, 473453036, 266576617, 242511340, 196284002, 117112466, 571217602, 193030676, 532031331, 218195487, 775809470, 447860980, 520589797, 720657688, 546910470, 68662310, 908927753, 789187944, 660297046, 920660595, 849022259, 296913705, 422725925, 719546691, 791537189, 837722648, 913393583, 809521540, 943884512, 924482455, 327854763, 818073421, 518505562, 800524457, 839869047, 644798984, 61796079, 738038479, 955866055, 567077778, 900285795, 501443675, 808762786, 446219826, 810501149, 127629415, 13612423, 379423193, 705965601, 528218985, 993787905, 257325211, 75089177, 386984595, 923813853, 357449943, 620647576, 963673120, 684141604, 844009174, 746550264, 437528376, 181883505, 800280283, 994050049, 54297810, 927535378, 981675982, 12374930, 607984215, 912329880, 338180740, 515353792, 392023086, 640003436, 352793185, 930363737, 616445716, 550618909, 836473529, 161133931, 461932681, 994344961, 42726412, 584243788, 319900700, 472246367, 497209831, 461021247, 918536629, 843213980, 764692844, 364021437, 463604119, 607141155, 924025442, 48063617, 7367117, 994574337, 354687554, 637564824, 210538809, 849954431, 918961408, 427306036, 14311747, 795030324, 497345941, 364606980, 567905798, 924430510, 938699953, 701563339, 726944494, 107449913, 701188940, 148015542, 898762957, 844405326, 705244304, 614565401, 145506804, 779035289, 860439577, 720209852, 323845158, 941677173, 785993062, 161966799, 962004459, 942421478, 729863904, 218569842, 877934773, 722754840, 12922257, 911300490, 38517467, 559912698, 38271349, 975990498, 41197386, 350649124, 135408540, 304495919, 43810097, 196529357, 600190530, 300713361, 417222872, 206427073, 178148223, 101049275, 873082217, 386515344, 740339277, 674571184, 907769034, 514155977, 470643734, 218179155, 485712924, 662525270, 805704641, 286478409, 382807569, 596010599, 556206531, 615875902, 811983016, 438182841, 81016933, 978048658, 451655226, 123346285, 497692027, 236726518, 497700176, 632410485, 548610211, 121255670, 739544408, 98142001, 329951915, 58556233, 136250622, 285608801, 268226322, 96515338, 340998071, 765137842, 76577649, 608219920, 97920427, 387904735, 10821077, 223930490, 260996502, 759417075, 562014247, 360328844, 952990609, 273455235, 497798245, 34331155, 371378506, 953586053, 772918856, 394593972, 573404067, 330148523, 578203872, 959452474, 56747741, 923633306, 338735873, 647579029, 952289370, 710485139, 307347498, 858895522, 879465911, 894890771, 829774903, 418861324, 242680958, 955818968, 463026059, 404760770, 240272214, 471942256, 364790529, 961363404, 385072146, 663049558, 763937610, 908158887, 425043216, 259252781, 674358776, 899384405, 211675911, 919056700, 950366926, 322399492, 362131603, 530020216, 884430270, 868141416, 243071320, 977055204, 77510738, 283538889, 521331360, 949265074, 134960775, 749844014, 653143637, 404381393, 680097192, 223109913, 98677028, 904372751, 221578266, 562936884, 877727381, 505928388, 742458385, 688833773, 306458763, 852104977, 477811342, 763231669, 812888019, 996016129, 371284648, 627784782, 371851555, 536666765, 107977866, 692614474, 412461403, 961029103, 930529747, 677847148, 145713228, 310323788, 207877349, 481836560, 263036309, 342070802, 607533660, 422004587, 720360486, 373275132, 489544139, 218764188, 650660332, 590063929, 772425863, 899262318, 962517713, 996147201, 535745397, 27148905, 423055540, 463767689, 632982386, 490837991, 200475574, 6187465, 139960033, 803114284, 717424073, 456164940, 400114301, 169090370, 18297758, 257676896, 204508478, 196011543, 116966005, 320001718, 813458678, 675518769, 178043582, 964304045, 145452770, 308222858, 63506599, 774431631, 776851546, 917358941, 190985606, 579689142, 992360791, 730088517, 339910993, 996294657, 77835817, 21363206, 606699966, 292121894, 834122941, 159950350, 319284321, 735245360, 821970878, 747727092, 166055944, 729632800, 823313914, 958390491, 770940136, 421606990, 139640987, 382346422, 413585231, 681132895, 84279542, 730924236, 360114318, 802692754, 704533724, 462012721, 698215438, 523153985, 31368122, 502805735, 729839794, 996409345, 124551589, 177343777, 133220910, 318782412, 72731829, 604391581, 760912211, 924099392, 200370928, 459480704, 482035111, 213653018, 987491272, 506278050, 730379142, 397515162, 572967347, 747795147, 491143314, 182303490, 429333412, 283952899, 688383672, 462215255, 335087296, 968472153, 111887283, 849903846, 263062648, 363472247, 447907901, 552847133, 557079171, 350594470, 306886865, 74007771, 864228760, 948503655, 438337143, 422202663, 98971235, 352622152, 392835512, 806404877, 164396778, 72753402, 239848897, 888639821, 383810645, 929341965, 197971149, 360104926, 944737118, 161922579, 773264407, 969960763, 568052527, 392996531, 602588631, 580105576, 4949972, 980124406, 572304835, 471210739, 640908936, 364931952, 859372389, 109284921, 607414590, 938089563, 605439258, 361377420, 734526639, 505583305, 866005198, 455650245, 932337721, 518380910, 626506488, 279956349, 771443236, 518257851, 880429230, 487995249, 484045354, 20598693, 414484977, 175324562, 578760944, 67704270, 264102443, 651370136, 437221624, 521027225, 189025926, 597386855, 808250888, 300095265, 636516617, 649478857, 832644127, 208611436, 354862753, 602335713, 156888943, 588196288, 148739942, 549646814, 582436598, 935663285, 583706240, 193257672, 375291256, 869291815, 645299081, 337285592, 945387239, 453884517, 791970633, 756200165, 544906316, 235321867, 454971939, 608211754, 176072995, 242856462, 331756320, 331262635, 930013684, 901974497, 418523188, 642361381, 7372558, 690525961, 955609469, 797127476, 128994865, 777225442, 29231167, 307937951, 55377059, 405991508, 119149981, 718213597, 140536578, 539630643, 37560569, 489024329, 653972491, 225827613, 370571285, 560795319, 534211110, 747968190, 614084509, 118363259, 207908239, 248850088, 380554035, 815327419, 145842792, 773427282, 127074953, 60627835, 249209098, 369772204, 599508212, 548193177, 135806034, 664098134, 80976465, 528400293, 18099270, 68125311, 951039474, 641926577, 861176127, 134113161, 659973445, 48257669, 458503958, 669621212, 768936503, 382568921, 202661405, 537411001, 323644202, 304109960, 153890330, 548082390, 445475031, 693074544, 674526035, 504532715, 20262064, 111965245, 130674362, 130498251, 738942657, 878830714, 687381682, 780129300, 450345846, 180164422, 399830849, 975617481, 870639216, 635849794, 538230023, 748021299, 863382202, 516287754, 181978495, 185689253, 944320745, 975915203, 627018135, 386459428, 374178093, 197296986, 486725678, 785824210, 363116264, 664196438, 983965175, 289101936, 346990255, 479726237, 238907122, 527496047, 364520196, 461816653, 772129802, 668490113, 635595891, 822911691, 608405009, 476144685, 498484728, 854364746, 989342811, 153673749, 625329690, 429447761, 638926994, 938855132, 449273059, 946567562, 203928859, 914009628, 920393850, 209430662, 50100093, 121340479, 657167121, 477909484, 487282824, 730635206, 851553402, 202380385, 319934215, 120136107, 973504716, 235971128, 832898564, 681517441, 470196477, 480681702, 667951941, 192536073, 40419710, 331524779, 814968156, 381968805, 783725420, 953201620, 477844130, 212521608, 992179685, 628748567, 70179603, 337179388, 231756851, 948814379, 738146910, 604960132, 639068587, 459528350, 569226972, 475183463, 87271662, 161199746, 337518700, 680187978, 386685834, 265010108, 16617623, 442215135, 498530098, 434070708, 913186846, 121535660, 716567375, 488527602, 854798168, 38755369, 140763011, 640891621, 912814297, 260665680, 645648102, 474632537, 234127322, 566602564, 233582206, 374922007, 575062949, 825693995, 624625667, 701312873, 990166075, 340048596, 899225882, 610677133, 218258259, 49338514, 647540826, 951308552, 632335770, 110789133, 693637219, 281468442, 349442436, 937985867, 900577670, 252964194, 873605444, 870351369, 746139607, 843539063, 48502268, 652351558, 901458542, 925174665, 46038266, 238905671, 619561310, 880738011, 745609164, 905566186, 622369105, 997130241, 107948386, 185642324, 176552672, 313892391, 224909660, 685047954, 594745805, 767455559, 637552747, 53988933, 906894539, 346307237, 320668153, 705352878, 115055606, 979636728, 640713243, 964387050, 243287968, 338923574, 844752037, 72856614, 458388593, 155161894, 625393042, 603060851, 821956347, 240918280, 89572196, 630640331, 4307419, 171035401, 827393059, 303766830, 246612461, 710124470, 678335391, 360180243, 942727020, 186637566, 175784758, 743894246, 345505234, 109382094, 321432560, 325330166, 394851690, 794154141, 13732462, 885335108, 386859216, 449631159, 566969132, 980381033, 45136180, 997195777, 210542618, 766994875, 557135330, 512696629, 680099601, 211527770, 895193059, 731006021, 293967900, 316491193, 200063510, 744541172, 184132119, 100237787, 356147158, 502215909, 804570526, 569102193, 884129911, 401557142, 264693775, 857834213, 59382741, 228082470, 403589068, 699179327, 126437487, 84545185, 956523641, 9148879, 726088212, 128838448, 742855950, 102254239, 246779759, 597127948, 933646134, 557605179, 698065930, 160000859, 302589678, 406729339, 966140012, 836881561, 185230898, 89021791, 822377480, 981274199, 913478349, 72726385, 218956887, 154111429, 161904308, 530875476, 96156606, 886337992, 483787402, 388425773, 934064449, 957801647, 663196890, 95492803, 184896491, 289844571, 127602523, 995302572, 984529514, 864166435, 674621551, 669077673, 185402177, 997269505, 762561296, 538040085, 31104011, 10681603, 603409123, 303349983, 66807818, 146060947, 113063494, 916183647, 359753762, 79975175, 97225342, 658764337, 944441000, 367622680, 150551742, 410985439, 776199588, 373863546, 528257538, 83027972, 498645460, 364816400, 462484991, 411656957, 749395618, 978317422, 831396294, 385470068, 546905437, 210803495, 759307909, 568942670, 515618188, 191173211, 791256834, 705914792, 101420875, 839688624, 912011038, 42139771, 517365630, 365462118, 326833979, 180057159, 775480207, 401346377, 903350668, 352266862, 100288735, 730128537, 45416874, 349107719, 618930002, 760699169, 832947647, 15684061, 89408774, 750525044, 688190577, 364919897, 777840816, 997326849, 779162259, 561397971, 279984209, 587794065, 872208012, 66610455, 25525883, 159391206, 323951677, 535488091, 278854428, 801317967, 365388260, 879578282, 468803785, 462049696, 874480121, 100185464, 669103261, 229740352, 272739440, 740139732, 625362799, 106826509, 86998834, 493745636, 105643797, 253139025, 291340787, 365189571, 520086200, 198757581, 458604676, 785605850, 41778704, 873019750, 650411654, 245571657, 941556120, 91151745, 76039871, 214666706, 498680866, 641098626, 729520145, 344191836, 77396919, 730229804, 456540953, 167543648, 788779559, 983358253, 599296566, 555065818, 923135854, 424951923, 870085471, 131531324, 812868549, 680858300, 191134689, 723076127, 487413837, 775545743, 230297483, 777661762, 192734624, 175297235, 644501756, 652565609, 34451919, 536126062, 684412149, 432114380, 596543272, 973374004, 568099576, 718290748, 778408193, 710223508, 632762246, 548607794, 116788622, 176311076, 317429790, 196417756, 686452287, 902324615, 254437813, 82198389, 102449166, 36376701, 180038990, 619046625, 81850974, 943442087, 958651539, 691027499, 456652640, 963793159, 863913742, 598107751, 609339752, 180052463, 674421583, 472368559, 10859562, 580083466, 746389888, 885754380, 964109225, 984102558, 526135450, 783148440, 819838255, 695620442, 395984067, 800416492, 41352293, 290052788, 80090738, 2474986, 564655146, 490062203, 370329727, 785274594, 121596843, 734727546, 629952065, 320454468, 79433718, 182465976, 128357382, 928808371, 621147958, 553764637, 67636148, 303707295, 254645870, 968166958, 493030368, 302719629, 369780199, 180688710, 141681072, 866385496, 677351229, 751913829, 217886803, 433002599, 890282494, 726947299, 81243094, 965291037, 921147444, 259190455, 70558637, 313253244, 568366873, 639100351, 807227219, 385721618, 649537093, 758251102, 729762033, 440214615, 722235755, 743119801, 453458652, 242022677, 738177516, 509421523, 591346972, 706364665, 294810090, 87662281, 566592447, 289380472, 170182147, 33852135, 413771891, 631173398, 3141603, 325685068, 180358367, 218610812, 691333148, 759635789, 515928953, 94512963, 943610182, 797815604, 173777120, 404125444, 362573553, 649169809, 208194153, 817380485, 44986925, 823861605, 854974217, 915444240, 564460401, 104305718, 883210781, 676553553, 63980140, 800290033, 544147076, 577566648, 226699064, 294098144, 316890790, 74369971, 979091545, 274823407, 698388578, 291218299, 604140232, 966953819, 815982779, 291853120, 73859422, 96628836, 222001029, 187645628, 583005067, 933768084, 958072029, 821771717, 32543220, 168642796, 876580961, 971815796, 580234246, 726064435, 552236310, 895107493, 88766265, 877222259, 102152921, 272453158, 818995367, 616783110, 467295181, 726608146, 492018565, 304105877, 255347471, 587158674, 847650358, 121428231, 270962673, 165878160, 845869005, 664753494, 384453959, 465006842, 456509667, 950109425, 142077773, 209261594, 987160959, 820302867, 456698636, 3686279, 201122294, 844385157, 595856983, 976926911, 35992622, 398563738, 495821589, 563619609, 626191432, 388612721, 470235252, 513737760, 65722013, 653091152, 546154142, 526810706, 642924700, 202995754, 418782773, 558697167, 441405503, 858228975, 48571076, 70268289, 673217729, 768937498, 146736860, 517902461, 734788685, 743634341, 982387764, 826108422, 808239660, 612035983, 753175005, 684407819, 676021697, 779519836, 119674664, 267105555, 202511220, 373984095, 120046565, 806164431, 745650714, 558303806, 240120162, 603076296, 592685350, 124425044, 698415800, 689399194, 828677615, 906785886, 879220186, 72921396, 179698133, 386713641, 549634895, 562659653, 912176642, 529436094, 892572756, 124604549, 922971523, 184886102, 987706939, 299754106, 157137551, 773218765, 986335473, 67903017, 981455380, 332049067, 229128165, 539610409, 178581799, 763322323, 943908652, 9049635, 544686640, 533184832, 473766631, 475519737, 49946903, 820085465, 809817938, 929710240, 876490364, 566178757, 140237788, 829108899, 965820383, 523251011, 399573309, 229251979, 955590218, 334810606, 983129848, 883590428, 379401462, 690406637, 682396277, 600452879, 116997796, 767827677, 904637593, 161822101, 519933149, 152054980, 540346602, 76945165, 798867669, 274041195, 472280344, 721859692, 519819969, 346537272, 671595488, 836385194, 428399102, 751388534, 675859413, 10131032, 733665728, 555104799, 674034, 65337181, 771401233, 564371302, 371736786, 868593505, 224890288, 439415357, 309060206, 343690841, 936649128, 390064650, 153113166, 225172923, 863364514, 90082211, 724844096, 699037601, 616660621, 986930917, 494134280, 435319608, 713980492, 317924897, 356847483, 768237188, 388169337, 873132826, 353916984, 431691101, 385159800, 258143877, 492854284, 590111424, 591698633, 591966803, 785039890, 971282549, 634171034, 987079778, 729158104, 812631244, 336243830, 193229714, 545270522, 686211223, 663535048, 98648493, 712938413, 243362839, 93891043, 392912105, 446051782, 181558132, 974182437, 332098219, 235110251, 991104764, 358693390, 144550968, 539609050, 672617304, 146857724, 738985295, 202233322, 119453561, 767234994, 762870200, 61866661, 182260098, 610789098, 730030503, 529654441, 386064901, 207352364, 833367233, 106428107, 816920122, 984157518, 910578022, 75459855, 803324681, 939486528, 737194519, 406952011, 249242364, 504537031, 427182373, 388100099, 993793582, 487366912, 575959051, 309055944, 312664845, 607186089, 713846057, 265860893, 319463497, 711225394, 469427566, 589728163, 723758706, 66213302, 473283781, 27081708, 601086606, 712043231, 457004814, 483102522, 460196925, 121721813, 104715331, 803357979, 524172223, 208410890, 559792416, 877604929, 827705737, 693589416, 238954742, 24940521, 243641412, 478883286, 365317603, 120038106, 425776701, 292578152, 600312369, 773034471, 659089284, 900340810, 559190230, 692520416, 486752358, 283093445, 117985564, 565486597, 416449282, 401394116, 839880897, 120084916, 734220415, 675952276, 240340851, 834225127, 833098147, 253395770, 595390213, 576028049, 20209855, 976210756, 664884566, 551387879, 407484078, 374265314, 690106579, 77444736, 391862710, 584694679, 476600810, 44406970, 238922065, 58934694, 106260804, 347716726, 995212019, 24243943, 813496460, 452206508, 534211978, 255153917, 168589694, 919133639, 615000602, 580851548, 973529366, 808475511, 369073455, 399538427, 302480066, 755444402, 818656470, 333748563, 229764175, 493426488, 284613486, 830572836, 736713908, 473702533, 43635831, 661911875, 80599873, 7756830, 168759350, 496440326, 340093989, 243459714, 193342917, 16647315, 132505054, 464976400, 507430988, 856485351, 720229744, 760087540, 249265049, 140239426, 217035354, 163714438, 456593423, 808749121, 60767830, 346702705, 857405864, 475859255, 244263801, 433533346, 427399084, 149237237, 518499861, 229461224, 569503682, 224502400, 819567987, 710187918, 955529325, 444443883, 130332840, 310746633, 322824051, 25087380, 736438445, 37295761, 117063661, 761343215, 283301282, 404646517, 116791103, 420435667, 686583180, 338161800, 786653651, 286785232, 911969174, 814798869, 811435010, 631200251, 849778613, 56003298, 994205214, 185693057, 170024298, 74882727, 449612941, 689277657, 804460743, 767791857, 608251306, 5166302, 24669257, 907077867, 323770413, 620824371, 475654276, 299187276, 316167885, 27427435, 554516743, 146112381, 845940786, 706923471, 140734221, 409433936, 174721218, 698486647, 968115110, 373276346, 450288835, 653200256, 126482097, 796441406, 436802722, 791574365, 934297861, 708668654, 872191980, 54798926, 920891708, 56994166, 24251134, 689921563, 326175779, 412697750, 450729271, 946504364, 961709509, 435924377, 23019133, 793433117, 618575012, 98086896, 309780655, 593459907, 939491182, 65990383, 372804582, 956906870, 452783093, 238261788, 810306729, 980408608, 997687297, 381370542, 53974193, 226898995, 92821162, 590502920, 88276336, 861741790, 656068372, 543741094, 112454830, 522098960, 342523977, 253294135, 796495079, 987195716, 882849956, 200862877, 817898550, 229304059, 526116643, 45700100, 952569446, 667146226, 672275795, 798815239, 659456253, 223356488, 352676439, 523516396, 57527803, 585366546, 489818364, 414613271, 819478798, 213636312, 482193525, 442087439, 121643984, 111218923, 169461787, 286457463, 921498195, 219232956, 36428307, 856414317, 728316473, 202471530, 77580947, 701644863, 312696521, 299527470, 800652602, 201813086, 910100350, 510742238, 120459140, 592252058, 44786098, 244842213, 814442342, 741275893, 501275886, 251848171, 584639877, 621416517, 912818706, 415084930, 151883415, 691422338, 622428407, 643527358, 355062235, 312051720, 838289872, 310648082, 679212298, 208835496, 471363510, 257697500, 93318783, 753080230, 87892379, 589895863, 371947123, 130830107, 172752617, 230037150, 54691047, 293476410, 160716280, 559822643, 162665083, 99559649, 197425845, 494096569, 896199247, 518410646, 6866231, 182122846, 442667554, 138161659, 193429608, 673222313, 723937756, 714084126, 283484566, 858416550, 989312693, 347626387, 22568090, 359326002, 997720065, 753530383, 105271309, 84801041, 882619614, 2614574, 278567665, 478488659, 755470491, 175331993, 839171977, 314329684, 105763885, 63008642, 946718706, 939983088, 864625187, 184994789, 146983950, 934913198, 657367773, 315289645, 100031755, 150746812, 372270586, 877668441, 591188236, 2584786, 549241070, 326378909, 178073579, 610296160, 750230131, 264377570, 402285263, 986918218, 783673273, 451035702, 941187132, 290276922, 200778571, 866342657, 631469064, 385044432, 928039283, 906051442, 528813547, 256340554, 114041235, 715076216, 201794534, 190457874, 848711840, 737588827, 562340920, 859641768, 541394769, 400112219, 977383997, 485646132, 503696616, 860064982, 363044106, 926687437, 64419224, 464394021, 371427975, 457845203, 550249296, 984077682, 622512056, 774839794, 298563974, 880595929, 466823067, 994713423, 777924766, 366342072, 349032965, 980625315, 579122606, 964550463, 151294839, 723438283, 702486846, 263990211, 483070006, 834293623, 917562957, 875029044, 92615449, 847131674, 543633072, 611843309, 411188740, 94381282, 989759276, 151657313, 955861351, 47843963, 535485369, 491902953, 608600620, 391439116, 576177891, 674274558, 80952154, 511283781, 265437738, 110585440, 48078303, 447352184, 443168996, 158867842, 241893701, 642752679, 693335063, 329455212, 966154401, 527988857, 978023000, 472255847, 331598445, 509217889, 546868578, 741918425, 591570422, 335205637, 644044462, 672697867, 562923438, 675961041, 497651286, 984032725, 492264757, 76373771, 931205394, 994820683, 836432952, 375746406, 833661013, 152787522, 591823265, 451087458, 997756929, 342491840, 381280648, 813780867, 768142219, 628704310, 514674182, 683955255, 504462978, 882259715, 800826738, 850374257, 650797168, 372464778, 33403909, 80324073, 572152650, 733818367, 56531747, 46845526, 957214000, 233518737, 179876881, 925942734, 539109764, 678016425, 48612671, 641281794, 828504345, 851175132, 472220500, 550738948, 183811340, 719541821, 75275871, 766774347, 704614896, 789019997, 388099794, 428570647, 186931773, 267122352, 264128769, 178070370, 41513986, 46263594, 249322730, 871021803, 182408200, 537442954, 730364672, 727638809, 704950655, 706990765, 374697809, 402050864, 489158711, 176886054, 415698147, 967922740, 192735034, 126851345, 772574895, 685672341, 604523924, 349598117, 878776131, 48614264, 284471335, 47625262, 257809094, 860214341, 594708782, 707854553, 395628417, 265195391, 352957396, 814097630, 549832614, 415817817, 419844312, 934945627, 456005519, 736855170, 520192062, 865332306, 258682815, 104266272, 182731059, 828678279, 662539166, 45268678, 589150756, 138010429, 886862280, 505876513, 699795365, 26992155, 451675334, 795991771, 176133431, 838450934, 549266544, 6033090, 864186445, 84384799, 22708437, 330277598, 673676036, 317013158, 309465001, 958481030, 879471761, 562176482, 915596000, 287058709, 506964207, 335668309, 44704387, 700659742, 375262522, 552739266, 843217465, 110354051, 681582125, 604551113, 388920408, 818330888, 997785601, 718534176, 888703306, 855310788, 779821162, 921808403, 639114281, 613213778, 793019209, 643262265, 436104006, 733050037, 532427404, 166906091, 511885118, 433286344, 79695603, 773377636, 661098015, 774492088, 766866222, 351225710, 139427214, 716793012, 899781160, 634504248, 182694130, 201189511, 439789141, 148491677, 733524069, 314354248, 231024848, 280177229, 936362237, 890338247, 50092732, 892240095, 833673807, 859887235, 114870176, 339502139, 136369720, 874982094, 370069866, 810371260, 811803576, 709054356, 552535431, 295211139, 43499417, 289118818, 246872818, 246314219, 551944075, 681455020, 625691689, 719290266, 644792570, 561875345, 681716962, 208841465, 260043100, 327249377, 598500967, 150115282, 229302338, 73878093, 392802925, 872852412, 20889352, 798773185, 436509875, 995137323, 325205827, 785380164, 621908005, 290213072, 470778060, 74370311, 544698049, 773119685, 537142112, 844906243, 107333353, 630028612, 249340433, 849588433, 320549313, 620542185, 863882249, 824751510, 172095918, 512980571, 537820636, 393407616, 365114902, 551164392, 727392653, 881087763, 83771824, 980269817, 893511956, 367497592, 990801303, 964108860, 299648283, 209006045, 277532909, 385754820, 461567927, 401130984, 711598138, 124726031, 934164912, 840076435, 65765662, 407482213, 905556451, 827738128, 340429150, 407641795, 594689521, 421616036, 860660240, 786534990, 742829095, 248369090, 886895048, 440873211, 614270918, 993484627, 388830881, 105920254, 96367312, 258308145, 586770794, 448411536, 322250878, 451905003, 825404981, 557500299, 516348136, 412383825, 268063031, 611591327, 841328251, 516096198, 216057190, 121506732, 298271636, 392948787, 486687002, 720930443, 284049788, 922872836, 359145374, 653800845, 888326273, 743018709, 355111754, 211865297, 316381123, 671328930, 274303897, 857952857, 58394311, 868297905, 88155538, 497206569, 158714895, 467860583, 98208878, 166161576, 842348320, 314631674, 950284484, 245212595, 626341083, 329780937, 540221371, 222349718, 51224583, 115100663, 517310527, 208443230, 90019495, 696194115, 808645489, 953080655, 40925487, 878471900, 970843220, 913126008, 978447946, 362921397, 844635926, 482505804, 228326320, 991099025, 981018756, 45775614, 431956871, 400724404, 798176052, 168959460, 304669876, 75402427, 589148408, 306797950, 836332968, 222064412, 735306456, 830686385, 5429781, 16700031, 290041733, 336224383, 373194944, 84611108, 442877190, 219055707, 981176789, 32456465, 492051279, 401210246, 263067725, 162427608, 391574220, 725543089, 909041304, 174184723, 347810221, 283851134, 697114210, 385882927, 400208246, 857588290, 519798323, 439392856, 145026394, 968920667, 40045369, 796862276, 1237493, 324501572, 282327573, 762175837, 744153278, 826587489, 684287040, 943129090, 392637297, 920160192, 559920598, 669739424, 367363773, 156732159, 814098209, 942080297, 160227234, 340803981, 39716859, 222650647, 91232988, 889463936, 64178691, 71098861, 963526362, 678969472, 310573979, 374086666, 776004495, 77446479, 33818074, 271656052, 650975824, 229518881, 127322935, 802255034, 484083479, 926738042, 246515184, 842763431, 650481991, 599108862, 684012276, 824777612, 90344355, 839497178, 70840536, 282842644, 433192748, 996222797, 837797791, 791404568, 875079091, 446848564, 608065578, 23393201, 715623476, 516652911, 445141247, 659187578, 862595826, 742748519, 40621547, 598222955, 981767695, 961287218, 460573722, 246048970, 628717404, 678998670, 534401495, 60111061, 156626622, 545770980, 783305613, 235257587, 818672352, 216679391, 902735786, 189742324, 192860809, 770735644, 823890723, 864639935, 379125551, 29090554, 864003193, 981918857, 719229484, 685124263, 860240054, 445254351, 870682077, 447283383, 226729326, 411999061, 620133515, 128895278, 369088758, 123244936, 753832938, 445863999, 295673486, 671035443, 852304509, 754316921, 147405045, 38318046, 542953317, 498924817, 782418400, 706383104, 144690236, 260891339, 584213250, 637143733, 516048244, 922303809, 706008122, 51111369, 315586699, 904352027, 500692978, 742696939, 162842534, 797418770, 589301360, 950428958, 109305406, 407286829, 345666574, 569754519, 878940071, 712417239, 757086653, 866577681, 546378658, 919774617, 471805091, 637019550, 398907802, 823230017, 86888560, 258227080, 202062722, 215216034, 680408953, 488816966, 823707081, 584413977, 603219253, 743538676, 907812419, 903579906, 521615639, 720286605, 911052979, 410608853, 926609285, 291848097, 457722120, 151225704, 781352377, 857183885, 52152859, 765771200, 940727567, 218016258, 837398953, 873704791, 31990070, 467337090, 899267193, 854648077, 272073538, 662803476, 288783324, 465104223, 113349532, 266941064, 147049072, 965238196, 158445395, 539964675, 536307162, 962989658, 988667949, 72752753, 636533880, 384911391, 349194289, 508106758, 644731326, 215846942, 302070116, 432508930, 982599086, 863975338, 907113566, 210778590, 145926560, 904170963, 36929711, 990252309, 48314418, 563960524, 610122691, 720468707, 93822814, 640182571, 790624710, 116480812, 466884042, 3033025, 978158191, 753134639, 910008035, 965688792, 16271610, 71114035, 84321398, 517832171, 937412657, 956698050, 485907898, 227577068, 290117123, 179510507, 862154394, 581461320, 276118155, 361491731, 946675923, 766085753, 543505309, 681663658, 937733306, 451971380, 550198637, 429481587, 136226579, 965982416, 908619860, 548415880, 308391555, 216504779, 732769767, 680842324, 363304073, 584584460, 745131459, 187988360, 651175115, 872016672, 626795912, 870618346, 293579337, 857662313, 423825179, 248536388, 559836292, 367127539, 634603513, 237748096, 82939080, 540204486, 922056679, 21176006, 332376747, 808544515, 691349156, 368730913, 232503421, 40404246, 727377010, 938238570, 974176889, 724347126, 570161063, 350994402, 104630797, 522960296, 992702656, 740466122, 909273610, 205922495, 228349318, 404165427, 500965316, 863744837, 100561147, 804560646, 921314755, 475021548, 797050668, 545265700, 987585632, 126387949, 17996311, 886267697, 199281869, 967794415, 747032971, 48390839, 780931981, 424208059, 313095716, 439637502, 693428537, 644524203, 235117626, 125740043, 256868880, 703848104, 531983183, 26644182, 326545576, 563860347, 273077071, 213571081, 263405353, 511686726, 321462350, 210348245, 101497877, 413844107, 708513563, 716613711, 778470760, 411063153, 719824928, 614332130, 928236664, 162083264, 24285538, 751129054, 534256321, 818292433, 835731041, 12663484, 384468749, 963535386, 73368430, 541212465, 758073407, 838669668, 866516519, 177497731, 870939347, 273985449, 491193882, 11888150, 413054211, 121675655, 404119830, 695353634, 805140168, 703480086, 875709679, 261145608, 841326086, 334183924, 837133025, 348291508, 389759918, 397147125, 59837332, 608545804, 632674954, 152116834, 101255610, 546870518, 686114224, 747700389, 559145459, 345724699, 902204392, 448977975, 372825357, 226111797, 279151903, 112262396, 120060081, 451934386, 301538148, 314242340, 296342675, 208752916, 62212522, 15636437, 349207900, 391343037, 344699597, 437197669, 913460984, 497526404, 453392943, 447916529, 439610093, 581453433, 36460698, 34324602, 588971243, 772640422, 692478997, 285515553, 773939624, 820629599, 780452003, 131617230, 456088321, 811360034, 264718047, 38407566, 446286378, 337325605, 561424451, 527447404, 960607938, 143108648, 92443051, 128953072, 992975646, 625702229, 149877053, 665964071, 577690952, 854485946, 885731559, 482829315, 992289913, 819323671, 533073685, 347793511, 490727690, 820972939, 665146710, 610057627, 613686259, 735677108, 768927381, 459520382, 588413076, 822165625, 880783338, 851208012, 471954326, 608626135, 503646994, 489901725, 272343320, 226699867, 266592416, 797066671, 736005492, 688528192, 736882045, 631145804, 524095628, 629320424, 909164909, 543992931, 404908969, 97989300, 464855120, 710362446, 438245182, 223714616, 782211555, 732184072, 70118894, 96336968, 913676626, 809499223, 982032368, 61377373, 760747682, 758073033, 698908831, 731724474, 613748166, 451463837, 477795109, 248271589, 167405303, 172845752, 491564924, 600938293, 441795214, 981086492, 189700731, 844958463, 844325495, 627458088, 840320315, 886262911, 799348616, 923641244, 58498898, 420979376, 883036015, 882050214, 951440973, 685417864, 580033227, 19794247, 759088751, 226455159, 76027490, 271628798, 270173301, 467277807, 537594759, 907371103, 898556011, 278215973, 636142774, 42145829, 236140172, 397056022, 360929846, 115064548, 759032161, 984337449, 173268636, 831474838, 335797744, 696772526, 418192597, 242029404, 214199551, 644072263, 375694267, 832264679, 837051883, 247618650, 5065516, 572884906, 366832864, 809998206, 776674576, 747756155, 337017, 150258853, 531790767, 76762129, 884822793, 311215378, 282185651, 80020935, 185868393, 117934624, 933418929, 565436761, 112445144, 438891971, 718829855, 795376421, 154530103, 100863226, 670967597, 726665631, 468324564, 890823489, 195032325, 987542906, 76556583, 896314481, 611708638, 502294917, 431682257, 727239868, 544163282, 739761435, 362422048, 354301752, 848640977, 939622062, 807452487, 805186092, 992587635, 386191834, 247067140, 304492783, 217659804, 313259376, 356990246, 505595660, 658084625, 72985629, 677545918, 554653870, 384118594, 474108088, 693206845, 719464338, 436566413, 235912570, 176958492, 191448652, 714967727, 32052202, 192579900, 307761739, 628194115, 200638865, 246427142, 494010585, 295055712, 756016027, 794971493, 382369414, 795105578, 644102934, 392519945, 114460967, 984763451, 995286105, 317085517, 221065630, 493539889, 674906409, 364579052, 417930761, 406315622, 727128399, 168121915, 628038866, 96614857, 572296205, 272635261, 375282292, 842227788, 991377949, 331767524, 571172219, 548446423, 993672740, 855591383, 31654038, 620803596, 836490286, 546067698, 557621968, 695578229, 121482918, 223025891, 395457088, 90779066, 727296961, 986213395, 568196395, 665171286, 267995962, 616677302, 919683334, 495552382, 363676282, 179346695, 319347414, 72275484, 675864239, 269804525, 621029085, 336308652, 546203069, 73428862, 533884492, 868614824, 707076285, 101116661, 135962754, 558848957, 687765508, 383617497, 971796522, 381435100, 588567707, 530055507, 370435949, 91130049, 756811504, 305394549, 303044209, 864137428, 785414156, 763949397, 695268999, 692154627, 141918303, 103676182, 365156565, 915805793, 505375233, 552336230, 923896780, 408460061, 980309902, 492078759, 741882145, 455289011, 937793157, 536852104, 50183914, 900784517, 753235259, 469743264, 183240249, 867719436, 258733196, 702598182, 930334405, 124621182, 536241700, 751390692, 176085846, 712713363, 880186127, 693172226, 403559122, 496896791, 498963271, 243683456, 53040664, 787101702, 496106812, 154527972, 819657899, 655454599, 986198216, 802715221, 446057775, 856045205, 582546657, 632052623, 282545866, 658853925, 338334323, 355612697, 277132098, 234713783, 572229917, 793986258, 70063309, 361879353, 515049930, 33106651, 41921850, 735764067, 706551620, 13540854, 585850754, 300543303, 705975521, 855143792, 851415971, 228502407, 504620847, 241551261, 335992909, 729220639, 464759474, 559983083, 263752278, 551479842, 486742066, 900801166, 824718350, 761208288, 366555076, 104205445, 579676210, 279896208, 1250541, 937924641, 636751797, 912975045, 80558975, 346794708, 132932821, 119477371, 172455210, 511592437, 185437212, 121820706, 960245660, 239441643, 774440895, 681780978, 534118278, 60019053, 30155622, 712010527, 591241520, 146289076, 326952194, 799278361, 514171866, 885639412, 633865007, 329544642, 356095238, 450170405, 699359525, 279595115, 366177696, 346260208, 885334781, 243376179, 843051208, 640668899, 15138958, 58992782, 520890264, 781865475, 869568033, 208224641, 871806236, 200697058, 569852982, 919062625, 465395624, 60042458, 943145451, 866232384, 829973271, 337976138, 809786149, 619292602, 695299160, 916234740, 918716427, 915671250, 21787688, 126697885, 229396859, 796817283, 263276604, 787136201, 854894136, 509227104, 259280272, 488105378, 431359037, 332442283, 915082802, 774816116, 259720753, 203742039, 245514977, 187132657, 346684679, 844175466, 758824305, 38722368, 116741248, 195931355, 39600783, 791469516, 290736004, 238300405, 465198298, 22203485, 69934877, 618583209, 674004863, 29467347, 733422608, 53130402, 755436362, 173858363, 440732010, 996728186, 496242334, 511244148, 728006428, 406748230, 92951476, 226103254, 858145191, 267105989, 961048335, 626699135, 787292322, 84294847, 588375189, 958688996, 94179691, 307500301, 489016046, 290425774, 252952888, 486764683, 204590376, 903359932, 956989609, 683658904, 122485816, 698891390, 394004249, 151240033, 555782538, 377722201, 662992864, 409328235, 707927875, 665996458, 756409382, 614004264, 644405862, 246713244, 894853689, 142306743, 541202384, 415286418, 490292129, 368356954, 269828111, 735973443, 361747729, 520940092, 464014810, 830078114, 318016822, 539422113, 35214599, 3878415, 863733387, 84379675, 101046532, 248220163, 762609831, 669169171, 345649178, 121729857, 66351264, 595793635, 838858302, 507445834, 724536985, 66252527, 291959000, 232488200, 485616343, 253715494, 585300478, 927364852, 946064072, 360114872, 679422470, 380043770, 655625333, 623754701, 353366071, 70119713, 882300120, 108517677, 352060712, 81857219, 889527596, 727418888, 313852040, 903496737, 225438571, 30383915, 800069994, 672473529, 690842859, 428702932, 1178217, 737051804, 367092512, 621254077, 498975073, 216766673, 590419635, 213699542, 612993147, 573740795, 908669617, 758372107, 6163814, 114730612, 975363642, 284751841, 25798973, 112251200, 29885801, 908906170, 815520834, 355093959, 817676553, 976886839, 816027467, 721344118, 205495104, 65166420, 928422755, 654495493, 684960881, 660534202, 729497481, 12543690, 199765522, 867341399, 410373153, 517770057, 323038514, 557654007, 640460069, 879793784, 645323805, 141650641, 585919712, 701445435, 622776608, 557517728, 573039310, 709340010, 535551274, 343291590, 270956183, 169080900, 638725620, 892449002, 826702798, 143392616, 63711563, 455984587, 941805487, 906521611, 171821833, 405717505, 162471279, 814722302, 406809855, 924011483, 365281778, 28001649, 742262063, 497102607, 173055941, 591968705, 850366977, 85012149, 729741110, 536563540, 143099926, 723928647, 293804406, 843761005, 880330154, 901352548, 404701425, 883018105, 74114257, 304125653, 11483973, 2583151, 544027391, 511456805, 655268126, 952661110, 228137383, 661007383, 106842222, 809534362, 829055247, 237827138, 531595875, 149593638, 121527886, 657206119, 595860142, 512835894, 522114643, 776380548, 992535206, 572178367, 729782525, 422970393, 924965633, 852583912, 133650186, 569489287, 440879389, 204716968, 876416984, 87360609, 276231196, 848365500, 182817180, 484057555, 704425776, 186638173, 76110807, 724266594, 587536483, 326600128, 105809930, 562363225, 722104052, 398220703, 845235000, 218401361, 228817429, 894909359, 973054745, 966271107, 203665609, 354334327, 417560722, 436095990, 450947633, 27399463, 824010473, 460445854, 34149722, 28497083, 537906748, 12125567, 729301932, 844082958, 725509232, 662210066, 848437302, 206348875, 227961073, 724486812, 27283658, 473252182, 384848358, 979976931, 37929352, 717084365, 319550513, 510631743, 843049209, 895838735, 85547774, 309287506, 817713782, 49043448, 854797508, 654012504, 426458948, 795852130, 620719365, 469745591, 535343147, 532117368, 828003297, 186402291, 868609486, 478453435, 16195293, 725513723, 761590394, 119130894, 557555312, 904275541, 508181920, 490204304, 673947276, 997965825, 3619854, 190685271, 865497613, 526109273, 774341677, 612571674, 581544747, 46410581, 892668830, 295251460, 589505636, 44138168, 986865977, 430870895, 535595956, 328034186, 531417502, 271870547, 508126601, 56227415, 371884096, 261049480, 17988878, 670384165, 606027536, 625769244, 866103450, 897369716, 939394077, 493597858, 131994689, 441424978, 983893038, 599553615, 974798437, 408949275, 679280333, 613774206, 83485520, 762180498, 890296274, 22850050, 692193148, 476284723, 199153737, 333573113, 347502303, 835260074, 188218382, 898529796, 952382783, 828850303, 620574782, 111678244, 456191360, 675460396, 990019324, 261758198, 115909240, 527886078, 40532281, 292683273, 973062428, 244909182, 472175871, 706428812, 875480257, 409739399, 498985543, 106818156, 264377711, 740218939, 26477906, 720165896, 903303376, 60821992, 308934950, 554731638, 42785794, 583853070, 30778066, 642350908, 626386762, 959871274, 539797437, 109616478, 638756738, 517336330, 638408926, 927329335, 688041618, 863280413, 746850752, 101235765, 350837170, 537912650, 750378192, 849944608, 561868190, 655470437, 134905207, 149763735, 164343456, 400326301, 965772322, 100906543, 771604210, 455050175, 456008184, 255371119, 403350154, 60229570, 28081529, 296126029, 47227024, 22393049, 507618447, 621543283, 590374057, 407221171, 225783743, 869760123, 436243823, 250637943, 220964846, 625046262, 405377052, 791442115, 773215933, 809830435, 347437402, 456409353, 629508949, 207542465, 390815751, 575063884, 616223402, 345711169, 359829149, 810336380, 337125207, 321763679, 910660263, 676653294, 307049148, 156025860, 439858943, 419144936, 847959508, 155324041, 689015781, 339606149, 941346829, 104417748, 806017572, 235681755, 522203742, 128848750, 983576055, 545781568, 479263911, 376540115, 934571975, 543068366, 399404249, 794070108, 322812690, 685095738, 549260482, 564537230, 773074455, 585498485, 668241828, 115018575, 243254011, 526467700, 216848082, 146738205, 672481912, 80358140, 906241487, 779033498, 960084760, 580454718, 612613210, 548902001, 151152884, 597835099, 527564071, 746170461, 372325311, 947221800, 246059172, 259205323, 671747920, 502555292, 411864901, 91061423, 529863775, 221333777, 36395699, 568203006, 717512841, 96714804, 98270030, 835733333, 31071705, 361968878, 493200611, 357042063, 188864149, 141742283, 230040508, 429208275, 651394512, 993778523, 389475500, 672935370, 538626719, 11284045, 125403627, 179663001, 803420199, 997982209, 131037589, 875887368, 108966059, 551757831, 1047201, 541522697, 873431101, 441309807, 41059566, 1307287, 725615691, 638406009, 112599664, 738366506, 286965876, 876857422, 895940618, 586788173, 241279338, 918708165, 446850567, 157164842, 837472553, 552004119, 96100226, 31504321, 471920994, 473359353, 647284845, 469991544, 226743703, 931434770, 192579814, 591619571, 723421942, 73491975, 196793035, 467456599, 725783586, 827806063, 120857851, 656766999, 276584452, 549138054, 952127692, 75373406, 69398051, 186135293, 679127089, 937956397, 316365080, 295594118, 680491877, 1292393, 640602576, 274620535, 247430295, 662311631, 950487641, 588158966, 421589887, 305148080, 741656099, 874237242, 188153467, 132188785, 671850651, 700264808, 177145245, 493459109, 959899829, 890958813, 885584980, 225517851, 685120062, 470593566, 354074831, 145138461, 24911166, 599511462, 454074122, 932293505, 846878594, 315734532, 784389796, 192522216, 726065790, 963141818, 741062590, 453025721, 426282854, 763528950, 447303545, 128170277, 438378381, 556142794, 520978743, 357538108, 266232561, 100897267, 659111966, 95228937, 903039765, 424355920, 674765222, 867916590, 898292428, 281170460, 283647170, 429820884, 456966157, 769819561, 534128195, 699178286, 562100886, 987814175, 796815174, 242823066, 937490495, 251848308, 149901799, 430032491, 187662828, 181522053, 357367925, 962465895, 125065938, 32209612, 944237229, 731319187, 74000343, 684836164, 497982339, 728044778, 335701753, 275124648, 527083140, 492038841, 101417782, 311256028, 556883340, 387419897, 319357343, 149281987, 785615528, 939420141, 489152353, 732533710, 10847740, 996478888, 291480291, 388962383, 578129903, 183171036, 957689889, 673638659, 440083513, 989434834, 461754068, 289561303, 526159533, 981397408, 296632671, 574769596, 112814426, 860841318, 184078770, 351243423, 844880687, 631117282, 41645781, 241535003, 29588755, 916268988, 333082286, 957903655, 808615501, 437514522, 699547209, 545429901, 421419777, 423565837, 528261607, 271816536, 938494691, 805043831, 730380036, 205594370, 443802906, 47190641, 488513178, 494879638, 648946154, 574950833, 328425634, 977052852, 496754306, 523044158, 632777803, 766864861, 984549307, 745073653, 750612059, 304300310, 588797504, 195719558, 369959551, 787211122, 615298237, 337137279, 278683793, 40476077, 238079168, 754764067, 90320891, 132718869, 63986843, 55292720, 576835016, 523161328, 281956335, 223676092, 132736039, 221584498, 313606644, 79433921, 793647555, 620069027, 8901857, 820498516, 364795411, 845789708, 152169889, 164727606, 463691045, 982199377, 565877454, 763116605, 712855493, 489011500, 428734732, 735250100, 920129453, 664921399, 329053653, 753731121, 293688166, 273434289, 828466536, 870081389, 817729114, 295785211, 61944737, 666724995, 179354757, 322022231, 732537000, 835471110, 693886596, 281461719, 540460140, 837102697, 531367112, 248825643, 246068581, 991138539, 8083942, 745254555, 677493776, 537309062, 177427594, 465602697, 205225928, 996532518, 165273863, 418216476, 761940243, 187873203, 203459150, 915952683, 541478595, 76393761, 525109227, 795033809, 742403081, 225543729, 156745084, 998000641, 57745646, 171245920, 868927995, 190640324, 687403573, 906012610, 867837584, 883193286, 95568826, 314352155, 847547616, 257337091, 198725695, 841099804, 8984442, 252231489, 547056351, 940252034, 198435937, 400413369, 742924629, 924309305, 805090493, 325398584, 240780123, 186232389, 23485254, 515824131, 812631403, 539284213, 692506320, 286076325, 298095250, 866031360, 681686594, 527388050, 828207086, 23422763, 645297982, 478607000, 889902145, 615881545, 509613510, 589060617, 752118421, 462971367, 714408522, 269554882, 147629382, 838130389, 771250279, 523428512, 910425797, 320640897, 910468109, 913374349, 291565230, 425587566, 327462588, 236110250, 756427643, 275369474, 503802572, 91905670, 269413220, 858893087, 442411922, 536760112, 313494265, 882509350, 251058335, 352307448, 124511169, 893632175, 735938956, 194049897, 890836801, 713407500, 217103203, 592588063, 478449891, 133561176, 705387790, 631186561, 894384919, 89035185, 518094308, 20756993, 67503740, 23131797, 553838460, 124661365, 417980567, 934633078, 705511757, 91204100, 253072680, 268721477, 476634908, 365182336, 248550238, 862941581, 492822230, 851597504, 467162199, 852617559, 80040054, 686471081, 801919007, 201025432, 81150361, 743701532, 530309901, 88443027, 681299993, 706971250, 415125589, 483961370, 898301502, 96367517, 341822349, 562547849, 552477024, 885409624, 941722107, 841958347, 945531, 302261962, 781583981, 673921235, 625821513, 938510242, 846937985, 24307132, 867535922, 641357844, 725395613, 23812631, 143313475, 128904547, 448114411, 929229347, 848707867, 297354391, 473348124, 853049453, 227504664, 696936385, 969555116, 631719872, 846168983, 176478698, 509576842, 407048815, 297524252, 274916307, 833239467, 707031085, 627099214, 209922156, 640405292, 966594990, 317356857, 727124936, 399438306, 368427585, 661983764, 260096031, 382211730, 432666153, 329862793, 628463584, 717875419, 52133136, 226948084, 590487706, 278003927, 913461316, 328778491, 331269583, 978405501, 22634339, 847539550, 294575378, 659899911, 568127391, 797803040, 443431140, 246474335, 752060433, 76376055, 849019859, 473403827, 512618254, 229379849, 225837667, 392275384, 897118062, 645663053, 587188892, 805657765, 419225467, 647384335, 274633272, 812567654, 3016545, 453768523, 931215399, 514310331, 541314576, 666346068, 510476395, 446186731, 165138799, 490670328, 336838018, 545759375, 158506579, 324574004, 653854677, 682145203, 479240515, 104932377, 938858057, 566002931, 281088241, 935435548, 457798000, 198033215, 642651531, 733168605, 752604280, 957659690, 666956331, 993404101, 521474370, 836746709, 350329871, 379494047, 187631261, 765082829, 276369633, 897016532, 920730909, 987436363, 554299202, 647491214, 839913239, 442949393, 801397733, 133191103, 194460204, 32364326, 409165444, 806900802, 998014977, 984026308, 359267088, 728454777, 444351653, 386971474, 427655394, 660458067, 389910581, 232107263, 960026378, 701264942, 818679317, 126467154, 306606889, 347682542, 895631781, 648436135, 820753309, 892961661, 218052003, 379620480, 865647195, 538025185, 266213702, 371747383, 582575222, 974992258, 255942559, 522705443, 216643172, 634293982, 538969978, 668835099, 386688818, 19568957, 829671184, 838807285, 387246044, 528335203, 383433111, 555135660, 175612855, 180115534, 69713607, 751918421, 358396506, 924039783, 449890580, 266289223, 317252124, 782181017, 91347065, 574018830, 599716932, 490174899, 719016747, 782701458, 573368015, 314341738, 865884211, 173273323, 157177124, 348876792, 115512424, 487031148, 639210791, 889361398, 967303295, 109511086, 944291300, 205381497, 25046366, 808295936, 945242224, 990126712, 915959080, 906285966, 929065794, 225286471, 57435088, 657089335, 668873246, 379940579, 68184860, 910051478, 437491047, 647655719, 185034933, 817971448, 405185630, 224678, 405901788, 608154265, 354527178, 819561532, 775389892, 589881862, 646727746, 662505913, 520871885, 22641518, 144559409, 123912262, 123436409, 890513697, 622279286, 62460232, 775094214, 407711547, 340727510, 127716228, 811968021, 548419574, 359645133, 768516304, 322396285, 696917069, 780059849, 641234127, 340858481, 312216376, 603542909, 124473821, 130021550, 216505532, 662746865, 51037722, 798372660, 108713065, 75057641, 835470179, 114651169, 620536289, 536061223, 543283421, 695523639, 930197400, 436426206, 907110934, 10444676, 244395457, 898508769, 234959405, 717377114, 538301658, 996690838, 976943740, 661725090, 803962626, 392690082, 830207662, 810076179, 44981932, 145106536, 107421458, 235389030, 570741615, 536307332, 188318764, 771471201, 560060869, 885682019, 118949161, 268571056, 332379789, 921575298, 375749866, 552788853, 129389779, 315014306, 266610475, 623792393, 327159420, 923916393, 117972328, 659396833, 50694679, 809393269, 725715493, 931063301, 128386600, 412375755, 580676649, 86047959, 499012165, 755612462, 497032879, 268910318, 948562956, 196703808, 878050723, 182557451, 862729113, 275582196, 82546707, 862818503, 946017016, 939666058, 594428081, 41885912, 308265223, 989257085, 621957733, 446755978, 876886580, 183748796, 928176752, 994522828, 162398007, 482054430, 575800819, 648946318, 926738131, 603625199, 688519753, 637888631, 777577512, 192877410, 796236909, 729906140, 289235462, 200565492, 847253076, 355799069, 166628509, 561485192, 944833157, 467082456, 553926467, 919160394, 450658426, 32882831, 368599278, 702863283, 903142373, 951900402, 810081057, 413869064, 85669413, 170214575, 364045132, 702943074, 890273201, 796466937, 70357009, 210808018, 481432045, 430330120, 993688141, 393267495, 288217846, 870536724, 324727479, 124184545, 176594128, 443447524, 486668488, 719558782, 743866319, 307135459, 92185583, 995864490, 364040140, 693537617, 452312581, 52960127, 14263721, 48183656, 116220615, 628276249, 512617801, 293385397, 616861051, 224205768, 277661656, 161125439, 714448810, 725074678, 534150185, 911824667, 734085584, 777872326, 400159225, 258174068, 702882858, 705314089, 711402421, 633153692, 255744998, 804917840, 674239563, 919786302, 564776353, 258048099, 353370338, 108028595, 252513521, 60753366, 966908366, 149135818, 203596366, 695596570, 648269104, 243343501, 978952536, 859587398, 509299598, 142024894, 565193488, 461436418, 173831099, 179572687, 734613690, 826022599, 471208980, 943285313, 778027672, 870631531, 700972271, 177555877, 58104529, 605054825, 188545404, 657312738, 328052506, 335664465, 421144337, 636274125, 622276655, 928098605, 25153285, 528319332, 833752434, 933271129, 966297126, 44077769, 313162176, 747725461, 799489242, 578479624, 20632794, 733052468, 468398788, 49104439, 47393760, 83080788, 952995141, 421174160, 500927128, 157315837, 59644198, 475142242, 64286512, 621728474, 794862935, 812292718, 641259114, 664012645, 418071770, 769232862, 495203755, 111174859, 78970338, 524734468, 760798908, 556672508, 103018648, 757777440, 904150149, 104221615, 19233588, 544131924, 202395363, 847219234, 247924449, 903444921, 978824078, 975662504, 754116533, 519584920, 75928157, 439235950, 676318455, 485421610, 569823249, 456563004, 428872231, 489223973, 876122074, 680582875, 529324172, 422317963, 313042697, 241252902, 486189371, 114163160, 687567336, 994671689, 504690157, 490509378, 706940983, 22887807, 9027236, 715100612, 680954998, 200362202, 476363296, 399088026, 902843979, 84479730, 424824964, 152334938, 840704006, 536823390, 161034174, 294574204, 767992982, 153398975, 237896422, 418166484, 706070173, 111032206, 111427066, 367653228, 440297436, 914465369, 267785993, 501837067, 4175881, 507472192, 595857752, 644143043, 734966532, 667234368, 131583912, 186597472, 432732361, 42305554, 625283094, 221438595, 486730034, 608650030, 578336353, 989710571, 231196472, 515350409, 331985411, 745147816, 859350950, 200605123, 8313507, 630656039, 58793580, 81213804, 201642452, 195787110, 159627762, 861893721, 620608784, 454520652, 720113109, 586214538, 40012702, 673027287, 80406645, 141925567, 235733985, 348557105, 763022286, 692063640, 20076654, 200104123, 436124165, 428794145, 257678157, 759021338, 896538778, 219696428, 184523330, 72513197, 632861721, 983582510, 869824914, 519144861, 433184804, 398431138, 896336374, 499740923, 234456482, 162250786, 875602315, 640285963, 759860717, 880210095, 672429918, 372076639, 964688191, 912415921, 521243650, 342143520, 639715627, 471564545, 775772594, 695440825, 799294274, 460080096, 932091918, 279960299, 844842063, 334869712, 372776423, 682804063, 52938755, 577488256, 674794313, 906171281, 558065543, 970162325, 876307299, 80113617, 663106294, 669524167, 610823160, 518980606, 37047822, 610447500, 218922209, 45616494, 749961492, 444731968, 54787935, 531211522, 879313296, 534671607, 857505585, 481763181, 391007964, 339484736, 840068239, 654409166, 658151703, 187043333, 224936368, 887124424, 610117490, 537845416, 849292195, 16909037, 191868227, 135828026, 279948192, 325487912, 790251340, 613881617, 29701177, 562783644, 770289185, 401127517, 25814912, 741163916, 804609737, 463369021, 344866513, 123257592, 527646344, 920503892, 25772928, 824363172, 910002879, 299554431, 347550441, 342006138, 148571190, 412388806, 335719686, 544294354, 19644898, 419748589, 762601192, 35420268, 691061112, 141421322, 448653693, 216596374, 549570215, 997233575, 487500583, 918021072, 340829432, 395702284, 226387198, 936661722, 586026968, 223424282, 816231738, 304032789, 303366237, 510818777, 43954205, 357811738, 750547541, 757448632, 139613186, 721692800, 564671609, 329593789, 971874115, 431297913, 487552120, 870496436, 320813972, 519432950, 859113418, 798233654, 250214258, 990006024, 462659840, 480643609, 269491837, 230286861, 973754948, 123024485, 392876873, 314358702, 798675711, 339499335, 965564331, 766322924, 981009056, 529177707, 917311036, 78313311, 835641662, 272885490, 14812529, 890774983, 111249521, 616750970, 19400862, 409336176, 634373990, 607461872, 164475496, 451367893, 258500739, 94871162, 57310688, 595552581};

const ll mod = 998244353;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int tests;cin>>tests;
	while(tests--){
		string s;cin>>s;
		int n=sz(s);
		vi aft(n,0);
		aft[n-1]=s[n-1]=='1';
		for(int i = n-2; i >= 0; i--) aft[i]+=aft[i+1]+(s[i]=='1');
		vector<ll> dp(aft[0]+1,0);
		dp[aft[0]]=1;
		rep(i,0,n){
			vector<ll> nex(aft[i]+1,0);
			rep(iso,0,sz(dp)){
				ll v = dp[iso];
				if(v==0) continue;
				int past = aft[i]-iso;
				if(s[i]=='1'){
					if(past>0){
						nex[iso]+=((v*past%mod)*(aft[i]-iso)%mod)*invs[aft[i]]%mod;
						nex[iso]%=mod;
						if(iso>0){
							nex[iso-1]+=((v*past%mod)*iso%mod)*invs[aft[i]]%mod;
							nex[iso-1]%=mod;
						}
					}
					if(iso>0){
						nex[iso-1]+=((v*iso%mod)*(aft[i]-iso)%mod)*invs[aft[i]]%mod;
						nex[iso-1]%=mod;
						if(iso>1){
							nex[iso-2]+=((v*(iso-1)%mod)*iso%mod)*invs[aft[i]]%mod;
							nex[iso-2]%=mod;
						}
					}
				}else{
					if(past>0){
						nex[iso]+=v*past%mod;
						nex[iso]%=mod;
					}
					if(iso>0){
						nex[iso-1]+=v*iso%mod;
						nex[iso-1]%=mod;
					}
				}
			}
			dp=nex;
		}
		cout<<(dp[0]%mod)<<'\n';
	}
}