1 1 2 1 3 2 4 2 5 6 6 2 7 14 8 6 9 16 10 7 11 55 12 6 13 100 14 17 15 44 16 32 17 296 18 14 19 489 20 35 21 178 22 77 23 1254 24 30 25 1156 26 147 27 731 28 142 29 4564 30 25 31 6841 32 390 33 1668 34 474 35 4780 36 114 37 21636 38 810 39 4362 40 432 41 44582 42 103 43 63260 44 1357 45 4186 46 2200 47 124753 48 364 49 105604 50 1232 51 24482 52 3583 53 329930 54 622 55 126757 56 3424 57 53843 58 8552 59 831819 60 301 61 1121504 62 13054 63 55348 64 16444 65 516334 66 1011 67 2679688 68 20442 69 232969 70 3039 71 4697204 72 2714 73 6185688 74 43286 75 112406 76 45280 77 3606786 78 2707 79 13848649 80 18276 81 936954 82 91604 83 23338468 84 2420 85 6388445 86 131574 87 1696514 88 95616 89 49995924 90 2230 91 20706304 92 198352 93 3145482 94 265378 95 20118994 96 15354 97 133230929 98 131860 99 3469788 100 86072 101 214481125 102 15812 103 271248949 104 397485 105 475732 106 723140 107 431149388 108 33955 109 541946239 110 88374 111 18041140 112 376933 113 851376627 114 35395 115 169103614 116 1465555 117 20317388 118 1871786 119 471890809 120 12578 121 1282153125 122 2544208 123 53680402 124 2728141 125 499620198 126 30081 127 3913864294 128 4013544 129 90855836 130 373056 131 5964539503 132 69153 133 1960521801 134 6218724 135 18730920 136 5082517 137 11097645015 138 157910 139 13610949894 140 325454 141 251634017 142 11053976 143 7686881800 144 297157 145 3008802627 146 14654218 147 101129538 148 15805449 149 37027355199 150 59051 151 45060624581 152 16224775 153 477378721 154 2770214 155 7354508958 156 290351 157 80630964768 158 33434258 159 1076748630 160 4482089 161 27491883431 162 800679 163 142798995929 164 47282971 165 63679957 166 57013146 167 207890420101 168 262189 169 157132632027 170 4886501 171 2007420153 172 80219357 173 362326859894 174 1193311 175 8822112106 176 47906041 177 4268601260 178 124180740 179 625846753119 180 242476 181 749474411780 182 16558088 183 6655433675 184 139538333 185 91894376497 186 2235744 187 463069190842 188 223121353 189 1962211244 190 15750126 191 1820701100651 192 3756765 193 2168627105468 194 337758774 195 512069301 196 77646269 197 3068829878529 198 1948752 199 3646072432124 200 42857539 201 24235630296 202 548979006 203 973232335274 204 3777896 205 443569778186 206 697517346 207 28711764392 208 378427527 209 2989023850174 210 190303 211 10085065885766 212 959801209 213 55641659664 214 1118765848 215 947669649131 216 11957163 217 2942780233350 218 1412455620 219 83604860674 220 42627282 221 8746735028828 222 13173363 223 27152408925614 224 356793090 225 7259906340 226 2237955842 227 37561133582569 228 12154804 229 44132934884254 230 137627097 231 9139482707 232 2550586351 233 60806135438328 234 11570975 235 4115986813645 236 3821234281 237 274971496152 238 401840156 239 97862933703584 240 3058004 241 114540884553037 242 1991174093 243 406361361683 244 5965288375 245 1195763702960 246 39788160 247 68058577052989 248 6281508927 249 593767739888 250 545258217 251 249291451168558 252 10498235 253 94568709518559 254 10577021854 255 21021465892 256 11784471548 257 394723676655356 258 67799580 259 66936362513185 260 340902254 261 1039149383864 262 16237871872 263 621837416509614 264 33887246 265 33400752869175 266 1712100951 267 1823808371316 268 21793307273 269 974834369944624 270 9724182 271 1131238503938605 272 15130741721 273 120189988165 274 30535002962 275 22101331166658 276 106032451 277 1762278433057268 278 37579372786 279 3160842006810 280 301691912 281 2362219145337710 282 190095419 283 2732873183547534 284 50126959091 285 113584530105 286 6995880591 287 468747914012045 288 280232730 289 2668024741249040 290 2561428178 291 7708010450176 292 75382093951 293 5622992691950604 294 53488861 295 242306896005146 296 80016948140 297 3285569736390 298 103931863038 299 3040502720486727 300 29174049 301 1197904295944272 302 126881738696 303 15510675567731 304 80941405651 305 458894530902141 306 278629672 307 15142952738857193 308 6015694447 309 21893244424593 310 6339328360 311 20017426762576944 312 269580988 313 23000006655487336 314 229153366556 315 88862896208 316 248483234263 317 30326181989842963 318 826356235 319 9989353455809869 320 13207711183 321 43205760585260 322 25036578705 323 17962369146842282 324 1179577633 325 617184556129612 326 409471280658 327 60418383462454 328 390399986715 329 7353195723608648 330 24028758 331 78801255302666614 332 537261328383 333 72970845541164 334 599567687214 335 2939693527311547 336 245299706 337 117949491546113971 338 264714736556 339 117117853691081 340 13917389486 341 42349355771760171 342 1184667213 343 18532026547828234 344 838120885583 345 2573243364756 346 1053789779186 347 229272286871217149 348 1974321404 349 261578907351144124 350 4944363024 351 77349896348688 352 386437508546 353 340122810048577427 354 3319626287 355 9697838971363607 356 1653016160331 357 11809452330836 358 1835054203050 359 502957566506000019 360 227430376 361 363021982525969413 362 2203371676842 363 107393420381228 364 78817147391 365 17399775230136610 366 5196293824 367 843250788562528426 368 1805040662311 369 515091206716691 370 81767501540 371 97591985083337410 372 4889323196 373 1238057794119125084 374 451137937973 375 17735795663838 376 3672348412923 377 510519396334700127 378 1031367963 379 1812356499739472949 380 75116987486 381 1091549488636103 382 5421744788388 383 2332821198543892335 384 11052567532 385 828892936369151 386 6473882132224 387 1320992555319152 388 6999121477089 389 3398704041358160274 390 189973084 391 1481417830058417941 392 789409873837 393 2020424955802242 394 9206173901728 395 96059937550770261 396 4326513844 397 5589233202595404487 398 10964253102592 399 94720931021174 400 344128275708 401 7154640222653942320 402 19124924979 403 2497670379737393332 404 14095300614261 405 69543330824510 406 930256914040 407 2494700494384640238 408 10913290116 409 11682316277192317779 410 401689470826 411 5003457808664123 412 19902709395889 413 1126489127636956023 414 17289999629 415 289789335128099607 416 7564529463396 417 6740475415257690 418 2992236180405 419 21424521360255636319 420 182348483 421 24167053021441363960 422 30754457260500 423 8160146091985392 424 30140755954030 425 232371055570541220 426 44183390138 427 2477297171183660956 428 39304078982843 429 707975643330002 430 865030907793 431 43955477170518116533 432 58889259553 433 49501890409405150714 434 2850751687020 435 171849297260626 436 54979579099475 437 24653230022542028344 438 66580950375 439 70593393646562135509 440 333862603913 441 1351985137610534 442 8930518011098 443 89322956321353645666 444 63229644533 445 1448148064899555644 446 83904171532880 447 29021943187048972 448 7101671910618 449 126891542690981417999 450 3738915575 451 31546755218935875811 452 106637239525827 453 38640428049487203 454 116563339740350 455 33200612585217373 456 58706966568 457 201933379285114688628 458 137245532416174 459 21503002510092614 460 1701295026949 461 254365395758574199974 462 3280576344 463 285381555241961986286 464 118569315042639 465 631045543449092 466 189882022170588 467 358963893768162876612 468 56245299830 469 24494546606536113389 470 3811664834592 471 90217687043420125 472 220760088449930 473 107144496177116896395 474 220720472677 475 3431729597563312122 476 7722895803325 477 109167641637189148 478 307468192593662 479 710369798236628238004 480 8953691396 481 220227713521129915585 482 360586852017664 483 4448298919917297 484 82687013323829 485 11422218569601844057 486 349110225037 487 1114608778936426484247 488 419286477570170 489 207395923187553092 490 658959747142 491 1394313503224447816938 492 311272410151 493 566692440560009454979 494 71450195761417 495 517756822314468 496 433566723590069 497 106757834519426266019 498 478862499611 499 2176192515439287461624 500 13431042963141 501 358294769960195701 502 792484026921036 503 2715220650772245313219 504 51360059155 505 31096574884082653309 506 99050844386634 507 119637632413633996 508 995518403929055 509 3778141924035171537109 510 7638014316 511 219510712256872229926 512 1168225267521350 513 276790516073978020 514 1261937651789618 515 50938897697512904609 516 671057560923 517 1139186730865077594963 518 67107318960353 519 804082561642604578 520 6594269746182 521 7274403582551733377345 522 642688561564 523 8107902911527474124145 524 1843382541871985 525 462306367677754 526 1999067452928936 527 3575993090289247146483 528 268877045328 529 7135886836999028434106 530 31513665253870 531 1268397154343185776 532 61938371325325 533 3577547880366588292872 534 1480167183941 535 134813089472722765844 536 2706880858101598 537 1780389585931108574 538 3150896081215680 539 160107953160794156486 540 47673737365 541 21333216422211708570597 542 3662943497983258 543 2313862229309927815 544 1515254770377656 545 217865268201712375335 546 42531816233 547 29349508915133986374840 548 4567382371236365 549 2794773171564912644 550 12945189983153 551 13694036290020354602566 552 1322673660241 553 1804115848636297972813 554 5736352482712334 555 24701346455653269 556 6153982122483699 557 49760750604354432757375 558 1970814480781 559 13707367640547696097906 560 5912577849742 561 277466655629917270 562 7715750586882048 563 68156060996536236172173 564 2963605514426 565 561806415798887600455 566 8941656904743882 567 262130137713378120 568 8970697736301056 569 93200902166643654187579 570 41017717361 571 103412067875563710992445 572 459643976773889 573 8404781166545114244 574 479003814059524 575 498669323653332072032 576 5562542307890 577 141113233412529912746557 578 5125383708846581 579 10835379829597119956 580 113871971843790 581 7036433479993548543095 582 6301113647831 583 33020150687032108956347 584 16129401634571594 585 20646530905635460 586 18552110870973384 587 236081701023305130945920 588 538856699242 589 96971738132050959274953 590 232261303125313 591 17940277963264333149 592 16802817045545879 593 320830596120295386610806 594 1760687146949 595 23533549968010467201 596 26515206106575973 597 23041613592403584401 598 3343548070434734 599 435350207840317348269999 600 232897392889 601 481818554503286362923738 602 1234746006958018 603 27777233990587168582 604 35307249953977417 605 520969085787400867318 606 12720189349377 607 652520246268116112057163 608 16814372538651550 609 790497199352642589 610 441964297610141 611 183942876157496374252915 612 5446485635797 613 882421087896683264554174 614 50526078279829544 615 241669143039152698 616 395846550341739 617 1078248955392080004474788 618 17981518024908 619 1191621108583631746910144 620 418619171641899 621 31206471830728573761 622 66998835397203806 623 51102184978348252392564 624 5289651526712 625 8793666336067441471204 626 77100565128093742 627 4163963091733685194 628 82463491481494401 629 645525704712618591490210 630 38658239729 631 2163909235608484556362423 632 89566286977927650 633 100873842168897956953 634 101970840415137378 635 13687887631472181861436 636 24585479174801 637 21137750932586511576692 638 11025795102371731 639 121430596236089789002 640 1312792151064388 641 3542738177508596708707873 642 35586899337122 643 3908089057205582486668933 644 2912107654547412 645 724957379583784533 646 20291590467357595 647 4753603989138067267826944 648 44014624513585 649 796765103996571817510483 650 368214826037210 651 3927947394976985421 652 189627734924066069 653 6369928557132709817142928 654 49830921337918 655 33012651713141592294368 656 163573213860451365 657 250028229335707641636 658 7699952173452566 659 8524746061205131302394949 660 195006012692 661 9391599660555044587641516 662 267741375983709238 663 19876298848023528636 664 271138213106177406 665 461566901397787717977 666 46527194282524 667 4956290835547789724215039 668 327658772508572259 669 424197943518705422580 670 2868112017821052 671 2221376157843016890375837 672 4840580574135 673 16741855262985451980947170 674 402494613393356750 675 2770708169872936706 676 92186223509497473 677 20277228247502764885900783 678 96839254720876 679 650876957896704191329273 680 1341781739536510 681 678979443787764437940 682 47429593911689801 683 27000417698448800353553864 684 43487143830256 685 120691094976853162834888 686 23952740313712967 687 857717989204779489440 688 489644601200678937 689 7423852676136789131669565 690 922807664802 691 39478915279883795756623330 692 735513814850775933 693 3218317376732358626 694 787915609312460828 695 184780599816819987411534 696 88074627962595 697 16362932878060829538256692 698 900188106443084154 699 1364696133537644131445 700 331317384488282 701 63286531028521032840985509 702 41787151539230 703 24216498695577446151582103 704 159163742267421849 705 6057761508302327013 706 1173710569842695356 707 2235004526640359107809120 708 181800568086781 709 92097768690318501305952844 710 9534598072100047 711 2062723572059659731985 712 1361289525006015970 713 43419716771566312660122792 714 4113972754414 715 8104951028957624598980 716 1628931209443449273 717 2719208939004985258575 718 1742705313499675016 719 146781769170263852819573504 720 4496310438906 721 4104595456209579356140337 722 736539840908408634 723 3415313812403853911303 724 2117168519055752125 725 405721522142559752721943 726 57186112442040 727 212632080937520072186590491 728 15709704372188493 729 4285861918836403213949 730 17168386688332173 731 77665774335493161105748112 732 346315731527942 733 280403140023083872114273883 734 2937387303255109000 735 516686114441812333 736 1441480571655461156 737 43748488289288288434708520 738 332892887049651 739 369369023603738655757458074 740 16450964836561935 741 388944707224593587474 742 104316641428674016 743 443591925059596733749014861 744 323404242314737 745 1488246680367125065599367 746 4329592155273560812 747 8063059402378097211907 748 180045306535055633 749 13609058040230618801344316 750 9075979692151 751 638864582333908382360557375 752 4076606701538018325 753 10531347489597830315015 754 592461714701713140 755 2240154902221571477389235 756 38270206997880 757 838862103313805798709299372 758 6362453440448750528 759 621531013113898459304 760 14993562195381245 761 1005292153304074193879898919 762 909368871766903 763 24577135576600025947274648 764 7692731094934305729 765 14603144297287906550 766 8210406002553780560 767 244839692129974780690741116 768 1097285145680511 769 1441770172223648126550509164 770 261835537713906 771 20481969225405907861651 772 9917970658225232345 773 1725445005022910006140645611 774 859192616788382 775 3228995083208970953034973 776 10795175080643558264 777 360270383992871660457 778 12006841512033271442 779 750899934172213572413661612 780 3803575417286 781 296691306852828043831665119 782 1756166226811919246 783 18052320647635221611440 784 452024994079104013 785 7521495829793442906075710 786 1686296991070565 787 3223934948277725160271634797 788 16423076285983724069 789 39536124774586706787679 790 95724160339492270 791 78905410751110263940754350 792 290732051954528 793 754807259281262270330310674 794 19842934692644121792 795 124372290989392905736 796 21094071930013277445 797 5021922058584382849328869241 798 32868241967958 799 1575996052837790207404188374 800 141261795658610284 801 58733414262232139852938 802 25462131415782501774 803 757379790544667765414080921 804 2254420021119777 805 112797199378636143588190 806 2942379315081186247 807 75763548766713463896876 808 29459795862020454838 809 8517409609130970421571757564 810 35557691646700 811 9297921602834531195851268717 812 519229610826557035 813 93957692698736478557451 814 2900922621198206224 815 24694345072532047233155791 816 1068932484048651 817 3927111520260177130754072931 818 41774555026733396958 819 301652673159941122640 820 161413536372382034 821 14391184287298069419105856948 822 4186554825664699 823 15700142401714084441377203062 824 48312138244783213604 825 36226674325451147189 826 1225469736148610244 827 18680303100276877491522988119 828 2030749696949923 829 20373118273183778133458320224 830 290497045887770490 831 178381543203188356338540 832 11240220891080003471 833 125534803460253997479200481 834 5644408553053204 835 53907270099704571352029234 836 2703251998868570060 837 129286146986967357613072 838 77060786916373372246 839 31388166898835484452139885749 840 3671816622939 841 21852598213763670739237032196 842 87025541138708396920 843 272478072469308327317769 844 92373010236212336115 845 11736896764220133270005180 846 5371982964188777 847 71950834021048469076003269 848 83340767112102995688 849 336390436780407691591181 850 143185588916948530 851 19739390929573426274157401165 852 7509351473491400 853 57245201602333536237114022804 854 2709329496226709077 855 286657304510903265781 856 128133786176715373452 857 67907762200418949875852866530 858 240703681470783 859 73951402289532005957331751319 860 484918343025274944 861 5980906407122998221490 862 159186075198642742612 863 87674799670795146675673859586 864 12118651356018989 865 170948015833136651750429470 866 179473733713630427100 867 162555910733950668988645 868 2583396180505684617 869 11706534835955483209387789879 870 61488140806281 871 19905734142503672615606808386 872 207279638418002691778 873 750638584130234986073148 874 30118118628374121831 875 3362402753008583399856472 876 13534664817447527 877 158606118553696417431847045995 878 256797690145344114624 879 954437149653013245933106 880 134551911464648774 881 187718762576041099642814429719 882 698925913586609 883 204193025881123335512830178820 884 12883482902982288608 885 2162457245451339952693 886 325645179394511870764 887 241538698168481624527315178360 888 12680023872354201 889 4020659693015012086631611764 890 1463454479886387595 891 128917953391318567954380 892 388538137414169537071 893 96104289467510983008574914355 894 24389578563527321 895 531679704654219179221283907 896 10519632723264513474 897 94753051737436139274585 898 464119934642880208360 899 161077155503607150849187690591 900 252531006721026 901 114516648339276909043032301867 902 37464166563833715328 903 23140885043336332568560 904 535528410129070428512 905 772878635146230086241528251 906 32493849704527493 907 556336482009740068071399064007 908 621943310444269969887 909 2581459555876922757415884 910 10333665772550622 911 656658071540248718776792346784 912 11908644659656292 913 68639199043151661698054098449 914 741762595781816192714 915 5423353679709182002928 916 785692492974507279709 917 11882111703694451862635742950 918 11783119666247899 919 913865816485680423486405066749 920 1301676691791698122 921 3993296304902179116715988 922 936337676949414287774 923 162809230623424217780942463750 924 223390571285001 925 1117604507376491961093603761 926 1051613764125201130650 927 4744226516803877613038475 928 577265763527824231798 929 1378663636778122744608506419569 930 225923550051626 931 6464248916699447289319702546 932 1250174634357841708447 933 5975488921605691553430182 934 1325522557882681949500 935 40745906123085639354151178 936 11463658656868041 937 1912696063727159213943851080854 938 27181819672272290988 939 7302681092316721944973664 940 4063977322866356627 941 2251738844689892053427982289843 942 76005423363759713 943 887895351503768306653891548972 944 1444414383984306261280 945 230582050423777156412 946 128467143033103295308 947 2874428410083806869907819978391 948 75673340280441202 949 455509139681337722856740903340 950 2145386226540783382 951 10886515072475580284601070 952 11030819326637977663 953 3666554760646647127956344306189 954 73070805126446290 955 4870309816644598668820676849 956 2491233925131751364401 957 521864451306138286158811 958 2639329902944440942464 959 58582411290916855924181165100 960 885774632587212 961 3239037255388302322363945116402 962 269685789447557872525 963 15750851725566191241091446 964 3129062709429367062273 965 6997892519719324341186941144 966 1538502001590287 967 6451387609023188709970129910796 968 346032232117309170074 969 1242401205314285992093113 970 11652404408136940840 971 7576130994027952290703815097176 972 155653700269729169 973 98947375745429791481030406809 974 4157929747040804426482 975 4345027926401202735387 976 3619336259469372035744 977 9635556074800288403768986034252 978 175015829948817068 979 902299049596478979142692208389 980 372812540348322432 981 28463035462683857852024070 982 5211674784511302420212 983 12245992177539511607834487453051 984 124319650207764442 985 14368494281674195086934870769 986 710584726836814848227 987 316093959935962810149326 988 252226104330645693726 989 5553997508345482054185682273614 990 214026212377583 991 16839773100833956878604913215476 992 3690112910382112179365 993 43206809942997421451525899 994 119506235103819407795 995 20533755775487817605684608889 996 230050864374326697 997 21366628562913781584556907794728 998 8166162064776517377472 999 33238665627389645669983921 1000 26922227369513652052