500 100
1625200 2614896 3707034 5394584 5965332 6652623 8003777 8134823 8382037 8658657 10386287 12028515 13464573 13706884 15149697 15449788 15461616 16413790 17152436 17963686 18931050 19291633 20973635 22229330 23708470 25705699 26697631 27197176 27877323 29364854 30703813 32009192 33337739 34994441 36094770 37009006 37874264 38916304 39063250 40936070 41007713 42873349 43246588 44712968 45737637 47610957 49442034 51233281 52151086 53913869 55547399 57154733 58633570 59808570 61034421 61128049 61558652 61560729 63495161 64775001 66597897 67220839 68186300 69000196 69804515 71762508 72490971 73323477 73506123 73637860 75401052 76190659 76277817 77377152 78651668 80647725 82358929 83120358 84839941 85194378 85309273 85460179 86939310 87722855 89716888 91251770 92919065 93340565 94692260 96555524 97058723 98216022 99580177 100208808 100729549 101544016 102377604 104087657 104996820 106376339 107581019 109330136 110888413 112397042 114309696 116105855 116171407 117180973 117272588 117927655 119074974 120666863 122068404 123170454 124724983 124799809 125049048 125334557 126603239 127782286 128225181 129796750 131772469 133121553 133263929 134107835 134297923 135412363 136316630 137891432 139681145 141421555 141478917 143022566 143236732 144409382 144857929 146349996 146726857 148260061 149334897 151004738 152886642 154867610 155928337 157048605 158587221 159185669 161025127 161880181 162170659 163605269 164557368 165535818 166160600 167406948 167639203 168037159 168755387 169483431 170223127 170280464 170458339 171643079 173164734 174738417 176215131 177194893 178948102 179948117 180165452 180972893 181700019 183623774 185063938 186940101 187639519 187681301 189515808 190748672 191027867 191892894 192045791 192892813 193610808 193813565 195563538 197162713 198864735 198936747 199409065 200720987 202171260 203314821 203450442 204654641 206470574 207987863 208476750 209246823 210569413 210799707 211515578 213011879 214631057 214688489 214795721 215179316 215528942 216850890 218384398 220012766 221312927 221801055 222324352 222849304 223069105 224057838 225550924 226363855 228053437 228856870 229118889 230344433 230660880 230895131 231817999 233792914 234832910 235954279 236713902 238627879 238868325 240125665 241892221 242885348 243219485 243878763 244561584 246454954 246864630 248784424 249294319 249502291 251157393 251913691 253745092 255331672 256784542 257294008 258746538 259035645 260040194 261585251 262933793 264307064 265143406 266185733 267549106 268124390 270076398 271546235 272770829 273146340 274569492 275665598 277504564 278862594 280533890 282473387 283639885 283796657 285604844 287218174 287404976 288498045 290235978 290780464 291891206 293172354 293174586 294159574 294644752 295820953 297019706 298960131 299344141 299573389 300201886 301697065 303153242 303799604 305717782 307243183 307862927 308381823 309955006 311591329 312267734 312945273 313299827 313703087 314811076 315516928 316445299 317091183 317586573 318528127 319983983 321584476 323331135 323814304 325011094 325408304 325747182 325826382 326836954 327028402 328318867 328367738 330154943 331525442 333153724 334092506 335225407 337204402 339126808 341066644 341758804 341997586 343545652 344795896 346345224 346684334 348479894 349638223 350282821 351199559 352965020 353681649 355325898 356542062 356646100 356669479 357370620 358826096 359321555 359477747 360239789 361485610 362650463 363489048 364606839 365405247 366791734 367437708 368456961 369200198 369288743 369662235 370118582 371095565 371895821 372607640 374428574 375580939 376874236 378725179 379281691 380216160 381545722 381803637 383037644 384344416 385292558 386180276 387360503 388923336 389418931 390185078 391111908 392848347 393259566 394776030 395432977 396369376 397398442 398124440 398392964 399610444 399658758 399929438 400352375 401421694 403035275 404381192 405824691 407623745 407634347 409445130 410343817 411477107 413122896 414814241 415995371 417267781 417359846 418521502 420031030 420366850 421189234 422315920 423334908 424376550 425587876 427397566 428460007 428598928 428806804 430771552 430917480 432845695 434787102 436260116 437639111 439168740 440673379 441559755 442599377 443196267 443942977 445266725 447025536 448885517 449062925 449954205 451070632 452704939 453451016 454513856 455883298 456125011 457662519 458809403 459208162 459776855 461209319 461992133 463946257 465197708 466686324 467303596 469283844 469638408 470975018 471419483 472560317 473156811 473949134 474940250 476129372 476139552 477830781 478942291 480216086 481653071 481743972 483335689 485198052 486156226 486586261 487455233 487849271 489193958 490892532 492823650 493990867 495574299 497395440 497978102 499121868 499302081 500681701 501718435 502605905 503310915 505062684 505127774 505259333 507076726 508816047 510061043 511395346 511654288 512327991 512461622 514413463 514537077 515650828
2792 5045 8819 2530 4501 873 8512 2919 8652 2434 5257 9895 9662 7857 7172 9487 6919 6038 646 633 2611 4289 9664 4709 3030 2861 9816 7835 2417 3955 1975 6217 8496 5817 1439 6303 9001 7780 1710 9181 2040 9792 6942 2598 4993 9780 6638 8221 2436 7535 5362 4009 3446 3702 1698 1756 5086 1312 97 7603 5167 2555 3936 7309 7801 7368 7565 8567 7075 8398 1882 9803 3802 9301 8271 7450 6522 2976 3412 1078 7176 9468 1239 8216 1125 2993 5200 5022 3698 7446 7360 5360 9904 7372 4636 5300 4859 3734 3320 3189 6734 7498 9456 1048 9357 7008 7417 9590 5374 397 182 9623 2680 4059 8029 3139 7388 2209 183 3100 616 1897 2994 1407 918 5193 3482 4757 1729 9062 4939 1774 4811 3671 2895 9978 5484 1553 8910 6809 6732 7722 4192 3538 9069 7038 1896 3181 7791 4487 8789 9245 2092 1901 6766 7287 2627 353 4332 9130 4012 792 4665 4574 9026 7325 1262 7244 4430 5901 6881 2743 4444 6957 9912 167 3594 271 5216 4482 8880 6630 408 9666 5174 1119 6604 9506 5841 4704 3948 8108 1034 1303 755 342 2815 169 6659 4276 2230 5923 18 2505 3899 6700 267 3350 9027 5079 3156 2849 5508 6732 4282 483 4992 3985 4952 7439 6662 4699 2964 6705 3920 6551 7837 2619 3441 1184 6200 7084 8654 5315 4689 9085 6715 1501 4093 8460 3316 8145 4594 2494 9704 1860 755 2301 1837 7544 459 3137 2444 143 7540 8636 6889 196 8788 2677 6215 2776 9600 8561 4731 8324 1973 2736 5151 8934 5828 1970 4709 3492 1500 2105 7610 789 3089 5565 2845 9340 4209 8809 9350 3550 3204 3674 4577 4367 7654 8024 6960 7146 4480 7042 116 8953 9316 9423 3049 138 8763 6184 7582 2247 6705 8358 3502 1979 9836 3906 3366 1634 4206 2758 8533 4381 606 3967 5116 3229 8677 4859 2500 9082 1988 7932 8101 1833 7956 9844 8332 4532 3065 8966 6805 8279 1885 8545 9250 3722 9375 3865 7655 5906 1969 6165 4943 7587 7475 2309 4709 2050 592 5467 7400 3758 3745 7100 6089 7889 4054 5397 3330 4169 3685 1607 4505 7997 2149 7028 454 5465 7946 8651 2383 6170 6658 3580 1909 6423 865 1899 3788 3460 3142 6803 9097 5155 8881 7224 477 1137 9274 9887 3206 2646 9985 9132 5042 2149 6890 3744 7168 2353 9533 6428 9763 2469 5071 5208 7914 7933 2200 4944 8585 1060 3791 3794 4652 865 4151 9856 2969 3113 6373 3097 7652 6042 1243 1141 4224 4466 6463 7261 5063 3163 6234 9209 1381 2853 1687 2174 1190 4195 8978 996 2976 2751 6432 7793 8613 903 9201 4443 9234 6073 6214 4044 9218 9767 2643 5040 9606 551 1697 567 7073 3503 4843 98 8825 1891 8480 2423 4495 1732 6551 6998 2697 3308 4849 7464 2690 1415 3636 9623 1539 5099 5358 8599 8727 1873 3783 7305 2539 729 5577 7998
714710081 511543841 951094285 766553105 89935771 517908408 6036061 734020412 378857231 519498111 89460099 409916926 501325206 105761240 87498789 756035651 290179323 512912505 279434334 758209460 277815667 168131016 898074133 956287768 994375392 983544441 897024466 172372728 510964436 691590538 549876166 17215328 728004872 947881116 907996029 996039164 694664212 216108707 707911855 102820168 454842503 630534298 147472894 206749024 140684712 895291158 167410988 266105966 98114058 531213796 400943855 82100739 451789161 410522734 320923472 125255949 660467125 77834124 889880388 83841003 501159850 654324281 129663971 446381693 769207868 649804103 71026632 601624383 923893444 996299056 823225492 400951797 282644056 58915728 132957217 933824007 203407479 224001516 458880830 714149394 854690372 107293375 870603163 366192965 500048723 787324387 369562839 21335968 883105761 534194852 512989099 577787274 452991740 552798991 654719834 111365552 143212719 847795181 587841771 932962080 890130690 814968955 798889156 964276438 43179447 707196521 22482923 620218229 302296230 60406162 234459645 219050306 145681434 36834044 365047347 375584072 44708542 752599537 826044218 256494841 612913110 856654272 122502215 368213215 270578058 567785244 76531258 826472797 365330692 314322108 190605944 968247092 901264183 70698312 527942510 309699290 518475926 49351458 60345592 298728686 943366250 164818478 448441822 966827869 110824018 143298298 649634909 407902599 129412857 786472584 324018282 11427302 719335076 346704569 137231501 293825273 695754167 65593017 2783666 671866723 912856950 260840982 354374865 252892122 168004866 855702714 127934153 167447722 672786981 984191281 597010039 353264570 609641070 826254147 718554493 210856233 840772429 70473937 455473730 84310820 36249275 754024932 768468428 530864061 471262208 959679050 9720226 760163494 500921329 686806385 196943073 241594551 122236574 63352668 912554331 375891385 144355934 895062519 255191214 701935104 581999197 841050139 596726303 872049246 863848893 423790369 72922099 184515057 90592588 381417631 89753166 334863850 600054476 731692482 220265295 5716794 221149000 524426273 620684495 608313654 536396825 60229874 797226159 397493250 909866293 107866302 710398898 548794942 355302856 706863837 36044073 775305232 487118979 957587707 24253990 750564576 31024805 649278288 255062572 454494116 994508727 428626903 132136416 187087432 267260840 753089421 971603334 553202268 170297225 689803757 669265141 301863474 704840674 532827385 144909987 958737729 313417443 103405061 552196069 741106970 247259494 196240814 660268053 194851548 285764785 655419671 241511994 647220224 350660252 862034943 737549119 109647346 982894945 935208336 373811455 126699089 309226535 812345737 257555128 788868929 22848136 447740780 829057286 497091616 141042753 110682179 59365049 63560799 380909050 481462376 616343461 91730113 942586154 150799803 55503278 727203735 758914134 225577832 382378350 929165177 682423081 258097779 20356546 268949612 765506513 887850449 422771990 847097786 272744226 564199683 918373627 28824074 95770309 449490808 3383675 712279102 130629065 637927034 778867767 544144600 323853893 569566548 667518592 555735529 653175806 987951386 84906536 20826116 179450819 540577578 913128250 441033019 284235210 128998004 41660961 138209696 932124037 959357409 474296484 715076823 954573850 19336575 235186502 542145969 948529281 85976595 924807878 123873602 55533081 906328350 84447618 921093203 113088713 683227195 243458324 218328579 71612897 400523593 107203141 346328784 319031980 277121902 662572908 890105265 924455126 508125884 92759537 644356918 379312956 460111762 888497652 912376472 246248154 366564070 989765004 21124077 803791303 779626876 276091597 702272279 821167165 160830845 302412537 57467972 781055629 358257508 449297737 675985087 466223895 766398693 130508523 446159089 569858483 124898209 426189086 820558581 346555752 938679906 299563085 251320594 104913974 738720147 38600405 959191947 289925155 903693491 43387340 550601743 129315693 187637302 462686558 825179032 767734805 551140246 990555333 13446789 620266591 346281401 79902593 431065222 926301256 525119572 49690554 432626186 424360680 272753951 103878317 363765524 802794561 179606348 550623012 74688878 643151231 300227771 667801421 409335765 80253263 883124769 336629293 751089374 996715296 451727895 172801441 898308693 161471679 123596815 987494322 840570616 4260250 79428498 614771411 845607930 455142824 344875381 692790947 60751294 149748050 730895295 487545519 467123534 142484401 125269403 265985940 190819322 17710644 739489880 855705424 672288819 304762615 937382749 152314382 285042037 645570148 153555548 542418072 116521289 558341622 563000097 97767684 463937059 64289261 295496328 233760319 197762676 434638621 609188937 79461500 736472090 11829110 810625889 679006698 264579661 939020410 25454105 605328702 360400891 729728712 469554559 640426872 351725561
705 470 849 22 416 429 457 919 301 186 31 6 841 299 5 887 894 649 39 999 669 159 182 824 674 888 709 822 938 644 40 204 501 837 302 639 447 596 886 747 532 698 266 916 421 370 233 683 721 646 289 636 758 253 752 961 356 429 923 743 309 167 939 867 413 6 572 240 848 15 107 178 358 994 609 661 150 850 667 639 989 968 957 594 817 485 118 336 978 236 639 969 289 78 52 117 972 403 947 391 196 126 188 281 61 448 77 180 654 229 900 808 991 317 886 152 970 993 899 517 771 918 622 867 327 517 111 974 255 675 509 451 884 209 356 640 668 256 953 170 686 682 470 745 737 536 188 991 857 483 536 523 878 175 765 181 342 634 839 342 1 62 786 165 536 145 950 796 280 13 714 887 823 987 149 118 926 637 782 422 534 660 65 853 897 189 639 237 547 907 531 765 835 910 776 236 682 663 499 905 548 463 696 848 729 503 635 995 499 287 972 358 240 205 323 145 441 691 647 225 551 576 643 59 225 301 17 192 815 691 553 707 824 0 230 785 934 199 58 572 247 967 783 705 907 437 7 56 192 654 802 506 712 258 474 782 770 664 845 862 444 786 398 778 293 176 33 743 409 764 797 63 164 980 888 684 223 46 255 210 614 344 32 657 25 64 293 879 255 663 599 913 700 659 538 363 913 705 80 66 894 204 833 192 398 819 979 940 466 858 285 149 245 683 335 473 767 706 667 640 277 363 563 658 733 6 495 864 483 446 895 357 509 68 58 144 642 434 143 829 469 86 437 514 262 393 180 930 719 157 279 842 462 459 116 149 376 791 480 814 123 942 271 243 386 941 211 319 962 352 205 854 755 289 144 575 874 568 814 222 350 180 290 477 907 780 115 516 758 27 597 667 553 505 358 983 75 288 583 882 389 698 821 792 434 385 927 165 648 675 310 178 883 341 392 386 221 262 865 841 260 261 512 228 345 162 101 647 133 317 70 576 324 764 103 462 274 432 924 176 882 364 286 730 738 144 802 702 891 287 861 420 702 228 162 507 761 395 834 478 377 556 292 714 831 454 220 814 346 263 472 660 932 505 372 441 629 586 644 667 782 808 72 659 535 154 397 396 648 280 986 979 301 37 837 573 952 872 316 637