-1 1 0 2 1 3 2 6 3 9 4 14 5 22 6 30 7 42 8 60 9 81 10 110 11 148 12 194 13 256 14 336 15 433 16 556 17 713 18 904 19 1144 20 1440 21 1798 22 2242 23 2784 24 3438 25 4234 26 5196 27 6353 28 7748 29 9419 30 11414 31 13796 32 16636 33 20004 34 23996 35 28722 36 34296 37 40869 38 48604 39 57678 40 68318 41 80779 42 95332 43 112313 44 132104 45 155117 46 181856 47 212890 48 248828 49 290418 50 338498 51 393976 52 457948 53 531628 54 616360 55 713738 56 825520 57 953666 58 1100466 59 1268461 60 1460490 61 1679822 62 1930096 63 2215382 64 2540340 65 2910149 66 3330598 67 3808274 68 4350508 69 4965499 70 5662504 71 6451830 72 7344996 73 8354961 74 9496156 75 10784662 76 12238508 77 13877788 78 15724846 79 17804675 80 20145080 81 22776934 82 25734728 83 29056771 84 32785538 85 36968369 86 41657790 87 46911989 88 52795692 89 59380596 90 66746034 91 74980120 92 84180348 93 94454458 94 105921904 95 118714676 96 132978528 97 148874810 98 166581548 99 186295143 100 208232668 101 232633396 102 259761044 103 289906606 104 323390500 105 360565548 106 401820536 107 447583139 108 498323752 109 554560062 110 616861012 111 685851752 112 762219430 113 846718475 114 940177046 115 1043504417 116 1157697980 117 1283851476 118 1423164480 119 1576951656 120 1746653292 121 1933847443 122 2140261966 123 2367788050 124 2618495860 125 2894650053 126 3198727096 127 3533435321 128 3901734900 129 4306860154 130 4752345040 131 5242048788 132 5780184524 133 6371351746 134 7020569174 135 7733311286 136 8515549556 137 9373794478 138 10315142276 139 11347327106 140 12478774588 141 13718661345 142 15076981084 143 16564612765 144 18193396246 145 19976215570 146 21927085754 147 24061248726 148 26395278264 149 28947190116 150 31736563172 151 34784671756 152 38114625148 153 41751520291 154 45722608192 155 50057470167 156 54788210176 157 59949664009 158 65579621284 159 71719067080 160 78412444524 161 85707934158 162 93657757022 163 102318503657 164 111751484720 165 122023110670 166 133205303736 167 145375936989 168 158619309064 169 173026659130 170 188696715896 171 205736290666 172 224260919824 173 244395549838 174 266275277194 175 290046148860 176 315866015964 177 343905455234 178 374348764540 179 407395025392 180 443259248958 181 482173612505 182 524388779460 183 570175322507 184 619825257344 185 673653680678 186 732000534684 187 795232506558 188 863745058196 189 937964611178 190 1018350896284 191 1105399464912 192 1199644390492 193 1301661171118 194 1412069833232 195 1531538266740 196 1660785806292 197 1800587061350 198 1951776028610 199 2115250505559 200 2291976810200 201 2482994845104 202 2689423530034 203 2912466610734 204 3153418887344 205 3413672892656 206 3694726031862 207 3998188233920 208 4325790151724 209 4679391926713 210 5060992576388 211 5472740051227 212 5916941981156 213 6396077180223 214 6912807965768 215 7469993318518 216 8070702965932 217 8718232455532 218 9416119252228 219 10168159958254 220 10978428734570 221 11851296969412 222 12791454310252 223 13803931151641 224 14894122639972 225 16067814332360 226 17331209619460 227 18690958990919 228 20154191304440 229 21728547189868 230 23422214689970 231 25243967326378 232 27203204746936 233 29309996083967 234 31575126244944 235 34010145322962 236 36627421289840 237 39440196229941 238 42462646341028 239 45709945905989 240 49198335536636 241 52945194963188 242 56969120619404 243 61290008377676 244 65929141766116 245 70909285971376 246 76254788044576 247 81991683710883 248 88147811151852 249 94752932255212 250 101838861812552 251 109439605110851 252 117591504505036 253 126333395548409 254 135706773219498 255 145755968941380 256 156528339083320 257 168074465594488 258 180448369598232 259 193707738769274 260 207914169275288 261 223133423268663 262 239435702907718 263 256895941849600 264 275594115385506 265 295615570380291 266 317051376153492 267 339998697690969 268 364561192567500 269 390849432948952 270 418981354317860 271 449082732564898 272 481287691092092 273 515739239871606 274 552589848412082 275 592002054606872 276 634149111764052 277 679215676139608 278 727398537336460 279 778907394286499 280 833965679576376 281 892811434942431 282 955698241144272 283 1022896205497769 284 1094693010436952 285 1171395026897242 286 1253328496421384 287 1340840785996732 288 1434301720104356 289 1534104994613588 290 1640669677286618 291 1754441800191402 292 1875896049516588 293 2005537558442879 294 2143903809336496 295 2291566651774104 296 2449134443106420 297 2617254318963992 298 2796614601407504 299 2987947352675500 300 3192031083277224 301 3409693623536820 302 3641815168006830 303 3889331503081439 304 4153237428569444 305 4434590384376452 306 4734514294486840 307 5054203640943865 308 5394927781021688 309 5758035521968591 310 6144959968299800 311 6557223657239932 312 6996443999257598 313 7464339041355620 314 7962733571553088 315 8493565584506230 316 9058893129086012 317 9660901559677758 318 10301911214678918 319 10984385546723676 320 11710939730303848 321 12484349774397033 322 13307562168987576 323 14183704095735365 324 15116094235252628 325 16108254204981642 326 17163920663299904 327 18287058117998260 328 19481872479119888 329 20752825398077534 330 22104649437849234 331 23542364121263793 332 25071292906660708 333 26697081143526032 334 28425715063332024 335 30263541863480135 336 32217290946085044 337 34294096376440802 338 36501520629151922 339 38847579694349242 340 41340769620061636 341 43990094570525720 342 46805096485345484 343 49795886428691932 344 52973177722112492 345 56348320960451187 346 59933341015397964 347 63740976136350374 348 67784719265116784 349 72078861686864028 350 76638539145810488 351 81479780562070623 352 86619559492920872 353 92075848488945507 354 97867676504638312 355 104015189531072258 356 110539714626717352 357 117463827532980488 358 124811424070451796 359 132607795521800205 360 140879708219348068 361 149655487566382098 362 158965106732920432 363 168840280280586715 364 179314562984170466 365 190423454131089474 366 202204507596037006 367 214697448003222615 368 227944293304537528 369 241989484120535046 370 256880020208799044 371 272665604442827910 372 289398794706002932 373 307135164125866953 374 325933470095550888 375 345855832553971754 376 366967922020510828 377 389339157905023382 378 413042917642718360 379 438156757231496157 380 464762643778562896 381 492947200696335716 382 522801966220270732 383 554423665955248532 384 587914500195561316 385 623382446801418442 386 660941580454428606 387 700712409158942451 388 742822228900105324 389 787405497415437390 390 834604228088093664 391 884568405020968325 392 937456420404234156 393 993435535348217027 394 1052682365412657624 395 1115383392125453095 396 1181735501852466620 397 1251946553448578704 398 1326235976192165614 399 1404835399584238586 400 1487989316672966336 401 1575955782647840354 402 1669007150538955484 403 1767430845948985106 404 1871530182842228392 405 1981625222520328517 406 2098053678020977592 407 2221171866288003322 408 2351355710582599100 409 2489001795729017931 410 2634528478917724908 411 2788377058929019132 412 2951013006783111284 413 3122927260972563744 414 3304637590594496646 415 3496690029865316982 416 3699660387673992020 417 3914155836016127212 418 4140816581342199808 419 4380317623053434576 420 4633370603593565310 421 4900725754805446938 422 5183173945452537774 423 5481548835052833274 424 5796729139427622316 425 6129641013634123588 426 6481260558236365166 427 6852616455162582568 428 7244792739705111264 429 7658931715547438923 430 8096237020041992100 431 8557976847317134224 432 9045487337170318668 433 9560176138094970913 434 10103526153197887504 435 10677099478199564514 436 11282541541159930940 437 11921585454043553544 438 12596056586739608688 439 13307877374670306372 440 14059072371664692508 441 14851773560351228940 442 15688225932919390044 443 16570793355726032642 444 17501964731885111448 445 18484360476666226590 446 19520739321247366152 447 20614005461129024690 448 21767216066307223776 449 22983589171131057044 450 24266511962645707736 451 25619549487130849174 452 27046453795496473452 453 28551173549203715884 454 30137864109423206478 455 31810898133237709136 456 33574876701850547780 457 35434641006962129336 458 37395284622733953506 459 39462166392085198366 460 41640923957446225524 461 43937487967536956546 462 46358096993259602984 463 48909313187378829216 464 51598038724319601260 465 54431533058158647103 466 57417431038702931200 467 60563761927450250888 468 63878969357229252344 469 67371932281401177058 470 71051986960687169154 471 74928950037980616945 472 79013142753895056992 473 83315416358299823010 474 87847178775726719412 475 92620422585271996428 476 97647754378485732756 477 102942425561755248664 478 108518364672830215560 479 114390211284423482287 480 120573351571274238674 481 127083955620658465812 482 133939016570096210936 483 141156391659958174812 484 148754845292794846384 485 156754094195522278025 486 165174854785122980498 487 174038892843237809006 488 183369075609959237908 489 193189426412313137170 490 203525181948314821160 491 214402852353131567488 492 225850284179804959484 493 237896726433162552258 494 250572899802007068744 495 263911069241441948360 496 277945120064255279124 497 292710637707669289552 498 308244991349502083718 499 324587421555863213067 500 341779132150946329188 501 359863386508326475686 502 378885608472397785776 503 398893488128233417438 504 419937092648253298960 505 442068982454627914230 506 465344332947365037630 507 489821062059565085149 508 515559963913371030120 509 542624848862721474476 510 571082690222188895986 511 601003777994931090314 512 632461879927147734176 513 665534410231468961846 514 700302606337391159630 515 736851714043267294658 516 775271181461513097260 517 815654862166589676980 518 858101227974024042148 519 902713591798294545532 520 949600341057823561860 521 998875182116647705556 522 1050657396274644982648 523 1105072107841476130892 524 1162250564853713882264 525 1222330433020063201016 526 1285456103506109108370 527 1351779015197743662127 528 1421457992111400877400 529 1494659596649463667046 530 1571558499430785195144 531 1652337866459277153082 532 1737189764427960454000 533 1826315584991842912598 534 1919926488880581448794 535 2018243870761110475463 536 2121499845801375812456 537 2229937758929112962738 538 2343812717824263991740 539 2463392150730251006238 540 2588956390218036906808 541 2720799284087727486717 542 2859228834645526674984 543 3004567867649283343914 544 3157154732273693797766 545 3317344033506585541263 546 3485507398450755619496 547 3662034278071609894143 548 3847332785999499950640 549 4041830576067349951113 550 4245975760338956215576 551 4460237869461397081550 552 4685108857256496679200 553 4921104151551305254204 554 5168763753336280319486 555 5428653386432485174227 556 5701365699945739764284 557 5987521525886475989244 558 6287771194439296357196 559 6602795909476003594663 560 6933309187020397722508 561 7280058359492682227017 562 7643826148685994016152 563 8025432310557640160408 564 8425735355053371815484 565 8845634344324586964288 566 9286070772846027884552 567 9748030533095641249464 568 10232545970618960633044 569 10740698032467987274526 570 11273618513179434674684 571 11832492402639559522036 572 12418560340372998594700 573 13033121180991457962612 574 13677534675744986519736 575 14353224275334326145856 576 15061680059367900225764 577 15804461798081651077150 578 16583202152184628342892 579 17399610016948450590558 580 18255474016924827001928 581 19152666157952751842016 582 20093145643406315899452 583 21078962861935683477933 584 22112263554268237361524 585 23195293166964807905600 586 24330401401367700838760 587 25520046966333566063850 588 26766802543715691531368 589 28073359975947551086843 590 29442535685483104615310 591 30877276336270211082714 592 32380664747872131592176 593 33955926073309279374908 594 35606434252169977431816 595 37335718751035655575338 596 39147471603783565401448 597 41045554764869677876442 598 43034007789256689971690 599 45117055853238024279218 600 47299118131019437007064 601 49584816542556197779080 602 51978984888806914842364 603 54486678391256157326425 604 57113183653278035469224 605 59864029061663126602575 606 62744995647412927766608 607 65762128425720475805132 608 68921748235904346051060 609 72230464102947429629864 610 75695186143212954228712 611 79323139037869772756441 612 83121876098558686167862 613 87099293950872925202426 614 91263647862310705295876 615 95623567742487879297539 616 100188074844575778386260 617 104966599198155384800864 618 109968997804956138504358 619 115205573630277803542956 620 120687095424279184731168 621 126424818408760466175968 622 132430505866568652181532 623 138716451672320577901384 624 145295503804767886100140 625 152181088882825632979887 626 159387237769053646839952 627 166928612286220407476430 628 174820533094495754983860 629 183079008778814376141673 630 191720766198030108493996 631 200763282149644715839629 632 210224816406147514416560 633 220124446181347829052129 634 230482102087524202115984 635 241318605646756592180252 636 252655708422454702905092 637 264516132839850993978626 638 276923614767095363484858 639 289902947931574684291429 640 303480030249188748923356 641 317681912147549797809046 642 332536846967440974267996 643 348074343530374758477750 644 364325220963741369807336 645 381321665878835228512401 646 399097292001000466869788 647 417687202355250556283610 648 437128054114999020046808 649 457458126225994285072770 650 478717389922189143212710 651 500947582255101491349218 652 524192282763245164109084 653 548496993413435782114931 654 573909221951214953569280 655 600478568803294962900512 656 628256817680814242605500 657 657298030038320797222942 658 687658643549775428984616 659 719397574769499168507971 660 752576326152890208567176 661 787259097618915118116292 662 823512902843848450995004 663 861407690483505786878064 664 901016470529299276939220 665 942415446011854538899232 666 985684150274676396265672 667 1030905590049451445957138 668 1078166394574041905907988 669 1127556971004072361331180 670 1179171666379253462595284 671 1233108936416240163624687 672 1289471521410903218045036 673 1348366629544417735150692 674 1409906127899559371762312 675 1474206741506065668507841 676 1541390260746885505787192 677 1611583757470623513208460 678 1684919810169509196453380 679 1761536738596803174138038 680 1841578848212717481302940 681 1925196684863696545593332 682 2012547300116303323088788 683 2103794527684006091424826 684 2199109271402891446760142 685 2298669805230764106480834 686 2402662085763262055443728 687 2511280077780545378156771 688 2624726093358837920095676 689 2743211145102643917949276 690 2866955314075859360372296 691 2996188133033282751665628 692 3131148985578237062841540 693 3272087521897180241990490 694 3419264091748342340066040 695 3572950195408622147416187 696 3733428953311245800439652 697 3900995595136075152294376 698 4075957969144998493962632 699 4258637072586585833063531 700 4449367604027191379206148 701 4648498538499986000005630 702 4856393726399052935459436 703 5073432517082732508750119 704 5300010408188910570331236 705 5536539721704967685671574 706 5783450307876699314843490 707 6041190278083742494363224 708 6310226767853965238740156 709 6591046731235955610459722 710 6884157767797256410286488 711 7190088983566399607917890 712 7509391887289174235540860 713 7842641323423988777783619 714 8190436443357743344004240 715 8553401716382388953354840 716 8932187982033406332739320 717 9327473545454873260814526 718 9739965317521698116379280 719 10170400001518073138724952 720 10619545328242342895597972 721 11088201341482392698513836 722 11577201735882444595072610 723 12087415249301915590580472 724 12619747111849856949274960 725 13175140553864573633968238 726 13754578375197442550410408 727 14359084578252833619199811 728 14989726067332521518402400 729 15647614416933195992227033 730 16333907711749776100357244 731 17049812461245356877909360 732 17796585591760919384890156 733 18575536519254574800391406 734 19388029305881255493460248 735 20235484903749582542746652 736 21119383489323306201548532 737 22041266892070417961499083 738 23002741121103961731162680 739 24005478993704924021019344 740 25051222869769564968641012 741 26141787496381377313010455 742 27279062966871748782543216 743 28465017798903584697210320 744 29701702136288860392082196 745 30991251079434562658048884 746 32335888149502002225998884 747 33737928891562301429029614 748 35199784622236256346579956 749 36723966327520027005206532 750 38313088716719519301436672 751 39969874438646193716572920 752 41697158466465687590551108 753 43497892657838400596758744 754 45375150497248407913741416 755 47332132027684088081067992 756 49372168979111051579105296 757 51498730101465711892487234 758 53715426710196549697574120 759 56026018452690194119353196 760 58434419304241306593506086 761 60944703802559344692198230 762 63561113530152063705691918 763 66288063854285555374908728 764 69130150934594218478762204 765 72092159008801815793784093 766 75179067967417223014306892 767 78396061228686166371634826 768 81748533925513746035037264 769 85242101416522438971446459 770 88882608133877179223124496 771 92676136780993659507653420 772 96629017893748839795042920 773 100747839779334467155991824 774 105039458847435912810699348 775 109511010348980545705658308 776 114169919538282945631306180 777 119023913275019299181920460 778 124081032083091130512261826 779 129349642684089940487108548 780 134838451023750237942360832 781 140556515810479749421460958 782 146513262585783229249924356 783 152718498347151234796262525 784 159182426744768488867057996 785 165915663874209069099007849 786 172929254688128727767603302 787 180234690050839275278943727 788 187843924460557321660677348 789 195769394465060969907156846 790 204024037797464540412097072 791 212621313259834373199386748 792 221575221383419547599367068 793 230900325895361365537006165 794 240611776022876106881848606 795 250725329667078377883182330 796 261257377479828881080852104 797 272224967878252241520875904 798 283645833032879292047692236 799 295538415866725668079767572 800 307921898104026473912255956 801 320816229408807007128800379 802 334242157654983976216368384 803 348221260371262303194084206 804 362775977405721523924362896 805 377929644856675109014455556 806 393706530318137934046563406 807 410131869490053915071679210 808 427231904205319856879970988 809 445033921927595290137680776 810 463566296775914039952346976 811 482858532134214099749024333 812 502941304906080806622643624 813 523846511477257151599918891 814 545607315450817230388819702 815 568258197222327376830005067 816 591835005464837560593924080 817 616375010596156417647991804 818 641916960303570183007443830 819 668501137203972297055340062 820 696169418720280164900944708 821 724965339258032202765762940 822 754934154769185779696068176 823 786122909793378962726518270 824 818580507070280253237662856 825 852357779820135064011841668 826 887507566793229979888298960 827 924084790192740483741161944 828 962146536579309591751952352 829 1001752140869728669227166868 830 1042963273546262713852494776 831 1085844031197485902691404868 832 1130461030515974689667795604 833 1176883505882850899974068898 834 1225183410673981986957086798 835 1275435522427635987686795006 836 1327717552018561050093351856 837 1382110256988820245562124472 838 1438697559191268488810766392 839 1497566666907316770332132202 840 1558808201606596822320011414 841 1622516329522324292466998922 842 1688788898222568269139777592 843 1757727578364277638881612488 844 1829438010823798592012504804 845 1904029959404751254418885666 846 1981617469331525848100392782 847 2062319031744319210970823284 848 2146257754419570512190102396 849 2233561538947880494625033251 850 2324363264610021812767520938 851 2418800979200479632945061372 852 2517018097057112616820545520 853 2619163604565006090197242402 854 2725392273412413385831763452 855 2835864881886860233674202985 856 2950748444510033265506157988 857 3070216450321000264969795857 858 3194449110128630247926933516 859 3323633613065809785363040454 860 3457964392790202663625033408 861 3597643403688888003391273124 862 3742880407457252832469801732 863 3893893270436024882633810402 864 4050908272104326672450935548 865 4214160425141129931675700226 866 4383893807482507912979561520 867 4560361906817640539063420564 868 4743827977982642694587556216 869 4934565413727979013705378772 870 5132858129352519643067960774 871 5339000961715201784377863434 872 5553300083153813192114526908 873 5776073430859628833207580026 874 6007651152276533993288106600 875 6248376067113880449039647666 876 6498604146583671969362161944 877 6758705010494787268667315946 878 7029062442859849432660201574 879 7310074926694068519677354234 880 7602156198709947207878479660 881 7905735824637177714796476136 882 8221259795923402494251144276 883 8549191148598793200648188853 884 8890010605115654997800595332 885 9244217240003520511950661440 886 9612329170210494782787242868 887 9994884271032985876200844992 888 10392440918568443070498416396 889 10805578759659364682449636754 890 11234899510331670986507771996 891 11681027783766606016097028584 892 12144611948882678459201718080 893 12626325020642821010136764086 894 13126865583241985590850833508 895 13646958747371846557682717614 896 14187357142802204768712725488 897 14748841947563123306863614898 898 15332223955057833579097229536 899 15938344680484083116306942483 900 16568077507990910232592510536 901 17222328880048884241351896614 902 17902039530564703664410386722 903 18608185763325761378263904010 904 19341780777416929614423729144 905 20103876041310456096058813507 906 20895562717390564568655377648 907 21717973138737190137099626698 908 22572282340058326187946168624 909 23459709644727791816501543882 910 24381520309954925754389926304 911 25339027232184856685065528848 912 26333592714902675217500828064 913 27366630301092127207487302900 914 28439606672679452119633719136 915 29554043619375797345359534806 916 30711520079417346637795552408 917 31913674254791008212495248648 918 33162205803625319119828168616 919 34458878112521244249464902123 920 35805520651695891465777812836 921 37204031415913943343685961226 922 38656379454286939093128613372 923 40164607492129549879143435557 924 41730834648174803368505924938 925 43357259250566959738014942104 926 45046161755171556792856933344 927 46799907769867166078696535406 928 48620951188612779454655497820 929 50511837439218625966951449798 930 52475206848886756523685030682 931 54513798131731088522161961980 932 56630452002634939344876723892 933 58828114921957567223739471371 934 61109842975760056821471332836 935 63478805896385217421959882242 936 65938291228396192442834296628 937 68491708645054405005237104505 938 71142594420699487035522921340 939 73894616064582167141422738694 940 76751577121895940602490305844 941 79717422147954935817118723275 942 82796241861673955523302302480 943 85992278484722445837665486340 944 89309931272947377438304196452 945 92753762246890965114638340500 946 96328502128468066992234427520 947 100039056491115264426503130306 948 103890512130979308370425417408 949 107888143666977117864895152016 950 112037420377833130831942236836 951 116344013284482846271320952379 952 120813802486524180316563586400 953 125452884761701117190623214437 954 130267581437717411779587785508 955 135264446546002146589272556288 956 140450275267384127381143360808 957 145832112679978796123757410916 958 151417262819949936942374116368 959 157213298066179353453114180388 960 163228068860261320631657844776 961 169469713773635391454287423244 962 175946669934081512607047020692 963 182667683824225834057108924636 964 189641822465144558966145685332 965 196878484998607163890757271079 966 204387414681969831386180978556 967 212178711310215501767167170854 968 220262844080139109100113607524 969 228650664912195877715124835214 970 237353422246067597395182638192 971 246382775326557164909067100674 972 255750808996995993515684853916 973 265470049017942787723851182664 974 275553477929566316363847764458 975 286014551476739873170162553907 976 296867215616531793350975607248 977 308125924128455423112301366856 978 319805656848544066942471778000 979 331921938549042439564005361633 980 344490858486256826422033579040 981 357529090639882335477055518924 982 371053914667928158278929397420 983 385083237602191532465011446145 984 399635616310089022747962570792 985 414730280749540754995722643036 986 430387158044520321138869339014 987 446626897409831226445060579360 988 463470895954651013345047615892 989 480941325395397639906758756521 990 499061159709520423988510140234 991 517854203762901030243530408148 992 537345122944669758384128143756 993 557559473844400008216803232391 994 578523736007840510797331456172 995 600265344808582027987408588669 996 622812725474334079872930283664 997 646195328307809250206620270158 998 670443665143579179197810264144 999 695589347083678962608798521230 1000 721665123556196866806616935640