505 806 425
123896998 846327665 154783285 671777520 692700806 989822722 55189283 626208892 506087093 959946160 372742550 259899171 41807780 455201155 641416024 620371159 522667030 654040312 773493702 808856895 963453346 282033535 525357649 721482805 302026549 358893565 343920384 619595336 533951373 20476748 744094445 913847611 685049791 412254903 743168195 855710852 613948337 908821631 147851079 791638478 749503136 120439384 555884492 174417271 318247836 961057772 289666749 794538259 407534087 699285847 505757719 616559591 34896922 551591337 743842283 381691758 753883488 623442279 303394017 504484312 162408249 184583947 306260144 40611974 511294809 593731967 161151655 700685455 571579462 172068518 856809512 222533439 144662493 263600084 304295719 891681939 249106893 139393616 813355183 542553533 552605210 237511641 5512029 601364902 632023964 246071070 75593187 57388391 280413821 658538053 332943750 305077967 161576639 910685541 406307489 901493985 469190324 785917707 217736480 245353042 352826756 817712313 526803718 746422799 830690218 555972450 495547623 727617461 225889143 101230576 950855790 437356567 571348878 799187391 986272985 177995196 512585062 911519519 310903160 837519199 400742348 239741397 559020081 483939949 763703134 160108442 975157247 362177930 153848080 653203099 410149230 574110476 590512811 945741815 814796065 230811518 836375369 157430341 100735053 98382367 792075739 535158283 508065595 542226785 350158243 372745288 416731594 605217130 488139962 785602795 543853034 416954518 139921547 262504281 590662178 919389171 818130006 840794347 499838474 315605955 204926382 516395885 829119186 31432190 759565052 814311841 54614458 556362445 820472313 126679994 31076504 504304400 185958456 978190305 194050133 637442265 143051674 705152180 975431024 656800751 940463831 186640322 175843449 212635212 857970684 178995728 74896535 365024415 113723623 420571799 576970755 312811211 751897037 693209795 646560395 545894502 454941109 925525237 948194320 39926587 153664763 781398274 710635272 200153545 543316942 146872499 21904124 440913345 889925297 502446659 636224267 511511691 482558718 628759780 259902054 905466818 589902686 939002682 997838546 291581876 303906898 224372702 698836265 141649379 669167278 497091036 510750169 868608902 207655448 120252725 539737443 371573768 964378509 42420574 83206877 998588808 24161757 384995775 410744945 129189720 397731882 400079926 624014300 7979647 328329325 212437393 915786992 827332663 245045745 356846615 845088786 626364015 943777238 182184448 852051132 852634185 142470031 807284728 873723900 567015069 537646436 541285280 447180531 364222581 449435377 624553997 42828632 215816591 132016037 543968839 674557939 439096030 837096260 224324044 152967458 579879689 955100774 832156426 827049815 557214955 978702582 986007016 537070999 20225553 331673267 572483134 818256892 297886015 733572530 501827672 636231733 109671148 745702106 871871863 521804801 379683265 951498342 391309392 548233655 280105245 975338599 710435211 100976322 2844564 779776320 131937861 273180701 20901227 313007144 867939982 722416347 78630686 39265195 197095916 779841697 602065371 185935402 883777495 787854890 671586820 321467990 378934330 45486018 773568433 55199161 403425784 578641868 153602860 853634861 544208229 932237117 521675123 230967138 106227913 9591838 910331577 389767005 596189921 580275213 165632229 71418611 663875934 57856700 130493457 881058130 973534563 181803633 76487436 505167225 423362059 415438469 443931097 647058619 533637344 799891429 859970094 204577601 310213733 407402900 475805174 906540164 859403918 710678823 617294287 436286422 86852931 60311879 643841421 514988250 667647713 800235059 88694453 714738184 688460984 252706875 89164035 21997355 51905422 632247878 682262756 606240738 475334682 639622733 972377085 474886690 519913866 551790046 256163234 309175474 711036926 552592538 21261151 599443373 405164810 932479670 9886067 472697092 56506936 766924670 445410640 520156922 459137924 889484238 890181661 303448230 728702430 391320727 60496180 419768436 369321899 364727648 474997412 184008868 326946629 92189890 544670640 507212746 883094390 218286827 461771597 438640460 804721153 617899036 45491880 865763815 224712217 563455787 427552670 847239723 310792424 280911874 511235395 261870330 292056586 365428254 216875612 769358349 565081615 285347601 840834020 155641455 679235836 799892736 326264715 349929728 163285194 932982053 970514482 740678899 290356710 371909198 319832688 233505360 186095024 448842076 183906576 195201139 778318076 756540869 408624017 946486411 231639700 399432211 330415781 226989596 931551155 990440547 350183090 477200765 206325899 229611239 759279700 621123163 682132672 913487460 21266137 891230260 792631276 875207349 520038083 31192797 543996441 292616518 113019466 172569341 317117514 290432409 24575959 948908175 201014514 730018757 245809802 872835428 875724922 924005618 227670198 227818911 702085568 308499422 258540639 424362039 878921363 993591131 174398403 430461816
283106872 435910862 272139214 684331906 217554920 109204658 748675748 945009353 547114831 484101907 681569307 169891475 532825871 104499732 25680958 101298557 20076859 633705577 175610827 24115191 269427164 943882205 72362166 490780867 868465520 743139790 785386660 778377594 306186597 168742316 230007665 437974279 836148899 847806846 971386794 694310953 709467135 598616156 933067540 133201397 161120969 394683126 696981283 887361107 326568767 348919307 723409796 565763708 252445975 356386035 183272083 14231938 16828409 29920278 942338021 106336456 480537091 605026675 841652416 365605510 674571844 29815578 503131806 255548486 242320705 896298930 250374062 428994410 938017650 408192244 449720659 923925412 32220614 158662701 111063715 175923067 16685083 549236928 735885033 345926861 581984711 146736290 387126307 32234311 24317970 943083741 562087300 256859375 555648185 914521613 778741235 659456667 145941613 641436902 504606859 549874807 754470226 230223020 21699865 112264323 554240896 160251321 109988001 280801555 724303750 852926458 470301658 342958925 392094434 186968434 670068141 7203246 146869898 396659383 217461177 644850310 409584998 596617584 331456722 522838135 276173011 608707293 985059710 518846714 179712289 349145167 467121271 455394522 899437590 905818027 458303276 973347510 131934058 188640747 131057727 170121091 198632777 928273309 448370184 364822280 108109524 897310562 880427280 262220385 163065504 162173040 657144983 659008125 215678773 726887697 958742800 950463136 793540496 14759714 885082783 751297762 475669409 627155605 629800354 325898413 228542670 143081967 631351077 801565506 696576110 353428682 233823084 205564469 528245839 195147348 747423853 408517101 637538097 517727695 395423827 432721445 740334409 235687183 474720765 348614254 14489791 819405055 670781308 937219243 111209520 516746268 550947992 161420691 54477612 619105528 117244236 287561522 254854329 300273848 188795462 568249192 783310286 960768919 299322728 359196776 602703321 260992865 924070986 918590779 646913338 39516152 198331061 189866555 100784069 137828307 145963817 584309144 36900676 304210042 49122648 314535894 681714675 779219723 105560745 864238669 202004226 795404472 364198582 355418024 962937623 875529031 832974286 898023015 157782729 212716433 857981300 536276829 986209062 544606211 130375901 259935794 356154926 876930336 306476406 736231905 261085525 594644476 901081437 54220091 980237317 683473091 836081123 799213411 151329818 167869744 544802832 488550481 189471844 748277014 479085855 257262415 931130152 522031323 270035197 546114430 11817632 701963768 624039118 321516626 33928566 915067258 292040041 418718226 126301005 829291140 327445463 36010585 334484792 779207883 730623447 993308312 144444993 319826200 226164829 920304785 291864036 69520330 575691279 600214237 112340625 650549073 324000711 129514856 347758125 414504628 11122964 138379248 934034065 636598284 641004728 958817929 449117706 260761863 202230059 885919771 483531735 608928102 450339607 152780002 833701551 448663423 809608666 809049326 693906744 860437179 256034311 335861921 144846481 857526809 503976933 805475636 275710665 565310122 22846446 360704305 281649509 618098195 408281937 739608314 848211422 39252238 681404529 898080577 709471265 292232169 680176996 903011726 396870925 514345733 248745589 828009661 288377080 525987672 792377507 231389565 467907115 865053931 442733088 334688978 738189153 320846173 151250130 593973907 308589644 594669151 376080597 178260972 939090448 426258486 355608310 737270750 156243910 293053501 560673082 589044666 49380091 297093472 60894037 605200298 202174510 828004513 933821748 265045288 882723157 842035094 375917428 563625349 393699928 279786729 822326760 843058275 206270869 849973463 557532182 688216635 183531611 868223410 485455803 211207897 354947951 594934367 768356675 261583835 160999306 185007321 248847953 693348661 306889176 693106348 252853309 157140399 300441722 303592826 783353489 368347493 587589381 43009402 771572108 771488326 71913729 575252980 612234399 121395863 791023212 482172870 309952754 739855213 846411316 8488930 817445856 512006966 977732288 93526989 66565494 243100209 143883368 412164130 7603448 648794353 930055672 302231821 708565341 936851166 515969842 925052625 777791438 140624051 617623880 421381699 386477611 859666689 419196774 944974156 412280198 16256683 661021990 120552810 619255461 210348392 926032665 698759727 377250948 244892741 973248837 451180481 162138833 822233632 622892450 584331097 998489199 525566510 594329756 534308292 151137267 775983733 484635028 238083045 44369962 77836883 970393439 73140017 121427601 650860277 67728069 475152945 840798683 227362785 349752067 654612227 407734895 552618349 494064202 198246362 298893544 452534085 683130942 186538362 68114067 74221289 9568375 526269884 209349620 971943468 344480003 436048400 435779393 933122486 343165666 439397366 524777701 932097923 91145865 580470660 127624703 186402659 534532192 756148195 695016160 558072184 13384004 970826706 122407313 615371450 909327621 775255074 628740171 8590198 12844777 898849848 826997756 606050251 693207079 210499214 21892297 363977772 269832813 249517361 766262918 160208865 751659611 113154116 498222912 411300229 658076678 492594812 452852660 216374153 735469430 477380515 712798165 799465136 738877736 156660502 21511497 390588049 452091020 916814919 674856941 740210713 772111496 169550139 337560141 172346886 277203955 583149836 319482925 906975084 224081947 671744104 540476163 750270516 227019072 420249104 409391225 475596184 782799126 813517658 419794672 20833449 203371335 40313520 923444216 359246025 457083887 176402447 763508441 27359793 755279390 703111049 411211022 695140972 966508634 695543235 980672197 487436506 272779034 92726904 458753888 180177198 499021644 441819380 543668726 863548401 577039567 84524697 766312402 3889917 434366202 938119517 406885619 902943234 488439060 707142730 778830475 861406468 595522777 935979005 738771329 555278555 706621691 105983784 256673519 714957745 93590431 537582865 709435044 556809608 16254172 531027984 97494946 582916274 123746624 927106581 237211809 345648727 368524874 357890847 277461131 930028274 189892337 710257606 356791550 131325140 536666139 818774450 139328205 670573216 847767847 772895777 711924863 67598797 556274276 467915877 439438030 76088616 393819031 294225508 920276266 18244943 87392889 661940503 856231476 709972790 10209079 934510859 867489347 218476198 509612784 705541859 71704546 933394105 608867387 938247635 585881680 358757472 28478366 919413799 25626110 460038877 649368088 356244410 735938325 839628873 308867480 212103295 311731182 403204111 127102851 498448124 84193175 892997999 506581810 411553994 41561173 26419708 455501425 611239190 940552732 953640478 120423938 840986403 13765913 520870289 639103000 23318214 819377705 58061284 708335836 853420265 287974239 728578300 688415468 217314312 738112642 201863054 679879639 80702135 472603532 246972328 569430690 652402201 701314860 348420904 582817862 527702634 147445061 339383875 208466479 812865399 624472941 213167616 614324926 67476257 344781679 656561851 511072201 720351710 430473161 241790627 793281814 160762168 739451951 106650683 486021347 378733132 183507974 883431132 164096609 73589323 628272874 920010546 257777716 758711548 27661608 237649339 826466549 615196472 858448452 432219980 777047984 601556333 494861685 287712651 877720166 777328668 217417252 110107509 662994060 530117212 559835761 263882202 317607819 13584980 40345006 183246300 802329918 425305028 572946145 715905396 601502327 474488957 951136582 640473581 172633977 921060068 655792843 133088871 922891391 754693747 715838099 896629333 284286516 25708600 982412660 787563007 42171962 67853141 116771961 720638209 240170915 756484990 125149536 267591882 996657019 926215038 390603036 13665054 941609276 408536498 844609620 615505557 495516503 411918988 348674019 428876570 548744114 159912721 680251734 501225580 123061285 423453020