0 1 1 2 2 5 3 10 4 20 5 34 6 59 7 94 8 149 9 224 10 334 11 480 12 685 13 950 14 1307 15 1762 16 2357 17 3100 18 4050 19 5220 20 6685 21 8466 22 10659 23 13294 24 16494 25 20298 26 24859 27 30234 28 36609 29 44056 30 52806 31 62952 32 74770 33 88380 34 104112 35 122116 36 142786 37 166304 38 193134 39 223504 40 257954 41 296756 42 340544 43 389644 44 444786 45 506360 46 575206 47 651784 48 737059 49 831566 50 936405 51 1052206 52 1180214 53 1321154 54 1476441 55 1646910 56 1834151 57 2039124 58 2263614 59 2508716 60 2776431 61 3067998 62 3385649 63 3730794 64 4105911 65 4512584 66 4953570 67 5430648 68 5946863 69 6504210 70 7106049 71 7754606 72 8453584 73 9205454 74 10014283 75 10882822 76 11815523 77 12815424 78 13887404 79 15034816 80 16262980 81 17575592 82 18978448 83 20475608 84 22073380 85 23776208 86 25590940 87 27522448 88 29578148 89 31763352 90 34086096 91 36552168 92 39170244 93 41946624 94 44890668 95 48009216 96 51312357 97 54807498 98 58505493 99 62414370 100 66545784 101 70908402 102 75514743 103 80374158 104 85500057 105 90902520 106 96595902 107 102591048 108 108903313 109 115544342 110 122530535 111 129874402 112 137593433 113 145701028 114 154215842 115 163152220 116 172530017 117 182364578 118 192677023 119 203483742 120 214807186 121 226664834 122 239080523 123 252072898 124 265667237 125 279883384 126 294748146 127 310282632 128 326515222 129 343468356 130 361172064 131 379650172 132 398934438 133 419050128 134 440030794 135 461903232 136 484702854 137 508458028 138 533206128 139 558977172 140 585810550 141 613738008 142 642801042 143 673033192 144 704478151 145 737171318 146 771158661 147 806477542 148 843176282 149 881294258 150 920882261 151 961981774 152 1004646123 153 1048918988 154 1094856334 155 1142504116 156 1191921043 157 1243155422 158 1296268797 159 1351311946 160 1408349339 161 1467434288 162 1528634322 163 1592005392 164 1657618163 165 1725531330 166 1795818813 167 1868542142 168 1943778612 169 2021592678 170 2102065115 171 2185263438 172 2271272007 173 2360161472 174 2452019928 175 2546921280 176 2644957448 177 2746205712 178 2850761952 179 2958706928 180 3070140616 181 3185147360 182 3303831352 183 3426280672 184 3552603848 185 3682892784 186 3817260512 187 3955802896 188 4098637576 189 4245864512 190 4397606104 191 4553966528 192 4715073097 193 4881034322 194 5051982565 195 5228030842 196 5409316700 197 5595957762 198 5788096947 199 5985856638 200 6189385245 201 6398810064 202 6614285166 203 6835942896 204 7063943157 205 7298423478 206 7539549747 207 7787464866 208 8042340861 209 8304326124 210 8573599026 211 8850313620 212 9134654757 213 9426782322 214 9726887835 215 10035137166 216 10351728694 217 10676834426 218 11010659771 219 11353383082 220 11705216969 221 12066346264 222 12436991006 223 12817342696 224 13207628954 225 13608048140 226 14018835664 227 14440196916 228 14872375306 229 15315583424 230 15770072870 231 16236063664 232 16713815786 233 17203556836 234 17705555424 235 18220046940 236 18747308794 237 19287584376 238 19841160126 239 20408287624 240 20989262571 241 21584344926 242 22193839861 243 22818015966 244 23457188094 245 24111633634 246 24781677393 247 25467605790 248 26169753775 249 26888417028 250 27623940894 251 28376630524 252 29146841911 253 29934889886 254 30741141321 255 31565921002 256 32409606911 257 33272533976 258 34155091586 259 35057625064 260 35980535415 261 36924178610 262 37888967545 263 38875269070 264 39883508248 265 40914063038 266 41967370923 267 43043821270 268 44143864235 269 45267900800 270 46416394116 271 47589757056 272 48788465996 273 50012945976 274 51263686896 275 52541126216 276 53845767660 277 55178061360 278 56538525140 279 57927622128 280 59345884524 281 60793788680 282 62271881520 283 63780652920 284 65320664780 285 66892420800 286 68496498180 287 70133414720 288 71803763245 289 73508075930 290 75246961525 291 77020966930 292 78830717120 293 80676773970 294 82559779055 295 84480309550 296 86439023905 297 88436514920 298 90473458270 299 92550462680 300 94668221401 301 96827359382 302 99028587775 303 101272548130 304 103559969825 305 105891511284 306 108267920514 307 110689873164 308 113158136169 309 115673402754 310 118236459159 311 120848016510 312 123508880730 313 126219781170 314 128981543787 315 131794916562 316 134660745837 317 137579798520 318 140552941770 319 143580961800 320 146664746910 321 149805102996 322 153002939904 323 156259083564 324 159574465774 325 162949932848 326 166386438914 327 169884851104 328 173446146254 329 177071212636 330 180761050256 331 184516568932 332 188338792190 333 192228651800 334 196187195242 335 200215376616 336 204314267791 337 208484845574 338 212728206629 339 217045350934 340 221437400354 341 225905378386 342 230450432589 343 235073610414 344 239776085491 345 244558929660 346 249423343086 347 254370422404 348 259401394779 349 264517382046 350 269719638805 351 275009312586 352 280387685859 353 285855932224 354 291415362546 355 297067176960 356 302812715131 357 308653204194 358 314590013109 359 320624396446 360 326757752956 361 332991365078 362 339326661819 363 345764954014 364 352307701391 365 358956243584 366 365712071600 367 372576554368 368 379551214608 369 386637451040 370 393836818624 371 401150746336 372 408580821904 373 416128505024 374 423795416688 375 431583047872 376 439493053328 377 447526955744 378 455686444224 379 463973073696 380 472388568080 381 480934515072 382 489612673968 383 498424665728 384 507372285585 385 516457188258 386 525681205445 387 535046026218 388 544553519268 389 554205408482 390 564003600171 391 573949853598 392 584046113189 393 594294174144 394 604696019598 395 615253481216 396 625968581437 397 636843188918 398 647879365963 399 659079018850 400 670444250309 401 681977004732 402 693679425938 403 705553497028 404 717601403437 405 729825167570 406 742227017107 407 754809014318 408 767573429758 409 780522366122 410 793658137435 411 806982887482 412 820498974353 413 834208583448 414 848114117622 415 862217804520 416 876522092322 417 891029251548 418 905741776368 419 920661980772 420 935792405586 421 951135408864 422 966693578718 423 982469317968 424 998465262642 425 1014683860884 426 1031127797376 427 1047799566252 428 1064701901442 429 1081837343736 430 1099208677014 431 1116818489352 432 1134669615283 433 1152764690798 434 1171106601749 435 1189698032782 436 1208541921734 437 1227641002498 438 1246998265673 439 1266616495102 440 1286498734775 441 1306647819188 442 1327066846462 443 1347758702412 444 1368726540031 445 1389973297118 446 1411502182241 447 1433316185962 448 1455418573127 449 1477812387688 450 1500500951586 451 1523487362904 452 1546775001343 453 1570367019858 454 1594266856689 455 1618477720366 456 1643003108448 457 1667846285742 458 1693010809867 459 1718500002726 460 1744317482739 461 1770466629568 462 1796951123292 463 1823774402112 464 1850940208468 465 1878452039880 466 1906313701968 467 1934528752312 468 1963101060532 469 1992034245008 470 2021332240140 471 2050998725968 472 2081037702452 473 2111452911992 474 2142248421008 475 2173428035080 476 2204995887828 477 2236955848832 478 2269312119772 479 2302068635008 480 2335229665141 481 2368799210090 482 2402781610197 483 2437180931842 484 2472001585928 485 2507247706034 486 2542923774567 487 2579033993166 488 2615582916521 489 2652574815192 490 2690014317054 491 2727905762408 492 2766253853217 493 2805063000342 494 2844337980695 495 2884083276642 496 2924303740905 497 2965003928132 498 3006188767842 499 3047862887868 500 3090031295345 501 3132698692194 502 3175870164111 503 3219550487966 504 3263744828962 505 3308458039778 506 3353695366027 507 3399461737186 508 3445762480181 509 3492602602104 510 3539987512226 511 3587922296200 512 3636412446502 513 3685463128292 514 3735079918240 515 3785268061916 516 3836033221174 517 3887380722896 518 3939316315066 519 3991845406912 520 4044973833494 521 4098707087244 522 4153051091376 523 4208011422516 524 4263594092934 525 4319804764440 526 4376649539394 527 4434134165736 528 4492264836951 529 4551047388054 530 4610488104645 531 4670592909894 532 4731368182506 533 4792819934706 534 4854954639429 535 4917778398990 536 4981297781499 537 5045518980396 538 5110448660046 539 5176093106004 540 5242459079971 541 5309552960606 542 5377381607981 543 5445951494986 544 5515269581099 545 5585342434384 546 5656177114898 547 5727780286960 548 5800159112195 549 5873320352258 550 5947271271469 551 6022018729854 552 6097570095556 553 6173932328006 554 6251112900251 555 6329118872302 556 6407957823191 557 6487636914496 558 6568163832456 559 6649545841344 560 6731790735640 561 6814905883440 562 6898899188640 563 6983778124240 564 7069550704728 565 7156224509088 566 7243807663528 567 7332307854240 568 7421733320280 569 7512091856080 570 7603391814816 571 7695641100336 572 7788848181016 573 7883021071296 574 7978168355976 575 8074298161216 576 8171419189465 577 8269539679730 578 8368668453285 579 8468813863258 580 8569984850924 581 8672189884610 582 8775438026915 583 8879737862590 584 8985098576685 585 9091528871600 586 9199038056110 587 9307634951440 588 9417328991365 589 9528129117110 590 9640044888675 591 9753085368610 592 9867260244365 593 9982578700940 594 10099050554610 595 10216685114100 596 10335492325685 597 10455481623090 598 10576663083915 599 10699046268110 600 10822641385926 601 10947458124762 602 11073506828795 603 11200797314250 604 11329340060505 605 11459145013784 606 11590222790094 607 11722583466984 608 11856237798314 609 11991195994284 610 12127468947984 611 12265067003540 612 12404001194650 613 12544282000640 614 12685920597142 615 12828927600112 616 12973314328442 617 13119091535940 618 13266270686240 619 13414862672380 620 13564879104010 621 13716331014776 622 13869230161774 623 14023587720584 624 14179415597179 625 14336725110398 626 14495528316469 627 14655836678974 628 14817662405774 629 14981017106466 630 15145913142081 631 15312362269662 632 15480377004735 633 15649969253220 634 15821151686622 635 15993936361116 636 16168336105671 637 16344363128094 638 16522030416249 639 16701350331114 640 16882336020879 641 17065000001016 642 17249355581634 643 17435415434184 644 17623193032071 645 17812701204210 646 18003953588841 647 18196963173774 648 18391743763624 649 18588308506526 650 18786671374955 651 18986845678966 652 19188845560379 653 19392684492544 654 19598376788276 655 19805936085760 656 20015376870236 657 20226712946264 658 20439958973104 659 20655128923176 660 20872237631356 661 21091299239408 662 21312328759364 663 21535340503984 664 21760349663996 665 21987370724584 666 22216419056880 667 22447509320088 668 22680657067228 669 22915877133120 670 23153185254324 671 23392596442816 672 23634126620349 673 23877790977594 674 24123605623093 675 24371585927922 676 24621748189008 677 24874107959314 678 25128681725919 679 25385485225326 680 25644535136305 681 25905847380552 682 26169438830238 683 26435325593848 684 26703524738665 685 26974052561558 686 27246926326575 687 27522162520738 688 27799778606513 689 28079791262612 690 28362218151746 691 28647076146028 692 28934383110009 693 29224156110914 694 29516413216903 695 29811171691966 696 30108449809642 697 30408265032338 698 30710635840683 699 31015579897330 700 31323115891709 701 31633261688312 702 31946036187258 703 32261457456648 704 32579544608942 705 32900315917620 706 33223790709312 707 33549987464588 708 33878925726078 709 34210624183152 710 34545102596210 711 34882379865312 712 35222475970398 713 35565410023868 714 35911202227152 715 36259871906820 716 36611439487502 717 36965924511768 718 37323347629338 719 37683728600552 720 38047088302111 721 38413446713894 722 38782824941413 723 39155243186038 724 39530722783922 725 39909284159634 726 40290948881981 727 40675737600622 728 41063672118787 729 41454773313116 730 41849063223214 731 42246562954532 732 42647294785003 733 43051280050718 734 43458541269829 735 43869100011082 736 44282979034739 737 44700200143968 738 45120786343218 739 45544759672032 740 45972143380875 741 46402959747618 742 46837232270757 743 47274983468382 744 47716237089036 745 48161015892918 746 48609343880571 747 49061244056382 748 49516740674847 749 49975856986368 750 50438617501536 751 50905045718784 752 51375166406688 753 51849003313728 754 52326581468544 755 52807924871616 756 53293058813728 757 53782007549312 758 54274796633312 759 54771450576256 760 55271995199264 761 55776455270848 762 56284856880512 763 56797225056832 764 57313586159648 765 57833965479680 766 58358389649248 767 58886884223232 768 59419476108577 769 59956191126338 770 60497056460165 771 61042098199498 772 61591343806772 773 62144819641762 774 62702553447963 775 63264571857630 776 63830902897333 777 64401573473952 778 64976611899342 779 65556045357088 780 66139902446541 781 66728210630070 782 67320998796667 783 67918294689762 784 68520127490133 785 69126525224284 786 69737517367122 787 70353132230436 788 70973399585341 789 71598348031122 790 72228007637379 791 72862407293038 792 73501577368462 793 74145547044362 794 74794346994075 795 75448006692442 796 76106557117985 797 76770028041752 798 77438450749862 799 78111855311848 800 78790273323570 801 79473735155324 802 80162272715056 803 80855916676036 804 81554699260642 805 82258651447328 806 82967805775182 807 83682193530256 808 84401847570626 809 85126799492084 810 85857082474176 811 86592728424780 812 87333770847122 813 88080241963512 814 88832175603270 815 89589604305416 816 90352562227779 817 91121082228366 818 91895198795861 819 92674945109742 820 93460355991894 821 94251464945474 822 95048307128121 823 95850916369086 824 96659328164039 825 97473576670740 826 98293697725374 827 99119725816556 828 99951697123471 829 100789646467934 830 101633610374545 831 102483624000874 832 103339724219351 833 104201946525576 834 105070328142434 835 105944904906040 836 106825714392079 837 107712792779666 838 108606177999841 839 109505906577134 840 110412016800496 841 111324545542286 842 112243531451851 843 113169011752006 844 114101025454979 845 115039610136384 846 115984805174028 847 116936648498880 848 117895179856740 849 118860437536488 850 119832461654544 851 120811290860184 852 121796965643076 853 122789525015376 854 123789009842556 855 124795459502352 856 125808915238596 857 126829416797016 858 127857005802576 859 128891722371624 860 129933608512740 861 130982704715520 862 132039053374860 863 133102695356160 864 134173673443333 865 135252028880138 866 136337804842133 867 137431042954210 868 138531786786200 869 139640078346610 870 140755961602391 871 141879478948366 872 143010674751161 873 144149591794616 874 145296274847806 875 146450767086216 876 147613113684145 877 148783358211350 878 149961546250055 879 151147721767138 880 152341930755449 881 153544217581540 882 154754628651810 883 155973208735260 884 157200004654465 885 158435061583650 886 159678426764415 887 160930145778910 888 162190266290610 889 163458834292290 890 164735897872075 891 166021503436290 892 167315699500485 893 168618532887160 894 169930052542290 895 171250305707400 896 172579341761590 897 173917208368260 898 175263955342560 899 176619630772540 900 177984284912326 901 179357966277392 902 180740725563690 903 182132611717120 904 183533675878310 905 184943967426284 906 186363537949424 907 187792437262804 908 189230717405334 909 190678428631064 910 192135623432434 911 193602352505320 912 195078668798695 913 196564623453110 914 198060269876997 915 199565659658662 916 201080846668922 917 202605882946610 918 204140822828085 919 205685718805710 920 207240625684235 921 208805596412556 922 210380686266894 923 211965948655604 924 213561439329459 925 215167212159198 926 216783323373149 927 218409827307594 928 220046780671419 929 221694238269296 930 223352257293906 931 225020893021392 932 226700203131155 933 228390243373890 934 230091071918877 935 231802744994366 936 233525321262676 937 235258857432614 938 237003412662619 939 238759044145294 940 240525811538279 941 242303772520896 942 244092987253304 943 245893513904704 944 247705413140776 945 249528743623760 946 251363566528096 947 253209941012144 948 255067928762344 949 256937589436256 950 258818985235480 951 260712176320096 952 262617225410024 953 264534193170864 954 266463142844256 955 268404135604560 956 270357235218216 957 272322503371584 958 274300004359224 959 276289800382656 960 278291956267881 961 280306534734738 962 282333601143909 963 284373218736954 964 286425453412476 965 288490368936834 966 290568031750035 967 292658506146558 968 294761859110973 969 296878155469200 970 299007462753774 971 301149846325296 972 303305374267669 973 305474112479414 974 307656129599123 975 309851492066722 976 312060269078813 977 314282527619884 978 316518337448114 979 318767766095956 980 321030883886405 981 323307758903282 982 325598462037883 983 327903061928718 984 330221630038870 985 332554235564858 986 334900950544955 987 337261844737258 988 339636990758633 989 342026458931992 990 344430322456446 991 346848652223208 992 349281522016954 993 351729003300684 994 354191170448208 995 356668095497716 996 359159853415722 997 361666516819008 998 364188161270278 999 366724859968560 1000 369276689076234