-1 1 0 1 1 2 2 1 3 3 4 4 5 5 6 6 7 7 8 11 9 15 10 17 11 22 12 24 13 34 14 40 15 48 16 56 17 69 18 84 19 104 20 118 21 144 22 164 23 200 24 234 25 273 26 318 27 372 28 436 29 511 30 582 31 681 32 775 33 906 34 1036 35 1192 36 1362 37 1562 38 1784 39 2046 40 2315 41 2647 42 2988 43 3409 44 3860 45 4371 46 4936 47 5573 48 6288 49 7104 50 7967 51 8979 52 10052 53 11321 54 12678 55 14206 56 15880 57 17760 58 19840 59 22173 60 24684 61 27536 62 30616 63 34119 64 37916 65 42124 66 46740 67 51862 68 57490 69 63738 70 70488 71 78046 72 86220 73 95364 74 105270 75 116193 76 128124 77 141254 78 155616 79 171414 80 188546 81 207465 82 227964 83 250597 84 275148 85 302037 86 331300 87 363315 88 398180 89 436331 90 477624 91 522888 92 571864 93 625536 94 683652 95 746972 96 815682 97 890472 98 971669 99 1060014 100 1155534 101 1259571 102 1372008 103 1494459 104 1626786 105 1770372 106 1925700 107 2094150 108 2276376 109 2473884 110 2686964 111 2918031 112 3167252 113 3437381 114 3728688 115 4043639 116 4383506 117 4750728 118 5146900 119 5574757 120 6035490 121 6533204 122 7068902 123 7647366 124 8269816 125 8940828 126 9663012 127 10441067 128 11278243 129 12179802 130 13148606 131 14191855 132 15312468 133 16518700 134 17814052 135 19206597 136 20702012 137 22308817 138 24033816 139 25886627 140 27873676 141 30007662 142 32295344 143 34751333 144 37383402 145 40206335 146 43231322 147 46474224 148 49948276 149 53671131 150 57656202 151 61925799 152 66494536 153 71387724 154 76622036 155 82223817 156 88215108 157 94624542 158 101477496 159 108806127 160 116636927 161 125009432 162 133952556 163 143511029 164 153717806 165 164620266 166 176259876 167 188688228 168 201952980 169 216111860 170 231215848 171 247333983 172 264522392 173 282859049 174 302407512 175 323251562 176 345468036 177 369149010 178 394381940 179 421270004 180 449907618 181 480415980 182 512899604 183 547494906 184 584319872 185 623521952 186 665240904 187 709639169 188 756875188 189 807130260 190 860576960 191 917425603 192 977867544 193 1042138904 194 1110454298 195 1183071189 196 1260239280 197 1342243099 198 1429363788 199 1521918582 200 1620215645 201 1724618862 202 1835470264 203 1953176630 204 2078121108 205 2210748891 206 2351500512 207 2500867908 208 2659345244 209 2827480464 210 3005816868 211 3194977858 212 3395565606 213 3608276016 214 3833781444 215 4072846189 216 4326235290 217 4594793664 218 4879376966 219 5180924775 220 5500379748 221 5838802606 222 6197238408 223 6576868239 224 6978856712 225 7404502281 226 7855120468 227 8332146975 228 8837048760 229 9371420024 230 9936877096 231 10535210991 232 11168211680 233 11837869809 234 12546174612 235 13295316727 236 14087530756 237 14925237480 238 15810922512 239 16747268394 240 17737015668 241 18783163982 242 19888745737 243 21057087333 244 22291552160 245 23595802383 246 24973598364 247 26428984340 248 27966131968 249 29589517170 250 31303737647 251 33113780703 252 35024726412 253 37042095428 254 39171512328 255 41419054077 256 43790985376 257 46294009201 258 48935062536 259 51721551951 260 54661119752 261 57761991096 262 61032599844 263 64482036090 264 68119621092 265 71955356829 266 75999589824 267 80263343025 268 84758050696 269 89495875955 270 94489404198 271 99752106700 272 105297855930 273 111141515376 274 117298392148 275 123784827841 276 130617768816 277 137815204082 278 145395829844 279 153379465461 280 161786671560 281 170639348351 282 179960130048 283 189773143834 284 200103323088 285 210977175540 286 222422237732 287 234467658409 288 247143765444 289 260482629446 290 274517571340 291 289283954730 292 304818415672 293 321159853883 294 338348570070 295 356427262745 296 375440348594 297 395434723794 298 416459233000 299 438565406145 300 461806853244 301 486240289676 302 511924582576 303 538922035431 304 567297311724 305 597118735970 306 628457438868 307 661388376987 308 695989661492 309 732343549128 310 770535682424 311 810656438165 312 852799747320 313 897064758404 314 943554515854 315 992377638954 316 1043647286680 317 1097482488887 318 1154007340176 319 1213352302451 320 1275653286830 321 1341053415486 322 1409701575184 323 1481754583577 324 1557375560994 325 1636736132544 326 1720015154740 327 1807400492790 328 1899088036540 329 1995283443316 330 2096201034444 331 2202066098984 332 2313113154008 333 2429588743104 334 2551749491408 335 2679864953122 336 2814216108012 337 2955097697032 338 3102817075771 339 3257696533938 340 3420071993546 341 3590296041288 342 3768735839160 343 3955776791670 344 4151820208684 345 4357287042894 346 4572616108268 347 4798267194986 348 5034719754780 349 5282475992936 350 5542059388968 351 5814018664401 352 6098925366004 353 6397378623953 354 6710002443300 355 7037450570351 356 7380404471358 357 7739577476028 358 8115713325060 359 8509590323429 360 8922019686480 361 9353850806730 362 9805968466846 363 10279299096024 364 10774807651116 365 11293504022034 366 11836440799836 367 12404718805127 368 12999485594008 369 13621941009870 370 14273335492198 371 14954977015553 372 15668228041128 373 16414513703814 374 17195318380576 375 18012194125518 376 18866758328220 377 19760701141890 378 20695784056812 379 21673847427710 380 22696808839884 381 23766672371304 382 24885525355664 383 26055549204815 384 27279015783642 385 28558298561194 386 29895870387306 387 31294313455578 388 32756318275976 389 34284693816367 390 35882366280216 391 37552391433799 392 39297951487247 393 41122369427706 394 43029105467816 395 45021771887643 396 47104131232140 397 49280109831022 398 51553797521696 399 53929461478221 400 56411545793618 401 59004688045603 402 61713716716368 403 64543670263463 404 67499794150482 405 70587560620869 406 73812667995976 407 77181058967039 408 80698921856640 409 84372709431200 410 88209140106504 411 92215220265315 412 96398242946492 413 100765813386130 414 105325847354736 415 110086597761619 416 115056655885546 417 120244976368260 418 125660881005280 419 131314084549222 420 137214698675076 421 143373262181564 422 149800742166332 423 156508568308254 424 163508633887780 425 170813331586527 426 178435558233240 427 186388748939249 428 194686885167472 429 203344530188460 430 212376837586516 431 221799592368168 432 231629216362512 433 241882814627364 434 252578180975688 435 263733846559185 436 275369090239672 437 287503985527596 438 300159415393476 439 313357121148503 440 327119718236180 441 341470752299751 442 356434711735784 443 372037090590017 444 388304401725228 445 405264242856655 446 422945316017784 447 441377492242395 448 460591836837236 449 480620677041775 450 501497629004784 451 523257674769306 452 545937185973906 453 569574009700536 454 594207493606308 455 619878576235326 456 646629820509600 457 674505503124732 458 703551655846774 459 733816159254708 460 765348786991512 461 798201311559427 462 832427545542336 463 868083459001739 464 905227223346186 465 943919335201356 466 984222671241012 467 1026202612148566 468 1069927107831984 469 1115466807865808 470 1162895131418988 471 1212288413384382 472 1263725971993860 473 1317290270150928 474 1373066987700888 475 1431145191881315 476 1491617424253864 477 1554579872764788 478 1620132472768960 479 1688379088505488 480 1759427621448042 481 1833390212348206 482 1910383348619222 483 1990528086590721 484 2073950166311040 485 2160780246859062 486 2251154040657270 487 2345212553052247 488 2443102235669202 489 2544975239607690 490 2650989579985981 491 2761309416173902 492 2876105217922368 493 2995554072311760 494 3119839861618544 495 3249153588667782 496 3383693581045368 497 3523665824666504 498 3669284193854256 499 3820770804535683 500 3978356261020944 501 4142280045143970 502 4312790768483844 503 4490146597284659 504 4674615522474708 505 4866475810763811 506 5066016310184608 507 5273536915401021 508 5489348908557036 509 5713775452620703 510 5947151957097888 511 6189826619034933 512 6442160800525407 513 6704529617540640 514 6977322344293260 515 7260943038960339 516 7555810996157208 517 7862361395824004 518 8181045803914092 519 8512332861433086 520 8856708821289570 521 9214678301169707 522 9586764841549980 523 9973511723118669 524 10375482564418836 525 10793262191183892 526 11227457299419368 527 11678697360887930 528 12147635352484596 529 12634948718488454 530 13141340152521576 531 13667538645278688 532 14214300301987600 533 14782409477240628 534 15372679650327108 535 15985954633029232 536 16623109534042572 537 17285052022038690 538 17972723380858800 539 18687099853020494 540 19429193770342476 541 20200055012750516 542 21000772195176032 543 21832474244290656 544 22696331669202148 545 23593558240329858 546 24525412382025432 547 25493198933621032 548 26498270667002266 549 27542030160755634 550 28625931425782924 551 29751481935065707 552 30920244335703360 553 32133838638802520 554 33393944051705558 555 34702301310986112 556 36060714681129768 557 37471054408490277 558 38935258891557048 559 40455337293986534 560 42033371868283052 561 43671520779432492 562 45372020558379204 563 47137189143278778 564 48969428504690280 565 50871227886122509 566 52845166657358468 567 54893917730296071 568 57020250648585120 569 59227035226020127 570 61517244853008960 571 63893960420656973 572 66360373818548804 573 68919792155524956 574 71575641500507772 575 74331471380952479 576 77190958835863890 577 80157913166533532 578 83236280314454939 579 86430147922605570 580 89743750018572530 581 93181472463698948 582 96747857915023308 583 100447611678408458 584 104285607013538790 585 108266891372332548 586 112396692132042472 587 116680423193194825 588 121123691159291112 589 125732302367015452 590 130512269493511780 591 135469819114393914 592 140611398711873132 593 145943684784036101 594 151473590334143220 595 157208273514228918 596 163155145700730314 597 169321880647023960 598 175716423172721328 599 182346998916010344 600 189222123620456190 601 196350613604926330 602 203741595622620424 603 211404518082527454 604 219349161581518160 605 227585650864486247 606 236124466159289688 607 244976455853261437 608 254152848670302328 609 263665267178380848 610 273525740797461414 611 283746720284031241 612 294341091548748792 613 305322191166500334 614 316703821131157340 615 328500265384824276 616 340726305671426308 617 353397239068693565 618 366528894997197036 619 380137653899426695 620 394240465401659560 621 408854868322225878 622 423999009973067384 623 439691667566093785 624 455952268815094932 625 472800914745604848 626 490258401799094458 627 508346246041037385 628 527086706847012156 629 546502812691865022 630 566618386429420236 631 587458072890801811 632 609047365758356624 633 631412637069069456 634 654581165887360296 635 678581169736818932 636 703441835325958692 637 729193351919882162 638 755866944230561720 639 783494907961514235 640 812110644896254355 641 841748700903170275 642 872444803243331088 643 904235901169698889 644 937160205715473536 645 971257232938570554 646 1006567846510466664 647 1043134303643996827 648 1081000300638353580 649 1120211021788433374 650 1160813187952659266 651 1202855108805841671 652 1246386734483573032 653 1291459711364293487 654 1338127437126006732 655 1386445120147858071 656 1436469838384253206 657 1488260602463807238 658 1541878418596733232 659 1597386355754666272 660 1654849612724596428 661 1714335589829251072 662 1775913960228715192 663 1839656746438399536 664 1905638396310071740 665 1973935864494764620 666 2044628693618724780 667 2117799100827140435 668 2193532064453226208 669 2271915416136094260 670 2353039933164528708 671 2436999436754432292 672 2523890890238197428 673 2613814503854098724 674 2706873839338898394 675 2803175921457990327 676 2902831349659893720 677 3005954416566557011 678 3112663227098025216 679 3223079824561585809 680 3337330317523739720 681 3455545014248124630 682 3577858557583359768 683 3704410068231646753 684 3835343288375590512 685 3970806734120548697 686 4110953848705734584 687 4255943164455870810 688 4405938466135576584 689 4561108963238661590 690 4721629463898063336 691 4887680558475034227 692 5059448804431011542 693 5237126921874021768 694 5420913990332804324 695 5611015656762986297 696 5807644345309932000 697 6011019478274631184 698 6221367699626695134 699 6438923110008957582 700 6663927504598129796 701 6896630623387674983 702 7137290403995054784 703 7386173248116542550 704 7643554290507467348 705 7909717682329263042 706 8184956877706251612 707 8469574934691568879 708 8763884820436170900 709 9068209731179937268 710 9382883416885948544 711 9708250521859267455 712 10044666929711335940 713 10392500125818410576 714 10752129564216379848 715 11123947052920192528 716 11508357144566057660 717 11905777545632308680 718 12316639532230666360 719 12741388385066045053 720 13180483831580149386 721 13634400508727510170 722 14103628432701870485 723 14588673491164605411 724 15090057942648968440 725 15608320939671321185 726 16144019060173743774 727 16697726862984885437 728 17270037453193752740 729 17861563072366015731 730 18472935699528823626 731 19104807678842612511 732 19757852357922985128 733 20432764755174768714 734 21130262238196155968 735 21851085232763018889 736 22595997944385328352 737 23365789110989060324 738 24161272770175469688 739 24983289058754767615 740 25832705028034528936 741 26710415493718224612 742 27617343901624674824 743 28554443230918760789 744 29522696913865967544 745 30523119795133485275 746 31556759109581286470 747 32624695500467781483 748 33728044058705912032 749 34867955404113951476 750 36045616789331379402 751 37262253248697906535 752 38519128770142443796 753 39817547515674501966 754 41158855065978015976 755 42544439716264259052 756 43975733798795170284 757 45454215057992625522 758 46981408055490520844 759 48558885629935855878 760 50188270388935713200 761 51871236259535242427 762 53609510071602786588 763 55404873204318276870 764 57259163267214133384 765 59174275847780761464 766 61152166296993341252 767 63194851583355322595 768 65304412189062842208 769 67482994077630377566 770 69732810706626451196 771 72056145116709941904 772 74455352067125754472 773 76932860253278832891 774 79491174573164625912 775 82132878480403539281 776 84860636390544816822 777 87677196176786780448 778 90585391724371560680 779 93588145578381397688 780 96688471654255949412 781 99889478047907554312 782 103194369910751169184 783 106606452431645641785 784 110129133887186114564 785 113765928804818108532 786 117520461200092844124 787 121396467930727099182 788 125397802131773863850 789 129528436772976348666 790 133792468302676339640 791 138194120421874259716 792 142737747948201914460 793 147427840819346691328 794 152269028191226160382 795 157266082683343002759 796 162423924726490799856 797 167747627063201608725 798 173242419359558670000 799 178913692976967501047 800 184767005862608570297 801 190808087610101684454 802 197042844643830687324 803 203477365585326418858 804 210117926750045917392 805 216970997836320942696 806 224043247754676862120 807 231341550657014570415 808 238872992117825061080 809 246644875524936338783 810 254664728632079629536 811 262940310334221754378 812 271479617611898089040 813 280290892713448693656 814 289382630515543693836 815 298763586134836650209 816 308442782731006326468 817 318429519571458905720 818 328733380302548897474 819 339364241495357929830 820 350332281411065293678 821 361647989057967193931 822 373322173478265407088 823 385365973345891746339 824 397790866806802605824 825 410608681647618438006 826 423831605723912869524 827 437472197731186045936 828 451543398255119071584 829 466058541181689182188 830 481031365403966089956 831 496476026910877544172 832 512407111186877127732 833 528839646018456539405 834 545789114628822495192 835 563271469242047660087 836 581303144997934197472 837 599901074315732166264 838 619082701634085940940 839 638865998622633493194 840 659269479792947455260 841 680312218609758575774 842 702013864021162537206 843 724394657521095856686 844 747475450654098155032 845 771277723081948276877 846 795823601122142256120 847 821135876874328977751 848 847238027851749764862 849 874154237230835819118 850 901909414636446005488 851 930529217582359028792 852 960040073474302613928 853 990469202309403126134 854 1021844639969504864648 855 1054195262249598563055 856 1087550809518863615756 857 1121941912151742849853 858 1157400116634760027032 859 1193957912483291095025 860 1231648759874592885872 861 1270507118138897619780 862 1310568475003288643184 863 1351869376746718655104 864 1394447459149726011570 865 1438341479405858152589 866 1483591348878522514522 867 1530238166866131688779 868 1578324255268780341672 869 1627893194315873956272 870 1678989859248780075840 871 1731660458126822855247 872 1785952570637618487274 873 1841915188099223555574 874 1899598754522518327808 875 1959055208931424074512 876 2020338028809741188904 877 2083502274867752169622 878 2148604637008422180256 879 2215703481682711369248 880 2284858900514940510196 881 2356132760398233363639 882 2429588754926209827492 883 2505292457383183570064 884 2583311375144857298484 885 2663715005723685047370 886 2746574894311537299140 887 2831964693049094209648 888 2919960221887475369280 889 3010639531267723779986 890 3104082966485205483920 891 3200373233976899702865 892 3299595469382078078492 893 3401837307640109161016 894 3507188954959992321456 895 3615743262939389166710 896 3727595804668780318472 897 3842844953093571711132 898 3961591961484751727260 899 4083941046287088432763 900 4209999472197541036398 901 4339877639757504983280 902 4473689175292993073508 903 4611551023516296164706 904 4753583542605472024996 905 4899910602091747105722 906 5050659683372769816720 907 5205961983176694728572 908 5365952519812578223472 909 5530770242528254625628 910 5700558143814020462844 911 5875463374990576820393 912 6055637364898868702040 913 6241235942065053604968 914 6432419460138486249962 915 6629352926995527723966 916 6832206137309364565480 917 7041153808973602996674 918 7256375723200334704392 919 7478056868676903642159 920 7706387589605869024400 921 7941563738032905949386 922 8183786830264192670184 923 8433264207818487288248 924 8690209202693627034624 925 8954841307415793386652 926 9227386349654642294280 927 9508076671867784208453 928 9797151315781855729080 929 10094856212170579178779 930 10401444375742172182104 931 10717176105620890546297 932 11042319191209746627602 933 11377149123966363008136 934 11721949314854983334892 935 12077011318034128734629 936 12442635060547621150836 937 12819129078574167493512 938 13206810760031631351952 939 13606006594088935956750 940 14017052427388575787516 941 14440293727561727349383 942 14876085853811235276048 943 15324794335199463811588 944 15786795156390157049460 945 16262475051514005865008 946 16752231805913664950072 947 17256474566434501935835 948 17775624160050419768040 949 18310113421490069094248 950 18860387529661902528080 951 19426904353578127478169 952 20010134807545858055520 953 20610563216389882548805 954 21228687690447061758228 955 21865020511135859938141 956 22520088526850046009384 957 23194433559978138921360 958 23888612824837485363600 959 24603199357325458730939 960 25338782456088803857164 961 26095968136055166852314 962 26875379594095477723064 963 27677657687736538515024 964 28503461426662343694260 965 29353468477970190648374 966 30228375684932425396656 967 31128899600230162665857 968 32055777033457231756219 969 33009765613864359283284 970 33991644368157823308218 971 35002214314372580958095 972 36042299071599677538264 973 37112745486676395780980 974 38214424277587185677200 975 39348230694739891962879 976 40515085199881966806680 977 41715934163824632012749 978 42951750582796343579856 979 44223534814600920115059 980 45532315334422859648010 981 46879149511515349084386 982 48265124406577592299404 983 49691357591160938367411 984 51158997988877678749812 985 52669226739819441718427 986 54223258087981364079500 987 55822340293106946470658 988 57467756566817609128440 989 59160826034454554312524 990 60902904722524705861908 991 62695386573251067884436 992 64539704486082500458368 993 66437331387785874725796 994 68389781330942687342808 995 70398610622554445405223 996 72465418982608713206496 997 74591850734324212227962 998 76779596026008577010536 999 79030392086266848614994 1000 81346024512530795279965