-1 1 0 1 1 1 2 1 3 2 4 2 5 2 6 3 7 5 8 5 9 5 10 7 11 9 12 10 13 11 14 14 15 18 16 20 17 22 18 27 19 32 20 36 21 40 22 48 23 57 24 63 25 70 26 82 27 95 28 106 29 119 30 137 31 158 32 175 33 195 34 222 35 252 36 280 37 311 38 352 39 397 40 439 41 486 42 546 43 611 44 676 45 747 46 834 47 929 48 1024 49 1128 50 1253 51 1389 52 1528 53 1679 54 1857 55 2052 56 2250 57 2467 58 2718 59 2993 60 3276 61 3584 62 3936 63 4321 64 4718 65 5150 66 5640 67 6173 68 6728 69 7329 70 8006 71 8740 72 9507 73 10337 74 11266 75 12269 76 13324 77 14462 78 15726 79 17090 80 18526 81 20075 82 21786 83 23629 84 25574 85 27669 86 29970 87 32448 88 35064 89 37881 90 40961 91 44272 92 47774 93 51538 94 55638 95 60041 96 64701 97 69704 98 75137 99 80961 100 87134 101 93749 102 100914 103 108587 104 116722 105 125430 106 134838 107 144899 108 155572 109 166982 110 179280 111 192424 112 206362 113 221251 114 237264 115 254361 116 272492 117 291841 118 312612 119 334773 120 358265 121 383314 122 410158 123 438768 124 469096 125 501403 126 535974 127 572789 128 611801 129 653323 130 697694 131 744899 132 794916 133 848104 134 904870 135 965214 136 1029126 137 1097038 138 1169430 139 1246322 140 1327738 141 1414185 142 1506228 143 1603926 144 1707322 145 1817034 146 1933722 147 2057490 148 2188432 149 2327275 150 2474799 151 2631170 152 2796528 153 2971749 154 3157752 155 3354776 156 3563048 157 3783593 158 4017508 159 4265124 160 4526761 161 4803641 162 5097069 163 5407487 164 5735356 165 6082107 166 6449298 167 6837521 168 7247382 169 7680597 170 8139010 171 8623402 172 9134578 173 9674571 174 10245570 175 10848599 176 11484684 177 12156267 178 12865938 179 13615013 180 14404818 181 15238250 182 16118388 183 17046910 184 18025494 185 19057603 186 20146896 187 21295476 188 22505490 189 23781034 190 25126472 191 26544433 192 28037614 193 29610896 194 31269466 195 33016587 196 34855650 197 36792441 198 38833128 199 40981766 200 43242553 201 45622393 202 48128598 203 50766176 204 53540328 205 56459256 206 59531634 207 62763645 208 66161668 209 69735479 210 73495354 211 77448872 212 81603876 213 85971960 214 90565326 215 95393240 216 100465281 217 105795223 218 111397542 219 117283504 220 123464820 221 129957800 222 136779630 223 143943995 224 151465114 225 159362339 226 167656038 227 176362777 228 185499812 229 195090062 230 205157666 231 215722659 232 226805862 233 238434463 234 250637022 235 263437701 236 276861616 237 290940958 238 305709516 239 321196384 240 337431738 241 354453707 242 372302237 243 391012250 244 410620012 245 431170588 246 452711214 247 475283728 248 498931576 249 523708032 250 549668899 251 576864189 252 605345930 253 635176998 254 666423286 255 699144504 256 733402760 257 769272287 258 806830806 259 846149488 260 887302412 261 930377109 262 975465192 263 1022651395 264 1072023840 265 1123685748 266 1177745000 267 1234302318 268 1293462454 269 1355346957 270 1420082807 271 1487789564 272 1558591500 273 1632631700 274 1710059526 275 1791016663 276 1875650442 277 1964129069 278 2056628152 279 2153315377 280 2254365098 281 2359974994 282 2470351362 283 2585692391 284 2706204228 285 2832118932 286 2963678688 287 3101117488 288 3244678653 289 3394634527 290 3551269178 291 3714858538 292 3885689524 293 4064081447 294 4250367267 295 4444872036 296 4647933586 297 4859926134 298 5081239638 299 5312256546 300 5553374302 301 5805031018 302 6067683128 303 6341780130 304 6627789028 305 6926222452 306 7237614258 307 7562492129 308 7901404344 309 8254950154 310 8623753568 311 9008433449 312 9409632750 313 9828051590 314 10264418786 315 10719459384 316 11193926692 317 11688637987 318 12204443898 319 12742193142 320 13302767328 321 13887119973 322 14496243096 323 15131129224 324 15792809230 325 16482394679 326 17201041706 327 17949910012 328 18730203786 329 19543218032 330 20390299176 331 21272800958 332 22192128906 333 23149790515 334 24147352830 335 25186394745 336 26268555254 337 27395588084 338 28569315775 339 29791578153 340 31064284980 341 32389474878 342 33769266168 343 35205800998 344 36701302606 345 38258139324 346 39878771502 347 41565691217 348 43321484628 349 45148901156 350 47050796510 351 49030067644 352 51089720256 353 53232944222 354 55463051844 355 57783408042 356 60197503532 357 62709036612 358 65321846724 359 68039839379 360 70867065293 361 73807809531 362 76866519630 363 80047725020 364 83356122956 365 86796674936 366 90374529690 367 94094936357 368 97963337742 369 101985474987 370 106167304718 371 110514905642 372 115034580104 373 119732966993 374 124616953280 375 129693573405 376 134970119538 377 140454264087 378 146153964570 379 152077355738 380 158232869316 381 164629366456 382 171276035940 383 178182278571 384 185357836731 385 192812938416 386 200558187602 387 208604440801 388 216962947420 389 225645505691 390 234664345402 391 244031995872 392 253761437821 393 263866272744 394 274360597062 395 285258861084 396 296576033820 397 308327785973 398 320530355980 399 333200398943 400 346355165408 401 360012699645 402 374191696578 403 388911340288 404 404191498252 405 420052935456 406 436517162436 407 453606262604 408 471343102794 409 489751565504 410 508856386598 411 528682971393 412 549257622934 413 570607793374 414 592761911370 415 615749186283 416 639599855182 417 664345455937 418 690018642864 419 716652978843 420 744283202982 421 772945526366 422 802677436372 423 833517475647 424 865505532102 425 898683159801 426 933093370860 427 968780400742 428 1005790023190 429 1044169897188 430 1083969347114 431 1125239113216 432 1168031693434 433 1212401719409 434 1258405723600 435 1306101874743 436 1355550349204 437 1406813737698 438 1459956799710 439 1515046183268 440 1572150827672 441 1631342404818 442 1692695059260 443 1756285112515 444 1822191500000 445 1890496249224 446 1961284205858 447 2034642721968 448 2110662129514 449 2189436259708 450 2271062153775 451 2355639735078 452 2443272323008 453 2534067195760 454 2628135286902 455 2725590840277 456 2826551967744 457 2931141259877 458 3039485467542 459 3151715139381 460 3267965228118 461 3388375751947 462 3513091462440 463 3642261463811 464 3776039871640 465 3914586530670 466 4058066667966 467 4206650494491 468 4360513921244 469 4519839337528 470 4684815250454 471 4855635868771 472 5032501880628 473 5215621299481 474 5405209088700 475 5601486728816 476 5804683062724 477 6015035214213 478 6232788199296 479 6458194476952 480 6691514867375 481 6933019550959 482 7182987666074 483 7441706844258 484 7709474209226 485 7986597461656 486 8273394466311 487 8570192771633 488 8877330696894 489 9195158511604 490 9524038012455 491 9864342028831 492 10216455607164 493 10580777291826 494 10957718695280 495 11347703990601 496 11751171201352 497 12168573595087 498 12600379247238 499 13047070523696 500 13509145486232 501 13987119407871 502 14481524334264 503 14992908558901 504 15521838153738 505 16068898619967 506 16634694448152 507 17219848590252 508 17825004127690 509 18450826068505 510 19098000911862 511 19767236119972 512 20459261936259 513 21174833344048 514 21914729638902 515 22679753905116 516 23470734999590 517 24288529684860 518 25134022217188 519 26008123831737 520 26911774907894 521 27845947294641 522 28811643919482 523 29809898288999 524 30841776853988 525 31908381543634 526 33010849404666 527 34150352124202 528 35328098612892 529 36545337770506 530 37803358161570 531 39103487570487 532 40447095824024 533 41835597809368 534 43270453197702 535 44753166041511 536 46285287858554 537 47868420929349 538 49504218077982 539 51194382324187 540 52940670255486 541 54744895628966 542 56608929225160 543 58534698567142 544 60524191609050 545 62579460673396 546 64702622391948 547 66895857507401 548 69161414911464 549 71501615947600 550 73918854459552 551 76415596691847 552 78994385711826 553 81657846115771 554 84408684203226 555 87249687997527 556 90183732090988 557 93213782792327 558 96342898451760 559 99574229624470 560 102911024379530 561 106356633935814 562 109914513160842 563 113588220905511 564 117381425823702 565 121297912543635 566 125341582372130 567 129516453830251 568 133826669033724 569 138276500456109 570 142870351869784 571 147612759117614 572 152508397112600 573 157562087249082 574 162778798622076 575 168163649071860 576 173721912865540 577 179459028823481 578 185380601858739 579 191492404338562 580 197800384519584 581 204310675458230 582 211029596922702 583 217963657119312 584 225119561957330 585 232504224826047 586 240124768931694 587 247988529446175 588 256103063687274 589 264476161848472 590 273115849825092 591 282030391848399 592 291228301672876 593 300718354360462 594 310509589662096 595 320611315210602 596 331033118819492 597 341784881426860 598 352876781113788 599 364319296935236 600 376123222443963 601 388299679916192 602 400860125092848 603 413816351739403 604 427180506524152 605 440965104652758 606 455183035436298 607 469847567678933 608 484972366050952 609 500571508279713 610 516659491654130 611 533251239354416 612 550362118477428 613 568007958940313 614 586205061050622 615 604970202904440 616 624320660234136 617 644274227206262 618 664849225193550 619 686064511387010 620 707939500656184 621 730494188434785 622 753749160854292 623 777725604730306 624 802445331642380 625 827930803129186 626 854205142354930 627 881292145651824 628 909216309052264 629 938002856029414 630 967677750897166 631 998267712107786 632 1029800241491812 633 1062303654812104 634 1095807097114350 635 1130340558004496 636 1165934903882796 637 1202621911598229 638 1240434286000976 639 1279405677447117 640 1319570717339995 641 1360965055211461 642 1403625378747162 643 1447589433799079 644 1492896063582720 645 1539585249538137 646 1587698134138032 647 1637277043719103 648 1688365531715457 649 1741008423699936 650 1795251843309962 651 1851143238248858 652 1908731427978994 653 1968066653376901 654 2029200606159714 655 2092186458444114 656 2157078915363888 657 2223934269826735 658 2292810435858552 659 2363766982154391 660 2436865190139348 661 2512168114354634 662 2589740620196156 663 2669649421935732 664 2751963146796030 665 2836752401557529 666 2924089815211902 667 3014050081989042 668 3106710032081362 669 3202148705114680 670 3300447398305982 671 3401689715088458 672 3505961643181638 673 3613351635648206 674 3723950665199066 675 3837852279080708 676 3955152685263582 677 4075950841872959 678 4200348518365626 679 4328450357414872 680 4460363970064034 681 4596200034414102 682 4736072364464064 683 4880097979815589 684 5028397210731860 685 5181093807044955 686 5338315015551788 687 5500191658445572 688 5666858249314138 689 5838453113340762 690 6015118474235286 691 6197000542402262 692 6384249643027988 693 6577020348745980 694 6775471577204334 695 6979766690084301 696 7190073634540602 697 7406565089636187 698 7629418575754686 699 7858816565710005 700 8094946640941210 701 8338001653144209 702 8588179846881426 703 8845684984153744 704 9110726516889300 705 9383519765362938 706 9664286055486318 707 9953252858369792 708 10250653980807912 709 10556729762229998 710 10871727228325780 711 11195900247285331 712 11529509740153242 713 11872823898248780 714 12226118354945844 715 12589676360466534 716 12963789014176152 717 13348755504595266 718 13744883301363576 719 14152488350655833 720 14571895331699580 721 15003437921732971 722 15447459010386581 723 15904310918015446 724 16374355678964860 725 16857965334052109 726 17355522169854711 727 17867418962489321 728 18394059290404844 729 18935857857247007 730 19493240758789766 731 20066645754967864 732 20656522615266956 733 21263333475107843 734 21887553133461430 735 22529669356234563 736 23190183257632422 737 23869609693540048 738 24568477593162990 739 25287330297202040 740 26026725978912964 741 26787238078302428 742 27569455671503652 743 28373983847531099 744 29201444173136088 745 30052475172041454 746 30927732736133882 747 31827890544992463 748 32753640579065448 749 33705693648577450 750 34684779851067581 751 35691649038314498 752 36727071382816018 753 37791837961490166 754 38886761264544204 755 40012675714905332 756 41170438293500294 757 42360929183370815 758 43585052335396760 759 44843736045865248 760 46137933646597448 761 47468624215689250 762 48836813206162842 763 50243533087900174 764 51689844109281804 765 53176835081374737 766 54705624076231818 767 56277359140054638 768 57893219133672220 769 59554414597710395 770 61262188527927256 771 63017817167188047 772 64822610932857748 773 66677915371225887 774 68585112018047106 775 70545619277681642 776 72560893446282114 777 74632429764599804 778 76761763372716966 779 78950470285568462 780 81200168521707996 781 83512519264513548 782 85889227921043108 783 88332045204083592 784 90842768377258020 785 93423242535671785 786 96075361779815328 787 98801070415328273 788 101602364326297972 789 104481292387470351 790 107439957765257828 791 110480519247536710 792 113605192758161040 793 116816252914098931 794 120116034466800114 795 123506933775607443 796 126991410477816532 797 130571989205411223 798 134251261181407896 799 138031885851829992 800 141916592727058227 801 145908183274326828 802 150009532685110290 803 154223591682129958 804 158553388549316450 805 163002031217808846 806 167572709222095040 807 172268695700165022 808 177093349631118414 809 182050118134191521 810 187142538633119075 811 192374241069375260 812 197748950368361196 813 203270488972887712 814 208942779237208224 815 214769845875271826 816 220755818678487540 817 226904935307233963 818 233221543938131410 819 239710105971434030 820 246375199025650224 821 253221520012949163 822 260253888065616858 823 267477247529111423 824 274896671261294454 825 282517364020185564 826 290344665698095464 827 298384054629524337 828 306641151225497598 829 315121721704890566 830 323831681667585930 831 332777099749281901 832 341964201624405184 833 351399374115323539 834 361089169138949640 835 371040307743713463 836 381259684517820832 837 391754372113998136 838 402531625607400276 839 413598886953467950 840 424963789841888614 841 436634164678225405 842 448618043394693382 843 460923664371447804 844 473559477780563176 845 486534151069895288 846 499856574272414814 847 513535865437641233 848 527581376514263040 849 542002699386032746 850 556809671729798214 851 572012383008396856 852 587621180945281116 853 603646678167055727 854 620099758665287748 855 636991584407191569 856 654333602460786306 857 672137552304025861 858 690415472950811568 859 709179710241321146 860 728442924681906722 861 748218099486541266 862 768518548433383572 863 789357923902621589 864 810750225501516879 865 832709808910282920 866 855251394541973458 867 878390076402324092 868 902141331577166240 869 926521029961768240 870 951545443803927966 871 977231257467505684 872 1003595577866865398 873 1030655945166356362 874 1058430343294197048 875 1086937210699314626 876 1116195451825635764 877 1146224448876676427 878 1177044073396315084 879 1208674698117200163 880 1241137209576610044 881 1274453021050277084 882 1308644085305374587 883 1343732907648250787 884 1379742559793338904 885 1416696694080279987 886 1454619557514625386 887 1493536006133018305 888 1533471520247278398 889 1574452220069843965 890 1616504881168739678 891 1659656950279692855 892 1703936562059194222 893 1749372556255170734 894 1795994494714946970 895 1843832678786177562 896 1892918167725425514 897 1943282797564061292 898 1994959199821179498 899 2047980820648811794 900 2102381941056533380 901 2158197697636794972 902 2215464103149322944 903 2274218067580892900 904 2334497420361707886 905 2396340933129996943 906 2459788342370253576 907 2524880372574087089 908 2591658760640799398 909 2660166280878075087 910 2730446769893805700 911 2802545152062253031 912 2876507466319436588 913 2952380893615409007 914 3030213784278316858 915 3110055686009515782 916 3191957373304288564 917 3275970877591502350 918 3362149517309314062 919 3450547928674042184 920 3541222097978442222 921 3634229394676818958 922 3729628604434362702 923 3827479962937742456 924 3927845191346926440 925 4030787532608045855 926 4136371787763125866 927 4244664353095613785 928 4355733259037643618 929 4469648210019500834 930 4586480624353471792 931 4706303675035137000 932 4829192332436323520 933 4955223408028904874 934 5084475598186044198 935 5217029528990195885 936 5352967803072885510 937 5492375047582229837 938 5635337962276997744 939 5781945368725196416 940 5932288261685588442 941 6086459861722760137 942 6244555668004628478 943 6406673512311398250 944 6572913615390528632 945 6743378644660894038 946 6918173772162671016 947 7097406733835702297 948 7281187891319838428 949 7469630295230773144 950 7662849748753170032 951 7860964872690249846 952 8064097173225264420 953 8272371111296484328 954 8485914172370060946 955 8704856937809378778 956 8929333159161300464 957 9159479834206627026 958 9395437283499113640 959 9637349228654045655 960 9885362873775077760 961 10139628988809891540 962 10400301993496119844 963 10667540043224199957 964 10941505118277600148 965 11222363115181510530 966 11510283938755822536 967 11805441596267898881 968 12108014295221047281 969 12418184543447596947 970 12736139250033708614 971 13062069828543835497 972 13396172304160025278 973 13738647423339853894 974 14089700764448440638 975 14449542850908434980 976 14818389268566497368 977 15196460785812064670 978 15583983474828772110 979 15981188835602417670 980 16388313924471443060 981 16805601485684650570 982 17233300084268130048 983 17671664241909282911 984 18120954577735781790 985 18581437952380029603 986 19053387613548991796 987 19537083344895736278 988 20032811620166941688 989 20540865760939439652 990 21061546096080008616 991 21595160124817573112 992 22142022685503431864 993 22702456128291668038 994 23276790489784389504 995 23865363671628586290 996 24468521625246718302 997 25086618540848581655 998 25720017038675759960 999 26369088364567854361 1000 27034212592144599427