-1 1 0 0 1 2 2 2 3 4 4 5 5 7 6 9 7 13 8 16 9 22 10 27 11 36 12 43 13 56 14 68 15 87 16 104 17 130 18 156 19 193 20 230 21 281 22 333 23 404 24 477 25 572 26 673 27 802 28 940 29 1113 30 1299 31 1531 32 1780 33 2085 34 2418 35 2820 36 3259 37 3784 38 4362 39 5047 40 5799 41 6685 42 7662 43 8806 44 10066 45 11532 46 13152 47 15026 48 17098 49 19482 50 22120 51 25143 52 28487 53 32305 54 36531 55 41337 56 46654 57 52682 58 59352 59 66892 60 75228 61 84625 62 95014 63 106697 64 119603 65 134080 66 150069 67 167965 68 187716 69 209778 70 234114 71 261246 72 291150 73 324433 74 361096 75 401830 76 446668 77 496408 78 551124 79 611731 80 678348 81 752035 82 832977 83 922388 84 1020530 85 1128801 86 1247564 87 1378428 88 1521867 89 1679737 90 1852659 91 2042770 92 2250858 93 2479388 94 2729361 95 3003609 96 3303381 97 3631945 98 3990854 99 4383864 100 4812875 101 5282229 102 5794248 103 6353926 104 6964081 105 7630467 106 8356500 107 9148799 108 10011469 109 10952140 110 11975730 111 13091024 112 14303890 113 15624445 114 17059680 115 18621228 116 20317388 117 22161544 118 24163527 119 26338726 120 28698735 121 31261262 122 34039966 123 37055199 124 40323004 125 43866769 126 47705328 127 51865531 128 56369418 129 61247828 130 66526521 131 72240887 132 78420966 133 85107368 134 92335088 135 100150683 136 108594846 137 117720952 138 127576260 139 138221914 140 149712706 141 162118674 142 175503273 143 189946670 144 205522246 145 222321726 146 240429902 147 259951653 148 280984810 149 303649258 150 328057761 151 354347287 152 382647644 153 413115249 154 445899414 155 481178644 156 519124489 157 559940590 158 603823882 159 651006537 160 701714385 161 756212024 162 814758222 163 877654345 164 945196606 165 1017728103 166 1095587661 167 1179165662 168 1268849316 169 1365082613 170 1468307726 171 1579029335 172 1697751952 173 1825048973 174 1961495646 175 2107743067 176 2264446616 177 2432345286 178 2612185239 179 2804804789 180 3011052798 181 3231879814 182 3468250922 183 3721243349 184 3991953528 185 4281601678 186 4591432692 187 4922828046 188 5277200218 189 5656112537 190 6061166658 191 6494130808 192 6956819977 193 7451233225 194 7979426102 195 8543657487 196 9146253945 197 9789766799 198 10476827853 199 11210317339 200 11993210566 201 12828757625 202 13720320342 203 14671564384 204 15686286156 205 16768618179 206 17922845352 207 19153624353 208 20465788760 209 21864583584 210 23355458526 211 24944318569 212 26637304834 213 28441062426 214 30362508162 215 32409116660 216 34588674459 217 36909585647 218 39380611590 219 42011197280 220 44811196062 221 47791218315 222 50962340250 223 54336476275 224 57926071304 225 61744498471 226 65805734136 227 70124782440 228 74717332358 229 79600211116 230 84791022280 231 90308629893 232 96172776900 233 102404602216 234 109026238539 235 116061364383 236 123534780662 237 131473000157 238 139903801872 239 148856860332 240 158363277018 241 168456252433 242 179170593520 243 190543431268 244 202613703466 245 215422921094 246 229014625497 247 243435206644 248 258733334076 249 274960830855 250 292172077266 251 310424944177 252 329780168864 253 350302352064 254 372059305090 255 395123114736 256 419569461278 257 445478756137 258 472935429924 259 502029147776 260 532854067132 261 565510136457 262 600102322026 263 636741995700 264 675546130635 265 716638784613 266 760150264308 267 806218710639 268 854989231804 269 906615598171 270 961259343915 271 1019091579151 272 1080292060630 273 1145051129744 274 1213568752665 275 1286056592970 276 1362737022318 277 1443845337658 278 1529628743204 279 1620348722597 280 1716279993726 281 1817713047492 282 1924953076965 283 2038322694583 284 2158160838186 285 2284825680018 286 2418693512067 287 2560161860663 288 2709648354546 289 2867594060726 290 3034462338650 291 3210742413584 292 3396948221458 293 3593622237881 294 3801334318533 295 4020685802583 296 4252308355016 297 4496868365352 298 4755065798385 299 5027638910356 300 5315363116153 301 5619056047511 302 5939576445206 303 6277829584974 304 6634766205310 305 7011388329537 306 7408748240514 307 7827954728869 308 8270172127910 309 8736627021446 310 9228607353186 311 9747469629421 312 10294638119682 313 10871612593192 314 11479967629092 315 12121360927677 316 12797532751570 317 13510314857038 318 14261630089014 319 15053501980800 320 15888054529190 321 16767522515940 322 17694251491332 323 18670708873934 324 19699484175469 325 20783300940872 326 21925017250022 327 23127638564264 328 24394318545297 329 25728372881034 330 27133280465250 331 28612698280645 332 30170462988582 333 31810606954577 334 33537360301905 335 35355168170692 336 37268693295848 337 39282834599548 338 41402730359238 339 43633778240592 340 45981639129024 341 48452258720462 342 51051872096226 343 53787026997284 344 56664589231888 345 59691767770605 346 62876121084126 347 66225584206339 348 69748476110484 349 73453528901632 350 77349896348688 351 81447185379649 352 85755465899991 353 90285304779792 354 95047777100715 355 100054502838327 356 105317659695246 357 110850022700421 358 116664978799644 359 122776569610832 360 129199507961079 361 135949224058413 362 143041884181168 363 150494440546843 364 158324652380890 365 166551139788124 366 175193407448208 367 184271902818958 368 193808042730358 369 203824276278582 370 214344114614226 371 225392198914140 372 236994333688778 373 249177560252731 374 261970193905046 375 275401903352448 376 289503752150859 377 304308284575210 378 319849571744058 379 336163304469343 380 353286844526522 381 371259325063991 382 390121707521442 383 409916890224740 384 430689771503151 385 452487367149438 386 475358880334432 387 499355828666609 388 524532121558282 389 550944197682251 390 578651110500357 391 607714676979162 392 638199572057252 393 670173489555024 394 703707246424767 395 738874956864814 396 775754147273538 397 814425944664019 398 854975203321962 399 897490708706089 400 942065316900092 401 988796175284226 402 1037784875965146 403 1089137694607456 404 1142965759131630 405 1199385308211267 406 1258517876639580 407 1320490575119637 408 1385436293823840 409 1453494005241382 410 1524808987584686 411 1599533152600887 412 1677825290624704 413 1759851425419746 414 1845785082830112 415 1935807674883933 416 2030108794166745 417 2128886629605206 418 2232348288863898 419 2340710248423067 420 2454198706499658 421 2573050070249446 422 2697511341923354 423 2827840646252214 424 2964307652783160 425 3107194146757216 426 3256794490817241 427 3413416242955376 428 3577380661055952 429 3749023371784368 430 3928694921717136 431 4116761501355310 432 4313605546911892 433 4519626523975282 434 4735241584362892 435 4960886414323200 436 5197015951236322 437 5444105301642030 438 5702650522963104 439 5973169617071062 440 6256203382641610 441 6552316490434605 442 6862098412352640 443 7186164585105475 444 7525157422549514 445 7879747574947113 446 8250635031704226 447 8638550484010827 448 9044256525683284 449 9468549127601367 450 9912258944991378 451 10376252912745777 452 10861435668170256 453 11368751277002405 454 11899184781380715 455 12453764067159193 456 13033561547656350 457 13639696183712086 458 14273335314630170 459 14935696843332102 460 15628051226837520 461 16351723839857151 462 17108097138151974 463 17898613214962489 464 18724776151671258 465 19588154782611945 466 20490385248620142 467 21433173986991915 468 22418300504766637 469 23447620611936740 470 24523069432655150 471 25646664901222565 472 26820511030875645 473 28046801693622109 474 29327824167835038 475 30665963224659793 476 32063704977339476 477 33523641298709439 478 35048473997000517 479 36641019590856780 480 38304213838336329 481 40041116897965057 482 41854918239770642 483 43748942223110574 484 45726653420865209 485 47791662647185442 486 49947732728426385 487 52198785016540375 488 54548905642987294 489 57002352556288523 490 59563562297997723 491 62237157605921537 492 65027954754312012 493 67940971767488694 494 70981436369716960 495 74154794857428546 496 77466720707815534 497 80923124161584765 498 84530161543122153 499 88294245609726223 500 92222055640326004 501 96320548611464097 502 100596970115981916 503 105058866430660534 504 109714096331066946 505 114570844120762890 506 119637632413633996 507 124923336199941571 508 130437196672984834 509 136188836413054250 510 142188274341209202 511 148445942108394194 512 154972700265507490 513 161779855951622807 514 168879180376385922 515 176282927908450968 516 184003854973632128 517 192055240652381553 518 200450907105051380 519 209205241795520298 520 218333219563457637 521 227850426600116800 522 237773084296653300 523 248118075107660440 524 258902968314452844 525 270146047922203616 526 281866340487682002 527 294083645206881750 528 306818563968080076 529 320092533798712187 530 333927859316826122 531 348347747718682662 532 363376343814809192 533 379038767753485097 534 395361152841682131 535 412370686214266494 536 430095649655254458 537 448565463438332238 538 467810730380094564 539 487863283094395280 540 508756231526689320 541 530524013882898052 542 553202447912692816 543 576828785793040847 544 601441769448380874 545 627081689689942594 546 653790445882330200 547 681611609662145380 548 710590489283656494 549 740774198264350049 550 772211724767197719 551 804954005546589894 552 839054000751379212 553 874566773572376867 554 911549570878940296 555 950061908998933341 556 990165660632313448 557 1031925147226354009 558 1075407232642580190 559 1120681422624238282 560 1167819965728229082 561 1216897960418489274 562 1267993463812404921 563 1321187606973073883 564 1376564712060273738 565 1434212416436736000 566 1494221798857239750 567 1556687513049202343 568 1621707923620122639 569 1689385249821240556 570 1759825711903539726 571 1833139685825126935 572 1909441860839606450 573 1988851405963473300 574 2071492139638094826 575 2157492708833012933 576 2246986771684328857 577 2340113190173697043 578 2437016226711845250 579 2537845751401465238 580 2642757453605272332 581 2751913064874322566 582 2865480586615700832 583 2983634529846309312 584 3106556160156376138 585 3234433755532882671 586 3367462869901925769 587 3505846610356017166 588 3649795920651364467 589 3799529879269755290 590 3955276004346422738 591 4117270574100503013 592 4285758954775832008 593 4460995945084567671 594 4643246128857460221 595 4832784245263608660 596 5029895567989031146 597 5234876303122278701 598 5448033996811003956 599 5669687962838798233 600 5900169720849573009 601 6139823455786193419 602 6389006488922420440 603 6648089771489276237 604 6917458390914787096 605 7197512101130301357 606 7488665866589979876 607 7791350431927176556 608 8106012906509380026 609 8433117376305125727 610 8773145531926659510 611 9126597325771459127 612 9493991646715212780 613 9875867025809860909 614 10272782361014432936 615 10685317674964480080 616 11114074893368954502 617 11559678658615094845 618 12022777165716861684 619 12504043035785790823 620 13004174213691727822 621 13523894905715124972 622 14063956543375089672 623 14625138789883247166 624 15208250574908799310 625 15814131174779825486 626 16443651323291443810 627 17097714370948621734 628 17777257477283187778 629 18483252854804476467 630 19216709048675350446 631 19978672271434845001 632 20770227776294279910 633 21592501289121309776 634 22446660482056338771 635 23333916509701782806 636 24255525590228328438 637 25212790653198823533 638 26207063035835385538 639 27239744250426167292 640 28312287803960169903 641 29426201093619493930 642 30583047358561164702 643 31784447712589663861 644 33032083237476674060 645 34327697162541321627 646 35673097109552014164 647 37070157429617517832 648 38520821610412872084 649 40027104781506148920 650 41591096295395666129 651 43214962413167993236 652 44900949071629601056 653 46651384762014756401 654 48468683496344620356 655 50355347892782488344 656 52313972355260862676 657 54347246380019856068 658 56457957963511639602 659 58648997145659577487 660 60923359662083864454 661 63284150740688404465 662 65734589015355634184 663 68278010593609660398 664 70917873250106945079 665 73657760784342657671 666 76501387513521872904 667 79452602940576434580 668 82515396567343935214 669 85693902894550146131 670 88992406577655772650 671 92415347781940308648 672 95967327704905438398 673 99653114311176263029 674 103477648246981451102 675 107446048981273559677 676 111563621139546452801 677 115835861079374957099 678 120268463672686707474 679 124867329345839895896 680 129638571341447302462 681 134588523255157392441 682 139723746810240828930 683 145051039925422875358 684 150577445037695911964 685 156310257737879039367 686 162257035679523074424 687 168425607821355752882 688 174824083962708248872 689 181460864634651650755 690 188344651305106488216 691 195484456963298765095 692 202889617040627470038 693 210569800736077930566 694 218535022702028439486 695 226795655161467023976 696 235362440411229770742 697 244246503785287317312 698 253459367031437352348 699 263012962178572794951 700 272919645846613568356 701 283192214079554257339 702 293843917652430484674 703 304888477936085176724 704 316340103269238849726 705 328213505925327108588 706 340523919622298709333 707 353287117666579934788 708 366519431678077660950 709 380237770991337590383 710 394459642678400770538 711 409203172292561956391 712 424487125277237687727 713 440330929143419515525 714 456754696358581390968 715 473779248054982340829 716 491426138498893778004 717 509717680433361410856 718 528676971234693506937 719 548327920000167475036 720 568695275505814335732 721 589804655156878559006 722 611682574868489536042 723 634356480004482257378 724 657854777310593046478 725 682206867975554047359 726 707443181755018950747 727 733595212297688069551 728 760695553607293668300 729 788777937785929076707 730 817877273991137631942 731 848029688758644994814 732 879272567621938316846 733 911644598187274518646 734 945185814594146740268 735 979937643526803674925 736 1015942951705721142000 737 1053246095031962445508 738 1091892969312248759109 739 1131931062745364006983 740 1173409510096696597160 741 1216379148749593880603 742 1260892576559380091592 743 1307004211707147045718 744 1354770354478292969478 745 1404249251171753431734 746 1455501160064109997942 747 1508588419643777119668 748 1563575519038759122024 749 1620529170862877653884 750 1679518386403374620670 751 1740614553384956968636 752 1803891516232720421000 753 1869425659079674535295 754 1937295991440969873846 755 2007584236811721009388 756 2080374924110335351826 757 2155755482235954730903 758 2233816337661889080454 759 2314651015345932442002 760 2398356242879586145590 761 2485032058169962243283 762 2574781920576730633578 763 2667712825811396731172 764 2763935424521823200854 765 2863564144883460106716 766 2966717319120978068655 767 3073517314296644858281 768 3184090667290173237232 769 3298568224321991675989 770 3417085284945973473136 771 3539781750879961046127 772 3666802279601727386914 773 3798296443095911173709 774 3934418891681498450208 775 4075329523323444829207 776 4221193658360294267170 777 4372182220070348858077 778 4528471921010910443670 779 4690245455573060081316 780 4857691698689574251454 781 5031005911159356993357 782 5210389951529511877712 783 5396052495020401225221 784 5588209259438824694412 785 5787083238587744114089 786 5992904943122216480886 787 6205912649384212315681 788 6426352656171073979582 789 6654479549995774955040 790 6890556478799433994620 791 7134855434701028874894 792 7387657545751116614547 793 7649253377302658334157 794 7919943242972812090532 795 8200037525838388992060 796 8489857009846649435566 797 8789733222115253389075 798 9100008786111668801628 799 9421037786418574664136 800 9753186145085064554922 801 10096832010304600535817 802 10452366157429963927887 803 10820192403102348851174 804 11200728032516293735178 805 11594404240635672089400 806 12001666587394967573412 807 12422975467741111932609 808 12858806596563800114394 809 13309651509411708180900 810 13776018079057459998759 811 14258431048853119448569 812 14757432582955316906628 813 15273582834408462266375 814 15807460531182841184154 815 16359663581205174160056 816 16930809696497648714022 817 17521537037514717645425 818 18132504877814519322562 819 18764394290208654566615 820 19417908854549767524936 821 20093775388357984620945 822 20792744700470116647225 823 21515592368973034107040 824 22263119543631573310004 825 23036153774135942867979 826 23835549864407571523674 827 24662190754355306872234 828 25516988429351765546106 829 26400884858892251111365 830 27314852964739329955886 831 28259897620089752199437 832 29237056680102691650761 833 30247402045404234686453 834 31292040758945743625760 835 32372116137913459468503 836 33488808941108573978698 837 34643338573581995173370 838 35836964328987789512226 839 37070986671531053842576 840 38346748558022311262682 841 39665636802010641719714 842 41029083480559331003474 843 42438567385737909472347 844 43895615521449867535330 845 45401804647777071435143 846 46958762873519732759349 847 48568171299225904831807 848 50231765711453253823212 849 51951338330676147201767 850 53728739613649310415510 851 55565880112766624884208 852 57464732393299728213558 853 59427333011187340966798 854 61455784552338613887796 855 63552257736260972539500 856 65718993585059944951518 857 67958305660768604735830 858 70272582372144221232315 859 72664289354044932188077 860 75135971920620428378488 861 77690257595593124315508 862 80329858720966894063047 863 83057575147612454343892 864 85876297009176679948947 865 88789007582946990961215 866 91798786239235868745542 867 94908811483108675464547 868 98122364090145649104704 869 101442830340263819781340 870 104873705351424082554378 871 108418596517462869090760 872 112081227052017100863886 873 115865439643007310723431 874 119775200219800714603404 875 123814601837756970578124 876 127987868682441759605642 877 132299360198461875789172 878 136753575345381203576112 879 141355156985936054652915 880 146108896409195051028306 881 151019737994161420984432 882 156092784016660984352916 883 161333299605308515538029 884 166746717849606889549784 885 172338645066282813160959 886 178114866227138516144610 887 184081350554851523708271 888 190244257290241545691206 889 196609941637783091951786 890 203184960893138100400406 891 209976080759852863492962 892 216990281859265333815244 893 224234766441153034229674 894 231716965299456998950545 895 239444544901019310104766 896 247425414731977621543382 897 255667734870184172147508 898 264179923788620395303443 899 272970666398628430197736 900 282048922338279302625145 901 291423934515178087453530 902 301105237909396693240394 903 311102668646340203670604 904 321426373345631841148404 905 332086818756356216998747 906 343094801685165327908508 907 354461459228150375546677 908 366198279313429733290578 909 378317111565950894989023 910 390830178501930650687934 911 403750087065059184274652 912 417089840512395995165000 913 430862850662746154848461 914 445082950515979969650946 915 459764407256784290314428 916 474921935651877100291738 917 490570711854912333640407 918 506726387628710493006876 919 523405104999821892108649 920 540623511355699511896672 921 558398775000311635134599 922 576748601179152369463503 923 595691248590349463590095 924 615245546393550700448334 925 635430911734205978785531 926 656267367795694078340444 927 677775562397880104953283 928 699976787155367487529716 929 722892997215053447320568 930 746546831587116630896598 931 770961634090125811792737 932 796161474925316051347230 933 822171172901861456705490 934 849016318329164609028540 935 876723296599195647403341 936 905319312475934028975783 937 934832415116216964859927 938 965291523840143232139656 939 996726454676678292176486 940 1029167947703771493159306 941 1062647695210048091377389 942 1097198370698619217251198 943 1132853658761568375722316 944 1169648285846964319050012 945 1207618051948538195114763 946 1246799863241260209442944 947 1287231765694621128476352 948 1328952979688322520619174 949 1372003935663941506820944 950 1416426310838830660821498 951 1462263067017677476183665 952 1509558489529633969889820 953 1558358227328403152571150 954 1608709334284941438161880 955 1660660311712235472863838 956 1714261152153665224474362 957 1769563384476599085218838 958 1826620120304695873491711 959 1885486101832868707725245 960 1946217751060465307980764 961 2008873220489057641585662 962 2073512445322598469425794 963 2140197197218911525823863 964 2208991139632606302651490 965 2279959884801101403518084 966 2353171052416318743278508 967 2428694330036601166819519 968 2506601535284032854589506 969 2586966679884743467346976 970 2669866035600146614448814 971 2755378202109890604612589 972 2843584176897406208695783 973 2934567427202204370284531 974 3028413964092914960539146 975 3125212418728782316511365 976 3225054120866897060258896 977 3328033179686640963166007 978 3434246566992105144448800 979 3543794202867928581285975 980 3656779043853001335738698 981 3773307173711670441818867 982 3893487896870791838039664 983 4017433834606690206646706 984 4145261024054496129990369 985 4277089020128592159517794 986 4413041000431003132313636 987 4553243873241391450190643 988 4697828388670112047317514 989 4846929253073190574405126 990 5000685246815566698931914 991 5159239345486957646223142 992 5322738844661853944939166 993 5491335488313798793844195 994 5665185600980931908375418 995 5844450223799067030984322 996 6029295254505068510160078 997 6219891591533253066134986 998 6416415282313700091144840 999 6619047675902011359206348 1000 6827975580055873555713954