1785
996530815 996530815 996530815 749484158 568315537 755634421 755634421 914061898 309251463 309251463 81823252 81823252 81823252 81823252 668669361 48373705 48373705 54106500 514254268 664144785 389515600 197114062 983168840 983168840 419201992 376712071 20758127 198411035 198411035 464688233 403919023 16949125 960417661 960417661 997995020 997995020 212616947 306057280 385066622 385066622 357629992 287531045 287531045 287531045 673087769 550931143 550931143 550931143 383969396 849028427 849028427 849028427 311442169 685107354 685107354 685107354 278350598 197385438 583706165 142658886 142658886 51769278 51769278 305206876 305206876 305206876 921746556 921746556 921746556 586314749 586314749 221443322 184293536 398828890 398828890 398828890 199332981 57851343 772310349 772310349 784005775 930618876 767137492 971666677 419045086 918358356 59025585 59025585 59025585 856065201 683637478 693763580 886650385 886650385 718393688 29377563 29377563 201732435 104305074 929713287 955587362 743856741 346773772 777780828 491576030 249636376 249614388 819620343 819620343 367421841 367421841 529270273 404968334 389475638 888665687 538938921 759370517 850212931 850803967 850803967 697140233 821500949 381472281 17684830 17684830 846751814 846751814 965709598 965709598 996772089 423738717 65524517 535897506 406855649 406855649 406855649 406855649 305948569 940962653 924130346 812057991 812057991 704111619 823772922 551270033 652642466 652642466 652642466 652642466 652642466 886314891 886314891 592442739 592442739 146257397 146257397 146257397 346034377 453229139 941843276 744771034 344729750 71843611 71843611 882093056 409890512 954908832 403942476 403942476 403942476 241369248 241369248 156710700 156710700 156710700 790475001 860587968 20584253 855202521 377720728 416291782 416291782 416291782 533586931 154028887 154028887 154028887 438248265 586683 586683 342177167 342177167 971912264 697739324 697739324 697739324 456747829 391898834 717036407 708163937 822982266 923022057 883043745 883043745 22185131 22185131 443194728 808069565 502501756 648980021 648980021 647269153 412263534 412263534 602802340 602802340 434125479 434125479 434125479 203268367 789187169 320113718 320113718 19320443 19320443 733192186 263370875 756768460 88490381 536186969 536186969 822103805 936147572 811928935 406923971 784506178 841159006 381531235 217482605 490319317 332706260 332706260 994288186 994288186 740653339 740653339 740653339 974871214 175089183 343707953 116805028 105362887 105362887 850403340 198485914 198485914 379384715 706298778 706298778 197278915 197278915 197278915 471512970 471512970 471512970 792308492 792308492 792308492 792308492 684678664 722628197 486149711 486149711 486149711 413671390 413671390 297608746 485491365 485491365 611570103 706203494 706203494 985509745 985509745 985509745 89624288 678610174 678610174 146561751 808002709 242421771 242421771 416275420 225868422 225868422 625344513 625344513 428561033 632475244 632475244 632475244 579947046 579947046 369889482 685573246 618852554 618852554 250808185 814262503 248884214 309596633 309596633 309596633 309596633 309596633 740130129 740130129 740130129 322245321 322245321 520288831 520288831 379794326 654027626 654027626 654027626 654027626 654027626 439243634 587017531 900941587 712948812 763602395 930748301 584466840 446328406 462230707 462230707 983963121 534080275 287287507 581412003 822322680 376247499 712505902 648864474 304573377 862312690 862312690 862312690 862312690 340677589 414375257 300028424 903882668 903882668 903882668 903882668 436041066 86144086 86144086 86144086 607109396 427394661 240720116 534294152 534294152 534294152 745620052 745620052 534029496 819316570 477016704 410226515 686565408 361332593 361332593 618059545 618059545 367341228 367341228 367341228 367341228 367341228 729827946 686175131 134490685 134490685 106997413 712959715 734717784 662606201 446281895 904330060 360306119 543362704 543362704 437847142 437847142 963222920 462792849 462792849 462792849 518307012 518307012 920924548 516855559 516855559 516855559 646667447 646667447 742801031 541178322 541178322 541178322 725572722 238523529 199377810 955722546 289745579 72588020 72588020 484706251 484706251 484706251 60452764 60452764 60452764 4033048 208961998 324443030 589037452 532008800 127447119 54458758 848641229 214950574 214950574 452392116 452392116 23436736 777431498 794689783 794689783 794689783 326488202 524489601 287924018 287924018 25540876 474437009 538399616 59508314 59508314 59508314 59508314 405193866 652843031 987871935 987871935 987871935 200782597 200782597 132706624 242644931 345742740 519297176 519297176 519297176 519297176 240332327 240332327 890339843 890339843 890339843 890339843 890339843 122071521 921480964 151297829 732374809 176037007 185869344 27438148 172704883 208630161 495221594 495221594 495221594 604922766 635628464 931247572 577072750 887848638 148567980 790194203 736963619 673807699 673807699 188732555 188732555 356058929 611783096 307693047 307693047 307693047 307693047 48836138 8777185 8777185 417623699 223400904 223400904 223400904 42053480 958402869 863334012 863334012 863334012 863334012 863334012 946302471 523902563 928919510 771081597 473516640 883330493 897416061 463160095 463160095 463160095 644409805 308167689 308167689 883773156 811364904 953594689 953594689 953594689 953594689 890648377 832179455 77871122 520060393 871582175 965992745 965992745 590760089 443021772 676860169 676860169 617365506 648446848 648446848 648446848 648446848 535901329 331646240 331646240 331646240 331646240 785215089 805445660 805445660 236243450 448762402 155077441 924458635 887959978 290494214 290494214 290494214 553847633 542646691 324800725 324800725 949761689 949761689 983242143 138741733 138741733 138741733 401904216 764169640 693347208 693347208 693347208 217420792 217420792 217420792 512511022 197767990 197767990 197767990 675688374 210852431 210852431 210852431 210852431 572863389 829158645 20320575 928255653 241078657 241078657 801703330 875382431 142276708 484198131 119943862 949387083 717282390 442348917 442348917 442348917 96538300 482843758 154114143 212399824 796824678 462723562 26924623 26924623 26924623 406198648 197077575 197077575 758012202 758012202 758012202 517207266 3449686 460942177 389093671 839176821 839176821 839176821 839176821 924230996 61036311 61036311 813500526 813500526 189828349 375787867 124056705 124056705 829238542 58186453 623446606 224498254 224498254 124028203 630617485 904582492 906955667 226544604 245729182 128756983 128756983 128756983 128756983 762375697 762375697 161545950 161545950 421008401 492563530 954231146 647318700 647318700 560481504 661903210 549919915 342568578 342568578 108019273 108019273 713794848 713794848 644000494 194035794 194035794 914883717 914883717 914883717 838302638 838302638 479286605 38395251 417988667 417988667 417988667 444195880 148866010 148866010 637115696 637115696 721476629 92597710 118381089 118381089 530672023 530672023 936814671 936814671 913802052 446961109 898900861 898900861 225725529 225725529 426811582 426811582 290644084 477478182 578209599 828631945 897123980 897123980 305595432 193406848 325919979 325919979 287001121 931173691 183436924 395139006 453914577 594882361 383296099 975985053 573590316 701363365 374131070 374131070 374131070 818931675 621362969 621362969 704295673 43770771 458617815 636307936 743531779 743531779 743531779 203393122 46635471 46635471 46635471 347155866 347155866 254442447 331466201 202225917 202225917 305190230 122399682 699773791 967964483 199422189 312600988 695134570 695134570 756494076 537539604 804165659 376930898 376930898 376930898 888859684 330352151 719233323 719233323 62172793 62172793 661932053 661932053 269869341 506963078 651448603 651448603 320936585 320936585 982097312 982097312 982097312 921184673 512743327 417182857 334615803 334615803 334615803 843621212 843621212 887771771 15000236 15000236 626253170 626253170 626253170 833510216 521436915 590759096 8112536 414046104 297114298 297114298 912774769 128288240 385013958 385013958 179101010 179101010 179101010 42727680 783174131 374939150 727127825 471220437 44679354 44679354 972290872 871681435 871681435 72440493 72440493 72440493 13975065 676821205 607983192 631914244 32666977 601189577 21214663 522244853 522244853 451690250 911489678 911489678 678540054 577883782 476798883 182783923 337258911 805012807 527763794 196756384 222305053 222305053 222305053 429792532 842245240 341821057 717923760 737559737 737559737 755533818 755533818 368824502 368824502 317427830 317427830 317427830 317427830 537458149 537458149 90441941 751425277 751425277 187626432 187626432 282848354 891885229 232633876 588529687 588529687 435720595 15574166 231349125 631273111 45398517 45398517 343293602 304623221 677773466 823356294 823356294 879335343 520086105 738356185 514581877 290868142 290868142 290868142 290868142 273971908 92808327 92808327 92808327 92808327 92808327 371042744 330706847 330706847 330706847 330706847 330706847 440639533 98433458 315413865 315413865 315413865 506944573 489875311 778558527 121215885 575230049 575230049 900132865 195812889 751661741 751661741 751661741 209154794 314362699 416792393 371529548 371529548 371529548 218937641 218937641 218937641 218937641 218937641 557021927 343670014 343670014 663758045 595238399 595238399 937806611 146329574 997340374 997340374 862822966 862822966 406079258 880417570 59077627 87919818 87919818 220324098 930540612 922548987 922548987 922548987 92785489 92785489 161510151 161510151 632100745 313230826 544282855 544282855 544282855 544282855 275866360 275866360 815838731 815838731 373277587 290503494 901063560 901063560 489659974 489659974 503470627 503470627 503470627 916078669 739897268 192871089 942100925 942100925 161920646 161920646 356520675 704712498 963512858 963512858 963512858 563343614 922862541 173292323 788174998 320313717 320313717 114691397 114691397 798716427 798716427 190823466 190823466 459952496 459952496 981518234 981518234 122390608 752949727 752949727 662452933 484533232 484533232 484533232 366909648 230964951 230964951 230964951 727414460 777866893 9441020 9441020 843144094 843144094 843144094 843144094 737800630 467246975 492285857 32733685 32733685 958613918 958613918 910600994 998236720 40894005 280219301 280219301 280219301 219759783 219759783 380571782 96929884 96929884 433026718 433026718 684261708 684261708 579331798 579331798 3776622 3776622 3776622 239623299 636660958 636660958 799325121 799325121 799325121 799325121 866039469 130254855 870509640 221566152 221566152 221566152 221566152 221566152 732058486 720160217 720160217 958572628 958572628 381805734 381805734 47946248 47946248 233016301 233016301 906778791 115969039 115969039 115969039 146661189 818508426 372321413 372321413 56401304 344202999 344202999 98052488 98052488 98052488 852688673 608863191 160577427 749873484 749873484 911419706 911419706 739107778 739107778 219491097 219491097 219491097 67682049 161799329 392019014 392019014 361708214 258809290 90657821 837375476 892509699 511072120 175581681 3925964 686870404 686870404 708074811 530164834 530164834 530164834 829437988 89180451 731591254 974578877 672794895 672794895 932924167 22692015 829315921 493992615 494570617 955256826 955256826 497433494 495087970 495087970 495087970 37502101 626332111 626332111 739703766 778759493 482708088 482708088 482708088 482708088 470308001 470308001 794626431 794626431 752177750 813062079 813062079 693976163 186870862 621544747 316140500 146983317 167594440 167594440 986302780 996799645 930437032 566184582 829345307 23652652 23652652 50597711 50597711 66345732 855284276 201775687 201775687 201775687 483110806 678908607 678908607 293422005 293422005 132682086 368752483 368752483 849013568 711892654 470201655 470201655 470201655 752281850 564445005 564445005 22390456 427258115 427258115 736225631 736225631 736225631 515710131 515710131 276562721 490603978 677517281 677517281 762497085 100949672 100949672 536904431 536904431 536904431 536904431 536904431 897716129 881321795 881321795 203016300 203016300 246186277 246186277 716551310 926129162 926129162 760124653 644898649 135124309 218015193 218015193 744603467 744603467 968939129 165499270 165499270 275115728 908329101 458070198 430617654 18384078 985546577 412052698 412052698 399553357 741918165 681044392 843226972 885922983 885922983 153082416 644025990 854908261 26793012 183455930 827876457 827876457 122460939 734005857 532810432 306601142 87785477 87785477 191473284 298824636 215689837 215689837 215689837 740174263 730288479 557786443 557786443 814703506 814703506 153628590 195217200 195217200 111253082 111253082 111253082 111253082 720018304 915995699 980274843 136000615 136000615 136000615 136000615 242764202 606563613 606563613 168655217 168655217 886063629 520737560 441861365 972421246 522055277 51040794 254021834 607050321 524337261 149508058 990124596 990124596 962512952 259737908 259737908 259737908 229402224 116829304 116829304 947068103 363641314 49289984 49289984 272668050 414254016 414254016 99512834 601468783 198754496 198754496 887788770 539376867 368148383 679041884 908755473 195373723 195373723 934122602 934122602 555972968 555972968 663463235 413797991 413797991 210799335 61640224 253354107 349499492 349499492 383666412 662164002 245683680 245683680 809518540 809518540 544377622 544377622 286515083 652027449 652027449 652027449 652027449 652027449 912881109 244756042 237265863 237265863 626425550 522135102 749181595 407434257 357319405 357319405 879001543 289062961 393891181 527488083 527488083 1531515 1531515 1531515 1531515 944761660 744079185 261113316 261113316 256835937 402713726 402713726 402713726 402713726 228692558 607093502 160975310 622164304 882678394 150019153 455770411 455770411 29884378 618588961 618588961 618588961 682805693 259562609 259562609 259562609 508544178 508544178 272134916 466977516 234416690 991225821 287593135 611748802 512190548 158885166 736472859 736472859 509652433 945385103 393290737 830250044 830250044 658259126 50187304 794638285 276716741 563599760 563599760 606948008 185815041 185815041 185815041 185815041 7941611 7941611 890986297 308047551 30011820 399110561 399110561 399110561 354008034 162862634 965798041 965798041 965798041 965798041 156652999 156652999 156652999 936789450 56391542 566724199 566724199 2805227 774873451 657227129 233218085 445210066 763087803 763087803 469136403 729731261 408505076 662739280 662739280 541779337 390991763 390991763 316614384 316614384 36141881 587904411 78092981 991133610 852365653 852365653 532009791 791187910 791187910 429054393 429054393 429054393 429054393 429054393 313331560 511072992 379874960 892680142 934418782 934418782 934418782 753411525 150991126 551175427 828770836 427991969 427991969 947571222 947571222 960237219 503416647 503416647 594086313 212988160 212988160 391792825 391792825 838233483 838233483 838233483 838233483 838233483 640842518 189223129 325510029 325510029 10675037 10675037 905941229 832862771 261689960 901922189 718999944 718999944 876456771 876456771 36816443 36816443 120726789 83244236 518738530 106041257 772816521 806225426 978991985 294613987 726008562 726008562 883637465 883637465 561740330 92734528 92734528 92734528 92734528 487114539 487114539 487114539 621955860 297631184 973680777 845419988 845419988 54454788 478358471 297901228 297901228 297901228 892833535 892833535 556533389 949568392 79603070 740716539 501935038 501935038 501935038 884930618 488513257 971493698 19657195 174995374 222787425 470078805 799623632 799623632 623770760 291080641 455119225 455119225 455119225 951250051 285787826 264956800 425478557 425478557 941815809 148870489 1011707 721550601 973046914 489061495 662719451 662719451 515102501 515102501 515102501 352092178 399250452 401364437 914452411 689530993 406332285 406332285 908204585 793569251 852945717 852945717 369252385 837332372 383548958 383548958 383548958 803955799 619879275 606025325 884424594 791656523 400402650 400402650 360718066 360718066 360718066 360718066 843878530 408142384 292652397 292652397 292652397 786421577 791259048 791259048 221611699 38052861 279314666 134712868 134712868 62006190 521707748 905479820 830138134 289162919 512834880 512834880 512834880 512834880 999703117 918679844 79942906 608174764 431416285 774713732 788644033 788644033 788644033 818220695 44585205 710452513 710452513 710452513 710452513 229727686 28718622 978470537 978470537 148781942 833982692 191441077 663690686 95520086 609075092 734347414 489469976 751691172 95686015 359107840 359107840 950359500 950359500 632581199 665153851 665153851 259134007 259134007 259134007 259134007 77886166 77886166 872722455 872722455 736559259 629062547 202383326 202383326 552212608 61204691 61204691 451404575 451404575 451404575 591228012 591228012 702623400 900849881 900849881 897587527 934926431 934926431 497115734 746362323 238491104 222866781 596470780 191556366 268870836 268870836 268870836 62140801 62140801 987265828 936925471 936925471 70434085 70434085 210452012 210452012 349258656 932185016 526961638 526961638 836574825 502249351 866728292 866728292 866728292 751678031 422133978 564402970 334677576 549654247 549654247 644908033 644908033 476448755 476448755 98849097 98849097 266416322 772522053 522443399 280960257 280960257 607262323 857933904 857933904 472179937 472179937 108439702 490204480 490204480 523929149 315235188 635898672 914676491 814376980 814376980 150181077 762254251 783442066 536518418 233260323 233260323 421507237 534499908 534499908 650024004 650024004 650024004 169563301 169563301 169563301 725722435 116506923 38165341 38165341 73866020 73866020 752575872 487129465 939740001