993 993
100461064 690903129 728253897 426930922 755185307 546549559 377293324 700281103 731664077 316907685 537528117 283728658 701104572 296384721 230142848 75928641 638260419 518143014 986986347 479941161 384134017 580399955 414748594 966687382 619530705 209457989 20146515 48208791 281424338 528488231 921453451 988967287 125790687 30691432 526692822 188743875 111554711 290434228 391864817 631586378 701104342 494090233 47475674 973937431 244073912 593430626 413756365 403319928 688152732 836792926 69610056 53850618 699827997 332111001 520904200 390285674 933299482 168313345 26377225 803305172 445796527 831000513 603479944 551042183 524107320 323319112 854609923 912080142 247608916 582065218 940206903 716588854 51887071 156041885 289954592 204878862 964577269 507129989 18523644 295464161 906435573 245932647 309158471 116427581 664630651 843009776 714453182 863450863 571363427 749752077 392520288 68663811 657028300 109025772 260348519 426256072 181447442 991636217 671898194 798646217 49548242 844259810 982081502 304642516 522532329 873227410 519792391 768259573 748618355 607718200 4239371 101682554 474243791 168510528 665327974 164247537 312062105 536044632 955124694 587954981 567373742 671525995 78534231 46023971 96090667 637995944 704271911 111381050 131232877 458558331 233286850 492599541 698310929 794966418 772185062 39806498 441593076 68529624 549431183 865622222 924881203 465791100 183247355 466067013 425097515 322507755 98109863 841566229 675642489 129065680 350295374 207922699 954752250 209198106 191664624 674444852 944085707 283343093 42692296 102927069 554631241 442132174 351086931 490613906 932515345 709780819 122959695 418721825 842622208 312380528 485985464 288706199 231754803 504133202 957825996 885291329 792549639 130774374 862167816 645090219 936408345 192504922 7309096 220027811 767182918 228102170 691673385 303280438 939631787 320499155 382756937 750215345 337711781 217724146 280125957 436813984 80779986 306389285 141716505 85677009 464205325 27728472 289348227 386734417 850472308 293307576 140286335 856062061 610251364 163709619 622427530 71394994 832978042 1794293 885829474 268460524 890636692 3702891 685904388 429106217 116150733 467347010 684358828 844919734 661478275 650668008 832714968 828004639 881526611 155354888 83086404 389763891 634862619 79939985 214346990 951347965 814488310 403615152 837841170 875053003 764108098 991843792 781036334 764769065 693871773 422398624 945716734 849894630 506281186 106497804 134086784 548563213 802228272 146867778 54841840 883582956 264450786 16559534 116132300 160794127 663373718 679560445 612060624 122721861 240663338 597061660 73292794 184318873 157322937 258102584 10449030 586356057 435254690 38026943 2952690 74271506 257576832 729782621 146831098 461003920 647505458 254304255 143662748 305939938 883966419 76977107 306418709 215526227 475280578 885765189 237721824 931889008 164972442 302085378 983401149 486257416 462644026 296976375 973431207 877157158 912627389 574554450 617904603 486808857 657211266 872756607 690356695 791707243 852777253 494312747 891385432 598494956 348026242 722685251 821845082 197877415 247434424 385623285 693982490 484906987 179971363 828585901 157245462 785413955 714679135 888099608 9320715 124396924 39390283 750083363 22073333 379151269 966339843 776082940 914904338 73019657 463629027 66432015 655690462 118651702 365443978 286355465 844272662 759041529 493748948 229392600 980977592 868500318 73636062 85689256 29778689 335849908 559592452 268199398 982014317 70624646 198661349 565715263 92228794 829010850 299455069 379363745 31628516 334458644 499660681 433021752 861308457 989145899 740446150 42034289 6134021 846877042 829195440 676506617 112803894 586833847 265841190 197505726 728338616 519515142 396124228 305156076 716085705 117545134 352598375 69775600 671855845 431645754 650537516 200298871 44403658 801609080 128874864 755183983 256727668 239753077 546077264 968253700 269428001 584410493 668731945 517348003 701580365 325475102 130035352 87583482 804224694 578512933 697855866 197423861 23690073 90144927 101000940 761939393 417829233 474248409 887705931 361459403 186531966 512667487 103729460 67380673 825574459 686512895 708686212 448008846 657296549 591806662 139044184 99792737 541541370 502938113 282104845 915419815 849307831 198734396 596516672 90050828 25813400 230818117 823214798 799513468 121925018 782063401 516786389 26438439 242156539 902535221 50886064 861100919 633419320 662847221 444404733 32228891 543183373 980297783 777474713 28270335 193162615 34645768 164761761 102972496 342508724 241369781 466634098 806648955 409012801 963197643 114708650 401758766 589913818 187841302 528183844 426788437 982805373 239362468 382098942 521601566 444026214 899112130 875724438 139033844 119763475 378957052 1017991 222857350 156959552 327252257 663793327 918884032 971505898 64976956 951750187 695872463 74542928 444026779 403257945 613983777 488202988 115636938 718098644 298270306 603869822 798838168 993635707 649615231 566125824 106330640 877876841 965377189 835618226 960784000 395642876 618337602 605391886 452572532 659638482 357181698 921664980 76500923 106194886 690314706 99735807 32088672 90980343 448760800 402536908 460033713 125594816 907823512 46476473 300242491 292886976 349984679 174992514 707933386 105737938 38425850 831746597 732125293 890254869 633164478 376858334 731544431 791907300 16895073 50099243 85400158 306466526 5732239 649676233 19619334 433199582 912863286 390097844 727556470 58619907 784684161 581252649 933515257 519713960 258632927 191308198 13589789 167528300 274751996 410494696 411833518 45461547 163717830 34331371 760838331 600269569 95428200 322377452 708132751 802972237 610039889 561196649 69146552 269825707 738744366 448271647 505961474 530909431 9641962 97485066 500668796 593123408 126492596 570517607 213727089 766717458 236876792 29878196 752516463 80640985 348069731 122720174 554728771 846424964 595824867 986355025 689274617 41441071 70084003 632101339 387255520 757357879 115851538 245995208 900485507 288432696 979264733 424696790 32070064 432877329 698500847 34110209 995452019 875658462 339716471 330126471 92277531 900027132 412856033 227112164 13532467 360679688 287787995 418980054 485776521 394631903 610277200 795063129 14042409 99904158 127498351 265890219 413168482 393617057 957180068 64322376 76058047 690840455 297758109 391393774 242266382 172557868 402355526 454800793 561194588 939679661 699623884 114775687 65840373 805810535 62068124 185157428 293508199 746262775 664437091 406585438 849166975 871184442 72408591 420217601 379364682 104113485 395717836 330891355 134897941 40401037 704424712 975940073 945119852 215503511 117074542 603091815 633093149 931151432 544154349 171933394 989537589 671256253 776843441 736972904 483671297 517555028 49977895 863972518 236404493 418459560 753416189 45363784 141606695 162086295 110167327 116678731 134300508 645203774 887592634 934579693 196699641 583680762 928083004 88126635 299279242 43556712 155129680 19487297 701256925 447178085 841812965 440171692 629736703 104006671 141610536 303898154 137411389 216362689 651984516 223319352 339124516 410790169 272640936 442658962 859736704 448505076 736600192 696659254 70687583 51727984 731071033 889102432 95312910 57009128 51070529 360742285 487726361 208552954 982421060 600604284 943529807 901674371 718279727 219375911 125851067 566385569 217004591 922895309 228767147 935819183 586003634 222894315 98145451 756774731 792477795 558134589 500263562 616313427 79458866 267601345 537617747 357239010 791585097 301901747 327313236 346520919 791237399 901065361 154684186 743979597 874413384 453590040 3970929 328160418 743986633 469471811 974620007 797076852 720875719 553759058 549346889 561862686 127499952 117656000 10304932 490031679 735973424 499167306 854828356 846744498 856757300 936717806 31764792 595224214 344566762 280124904 536890827 780670790 424179390 816406966 944277387 536036961 401440349 685722901 379352388 907705539 489332916 150090240 525233669 829567880 76205041 156284087 448406297 275595279 141905536 719784373 867145742 496663027 673527054 78068151 125203120 25703699 638993032 663836091 197351694 651785611 107931676 783697662 220817779 245593527 815099190 919078140 58212461 913081398 281417603 109477747 566249672 378895332 377201393 516124255 569333139 844829661 705842603 837748733 717520921 963118976 904619552 136721611 870407144 105090665 175537917 697148294 102930637 334391412 848983341 408783658 531052245 560476096 357111775 919931125 875669580 774743721 92174463 463906403 288196032 613764044 84842682 979518258 61500414 922766342 978155134 527335774 603690514 876578931 327835127 705529636 558528331 805535858 133524882 475614979 664377652 53965727 664888828 21202357 137266587 806196695 57258531 278740538 529573004 502364983 957571891 648554444 998152790 254288924 120673433 263137259 130803588 819219747 87213058 108155473 509163748 572871465 862527836 143617790 977364867 810721099 512450771 571872301 762971309 688751334 104151764 696390235 745567216 376841111 859593741 305090630 724917530 179836219 686635882 233730794 689456693 510939631 184711192 76977029 85039505 12749328 323511684 571630996 935356345 415386683 858796892 750282450 258429819 362763597 600784268 324699455 334579172 680940131 535318081 691604246 827621953 646383834 534383080 906260180 758264350 402237007 35084591 508509495 657491785 931215519 455096578 528385340 655057359 472334823 756445326 164862495 780356093 936161412 271219520 349149533 493462623 730817812 117608134 718144692 101005252 325995634 615872780 177891873 319523639 668207036 114188863 24552928 101604869 859535439 994650829 917666927 199077309 868640712 909277025 591351946 136728618 651567621 933138154 975080750 922950490 420103457 95722645 19653018 580874650 910496122
524708724 753406383 89809847 933039319 33380603 49120638 17402941 764246256 109200058 364780542 280177781 45786493 508051124 831957702 812268163 726026805 188246832 724912042 884513997 62357259 726403250 203982528 372655096 889942069 880895487 403977308 763467496 152921128 122698780 587695379 95768259 909792665 789139534 529152955 408445678 12327805 466892314 519785320 419373838 258633481 850665286 194222448 793606407 334452146 864238038 946294119 411832574 113872172 486106127 49838370 933931353 485234542 608264821 222386871 329550525 767170731 9206224 155940474 32218127 682124121 622801186 817777921 616913523 919543853 659140529 686755616 69375311 109537308 872564995 758821356 53967431 533678683 273194715 78346939 772102465 508628575 657475392 38707489 51123298 834295261 466765430 323515635 792300559 734937801 760693506 354913863 59484908 307655002 190745513 529481074 527530462 53128195 5942129 371655943 718168588 144404859 436556701 212487645 5980377 989863093 699891124 457665801 296852458 354511591 678731642 3492831 591367461 480929158 484804852 800667636 105743535 504843846 579684455 237380894 687872237 576531230 190927448 292902257 938094211 423844418 432620428 215970626 330237015 31095846 279163145 88315687 922653069 201988993 423593490 797851636 741347723 270885702 103395886 455108287 228828662 486294699 221801249 808548060 332168370 868967205 353136880 70996960 656493029 38262377 126937568 630223777 143831540 922660972 495811703 22690867 193596291 733581667 36741496 54329835 963588472 233607618 891891178 658932063 163650296 4942400 922128657 134186340 503859047 12767696 237637233 442651405 225597547 841510312 499346897 37400498 517624808 437872446 859545910 541001445 79171588 52000325 115369699 193415805 93560100 243423923 829838686 88233102 201856493 1865404 305150317 883381102 508319043 573244119 146167828 774974897 111894603 318329272 86589080 60314156 669084780 685605971 699492990 406470133 515442505 37837279 518410123 528905312 376151239 100192719 10909636 49700099 749415180 458769369 142055279 913394098 60177533 746433522 494951695 475802242 190994367 141341775 687241067 394561481 340228534 962749797 196485511 422815771 848054664 907312105 366631080 562606670 317955737 201948368 643455571 890583414 474097807 135372622 580934221 121917672 135899983 473672409 109400732 435751482 895507197 23732007 214003075 186464576 271999999 901819435 645806985 876769808 536842490 917009435 190088050 279144190 834887378 872090476 492336707 146277023 600544941 536955091 916616001 37369801 826042352 327055685 224082929 881362832 329781311 456860662 136477209 655325513 25088896 470826589 604347836 390756490 598280152 659403309 780672801 146482471 957245355 474678621 731798732 130056502 320036766 946678304 263216514 523599115 73193624 361461484 188181064 79279419 744968636 972453494 38618211 618622620 569209968 973344691 890933080 922565187 458325592 209751000 339498733 820467587 272066906 856850521 650341670 753406451 380853659 835978477 144073287 484852072 491615103 525173639 54902999 779582965 916475308 142896222 61020571 819166705 283332358 48541669 733511062 618227185 509641907 978871506 182097422 997605577 628127256 758658074 798334601 693134 940333786 11722482 492007626 308748182 399986397 249324751 549292760 215105653 471478343 613521766 458696951 40494081 103392636 523466923 622095788 959073358 701794082 418211029 33058236 4833201 136037918 845780567 135368237 749360832 122749844 321273319 353964098 718304847 526012138 595478138 248361858 806954355 151605701 480388421 895979953 106506114 637032457 708313533 603275476 762291216 98437596 609712023 174101808 357132531 20828578 529491656 30451530 65030207 756694529 242752388 481338343 624388169 417142750 370889794 843212301 164117415 107510366 912436149 3874559 914444589 343762661 101418196 542990916 180335089 467875608 675878610 705908128 52596551 64135902 851528485 114200344 938752708 637563994 589580674 444616433 421237310 472140785 13508574 434397105 231243209 604525642 676748397 412771355 811752379 797250120 536581030 159019318 701384872 544755984 369842236 433739333 129945445 456949256 189157158 131779791 812206856 117394133 215904663 371284632 543522021 56899932 443968261 236690854 583378065 316911553 465839397 572347964 924212706 980579946 35614700 135974112 149051116 325956091 337714063 424431704 110748165 357192538 107787395 237314472 199985601 662704556 606170492 945436181 56244470 93953621 623726449 21606180 541359287 328444667 12883349 194085530 712908380 138509699 398344543 420042876 535055223 364796433 3519618 859272464 704782815 626880267 360874228 289576665 509890985 296785685 138229994 523262622 212812584 472671509 702286041 527590243 351291124 984574000 239034230 546203245 827131359 630346187 22903221 514544449 206745856 329212298 684526285 328836004 252290988 94928723 332303409 818945436 485188470 9600330 967816599 459882348 601901109 786776021 606966005 344828315 5134334 745166745 696073342 158756589 251702565 371937658 380075688 184306279 994222143 443614878 328497704 832787278 986526754 147090537 446587890 60054311 499607010 642947714 143479613 77413816 852975828 744178379 10909053 882727172 419985550 774311788 976245350 971153746 159455461 688550600 538986990 456155942 768570860 46964613 923759179 632955205 771404282 430790791 758802416 656955060 820150180 710561524 344723347 959844536 373187518 167207985 512557609 960177366 111412573 202901474 7422182 742024404 353850838 19574765 494225729 618560694 883498175 739861623 89033966 252579008 511333869 707872740 69550561 73052025 196637556 430266074 586384464 100285349 463223721 729899582 603694257 952578122 667832097 718631732 347840951 229351083 678649010 919080226 133425752 369340495 28599665 679840684 336287177 624512761 593771185 149434040 252481407 623225520 862032393 281951339 776213806 48683448 53809486 925574953 111270093 349910678 275607700 123485593 301562511 10239503 313466928 792481949 679684331 520635177 228737720 991108957 955398292 943151911 889151744 630892347 779158144 589519760 89826845 6983135 600335332 26887720 264141157 804425004 198158389 903894260 899377772 628798792 98012968 218992185 920803080 864842392 134275250 588937340 696983885 502291904 129455879 517441154 13636496 699370406 899484318 663102289 489173095 756243822 932623402 255936044 548616358 530862206 510081185 922789530 691694947 707546747 859598136 103707231 203783154 917798217 96484708 909928320 982004200 8621838 671880922 212866626 656235291 606376495 51212175 91977003 299588511 794837328 687710648 923702526 402489290 826233687 28289482 681988290 140542512 94770537 44514937 617130426 495930790 994855146 91127995 523642221 967862594 862331264 584270790 304365471 251552344 865222415 712590093 943434838 801250429 797253053 410627654 479897557 98830215 526009839 627145062 13587618 922243979 229536329 741292706 383679875 171462364 401387953 683582063 731818364 874184721 677423436 203784577 181096402 717335551 103507071 140075727 988955658 609766842 994554605 834483084 930904041 98885783 875112062 959022382 11291508 195906091 222844757 931669867 27028209 87574092 851993048 627203638 803163363 256354575 181959340 55528389 494185489 159345352 800567477 778008205 114535807 529085964 437354777 28012866 250039410 756849584 527585084 716923099 178353263 308910282 37434564 227750027 990331707 437089455 323103126 305944009 858089180 857473778 661131222 147752008 303783829 461256555 959994858 964001278 762811373 140742700 880488055 542932768 262293672 205091724 104408161 76795939 132149451 943937567 750462670 577264060 273255323 453262523 200306979 291799776 836196509 903951476 661803780 676750532 79526294 105084064 584864343 960902876 343254668 624775891 340494144 824003807 464656835 763896546 78265894 255151296 46958528 119361762 700725675 821119157 137595208 999974697 983709879 197394739 234119008 810176588 992415853 321733359 257916749 645495071 497505331 777417438 822174356 233942199 948265389 946581557 205693179 89142890 741293761 246643305 916345990 336569292 488987539 577973038 959139705 981669042 435122314 413299835 957646427 326001458 723603017 802635395 126967792 235496864 224272309 200032700 427518782 966658193 391464948 174034140 800868744 24787675 794783339 86225622 733066325 990057363 125135551 654921951 818161000 933252108 20609236 370582126 879240904 684356574 334960336 469855031 941692089 806043867 406200087 203511087 796752832 452033306 472206927 252742282 974871202 897865967 496764253 849839550 161742949 104819440 175860581 899230593 909152844 430192113 320424397 688550598 575946718 11381511 715632186 714319555 218971359 476201352 93381264 803012845 534079316 359476489 401630453 117164793 714421122 75908957 219815373 243496667 866417646 41377947 27304382 936471242 540961629 531133720 29534637 616846649 738865877 210933607 721304255 262485215 884810649 700465248 302810200 644358319 947824432 136540437 653005853 889871327 562649438 556878557 745540597 456548836 35222568 348202317 769830403 137646707 579171795 482570296 251702444 593255297 321067749 227759542 764695191 471402819 274567713 121442329 903186599 561216557 313347214 828986872 108530177 176378614 177301871 526978599 117478411 718778513 855741003 909585852 460540010 946772532 298622182 14138891 647788803 96221525 832261446 342036650 667646970 738750375 837952942 12366701 582562740 723014944 757679268 555262569 60015320 917797877 477796590 507876339 493519945 448111770 334646672 945186978 8370989 258556870 941053391 748620104 845359848 529490028 601574192 316889340 366419744 650087363 581414776 391870226 880761786 634677054 79590060 179801888 618363610 243285651 792806161 61735162 735679718 692872631 35744557 862611125 994130050 893138655 305009604 234127015 28785300 895047296 957322203 103520100 206528065 274149711 478172343