1 1 2 2 3 3 4 5 5 6 6 11 7 12 8 20 9 26 10 37 11 45 12 71 13 84 14 117 15 152 16 203 17 253 18 342 19 421 20 556 21 694 22 884 23 1096 24 1409 25 1729 26 2168 27 2672 28 3327 29 4061 30 5039 31 6114 32 7514 33 9110 34 11098 35 13400 36 16275 37 19537 38 23575 39 28245 40 33929 41 40465 42 48424 43 57552 44 68569 45 81296 46 96449 47 113967 48 134842 49 158832 50 187251 51 220024 52 258590 53 303003 54 355164 55 415099 56 485202 57 565770 58 659573 59 767289 60 892492 61 1035873 62 1202010 63 1392323 64 1612068 65 1863421 66 2153120 67 2483910 68 2864297 69 3298284 70 3796063 71 4363236 72 5012745 73 5751614 74 6596018 75 7555829 76 8650443 77 9893049 78 11308073 79 12912196 80 14735924 81 16801190 82 19145127 83 21796493 84 24801571 85 28196421 86 32038532 87 36374706 88 41275075 89 46799316 90 53034666 91 60055833 92 67970662 93 76874167 94 86898113 95 98162578 96 110830350 97 125050705 98 141024375 99 158938948 100 179039597 101 201560573 102 226803696 103 255059033 104 286696944 105 322078270 106 361654773 107 405873994 108 455289605 109 510452193 110 572039069 111 640730207 112 717350150 113 802735907 114 897893996 115 1003850115 116 1121830448 117 1253093417 118 1399128126 119 1561475096 120 1741945255 121 1942416776 122 2165088735 123 2412253401 124 2686573463 125 2990840370 126 3328280720 127 3702284374 128 4116755808 129 4575811326 130 5084165467 131 5646808731 132 6269434450 133 6958078493 134 7719607408 135 8561320122 136 9491482968 137 10518908070 138 11653545744 139 12906015216 140 14288279304 141 15813127654 142 17494920768 143 19349043110 144 21392725567 145 23644442773 146 26124847694 147 28856112714 148 31862958865 149 35171963044 150 38812699921 151 42816981854 152 47220153328 153 52060265913 154 57379508877 155 63223347287 156 69642108310 157 76690046234 158 84427138582 159 92918080242 160 102234271381 161 112452776324 162 123658535481 163 135943246952 164 149407865785 165 164161417643 166 180323772418 167 198024435101 168 217405633442 169 238621039937 170 261839264127 171 287242518387 172 315030501607 173 345419071601 174 378644580122 175 414962504489 176 454652344241 177 498016238065 178 545384425575 179 597113928381 180 653594658326 181 715248118952 182 782534313711 183 855950509260 184 936038956695 185 1023385831843 186 1118629890874 187 1222461551735 188 1335632681867 189 1458955891781 190 1593315508102 191 1739667233651 192 1899050474030 193 2072588352022 194 2261501663185 195 2467109361144 196 2690844233805 197 2934254083747 198 3199019379108 199 3486955152096 200 3800030996209 201 4140373871382 202 4510290627441 203 4912272033803 204 5349018183946 205 5823443852604 206 6338707305678 207 6898217278835 208 7505665485798 209 8165035681304 210 8880640404817 211 9657132341901 212 10499546027217 213 11413311972414 214 12404303815822 215 13478855893993 216 14643816607482 217 15906569847081 218 17275095614808 219 18757996021179 220 20364563926496 221 22104814505680 222 23989563057424 223 26030462845212 224 28240093533955 225 30632006421684 226 33220824712300 227 36022297601787 228 39053414053548 229 42332466918763 230 45879182332568 231 49714795556355 232 53862197834603 233 58346026129549 234 63192829904611 235 68431176644158 236 74091841587923 237 80207931605732 238 86815100703921 239 93951695446178 240 101658999839769 241 109981405281747 242 118966689216884 243 128666213471640 244 139135240907843 245 150433166873107 246 162623879161635 247 175776027178262 248 189963431539009 249 205265396736111 250 221767176739289 251 239560338112591 252 258743289372989 253 279421701585586 254 301709110677586 255 325727404133082 256 351607505684563 257 379489938347744 258 409525602868923 259 441876427688206 260 476716254452288 261 514231587693808 262 554622601386414 263 598104003354188 264 644906179437911 265 695276188509164 266 749479063562939 267 807798956194907 268 870540615160519 269 938030702303947 270 1010619472767359 271 1088682285935157 272 1172621515223384 273 1262868281768814 274 1359884623938188 275 1464165485859001 276 1576241181746086 277 1696679674084760 278 1826089373209493 279 1965121745697935 280 2114474493170587 281 2274894537628849 282 2447181630416096 283 2632191765593773 284 2830841277386097 285 3044110740766418 286 3273049621375834 287 3518780731139883 288 3782505504287796 289 4065509082658954 290 4369166301954817 291 4694947492660619 292 5044425269222607 293 5419281144775597 294 5821313229514413 295 6252443767805301 296 6714727866705316 297 7210362079880942 298 7741694300236239 299 8311233532316906 300 8921661101931077 301 9575841774320320 302 10276836454467600 303 11027914830540916 304 11832569757714020 305 12694531630818798 306 13617784671191944 307 14606583255455631 308 15665470354104169 309 16799296074614624 310 18013238528697337 311 19312824882356129 312 20703954966024858 313 22192925157871027 314 23786455092318478 315 25491714746815913 316 27316354645055158 317 29268536566010166 318 31356967690704125 319 33590935401031638 320 35980345876880981 321 38535763514048470 322 41268454537522826 323 44190431636167236 324 47314503231495880 325 50654323996993556 326 54224450503379374 327 58040398377094984 328 62118705127417697 329 66476994794856682 330 71134048868778330 331 76109879376767504 332 81425808915874832 333 87104553255638543 334 93170311626492101 335 99648860044177704 336 106567653143301469 337 113955929573687431 338 121844826827773713 339 130267500229703053 340 139259252375874149 341 148857667426954962 342 159102756983159652 343 170037111591600050 344 181706065102524553 345 194157865542637829 346 207443860239839032 347 221618688478018441 348 236740489960060534 349 252871121945030544 350 270076393933427760 351 288426312320153268 352 307995344525323717 353 328862694566508004 354 351112600252201095 355 374834643477931686 356 400124084537457224 357 427082211410856189 358 455816715724824496 359 486442085816627964 360 519080029422774240 361 553859915864824317 362 590919251155727165 363 630404175298287096 364 672469996164156517 365 717281748613522996 366 765014794263464551 367 815855449922437998 368 870001661212002452 369 927663708705294953 370 989064964294794867 371 1054442684420514716 372 1124048859132646996 373 1198151102888821081 374 1277033607435947599 375 1360998141897265690 376 1450365121888724654 377 1545474731997801088 378 1646688125012573374 379 1754388681413297482 380 1868983354219089119 381 1990904081831030727 382 2120609295792547565 383 2258585505233237377 384 2405348986860234314 385 2561447561357038575 386 2727462487171165035 387 2904010451594348860 388 3091745692389866869 389 3291362228918047795 390 3503596238435468875 391 3729228555539506906 392 3969087333071030393 393 4224050841421805381 394 4495050447393941079 395 4783073748548059604 396 5089167907212312387 397 5414443159062675246 398 5760076543740963471 399 6127315831357587842 400 6517483695890826247 401 6931982108300499221 402 7372297004158566173 403 7840003197585295936 404 8336769600422157624 405 8864364717381022941 406 9424662480549125091 407 10019648393002435064 408 10651426049672710637 409 11322224004261318667 410 12034403055536088627 411 12790463920851885730 412 13593055375831632747 413 14444982827200396125 414 15349217403720827774 415 16308905531442760456 416 17327379084764511786 417 18408166078790187983 418 19555002001555180949 419 20771841751039648709 420 22062872283151025367 421 23432525935161066430 422 24885494539070139476 423 26426744289066046881 424 28061531486518645013 425 29795419126610454113 426 31634294459707495381 427 33584387491722653452 428 35652290567109949121 429 37844978999107118115 430 40169832902273252449 431 42634660192675995775 432 45247720923089079436 433 48017752919639948850 434 50953998900697525420 435 54066235045876212801 436 57364801210507963649 437 60860632755438492794 438 64565294203243179919 439 68491014693227415919 440 72650725463484714094 441 77058099335434824254 442 81727592447763463226 443 86674488219023058057 444 91914943806010379910 445 97466039041801358138 446 103345828142602082339 447 109573394172742012308 448 116168906580925814242 449 123153681803623313490 450 130550247274695635002 451 138382408844825408322 452 146675321978223385241 453 155455566739078605502 454 164751226966094724463 455 174591973658034786458 456 185009153002141442093 457 196035879080432072872 458 207707131722363502008 459 220059859552684178553 460 233133088742857899452 461 246968037530865213856 462 261608237061139104192 463 277099658627715677363 464 293490847919764997668 465 310833066373329164944 466 329180440280108021001 467 348590117780868399577 468 369122434450568369477 469 390841087629715864941 470 413813320270563209028 471 438110114483064993702 472 463806395616301396345 473 490981247094835052992 474 519718136918818234028 475 550105156086283411239 476 582235269926413843574 477 616206582646008447310 478 652122616165247944204 479 690092603594412252531 480 730231798522876809071 481 772661800527562185675 482 817510898176359780708 483 864914429995871624631 484 915015164792803439247 485 967963701868218518025 486 1023918892638213488370 487 1083048284278420084810 488 1145528587041862330783 489 1211546165954868071606 490 1281297558689166656604 491 1354990020412619123170 492 1432842097579008452946 493 1515084231568418577177 494 1601959394316312344821 495 1693723756964314739134 496 1790647393865091904291 497 1893015023109941883361 498 2001126786123786427799 499 2115299067647145757245 500 2235865358882256076332 501 2363177165290688578675 502 2497604962073909024678 503 2639539199010950219695 504 2789391357962625838642 505 2947595064924000909990 506 3114607260238990000425 507 3290909429089041532793 508 3477008896202881211751 509 3673440187155087694541 510 3880766460564767387377 511 4099581013845794128821 512 4330508867218878148565 513 4574208428951167421739 514 4831373246970299986523 515 5102733850167095889735 516 5389059685011485593051 517 5691161151181730594294 518 6009891742354739391842 519 6346150296284360049173 520 6700883360888130672764 521 7075087680941950693396 522 7469812812729765534273 523 7886163871770283694639 524 8325304421654158050841 525 8788459509690973299007 526 9276918858150780474751 527 9792040217437822749411 528 10335252890803375092962 529 10908061437640287228112 530 11512049565866673568121 531 12148884221219308136847 532 12820319884949981808931 533 13528203088604441734097 534 14274477158456062391627 535 15061187199221580469592 536 15890485330812655129211 537 16764636188795432587281 538 17686022703605401114491 539 18657152170342170917258 540 19680662625607160704802 541 20759329544478950936661 542 21896072875639612198532 543 23093964429145795725435 544 24356235636554981577349 545 25686285699442222320974 546 27087690147875109265220 547 28564209826579707455779 548 30119800332398887590893 549 31758621922643914014704 550 33485049920166752551053 551 35303685636810476605226 552 37219367843501308211465 553 39237184810902237025103 554 41362486951558738063868 555 43600900089944703540834 556 45958339394257982964879 557 48441023999110453071723 558 51055492356155972306060 559 53808618344809832531014 560 56707628183599154173838 561 59760118177604152628350 562 62974073346355452631953 563 66357886971281246192227 564 69920381111255201492578 565 73670828129330939818188 566 77618973283794753718055 567 81775058431006335576498 568 86149846898171010860704 569 90754649578328040335306 570 95601352311181035977965 571 100702444607340854603699 572 106071049785605694711763 573 111720956586649833585176 574 117666652339307621548110 575 123923357749191068245080 576 130507063393004522591034 577 137434567995280136189416 578 144723518578748308664878 579 152392452572728507989040 580 160460841979340632121672 581 168949139690326021756320 582 177878828063667020420489 583 187272469862008744147397 584 197153761672339642780696 585 207547589919035518074725 586 218480089600950325221972 587 229978705875731097584102 588 242072258634313993077834 589 254791010200913015342848 590 268166736314877666192132 591 282232800543025415422055 592 297024232293494365622640 593 312577808594287013013401 594 328932139823583713557443 595 346127759570949583000241 596 364207218834038484562133 597 383215184747386844233290 598 403198544067053365286887 599 424206511626825879279573 600 446290744010679586841518 601 469505458678148376373435 602 493907558810162617656277 603 519556764134934421602096 604 546515748026429893730362 605 574850281160093165377861 606 604629382045657349644253 607 635925474749153635478767 608 668814554153772370389770 609 703376359101713149756919 610 739694553799247835570747 611 777856917859978950134866 612 817955545404088277992880 613 860087053624480375245754 614 904352801276463544119100 615 950859117541153119774099 616 999717541761659898925830 617 1051045074545197311448883 618 1104964440776485914584307 619 1161604365082539552950582 620 1221099860344779345131958 621 1283592529849876655809736 622 1349230883730473292166003 623 1418170670343264434680441 624 1490575223295846715826318 625 1566615824831100476844975 626 1646472086346274672992713 627 1730332346822497168229823 628 1818394090013651463386502 629 1910864381243484815324132 630 2007960324738207328678032 631 2109909542423335817625794 632 2216950675197499336725317 633 2329333907699204360785004 634 2447321517672511273434021 635 2571188451042888219363184 636 2701222923910902338873839 637 2837727052679027290174944 638 2981017513630172759591413 639 3131426233286758228454311 640 3289301110989943501311945 641 3455006775151773761052449 642 3628925374751817051187007 643 3811457407666309594660601 644 4003022587545293978496400 645 4204060750973358600017848 646 4415032806786373762760700 647 4636421729440870552890647 648 4868733598479527355365534 649 5112498686165091182840244 650 5368272595512691815523956 651 5636637450984505324265857 652 5918203144280008219735563 653 6213608637694783798332275 654 6523523327702682508527892 655 6848648471462221448742957 656 7189718679143487943878927 657 7547503475024953698287384 658 7922808930519587369028769 659 8316479372350625716013729 660 8729399169323085609620914 661 9162494601206747265637861 662 9616735813489043922419421 663 10093138861835533725583601 664 10592767850356658099680440 665 11116737167869338704509230 666 11666213826622757586371726 667 12242419908059229091535228 668 12846635120483197445303377 669 13480199473625877253686449 670 14144516075418206840742577 671 14841054056413515058495216 672 15571351627651304252275102 673 16337019277897979865985907 674 17139743116577191634000449 675 17981288368864149493696447 676 18863503029824086845846575 677 19788321684655744279851353 678 20757769502537837381906497 679 21773966411778064053705870 680 22839131464435086280067100 681 23955587398808454589123818 682 25125765408698822466117725 683 26352210128590524624020856 684 27637584844455391038389607 685 28984676940154042835466065 686 30396403590000306319736057 687 31875817708362066610057750 688 33426114167807294937350355 689 35050636297644899733021169 690 36752882675395183646690399 691 38536514224102015556779355 692 40405361629137694214381088 693 42363433088568668738101559 694 44414922411947226347751835 695 46564217482855084701027668 696 48815909101384531399853808 697 51174800223251329028024753 698 53645915613161153238946075 699 56234511930612115884411955 700 58946088267316815461776641 701 61786397156045224375951909 702 64761456071769884703168209 703 67877559446675135494648070 704 71141291221757965096295908 705 74559537958496468549201222 706 78139502535320428812971106 707 81888718454441339588806233 708 85815064785957906267033276 709 89926781777057096643555295 710 94232487155597860458700624 711 98741193158357308970450529 712 103462324315803333851052601 713 108405736026347022814938945 714 113581733954739071536011612 715 119001094290469242062290451 716 124675084903875729947595751 717 130615487438981131690163247 718 136834620384067641630503662 719 143345363162439269276746611 720 150161181287974977632298150 721 157296152631648380625826239 722 164764994847518976967130395 723 172583094008420399878625578 724 180766534504087851544602741 725 189332130256349421585004010 726 198297457308725279041128604 727 207680887849837682544899388 728 217501625732973169260428733 729 227779743556389266428393364 730 238536221372133480353006824 731 249792987093602294466504198 732 261572958675499616081731499 733 273900088142541487775811940 734 286799407546962791997207504 735 300297076937816397262795796 736 314420434429063918956860117 737 329198048456661000119345720 738 344659772319172975676387529 739 360836801099953027429794412 740 377761731073598573613654610 741 395468621703215847836744502 742 413993060340085529391282685 743 433372229741482104283026844 744 453644978527872702031850346 745 474851894705256537903495187 746 497035382384322751564633160 747 520239741833047831995504325 748 544511253005750224001625588 749 569898262697006333526181310 750 596451275475747349508397643 751 624223048560724296232407484 752 653268690806004987462719821 753 683645765971557230171273026 754 715414400462055623160302368 755 748637395724007449274148763 756 783380345500032247571740241 757 819711758146703804408687957 758 857703184231811873043281159 759 897429349635143603345866730 760 938968294387100425054017498 761 982401517488434248255812319 762 1027814127965432134536831054 763 1075295002424633802212461625 764 1124936949383108572016867552 765 1176836880660927361630974914 766 1231095990135377397973478412 767 1287819940168002376627528393 768 1347119056029511378706195499 769 1409108528660139195984703533 770 1473908626118134921390451650 771 1541644914082683903283857975 772 1612448485793887949989506618 773 1686456201827237451416978416 774 1763810940117653769563988888 775 1844661856664268725769028407 776 1929164657366184961177136744 777 2017481881456936358297459949 778 2109783197025992915411272512 779 2206245709134632895867985736 780 2307054281055803793617927132 781 2412401869188200672567695363 782 2522489872218898053086559897 783 2637528495131242887874818364 784 2757737128680778913515103457 785 2883344744986255290009044151 786 3014590309910948210049200223 787 3151723212935876899066534016 788 3295003715256954834964504109 789 3444703416866711583497164875 790 3601105743414147947108929060 791 3764506453667309250633378239 792 3935214168438755709806825865 793 4113550921867759293127553701 794 4299852735991532325818561836 795 4494470219574288863441131912 796 4697769192204529453277629514 797 4910131334710515596245381677 798 5131954866988854040157566792 799 5363655254384020181986740270 800 5605665943805238419439400713 801 5858439130813653806547537624 802 6122446558965244716705876195 803 6398180352745346164228191280 804 6686153885487410769195353111 805 6986902683723277600540846124 806 7300985369473558790622199055 807 7628984642045965858581543465 808 7971508300975687013134265324 809 8329190311806080850485361294 810 8702691916479587285484614138 811 9092702790178256007887007508 812 9499942246530702200630810580 813 9925160493177579414482129362 814 10369139939771304768247166874 815 10832696560567302805362663720 816 11316681313854413701204049335 817 11821981620560401512106254628 818 12349522904466149361926693752 819 12900270196557725526163141781 820 13475229806151007626066900863 821 14075451061527048281264905885 822 14702028122930346762149832234 823 15356101870894225466764741254 824 16038861872980644530117346093 825 16751548432143050052575336581 826 17495454720053867730390609420 827 18271928998869488345380827628 828 19082376935049275426075632289 829 19928264008987136155483763576 830 20811118024369395658546503229 831 21732531721326368752317151896 832 22694165497612651702496601123 833 23697750242217389455623155785 834 24745090285986817504008802027 835 25838066474021199111986194741 836 26978639364803800794562065692 837 28168852561214048353765788155 838 29410836178788152918238206814 839 30706810456800848846122412377 840 32059089517969893564522463102 841 33470085282812452451689300355 842 34942311544928694033301722306 843 36478388213733881550932887603 844 38081045731426080036601349553 845 39753129671242521204322749975 846 41497605524344681408226770163 847 43317563682959603749876933302 848 45216224627714858085987389015 849 47196944327415275885681153119 850 49263219859844109181866650149 851 51418695262507122481710502731 852 53667167622599228227084238597 853 56012593415836245999769830633 854 58459095104184147597569658626 855 61010968002910378756747989275 856 63672687427802563557841796434 857 66448916133823702099159190443 858 69344512056927048402773103860 859 72364536371211733279436567314 860 75514261874090250554359375980 861 78799181712633567522443957416 862 82225018464788470224545417443 863 85797733589696062218029392629 864 89523537261911017955956418535 865 93408898604898291716831839267 866 97460556339799769791849834045 867 101685529866086613640233088553 868 106091130791377457032614964972 869 110684974928375670018680547330 870 115474994777595742341591923953 871 120469452515275589077491832182 872 125676953506644934284345037035 873 131106460365504591614353282382 874 136767307581905730630670658835 875 142669216740565332017851912462 876 148822312353553963578100194031 877 155237138331706462987411618759 878 161924675120176807763604281170 879 168896357524545511495955623246 880 176164093254934844598451536264 881 183740282216652511428993490944 882 191637836577013560151172332827 883 199870201639140016798824013128 884 208451377554755439476899045669 885 217395941909232260650368304127 886 226719073213462912557637377870 887 236436575338464440082969871798 888 246564902930042242525040219347 889 257121187842282955399310803568 890 268123266630173182805662146009 891 279589709143199027700323859875 892 291539848263427388496656837102 893 303993810833250929215518266370 894 316972549819753185237930705024 895 330497877764463417571840683086 896 344592501569183831525748100245 897 359280058670527374510671973461 898 374585154657866448020190709411 899 390533402391501932590689380765 900 407151462680084642686812053482 901 424467086578595713473336156302 902 442509159370588090634734647440 903 461307746300843759211588711295 904 480894140127183258745781316788 905 501300910562808305678185533579 906 522561955683340796279818611798 907 544712555375572317805778552154 908 567789426907936671729290603981 909 591830782705791240685257973105 910 616876390417823878108771962521 911 642967635363214898530600428325 912 670147585452664863655730192789 913 698461058679969722238102200447 914 727954693284575392728586447257 915 758677020689392488442687685938 916 790678541322192418970002647326 917 824011803433053739975009084982 918 858731485024680302319621236012 919 894894479016882304089977313719 920 932559981771199983406647495482 921 971789585106465769452356898592 922 1012647371941150902175160987979 923 1055200015703531605580780002029 924 1099516883656149179826271165630 925 1145670144286628907343021757881 926 1193734878922780633415230418267 927 1243789197735926468134666966494 928 1295914360302709526321340074902 929 1350194900902125165776960478070 930 1406718758731309364144294525204 931 1465577413230606746239009394952 932 1526866024715755433351899614214 933 1590683580522552108158739444832 934 1657133046877236350410879584620 935 1726321526713938743299588280474 936 1798360423669016391674081298070 937 1873365612490828091843755519201 938 1951457616112629666389327848041 939 2032761789645668945687862129734 940 2117408511559386344884596631881 941 2205533382325747066881190648422 942 2297277430815308342147630591348 943 2392787328743520842579642466878 944 2492215613477148349286976157236 945 2595720919522419721761768742452 946 2703468219028780587770222467801 947 2815629071654739344260071498536 948 2932381884155489254512411216923 949 3053912180065580449040239288049 950 3180412879864106909991189862354 951 3312084592024503069550445533181 952 3449135915366315472843539784611 953 3591783753142060111432368990918 954 3740253639308707469530816722154 955 3894780077450281955974406307457 956 4055606892835741524212610031925 957 4222987598114537476987271171962 958 4397185773171274799504420629595 959 4578475459680513884725682343890 960 4767141570923216522305248589209 961 4963480317447449790435008896957 962 5167799649177973025918100069168 963 5380419714602045668687181851725 964 5601673337682470673805024068265 965 5831906513173322507795035223851 966 6071478921039275381424955725709 967 6320764460705732091902109027093 968 6580151805894343767568321348817 969 6850044980826784107815185528559 970 7130863958609098297023268789198 971 7423045282639357010826932613301 972 7727042711913023114988671447553 973 8043327891133145115630877642028 974 8372391046566554443819349742177 975 8714741708622417324122164399380 976 9070909462166118226001595598087 977 9441444725619276322094891707146 978 9826919559936076249760634617798 979 10227928508586766676923075118985 980 10645089469721518026412536215430 981 11079044601731562163185202637028 982 11530461263470052009149679915982 983 12000032990442096704117365886593 984 12488480508322355775194466480108 985 12996552785209123202990701737826 986 13525028124076425387595656431331 987 14074715296939995593638725508551 988 14646454722309516878239285012905 989 15241119687557935706642518462863 990 15859617617899405015289002470498 991 16502891393730198253590417027895 992 17171920718152231650040115138320 993 17867723536566310181468121614591 994 18591357510292382360453522017335 995 19343921546246609068322350820585 996 20126557384780454349074591126822 997 20940451247864939705343218342525 998 21786835549884224427296549363387 999 22666990673386420285621887818926 1000 23582246812226601455525100715662