0 1 1 1 2 1 3 3 4 3 5 5 6 8 7 10 8 13 9 18 10 26 11 31 12 42 13 52 14 68 15 89 16 110 17 136 18 173 19 212 20 262 21 330 22 398 23 487 24 592 25 720 26 864 27 1050 28 1262 29 1508 30 1804 31 2152 32 2550 33 3037 34 3584 35 4236 36 5011 37 5880 38 6901 39 8095 40 9472 41 11048 42 12899 43 14996 44 17436 45 20261 46 23460 47 27128 48 31385 49 36189 50 41713 51 48020 52 55209 53 63359 54 72708 55 83298 56 95299 57 108960 58 124401 59 141887 60 161737 61 184108 62 209351 63 237948 64 270079 65 306331 66 347222 67 393090 68 444660 69 502715 70 567739 71 640722 72 722567 73 814206 74 916681 75 1031571 76 1159721 77 1303027 78 1463159 79 1641599 80 1840601 81 2062626 82 2309640 83 2584696 84 2890862 85 3231120 86 3609253 87 4029479 88 4495722 89 5013056 90 5587183 91 6223271 92 6927797 93 7708411 94 8572082 95 9527531 96 10584447 97 11752132 98 13042341 99 14467282 100 16039846 101 17774660 102 19688613 103 21797641 104 24121819 105 26682361 106 29500808 107 32602461 108 36015571 109 39767931 110 43893086 111 48426348 112 53405113 113 58871780 114 64873026 115 71456549 116 78677448 117 86595519 118 95273045 119 104780569 120 115195535 121 126596997 122 139076843 123 152733100 124 167669196 125 184001534 126 201856065 127 221365149 128 242677527 129 265954242 130 291364715 131 319098591 132 349360226 133 382367223 134 418359161 135 457598100 136 500358834 137 546946809 138 597692798 139 652947895 140 713098247 141 778562713 142 849784804 143 927254964 144 1011500075 145 1103083797 146 1202621156 147 1310779968 148 1428268584 149 1555864162 150 1694404638 151 1844783861 152 2007977219 153 2185039214 154 2377089294 155 2585355754 156 2811155651 157 3055899278 158 3321118130 159 3608465820 160 3919705005 161 4256752295 162 4621670023 163 5016664325 164 5444125254 165 5906626963 166 6406918181 167 6947978461 168 7533013515 169 8165444553 170 8848979968 171 9587602300 172 10385565988 173 11247474567 174 12178271011 175 13183239154 176 14268084480 177 15438930094 178 16702326223 179 18065332796 180 19535532603 181 21121021694 182 22830532608 183 24673428280 184 26659716797 185 28800171044 186 31106343638 187 33590577981 188 36266155739 189 39147303717 190 42249233232 191 45588276771 192 49181950932 193 53048950284 194 57209365777 195 61684700675 196 66497930038 197 71673698844 198 77238401528 199 83220207311 200 89649341275 201 96558124039 202 103981076578 203 111955186942 204 120520016994 205 129717789949 206 139593732331 207 150196188075 208 161576751023 209 173790642507 210 186896879883 211 200958404581 212 216042578757 213 232221339555 214 249571413425 215 268174845358 216 288119230064 217 309497969762 218 332410887017 219 356964516397 220 383272427062 221 411455925470 222 441644434854 223 473975880918 224 508597519683 225 545666402895 226 585349838286 227 627826386343 228 673286401749 229 721932630787 230 773981347009 231 829663027537 232 889223061464 233 952923142014 234 1021042007399 235 1093876401187 236 1171742561607 237 1254977301122 238 1343939010649 239 1439009539747 240 1540595366732 241 1649128960667 242 1765070849109 243 1888911166943 244 2021171158233 245 2162405770759 246 2313205324532 247 2474197533524 248 2646050349902 249 2829474168675 250 3025224095579 251 3234103384063 252 3456966022093 253 3694719546677 254 3948328939942 255 4218819904334 256 4507282030109 257 4814873625420 258 5142825353240 259 5492444288841 260 5865119366951 261 6262325916027 262 6685630371423 263 7136696773837 264 7617292072770 265 8129291912253 266 8674688056036 267 9255594901820 268 9874256224011 269 10533054048151 270 11234516255134 271 11981324699931 272 12776325561961 273 13622538508040 274 14523166192844 275 15481606554901 276 16501463526384 277 17586558499569 278 18740944657913 279 19968919664359 280 21275039395720 281 22664134507713 282 24141325778123 283 25712040111287 284 27382030186499 285 29157392442904 286 31044586177291 287 33050456413081 288 35182255382471 289 37447664893333 290 39854823407916 291 42412351015228 292 45129376361508 293 48015567910557 294 51081163851263 295 54337003485161 296 57794564161203 297 61465996324550 298 65364160780065 299 69502671623997 300 73895937927763 301 78559207135951 302 83508615982041 303 88761238854790 304 94335139637454 305 100249430507321 306 106524329531359 307 113181221081770 308 120242725155102 309 127732764472144 310 135676636207321 311 144101092184099 312 153034418576828 313 162506519355630 314 172549010738368 315 183195314061381 316 194480754283007 317 206442669780201 318 219120521913393 319 232556009813783 320 246793199397241 321 261878650773005 322 277861553954625 323 294793878213160 324 312730522468863 325 331729473169671 326 351851979211954 327 373162727647063 328 395730028688424 329 419626019401599 330 444926869372944 331 471712996853511 332 500069306601092 333 530085429753057 334 561855976876335 335 595480814732681 336 631065346548681 337 668720807643030 338 708564587540231 339 750720557419453 340 795319414859867 341 842499058793623 342 892404971578628 343 945190621230657 344 1001017897355784 345 1060057556926826 346 1122489692574009 347 1188504240343555 348 1258301498342119 349 1332092672755131 350 1410100467692000 351 1492559689367775 352 1579717881490988 353 1671836011138955 354 1769189170951215 355 1872067319787567 356 1980776077282098 357 2095637542696657 358 2216991154226783 359 2345194613205356 360 2480624834099147 361 2623678944528746 362 2774775356469687 363 2934354871349576 364 3102881839879814 365 3280845406038826 366 3468760788057459 367 3667170627640355 368 3876646429010234 369 4097790048215611 370 4331235255817714 371 4577649406917953 372 4837735165923817 373 5112232321190150 374 5401919716482457 375 5707617253446471 376 6030187991008993 377 6370540385306155 378 6729630605774933 379 7108464970763224 380 7508102536177754 381 7929657779877212 382 8374303419701688 383 8843273409443514 384 9337866043412880 385 9859447220088186 386 10409453902329066 387 10989397712739205 388 11600868704753531 389 12245539363944753 390 12925168762808832 391 13641606922070118 392 14396799431105969 393 15192792250458765 394 16031736750059277 395 16915895045433070 396 17847645542483446 397 18829488758945774 398 19864053480079150 399 20954103162811109 400 22102542653597891 401 23312425290280795 402 24586960291976669 403 25929520511184678 404 27343650621026113 405 28833075640695442 406 30401709873747614 407 32053666346143157 408 33793266634538697 409 35625051169733786 410 37553790110521736 411 39584494667670988 412 41722428978666907 413 43973122626840723 414 46342383687129204 415 48836312400826912 416 51461315586674260 417 54224121660579231 418 57131796378945069 419 60191759417886255 420 63411801661739190 421 66800103313611946 422 70365252969199531 423 74116267499053068 424 78062612883806974 425 82214226137314418 426 86581538172046814 427 91175497749453962 428 96007596677634546 429 101089896085894630 430 106435053955379618 431 112056354054352348 432 117967736134944995 433 124183827546159912 434 130719976469859894 435 137592286587123466 436 144817653385785862 437 152413802300907734 438 160399328515701790 439 168793738624993163 440 177617494403157216 441 186892058463042761 442 196639942066583093 443 206884755309456479 444 217651259501250206 445 228965421984393382 446 240854473676059429 447 253346969113664757 448 266472849305116113 449 280263507660816713 450 294751858819221160 451 309972410652850971 452 325961339810308079 453 342756570548636750 454 360397857223633362 455 378926870781793442 456 398387289043081018 457 418824891144237949 458 440287656551592539 459 462825868396752969 460 486492221582547307 461 511341936063711492 462 537432875105095218 463 564825668949093652 464 593583844403830307 465 623773960094713265 466 655465747908755993 467 688732261158011471 468 723650029229947163 469 760299219286795642 470 798763805616547623 471 839131746383732463 472 881495168432778722 473 925950560770102242 474 972598976516227755 475 1021546244015603327 476 1072903187825004399 477 1126785859364459566 478 1183315777999832809 479 1242620183349636566 480 1304832298621524861 481 1370091605817819832 482 1438544133704799339 483 1510342758349655855 484 1585647517173266579 485 1664625937501850122 486 1747453379436320878 487 1834313394113653351 488 1925398098418171957 489 2020908566024667159 490 2121055235926972160 491 2226058339661482956 492 2336148347120241793 493 2451566432257351653 494 2572564959994502116 495 2699407994319363130 496 2832371828955329496 497 2971745542140025344 498 3117831575466769368 499 3270946338417893883 500 3431420840213036900 501 3599601349060589258 502 3775850080564268302 503 3960545917140247995 504 4154085158560259449 505 4356882305637441334 506 4569370879030397374 507 4792004273484129353 508 5025256649624751538 509 5269623865639159080 510 5525624449143791138 511 5793800611729791721 512 6074719308665290536 513 6368973344291138852 514 6677182525766808107 515 6999994868052824111 516 7338087850695802353 517 7692169729525174061 518 8062980906307803941 519 8451295357271838205 520 8857922123804532916 521 9283706868869225420 522 9729533500131306398 523 10196325863616671058 524 10685049511710291343 525 11196713546891024290 526 11732372545266943578 527 12293128564394623388 528 12880133236820297735 529 13494589954126948835 530 14137756146261439241 531 14810945658087779606 532 15515531228349832433 533 16252947076502933305 534 17024691599612897212 535 17832330185254972721 536 18677498146334193641 537 19561903780664570499 538 20487331561689194327 539 21455645467194329698 540 22468792449148221591 541 23528806051990014145 542 24637810186853400614 543 25798023065561713697 544 27011761302444487429 545 28281444192481133428 546 29609598170100114984 547 30998861457823662707 548 32451988914056782025 549 33971857085280908549 550 35561469472740396866 551 37223962024168538191 552 38962608856565763493 553 40780828221381395389 554 42682188723816057841 555 44670415803304728668 556 46749398487783635497 557 48923196434944492041 558 51196047268537126013 559 53572374223891456289 560 56056794117394399946 561 58654125649205464067 562 61369398055134598295 563 64207860124063121575 564 67174989591684206976 565 70276502928331508461 566 73518365539209238141 567 76906802389472317573 568 80448309073957782653 569 84149663352086165729 570 88017937162243621989 571 92060509137698385058 572 96285077647175075885 573 100699674376254978908 574 105312678474507686039 575 110132831294002661610 576 115169251737885575358 577 120431452246738503895 578 125929355451527502601 579 131673311514359462940 580 137674116188220048507 581 143943029627691255092 582 150491795975153482933 583 157332663757006822724 584 164478407126051302412 585 171942347977604690942 586 179738378978318115567 587 187880987547821667648 588 196385280824880247431 589 205267011661302052294 590 214542605688913567387 591 224229189495117916388 592 234344619955990100301 593 244907514776956433961 594 255937284282060523596 595 267454164505937179693 596 279479251645058708152 597 292034537914284437778 598 305142948869680153268 599 318828382260435011596 600 333115748462558080903 601 348031012561971756439 602 363601238157967636661 603 379854632945903368297 604 396820596155573822300 605 414529767923856600795 606 433014080668987486954 607 452306812551319488764 608 472442643109040434738 609 493457711144424521219 610 515389674956183632235 611 538277775016099948664 612 562162899176207068853 613 587087650512444071272 614 613096417915533334161 615 640235449525582574227 616 668552929129667174747 617 698099055645515025947 618 728926125800870776070 619 761088620141181813174 620 794643292503984222976 621 829649263082790734123 622 866168115229646336352 623 904263996150122450782 624 944003721630032527175 625 985456884959838869355 626 1028695970229330928035 627 1073796470148901700848 628 1120837008583380531710 629 1169899467990893623770 630 1221069121943234081827 631 1274434772934986390469 632 1330088895697237177075 633 1388127786213610836171 634 1448651716671075681698 635 1511765096585932168908 636 1577576640328006696729 637 1646199541302335884488 638 1717751653057247053323 639 1792355677569307440536 640 1870139360995064162402 641 1951235697189647524907 642 2035783139274201198277 643 2123925819575350338347 644 2215813778272508063658 645 2311603201069185166009 646 2411456666249691709851 647 2515543401496103643766 648 2624039550820385063421 649 2737128452015346939307 650 2855000925043063190531 651 2977855571758905915889 652 3105899087422104365260 653 3239346584460057781245 654 3378421928933174584812 655 3523358090203611137246 656 3674397504329371537600 657 3831792451685115426932 658 3995805449371024099032 659 4166709658992413876792 660 4344789310371402234898 661 4530340141817707076342 662 4723669857608538989139 663 4925098603306787871004 664 5134959459616814121111 665 5353598955503893465581 666 5581377601281026602595 667 5818670442444678736297 668 6065867635068073773162 669 6323375043541345406434 670 6591614861529192595496 671 6871026257049294855053 672 7162066042553880721681 673 7465209370986488659149 674 7780950458820512653329 675 8109803337067920568484 676 8452302631340749780487 677 8809004372089872113629 678 9180486836124356213507 679 9567351420620861159394 680 9970223550874746965895 681 10389753623028627246513 682 10826617983124983213144 683 11281519943880003871572 684 11755190840558099119969 685 12248391127450242822502 686 12761911516511359402576 687 13296574159700752107907 688 13853233876698062496053 689 14432779429731042987860 690 15036134847237100560543 691 15664260798225094652804 692 16318156019269766870386 693 16998858796064109289553 694 17707448501606988790105 695 18445047193181631828191 696 19212821270271522519305 697 20011983195731180361350 698 20843793282609726698509 699 21709561549026407679627 700 22610649643676260510204 701 23548472844639489078169 702 24524502134169348444759 703 25540266352331749855177 704 26597354432471774146960 705 27697417721493459641274 706 28842172388149144442348 707 30033401922654548182466 708 31272959730956135819481 709 32562771827213249231724 710 33904839628182881528763 711 35301242853219442411204 712 36754142533852081827971 713 38265784137046866458797 714 39838500806289468173542 715 41474716724900939895877 716 43176950606154561671705 717 44947819314805935214363 718 46790041624942605586760 719 48706442119239620494186 720 50699955234756121601057 721 52773629460734512641451 722 54930631694058262197619 723 57174251758090281406323 724 59507907090964872487785 725 61935147609626926343365 726 64459660755987606637018 727 67085276731953881475586 728 69815973930327744157958 729 72655884568669547944102 730 75609300533636697093883 731 78680679443578799341938 732 81874650937284409960990 733 85196023197231436779944 734 88649789715990705433219 735 92241136314569924784389 736 95975448421980619914225 737 99858318625644549832295 738 103895554502413851608983 739 108093186740523600158689 740 112457477563163145171165 741 116994929464538748174423 742 121712294269894637760963 743 126616582531365739401476 744 131715073271754498673972 745 137015324088971616954151 746 142525181634331805859280 747 148252792478150370982054 748 154206614376791694241459 749 160395427955822986950461 750 166828348824220132062136 751 173514840135341788919529 752 180464725610948144781134 753 187688203044873151363302 754 195195858303805970637808 755 202998679843252428331742 756 211108073757134256781666 757 219535879380405112623909 758 228294385464748171847538 759 237396346947858524732200 760 246855002337826213783778 761 256684091734889110519841 762 266897875513333796396351 763 277511153687419746522799 764 288539285986048634356006 765 299998212661468187756449 766 311904476058510992772143 767 324275242971797422226956 768 337128327818985034513233 769 350482216659463425519356 770 364356092088932928411740 771 378769859041033310938766 772 393744171528645240598274 773 409300460358621234570391 774 425460961854544466647902 775 442248747623692172454397 776 459687755405651799833210 777 477802821040974915982973 778 496619711599994645054756 779 516165159713329273250211 780 536466899146663577346504 781 557553701664292388298593 782 579455415227475329309466 783 602203003574834280941142 784 625828587234122912227721 785 650365486016406095090859 786 675848263045039883670830 787 702312770374122189926687 788 729796196252993746281100 789 758337114094870972307339 790 787975533210210455948560 791 818752951367497150454933 792 850712409245857908135884 793 883898546846637350856738 794 918357661933415458908731 795 954137770571836188769772 796 991288669843642157683524 797 1029862002811878230235098 798 1069911325816365251883229 799 1111492178181844053660082 800 1154662154424052682124443 801 1199480979041367179292864 802 1246010583983284492495109 803 1294315188890161470220787 804 1344461384201302479016820 805 1396518217232461891449510 806 1450557281327322375038823 807 1506652808190477824330456 808 1564881763513833471347619 809 1625323946012177355830811 810 1688062089987014195385213 811 1753181971542539220553628 812 1820772518581905671492639 813 1890925924715628859463581 814 1963737767219258541389450 815 2039307129182146083809494 816 2117736725993273568237620 817 2199133036315896538161577 818 2283606437707957801345399 819 2371271347049827685492744 820 2462246365947294158501031 821 2556654431283459748024024 822 2654622971098343537502197 823 2756284065981954261925904 824 2861774616172963304227126 825 2971236514560798530878435 826 3084816825796659123666519 827 3202667971725957968919573 828 3324947923361045447119351 829 3451820399621489890808299 830 3583455073076940996253170 831 3720027782934643179054719 832 3861720755522934974912809 833 4008722832530608259835969 834 4161229707269843775085200 835 4319444169240605935972583 836 4483576357283818096727227 837 4653844021619340860886569 838 4830472795075947973781579 839 5013696473830913149705385 840 5203757307986479839800175 841 5400906302322757524116506 842 5605403527578094048639491 843 5817518442618679165398357 844 6037530227872628921629979 845 6265728130416490334697124 846 6502411821113978606675926 847 6747891764221594807998625 848 7002489599889758855017775 849 7266538540001271448650765 850 7540383777805203286372524 851 7824382911819755307338480 852 8118906384492226847994123 853 8424337936122128312941178 854 8741075074570507426263508 855 9069529561294729683712857 856 9410127914267611824100156 857 9763311928358610070149139 858 10129539213772643714096032 859 10509283753163769628528940 860 10903036478061625266808599 861 11311305865268375201482170 862 11734618553907647997811368 863 12173519983829795138005770 864 12628575056099709983617895 865 13100368816319572565103394 866 13589507161564035115505910 867 14096617571729638321388725 868 14622349866128908086227819 869 15167376986187357555597107 870 15732395805128407499401174 871 16318127965562783358627620 872 16925320745929510667882256 873 17554747956765284058025625 874 18207210867813608203224808 875 18883539167018833934884564 876 19584591952482926913108927 877 20311258758500918121840780 878 21064460616828064650815987 879 21845151154367972182048277 880 22654317728512731014477450 881 23492982601407034979739577 882 24362204154448193820638848 883 25263078144379940130970463 884 26196739002382939183338665 885 27164361177609076694259371 886 28167160526657057530639240 887 29206395750536500408868779 888 30283369880716368311790796 889 31399431815909118859235371 890 32555977911296525052676657 891 33754453621956913523201538 892 34996355202314499302285472 893 36283231463491653919521038 894 37616685590504218246418107 895 38998377021306996143411056 896 40430023389762695111760665 897 41913402534673063102500538 898 43450354577084491288657341 899 45042784068153252794194853 900 46692662209927648087432857 901 48402029151485196212461985 902 50172996362943140860705300 903 52007749089940119028161578 904 53908548891275586268827868 905 55877736262481852416402096 906 57917733348191195525028254 907 60031046746258118085856348 908 62220270406693779495467796 909 64488088628566327814807420 910 66837279158127914240701381 911 69270716391535963412312576 912 71791374685642700183682826 913 74402331780444599809543908 914 77106772336900800952516915 915 79907991593946846399003873 916 82809399148659233660964571 917 85814522863655449912619343 918 88927012905943252090915920 919 92150645921574867355253768 920 95489329350603721642664398 921 98947105886983553946713687 922 102528158088205502395695089 923 106236813139624874057431534 924 110077547778585837443084510 925 114054993383623332647118953 926 118173941234193036979132901 927 122439347946552605600339642 928 126856341091605089732639631 929 131430225000704101089210847 930 136166486765609881372239701 931 141070802438991560279000670 932 146149043442078156634789653 933 151407283186269528136472329 934 156851803915744687092442827 935 162489103778332709863397884 936 168325904132140934873410266 937 174369157095683503333348683 938 180626053349503510321535114 939 187104030197534498527075532 940 193810779896719523779809385 941 200754258263680958980447506 942 207942693567511786391917672 943 215384595718058185104365103 944 223088765759365209626360724 945 231064305678262562754675647 946 239320628538395591031750709 947 247867468950338354099476255 948 256714893888761056046677013 949 265873313867984211262566505 950 275353494487616159091937220 951 285166568360339221801294065 952 295324047434304876124209185 953 305837835722998199811642916 954 316720242455837054576877009 955 327983995663204815542552466 956 339642256210054526934371479 957 351708632292667538658733414 958 364197194413625030508181525 959 377122490850532807647221586 960 390499563634528804736563564 961 404343965055124070253360472 962 418671774708457089676089182 963 433499617106578351761956842 964 448844679865953940225359385 965 464724732493957461852940556 966 481158145792709502857701101 967 498163911900250837666448131 968 515761664989672722106105558 969 533971702647475208562962480 970 552815007953112072954363852 971 572313272282379831281017826 972 592488918858019454504624683 973 613365127071653136698535326 974 634965857601945397838720900 975 657315878354658175430733364 976 680440791251096084467201345 977 704367059892279104336744300 978 729122038127036563068534791 979 754733999553122164950518057 980 781232167981372460366174240 981 808646748893870934790760122 982 837008961928073071671240212 983 866351074419859260522151123 984 896706436039513837877283075 985 928109514555716748525763908 986 960595932763743730384145670 987 994202506615202153081343582 988 1028967284587822389534888774 989 1064929588335040720887292042 990 1102130054656350803615337880 991 1140610678830707423278798570 992 1180414859356599746633535172 993 1221587444143771947023160465 994 1264174778203001163542500880 995 1308224752881804004215181715 996 1353786856695435210662043470 997 1400912227804110671554220457 998 1449653708188988781257795975 999 1500065899581080101714372446 1000 1552205221198973871536503349