709 677
195669607 164222111 622261782 773237464 8661137 589123682 51926837 466711 87443926 519502372 638690512 514612740 580496605 867572558 687967675 365752982 357611407 25643726 470010742 807667183 260946618 901501615 381231690 877964890 89699502 662020236 818303685 756068036 131607035 769734298 622734271 416371448 318430520 532116697 979591763 703284863 30920454 951410377 662651244 501294583 236510686 938936445 287996398 746003520 910560435 590684672 208640179 448248946 491206488 99439450 118469103 277795039 734142826 85507845 617386518 103476229 609867258 484202077 684125654 990490468 350740361 877014146 484464534 423530314 47143124 373290181 722033189 251077596 278234196 598597483 378783115 477485210 960482750 765356629 616108662 824609928 621386289 965200872 405949487 922916740 767715918 623204939 341777284 678026081 155883842 223451357 984979283 208070345 618819500 961945962 338283495 486449367 177529488 615886034 949984988 745879023 50312393 651127154 876930477 24069700 873418612 615668152 239390698 563707963 757106974 916787882 329676737 203437460 394786480 382596818 687490514 460379954 472042176 671900964 72908674 53729483 432269924 160003682 170909563 581507215 563019007 392389391 325374185 254046875 586553435 47249523 855402724 506887573 80360017 810586555 875745760 467764748 640390254 663191733 107082498 322863640 958112060 811552568 334313318 856039518 875477826 111453609 392643227 898218508 773645517 124725143 172877714 50669409 298468000 643811214 56465426 394575451 129440185 889877259 65467431 700578059 734988243 46859944 25978663 834003067 615471464 355897281 127241528 733865045 436931218 624935314 256471401 514671850 588458046 665701431 607492483 939144046 572366076 897505874 861940016 430400039 290470706 90308668 743310571 661067695 889225938 167070347 792831126 567768512 101327409 977842274 609404343 722879617 503606597 181878099 122461607 964782444 675433166 693172184 401226099 304494433 130480411 971383635 339296500 709457307 849168505 73348427 521868504 26391737 366607699 509360221 764949149 116412342 27019843 933208794 992095500 335980516 903751471 267004473 269950354 414687603 933487129 463638246 360862565 50629814 336410213 5257579 265454373 913355337 426813264 193743200 928520140 89107098 394263885 689161743 159986967 15761992 383611232 30617717 319674581 534368552 361656062 73539350 688512985 655329190 677084582 381604516 402201685 507720006 416563227 532599716 683790635 627696702 164000486 963417802 473290427 828241029 680338032 49966042 698923635 609720301 623361820 630406509 679607406 653948967 365187015 45091160 752420872 717486601 427155775 740802584 449318683 681700102 987625430 301677701 974095711 378244702 500627513 791441496 784048943 625126442 177794682 530845352 739586049 142746014 488676249 502153287 728381393 578769271 978647408 935348316 510700935 75937350 850503532 906758022 783982244 433688783 828009489 706084307 90164709 270782797 424542443 951771242 430076156 565945908 482243670 247781446 488058768 576466176 192523585 212196902 188827869 982023739 110059152 908326658 974275670 519957606 871226115 844785859 356014088 558286669 431240757 224424865 690649704 467736895 274618017 745521641 22576897 835379056 960908680 684054371 583143462 740809011 780614079 135243899 315390703 345841474 906896511 455967274 922141831 703853594 707985381 945019581 193185128 906116659 572102018 240237956 69989567 508257502 875045421 583181236 158565977 897034057 319485412 912198219 35285861 619768226 868699427 596153745 701405599 47999755 739948161 77308603 685742018 643106381 148251350 425070987 334988248 787128592 384812478 313272100 675265006 960962968 378417807 857856572 962272031 307342803 854079160 558445197 772081295 193206799 227975531 412496016 275825444 643560782 299437954 568835594 147077282 679636865 213983431 122805746 494153196 386768183 328074023 806779699 574256037 133657572 554666766 954944023 845526958 229629653 598415939 227013654 754237053 128679886 284106261 211484462 809051838 815067564 864993768 185301077 431362729 255697788 674122987 19584176 94622455 827473239 785006639 380798076 110842730 79009214 436275417 101734575 109365451 587142002 376851128 314891434 948206668 184904933 787563274 743544329 711824097 2442677 37375084 111233499 223029875 152543232 616133667 849267003 530092034 469044060 372569081 192245293 54066857 759562397 155270749 233549019 780998189 442898251 917083900 918745886 875016154 227967087 428511770 366522921 399501723 523919595 322629091 709752805 695582300 998334359 390869735 764512447 299322357 18386631 388800275 655860688 823823314 773430580 505067217 365065625 524304577 863971085 872216691 129503050 251158699 128322279 898017479 309495203 672203489 68559457 375430529 536124570 762282593 310291270 639024935 89948863 731229346 198378150 369195591 803632521 15869382 363158226 742305969 613143489 364612004 804844883 29272981 156246837 695112376 116206035 415249808 279913513 903623495 693581688 314829071 196184076 172431397 872104508 332837844 812186252 250548656 651606376 2804541 237921695 769348124 749843507 178835217 804030531 779742269 528282677 69295813 301862098 880942751 519436849 345901660 879660091 108678009 684881137 583647780 938656390 391204778 565771330 654339377 457905706 868934739 247630034 632146845 556726455 854985244 205311685 757828192 140233386 84680475 242008296 57293702 716037632 327500999 380622771 695211619 907180875 644786450 58871575 958184305 139446150 860089801 211048931 412522337 313355684 71644960 291783455 170027734 356225380 545661683 16181012 153394936 71433319 344791416 684727931 793065517 11407103 462178084 836333066 57779389 890281350 244657688 710962780 723563163 504677235 640005532 975796569 597018608 716356433 845969127 305137973 605590508 212021539 295804815 605705879 853028178 734302396 44742793 71699749 943611494 509182594 735528194 800882644 436965074 250332717 137738267 337652310 603993001 744502921 190285223 325457153 555743797 826108114 30723364 894597539 617433548 64160799 619329928 659441724 69550489 63147806 218574021 274468109 398921938 298876854 685454704 716447698 678833633 417681473 428778187 990615975 476836711 406315995 484249338 127098195 507556045 905357690 990779374 363050668 572437977 670709163 145110334 816488239 558149894 229426019 623436049 546146444 448629226 914034235 772098953 75060939 288277628 549724219 661134871 387078122 770827910 915408285 235763604 360181302 114652378 891496112 392255434 614251380 196745807 323683586 463893595 395432188 301384992 955934297 281973884 704647120 871060697 562745646 309857942 94739798 802706891 967492211 16458258 934123085 149554384 924914637 902106764 141572036 289335200 966678448 277389649 773539453 39052249 472128709 237753703 631567564 956672073 229401956 295551717 831310889 640909181 324812311 345712318 731789399 535888598 692024567 521476770 175173771 763878353 930627804 702477221 550116859 110593169 782543820 423960486 972092455 632001440 747387482 790309181 394075534 212152725 349677476 636803514 408994059 855503105
822872373 137770941 457746273 347898764 94368543 222348790 81301098 248458811 75930249 147540121 417321223 290586784 301947042 663028675 767852293 10477530 16008086 597581977 141068527 80981697 877785405 797242112 178960949 512606575 993303968 816263022 261282452 678963014 903628850 872582148 802859898 586988202 657664857 388076310 302369563 81610266 73756360 847954773 651662184 856963666 945666176 257553145 6303040 972719599 787631799 559809547 279572826 935221262 128745456 21957461 239259576 202751915 92110956 147069606 107224955 118211621 654180644 344827086 125443629 405850426 56275970 787626615 236582705 179394085 520123358 500011246 563878148 277916594 216592765 47794879 789475897 571706334 53634873 859197292 899970079 733057938 151949190 433930176 256080573 909260727 963085326 136231852 642563660 932052933 825258950 805644044 530843863 920118724 476140580 410717899 784672612 208241379 596758923 31355694 621355780 217278691 625151703 4147323 853312241 166989694 129376421 60935516 522172345 179264648 363575875 632515718 504613993 539039442 430015171 636333510 348890528 358486679 516719945 909690335 399774565 84850451 44762307 840053595 169759170 451818148 352760704 509792808 176813660 508537199 986306064 447658607 720473028 138472886 627182918 303978813 353357029 158358465 898658077 102838193 853681640 56043958 452336545 895341522 21075362 842783062 319636112 396445424 385303490 627370665 159628695 965874414 555547726 604614384 764535969 907320905 299975639 889899761 456199226 728914946 596537067 814415464 399399139 126046352 901218875 95340493 490612683 663590706 762416028 79193285 142313778 899410938 81334207 221647683 102081294 578456043 644432277 460958227 225844154 531417358 730110302 944517471 574989889 762228328 283188014 326756907 588406815 387177277 618767478 638828362 615169143 709358207 242293284 364493289 203699587 639584722 961546618 921885422 643310260 938912648 954543874 143108599 633950853 677241486 973283922 95154365 564137685 738774993 508838197 64806282 747098079 366777286 205481934 172027393 24658615 802568785 536249186 201285008 645322434 991502701 500818376 333563359 460368067 423949248 373556472 238014953 192490406 168970341 246362417 550418918 538429317 954740450 77694550 168854353 300914830 266415848 930008572 718272888 3061807 788615658 32314218 911808641 891080634 475540483 915404058 75309639 903431510 19618126 647221267 753517561 638016160 660313685 468381206 592318139 361891693 876699947 640391530 414773630 677040100 801591873 783849252 153589569 356676059 483185149 264705649 71087881 506633926 653094586 504067454 344762743 242099775 897406682 391701418 561883450 143393961 797727209 318961995 519784695 516579593 596098915 311448533 13366901 503210765 235274736 375510130 355016796 393152006 434797738 952050598 276017375 120051913 124280794 996774431 347046126 374743079 244448295 266101699 818831944 886871203 52149658 684672544 201892787 329029003 75774114 730360717 430344391 428311140 996451028 88250197 181713045 331791906 977297772 941410140 407504315 863672572 235411771 176887165 493148434 976954551 332322310 741018271 496608301 342438698 691232011 520463584 946500547 678942034 358629218 785518048 208124940 828793962 216863636 411400828 635524034 203751992 200877489 256701518 581771763 246082782 930765014 234985366 20741497 480349852 484534237 910725057 450062512 125867296 34518625 283906746 996996174 158458836 515226474 240814348 964257858 202709777 232214588 945232749 81631391 68235181 365704469 874785286 407208128 673514275 938645251 961057293 201620795 353923630 761624855 686799924 278233811 415944486 369395831 991823318 120089843 208461270 948373629 253817002 831664027 77505947 196989695 151650978 217843816 14922698 861493082 923008668 146857532 661316585 357163708 130002105 23844081 505830495 450345618 967622430 66644044 653067399 366463116 756257389 542806679 326748867 680303510 829638958 261316585 509870718 276482383 958992033 133207264 526377931 473409156 84050825 162262143 135408690 636710882 511932986 41360080 341145670 838667785 131128900 65485758 824250264 65572366 327602599 71729736 373004066 562077598 876008368 235600097 799665123 883718483 925222438 783856956 56714361 319434586 688919182 841628016 53229001 950133624 832556033 396660618 439838916 858410914 435358050 31150916 196164268 706990965 364567679 399322896 230612442 200972794 203513456 534165186 648933029 902225250 739336762 768004438 401414108 345647408 300272487 946017886 88191652 208125054 621463654 484263913 491438196 94030822 247635874 721358604 676405608 279460849 820860532 495565635 448243169 236985521 729494054 404092623 366031311 461143482 230854163 610978422 503388562 548829083 663790860 481125720 647988271 924703959 608466288 568005672 585324199 263619155 719739531 152582998 159144923 288580740 575803671 19354520 450248382 780138210 406707200 595530522 247386995 142470119 498123580 189916012 17266372 546136821 747729949 607211713 612597691 100778101 204160150 342246498 419592418 259526298 434464766 146435462 246978850 83594625 190532766 274440954 714855083 486702819 570932110 762028949 636082004 786242113 69598757 391784141 947214412 978624412 885923224 887118253 485342968 170095717 369794024 25912463 69758539 161336647 94863333 273044023 806605860 514595756 611666838 149432675 405201728 153437059 379930133 889089410 235588499 702186807 36411193 839088063 126347814 150902670 358132526 457149704 560778642 628594757 456937728 200354137 184611994 770479693 801271077 636186704 980159267 960433088 482825168 140465774 270152540 962967451 65513638 962057485 902251579 367375816 174831161 457022837 736604319 169507679 197889592 974982005 435603794 210906343 96693419 841274757 624260982 650184176 326713337 537219225 456436154 91980622 12005673 404693107 393241715 812951160 251092574 171304342 399335805 877341800 900498993 117737055 160086159 570454388 272783151 44861804 295081866 577903806 497394658 845368565 153133309 288482700 509199281 459383708 973996316 306632654 489403920 743326306 265051513 647625921 111975483 351129854 662698830 224577870 251713128 904785678 235955673 747859339 296010289 885922683 285675274 804384094 19399031 365558871 141940132 406932766 610190150 346448946 156253993 472455265 498455707 303152595 166536586 132232841 756648955 48959391 755676644 330414657 944888680 315570205 731310296 137159158 952514635 566313464 898955491 838471838 61147376 189701997 525819642 285892884 764367508 702132325 167627486 201243306 124993402 739686151 316683123 795628840 315102342 217531097 854032649 832958974 896877704 144394182 740252857 305305944 929992372 241440051 561520015 385219589 669677911 109853479 284503146 527501692 28364072 705677548 871606714 310209412 574804137 201121434 401394704 93900331 760588658 31218143 490227 221788508 117273776 477727580 652612321 660878415 420540913 579001385 197457429 927147305 219492005 840735986 206565200 653837118 763055476 741044440 145675440 66648063 814118966 980527447 266504219 559155847 679176969 564688063 236651352