0 1 1 1 2 2 3 2 4 3 5 3 6 5 7 5 8 8 9 9 10 13 11 15 12 22 13 25 14 35 15 42 16 56 17 67 18 89 19 106 20 138 21 166 22 211 23 254 24 321 25 384 26 479 27 575 28 709 29 848 30 1040 31 1239 32 1508 33 1795 34 2168 35 2574 36 3095 37 3661 38 4379 39 5171 40 6154 41 7246 42 8592 43 10088 44 11915 45 13960 46 16425 47 19197 48 22520 49 26253 50 30702 51 35718 52 41647 53 48343 54 56225 55 65122 56 75548 57 87332 58 101067 59 116601 60 134648 61 155039 62 178652 63 205344 64 236132 65 270929 66 310963 67 356170 68 408047 69 466611 70 533624 71 609238 72 695579 73 792907 74 903812 75 1028765 76 1170828 77 1330773 78 1512302 79 1716487 80 1947827 81 2207852 82 2501929 83 2832215 84 3205192 85 3623698 86 4095606 87 4624712 88 5220437 89 5887817 90 6638249 91 7478187 92 8421449 93 9476371 94 10659544 95 11981700 96 13462886 97 15116627 98 16967207 99 19031740 100 21339418 101 23911835 102 26784254 103 29983572 104 33552416 105 37524345 106 41950628 107 46873054 108 52353456 109 58443397 110 65217507 111 72739458 112 81098954 113 90374473 114 100674038 115 112093787 116 124763798 117 138801829 118 154364068 119 171594523 120 190680896 121 211798492 122 235172862 123 261017330 124 289602260 125 321186853 126 356095341 127 394641604 128 437214306 129 484193271 130 536043531 131 593224105 132 656291386 133 725798624 134 802411184 135 886795382 136 979745605 137 1082063337 138 1194696816 139 1318608065 140 1454928241 141 1604811074 142 1769604113 143 1950689438 144 2149671689 145 2368203565 146 2608194591 147 2871619380 148 3160747520 149 3477935704 150 3825880114 151 4207389270 152 4625663840 153 5084047904 154 5586336957 155 6136508818 156 6739061663 157 7398721011 158 8120814034 159 8910949754 160 9775430912 161 10720908962 162 11754836211 163 12885091294 164 14120479366 165 15470324961 166 16945022325 167 18555597524 168 20314312650 169 22234192365 170 24329692016 171 26616184919 172 29110697566 173 31831360283 174 34798214856 175 38032623081 176 41558159461 177 45399973906 178 49585774461 179 54145147466 180 59110637817 181 64517020846 182 70402496543 183 76807909205 184 83778062904 185 91360893908 186 99608918037 187 108578349896 188 118330703304 189 128931854055 190 140453804469 191 152973696560 192 166575755712 193 181350249107 194 197395636377 195 214817471129 196 233730774619 197 254258890940 198 276536105169 199 300706448428 200 326926597264 201 355364629260 202 386203227437 203 419638401891 204 455883029523 205 495165541766 206 537733848781 207 583853998451 208 633814519648 209 687925076239 210 746521272981 211 809963310413 212 878641319493 213 952974031020 214 1033414689618 215 1120449773393 216 1214605549195 217 1316446859434 218 1426584408758 219 1545673644475 220 1674422848223 221 1813592164483 222 1964002586263 223 2126535165505 224 2302141016136 225 2491840754408 226 2696735626363 227 2918007260052 228 3156930044793 229 3414871256894 230 3693304861666 231 3993812092793 232 4318096832236 233 4667986767383 234 5045450531947 235 5452599544645 236 5891707148594 237 6365211262360 238 6875735742947 239 7426094034769 240 8019313019149 241 8658637830306 242 9347558524222 243 10089816267630 244 10889433151558 245 11750720031502 246 12678309863609 247 13677167462473 248 14752626827647 249 15910403138954 250 17156634544057 251 18497896803879 252 19941250084021 253 21494256663534 254 23165033390554 255 24962272942016 256 26895302622103 257 28974109784576 258 31209407754000 259 33612666039320 260 36196184312172 261 38973128147764 262 41957612038560 263 45164741562448 264 48610706550556 265 52312830630203 266 56289675871796 267 60561100804648 268 65148377949547 269 70074261628266 270 75363119986493 271 81041014007490 272 87135845905728 273 93677450971883 274 100697764357236 275 108230927677726 276 116313476485997 277 124984463720099 278 134285670534316 279 144261748983492 280 154960459107442 281 166432833655196 282 178733444707988 283 191920593501838 284 206056610382021 285 221208073219443 286 237446144837777 287 254846824084281 288 273491325418370 289 293466367097674 290 314864598313792 291 337784929571199 292 362333013281589 293 388621622196934 294 416771190144911 295 446910244983574 296 479176017116744 297 513714934314754 298 550683306432457 299 590247890521986 300 632586661258578 301 677889455679900 302 726358840145339 303 778210845273266 304 833675941407362 305 892999875828240 306 956444770222302 307 1024290073577190 308 1096833796972470 309 1174393597317633 310 1257308166453070 311 1345938462976582 312 1440669274775947 313 1541910618134447 314 1650099495343154 315 1765701482735837 316 1889212707429678 317 2021161648846962 318 2162111361623691 319 2312661517974177 320 2473450907307248 321 2645159750251915 322 2828512508954706 323 3024280507623333 324 3233285091659848 325 3456400593590767 326 3694557884045649 327 3948747726792256 328 4220024769448007 329 4509511336959301 330 4818401915776490 331 5147967440816277 332 5499560333558505 333 5874619344324505 334 6274675211653138 335 6701356129532566 336 7156394103557448 337 7641631120821201 338 8159026287682384 339 8710662789505166 340 9298755904572313 341 9925660851702199 342 10593881786185015 343 11306080644661710 344 12065087241870228 345 12873909235390180 346 13735743455603141 347 14653987127930852 348 15632250584165257 349 16674369895761720 350 17784421132558028 351 18966734579055925 352 20225910725571009 353 21566836260248345 354 22994701999532578 355 24515020870919219 356 26133648014313140 357 27856800996016076 358 29691082339040344 359 31643502237601241 360 33721503804691102 361 35932988587346439 362 38286344853846543 363 40790476245322859 364 43454833461739082 365 46289446425135645 366 49304959765329636 367 52512668913117109 368 55924559833559923 369 59553349516249697 370 63412530455007318 371 67516416057054421 372 71880190425563069 373 76519959269162236 374 81452805608348416 375 86696846834010555 376 92271297029097028 377 98196530900175711 378 104494153485056735 379 111187071763659426 380 118299572610992863 381 125857402986167994 382 133887857087131327 383 142419866120127206 384 151484095721525845 385 161113046423345522 386 171341162529179092 387 182204944518509403 388 193743070697080633 389 205996522924627450 390 219008722509444149 391 232825670799824764 392 247496100959165606 393 263071635135689324 394 279606953937339402 395 297159972088568141 396 315792027628783509 397 335568078178429326 398 356556912112470110 399 378831367796419729 400 402468569236747602 401 427550170912900396 402 454162620685936949 403 482397433144586313 404 512351482864189480 405 544127309510462543 406 577833444882904128 407 613584753381925513 408 651502796651979754 409 691716213416390787 410 734361125958872603 411 779581563774245321 412 827529916593411643 413 878367406791101625 414 932264594178238803 415 989401902651047775 416 1049970182550640461 417 1114171297641788554 418 1182218751474269103 419 1254338341449702662 420 1330768856324388940 421 1411762804861338703 422 1497587192396350886 423 1588524332392706894 424 1684872710854376412 425 1786947890010252950 426 1895083470315181091 427 2009632096493343746 428 2130966527927951376 429 2259480758405732357 430 2395591206865098714 431 2539737963415758157 432 2692386113711151458 433 2854027125175882725 434 3025180319703089891 435 3206394415528046052 436 3398249164533331990 437 3601357066873460571 438 3816365190923218153 439 4043957079595838144 440 4284854772908750724 441 4539820926972516008 442 4809661061286097542 443 5095225913624145887 444 5397413936539826154 445 5717173913859375785 446 6055507733486270978 447 6413473293956984774 448 6792187583524102601 449 7192829908261212047 450 7616645310591505841 451 8064948153774480390 452 8539125916569909450 453 9040643172636401908 454 9571045801904325381 455 10131965407500226634 456 10725123988693663437 457 11352338842462757596 458 12015527747618380504 459 12716714403098276434 460 13458034178093846517 461 14241740144649007895 462 15070209454380794497 463 15945950029006991817 464 16871607630614650319 465 17849973280416653940 466 18883991096532142006 467 19976766518637444065 468 21131574994957721865 469 22351871098590876684 470 23641298153940938258 471 25003698339443686448 472 26443123353068015730 473 27963845606040513966 474 29570370037402632568 475 31267446514198337551 476 33060082916496253252 477 34953558871485175658 478 36953440242944778650 479 39065594339896430774 480 41296205958364887587 481 43651794219765106590 482 46139230328065417276 483 48765756209104438840 484 51539004163069609762 485 54467017493575712958 486 57558272253881935502 487 60821700073971137736 488 64266712219309318399 489 67903224845537117020 490 71741685610997313559 491 75793101612177583717 492 80069068815916136194 493 84581802954613853042 494 89344172071194632588 495 94369730681588542428 496 99672755755398910280 497 105268284484498172542 498 111172154055226837557 499 117401043396402560063 500 123972517135036533403 501 130905071734963332850 502 138218184067810961406 503 145932362395147023940 504 154069200030155348826 505 162651431662012470698 506 171702992631788937271 507 181249081148147774330 508 191316223753804809331 509 201932344037016883440 510 213126834922992581191 511 224930634546475980183 512 237376306066300848897 513 250498121431234894685 514 264332149485950477714 515 278916348435752474202 516 294290663089235142158 517 310497126908187724908 518 327579969316783146961 519 345585728311567980116 520 364563368859889597534 521 384564407142190991699 522 405643041164360955208 523 427856287811379791594 524 451264126910242612005 525 475929652391289179052 526 501919231161234106338 527 529302669797260085049 528 558153389724574914146 529 588548611009620090850 530 620569545484605304831 531 654301599361221387243 532 689834586107002808657 533 727262949771042722705 534 766685999595215897464 535 808208156129977836485 536 851939209758940424845 537 897994591887509226797 538 946495659773650714436 539 997569995296593049077 540 1051351718721696782112 541 1107981817802557304378 542 1167608493365647594896 543 1230387521769013972863 544 1296482635474909008066 545 1366065922184103821735 546 1439318243874466417534 547 1516429676254136989155 548 1597599970083488727036 549 1683039034945758959025 550 1772967447041816882261 551 1867616981666234185593 552 1967231172071892108803 553 2072065895466067349569 554 2182389987988476285479 555 2298485889509297136532 556 2420650320253380031208 557 2549194990194034717039 558 2684447343391880870032 559 2826751338338824088549 560 2976468266666730334053 561 3133977611409907268490 562 3299677947381168061959 563 3473987884993292791721 564 3657347060303360031397 565 3850217172769459240068 566 4053083073734075077963 567 4266453907297749480723 568 4490864306854937978933 569 4726875649147836206328 570 4975077369390317124809 571 5236088339529739680059 572 5510558313503681963592 573 5799169441793015702455 574 6102637859460155578635 575 6421715350231402325177 576 6757191091173187035173 577 7109893480804759149086 578 7480692055589977451058 579 7870499497962927250446 580 8280273741257570136181 581 8711020175039708511009 582 9163793956676727824640 583 9639702433021305606391 584 10139907678550966053899 585 10665629154255111579955 586 11218146494162623874503 587 11798802424258299911291 588 12409005821281130467938 589 13050234916654380851853 590 13724040653693530940933 591 14432050203892949768331 592 15175970651148243056812 593 15957592850320020579025 594 16778795469769782950129 595 17641549224937532997253 596 18547921313434150151244 597 19500080059446398447615 598 20500299778844581820984 599 21550965873589515291974 600 22654580167826960283623 601 23813766495142054370118 602 25031276550448498558134 603 26309996016945004797116 604 27652950982796672070434 605 29063314659025794114445 606 30544414414557381843489 607 32099739141056397749813 608 33732946964903714823314 609 35447873320209930499004 610 37248539401739951726242 611 39139161013029476901047 612 41124157830227225054029 613 43208163098456853493381 614 45396033783040457295621 615 47692861194033075075710 616 50103982108378193527791 617 52634990409945014021496 618 55291749273899614431874 619 58080403917652128003484 620 61007394947163759530765 621 64079472323022463479653 622 67303709977608988638319 623 70687521110131156582798 624 74238674193610159921700 625 77965309723186414064997 626 81875957742834920388359 627 85979556182687757141261 628 90285470047325316118548 629 94803511490326281892960 630 99543960818998263859985 631 104517588467957327832946 632 109735677989352773718713 633 115210050102095052654847 634 120953087852099225346554 635 126977762929931043136541 636 133297663202455459176047 637 139927021509273732907894 638 146880745785540388559461 639 154174450566748045386267 640 161824489942502132436280 641 169847992020114299022856 642 178262894970944742800524 643 187087984726041035160538 644 196342934400431213788177 645 206048345518857761619839 646 216225791129302318967351 647 226897860883893486782648 648 238088208181153104563600 649 249821599456595947293157 650 262123965723910831623396 651 275022456461831852416486 652 288545495957925302619962 653 302722842213225510799389 654 317585648528730355410722 655 333166527887309292400228 656 349499620262676082708263 657 366620662979463487470146 658 384567064267623853374774 659 403377980146618413887894 660 423094394795201515278748 661 443759204554711769967821 662 465417305735356845618076 663 488115686386966086797085 664 511903522218571136526620 665 536832276843061637869645 666 562955806547445223176547 667 590330469781048077872571 668 619015241579761887478329 669 649071833136193460225778 670 680564816752928062173259 671 713561756407838477862571 672 748133344189415820988786 673 784353542851820676716399 674 822299734770198282674330 675 862052877568560178373637 676 903697666725300981204201 677 947322705453253462701449 678 993020682186000220977242 679 1040888555994115459417756 680 1091027750292011808658523 681 1143544355188192749292200 682 1198549338871046409016892 683 1256158768414668820290474 684 1316494040431031010071556 685 1379682121987446507979902 686 1445855802252782375415075 687 1515153955328858686384264 688 1587721814770809786368763 689 1663711260293620355951276 690 1743281117212413525040489 691 1826597469158033155858149 692 1913833984663071104270086 693 2005172258208076311699380 694 2100802166374759891056656 695 2200922239748324652489820 696 2305740051271833029922895 697 2415472621751688713596368 698 2530346843278058822060543 699 2650599921321202209499929 700 2776479836333664119809660 701 2908245825686558229956852 702 3046168886841691278995185 703 3190532302660828251171627 704 3341632189831788848817506 705 3499778071392065753562530 706 3665293474414249600591221 707 3838516553920195800699025 708 4019800744180031800307586 709 4209515438556617130822663 710 4408046699151196571097090 711 4615797997512597010529737 712 4833190987773836435859528 713 5060666313588976823411094 714 5298684450351416293333516 715 5547726584186414214776338 716 5808295529326343127780380 717 6080916685491702347340765 718 6366139037024492976678968 719 6664536195538375712813254 720 6976707487982028774833089 721 7303279092033596041128170 722 7644905220885152486904356 723 8002269359501641737442451 724 8376085554589475020744309 725 8767099760540006103563507 726 9176091243774233213461935 727 9603874047950085988939178 728 10051298522665952664986910 729 10519252918334618749297745 730 11008665050086063109050373 731 11520504033604159155076009 732 12055782095999458055374353 733 12615556464873548193898008 734 13200931338941413729288787 735 13813059943638933110453758 736 14453146675368403628577147 737 15122449338103844989545523 738 15822281476319489561076558 739 16554014808282698624242424 740 17319081764011285463193301 741 18118978132282909431082685 742 18955265821361301267194423 743 19829575738202581830086382 744 20743610791201749885123419 745 21699149021649788150188017 746 22698046869389835829276460 747 23742242578284264911104877 748 24833759747445263280687008 749 25974711034319177730845238 750 27167302016080102655531935 751 28413835215941466168785568 752 29716714301385896950836525 753 31078448461484007582928888 754 32501656970892533680082444 755 33989073948311306609052144 756 35543553317628735385293579 757 37168073980194936140548423 758 38865745207144526449943286 759 40639812260922874328892278 760 42493662255687614995738146 761 44430830266513379396025841 762 46455005697883496329689968 763 48570038922235143714080867 764 50779948199920892655057608 765 53088926892261295640789633 766 55501350980003364891712159 767 58021786899843106066814403 768 60654999712357504188554834 769 63405961615069129183910781 770 66279860815104364187802562 771 69282110776321558151287297 772 72418359856577686917004873 773 75694501351258270334041719 774 79116683960046158352299039 775 82691322694405445335877731 776 86425110244170676579127621 777 90325028822180557460779637 778 94398362506877120862630858 779 98652710103393001118281513 780 103095998544704216315135962 781 107736496855084799736943705 782 112582830699232951692199193 783 117643997541159546580835512 784 122929382438147736292445698 785 128448774495881171807248223 786 134212384012147304748314212 787 140230860337384467248870296 788 146515310481748360155479312 789 153077318499315587736672992 790 159928965681554296199297501 791 167082851593220589980329188 792 174552115985465376078017247 793 182350461622058910312626838 794 190492178056388547179701981 795 198992166398109824913714337 796 207865965110210862235085558 797 217129776878585334266309500 798 226800496598230840155518581 799 236895740521644787585596229 800 247433876617164027386927930 801 258434056186579922358807559 802 269916246793698906264789951 803 281901266557245117824776052 804 294410819864016927549808848 805 307467534560088608252009221 806 321095000680554064506700892 807 335317810780354649735195948 808 350161601931643811573473125 809 365653099455365909049283999 810 381820162457858040398160398 811 398691831245702733881350757 812 416298376695428582011499548 813 434671351657285437685225600 814 453843644475946005675600292 815 473849534713843134167547910 816 494724751166752964670250616 817 516506532264338305600771029 818 539233688952564252399580995 819 562946670158269317917125330 820 587687630940692590597345653 821 613500503438417632529641268 822 640431070725055215488235776 823 668527043690959806783110340 824 697838141073506657619618688 825 728416172762767318597445272 826 760315126515052353440482959 827 793591258211466720488238142 828 828303185804683868788449555 829 864511987102216773146882552 830 902281301540987316525039779 831 941677436113495182196051311 832 982769475612908711813739810 833 1025629397370362150704631801 834 1070332190665301318403263504 835 1116955980996181284077711265 836 1165582159406954707058413798 837 1216295517071790918114200498 838 1269184385349222649735104098 839 1324340781524502080053409671 840 1381860560468374104210912851 841 1441843572448689722421485854 842 1504393827341429408875028963 843 1569619665496602061214081156 844 1637633935525408057987278701 845 1708554179284685945280627055 846 1782502824346420585051491776 847 1859607384250515605129786500 848 1940000666851690651885615135 849 2023820991082646295329227269 850 2111212412469265288023058676 851 2202324957745826832836083313 852 2297314868932878629010255837 853 2396344857253618597719203983 854 2499584367280428278425236301 855 2607209851717485472926832608 856 2719405057242381555143865556 857 2836361321845118332242909265 858 2958277884121157216845476566 859 3085362204991898864633408225 860 3217830302345668632836791958 861 3355907099110343688587341929 862 3499826785289960954100449245 863 3649833194517167442817525139 864 3806180195696198973584898509 865 3969132100332172565625163516 866 4138964086167046955802737808 867 4315962637765405848797638160 868 4500426004719665348455076020 869 4692664678168941483465099941 870 4893001886354281319413485305 871 5101774109959573606257837214 872 5319331618018097092996894224 873 5546039025193409799458329042 874 5782275871276264809800391685 875 6028437223770282582903361852 876 6284934304474610108255383073 877 6552195141005320261356890074 878 6830665244235514502448174342 879 7120808312670286698796323504 880 7423106964813830922966819001 881 7738063500625050086756066881 882 8066200693202283938135151442 883 8408062611879951931880597661 884 8764215477967542723352555625 885 9135248554406902615044868942 886 9521775070675041968845405872 887 9924433184308801707242169105 888 10343886980482894238145306314 889 10780827511125837389044510422 890 11235973875117673420529566243 891 11710074341170550320033090587 892 12203907515057135268254879409 893 12718283552913518650597981499 894 13254045422412020634642453847 895 13812070213665851052494950632 896 14393270501801555288394201105 897 14998595763206940934302572426 898 15629033847541785102506502365 899 16285612507676008992993324702 900 16969400989805658964859847531 901 17681511686080476303114890048 902 18423101852168994126793746249 903 19195375392277063158027796275 904 19999584714234858060811292802 905 20837032657364398713622321509 906 21709074495946291177910747148 907 22617120021208931747003904554 908 23562635704878174207648853293 909 24547146947438131910940917456 910 25572240414377237440390919053 911 26639566463815107146412592979 912 27750841669038556773551728229 913 28907851439605958572277550739 914 30112452744821978920353991815 915 31366576943525715891840667335 916 32672232724288908580976117777 917 34031509160272776821439644794 918 35446578883157316056606310104 919 36919701380720493092566709180 920 38453226422822538425183181059 921 40049597620726775430036164117 922 41711356124879595090138499919 923 43441144466462008965640474691 924 45241710548230803679207311244 925 47115911790371750656822039754 926 49066719437308415646304260876 927 51097223031630252830103428494 928 53210635061541417066559758911 929 55410295788468763332106233765 930 57699678261723152290851908464 931 60082393527363385137220159771 932 62562196038686976805442974672 933 65142989276046717402799430782 934 67828831583987527159390206406 935 70623942233993856725981503578 936 73532707721455648538664114296 937 76559688305779205274994363324 938 79709624802910936024562680742 939 82987445639884559517302285560 940 86398274181369602845196475293 941 89947436338567741097069767398 942 93640468471198321008432261715 943 97483125593711171130880541340 944 101481389897289181212160767539 945 105641479599630043487677578877 946 109969858134952705135966350099 947 114473243697133394504720188984 948 119158619149366371260959736341 949 124033242314238685810347338519 950 129104656658635178961845806257 951 134380702388421506069315268358 952 139869527968419285606189282684 953 145579602083759230339866895645 954 151519726059306715338283505846 955 157699046754469191551047223385 956 164127069951348852970035330497 957 170813674254865326720434561415 958 177769125524175908679494979974 959 185004091855432081025989543809 960 192529659136666150452635755304 961 200357347196366609704901213151 962 208499126568112133586985824143 963 216967435894456402466743809878 964 225775199994127598802671680169 965 234935848617490479597440576045 966 244463335916155362989096339101 967 254372160653568768128025261904 968 264677387184426427026563163506 969 275394667231771032439166704609 970 286540262491717716771816726520 971 298131068096848404496138591749 972 310184636970476940544917939243 973 322719205105167186809795718920 974 335753717800133042682997959413 975 349307856893417827214188040333 976 363402069026089528363063065335 977 378057594977051587450208213838 978 393296500108507015055741307494 979 409141705963578437851335537990 980 425617023059131108916589965144 981 442747184918419821774014920530 982 460557883389839174434897224610 983 479075805299747646032922463037 984 498328670489116856411572174639 985 518345271285574086950683194319 986 539155513464318379882694897545 987 560790458753342136040830682677 988 583282368940443274032805489790 989 606664751641609378817725466884 990 630972407792559576890425266128 991 656241480927481581743688590451 992 682509508311367829031052861546 993 709815473994773010216746269094 994 738199863862355746807958809876 995 767704722749164377436321076447 996 798373713701353858670601361586 997 830252179460809883789314200709 998 863387206256083492268834110827 999 897827689985034388054702726696 1000 933624404877723008811705095742