0 1 1 0 2 1 3 1 4 2 5 2 6 5 7 6 8 11 9 16 10 25 11 34 12 51 13 69 14 98 15 134 16 181 17 238 18 316 19 410 20 536 21 691 22 887 23 1122 24 1423 25 1788 26 2246 27 2800 28 3483 29 4300 30 5304 31 6508 32 7983 33 9745 34 11869 35 14399 36 17436 37 21040 38 25367 39 30482 40 36568 41 43735 42 52239 43 62239 44 74073 45 87950 46 104277 47 123348 48 145739 49 171864 50 202437 51 238027 52 279527 53 327687 54 383720 55 448656 56 524019 57 611157 58 712010 59 828347 60 962704 61 1117463 62 1295856 63 1500928 64 1736747 65 2007321 66 2317879 67 2673646 68 3081326 69 3547546 70 4080711 71 4689428 72 5384461 73 6176802 74 7080094 75 8108328 76 9278538 77 10608605 78 12120137 79 13835850 80 15782941 81 17990041 82 20491140 83 23322367 84 26526496 85 30149187 86 34243798 87 38867479 88 44086782 89 49973270 90 56610070 91 64086885 92 72507001 93 81981989 94 92640005 95 104619975 96 118080987 97 133195735 98 150161147 99 169191063 100 190528403 101 214437905 102 241219692 103 271200778 104 304750835 105 342272817 106 384220756 107 431090717 108 483440950 109 541881111 110 607095459 111 679831745 112 760927187 113 851297660 114 951967484 115 1064057136 116 1188816894 117 1327614568 118 1481974089 119 1653563518 120 1844238869 121 2056031944 122 2291199631 123 2552211583 124 2841807983 125 3162988350 126 3519076632 127 3913711278 128 4350918919 129 4835105323 130 5371141219 131 5964356927 132 6620639434 133 7346429236 134 8148831858 135 9035618581 136 10015354618 137 11097407220 138 12292092827 139 13610689663 140 15065606859 141 16670406855 142 18439998913 143 20390674860 144 22540332383 145 24908521956 146 27516702818 147 30388308188 148 33549040515 149 37026959298 150 40852821454 151 45060193020 152 49685839680 153 54769869960 154 60356187724 155 66492675663 156 73231715151 157 80630413924 158 88751206505 159 97662134228 160 107437541134 161 118158423967 162 129913232700 163 142798296404 164 156918749013 165 172389046853 166 189334039639 167 207889604585 168 228203883112 169 250438041492 170 274767700043 171 301383851052 172 330494512238 173 362325832333 174 397124005189 175 435156586833 176 476714705231 177 522114637169 178 571700366786 179 625845465024 180 684956050919 181 749473020337 182 819875466441 183 896683324166 184 980461331898 185 1071822166009 186 1171431020979 187 1280009307779 188 1398339949493 189 1527271740706 190 1667725477210 191 1820699100316 192 1987274779472 193 2168624951580 194 2366020512690 195 2580837907504 196 2814568599641 197 3068827401150 198 3345363413178 199 3646069768153 200 3972996273279 201 4328360809060 202 4714563936765 203 5134202230487 204 5590085146931 205 6085250576224 206 6622984313853 207 7206838198744 208 7840652597646 209 8528577543198 210 9275098678648 211 10085061852569 212 10963703037978 213 11916676931644 214 12950091475357 215 14070541091907 216 15285146476732 217 16601593171719 218 18028177418527 219 19573850897778 220 21248273569411 221 23061865544565 222 25025867933892 223 27152402901508 224 29454543722509 225 31946384279230 226 34643119694718 227 37561126727293 228 40718056536171 229 44132927556256 230 47826232183093 231 51820044038264 232 56138140618203 233 60806127113751 234 65851577363518 235 71304176626384 236 77195883495451 237 83561094472668 238 90436829913814 239 97862923625041 240 105882236306442 241 114540873799379 242 123888431990463 243 133978247917868 244 144867680709763 245 156618400358281 246 169296709821528 247 182973876882317 248 197726503313542 249 213636906047939 250 230793540162993 251 249291436509997 252 269232686119287 253 290726942306488 254 313891975225689 255 338854247688983 256 365749549803976 257 394723659046457 258 425933066239135 259 459545731715233 260 495741915466640 261 534715043045373 262 576672654484364 263 621837395406275 264 670448101293076 265 722760931259164 266 779050606469376 267 839611706600642 268 904760083841836 269 974834344715000 270 1050197463916517 271 1131238477138272 272 1218374322264885 273 1312051772442991 274 1412749535964043 275 1520980462755652 276 1637293938320870 277 1762278401114931 278 1896564070731849 279 2040825818780362 280 2195786276900750 281 2362219109511834 282 2540952553139264 283 2732873145553237 284 2938929754855930 285 3160137826979090 286 3397583970661252 287 3652430793520531 288 3925922117671570 289 4219388483494695 290 4534253080538973 291 4872038008820338 292 5234371020749368 293 5622992641510879 294 6039763830170463 295 6486674073666490 296 6965850089299369 297 7479565022102428 298 8030248326951841 299 8620496215797187 300 9253082875317511 301 9930972329255870 302 10657331167667472 303 11435542011173296 304 12269217950730290 305 13162217824606188 306 14118662592805801 307 15142952664348174 308 16239786459295364 309 17414180054552038 310 18671488218842184 311 20017426679539135 312 21458095951961387 313 23000006567725184 314 24650106060708359 315 26415807541048534 316 28305020245964484 317 30326181892157978 318 32488293251045199 319 34800954766264615 320 37274405670820821 321 39919565418278818 322 42748077924311627 323 45772358428854157 324 49005643517335088 325 52462044107732536 326 56156601988588254 327 60105349712132077 328 64325374478189795 329 68834885811579588 330 73653287723662859 331 78801255160770337 332 84300815490631213 333 90175434831187956 334 96450110038909702 335 103151466164313719 336 110307860263602190 337 117949491380127163 338 126108517663525478 339 134819180448668987 340 144117936348683267 341 154043597195602762 342 164637478976858232 343 175943559616554655 344 188008646853466418 345 200882556083820065 346 214618299534163938 347 229272286656567949 348 244904537235042923 349 261578907125071835 350 279363328251891560 351 298330062825122711 352 318555973544625406 353 340122809798499298 354 363117511791468273 355 387632532655786292 356 413766180663492454 357 441622981652787649 358 471314063984831800 359 502957566215094863 360 536679070012218011 361 572612058591952251 362 610898403438191916 363 651688879675770859 364 695143713129449448 365 741433159546156408 366 790738119302794162 367 843250788207150727 368 899175348031958779 369 958728697539300863 370 1022141227985031388 371 1089657644032391341 372 1161537834447974427 373 1238057793707074422 374 1319510599305361029 375 1406207446129149012 376 1498478743147606757 377 1596675274036649416 378 1701169427510254207 379 1812356499262373943 380 1930656071861804209 381 2056513474836224968 382 2190401331911157684 383 2332821198018522798 384 2484305293726924963 385 2645418340137065222 386 2816759502653002254 387 2998964447158041210 388 3192707517841145682 389 3398704040751167112 390 3617712763245574785 391 3850538434030261676 392 4098034534974267778 393 4361106170094534896 394 4640713124015873290 395 4937873096087754721 396 5253665123699364996 397 5589233201860476250 398 5945790113955610824 399 6324621481734401790 400 6727090050952837236 401 7154640221846655226 402 7608802842512988934 403 8091200275637795435 404 8603551758482173701 405 9147679067972511102 406 9725512512834521460 407 10339097266194666311 408 10990600062824279985 409 11682316276218108049 410 12416677402154348030 411 13196258965905601901 412 14023788882475194210 413 14902156289241469643 414 15834420883394208943 415 16823822786019565756 416 17873792968544425990 417 18987964266159994765 418 20170183017607121641 419 21424521359028554222 420 22755290215323881340 421 24167053020155944041 422 25664640212522941925 423 27253164544885787134 424 28938037255709258403 425 30724985145687374591 426 32620068615969535698 427 34629700712429572402 428 36760667240324122576 429 39020147998695892756 430 41415739205525817648 431 43955477168905020217 432 46647863282578665859 433 49501890407716691394 434 52527070727381800757 435 55733465142871276904 436 59131714307364677939 437 62733071374196617403 438 66549436565077257414 439 70593393644630125427 440 74878248417495718656 441 79418069344424409512 442 84227730405665191541 443 89322956319242237366 444 94720370255733764321 445 100437544169544436782 446 106493051902981785358 447 112906525196889030815 448 119698712780361741076 449 126891542688569587101 450 134508187999106322232 451 142573136152825573916 452 151112262069340045455 453 160152905241920071092 454 169723951043766166161 455 179855916451206012212 456 190581040439837709461 457 201933379282237921190 458 213948907029793522679 459 226665621432827974122 460 240123655610855866813 461 254365395755436505708 462 269435605209747218432 463 285381555238683463281 464 302253162869227064553 465 320103136149571553633 466 338987127246029153716 467 358963893764589292021 468 380095468759467823801 469 402447339857978763635 470 426088638011839329377 471 451092336351201393128 472 477535459704185197395 473 505499305310138403263 474 535069675347451601891 475 566337121861559713234 476 599397204777965230880 477 634350763649358203358 478 671304203892207903224 479 710369798232005821750 480 751666004190269746213 481 795317798409932985042 482 841457028737896037169 483 890222784946896435061 484 941761789109858759267 485 996228806603323456067 486 1053787078857091636882 487 1114608778930947901983 488 1178875491150141794960 489 1246778715995561604433 490 1318520401606437915313 491 1394313503218490358499 492 1474382572034278378307 493 1558964374988762824830 494 1648308547059827379191 495 1742678277741283822837 496 1842351033496546535413 497 1947619317980903808672 498 2058791472035986435985 499 2176192515432243357213 500 2300165032567133374093 501 2431070104301947915022 502 2569288288369605631468 503 2715220650764594139422 504 2869289850794587255429 505 3031941282456436002713 506 3203644275088060185688 507 3384893356236040552528 508 3576209579989673028121 509 3778141924026511748525 510 3991268758949321934593 511 4216199393495613824683 512 4453575699561729501153 513 4704073820992776223060 514 4968405970478533021996 515 5247322318914085468617 516 5541612982003115872484 517 5852110108911096795272 518 6179690078227671928473 519 6525275806539028589560 520 6889839175398700609130 521 7274403582540666980951 522 7680046623704798214036 523 8107902911515945905457 524 8559167038425955020413 525 9035096690817007129454 526 9537015921977997197894 527 10066318591775005311861 528 10624471981499322608344 529 11213020592508682441624 530 11833590137993025740640 531 12487891737353981102747 532 13177726323460710307725 533 13904989273231470619850 534 14671675272826397784310 535 15479883428956084065146 536 16331822638714730935863 537 17229817230601941951383 538 18176312890375286121640 539 19173882885671562912706 540 20225234604392936217962 541 21333216422195166886420 542 22500824915560485726433 543 23731212437329165698820 544 25027695072803731434808 545 26393760994987481371036 546 27833079238861585899256 547 29349508915115357289201 548 30947108885198478030698 549 32630147920143863201267 550 34403115367185295836474 551 36270732348851134033079 552 38237963520922621500320 553 40310029416388279977526 554 42492419404376344592138 555 44790905293885223796970 556 47211555614138174321424 557 49760750604331766337704 558 52445197947723194976857 559 55271949286061562101348 560 58248417552727832082123 561 61382395164137272058928 562 64682073111517960211181 563 68156060996510758462278 564 71813408056813613334897 565 75663625229582562319711 566 79716708303316123342028 567 83983162210613350791460 568 88474026517467752816088 569 93200902166615036993196 570 98175979536004790078746 571 103412067875533960012851 572 108922626189037068163711 573 114721795630829501074002 574 120824433490289058418755 575 127246148840519845055502 576 134003339931692403085652 577 141113233412496526569724 578 148593925468085863836431 579 156464424966048140961365 580 164744698707305043693677 581 173455718882344065534437 582 182619512839020092188191 583 192259215272040689128336 584 202399122950590941315814 585 213064752104845328263074 586 224282898599007208430135 587 236081701023264743048208 588 248490706844545092281628 589 261540941761198683623050 590 275264982414891418860413 591 289697032618783560966653 592 304873003269930975618078 593 320830596120250143913696 594 337609391590019056920371 595 355250940814955711046268 596 373798862128388975287191 597 393298942187834474249996 598 413799241966678133783257 599 435350207840266700561263 600 458004788008092692505097 601 481818554503233768492770 602 506849831053681281113191 603 533159827070625284857434 604 560812778053420930617113 605 589876092712445669913351 606 620420507127001975035112 607 652520246268057284481456 608 686253193232959902649450 609 721701066553168719807874 610 758949605954907529935375 611 798088766967935833884333 612 839212924798161862204658 613 882421087896617505937590 614 927817121679656743992920 615 975509982873688581667465 616 1025613964982065506673061 617 1078248955392009217326833 618 1133540704665907502234908 619 1191621108583558286320437 620 1252628503530720690853061 621 1316707975853741779202970 622 1384011685831349358964237 623 1454699206941479068209604 624 1528937881135087751776169 625 1606903190858272673952722 626 1688779148601106090006822 627 1774758704783792320072177 628 1865044174831116072101986 629 1959847686321440747679838 630 2059391647140437372783474 631 2163909235608393044634531 632 2273644913597744148882501 633 2388854963699837506757961 634 2509808051551934996500566 635 2636785814481864258128184 636 2770083477684317900135724 637 2910010499193589796184072 638 3056891244979128332834577 639 3211065695545874498502370 640 3372890185488374705789052 641 3542738177508487029251605 642 3721001072479429757796425 643 3908089057205468756565974 644 4104431991605897917026550 645 4310480337124753595195042 646 4526706128254053780728621 647 4753603989137945078184242 648 4991692197319095950981697 649 5241513796775689642076513 650 5503637762499598198049596 651 5778660218961427741514301 652 6067205714919350680807849 653 6369928557132573766824393 654 6687514205661301650607880 655 7020680733548608444876018 656 7370180353811282007759167 657 7736801016790742937875131 658 8121368081058364174386522 659 8524746061204979904264069 660 8947840456000178683273566 661 9391599660554887687611440 662 9857016966290241744068321 663 10345132652677205000092799 664 10857036174895773240450564 665 11393868451738831909201030 666 11956824258286274105750406 667 12547154728067319123754662 668 13166169969647077925318037 669 13815241802783268253888507 670 14495806619536193111938217 671 15209368375944028305638995 672 15957501720133440780055134 673 16741855262985258073262081 674 17564154997755452943144806 675 18426207875324009659088299 676 19329905542049307098380702 677 20277228247502556930646592 678 21270248929688553453013947 679 22311137485682665173093660 680 23402165235974673208882590 681 24545709591162862130669787 682 25744258930033904625858429 683 27000417698448569435167215 684 28316911738879596359200209 685 29696593860867038736839929 686 31142449663119816944645668 687 32657603618448671402425060 688 34245325433219476865793388 689 35909036693513092792631309 690 37652317810725501805269775 691 39478915279883530399710880 692 41392749264546596902226004 693 43397921522754668544719031 694 45498723689129423662807511 695 47699645928877743427257379 696 50005385980149571477757441 697 52420858601901255156750580 698 54951205445179308899702712 699 57601805366500505955937753 700 60378285202834164807895885 701 63286531028520717644259728 702 66332699915362403430435355 703 69523232218023226127570672 704 72864864407855009372658023 705 76364642479247069441981927 706 80029935953661313233048170 707 83868452507581503085596301 708 87888253251761528829184937 709 92097768690318139836041536 710 96505815389469330226915376 711 101121613386981920968683204 712 105954804374755750999878322 713 111015470688344721266626159 714 116314155138696130884076732 715 121861881722882538350150812 716 127670177252208874666742626 717 133751093937700570104374720 718 140117232974725056023037472 719 146781769170263424512036685 720 153758476658245445931421354 721 161061755750279034536686772 722 168706660971164179519714313 723 176708930330665813644771133 724 185085015885255280890612325 725 193852115645795279039541215 726 203028206889569504154245872 727 212632080937519581954238919 728 222683379460185526355406104 729 233202632378520136722218022 730 244211297428606191269665390 731 255731801462210341666927327 732 267787583558209790808238639 733 280403140023083329988238096 734 293604071362024734620651082 735 307417131305663658505371217 736 321870277981032052712328756 737 336992727319135888064726748 738 352815008795455367818086603 739 369369023603738056525082538 740 386688105367749331977723952 741 404807083500032231256681411 742 423762349321393522159470195 743 443591925059596093389667279 744 464335535850797832487900986 745 486034684872447609732304028 746 508732731741837434552693938 747 532474974320121688297914460 748 557308734067566940181612316 749 583283445101886106259029146 750 610450747117966197054771309