0 1 1 1 2 2 3 3 4 5 5 6 6 11 7 14 8 21 9 28 10 39 11 51 12 72 13 92 14 124 15 160 16 210 17 266 18 349 19 438 20 562 21 704 22 892 23 1107 24 1395 25 1720 26 2141 27 2631 28 3249 29 3965 30 4873 31 5916 32 7216 33 8730 34 10585 35 12742 36 15387 37 18443 38 22151 39 26466 40 31646 41 37659 42 44873 43 53212 44 63149 45 74666 46 88295 47 104060 48 122687 49 144166 50 169422 51 198571 52 232676 53 271964 54 317854 55 370591 56 431966 57 502485 58 584257 59 678054 60 786631 61 910920 62 1054389 63 1218515 64 1407433 65 1623211 66 1871181 67 2153913 68 2478081 69 2847367 70 3269815 71 3750366 72 4299266 73 4922701 74 5633447 75 6439916 76 7357598 77 8397496 78 9579149 79 10916335 80 12433328 81 14148258 82 16090668 83 18283860 84 20764799 85 23562565 86 26722914 87 30283310 88 34299519 89 38819031 90 43911172 91 49634983 92 56075914 93 63308862 94 71437991 95 80557260 96 90795390 97 102268638 98 115135084 99 129540498 100 145677353 101 163726964 102 183925971 103 206497654 104 231731522 105 259904953 106 291369848 107 326468747 108 365632250 109 409280234 110 457937600 111 512121986 112 572470005 113 639616930 114 714338396 115 797409694 116 889772931 117 992377766 118 1106363987 119 1232890739 120 1373341122 121 1529123852 122 1701913090 123 1893424828 124 2105679101 125 2340760232 126 2601110362 127 2889252559 128 3208133035 129 3560810158 130 3950829073 131 4381888341 132 4858258816 133 5384400870 134 5965450409 135 6606790500 136 7314583954 137 8095314586 138 8956382175 139 9905578560 140 10951774879 141 12104337521 142 13373882124 143 14771648823 144 16310343908 145 18003430165 146 19866095387 147 21914464188 148 24166661761 149 26641972380 150 29362026224 151 32349848401 152 35631219972 153 39233626128 154 43187752861 155 47526366523 156 52285983166 157 57505609047 158 63228649321 159 69501520968 160 76375754321 161 83906520171 162 92154973431 163 101186606469 164 111073921828 165 121894627687 166 133734584380 167 146685896006 168 160850196514 169 176336528679 170 193265083553 171 211764888782 172 231977936779 173 254056753033 174 278169001211 175 304494798027 176 333231943967 177 364593016181 178 398811151420 179 436137009473 180 476845226489 181 521231087828 182 569617847102 183 622353153207 184 679817154270 185 742418801728 186 810604898683 187 884856088451 188 965697104144 189 1053692507565 190 1149458055692 191 1253656353451 192 1367009553349 193 1490294696745 194 1624358085930 195 1770110410743 196 1928542712115 197 2100721514892 198 2287806677689 199 2491046273326 200 2711796775340 201 2951517830278 202 3211794715716 203 3494333305134 204 3800985200861 205 4133742605181 206 4494766729283 207 4886382785339 208 5311111642559 209 5771665354417 210 6270982617382 211 6812224530209 212 7398814661476 213 8034435362620 214 8723072485281 215 9469012822497 216 10276894244292 217 11151703971585 218 12098835217701 219 13124086776348 220 14233726331060 221 15434492161894 222 16733664191754 223 18139067564522 224 19659152903762 225 21303002483574 226 23080420062859 227 25001940782969 228 27078932070110 229 29323607131374 230 31749138939590 231 34369678405133 232 37200482126824 233 40257936850016 234 43559703077117 235 47124745912847 236 50973497298558 237 55127894852578 238 59611563913441 239 64449866670806 240 69670106963751 241 75301590209930 242 81375854772502 243 87926745077868 244 94990671504722 245 102606699977558 246 110816844536056 247 119666174587624 248 129203145442542 249 139479726770604 250 150551774218136 251 162479183786041 252 175326310411505 253 189162150536565 254 204060815011336 255 220101745090855 256 237370244514189 257 255957735712519 258 275962359403623 259 297489274976498 260 320651337875714 261 345569451877597 262 372373331696316 263 401201916910965 264 432204231628909 265 465539866632666 266 501379950495510 267 539907711267846 268 581319570266203 269 625825797347364 270 673651744183272 271 725038603622521 272 780244802664707 273 839546882463639 274 903241067761097 275 971644287740728 276 1045095945810393 277 1123959097679113 278 1208622449924536 279 1299501719412498 280 1397041885456910 281 1501718759630925 282 1614041525465241 283 1734554543701455 284 1863840219581618 285 2002521078570061 286 2151262997676830 287 2310777593345610 288 2481825865027856 289 2665220933015940 290 2861832150727298 291 3072588243171178 292 3298481941128353 293 3540573580016460 294 3799996324409003 295 4077960283604140 296 4375758406094878 297 4694771184957254 298 5036473299456439 299 5402438995755447 300 5794349572719755 301 6213999521062344 302 6663304965602047 303 7144310667965854 304 7659199536751818 305 8210300615872132 306 8800099800114210 307 9431248930819747 308 10106577875062895 309 10829104879332040 310 11602050172537676 311 12428847751641492 312 13313160702997714 313 14258894596882341 314 15270214750024859 315 16351561444318814 316 17507669359909206 317 18743584865385936 318 20064687896180248 319 21476711571975710 320 22985766834024567 321 24598364696479856 322 26321443969777896 323 28162396496684005 324 30129098349232890 325 32229938417113484 326 34473853519002134 327 36870360778967399 328 39429597117191266 329 42162355910861026 330 45080131409847634 331 48195160208017772 332 51520471202743620 333 55069932493810305 334 58858307545556553 335 62901308214385284 336 67215657880312720 337 71819151352246855 338 76730725836535958 339 81970528591903289 340 87559996665538264 341 93521933285231266 342 99880597438727769 343 106661790065983351 344 113892954696180316 345 121603274668580890 346 129823786137816605 347 138587487711330736 348 147929467329261460 349 157887025821072095 350 168499819357132588 351 179809998650981325 352 191862368823465284 353 204704546197012175 354 218387137677631412 355 232963917258151825 356 248492027285762312 357 265032177094423200 358 282648868736839405 359 301410620469268110 360 321390219884754144 361 342664975223422280 362 365316999204475602 363 389433491546447472 364 415107057101712904 365 442436023388335287 366 471524797116002721 367 502484220892495661 368 535431972725386692 369 570492966624841169 370 607799800104814803 371 647493203977592443 372 689722543536443263 373 734646323354757796 374 782432748512075303 375 833260290969860518 376 887318317827790941 377 944807726636321815 378 1005941648563708581 379 1070946160740199883 380 1140061073148521117 381 1213540727126547178 382 1291654875676486739 383 1374689578334152629 384 1462948185805547493 385 1556752342446703039 386 1656443087413096655 387 1762381977396943147 388 1874952317713355017 389 1994560419423512263 390 2121636975429381815 391 2256638467562849065 392 2400048704507149597 393 2552380396338810341 394 2714176872822733536 395 2886013844920918731 396 3068501324245517127 397 3262285593072133291 398 3468051348120772059 399 3686523903201958800 400 3918471582897385041 401 4164708184736737823 402 4426095651386325800 403 4703546822063060768 404 4998028415093760082 405 5310564101789917881 406 5642237834563633279 407 5994197280265276014 408 6367657533160477237 409 6763904948614568428 410 7184301284668486552 411 7630287981725695329 412 8103390781045802768 413 8605224501236661665 414 9137498187566423063 415 9702020441408941248 416 10300705160305785604 417 10935577482981448143 418 11608780186380230859 419 12322580315868075912 420 13079376313028015030 421 13881705408002093846 422 14732251560020766785 423 15633853697597735505 424 16589514562388062383 425 17602409892455075397 426 18675898270277748777 427 19813531354347855207 428 21019064843257442708 429 22296469872733462212 430 23649945219507854900 431 25083929993786187075 432 26603117220421961669 433 28212467970514275184 434 29917226472454137490 435 31722935842356260291 436 33635454893579760427 437 35660975643148247422 438 37806042007001340974 439 40077569278200509735 440 42482864915513499355 441 45029650210809782265 442 47726083400367732153 443 50580783762448652082 444 53602857305867255300 445 56801923564044811617 446 60188144142853839261 447 63772252506573257141 448 67565585696555055398 449 71580117436334085383 450 75828493366532795117 451 80324067830664736601 452 85080943008727583672 453 90114009784441884924 454 95438991199937597637 455 101072487848059932825 456 107032026116104427575 457 113336108593165284449 458 120004267620726843305 459 127057121257732074461 460 134516432709774452974 461 142405172452270616100 462 150747584171177875927 463 159569253707167219593 464 168897182207800231154 465 178759862626355422156 466 189187360858064571827 467 200211400604768307440 468 211865453349881066172 469 224184832484208991177 470 237206793064247567470 471 250970636189363641833 472 265517819585745840278 473 280892073329141373006 474 297139522406722193619 475 314308814992651845561 476 332451258260658445881 477 351620960546732590150 478 371874981816361560670 479 393273491187942684580 480 415879933605720335546 481 439761204349181376699 482 464987833624030290972 483 491634179852685850805 484 519778634071381721932 485 549503833983167598280 486 580896890245740633411 487 614049623471455396222 488 649058814706028333021 489 686026467786872107471 490 725060086547916958336 491 766272965196369350648 492 809784495041104049065 493 855720485819442256602 494 904213505034180431506 495 955403233464444640812 496 1009436840510401628727 497 1066469377454025631542 498 1126664192559932211478 499 1190193366014225734817 500 1257238168913146057632 501 1327989544210967220188 502 1402648614146803755260 503 1481427211974368652609 504 1564548442842236787830 505 1652247271561069472561 506 1744771142462611128147 507 1842380628995701604447 508 1945350118646653664118 509 2053968530742958868904 510 2168540073135600458543 511 2289385035231691933627 512 2416840623816961028801 513 2551261839050096725177 514 2693022397544572638901 515 2842515699837812556774 516 3000155849671625628621 517 3166378722302608143014 518 3341643089819772949487 519 3526431800606425740909 520 3721253021517074315788 521 3926641539835925585384 522 4143160134222208824112 523 4371401011642364467731 524 4611987320184737769807 525 4865574734692831944695 526 5132853125853947425358 527 5414548309631567772761 528 5711423888471542934098 529 6024283181131054169198 530 6353971253423329823023 531 6701377046694799143961 532 7067435617254836075885 533 7453130483565749805057 534 7859496095406579146457 535 8287620421823917987723 536 8738647673163752181372 537 9213781154016797461041 538 9714286263533168902626 539 10241493639990915662038 540 10796802467320451213090 541 11381683940544933443058 542 11997684909193714803907 543 12646431695747543617711 544 13329634109631030042003 545 14049089653955363415772 546 14806687947092714988825 547 15604415356465458836979 548 16444359868334118002090 549 17328716191183610925597 550 18259791118325389764970 551 19240009147594551689948 552 20271918385730378476842 553 21358196735651764634303 554 22501658396358443904237 555 23705260674056398559186 556 24972111136547657673602 557 26305475109956177745272 558 27708783552314438625468 559 29185641303631880445763 560 30739835749670275622027 561 32375345899676131554243 562 34096351918208038517612 563 35907245112055561415625 564 37812638415524133015576 565 39817377375936670270670 566 41926551686035391031373 567 44145507266102155105175 568 46479858946160366217245 569 48935503752203336056024 570 51518634850777662702572 571 54235756157143113189587 572 57093697665647313679954 573 60099631508972577135228 574 63261088809547859853239 575 66585977331432934097981 576 70082600000988135042235 577 73759674306493276387996 578 77626352650485011728176 579 81692243667053349881849 580 85967434583762624058538 581 90462514642801262974359 582 95188599667389503014969 583 100157357790695352124078 584 105381036440203634164118 585 110872490597736811473251 586 116645212435549972267808 587 122713362352029267756516 588 129091801515492423065309 589 135796125943333747845757 590 142842702233788569941378 591 150248704981683693542835 592 158032156004942792776644 593 166211965417845444922820 594 174807974688069044448754 595 183841001718659390520541 596 193332888103108564838489 597 203306548600387615676644 598 213786022990179142345258 599 224796530361531754088730 600 236364526008229112528845 601 248517760991159360758043 602 261285344555155378657669 603 274697809468399317537075 604 288787180487211888539175 605 303587046023015778755167 606 319132633230899975452649 607 335460886606188590821851 608 352610550326484995706632 609 370622254436201341615190 610 389538605130587184317360 611 409404279248043314429409 612 430266123248886035285202 613 452173256802342010044403 614 475177181282920750149971 615 499331893312256480342645 616 524694003672465002574625 617 551322861742954751283748 618 579280685813695955505678 619 608632699444343885261348 620 639447274251509781140065 621 671796079312774705402193 622 705754237601480820595811 623 741400489662106580289202 624 778817364974638387269781 625 818091361241075591935446 626 859313132079830407894315 627 902577683386786035408954 628 947984578889258377701869 629 995638155179880846186939 630 1045647746800517350392786 631 1098127921694261040624844 632 1153198727643270886014254 633 1210985950044557354450966 634 1271621381693124958825939 635 1335243104962066668184699 636 1401995787104994374016849 637 1472030989111525780394689 638 1545507488902017314061198 639 1622591619337337939670587 640 1703457621895804431062406 641 1788288016542612430899142 642 1877273988715343427253284 643 1970615794005176380509007 644 2068523181535001753346063 645 2171215836673518944932376 646 2278923844170684810233748 647 2391888172418847761142766 648 2510361180016177100330679 649 2634607145408169633779104 650 2764902820882938469920187 651 2901538011774233713144454 652 3044816182255369358126587 653 3195055088663697931826169 654 3352587441855319805368547 655 3517761599623411755676336 656 3690942290806389204890982 657 3872511372221765638831374 658 4062868620189150483807091 659 4262432557890470404165410 660 4471641320479641519132718 661 4690953559312443031237639 662 4920849387370376107919745 663 5161831367383256770097985 664 5414425544899548454390295 665 5679182527955776191442424 666 5956678615784019268583768 667 6247516978368940163872474 668 6552328889499618379909273 669 6871775015302435932134688 670 7206546761124002063169105 671 7557367678941410713961823 672 7924994938411399485410139 673 8310220863944228274618433 674 8713874541177178641544434 675 9136823495460980581301748 676 9579975446019666067460952 677 10044280138645600163298903 678 10530731260899864950891925 679 11040368442950743720550498 680 11574279348356598331949462 681 12133601858221351593856892 682 12719526353393387960665145 683 13333298098458522375349635 684 13976219732593090169851625 685 14649653871379300881580149 686 15355025825077830103566859 687 16093826437842804020490588 688 16867615053839285099415682 689 17678022615166099051601949 690 18526754898048417788375623 691 19415595892658000878294526 692 20346411333572703835851563 693 21321152386728758637828689 694 22341859500470775959843165 695 23410666427093092444032891 696 24529804423120676171258470 697 25701606635311346130147465 698 26928512681325368792073887 699 28213073432684390053725856 700 29557956009722391159295280 701 30965948996847908713717641 702 32439967888640419742038273 703 33983060775859010572644594 704 35598414282775887619050941 705 37289359765738514879654613 706 39059379785337410509347769 707 40912114862982156491585182 708 42851370535308071081959090 709 44881124718193786866522309 710 47005535394945906272680496 711 49228948641494219455982896 712 51555907004382560299532628 713 53991158245555545374307215 714 56539664471058149279849491 715 59206611658906110565493594 716 61997419604688228645920290 717 64917752301525750921987827 718 67973528774515034604659758 719 71170934387765387977875703 720 74516432645854318794939499 721 78016777509427878021063324 722 81679026248606928700613811 723 85510552855682680472600890 724 89519062042754692515645553 725 93712603847702875208147623 726 98099588876305408957324052 727 102688804205967090757485352 728 107489429981209726269216710 729 112511056728640585462711667 730 117763703424085506751204018 731 123257836342048678878169731 732 129004388722931867384429715 733 135014781290831278101494567 734 141300943660320638993277501 735 147875336667922473852215146 736 154750975669899769353694699 737 161941454845201553075636234 738 169460972548686220499877699 739 177324357756855386899456636 740 185547097655004924213283421 741 194145366411715113620798905 742 203136055193683672665701854 743 212536803470828034959028908 744 222366031669097609096195685 745 232642975225267532879515295 746 243387720105960630865865137 747 254621239849883061746392231 748 266365434200724662919096434 749 278643169394824288204154021 750 291478320176686143364428645 751 304895813611995349895380258 752 318921674777321093118817321 753 333583074402172309105239230 754 348908378549201118504636013 755 364927200414744800396243211 756 381670454342653801162787874 757 399170412140672511040610313 758 417460761800064119950254407 759 436576668715417478457510098 760 456554839513709657640759370 761 477433588597879366884905372 762 499252907523057577643841365 763 522054537319725750536637619 764 545882043891768889825949596 765 570780896613464175554391876 766 596798550264000990663563857 767 623984530434162496206754040 768 652390522555266144453648460 769 682070464696467541223003714 770 713080644292972430913838087 771 745479798963692493164665836 772 779329221594358099559698358 773 814692869858092469363665613 774 851637480364032045686251426 775 890232687620586990123415986 776 930551148019693093970887363 777 972668669044450275576532803 778 1016664343923555150030077426 779 1062620691952037115010009611 780 1110623804720155062052089582 781 1160763498488496604126824541 782 1213133472971094911145379590 783 1267831476784670575131418992 784 1324959479847399638670995884 785 1384623853007041032185189552 786 1446935555205169269446146855 787 1512010328480864508244150684 788 1579968901145853493191049287 789 1650937199459910200556990353 790 1725046568165811155035849740 791 1802434000240208638097208041 792 1883242376249236349553784679 793 1967620713695030209665796237 794 2055724426773897644376595511 795 2147715596964584920732688903 796 2243763254901883743777665727 797 2344043673988941694604669081 798 2448740676240821332953486979 799 2558045950850446541505978645 800 2672159386009807381794475018 801 2791289414518424431741362596 802 2915653373755532033970820940 803 3045477880592184138733901736 804 3180999221866851699320512973 805 3322463761048523704423704812 806 3470128361761796406513328589 807 3624260828849665310121629173 808 3785140367703526396015303422 809 3953058062592013717241899934 810 4128317374777634092382245724 811 4311234661213282370551195948 812 4502139714671841328110521574 813 4701376326166312026900844555 814 4909302870583088182513989086 815 5126292916456484921517435614 816 5352735860882120163983050082 817 5589037590573644952975522477 818 5835621170141427660930977762 819 6092927558680250401225770436 820 6361416355832124454010355551 821 6641566578500517489884653301 822 6933877469476609324222546909 823 7238869339250302091989183830 824 7557084442368678840774874601 825 7889087889718838423226048955 826 8235468598208038625141492661 827 8596840279330667856920188603 828 8973842468214018530402909323 829 9367141594754025325235303047 830 9777432098561485629937626339 831 10205437589461333303446133630 832 10651912055404273617745822489 833 11117641119675301395492941806 834 11603443349408251734075686096 835 12110171617444226216631032728 836 12638714519704811432227035875 837 13189997850283518554951062435 838 13764986136600984957772167626 839 14364684237006190288193502640 840 14990139003357715512672097601 841 15642441011160394578004234067 842 16322726359994831529037712115 843 17032178547023623430942389070 844 17772030416531327667895404935 845 18543566188507114165236067976 846 19348123569464086931139730095 847 20187095948747221133959206941 848 21061934683779591716148466218 849 21974151477761151390201903725 850 22925320853545627452590765405 851 23917082727492931876134405650 852 24951145087320322165294020678 853 26029286778055289447264104634 854 27153360400434558724216412138 855 28325295326181955266440584681 856 29547100834855968067661047683 857 30820869377055633724006193231 858 32148779969049280165693075726 859 33533101723998739448930831047 860 34976197525246666900467133091 861 36480527847253863596243608935 862 38048654730088997947548541716 863 39683245913504579116233409764 864 41387079136970447950274861356 865 43163046612180789630215723533 866 45014159674911566947358770224 867 46943553623264452874660967979 868 48954492749719391682587465794 869 51050375574592814950752650167 870 53234740288911525557107930199 871 55511270414904250667817261493 872 57883800692754718741347523855 873 60356323202470664336954845889 874 62932993730195949046650754276 875 65618138388523709604325003030 876 68416260500874355334704107447 877 71332047760254869818881704066 878 74370379673257288931397640708 879 77536335300430629129744032859 880 80835201304740006790450028664 881 84272480320128895218264665414 882 87853899652820691728593315361 883 91585420328325967008159461287 884 95473246497785686407168455791 885 99523835217641232675968555731 886 103743906617332804685576154009 887 108140454470121209344676752873 888 112720757182888979113000637503 889 117492389221205850260666745253 890 122463232986758337586047737989 891 127641491164710859137764541749 892 133035699559438217182815677552 893 138654740437578796345408789179 894 144507856398291968809817837430 895 150604664791158053751896632495 896 156955172703159540265482932980 897 163569792536786158240842310584 898 170459358202377745133186628946 899 177635141948475793510909942600 900 185108871855102017531797674517 901 192892750015596624538399675466 902 200999471433878015765438400985 903 209442243664762062840825516711 904 218234807226295609129708232471 905 227391456813902410492602744561 906 236927063347549974790331649932 907 246857096884061917911754150866 908 257197650428211215728692883167 909 267965464677224327513398142842 910 279177953734944695723401059942 911 290853231832983504092839234538 912 303010141097919617749867559520 913 315668280404781606947539880028 914 328848035358902662186819669961 915 342570609449509101833569292951 916 356858056420393884732309681569 917 371733313904403277762617106276 918 387220238370597898064536281148 919 403343641434441454128007215444 920 420129327583656234316580917643 921 437604133374001004663319512804 922 455795968151676380300572827130 923 474733856360813755148729785974 924 494447981497128737458513914263 925 514969731770716104039841739612 926 536331747543776301180946811508 927 558567970611116041317487614662 928 581713695394280301653965706530 929 605805622122394350397796763616 930 630881912076025454460135097501 931 656982244972777302773159430445 932 684147878576793121207810511920 933 712421710616943122274094432794 934 741848343102183539030430347292 935 772474149125385820336034503170 936 804347342250912747914186435086 937 837518048584257739961008394803 938 872038381626327642836164065076 939 907962520018234708949409186272 940 945346788287033992447876105587 941 984249740706392812020118570381 942 1024732248391078039695190272285 943 1066857589747982959551416605972 944 1110691544411666875692137047106 945 1156302490796524238952818971392 946 1203761507403329257974311058021 947 1253142478022376932862634408235 948 1304522200981475615240161639419 949 1357980502591878087623354962544 950 1413600354951706545167150458350 951 1471467998271643054587834468442 952 1531673067894591011085627498796 953 1594308726186643135791051021450 954 1659471799484124578921265549830 955 1727262920287555247811145633187 956 1797786674901343606289491826618 957 1871151756724579277342701020303 958 1947471125406833598042252296905 959 2026862172089948526547348681594 960 2109446890965951093226090651821 961 2195352057388857328621445414888 962 2284709412787945725808852818078 963 2377655856638304695069504864859 964 2474333645754981431313694177687 965 2574890601185927085431866691543 966 2679480322990213764538741072081 967 2788262413197558163298887452252 968 2901402707257279530880963475333 969 3019073514295123019001263926431 970 3141453866509343097591279064584 971 3268729778048545371569652308402 972 3401094513727682082192546002374 973 3538748867950560878352338358700 974 3681901454222123883309938007647 975 3830769005646643741061790533231 976 3985576686823953200706317532945 977 4146558417569709413217919780223 978 4313957208902813414529865700866 979 4488025511758059509786729367183 980 4669025578900440638202615804208 981 4857229840533639707652820713400 982 5052921294114908811768596067714 983 5256393908905877883846245483143 984 5467953045809921528331553222860 985 5687915893065380454510033447079 986 5916611918386538008479132299579 987 6154383338164346970217826831480 988 6401585604363131553615966264043 989 6658587909771117542946659977544 990 6925773712288615419868866108004 991 7203541278960956690324871484556 992 7492304250491122613363972369601 993 7792492226992049462779928771890 994 8104551375768434271933746346824 995 8428945061944810806198596784900 996 8766154502788649291322939742645 997 9116679446606220852446324073167 998 9481038877123248878029646348265 999 9859771744293549424727351296392 1000 10253437722515605866482948615801