-1 1 0 0 1 1 2 3 3 3 4 4 5 7 6 7 7 9 8 15 9 16 10 20 11 29 12 32 13 40 14 55 15 61 16 74 17 99 18 111 19 134 20 170 21 192 22 230 23 285 24 323 25 382 26 466 27 530 28 622 29 746 30 848 31 988 32 1173 33 1331 34 1540 35 1810 36 2052 37 2363 38 2752 39 3114 40 3568 41 4129 42 4663 43 5318 44 6118 45 6895 46 7834 47 8963 48 10078 49 11410 50 12993 51 14579 52 16452 53 18655 54 20891 55 23506 56 26551 57 29673 58 33294 59 37480 60 41806 61 46784 62 52500 63 58450 64 65256 65 73015 66 81142 67 90384 68 100866 69 111901 70 124380 71 138465 72 153355 73 170118 74 188954 75 208932 76 231328 77 256402 78 283070 79 312854 80 346078 81 381498 82 420928 83 464772 84 511598 85 563563 86 621184 87 682818 88 751026 89 826455 90 907232 91 996406 92 1094782 93 1200231 94 1316372 95 1444208 96 1581345 97 1732068 98 1897619 99 2075315 100 2270232 101 2483915 102 2713372 103 2964602 104 3239522 105 3534829 106 3857610 107 4210237 108 4589080 109 5002513 110 5453468 111 5937999 112 6465976 113 7041025 114 7658900 115 8331232 116 9062508 117 9848186 118 10701984 119 11629439 120 12625772 121 13707141 122 14880366 123 16140501 124 17506588 125 18987014 126 20576751 127 22298236 128 24161771 129 26162400 130 28326540 131 30666824 132 33178550 133 35892844 134 38825172 135 41971321 136 45367960 137 49033986 138 52966034 139 57207282 140 61780774 141 66684415 142 71969058 143 77662789 144 83765306 145 90336480 146 97410490 147 104989548 148 113144136 149 121915777 150 131310037 151 141409906 152 152265792 153 163887677 154 176373250 155 189783596 156 204134488 157 219540914 158 236076812 159 253765343 160 272741860 161 293095788 162 314859679 163 338192844 164 363203246 165 389935317 166 418576580 167 449257229 168 482036519 169 517135166 170 554709996 171 594838745 172 637781164 173 683725869 174 732773502 175 785229739 176 841321198 177 901176689 178 965155880 179 1033530723 180 1106464630 181 1184380738 182 1267604958 183 1356343002 184 1451092606 185 1552243944 186 1660054220 187 1775108772 188 1897874180 189 2028670214 190 2168185084 191 2316976089 192 2475438708 193 2644381933 194 2824470754 195 3016192007 196 3220496388 197 3438176526 198 3669829294 199 3916571642 200 4179347293 201 4458885276 202 4756497488 203 5073306455 204 5410199594 205 5768717248 206 6150193236 207 6555704437 208 6987058904 209 7445839882 210 7933350368 211 8451711914 212 9002802032 213 9588193179 214 10210373830 215 10871568203 216 11573669319 217 12319595003 218 13111977658 219 13953090966 220 14846354756 221 15794881648 222 16801396730 223 17869906548 224 19004088033 225 20207200699 226 21483936562 227 22838635218 228 24275188012 229 25799087192 230 27415449860 231 29128913438 232 30945904006 233 32872450064 234 34914068694 235 37078275160 236 39372165584 237 41802292968 238 44377442128 239 47105958699 240 49995614194 241 53056672612 242 56298940783 243 59731621684 244 63366701744 245 67215695280 246 71289485208 247 75602062402 248 80166934820 249 84996954717 250 90108444520 251 95517238230 252 101238494106 253 107291245035 254 113694036840 255 120464725539 256 127625493142 257 135198044587 258 143203388744 259 151667364544 260 160615354544 261 170072048733 262 180067530084 263 190631459285 264 201792820498 265 213586619370 266 226047489692 267 239209420171 268 253113123304 269 267799009967 270 283306896188 271 299684106512 272 316977758110 273 335234446893 274 354509154042 275 374856776379 276 396331791046 277 418998040684 278 442919441124 279 468159623603 280 494792680752 281 522892977094 282 552534768188 283 583803996510 284 616787123710 285 651570726062 286 688254437996 287 726938717994 288 767724419777 289 810726989365 290 856063069480 291 903850046664 292 954221616716 293 1007313124371 294 1063261086295 295 1122220250746 296 1184347560762 297 1249801653173 298 1318761548786 299 1391409118088 300 1467928557668 301 1548526858919 302 1633414645148 303 1722805626725 304 1816939009688 305 1916058562913 306 2020412053972 307 2130275772202 308 2245931673178 309 2367666798474 310 2495800103136 311 2630657512411 312 2772571328446 313 2921909569052 314 3079048758750 315 3244373326885 316 3418307681588 317 3601286542736 318 3793754337634 319 3996200253594 320 4209125905634 321 4433044736101 322 4668520310366 323 4916131096308 324 5176469876240 325 5450185572480 326 5737944897724 327 6040431789597 328 6358393077980 329 6692596747096 330 7043831404284 331 7412956127410 332 7800855059764 333 8208436928009 334 8636689436340 335 9086629893538 336 9559304797792 337 10055849175843 338 10577432919705 339 11125260458373 340 11700635473672 341 12304902600002 342 12939447207564 343 13605765963247 344 14305403520192 345 15039952441302 346 15811130113248 347 16620710026335 348 17470521871452 349 18362535357384 350 19298785652269 351 20281373693536 352 21312557505530 353 22394671342435 354 23530126256308 355 24721509562368 356 25971497191774 357 27282854569754 358 28658544929930 359 30101634349667 360 31615292999276 361 33202913066746 362 34868005911002 363 36614203751823 364 38445388029620 365 40365578074424 366 42378933316850 367 44489892976672 368 46703055602782 369 49023181897779 370 51455346705648 371 54004808734155 372 56677014098692 373 59477761659671 374 62413062193724 375 65489142778718 376 68712626620076 377 72090380886746 378 75629522076983 379 79337611569422 380 83222491289348 381 87292290214590 382 91555636988986 383 96021482531578 384 100699107865231 385 105598355243624 386 110729436757954 387 116102943695804 388 121730097755444 389 127622544646549 390 133792365216196 391 140252348454370 392 147015769023679 393 154096400422639 394 161508811631130 395 169268127438642 396 177390043950638 397 185891150878334 398 194788673469552 399 204100490706054 400 213845485409122 401 224043266507133 402 234714190318484 403 245879740830180 404 257562230963134 405 269784827386675 406 282571963525942 407 295949018412580 408 309942345537760 409 324579721358460 410 339890000243780 411 355903147939550 412 372650728580852 413 390165534165339 414 408481623276026 415 427634849861282 416 447662465586934 417 468603164550387 418 490497657365264 419 513388244660780 420 537318868613986 421 562335736179895 422 588486861924184 423 615822127306243 424 644393957220058 425 674256830263839 426 705467346828666 427 738084963470322 428 772171468635534 429 807791060742331 430 845011145292080 431 883901773991401 432 924535734160326 433 966989413911416 434 1011342202525620 435 1057676592695196 436 1106079119554936 437 1156639720091932 438 1209451849915394 439 1264613502423794 440 1322226524957228 441 1382396751998023 442 1445235111296256 443 1510856894403895 444 1579381908447304 445 1650935676625712 446 1725648660704800 447 1803656433761977 448 1885100983115274 449 1970129882302412 450 2058896487497133 451 2151561351623588 452 2248291343301452 453 2349259869962412 454 2454648412669504 455 2564645589480543 456 2679447408658852 457 2799258934546319 458 2924293292784530 459 3054771957428165 460 3190926559125476 461 3332997829637289 462 3481235927120626 463 3635902398859786 464 3797269062551760 465 3965618374538192 466 4141245560404378 467 4324457430551464 468 4515572796731160 469 4714924785004039 470 4922859583198400 471 5139736911738924 472 5365932534737432 473 5601836937060308 474 5847855856151468 475 6104413008424534 476 6371948693817818 477 6650920396108076 478 6941805743301418 479 7245101037757721 480 7561321933372592 481 7891006650330526 482 8234714429145146 483 8593026294070372 484 8966548544396388 485 9355911131071737 486 9761768516802651 487 10184803468063670 488 10625725353360262 489 11085271111690302 490 11564209371612436 491 12063338670687139 492 12583488545331990 493 13125524005663842 494 13690343676218204 495 14278881021741009 496 14892109209119996 497 15531039170154871 498 16196720979503928 499 16890249137852798 500 17612760558303908 501 18365436114565554 502 19149506382608264 503 19966249553163881 504 20816993170317679 505 21703120372300513 506 22626067733670224 507 23587327216770084 508 24588452956010704 509 25631059034561131 510 26716821673701492 511 27847486609011644 512 29024866807841233 513 30250844924424760 514 31527381320840256 515 32856511733199660 516 34240350023550724 517 35681096903325108 518 37181037558105002 519 38742544730841427 520 40368088210841540 521 42060232429153585 522 43821639911512302 523 45655081601746106 524 47563434442328932 525 49549685239777710 526 51616941897736646 527 53768431000092046 528 56007502136329118 529 58337640126549611 530 60762462627783400 531 63285724972106489 532 65911333473504452 533 68643343081696307 534 71485962791695160 535 74443570130815120 536 77520708888481916 537 80722095162426971 538 84052633133336892 539 87517412903832807 540 91121717253697402 541 94871038819732802 542 98771078082410660 543 102827750910528744 544 107047207274877012 545 111435829427049972 546 116000240322772226 547 120747324010077472 548 125684224051528652 549 130818352925241482 550 136157414241532794 551 141709401467387845 552 147482608415058950 553 153485653455673763 554 159727478613312858 555 166217361263048204 556 172964940525941508 557 179980216809673295 558 187273564851153516 559 194855762494798262 560 202737990767381906 561 210931848415034610 562 219449383285841786 563 228303093038606650 564 237505941340263580 565 247071392094850944 566 257013410899327232 567 267346483085368350 568 278085651059785230 569 289246516635565125 570 300845261121852604 571 312898686066145024 572 325424216605524700 573 338439923830516681 574 351964569247091236 575 366017609311806369 576 380619220319442376 577 395790346933207908 578 411552708088411529 579 427928824680504273 580 444942072545209100 581 462616689938647204 582 480977808331923410 583 500051510259431874 584 519864838609322282 585 540445830863361329 586 561823582271736976 587 584028257216629218 588 607091127272048096 589 631044640207418589 590 655922433719168988 591 681759377724929466 592 708591649746377308 593 736456751339488061 594 765393555081283966 595 795442386935295748 596 826645045750811816 597 859044855448666287 598 892686755030672428 599 927617321562305705 600 963884828117292737 601 1001539342155967702 602 1040632752454755344 603 1081218833428076672 604 1123353352670350596 605 1167094102349921617 606 1212500970591544444 607 1259636059053269338 608 1308563719362667704 609 1359350632314530175 610 1412065936437785452 611 1466781270118576992 612 1523570859446466602 613 1582511658818587574 614 1643683399468019624 615 1707168686878429740 616 1773053154573592430 617 1841425519851351101 618 1912377691782081788 619 1986004939442400330 620 2062405955745549856 621 2141682977144193523 622 2223941967688531068 623 2309292691944151543 624 2397848847635391644 625 2489728267041183032 626 2585053000102229398 627 2683949461368595582 628 2786548650392564552 629 2892986246249473184 630 3003402770293441040 631 3117943827366565530 632 3236760213093122788 633 3360008094101670486 634 3487849272045352826 635 3620451305178709958 636 3757987707874206008 637 3900638239640787879 638 4048589042657647556 639 4202032862600004639 640 4361169365053960056 641 4526205290863839795 642 4697354700487494302 643 4874839320436641074 644 5058888718495548242 645 5249740574052028808 646 5447641057445878432 647 5652845027338516080 648 5865616329714196187 649 6086228213296887598 650 6314963551595183838 651 6552115173541266495 652 6797986318440943032 653 7052890885487865359 654 7317153799307821034 655 7591111508240256206 656 7875112264413102682 657 8169516527789640728 658 8474697511945373460 659 8791041498122294313 660 9118948281737788164 661 9458831770221241368 662 9811120334827297488 663 10176257303964122812 664 10554701618092999476 665 10946928223477327419 666 11353428617124507066 667 11774711564232508326 668 12211303538488636284 669 12663749323899093180 670 13132612800793155280 671 13618477437766888011 672 14121946956201174585 673 14643646191411017842 674 15184221641858805490 675 15744342202739763233 676 16324700109495672800 677 16926011550504591421 678 17549017476747255810 679 18194484635596417146 680 18863206253830215268 681 19556002931089310819 682 20273723772610724448 683 21017247150116016023 684 21787481687532798612 685 22585367502171536758 686 23411877051813345127 687 24268016222007475938 688 25154825686097808740 689 26073381847685181128 690 27024798039731378100 691 28010226014836347186 692 29030856993183882430 693 30087922984690344641 694 31182698422021963898 695 32316501325158350024 696 33490694758928991798 697 34706688622451234562 698 35965940942572299038 699 37269959480347637716 700 38620303691883805566 701 40018586164156019818 702 41466474385309812418 703 42965692893319509938 704 44518024869035240726 705 46125314086643874324 706 47789467268114679012 707 49512455849818607130 708 51296318131078151228 709 53143161854079319958 710 55055166162039465572 711 57034583965521550280 712 59083744769359526308 713 61205056842142487764 714 63401009821881046000 715 65674177813536386900 716 68027221791553142562 717 70462892468559662175 718 72984033689325538246 719 75593585090229484260 720 78294585256968290410 721 81090175443211206855 722 83983602513250024091 723 86978222417201776536 724 90077504265300281300 725 93285033582563045725 726 96604516132720561123 727 100039782382006459060 728 103594791097510838422 729 107273633554076324261 730 111080538424641734192 731 115019875757057044392 732 119096161601477155372 733 123314063367804543494 734 127678404219142639328 735 132194168160818728882 736 136866505909285999038 737 141700739744116909176 738 146702369103725386176 739 151877077014257730448 740 157230735446105684100 741 162769411465706076624 742 168499374277505451058 743 174427101135436674571 744 180559284104885512252 745 186902837775790841034 746 193464905784414294746 747 200252868244714791981 748 207274350196083283892 749 214537228796081061913 750 222049641486095303872 751 229819995243146122218 752 237856974510118104804 753 246169550166726498357 754 254766989661320553516 755 263658865751530653468 756 272855066358303545266 757 282365805660709253905 758 292201633726923231056 759 302373447336442219119 760 312892502128636222332 761 323770423211636174589 762 335019217045876435688 763 346651284745577464468 764 358679433761474192110 765 371116890927608487858 766 383977317024146280368 767 397274819639025319084 768 411023967489508625498 769 425239806364801486330 770 439937873281690251620 771 455134212202839132787 772 470845391488653859796 773 487088519472902717013 774 503881261711173724680 775 521241860083415294570 776 539189149927460929314 777 557742578963548858398 778 576922228202045604190 779 596748830785827877296 780 617243792750396619992 781 638429215905555030717 782 660327918551834760796 783 682963458250613830353 784 706360156864082577258 785 730543123326444640287 786 755538278614685494280 787 781372383148133820906 788 808073061812138582400 789 835668831337853622677 790 864189130281214190088 791 893664346515318027617 792 924125847246924078586 793 955606011814851030913 794 988138261887512212990 795 1021757094364917218982 796 1056498117258510468032 797 1092398082852378372203 798 1129494923762548149104 799 1167827792184281503380 800 1207437096299553231591 801 1248364539790532113501 802 1290653164766503741958 803 1334347391726491746464 804 1379493062851166865928 805 1426137488950085281443 806 1474329493316982023184 807 1524119459154187300229 808 1575559380911940396084 809 1628702912405141879451 810 1683605418756880140044 811 1740324032535441863638 812 1798917706535395765656 813 1859447270662285056738 814 1921975493309849637268 815 1986567139245479888705 816 2053289031896770823606 817 2122210120451665195206 818 2193401543328833903666 819 2266936696368896140301 820 2342891306183976475440 821 2421343499737734366624 822 2502373878989936907202 823 2586065601069611864698 824 2672504454537584339284 825 2761778941083076233521 826 2853980363146573044412 827 2949202907490180275977 828 3047543734599377001022 829 3149103074438268533586 830 3253984318010227954692 831 3362294115177241174872 832 3474142479291794083516 833 3589642887492527869475 834 3708912387718204582304 835 3832071713027513752860 836 3959245391442291520144 837 4090561863003470449957 838 4226153604663062670616 839 4366157250561357918531 840 4510713720048799838996 841 4659968354113826709463 842 4814071047060900295994 843 4973176386505616745090 844 5137443802388522029300 845 5307037711108404464595 846 5482127668588691952380 847 5662888533021415762381 848 5849500622605546276036 849 6042149882881489838961 850 6241028064451711227572 851 6446332895577679641978 852 6658268265086752965318 853 6877044416427302031974 854 7102878136490793883226 855 7335992955512293005626 856 7576619358939036446098 857 7824994993967108359163 858 8081364887984014575884 859 8345981679861379116350 860 8619105845829420193800 861 8901005938148454047601 862 9191958837579634414902 863 9492250000365959914403 864 9802173718970098035733 865 10122033397632861223901 866 10452141822387773273350 867 10792821445866318458067 868 11144404688023215617692 869 11507234231283746745641 870 11881663331595561992976 871 12268056146583942185114 872 12666788058118338417890 873 13078246011983428420238 874 13502828875927712154776 875 13940947792139320499158 876 14393026548119453005252 877 14859501967305200111537 878 15340824294166053771896 879 15837457599091604130261 880 16349880204505910586196 881 16878585105536807027147 882 17424080411978358864831 883 17986889813071023133054 884 18567553036957433591884 885 19166626333050314974356 886 19784682978931823106034 887 20422313782093805681872 888 21080127606335474482042 889 21758751924538590484806 890 22458833366499159186124 891 23181038293298163830081 892 23926053400038705088160 893 24694586313911802249883 894 25487366220830047856090 895 26305144522570644724374 896 27148695489582717055547 897 28018816944550195449620 898 28916330978773319316582 899 29842084664621075515708 900 30796950801098492693376 901 31781828694721196728622 902 32797644936946954537932 903 33845354217266589247503 904 34925940174284408889834 905 36040416243930225592937 906 37189826546075266398956 907 38375246812028793858802 908 39597785309839522360072 909 40858583810961407382893 910 42158818600916845451732 911 43499701488547505062651 912 44882480859823210611812 913 46308442779008326751194 914 47778912089320325836562 915 49295253561591909139577 916 50858873093913421105004 917 52471218911806956787955 918 54133782820121460963676 919 55848101509814473490936 920 57615757866454533917316 921 59438382334455684175875 922 61317654340411055877400 923 63255303719501403721426 924 65253112201963987291370 925 67312914963203386212964 926 69436602178514221195956 927 71626120642534976186354 928 73883475457243281938570 929 76210731726301707795473 930 78610016319175302880096 931 81083519709075173775954 932 83633497819213542770460 933 86262273944270689123412 934 88972240751388183452816 935 91765862291679583685432 936 94645676092824594690518 937 97614295337338540221060 938 100674411053835001089988 939 103828794395709468556620 940 107080299012131814705792 941 110431863434804327335883 942 113886513558981571923674 943 117447365223955636123374 944 121117626812405450228408 945 124900601951392282882396 946 128799692320541899406136 947 132818400482547499391713 948 136960332823290214896532 949 141229202607477243528345 950 145628833060450620697608 951 150163160568218956510924 952 154836238001996037518524 953 159652238073191181564124 954 164615456815912719837970 955 169730317203678268851632 956 175001372801330618852054 957 180433311554496467592570 958 186030959723719181734012 959 191799285859068968742743 960 197743404923124343536070 961 203868582569923301512335 962 210180239470230805973172 963 216683955796868653738285 964 223385475878205163230300 965 230290712904420703301228 966 237405753806458322319878 967 244736864316290003682788 968 252290494087097121616275 969 260073281999764867855102 970 268092061664890716038392 971 276353866992587581673132 972 284865937963316424639828 973 293635726609556944643218 974 302670903073964422026396 975 311979361884444938304114 976 321569228456608026399652 977 331448865682282666382944 978 341626880752107846612116 979 352112132223351931313744 980 362913737184339593430858 981 374041078671477996312548 982 385503813350779640015850 983 397311879307592291109168 984 409475504108930646090948 985 422005213151101729178790 986 434911838128288059767808 987 448206525795330832939288 988 461900747038254785947780 989 476006306079756774054759 990 490535350002215802189036 991 505500378602674890694424 992 520914254398160821599332 993 536790212973707427436308 994 553141873688504775526790 995 569983250549251237554844 996 587328763453400220998976 997 605193249818763705672352 998 623591976398807517476616 999 642540651497201570180389 1000 662055437599199704891552