0 0 1 0 2 1 3 1 4 2 5 2 6 5 7 5 8 8 9 11 10 16 11 19 12 28 13 35 14 48 15 60 16 79 17 99 18 131 19 161 20 205 21 256 22 324 23 397 24 498 25 609 26 755 27 921 28 1131 29 1372 30 1677 31 2022 32 2452 33 2952 34 3561 35 4260 36 5116 37 6102 38 7291 39 8667 40 10309 41 12210 42 14477 43 17087 44 20177 45 23752 46 27957 47 32804 48 38496 49 45049 50 52704 51 61518 52 71773 53 83562 54 97251 55 112947 56 131113 57 151948 58 175980 59 203481 60 235150 61 271339 62 312901 63 360344 64 414701 65 476656 66 547525 67 628166 68 720215 69 824861 70 944071 71 1079385 72 1233309 73 1407791 74 1605920 75 1830251 76 2084571 77 2372158 78 2697745 79 3065432 80 3481084 81 3949996 82 4479325 83 5075734 84 5748164 85 6504938 86 7357060 87 8315054 88 9392405 89 10602284 90 11961368 91 13485979 92 15196636 93 17113765 94 19262434 95 21667961 96 24361249 97 27373540 98 30742650 99 34507289 100 38713627 101 43409386 102 48651120 103 54497353 104 61017142 105 68282519 106 76377500 107 85390307 108 95423463 109 106584731 110 118998757 111 132797309 112 148131663 113 165162445 114 184073405 115 205059802 116 228344370 117 254164664 118 282790042 119 314508707 120 349646674 121 388552939 122 431621198 123 479273981 124 531986034 125 590267920 126 654692037 127 725874180 128 804503390 129 891322220 130 987158835 131 1092906986 132 1209561883 133 1338197705 134 1480008516 135 1636284585 136 1808456861 137 1998072937 138 2206846635 139 2436631628 140 2689478020 141 2967604759 142 3273461210 143 3609699930 144 3979245680 145 4385265688 146 4831248140 147 5320971970 148 5858593007 149 6448614819 150 7095985149 151 7806065198 152 8584739417 153 9438385246 154 10373994050 155 11399143888 156 12522135513 157 13751964733 158 15098476980 159 16572342753 160 18185228976 161 19949780285 162 21879811794 163 23990293319 164 26297568921 165 28819347869 166 31574948961 167 34585302907 168 37873228201 169 41463441527 170 45382871636 171 49660683979 172 54328631909 173 59421101065 174 64975506511 175 71032354829 176 77635696795 177 84833214822 178 92676731177 179 101222329918 180 110530933097 181 120668455537 182 131706461550 183 143722364581 184 156800167694 185 171030719845 186 186512556612 187 203352214991 188 221665192892 189 241576338594 190 263220935278 191 286745183699 192 312307435957 193 340078776389 194 370244429992 195 403004466256 196 438575395865 197 477191023126 198 519104264140 199 564588161507 200 613937961361 201 667472324792 202 725535686461 203 788499702265 204 856765938538 205 930767579416 206 1010972499314 207 1097885282473 208 1192050718050 209 1294056188521 210 1404535656376 211 1524172464477 212 1653703892208 213 1793924442869 214 1945691031406 215 2109926844566 216 2287627261716 217 2479864356740 218 2687793663499 219 2912659432672 220 3155802341173 221 3418665628407 222 3702803895295 223 4009890233083 224 4341726276726 225 4700250490167 226 5087549625799 227 5505868352933 228 5957622337210 229 6445409386848 230 6972024390111 231 7540472223712 232 8153984782057 233 8816035920284 234 9530360884962 235 10300973563525 236 11132188666230 237 12028641638226 238 12995313943318 239 14037556043592 240 15161116238045 241 16372167119562 242 17677338476330 243 19083747752479 244 20599037540029 245 22231410634076 246 23989672772266 247 25883272904955 248 27922351924998 249 30117788920264 250 32481256674777 251 35025274773549 252 37763272833392 253 40709651381306 254 43879853893088 255 47290436570308 256 50959150343602 257 54905020814998 258 59148441613970 259 63711265874621 260 68616912513127 261 73890470874460 262 79558821627313 263 85650756430939 264 92197115463129 265 99230924117351 266 106787549433640 267 114904856206799 268 123623384803413 269 132986529364688 270 143040739920233 271 153835725633870 272 165424684500459 273 177864535078900 274 191216177382762 275 205544756992960 276 220919961346736 277 237416320519072 278 255113543646073 279 274096861359020 280 294457407580658 281 316292609227268 282 339706619426251 283 364810760713668 284 391724016493816 285 420573534906173 286 451495186088106 287 484634134805033 288 520145472207729 289 558194866214775 290 598959277548922 291 642627698187906 292 689401962567903 293 739497585716989 294 793144682072312 295 850588916240344 296 912092543442703 297 977935487677011 298 1048416519404544 299 1123854477751300 300 1204589603229814 301 1290984922535616 302 1383427756311930 303 1482331287661985 304 1588136267291579 305 1701312789487228 306 1822362219992543 307 1951819205985540 308 2090253855198217 309 2238274009983091 310 2396527709512589 311 2565705761766396 312 2746544524872573 313 2939828814814542 314 3146395046416717 315 3367134519549591 316 3602996965029599 317 3854994257360531 318 4124204416689951 319 4411775801802577 320 4718931625548426 321 5046974688721149 322 5397292473130813 323 5771362484428010 324 6170757995194005 325 6597154072796993 326 7052334053669772 327 7538196341948060 328 8056761705683203 329 8610180942415950 330 9200743099468168 331 9830884113964639 332 10503196071701571 333 11220436942551786 334 11985541005882405 335 12801629816876850 336 13672023942345358 337 14600255309447395 338 15590080412993444 339 16645494216745554 340 17770745012246931 341 18970350063240799 342 20249112318091997 343 21612138010255573 344 23064855450452434 345 24613034822042441 346 26262809305591244 347 28020697336419438 348 29893626344781709 349 31888957774117855 350 34014513753582631 351 36278605211503204 352 38690061833959832 353 41258263647432337 354 43993174659473889 355 46905378328111285 356 50006115327230738 357 53307323370066606 358 56821679593307821 359 60562645256825925 360 64544513299101789 361 68782458495854985 362 73292590803907422 363 78092011630205008 364 83198873652568335 365 88632443926441197 366 94413170951848074 367 100562755429109563 368 107104225430574070 369 114062015711461143 370 121462051943624619 371 129331839592508181 372 137700558281708270 373 146599161362969209 374 156060481603435131 375 166119342706401755 376 176812677649442497 377 188179653558092211 378 200261804176440561 379 213103169655886977 380 226750444809380520 381 241253135557156331 382 256663724803519146 383 273037847480270743 384 290434476095704659 385 308916116536502703 386 328549015571632614 387 349403379820290354 388 371553607751462062 389 395078534498387915 390 420061691183517302 391 446591578562219393 392 474761956822531216 393 504672151378906051 394 536427376650090951 395 570139077697739004 396 605925291881340219 397 643911030450628248 398 684228682414063929 399 727018440656396431 400 772428752841737313 401 820616797139142821 402 871748985521797569 403 926001494749864051 404 983560828025255648 405 1044624407512250424 406 1109401200969231648 407 1178112382785940420 408 1250992032950840670 409 1328287874356841568 410 1410262052278429006 411 1497191956558079077 412 1589371090669880481 413 1687109988350429605 414 1790737182329524542 415 1900600226022402467 416 2017066773118349615 417 2140525716121622130 418 2271388389217150948 419 2410089836741918034 420 2557090153111554493 421 2712875895735772313 422 2877961577298412058 423 3052891239220352211 424 3238240113254331685 425 3434616373356244401 426 3642662985407786115 427 3863059657300582417 428 4096524897646566390 429 4343818186034904451 430 4605742263852925384 431 4883145549058104841 432 5176924684741038832 433 5488027225387970733 434 5817454471589232356 435 6166264457685674116 436 6535575104089437532 437 6926567539431128921 438 7340489605352662917 439 7778659549833791319 440 8242469923064469983 441 8733391682572449082 442 9252978522922519951 443 9802871437621543774 444 10384803529973382116 445 11000605081547061957 446 11652208896574592126 447 12341655932088160972 448 13071101233833540347 449 13842820189055069897 450 14659215118073565719 451 15522822217181263605 452 16436318876849750610 453 17402531389363484766 454 18424443072146589215 455 19505202822671450574 456 20648134133706369766 457 21856744586761495404 458 23134735855230315408 459 24486014237273728809 460 25914701752945792210 461 27425147828047566805 462 29021941602499278058 463 30709924888420875205 464 32494205819332209734 465 34380173218660166962 466 36373511732932784624 467 38480217761182322436 468 40706616230289717024 469 43059378251483926461 470 45545539712516054919 471 48172520844809306694 472 50948146825353389554 473 53880669457183241044 474 56978789993968081117 475 60251683157570215273 476 63709022420430444126 477 67361006607191227230 478 71218387894356973090 479 75292501268557213868 480 79595295529828050750 481 84139365907277488548 482 88937988381922406861 483 94005155791576168587 484 99355615821756856659 485 105004910965812182592 486 110969420568304837627 487 117266405044035420250 488 123914052397817368314 489 130931527147515998306 490 138339021787608542496 491 146157810906982155876 492 154410308111547815713 493 163120125877745727452 494 172312138502155203640 495 182012548286915844963 496 192248955142224581946 497 203050429760668192072 498 214447590562264589004 499 226472684581562806496 500 239159672515014357431 501 252544318118249866353 502 266664282192683905989 503 281559221371252164495 504 297270891965968895025 505 313843259109323055312 506 331322611477744873652 507 349757681853625470962 508 369199773842132814495 509 389702895026269329864 510 411323896907135370686 511 434122621942519121508 512 458162058064495882533 513 483508501021815287169 514 510231724964730556214 515 538405161654011168063 516 568106088752332512177 517 599415827619339107140 518 632419951113056065293 519 667208501862448162323 520 703876221562563597088 521 742522791804929114209 522 783253087048091423617 523 826177440293588588718 524 871411922130881956467 525 919078633774364283484 526 969306014820240810140 527 1022229166409987149552 528 1077990190598618348805 529 1136738546684329877757 530 1198631425374979185230 531 1263834141624704191704 532 1332520547100777878285 533 1404873463198311348943 534 1481085135655638826821 535 1561357711780573727394 536 1645903741442016608758 537 1734946702938739296235 538 1828721555011179507787 539 1927475316219675040921 540 2031467673076954378213 541 2140971618280786063667 542 2256274120568264864669 543 2377676827672021913279 544 2505496804046220947700 545 2640067304990106198658 546 2781738588997275591068 547 2930878770120202241700 548 3087874712353776400874 549 3253132968004788287621 550 3427080762243382912508 551 3610167025997979329509 552 3802863479600173360671 553 4005665769554420628459 554 4219094661069498840918 555 4443697288960358253831 556 4680048469809631299503 557 4928752078253720109942 558 5190442490558839960960 559 5465786098632788830313 560 5755482897940046435997 561 6060268152773677629982 562 6380914142682343988518 563 6718231993843037808877 564 7073073599539673596675 565 7446333633907399259964 566 7838951663498682953225 567 8251914361235402749265 568 8686257827736082611268 569 9143070025025328951366 570 9623493328088316840026 571 10128727199762162795651 572 10660030994945186793804 573 11218726900146547308838 574 11806203014923866704317 575 12423916581812176242452 576 13073397371911352241555 577 13756251233370970162739 578 14474163810617199571480 579 15228904442256091607652 580 16022330246238452858046 581 16856390400981519738938 582 17733130631842126128219 583 18654697912468805829039 584 19623345391312360062118 585 20641437553732504695278 586 21711455630947092165071 587 22836003267256900625131 588 24017812457849099843050 589 25259749769700670307600 590 26564822859039436904017 591 27936187299073709573537 592 29377153732709490129187 593 30891195365266768470522 594 32481955813291647646673 595 34153257325897160700263 596 35909109396234484157966 597 37753717781080591724660 598 39691493947787621308242 599 41727064968277141757259 600 43865283881119349444678 601 46111240543234434387932 602 48470272994215907121621 603 50947979356838352545820 604 53550230298888943496476 605 56283182082097223363399 606 59153290225638069846750 607 62167323812397965281892 608 65332380468028918144672 609 68655902043617768047903 610 72145691034777607770989 611 75809927770868827437103 612 79657188410192834932798 613 83696463778009550271278 614 87937179086534939870533 615 92389214577200863040492 616 97062927127948263003874 617 101969172869580725855887 618 107119330857892801130760 619 112525327849686386998535 620 118199664233691090715904 621 124155441168960299065140 622 130406388986450351209563 623 136966896911218599465282 624 143852044166064018636639 625 151077632519351855246279 626 158660220343425064685413 627 166617158252130819293256 628 174966626389947716760169 629 183727673447552895866153 630 192920257482946168449714 631 202565288629851840205883 632 212684673779744293302273 633 223301363326720727977206 634 234439400069446314556265 635 246123970367574459981922 636 258381457655454421839816 637 271239498419444562205756 638 284727040751001048671683 639 298874405591577340428856 640 313713350791700213417916 641 329277138110847200497741 642 345600603291599477743678 643 362720229346233819980291 644 380674223201328836377417 645 399502595851120737706772 646 419247246178364969649178 647 439952048607134607059967 648 461662944760667797204513 649 484428039303613283470490 650 508297700157420389559485 651 533324663284470446800127 652 559564142246719932908322 653 587073942752146881194726 654 615914582413306144858286 655 646149415950552567270101 656 677844766084416726782597 657 711070060370670235768701 658 745897974244531216826665 659 782404580550384898241991 660 820669505847378543425454 661 860776093792125443787054 662 902811575914897809900072 663 946867250117600965794835 664 993038667238224549083205 665 1041425826039510097335990 666 1092133376997341149481495 667 1145270835278638595410683 668 1200952803317789008778431 669 1259299203416253622338167 670 1320435520810852835184616 671 1384493057673305120160342 672 1451609198526182714648847 673 1521927687579125235133548 674 1595598918513618226441957 675 1672780237265058909609463 676 1753636258377337409765026 677 1838339195527468273479176 678 1927069206846523907899854 679 2020014755687486973228842 680 2117372987521752163910243 681 2219350123672613753624115 682 2326161872627786009878407 683 2438033859702048232916899 684 2555202075857631363141639 685 2677913346521661042513784 686 2806425821279547843837011 687 2941009485357799180353072 688 3081946693852609132800632 689 3229532729698305499831678 690 3384076386416197115576231 691 3545900576725501210632763 692 3715342968148376454130455 693 3892756646785935047339600 694 4078510810496659631014073 695 4272991492757533178185858 696 4476602318547299880732833 697 4689765293644542575383680 698 4912921628797310698274685 699 5146532600279065101934792 700 5391080448415105167297751 701 5647069315726853753316366 702 5915026226416570998404383 703 6195502108983902933877097 704 6489072863847146547966755 705 6796340477917056980367811 706 7117934188159301485148831 707 7454511696263244228752588 708 7806760436630394002042870 709 8175398899984631437874286 710 8561178015009963219115538 711 8964882590518157308548951 712 9387332820760890607266661 713 9829385856606139057672462 714 10291937445420181793775333 715 10775923642610906790910861 716 11282322597919889544149472 717 11812156419675034547266197 718 12366493120358337284785830 719 12946448646978497239856812 720 13553188999892774124474860 721 14187932443869429017043841 722 14851951815349633765497380 723 15546576930027456355048109 724 16273197095048017663829690 725 17033263730297496952232370 726 17828293103455249990049772 727 18659869183666914656940945 728 19529646618910313141338307 729 20439353842330867521621717 730 21390796313053877480446537 731 22385859897203587638605580 732 23426514395108761160750329 733 24514817220916212763559908 734 25652917241104281194859569 735 26843058778650723955649874 736 28087585789902490010969296 737 29388946221479838071364551 738 30749696554864533695519639 739 32172506546631264393443804 740 33660164172624969305395819 741 35215580784722618976013991 742 36841796489189990141448811 743 38541985756008460698571346 744 40319463268949646322241633 745 42177690026571209532325829 746 44120279704743281854570855 747 46151005291744060317585717 748 48273806007435292968234850 749 50492794518493895411746928 750 52812264462187087655320731 751 55236698291683396604681380 752 57770775456445202064830367 753 60419380931796156176121320 754 63187614112355771755650740 755 66080798084627358794187141 756 69104489294673812123171251 757 72264487627459690150010343 758 75566846915139734930857651 759 79017885892272104341098263 760 82624199616694035392238926 761 86392671375554429981064646 762 90330485096819741076593061 763 94445138287389789453421621 764 98744455519849547691785695 765 103236602490771877512716295 766 107930100674448620900850924 767 112833842596890733859393480 768 117957107755979500927674258 769 123309579214694590993674970 770 128901360895471404675236150 771 134742995604870904711989736 772 140845483818964067616277493 773 147220303261057972710444919 774 153879429304709217301603435 775 160835356236297049265059231 776 168101119412855075971804552 777 175690318352297239376573649 778 183617140794716721194046748 779 191896387774992374457290833 780 200543499748606163214460387 781 209574583814259815432129046 782 219006442078683849156543010 783 228856601210856109282840928 784 239143343234798941262790753 785 249885737612098662302054717 786 261103674667401848507792271 787 272817900412280250058255821 788 285050052825138652582981633 789 297822699647153229468012056 790 311159377756695875078660127 791 325084634187203394985083436 792 339624068856118696403695601 793 354804379075240023084291282 794 370653405915698933787894327 795 387200182503718712803477285 796 404474984326423277975782692 797 422509381630137622324600601 798 441336293996991627140501210 799 460990047189069344544119245 800 481506432352989258402268993 801 502922767681511416903608618 802 525277962632705123574045191 803 548612584811223869609055114 804 572968929620489853719350373 805 598391092798930303868416039 806 624925045958006689951166139 807 652618715244470829156538784 808 681522063254251302862264388 809 711687174330447801680518726 810 743168343383280450937202730 811 776022168375327111988874887 812 810307646621182904179960516 813 846086275056606734002298679 814 883422154638486965556655383 815 922382099043368946640088243 816 963035747839057517764607248 817 1005455684310736466869004676 818 1049717558130360236888978760 819 1095900213065561493665579744 820 1144085819932217415639554397 821 1194360015002909774395556869 822 1246812044092045370224703549 823 1301534912547147415816084631 824 1358625541385042149877114577 825 1418184929821112467234688628 826 1480318324449740075120984333 827 1545135395344264358369453581 828 1612750419355529923414996743 829 1683282470899120661707366337 830 1756855620532978574193757765 831 1833599141639015367937107390 832 1913647725534849255719866612 833 1997141705354662799051854113 834 2084227289051698706959545108 835 2175056801888802708448982251 836 2269788938798018613730326597 837 2368589027005242667073108021 838 2471629299331699547551784661 839 2579089178600201418129983450 840 2691155573591156786389336951 841 2808023187010786069695260850 842 2929894835952354115055564795 843 3056981785350112439719850644 844 3189504094945450749586838797 845 3327690980305141334517126649 846 3471781188452933734158858440 847 3622023388697760197466466326 848 3778676579264875589390092532 849 3942010510360004240781472317 850 4112306124321450449059238644 851 4289856013540760284704298131 852 4474964896859369526603716755 853 4667950115176332486006250945 854 4869142147031189390653826927 855 5078885144955877101257283161 856 5297537493420831098016295060 857 5525472389232631274500161616 858 5763078445274244617506875244 859 6010760318513663349253482501 860 6268939363243085728383359620 861 6538054310548270555580522086 862 6818561975046898420856809538 863 7110937989975207515834871649 864 7415677571744448181894035970 865 7733296315132314929114903961 866 8064331020320103242417514758 867 8409340553033379157786112310 868 8768906739093106430105444685 869 9143635294734908025528957119 870 9534156794107139304260700725 871 9941127675413158772205229827 872 10365231287220323243097959574 873 10807178976517226459041876086 874 11267711220162300601591636661 875 11747598801430506505421147164 876 12247644033431241533055575389 877 12768682031239170222722308147 878 13311582034651258158727940088 879 13877248783557218047376889757 880 14466623947987721956877862324 881 15080687614984426248338523553 882 15720459834518997903678632035 883 16387002226774230413209715030 884 17081419653189936722974992819 885 17804861953768889473589653452 886 18558525753234629997937607172 887 19343656338732745996656554386 888 20161549611871253066682866858 889 21013554118003240597781847445 890 21901073155767034143190282769 891 22825566970014991378624191871 892 23788555031382812161896398419 893 24791618405876085396156486441 894 25836402217980892448631821571 895 26924618210939791797661940173 896 28058047407974651967577310719 897 29238542878382704616003924062 898 30468032612583142564902348493 899 31748522510347684872704911313 900 33082099486611117202483112627 901 34470934699425957711491599434 902 35917286904800502542501632595 903 37423505943340607758151483675 904 38992036363804136897218432323 905 40625421188872051733969142416 906 42326305828643186655662812836 907 44097442147569799743080178048 908 45941692690769645503636657634 909 47862035075876509000538598104 910 49861566556826562688356109226 911 51943508766221467148440750281 912 54111212643162597058477514862 913 56368163553713013017470427786 914 58717986611416662165037421893 915 61164452205586621624551089838 916 63711481745367928565827883478 917 66363153627884481313775685104 918 69123709439095667568789617191 919 71997560396315556756772469478 920 74989294041687798671416926704 921 78103681196261543981713037328 922 81345683184679958233543380533 923 84720459340871949277398319860 924 88233374805531887431878758135 925 91890008626580043134971162515 926 95696162174220626879845372781 927 99657867882653331120248121918 928 103781398330950687391621110736 929 108073275676085969617136572076 930 112540281451587461379228466790 931 117189466745803231700852052778 932 122028162774288922796619363200 933 127063991861377980713494298136 934 132304878846562181808060063995 935 137759062931898726844585676223 936 143435109987271656820083631861 937 149341925330968359012038677431 938 155488767003689692789413224473 939 161885259554793207898288214038 940 168541408360276423434971294368 941 175467614492739586672024287239 942 182674690164328271170389464915 943 190173874764443974939623917040 944 197976851514829247876866853006 945 206095764765481154768147863227 946 214543237955726953144542252460 947 223332392265707046737661225963 948 232476865984456643330424334383 949 241990834621757385595352075477 950 251889031791947814093430197502 951 262186770898935122540417140804 952 272899967652744767375290560545 953 284045163449077332684286899465 954 295639549644518341109821359309 955 307700992761264656581226154051 956 320248060656495693776672183160 957 333300049692827028880924606997 958 346877012947643392119206820229 959 360999789500515596176355213028 960 375690034839367172370086477304 961 390970252427569518051507038753 962 406863826475714935459176203492 963 423395055963443225956777529721 964 440589189958385515452597525189 965 458472464281036885080231658019 966 477072139566183492814322745272 967 496416540773388356204060332407 968 516535098200989473205333224263 969 537458390060082653447509279616 970 559218186667056305864992168158 971 581847496315414659368196384161 972 605380612889876829864994319650 973 629853165288069987689549802310 974 655302168717553352108274023500 975 681766077938414068781296437750 976 709284842524274339839601416454 977 737899964217239733864149088333 978 767654556455109955044706268648 979 798593406152063799854475864952 980 830763037817028572526691644226 981 864211780097049223192408771786 982 898989834836193383115574287373 983 935149348743863719427769349654 984 972744487769848583673845003390 985 1011831514287024279064863550997 986 1052468867186337913653786083771 987 1094717244992547323399378139992 988 1138639692113184989945408283712 989 1184301688337344927463097441539 990 1231771241705176809167845569379 991 1281118984873408948741668947507 992 1332418275106823405187727344884 993 1385745298030371376695799987095 994 1441179175281558108433179023456 995 1498802076207842847319789197260 996 1558699333759104548528224673266 997 1620959564730717331262965450793 998 1685674794518475446703922157919 999 1752940586552505208644371708527 1000 1822856176583416078379851913010