0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 11 56 12 77 13 100 14 133 15 172 16 224 17 285 18 366 19 460 20 582 21 725 22 905 23 1116 24 1380 25 1686 26 2063 27 2503 28 3036 29 3655 30 4401 31 5262 32 6290 33 7476 34 8877 35 10489 36 12384 37 14552 38 17084 39 19978 40 23334 41 27156 42 31570 43 36578 44 42333 45 48849 46 56297 47 64707 48 74287 49 85067 50 97299 51 111036 52 126560 53 143948 54 163540 55 185425 56 210005 57 237405 58 268079 59 302196 60 340293 61 382562 62 429636 63 481769 64 539672 65 603666 66 674585 67 752802 68 839286 69 934502 70 1039543 71 1154981 72 1282083 73 1421506 74 1574714 75 1742509 76 1926533 77 2127747 78 2348042 79 2588523 80 2851355 81 3137850 82 3450438 83 3790670 84 4161319 85 4564153 86 5002329 87 5477923 88 5994463 89 6554363 90 7161629 91 7819004 92 8531017 93 9300841 94 10133529 95 11032739 96 12004167 97 13051942 98 14182475 99 15400502 100 16713148 101 18125814 102 19646498 103 21281274 104 23039092 105 24926852 106 26954477 107 29129786 108 31463856 109 33965430 110 36646856 111 39518001 112 42592509 113 45881477 114 49400076 115 53160671 116 57180092 117 61472199 118 66055542 119 70945627 120 76162989 121 81724822 122 87653830 123 93969189 124 100695843 125 107855124 126 115474549 127 123577695 128 132194866 129 141352216 130 151082958 131 161416060 132 172388026 133 184030746 134 196384297 135 209483911 136 223373383 137 238091562 138 253686437 139 270200645 140 287686698 141 306191497 142 325772294 143 346480619 144 368379006 145 391523820 146 415983299 147 441819235 148 469105831 149 497910726 150 528314754 151 560391695 152 594229505 153 629908782 154 667524961 155 707165997 156 748935563 157 792929324 158 839259810 159 888031219 160 939365365 161 993375601 162 1050193944 163 1109943379 164 1172766841 165 1238797888 166 1308190930 167 1381090877 168 1457664666 169 1538069121 170 1622484589 171 1711080939 172 1804052588 173 1901583352 174 2003882972 175 2111149939 176 2223610336 177 2341478619 178 2464998052 179 2594400159 180 2729946816 181 2871887468 182 3020503840 183 3176064836 184 3338873011 185 3509218000 186 3687424878 187 3873805083 188 4068707635 189 4272467521 190 4485458922 191 4708041905 192 4940617736 193 5183572815 194 5437337195 195 5702325669 196 5978998490 197 6267800603 198 6569224718 199 6883747464 200 7211895961 201 7554180856 202 7911165395 203 8283396339 204 8671475616 205 9075987879 206 9497576045 207 9936865387 208 10394541798 209 10871273563 210 11367792525 211 11884812118 212 12423112770 213 12983456152 214 13566673647 215 14173577980 216 14805054848 217 15461970494 218 16145268015 219 16855870747 220 17594781914 221 18362985147 222 19161547676 223 19991516353 224 20854025918 225 21750190477 226 22681215492 227 23648286058 228 24652682732 229 25695664944 230 26778592414 231 27902803544 232 29069740890 233 30280826060 234 31537589457 235 32841539820 236 34194299999 237 35597471079 238 37052772644 239 38561903014 240 40126684137 241 41748916034 242 43430528315 243 45173428665 244 46979659225 245 48851240864 246 50790334667 247 52799079872 248 54879762482 249 57034646782 250 59266149323 251 61576665764 252 63968750386 253 66444936098 254 69007921736 255 71660385050 256 74405175795 257 77245123676 258 80183237509 259 83222505711 260 86366103824 261 89617187452 262 92979106162 263 96455190852 264 100048974197 265 103763970008 266 107603902772 267 111572478795 268 115673622594 269 119911242044 270 124289471937 271 128812430413 272 133484472277 273 138309936606 274 143293407570 275 148439455461 276 153752905208 277 159238568080 278 164901520768 279 170746827516 280 176779827261 281 183005848685 282 189430505762 283 196059402688 284 202898440732 285 209953512926 286 217230819692 287 224736555811 288 232477235048 289 240459366307 290 248689790475 291 257175345490 292 265923212599 293 274940573134 294 284234964556 295 293813925546 296 303685365079 297 313857195693 298 324337712773 299 335135218803 300 346258413115 301 357716003670 302 369517110864 303 381670866542 304 394186828724 305 407074570971 306 420344108442 307 434005473837 308 448069158407 309 462545674303 310 477446007408 311 492781169215 312 508562661764 313 524802015218 314 541511268879 315 558702494141 316 576388288106 317 594581285375 318 613294664723 319 632541645528 320 652336011534 321 672691591725 322 693622797703 323 715144092478 324 737270541762 325 760017266438 326 783400012168 327 807434585186 328 832137436383 329 857525084236 330 883614713879 331 910423582530 332 937969638005 333 966270906433 334 995346126358 335 1025214122588 336 1055894456220 337 1087406779942 338 1119771508841 339 1153009156753 340 1187141023633 341 1222188517155 342 1258173857200 343 1295119377607 344 1333048252678 345 1371983778851 346 1411950118977 347 1452971568152 348 1495073316143 349 1538280692213 350 1582619951047 351 1628117496125 352 1674800684513 353 1722697033409 354 1771835044388 355 1822243387532 356 1873951750514 357 1926990000056 358 1981389051198 359 2037180010722 360 2094395067030 361 2153066609864 362 2213228146660 363 2274913398087 364 2338157235782 365 2402994758784 366 2469462253292 367 2537596243873 368 2607434481155 369 2679014967508 370 2752376967582 371 2827560013543 372 2904604938920 373 2983552857201 374 3064446225387 375 3147327795434 376 3232241701952 377 3319232392038 378 3408345737823 379 3499627937998 380 3593126661680 381 3688889921297 382 3786967242213 383 3887408512533 384 3990265178978 385 4095589066857 386 4203433609169 387 4313852636184 388 4426901631720 389 4542636498358 390 4661114841665 391 4782394703748 392 4906535882478 393 5033598633023 394 5163645015998 395 5296737573046 396 5432940704450 397 5572319311409 398 5714940210713 399 5860870743090 400 6010180218373 401 6162938496471 402 6319217463860 403 6479089579261 404 6642629389110 405 6809912037556 406 6981014814308 407 7156015635549 408 7334994624754 409 7518032556516 410 7705212478593 411 7896618117970 412 8092335537010 413 8292451508870 414 8497055208633 415 8706236549505 416 8920087917237 417 9138702466676 418 9362175892327 419 9590604692395 420 9824087976141 421 10062725686741 422 10306620454379 423 10555875777203 424 10810597912425 425 11070894023088 426 11336874108118 427 11608649105627 428 11886332870923 429 12170040235864 430 12459889027098 431 12755998089192 432 13058489343812 433 13367485767255 434 13683113500216 435 14005499778956 436 14334775087308 437 14671071049814 438 15014522626994 439 15365265960420 440 15723440620990 441 16089187405409 442 16462650629122 443 16843975882557 444 17233312369463 445 17630810612810 446 18036624848940 447 18450910682296 448 18873827526399 449 19305536216370 450 19746201497841 451 20195989586461 452 20655070715246 453 21123616640504 454 21601803238608 455 22089807967355 456 22587812512970 457 23096000196013 458 23614558679829 459 24143677320094 460 24683549925051 461 25234372058343 462 25796343852221 463 26369667252047 464 26954548893764 465 27551197289465 466 28159825759424 467 28780649568433 468 29413888913275 469 30059765998102 470 30718508089414 471 31390344529503 472 32075509848563 473 32774240726575 474 33486779163794 475 34213369378614 476 34954261048564 477 35709706143496 478 36479962226684 479 37265289233736 480 38065952834753 481 38882221146377 482 39714368167954 483 40562670425685 484 41427410471646 485 42308873471180 486 43207350766106 487 44123136391992 488 45056530718579 489 46007836896205 490 46977364562296 491 47965426228095 492 48972341052248 493 49998431154359 494 51044025469514 495 52109455987568 496 53195061676675 497 54301184660233 498 55428174210850 499 56576382850627 500 57746170429523 501 58937900148188 502 60151942708793 503 61388672272367 504 62648470683172 505 63931723346131 506 65238823539556 507 66570168211498 508 67926162368084 509 69307214801519 510 70713742555564 511 72146166569888 512 73604916237619 513 75090424965209 514 76603134809279 515 78143491964788 516 79711951482329 517 81308972669202 518 82935023902987 519 84590577944252 520 86276116832813 521 87992127125666 522 89739104877563 523 91517550787852 524 93327975281290 525 95170893562903 526 97046830785397 527 98956317025692 528 100899892540180 529 102878102646479 530 104891503083428 531 106940654796711 532 109026129389101 533 111148503824455 534 113308365969914 535 115506309200892 536 117742938052211 537 120018862723130 538 122334704822890 539 124691091790316 540 127088662735115 541 129528062754522 542 132009948888340 543 134534984331204 544 137103844485919 545 139717211086793 546 142375778353083 547 145080247004904 548 147831330534876 549 150629749115564 550 153476235973876 551 156371531205506 552 159316388253516 553 162311567611142 554 165357843423668 555 168455997078095 556 171606823911889 557 174811126705940 558 178069722502115 559 181383435979827 560 184753106401648 561 188179580872370 562 191663721396253 563 195206398035043 564 198808496078354 565 202470909080846 566 206194546166043 567 209980324941078 568 213829178916526 569 217742050316139 570 221719897614749 571 225763688222101 572 229874406159279 573 234053044615456 574 238300613745379 575 242618133116532 576 247006639629275 577 251467179833407 578 256000817992513 579 260608628268215 580 265291702910263 581 270051144326956 582 274888073403149 583 279803621434705 584 284798938596092 585 289875185737619 586 295033542984103 587 300275201413446 588 305601371788079 589 311013276092577 590 316512156420737 591 322099266370419 592 327775880066698 593 333543283433527 594 339402783355231 595 345355698801556 596 351403370150475 597 357547150165295 598 363788413459168 599 370128547343892 600 376568961437951 601 383111078363391 602 389756343521587 603 396506215636292 604 403362176676406 605 410325722265952 606 417398371756240 607 424581658477974 608 431877139987141 609 439286388157809 610 446810999581007 611 454452585518997 612 462212782459076 613 470093241904350 614 478095641108023 615 486221672698677 616 494473055573141 617 502851524378218 618 511358840564671 619 519996781699165 620 528767152705108 621 537671775003281 622 546712497917617 623 555891187666504 624 565209738935519 625 574670063693028 626 584274102956885 627 594023815432222 628 603921189448992 629 613968231445098 630 624166978077465 631 634519484522809 632 645027836789430 633 655694139834015 634 666520530050978 635 677509163228532 636 688662227217709 637 699981929699855 638 711470511063851 639 723130231982783 640 734963386474986 641 746972289314315 642 759159289277836 643 771526756360497 644 784077095238134 645 796812732284853 646 809736129226906 647 822849769987298 648 836156174532800 649 849657885516385 650 863357482347465 651 877257567629790 652 891360781429213 653 905669787532816 654 920187287917145 655 934916008797803 656 949858715328382 657 965018197438735 658 980397284738854 659 995998832171635 660 1011825735124108 661 1027880914863720 662 1044167333888613 663 1060687981144950 664 1077445887589153 665 1094444111213422 666 1111685752823024 667 1129173940837618 668 1146911847315450 669 1164902672528565 670 1183149661206806 671 1201656086914100 672 1220425268514797 673 1239460554318436 674 1258765338801756 675 1278343046519354 676 1298197149052869 677 1318331148716102 678 1338748595734632 679 1359453071711299 680 1380448207069792 681 1401737664278469 682 1423325155529403 683 1445214425749161 684 1467409270515950 685 1489913518823086 686 1512731051269293 687 1535865782572143 688 1559321680001565 689 1583102745673265 690 1607213035228877 691 1631656639873524 692 1656437705337879 693 1681560413657745 694 1707029002388021 695 1732847746154409 696 1759020976122067 697 1785553061283424 698 1812448428218369 699 1839711542115292 700 1867346926791371 701 1895359145478365 702 1923752821106597 703 1952532616817875 704 1981703256550196 705 2011269505275573 706 2041236189853946 707 2071608179027543 708 2102390404546936 709 2133587840884085 710 2165205526669242 711 2197248544119654 712 2229722040754321 713 2262631208571467 714 2295981306044889 715 2329777637010729 716 2364025572984285 717 2398730531753744 718 2433897999984396 719 2469533511552495 720 2505642670439980 721 2542231128768747 722 2579304610026479 723 2616868886798178 724 2654929804288470 725 2693493257785140 726 2732565216481825 727 2772151700632166 728 2812258805713682 729 2852892679270046 730 2894059545381485 731 2935765681229970 732 2978017441879399 733 3020821236522074 734 3064183553611200 735 3108110936785364 736 3152610010317057 737 3197687454751569 738 3243350032675642 739 3289604564027386 740 3336457952227839 741 3383917159159283 742 3431989231623396 743 3480681276024446 744 3530000485157420 745 3579954112552499 746 3630549499637719 747 3681794049741290 748 3733695255590799 749 3786260673011480 750 3839497948766269 751 3893414793904588 752 3948019011988058 753 4003318472087061 754 4059321137354051 755 4116035037706114 756 4173468298749426 757 4231629114102165 758 4290525774716774 759 4350166640839599 760 4410560171691217 761 4471714897102685 762 4533639447558435 763 4596342525461608 764 4659832935586383 765 4724119555969542 766 4789211368732406 767 4855117430638630 768 4921846904289481 769 4989409028300074 770 5057813148916816 771 5127068689808294 772 5197185184063328 773 5268172243638244 774 5340039591740201 775 5412797031881172 776 5486454480695571 777 5561021936597947 778 5636509512993279 779 5712927406580186 780 5790285930957815 781 5868595484524602 782 5947866584532793 783 6028109834578817 784 6109335959061977 785 6191555770310070 786 6274780203447118 787 6359020283102325 788 6444287158738111 789 6530592070939236 790 6617946387157647 791 6706361567625460 792 6795849201520726 793 6886420972452082 794 6978088695098725 795 7070864280262638 796 7164759771937379 797 7259787311973462 798 7355959177581056 799 7453287745554278 800 7551785530261372 801 7651465147424595 802 7752339352552455 803 7854421004320845 804 7957723103451597 805 8062258755640386 806 8168041210937238 807 8275083826216932 808 8383400105014103 809 8493003659583688 810 8603908251195950 811 8716127751730360 812 8829676184486468 813 8944567685307766 814 9060816543860965 815 9178437164337513 816 9297444107205727 817 9417852049433115 818 9539675826769433 819 9662930393485326 820 9787630865136925 821 9913792477870411 822 10041430631673700 823 10170560849187904 824 10301198819504421 825 10433360356479698 826 10567061443028241 827 10702318188990415 828 10839146875926037 829 10977563914475886 830 11117585889716453 831 11259229518010489 832 11402511692871428 833 11547449441354711 834 11694059970437621 835 11842360622889874 836 11992368924229676 837 12144102538069823 838 12297579313598412 839 12452817240452270 840 12609834496727201 841 12768649403316907 842 12929280472515902 843 13091746361819079 844 13256065923063613 845 13422258155743106 846 13590342256694452 847 13760337572862478 848 13932263651595162 849 14106140192854812 850 14281987100067926 851 14459824431836906 852 14639672453349652 853 14821551587527413 854 15005482467059836 855 15191485884983929 856 15379582847288671 857 15569794522981255 858 15762142297267488 859 15956647721038555 860 16153332564693253 861 16352218767041146 862 16553328489710702 863 16756684065525094 864 16962308053501511 865 17170223186632573 866 17380452427545237 867 17593018915682600 868 17807946023564245 869 18025257303426862 870 18244976544092527 871 18467127716998668 872 18691735033743028 873 18918822891498687 874 19148415931177463 875 19380538982288564 876 19615217121725917 877 19852475618000697 878 20092339990723795 879 20334835954206754 880 20579989477578902 881 20827826727817483 882 21078374130506201 883 21331658312222305 884 21587706162008037 885 21846544773110221 886 22108201505104028 887 22372703925046004 888 22640079870255888 889 22910357388810495 890 23183564803057661 891 23459730649445300 892 23738883742704601 893 24021053115077488 894 24306268081176037 895 24594558176533255 896 24885953223213066 897 25180483267679772 898 25478178647095637 899 25779069926572354 900 26083187966162213 901 26390563857416122 902 26701228991145355 903 27015214993280246 904 27332553793337142 905 27653277559643504 906 27977418768517297 907 28305010138780481 908 28636084701728134 909 28970675734925468 910 29308816832901268 911 29650541840294244 912 29995884923277013 913 30344880501973411 914 30697563322692971 915 31053968389613112 916 31414131037756212 917 31778086864004956 918 32145871800829528 919 32517522046555054 920 32893074139919233 921 33272564889586813 922 33656031449469716 923 34043511247556931 924 34435042062003566 925 34830661949194783 926 35230409320686805 927 35634322870498581 928 36042441652834274 929 36454805008673517 930 36871452644283204 931 37292424557022186 932 37717761114725767 933 38147502980719597 934 38581691194006297 935 39020367093559569 936 39463572399319636 937 39911349135683100 938 40363739713393395 939 40820786852219808 940 41282533663669836 941 41749023572930912 942 42220300402412773 943 42696408292864597 944 43177391787833905 945 43663295753953679 946 44154165466244564 947 44650046527645672 948 45150984955167048 949 45657027098576480 950 46168219727491676 951 46684609949216256 952 47206245296695811 953 47733173645579385 954 48265443303047777 955 48803102924009998 956 49346201600893577 957 49894788778970352 958 50448914347032842 959 51008628551925789 960 51573982090115845 961 52145026021337934 962 52721811861151012 963 53304391493692200 964 53892817265139959 965 54487141895655139 966 55087418573760230 967 55693700867373490 968 56306042819197373 969 56924498856839838 970 57549123889133246 971 58179973215422086 972 58817102622819861 973 59460568294568992 974 60110426908331801 975 60766735543615313 976 61429551781014824 977 62098933608785629 978 62774939523048163 979 63457628433409379 980 64147059764225981 981 64843293359269332 982 65546389583965215 983 66256409229184413 984 66973413614466757 985 67697464490839750 986 68428624145126482 987 69166955301784762 988 69912521228214484 989 70665385635702209 990 71425612785737305 991 72193267389961219 992 72968414717592394 993 73751120494373904 994 74541451011022615 995 75339473021260304 996 76145253851295109 997 76958861296835013 998 77780363733704738 999 78609830013833755 1000 79447329576921235