1 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 6 10 8 11 10 12 12 13 15 14 18 15 22 16 27 17 32 18 38 19 46 20 54 21 64 22 76 23 89 24 105 25 123 26 143 27 167 28 194 29 225 30 260 31 301 32 346 33 398 34 458 35 524 36 600 37 686 38 782 39 891 40 1014 41 1151 42 1306 43 1480 44 1674 45 1892 46 2137 47 2409 48 2713 49 3053 50 3431 51 3852 52 4322 53 4842 54 5421 55 6064 56 6776 57 7566 58 8441 59 9408 60 10478 61 11662 62 12967 63 14408 64 15999 65 17750 66 19680 67 21806 68 24142 69 26713 70 29540 71 32641 72 36046 73 39785 74 43880 75 48371 76 53292 77 58676 78 64569 79 71018 80 78064 81 85765 82 94179 83 103360 84 113382 85 124316 86 136232 87 149221 88 163374 89 178780 90 195552 91 213804 92 233650 93 255229 94 278683 95 304156 96 331824 97 361860 98 394449 99 429804 100 468146 101 509702 102 554738 103 603528 104 656355 105 713548 106 775446 107 842402 108 914820 109 993120 110 1077740 111 1169178 112 1267950 113 1374600 114 1489738 115 1614002 116 1748062 117 1892662 118 2048588 119 2216668 120 2397810 121 2592981 122 2803190 123 3029555 124 3273252 125 3535524 126 3817732 127 4121311 128 4447781 129 4798800 130 5176120 131 5581593 132 6017234 133 6485176 134 6987676 135 7527178 136 8106276 137 8727708 138 9394443 139 10109623 140 10876568 141 11698873 142 12580343 143 13524998 144 14537186 145 15621498 146 16782805 147 18026341 148 19357658 149 20782630 150 22307565 151 23939153 152 25684470 153 27551112 154 29547124 155 31681022 156 33961932 157 36399520 158 39004018 159 41786378 160 44758194 161 47931748 162 51320157 163 54937311 164 58797926 165 62917704 166 67313262 167 72002208 168 77003300 169 82336408 170 88022556 171 94084148 172 100544888 173 107429866 174 114765791 175 122580916 176 130905148 177 139770280 178 149209952 179 159259759 180 169957516 181 181343222 182 193459190 183 206350342 184 220064189 185 234650968 186 250163981 187 266659588 188 284197380 189 302840528 190 322655824 191 343713850 192 366089411 193 389861553 194 415113814 195 441934658 196 470417550 197 500661233 198 532770224 199 566854926 200 603031927 201 641424586 202 682163162 203 725385188 204 771236106 205 819869454 206 871447298 207 926140950 208 984131205 209 1045608844 210 1110775452 211 1179843724 212 1253038016 213 1330595321 214 1412765590 215 1499812448 216 1592014215 217 1689664384 218 1793072400 219 1902564837 220 2018485980 221 2141198728 222 2271085932 223 2408551084 224 2554019390 225 2707939266 226 2870783186 227 3043048904 228 3225261176 229 3417972756 230 3621765832 231 3837253956 232 4065083237 233 4305934031 234 4560523118 235 4829605094 236 5113974372 237 5414467586 238 5731965344 239 6067394425 240 6421730612 241 6796000682 242 7191284977 243 7608720632 244 8049503900 245 8514893138 246 9006212445 247 9524854418 248 10072283597 249 10650040596 250 11259745320 251 11903100952 252 12581898628 253 13298021242 254 14053447977 255 14850259660 256 15690643202 257 16576896803 258 17511436032 259 18496799028 260 19535652418 261 20630798346 262 21785180379 263 23001890446 264 24284176730 265 25635450572 266 27059294428 267 28559470844 268 30139930486 269 31804821209 270 33558498332 271 35405533896 272 37350727062 273 39399115824 274 41555987692 275 43826891590 276 46217651244 277 48734377421 278 51383481621 279 54171691306 280 57106064004 281 60194002936 282 63443274409 283 66862023982 284 70458794440 285 74242545460 286 78222672332 287 82409026372 288 86811937408 289 91442235219 290 96311272872 291 101430952336 292 106813748994 293 112472738384 294 118421625291 295 124674771848 296 131247228042 297 138154764818 298 145413906246 299 153041964343 300 161057076664 301 169478243136 302 178325365751 303 187619291342 304 197381853594 305 207635918364 306 218405432204 307 229715470464 308 241592288768 309 254063378300 310 267157520548 311 280904846005 312 295336896915 313 310486689736 314 326388781932 315 343079343160 316 360596226532 317 378979044510 318 398269249778 319 418510216330 320 439747325786 321 462028059130 322 485402089026 323 509921377856 324 535640281786 325 562615655797 326 590906965021 327 620576402656 328 651689009491 329 684312800128 330 718518896828 331 754381665083 332 791978857026 333 831391762940 334 872705365268 335 916008501216 336 961394034374 337 1008959029492 338 1058804936752 339 1111037786148 340 1165768385664 341 1223112530102 342 1283191221012 343 1346130891440 344 1412063642344 345 1481127491494 346 1553466628042 347 1629231680160 348 1708579996612 349 1791675935001 350 1878691164534 351 1969804984477 352 2065204650238 353 2165085716077 354 2269652394684 355 2379117926382 356 2493704966348 357 2613645990932 358 2739183715169 359 2870571530318 360 3008073962764 361 3151967145833 362 3302539314112 363 3460091321469 364 3624937174102 365 3797404588642 366 3977835576762 367 4166587047064 368 4364031435107 369 4570557362710 370 4786570317420 371 5012493363344 372 5248767884542 373 5495854351626 374 5754233123500 375 6024405285116 376 6306893512345 377 6602242975411 378 6911022283238 379 7233824458136 380 7571267954004 381 7923997719975 382 8292686298724 383 8678034973508 384 9080774965599 385 9501668671592 386 9941510954889 387 10401130493464 388 10881391173054 389 11383193540792 390 11907476321596 391 12455217986336 392 13027438387201 393 13625200463385 394 14249612005373 395 14901827494292 396 15583050019564 397 16294533263255 398 17037583567896 399 17813562092096 400 18623887041021 401 19470035990790 402 20353548310072 403 21276027666943 404 22239144640208 405 23244639439258 406 24294324720314 407 25390088518960 408 26533897304176 409 27727799140761 410 28973926981696 411 30274502095940 412 31631837618462 413 33048342245256 414 34526524079414 415 36068994614708 416 37678472881138 417 39357789758807 418 41109892446664 419 42937849111576 420 44844853725552 421 46834231076608 422 48909441981336 423 51074088706530 424 53331920586682 425 55686839865624 426 58142907771813 427 60704350813192 428 63375567322128 429 66161134260682 430 69065814272096 431 72094563011376 432 75252536765639 433 78545100350838 434 81977835319234 435 85556548489966 436 89287280789168 437 93176316436478 438 97230192491307 439 101455708745911 440 105859938004368 441 110450236762238 442 115234256274134 443 120219954051697 444 125415605807042 445 130829817831008 446 136471539849716 447 142350078378110 448 148475110558816 449 154856698534062 450 161505304370586 451 168431805526990 452 175647510914446 453 183164177572745 454 190994027952482 455 199149767857348 456 207644605071310 457 216492268662276 458 225707029020612 459 235303718659172 460 245297753768646 461 255705156589977 462 266542578634044 463 277827324743972 464 289577378065923 465 301811425961970 466 314548886862979 467 327809938130918 468 341615544969628 469 355987490381900 470 370948406250100 471 386521805581000 472 402732115917080 473 419604713996336 474 437165961705742 475 455443243333978 476 474465004211148 477 494260790786180 478 514861292150435 479 536298383102168 480 558605168807850 481 581816031073146 482 605966676324916 483 631094185367104 484 657237064926598 485 684435301099572 486 712730414767256 487 742165519002091 488 772785378583702 489 804636471701327 490 837767053868272 491 872227224179135 492 908068993991992 493 945346358070600 494 984115368324562 495 1024434210241216 496 1066363282049973 497 1109965276768824 498 1155305267237030 499 1202450794181789 500 1251471957482372 501 1302441510745480 502 1355434959249230 503 1410530661432746 504 1467809934057120 505 1527357161105092 506 1589259906611820 507 1653609031564788 508 1720498814952768 509 1790027079171525 510 1862295319939252 511 1937408840814012 512 2015476892539533 513 2096612817387106 514 2180934198601759 515 2268563015196028 516 2359625802280032 517 2454253817048318 518 2552583210691228 519 2654755206436874 520 2760916283862706 521 2871218369767820 522 2985819035832738 523 3104881703226792 524 3228575854478020 525 3357077252857336 526 3490568169458102 527 3629237618314428 528 3773281599835912 529 3922903352764145 530 4078313615024536 531 4239730893780848 532 4407381744923804 533 4581501062401293 534 4762332377728496 535 4950128169940604 536 5145150186430282 537 5347669775045671 538 5557968227741505 539 5776337136269098 540 6003078760316082 541 6238506408427909 542 6482944832238952 543 6736730634467538 544 7000212691046786 545 7273752587967136 546 7557725073332766 547 7852518525046715 548 8158535434755072 549 8476192908602460 550 8805923185264028 551 9148174171941582 552 9503409998933121 553 9872111593294840 554 10254777272347473 555 10651923357698144 556 11064084810356780 557 11491815887768212 558 11935690823501366 559 12396304530237856 560 12874273326961308 561 13370235691159732 562 13884853036760782 563 14418810518781156 564 14972817865587862 565 15547610239570316 566 16143949127297000 567 16762623260145060 568 17404449566290401 569 18070274155233598 570 18760973335948568 571 19477454669640524 572 20220658058398038 573 20991556870936854 574 21791159106528422 575 22620508598520515 576 23480686258766266 577 24372811364174841 578 25298042886923367 579 26257580869777717 580 27252667847866542 581 28284590318594932 582 29354680261287190 583 30464316708051452 584 31614927367706333 585 32807990304523932 586 34045035673435164 587 35327647513715937 588 36657465603081128 589 38036187374006710 590 39465569894490440 591 40947431915368349 592 42483655986200576 593 44076190642145042 594 45727052664146624 595 47438329414665968 596 49212181251596244 597 51050844022924730 598 52956631644596663 599 54931938764478152 600 56979243515230315 601 59101110358805049 602 61300193025733920 603 63579237552299684 604 65941085418581064 605 68388676790840754 606 70925053871653974 607 73553364361069132 608 76276865032606812 609 79098925427820512 610 82023031673052736 611 85052790422550163 612 88191932932027108 613 91444319266680848 614 94813942648215204 615 98304933945364410 616 101921566312323292 617 105668259980073418 618 109549587205535250 619 113570277383396304 620 117735222326077446 621 122049481717248527 622 126518288744227931 623 131147055915248488 624 135941381067524379 625 140907053571988001 626 146050060741244724 627 151376594447257604 628 156893057955212836 629 162606072980737060 630 168522486977603368 631 174649380663024244 632 180994075788372658 633 187564143163164612 634 194367410940098298 635 201411973169734322 636 208706198633405076 637 216258739962915123 638 224078543056430708 639 232174856799968722 640 240557243103891032 641 249235587264686844 642 258220108662358058 643 267521371803733930 644 277150297722966898 645 287118175750511744 646 297436675661924524 647 308117860218790421 648 319174198114164529 649 330618577334963384 650 342464318954777209 651 354725191370664452 652 367415424997578452 653 380549727435154755 654 394143299121720080 655 408211849490485382 656 422771613644040225 657 437839369563417546 658 453432455868137274 659 469568790144854904 660 486266887862427476 661 503545881891386366 662 521425542647088977 663 539926298876052116 664 559069259105179092 665 578876233774956776 666 599369758077966848 667 620573115524310585 668 642510362256989516 669 665206352140601228 670 688686762647010164 671 712978121563183676 672 738107834546751242 673 764104213555202271 674 790996506176251880 675 818814925887342405 676 847590683272646924 677 877356018227673866 678 908144233182054778 679 939989727371574428 680 972928032192333204 681 1006995847670488772 682 1042231080081569648 683 1078672880755299543 684 1116361686102507056 685 1155339258901313896 686 1195648730881870396 687 1237334646649622180 688 1280443008987800376 689 1325021325582031422 690 1371118657210776164 691 1418785667446103644 692 1468074673911658828 693 1519039701145594984 694 1571736535117138808 695 1626222779447967962 696 1682557913390605589 697 1740803351617037104 698 1801022505873449037 699 1863280848558115699 700 1927645978280608062 701 1994187687463350184 702 2062978032047827895 703 2134091403369026180 704 2207604602264721394 705 2283596915487681674 706 2362150194490244977 707 2443348936654009680 708 2527280369038953644 709 2614034534727880692 710 2703704381845583644 711 2796385855333870820 712 2892177991565360852 713 2991183015882690725 714 3093506443151722744 715 3199257181419299600 716 3308547638770092344 717 3421493833479238297 718 3538215507559644334 719 3658836243807112224 720 3783483586448816208 721 3912289165503089468 722 4045388824963043113 723 4182922754919191214 724 4325035627738908778 725 4471876738425473627 726 4623600149282347707 727 4780364839011294474 728 4942334856378210536 729 5109679478583745761 730 5282573374479043376 731 5461196772772587312 732 5645735635377673136 733 5836381836053606728 734 6033333344499807298 735 6236794416065874774 736 6446975787244636234 737 6664094877121701656 738 6888375994959340022 739 7120050554096828043 740 7359357292356431604 741 7606542499148879674 742 7861860249476970116 743 8125572645043469392 744 8397950062674642377 745 8679271410275980668 746 8969824390544813164 747 9269905772670129064 748 9579821672255718488 749 9899887839711441600 750 10230429957363643520 751 10571783945542063256 752 10924296277909949873 753 11288324306310910876 754 11664236595412944419 755 12052413267440201518 756 12453246357290475930 757 12867140178344014538 758 13294511699280107924 759 13735790932226079326 760 14191421332571604596 761 14661860210793007789 762 15147579156641094667 763 15649064476055192800 764 16166817641178679802 765 16701355753861044280 766 17253212023041469420 767 17822936256422542576 768 18411095366853341116 769 19018273893852047850 770 19645074540712893968 771 20292118727653889143 772 20960047161473690894 773 21649520422201770940 774 22361219567238763592 775 23095846753496874455 776 23854125878067280360 777 24636803237955332596 778 25444648209438576876 779 26278453947620986866 780 27139038106771966202 781 28027243582054165206 782 28943939273264000826 783 29890020871225296099 784 30866411667493364043 785 31874063388048269512 786 32913957051674025369 787 33987103853738919212 788 35094546076115284378 789 36237358023996653766 790 37416646990390367744 791 38633554249088629628 792 39889256076942424868 793 41184964806284624474 794 42521929908375533619 795 43901439108767460724 796 45324819535508759218 797 46793438901136881710 798 48308706719435374860 799 49872075557955754828 800 51485042327336608610 801 53149149608479915776 802 54865987018672899320 803 56637192617777645794 804 58464454355640814590 805 60349511561906591276 806 62294156479452679749 807 64300235842701869853 808 66369652502095264846 809 68504367096052835038 810 70706399771782584264 811 72977831956336118025 812 75320808179351149722 813 77737537948960248584 814 80230297682384792884 815 82801432692779331306 816 85453359233933653550 817 88188566604483039216 818 91009619313327091933 819 93919159308003336296 820 96919908267808684466 821 100014669963515837110 822 103206332685581436076 823 106497871742793776665 824 109892352033366209764 825 113392930690536415698 826 117002859804787140864 827 120725489224867013384 828 124564269439848779928 829 128522754544522480710 830 132604605290489219204 831 136813592225384944441 832 141153598922729023625 833 145628625304966033576 834 150242791062338433783 835 155000339170298741464 836 159905639508249463660 837 164963192582474159035 838 170177633356200090172 839 175553735189818943920 840 181096413894373683108 841 186810731901503225128 842 192701902553129639346 843 198775294514261086604 844 205036436312374469372 845 211491021006942305720 846 218144910992764367678 847 225004142940863099644 848 232074932880810506914 849 239363681428458371730 850 246876979163150476782 851 254621612158612991614 852 262604567671832139250 853 270833039994344138794 854 279314436470489381388 855 288056383687305300920 856 297066733840858051906 857 306353571283950352583 858 315925219260275646704 859 325790246830224996993 860 335957475993701432160 861 346435989015440471320 862 357235135958483195660 863 368364542431608600563 864 379834117556687984160 865 391654062162084181620 866 403834877208391772616 867 416387372452983455163 868 429322675360001243118 869 442652240262618439444 870 456387857784581541956 871 470541664528229165826 872 485126153036387501664 873 500154182035740287280 874 515638986969474858974 875 531594190827224621288 876 548033815280543245072 877 564972292132366403130 878 582424475089153291381 879 600405651864632979096 880 618931556624319449892 881 638018382780214670416 882 657682796145371137510 883 677941948458243902332 884 698813491287038194498 885 720315590324531659944 886 742466940084130202767 887 765286779008214742965 888 788794905000131634158 889 813011691391482545544 890 837958103356691950552 891 863655714787150137378 892 890126725637557647896 893 917393979757445345406 894 945480983221190345226 895 974411923170203012738 896 1004211687181336506906 897 1034905883175944785347 898 1066520859884399068918 899 1099083727881279271937 900 1132622381206862000576 901 1167165519590942260744 902 1202742671295465146036 903 1239384216592882012896 904 1277121411897595118540 905 1315986414568329096168 906 1356012308399741579269 907 1397233129822071509162 908 1439683894828135994998 909 1483400626647499209348 910 1528420384188162593516 911 1574781291266679016194 912 1622522566648147831134 913 1671684554918116328620 914 1722308758209010714494 915 1774437868804319045108 916 1828115802644363272856 917 1883387733758142935584 918 1940300129646380918222 919 1998900787641566242576 920 2059238872271485767814 921 2121364953653436988456 922 2185331046947032441069 923 2251190652894258726011 924 2318998799476210037816 925 2388812084716692458386 926 2460688720663707729868 927 2534688578580643133600 928 2610873235379833135374 929 2689306021332035512303 930 2770052069086248555912 931 2853178364035202444246 932 2938753796062804755326 933 3026849212710774995069 934 3117537473802682408318 935 3210893507564623442456 936 3306994368282806783318 937 3405919295539371915102 938 3507749775068870340604 939 3612569601278952854264 940 3720464941479949077294 941 3831524401869216108164 942 3945839095317336563260 943 4063502711004480567335 944 4184611585956531147572 945 4309264778531872116660 946 4437564143911070393744 947 4569614411643071255045 948 4705523265302928339664 949 4845401424317529428315 950 4989362728017275089506 951 5137524221973182476870 952 5290006246680440305964 953 5446932528651055304262 954 5608430273979866037580 955 5774630264449877433872 956 5945666956244610789556 957 6121678581336929610086 958 6302807251625612253474 959 6489199065892820938736 960 6681004219657522323278 961 6878377118001868991450 962 7081476491449577607064 963 7290465514977396033180 964 7505511930242860581546 965 7726788171113730194074 966 7954471492586703558154 967 8188744103185300711859 968 8429793300929147925721 969 8677811612969299051560 970 8932996938986681744108 971 9195552698453298987970 972 9465687981858399593440 973 9743617706004480041056 974 10029562773480721202617 975 10323750236424250027361 976 10626413464682473589010 977 10937792318492688334966 978 11258133325798173154863 979 11587689864323056688672 980 11926722348531435705518 981 12275498421599463141664 982 12634293152532448066837 983 13003389238562444963086 984 13383077212965305572027 985 13773655658439750802930 986 14175431426194723036506 987 14588719860895048760308 988 15013845031619306226124 989 15451139968987783963272 990 15900946908622480298072 991 16363617541105260872632 992 16839513268604592644648 993 17329005468345654515451 994 17832475763103116776218 995 18350316298900517204888 996 18882930030104884885190 997 19430731012110105053162 998 19994144701807513472315 999 20573608266047299944966 1000 21169570898299519574892