0 1 1 4 2 9 3 16 4 26 5 39 6 56 7 78 8 106 9 141 10 184 11 236 12 299 13 374 14 465 15 570 16 696 17 843 18 1014 19 1212 20 1441 21 1708 22 2014 23 2365 24 2769 25 3226 26 3749 27 4343 28 5016 29 5774 30 6630 31 7596 32 8676 33 9897 34 11259 35 12784 36 14482 37 16383 38 18502 39 20847 40 23458 41 26354 42 29562 43 33112 44 37041 45 41370 46 46144 47 51401 48 57204 49 63575 50 70566 51 78251 52 86675 53 95920 54 106029 55 117082 56 129173 57 142389 58 156810 59 172523 60 189664 61 208328 62 228646 63 250737 64 274753 65 300820 66 329155 67 359909 68 393246 69 429344 70 468446 71 510798 72 556614 73 606184 74 659730 75 717596 76 780071 77 847509 78 920260 79 998667 80 1083172 81 1174233 82 1272312 83 1377836 84 1491389 85 1613472 86 1744694 87 1885740 88 2037270 89 2199927 90 2374479 91 2561736 92 2762589 93 2977907 94 3208714 95 3456018 96 3720790 97 4004217 98 4307547 99 4632084 100 4979245 101 5350401 102 5747022 103 6170822 104 6623497 105 7106982 106 7622988 107 8173639 108 8761210 109 9387856 110 10055938 111 10768151 112 11527105 113 12335740 114 13196950 115 14113972 116 15090138 117 16129003 118 17234332 119 18410171 120 19660495 121 20989852 122 22402772 123 23904247 124 25499390 125 27193808 126 28993079 127 30903541 128 32931207 129 35082690 130 37365329 131 39786890 132 42354798 133 45077428 134 47963535 135 51022255 136 54263162 137 57696606 138 61333058 139 65183785 140 69260816 141 73576698 142 78144201 143 82977246 144 88090079 145 93497884 146 99216792 147 105263802 148 111656271 149 118412705 150 125552452 151 133096235 152 141064949 153 149481827 154 158369991 155 167754408 156 177661499 157 188118314 158 199152891 159 210795892 160 223078698 161 236034404 162 249698126 163 264105759 164 279295466 165 295307281 166 312183335 167 329967112 168 348704582 169 368444185 170 389236925 171 411134981 172 434193748 173 458471679 174 484029536 175 510929941 176 539240533 177 569030899 178 600374208 179 633346440 180 668027769 181 704501901 182 742855929 183 783180927 184 825573845 185 870134285 186 916966840 187 966180937 188 1017891767 189 1072218672 190 1129286826 191 1189226035 192 1252173518 193 1318272465 194 1387672129 195 1460528589 196 1537005439 197 1617271935 198 1701505964 199 1789893489 200 1882627715 201 1979912097 202 2081957992 203 2188986193 204 2301228033 205 2418922025 206 2542321337 207 2671687174 208 2807292980 209 2949424819 210 3098379298 211 3254467864 212 3418013826 213 3589357656 214 3768851937 215 3956862471 216 4153772961 217 4359984163 218 4575913017 219 4801994522 220 5038681476 221 5286447192 222 5545782268 223 5817203160 224 6101243192 225 6398460336 226 6709436245 227 7034774417 228 7375105388 229 7731085860 230 8103403833 231 8492770181 232 8899926556 233 9325647211 234 9770737891 235 10236034900 236 10722410704 237 11230775209 238 11762076087 239 12317296322 240 12897462384 241 13503641259 242 14136940403 243 14798520842 244 15489581626 245 16211375213 246 16965204213 247 17752419505 248 18574431019 249 19432707852 250 20328770665 251 21264209198 252 22240671461 253 23259869472 254 24323590656 255 25433684020 256 26592081291 257 27800787858 258 29061884432 259 30377537768 260 31749999100 261 33181611859 262 34674804066 263 36232109833 264 37856149706 265 39549650373 266 41315452266 267 43156501928 268 45075865102 269 47076714255 270 49162354987 271 51336221836 272 53601879991 273 55963029784 274 58423512537 275 60987321690 276 63658601332 277 66441655374 278 69340957186 279 72361143473 280 75507031593 281 78783625448 282 82196112094 283 85749882812 284 89450527460 285 93303849486 286 97315873535 287 101492855127 288 105841267266 289 110367839199 290 115079569000 291 119983689035 292 125087727955 293 130399474641 294 135927009876 295 141678730357 296 147663342100 297 153889850098 298 160367635116 299 167106387736 300 174116183809 301 181407458415 302 188991028931 303 196878115936 304 205080356889 305 213609805866 306 222478970808 307 231700797521 308 241288744596 309 251256707810 310 261619124786 311 272390956496 312 283587698989 313 295225407705 314 307320731835 315 319890921278 316 332953848940 317 346528007565 318 360632589622 319 375287457117 320 390513195313 321 406331130266 322 422763337166 323 439832711002 324 457562926954 325 475978526190 326 495104916862 327 514968416516 328 535596282265 329 557016722594 330 579258956778 331 602353223136 332 626330834541 333 651224231502 334 677066972918 335 703893802391 336 731740679024 337 760644848801 338 790644824710 339 821780509534 340 854093148539 341 887625466273 342 922421666766 343 958527499230 344 995990284090 345 1034858976826 346 1075184292561 347 1117018626262 348 1160416245546 349 1205433238031 350 1252127654669 351 1300559524797 352 1350790975055 353 1402886250851 354 1456911814449 355 1512936366448 356 1571030999724 357 1631269175201 358 1693726953799 359 1758482928923 360 1825618412156 361 1895217418314 362 1967366845968 363 2042156574495 364 2119679444243 365 2200031493422 366 2283312022147 367 2369623644731 368 2459072472318 369 2551768157502 370 2647824017661 371 2747357238168 372 2850488876580 373 2957344102795 374 3068052194159 375 3182746836382 376 3301566113362 377 3424652726614 378 3552154157005 379 3684222734645 380 3821015906770 381 3962696343069 382 4109432014431 383 4261396587693 384 4418769389105 385 4581735630989 386 4750486727414 387 4925220331876 388 5106140618970 389 5293458460205 390 5487391626195 391 5688165105765 392 5896011187405 393 6111169754397 394 6333888618067 395 6564423586690 396 6803038833889 397 7050007073314 398 7305609985894 399 7570138341785 400 7843892369681 401 8127182014480 402 8420327222466 403 8723658348111 404 9037516368065 405 9362253321477 406 9698232471441 407 10045828889406 408 10405429626035 409 10777434263222 410 11162255142573 411 11560317782906 412 11972061310112 413 12397938965239 414 12838418360180 415 13293982143411 416 13765128342114 417 14252370703092 418 14756239466709 419 15277281581518 420 15816061400724 421 16373161186772 422 16949181594186 423 17544742271124 424 18160482501993 425 18797061637042 426 19455159886511 427 20135478840893 428 20838742226318 429 21565696412400 430 22317111210789 431 23093780590875 432 23896523420702 433 24726184148369 434 25583633602678 435 26469769786009 436 27385518769486 437 28331835398019 438 29309704290227 439 30320140611359 440 31364190969798 441 32442934748086 442 33557484422909 443 34708987128390 444 35898625319248 445 37127618345708 446 38397222746706 447 39708733918629 448 41063487251493 449 42462859193420 450 43908268451421 451 45401177246817 452 46943092690092 453 48535568242676 454 50180204627268 455 51878651762541 456 53632609762366 457 55443830718447 458 57314120118166 459 59245338507990 460 61239402991808 461 63298288870284 462 65424031474998 463 67618727935952 464 69884538920231 465 72223690420597 466 74638475601777 467 77131257193354 468 79704469194327 469 82360618986682 470 85102289248089 471 87932140788726 472 90852914216860 473 93867432427084 474 96978602928221 475 100189420573858 476 103502969705234 477 106922427180294 478 110451064703780 479 114092251652769 480 117849457975855 481 121726256802081 482 125726328017997 483 129853460724070 484 134111556826600 485 138504633988117 486 143036828980957 487 147712400963979 488 152535735616215 489 157511348407492 490 162643887617153 491 167938139453698 492 173399030800034 493 179031633696388 494 184841169709288 495 190833013818309 496 197012699340658 497 203385921534628 498 209958542897628 499 216736598006385 500 223726297700915 501 230934034464755 502 238366387868284 503 246030129295717 504 253932227866248 505 262079855418032 506 270480392877783 507 279141435747990 508 288070800596675 509 297276530454409 510 306766902020842 511 316550431466995 512 326635881894813 513 337032269801443 514 347748872292888 515 358795234474731 516 370181176968103 517 381916803200813 518 394012507539941 519 406478983479907 520 419327231984645 521 432568569965838 522 446214639389494 523 460277415380790 524 474769216767680 525 489702714286264 526 505090941902981 527 520947305472596 528 537285593100381 529 554119986883091 530 571465072411645 531 589335851339463 532 607747751551151 533 626716639062297 534 646258830581267 535 666391106220662 536 687130721652606 537 708495420743916 538 730503450242716 539 753173572310345 540 776525079075845 541 800577807253018 542 825352153452137 543 850869088561376 544 877150173734906 545 904217576901470 546 932094089076382 547 960803141475165 548 990368821812127 549 1020815894025063 550 1052169815465580 551 1084456755406227 552 1117703615257465 553 1151938048374103 554 1187188479191264 555 1223484125928698 556 1260855021182204 557 1299332033148759 558 1338946889765262 559 1379732199347084 560 1421721477854832 561 1464949170368818 562 1509450676306313 563 1555262377877108 564 1602421663928481 565 1650966957087686 566 1700937742158736 567 1752374594020349 568 1805319207492635 569 1859814427537399 570 1915904279220840 571 1973633998575136 572 2033050066809429 573 2094200242418687 574 2157133595168017 575 2221900541066363 576 2288552878365021 577 2357143824367286 578 2427728053453456 579 2500361734213987 580 2575102570459175 581 2652009842262237 582 2731144446576016 583 2812568941372053 584 2896347586816349 585 2982546394101262 586 3071233168989217 587 3162477559812901 588 3256351106211747 589 3352927289210791 590 3452281581481706 591 3554491499934798 592 3659636660881184 593 3767798832094735 594 3879061992744444 595 3993512390275661 596 4111238597235142 597 4232331576303211 598 4356884740321332 599 4484994017633874 600 4616757914959008 601 4752277588294574 602 4891656909114807 603 5035002539009618 604 5182423997540657 605 5334033740894923 606 5489947233842200 607 5650283032497465 608 5815162861180690 609 5984711697986570 610 6159057854127404 611 6338333065334797 612 6522672577343892 613 6712215237860094 614 6907103591020480 615 7107483970163623 616 7313506597160701 617 7525325683674094 618 7743099532184630 619 7966990640948400 620 8197165815301912 621 8433796273591671 622 8677057766035075 623 8927130685628627 624 9184200191966385 625 9448456329889135 626 9720094158512399 627 9999313875719685 628 10286320952095518 629 10581326266135653 630 10884546239075137 631 11196202979932037 632 11516524428538715 633 11845744505952498 634 12184103267206760 635 12531847055057200 636 12889228661619436 637 13256507491719195 638 13633949729793527 639 14021828515300019 640 14420424118241625 641 14830024116568161 642 15250923585364195 643 15683425284868313 644 16127839853874052 645 16584486012980420 646 17053690762520694 647 17535789595928627 648 18031126716103998 649 18540055249670229 650 19062937476472797 651 19600145055019979 652 20152059263856201 653 20719071239415640 654 21301582222225868 655 21900003818260585 656 22514758252119805 657 23146278637332546 658 23795009244614625 659 24461405784349174 660 25145935693502453 661 25849078427906737 662 26571325762244961 663 27313182097557022 664 28075164777120460 665 28857804408141668 666 29661645194026954 667 30487245267320493 668 31335177044378139 669 32206027578856565 670 33100398920486157 671 34018908495459926 672 34962189476087126 673 35930891180391235 674 36925679472935823 675 37947237173521994 676 38996264468418720 677 40073479351942607 678 41179618062837545 679 42315435531197394 680 43481705844125204 681 44679222715145406 682 45908799970902029 683 47171272044424046 684 48467494482698483 685 49798344466910339 686 51164721346900290 687 52567547181094025 688 54007767295022484 689 55486350856044508 690 57004291455225748 691 58562607701608240 692 60162343847683611 693 61804570399786696 694 63490384775388170 695 65220911956039725 696 66997305151187484 697 68820746502281964 698 70692447780995859 699 72613651111875026 700 74585629710332266 701 76609688639185318 702 78687165592733785 703 80819431679641412 704 83007892236677569 705 85253987663030199 706 87559194274106154 707 89925025161157605 708 92353031098169077 709 94844801437657602 710 97401965061773405 711 100026191320064719 712 102719191023950253 713 105482717445409292 714 108318567337497426 715 111228581981297264 716 114214648263309663 717 117278699780145007 718 120422717955300995 719 123648733191386547 720 126958826053674710 721 130355128462035955 722 133839824944520875 723 137415153886285716 724 141083408828694429 725 144846939782297227 726 148708154596565160 727 152669520332247438 728 156733564677095118 729 160902877400381455 730 165180111835364405 731 169567986402985890 732 174069286159944417 733 178686864396242965 734 183423644238330740 735 188282620345005625 736 193266860601887050 737 198379507844913883 738 203623781662105878 739 209002980210671545 740 214520482091098343 741 220179748243538562 742 225984323917524673 743 231937840654170638 744 238044018344022062 745 244306667315014351 746 250729690467477057 747 257317085477755816 748 264072947018539988 749 271001469078371595 750 278106947272075023 751 285393781262678277 752 292866477214113882 753 300529650283053954 754 308388027211293412 755 316446448929852032 756 324709873258039021 757 333183377651201885 758 341872162012885297 759 350781551549664826 760 359916999742519211 761 369284091333805319 762 378888545412477108 763 388736218563891526 764 398833108088442163 765 409185355278764362 766 419799248806080717 767 430681228162642830 768 441837887156660957 769 453275977553855181 770 465002412743532435 771 477024271498409328 772 489348801854141550 773 501983425017656859 774 514935739426089266 775 528213524854143761 776 541824746617529183 777 555777559919131971 778 570080314224830111 779 584741557782754571 780 599770042243063648 781 615174727354289550 782 630964785803330331 783 647149608117164477 784 663738807742763953 785 680742226159346119 786 698169938198126893 787 716032257361275913 788 734339741400238490 789 753103197917018936 790 772333690114063714 791 792042542721911820 792 812241347992538808 793 832941971870080888 794 854156560268076399 795 875897545518752160 796 898177652983656326 797 921009907733544111 798 944407641454158501 799 968384499454046384 800 992954447899893510 801 1018131781119355037 802 1043931129149304159 803 1070367465388749542 804 1097456114494466268 805 1125212760376361771 806 1153653454412807557 807 1182794623832565584 808 1212653080303496849 809 1243246028727193230 810 1274591076134925102 811 1306706240921505664 812 1339609962164005559 813 1373321109189583004 814 1407858991405920465 815 1443243368291623874 816 1479494459576617765 817 1516632955743080427 818 1554680028689222694 819 1593657342623701022 820 1633587065282498123 821 1674491879280991566 822 1716394993794985737 823 1759320156485261418 824 1803291665654609874 825 1848334382695533648 826 1894473744847221816 827 1941735778142127386 828 1990147110728511437 829 2039734986456830353 830 2090527278719397278 831 2142552504700392609 832 2195839839798337082 833 2250419132492969939 834 2306320919440260889 835 2363576440984799322 836 2422217656945892848 837 2482277262763407977 838 2543788706027932822 839 2606786203359444314 840 2671304757617672051 841 2737380175534079880 842 2805049085709479881 843 2874348957032666057 844 2945318117442362595 845 3017995773143206154 846 3092422028255014284 847 3168637904832669525 848 3246685363372769263 849 3326607323759901492 850 3408447686592981698 851 3492251355163356891 852 3578064257665310884 853 3665933370077623838 854 3755906739459551250 855 3848033507779292757 856 3942363936239843500 857 4038949430124597619 858 4137842564227386742 859 4239097108791385454 860 4342768055999199193 861 4448911647063713632 862 4557585399940880401 863 4668848137579618069 864 4782760016778213524 865 4899382557706802727 866 5018778674057104550 867 5141012703774562646 868 5266150440606867715 869 5394259166178778320 870 5525407682800878143 871 5659666347014563012 872 5797107103873193096 873 5937803521933062463 874 6081830828935185140 875 6229265948313667635 876 6380187536533029530 877 6534676021149173157 878 6692813639765429216 879 6854684479739439240 880 7020374518727447866 881 7189971666210853277 882 7363565805804094213 883 7541248838584763224 884 7723114727158813383 885 7909259540879258041 886 8099781501921300427 887 8294781032275844855 888 8494360801940993269 889 8698625777928570441 890 8907683274436149067 891 9121643004124577843 892 9340617130318680683 893 9564720320534618000 894 9794069800966699534 895 10028785412176402163 896 10268989666137706790 897 10514807804166477602 898 10766367856316581741 899 11023800702109126522 900 11287240132250972252