1 2 2 1499 3 1783 4 9719 5 9311 6 67883 7 134947 8 203317 9 189433 10 560171 11 438533 12 943849 13 640973 14 578827 15 2172383 16 28687 17 1505657 18 7595033 19 2822971 20 1242379 21 22899523 22 9232219 23 5730031 24 12336083 25 3487607 26 35451433 27 12174803 28 10234079 29 84459019 30 68736683 31 44671169 32 85507057 33 103260119 34 22478971 35 79035049 36 136537 37 107039071 38 243754463 39 249787423 40 159438341 41 2279933 42 233272727 43 219624319 44 645202963 45 376111891 46 111369211 47 509858803 48 1100204377 49 333691019 50 748516033 51 840925433 52 1354433783 53 716203361 54 1143729137 55 363109801 56 4406477 57 1083762059 58 1333434313 59 2116924471 60 2277914833 61 1954449919 62 602358283 63 1983598619 64 467296399 65 1357852303 66 1939743083 67 4659763627 68 1600751611 69 5479228423 70 1437069787 71 4654886801 72 707532983 73 425323117 74 2306166307 75 3215265433 76 2903316487 77 7109149651 78 5330927629 79 7452416029 80 7528822993 81 942359837 82 3407132107 83 7634616211 84 4425047233 85 2612138483 86 639269119 87 11567963053 88 10704247369 89 12170593817 90 8774533483 91 10368837569 92 10650124883 93 7232129309 94 6571059431 95 1350557119 96 8370124687 97 681181393 98 8485991483 99 9085010651 100 10066174109 101 12003366619 102 3187758403 103 19403246251 104 21809983007 105 2554798583 106 7439872897 107 6193392983 108 573956281 109 13845314719 110 12392586827 111 1201011463 112 1553106481 113 19273063321 114 12969602309 115 32988098797 116 1729399319 117 5177425717 118 1309489297 119 27161121313 120 23450131577 121 31659376501 122 6516355033 123 9099553763 124 19963574551 125 14175993107 126 28119173183 127 3784567051 128 6001445633 129 9717870619 130 33099134821 131 21602602369 132 40923044299 133 12436251649 134 29141770033 135 39011372683 136 14504093083 137 20319131423 138 29894025869 139 56952643919 140 6583172119 141 62528027351 142 10684749983 143 47897982019 144 192575899 145 24656903603 146 12718468949 147 25735157029 148 1092807451 149 68800816769 150 19989209183 151 79132253869 152 15272236531 153 63560994449 154 29319707863 155 83304201133 156 20421634901 157 24278892751 158 32040507377 159 51058846439 160 73411629623 161 91137919339 162 103801064869 163 10661093783 164 99559842013 165 69002370869 166 20264376383 167 134652213349 168 40658011649 169 109482800111 170 42965941969 171 100250305609 172 41341841911 173 165909126259 174 26505960139 175 97586002093 176 37967677519 177 96519248887 178 24739898149 179 12319839019 180 153924917869 181 74593309771 182 63767551591 183 27487123997 184 103440799447 185 143865821083 186 107763002833 187 46938503669 188 34460972983 189 143237052043 190 103933072297 191 53790348463 192 181473572719 193 17783543269 194 145487888531 195 142669643383 196 187201842283 197 149766379067 198 222047047883 199 145008641341 200 170810103469 201 257160984517 202 147648774719 203 123205136933 204 90380427233 205 47146466827 206 63530365903 207 199602830027 208 32779328419 209 15636716119 210 13221407033 211 107239775329 212 309484859443 213 187600349821 214 282943285769 215 272687446253 216 41155436677 217 170257245311 218 232697317819 219 299214393229 220 220092401713 221 80396377349 222 5799669157 223 339212660851 224 112745762993 225 195304497827 226 275032977697 227 320807522647 228 11090446183 229 236487014021 230 82166852351 231 368770911533 232 287244970633 233 289082847413 234 267931597667 235 10852485433 236 392754325571 237 147958333183 238 422448139187 239 92702182943 240 2774886839 241 12431401397 242 467838572689 243 413406123583 244 265695726097 245 167147509519 246 468790585453 247 187568365951 248 38391662233 249 264267122783 250 215492529709 251 256331866447 252 257956359569 253 214305710401 254 523600307519 255 25425187171 256 164231592769 257 534244135333 258 537596361019 259 288452946583 260 504896716801 261 86953431283 262 218033914159 263 360310494241 264 321050178583 265 342830651203 266 634763759221 267 141552698851 268 566292751919 269 675741189637 270 435690607529 271 633811991819 272 192481700483 273 166014662117 274 514262761651 275 353476089163 276 216232482197 277 9513290681 278 227899536769 279 203823438121 280 603808727779 281 111585881233 282 149680709929 283 551064700019 284 352418400127 285 392236490983 286 9367605019 287 882966101833 288 915032550769 289 609628200211 290 795134946371 291 482475679633 292 450203727469 293 422178756239 294 1024423591237 295 1044936858089 296 886503998719 297 673636789009 298 695717069783 299 983788022953 300 869332134691 301 793255654459 302 715364167933 303 212231030419 304 552693246797 305 200454130027 306 549266436559 307 715031162569 308 523172682083 309 496485457483 310 891723870461 311 683658533023 312 917429812933 313 1269384800833 314 614650282289 315 308134239601 316 444292013521 317 829551508283 318 757476459871 319 812271841669 320 27499733531 321 917759166913 322 903954722743 323 631513259953 324 1433099543059 325 1592709647383 326 1504182811933 327 1480983464501 328 907574590459 329 1496307045917 330 554299057063 331 1192099377019 332 1550480728591 333 494377862047 334 288160399573 335 1477304513239 336 742305638719 337 942501047563 338 1611279570619 339 1807455740033 340 549411796147 341 149517369299 342 1094733693721 343 1712171788003 344 8507080783 345 1655236440019 346 650893390957 347 815008699819 348 981485715251 349 435935027783 350 418100072167 351 181090809919 352 372952366363 353 1724417422543 354 485854385167 355 1054992581833 356 1017419236201 357 1354652392033 358 530853665977 359 236558957699 360 1691370110233 361 2240562133853 362 354511446769 363 1569111753889 364 543450503719 365 347326762919 366 2374016418283 367 433778393651 368 1857015724429 369 2414985752251 370 2048242767419 371 138731658067 372 538341184547 373 1913322236311 374 1200303076663 375 1447046240533 376 1017825224257 377 2625787846009 378 790703891177 379 1254323992513 380 1900189557269 381 794508749029 382 15862391191 383 154182511477 384 1465023870593 385 1280774339057 386 1122431219999 387 1256738128769 388 1854329771233 389 2923742695969 390 103259978567 391 1810280194483 392 1592332576283 393 2046997419427 394 1466743448719 395 1571396898943 396 2408599907887 397 409225017241 398 1478770621183 399 1820643176663 400 2814749383681 401 438521646611 402 986083918279 403 2378228693021 404 910972664333 405 2072202748669 406 1899800468173 407 2464400273033 408 801959578489 409 3116135243719 410 3462035326333 411 1058472030839 412 2374098904217 413 2240563559911 414 2533215307277 415 3746222371211 416 3199636934183 417 3481139386883 418 2979697818059 419 1719363064043 420 1108758250123 421 470895190417 422 2926119666341 423 618915921461 424 1242262380277 425 3046550599369 426 1850597628301 427 2749734028193 428 3888004042333 429 820996201633 430 2245121861669 431 1250676994159 432 1552633965977 433 736201313101 434 3980405785661 435 1538378265733 436 2481244684769 437 1990706674609 438 3677722436083 439 1721119702699 440 534300675929 441 980819536933 442 2256665037983 443 2161913996551 444 1391992133759 445 3728468545741 446 413066675419 447 334630468693 448 1032579020233 449 4065425687051 450 2837108879497 451 2146443614389 452 1622598711269 453 1289734733593 454 2717356362179 455 3760479130519 456 1548166235519 457 5210782719931 458 2792333120257 459 3612305152873 460 431788186073 461 4268301329449 462 338768443147 463 508647701239 464 3877119597511 465 1946992419607 466 954558762671 467 799301045017 468 2211481167869 469 950955522269 470 175089198457 471 1394889608669 472 921925137569 473 1060715969497 474 4226189072881 475 1466663761889 476 5590513227907 477 5315987431133 478 3911223946811 479 974971538083 480 1898168945683 481 135705467017 482 5389361420581 483 3350715482287 484 4452598959833 485 257417417249 486 5585673289841 487 511777428769 488 2503212780583 489 1208389681547 490 5102642203669 491 5173867763653 492 5988261740491 493 3870115482539 494 6615889039127 495 352087250863 496 4431322159949 497 614344760671 498 2415440520217 499 5545507775707 500 3693811069801 501 4207563058607 502 5283690028907 503 7373495990767 504 762815199709 505 6208874784349 506 3068170594733 507 513836860319 508 5098199700241 509 5220216357607 510 1147104329897 511 7422748089907 512 5863024265869 513 5349810105383 514 180951436697 515 2894509664857 516 2016379835693 517 2274793736597 518 6059456063723 519 4412049215999 520 7943909145049 521 8395207707853 522 1120776917719 523 5983028810701 524 7262074508959 525 5386825851769 526 697521687607 527 5831655837247 528 5006548666627 529 4931240511317 530 5641028712119 531 7308147053099 532 6285728021137 533 4938927473251 534 8003279618753 535 7830839093719 536 308805639169 537 5714681684233 538 9728918790607 539 6453684371833 540 7181519096683 541 2496500189669 542 5604785707819 543 5944287328883 544 822869782687 545 8023154350843 546 733210485131 547 2506992763883 548 1877000218573 549 1820006910613 550 2302273616813 551 1660850659747 552 1399750816033 553 3931152288409 554 4551771844369 555 3256057533257 556 8682868820513 557 1595109266533 558 4798588829927 559 1460418017837 560 5524682022443 561 408957091463 562 10637399701603 563 2061046089967 564 11483225315477 565 10728193957219 566 3931557354031 567 7436673596047 568 3148410670579 569 11354203903363 570 11916440121403 571 2801537626519 572 5381107948969 573 10643549736277 574 6730050797443 575 11849146640839 576 11101130564297 577 12519484232557 578 4860965217169 579 5851727440219 580 9136505656919 581 6399343871561 582 9326182468513 583 6582219260957 584 6059810054447 585 7941468031633 586 1055056447369 587 12222702066119 588 5729337728531 589 2349680377939 590 9555616983511 591 9322339557151 592 3744380598733 593 10024029124699 594 8414486134519 595 13995751015657 596 13942189218637 597 9067024211569 598 1020471025781 599 7087417614523 600 8104289274919 601 10505173640033 602 9597166407739 603 7439352806719 604 11174796621403 605 4739612495743 606 7274150768719 607 5208701969183 608 12335913828841 609 3214366453621 610 9207397207781 611 15702001969609 612 1299027743119 613 1659145406833 614 1339210681621 615 9127228892581 616 7918500686717 617 2315208087551 618 13565056233241 619 10903401353191 620 5723133070231 621 3538479155287 622 4372768109063 623 150113932939 624 14570935634413 625 9520828859053 626 3493417585069 627 474963920749 628 16228349878283 629 1122994590589 630 11324041623163 631 17193927658741 632 16825086572941 633 910953470503 634 16392939193483 635 519363605809 636 14584477186133 637 14933142853201 638 15734388142981 639 3952802654357 640 14780881116949 641 11979930354149 642 7465860637771 643 18585184977883 644 6414197625001 645 17449377675967 646 3399263744689 647 11489061877129 648 2228544323933 649 5148539603677 650 17580864323377 651 10557874944791 652 14860554573383 653 16778113277521 654 9312379343173 655 6268477519729 656 8614461792997 657 8184081972533 658 11300175646219 659 7395514880939 660 11283125342233 661 5649772214413 662 13067501435999 663 8245382666539 664 19522548633547 665 2462004533647 666 12153817307363 667 425021615519 668 161006295701 669 5919784417711 670 7853325333193 671 5869293905311 672 457181272931 673 18948755074393 674 781943969579 675 18103119753167 676 2751396818383 677 15091402546711 678 23013334028059 679 9034115098069 680 2573972842561 681 11024876866681 682 11062064402569 683 23901225972823 684 8747011969669 685 15003242443513 686 7715023118233 687 4297220631709 688 5667934044403 689 6747446350039 690 22336244385431 691 17102293514641 692 18889966819483 693 12496069667747 694 770159522213 695 15121287335839 696 12943821579079 697 23839437831227 698 11966655980497 699 8760796312069 700 20257587454249 701 2514513562277 702 25575281576609 703 20252612232383 704 14762826590761 705 20906986627459 706 16997714848747 707 15842954770583 708 5872677223519 709 23242201675723 710 17413604562223 711 21095139265169 712 643911601127 713 1440904357301 714 24404323560233 715 14665540904983 716 11323807547071 717 18950454875917 718 7293534939583 719 3736885376599 720 5911088106619 721 2051010308899 722 2489868793241 723 18219871721899 724 9213101965831 725 10605102237727 726 27751155619987 727 22398637131799 728 11793637314379 729 29117959835303 730 22899898056083 731 27520559012729 732 14679644947783 733 18909743524327 734 19945846666549 735 26681786817443 736 13169676676183 737 28014686562601 738 23375139136273 739 21367638006233 740 18182473464079 741 2465785496983 742 11243565832861 743 17336741317183 744 7275163040623 745 28069563899633 746 7455619659113 747 11572077900083 748 21073701878533 749 23296952839159 750 4661796228403 751 30832813741517 752 18130221367619 753 33704245613471 754 11596190879107 755 431009775491 756 23974355004569 757 32497834334599 758 15311801327843 759 21102128667649 760 8730896696527 761 1291059057689 762 1635548566297 763 24568298507491 764 17313060625097 765 12364003377533 766 36151558877377 767 14515346950933 768 12523743259583 769 17881899133933 770 30620242353607 771 15487132822243 772 18560048335061 773 22321169184331 774 35730787985569 775 23769481191319 776 14020483940167 777 22197080435683 778 28272181321411 779 36057588726079 780 32283654381541 781 24578860719433 782 35438037648001 783 31446428115433 784 24783518854333 785 37505399323897 786 22360272773437 787 4677438717709 788 2425222793393 789 16693444884617 790 19884225040723 791 37501421583121 792 18181738721453 793 32147681144077 794 38245702962589 795 28441901379259 796 32987225840479 797 14813520151987 798 35147464672259 799 16377546777953 800 11644236594973 801 33727316721017 802 26884209950659 803 8297865155863 804 10338871104811 805 20721703917833 806 27551937685339 807 19193920379629 808 655606280377 809 29490485293637 810 16869985269751 811 24407958104807 812 40999968841177 813 17790896944783 814 24760155281671 815 26703355185643 816 31244055990031 817 1143696884111 818 39383957524861 819 40400529415819 820 18839546004457 821 12243630389033 822 39248157531511 823 15481378446949 824 42479685028549 825 30059921405387 826 17393189104337 827 40387824822871 828 4553538993103 829 21378398906281 830 3977242285087 831 20949671987533 832 31925635717231 833 42821076050281 834 32464280775233 835 15766336531639 836 27935277062989 837 6954148072141 838 6215480214841 839 47881446420683 840 1703029983533 841 29960983403623 842 20020522628147 843 17597072604763 844 45330863776903 845 3717825270157 846 41941776626011 847 14709892588687 848 44577180866467 849 30315932936137 850 2553780175543 851 25647126342373 852 28116546378727 853 12333680866459 854 31133192030587 855 22904588850769 856 40876169982499 857 38443779166519 858 24066539626933 859 36131368359439 860 40226065402319 861 9534192409639 862 53275708021093 863 3542831106517 864 5643326235709 865 36356587709219 866 41215778421569 867 45890031378341 868 1381172327441 869 51422741803183 870 275738006197 871 33490205559583 872 32364794665757 873 37902828451219 874 1755152366887 875 11128072557853 876 21969697283291 877 54643287835153 878 4098771806951 879 10292395051711 880 10907894295163 881 44108016323069 882 41078841478919 883 24602183421619 884 11054795151683 885 27857351040983 886 24139439862119 887 48755144271553 888 20772760173167 889 27872292553579 890 4481992771819 891 23593038980419 892 11752845643237 893 40377057690349 894 34527643270853 895 27102715179247 896 39649497818993 897 21516704138549 898 62729804291743 899 24113913379489 900 62607298592437 901 16574498896069 902 47306505842083 903 62887127241229 904 23376288447313 905 3935468627747 906 9685147992497 907 40091505338237 908 44606317464883 909 31786329592099 910 47661560825869 911 21740981974787 912 23326623266117 913 46909897994503 914 38528588082169 915 4730026445693 916 57574515483883 917 2212550981983 918 34672977741979 919 51494693797271 920 68386804934039 921 25026874817149 922 44169072931117 923 46334864628667 924 66666157946029 925 48144902742121 926 10266373728379 927 14166442426141 928 17480837616481 929 39959874052933 930 44854218890017 931 56101761836431 932 7076767342699 933 16937771159579 934 4753726694179 935 70380946254413 936 7761495934369 937 4607751393433 938 11226064024621 939 60256789629373 940 22258421279287 941 62867691167707 942 55217922823319 943 68508829542019 944 4660086769831 945 16067987012393 946 13973697044599 947 8217347885497 948 67137262473383 949 20785051297333 950 37194554630719 951 32865675565213 952 42878684473381 953 20071866818429 954 14107217960273 955 20195168730427 956 1966259536693 957 7901346866993 958 29190040874483 959 9149007266339 960 38108416478659 961 4013899119883 962 80003738238751 963 14531817841603 964 21278534802823 965 69087829764817 966 78793722423253 967 69790189444777 968 28912676907043 969 20637716689069 970 71834464455119 971 46801717983883 972 9521229430309 973 83796659927003 974 9822434250683 975 44031129873733 976 43805381592563 977 30301028728507 978 20175768758683 979 33128864710483 980 69438375909533 981 28340365582967 982 22641817786163 983 11844694730989 984 63464227425869 985 82361362228931 986 34755214898659 987 50413364201911 988 13968749032703 989 88460910329833 990 53989812401419 991 38406352205293 992 89023008160747 993 29050027429627 994 9397582586167 995 80432225189707 996 56034537463199 997 84414746322331 998 79039598276467 999 87188308270919 1000 9475365440869