0 0 1 0 2 2 3 0 4 2 5 3 6 4 7 7 8 8 9 14 10 17 11 27 12 33 13 48 14 63 15 84 16 112 17 147 18 191 19 248 20 322 21 409 22 527 23 666 24 845 25 1062 26 1336 27 1666 28 2079 29 2579 30 3190 31 3936 32 4842 33 5933 34 7259 35 8854 36 10768 37 13074 38 15826 39 19120 40 23048 41 27728 42 33279 43 39879 44 47686 45 56916 46 67818 47 80667 48 95777 49 113552 50 134396 51 158825 52 187419 53 220833 54 259828 55 305301 56 358240 57 419797 58 491320 59 574296 60 670461 61 781811 62 910584 63 1059344 64 1231067 65 1429045 66 1657094 67 1919554 68 2221301 69 2567903 70 2965716 71 3421850 72 3944429 73 4542650 74 5226869 75 6008796 76 6901749 77 7920612 78 9082273 79 10405799 80 11912554 81 13626680 82 15575376 83 17789109 84 20302209 85 23153284 86 26385542 87 30047555 88 34193849 89 38885392 90 44190568 91 50186033 92 56957369 93 64600438 94 73222473 95 82943100 96 93896055 97 106230726 98 120113543 99 135730328 100 153288253 101 173017976 102 195176512 103 220050123 104 247957060 105 279251516 106 314327393 107 353622163 108 397622008 109 446866964 110 501956077 111 563554315 112 632399290 113 709308424 114 795187905 115 891041747 116 997981435 117 1117237652 118 1250172430 119 1398291994 120 1563262220 121 1746924774 122 1951314176 123 2178678202 124 2431499136 125 2712516518 126 3024753872 127 3371546696 128 3756572691 129 4183886611 130 4657957230 131 5183707104 132 5766558217 133 6412480389 134 7128043724 135 7920477942 136 8797736021 137 9768562671 138 10842571882 139 12030329812 140 13343444465 141 14794666435 142 16397996885 143 18168804532 144 20123956362 145 22281957915 146 24663105625 147 27289655843 148 30186007109 149 33378897539 150 36897623523 151 40774275543 152 45043993691 153 49745249935 154 54920152639 155 60614776595 156 66879526686 157 73769530210 158 81345062475 159 89672014167 160 98822396156 161 108874886860 162 119915432023 163 132037892949 164 145344748990 165 159947866060 166 175969327299 167 193542333017 168 212812183656 169 233937342312 170 257090585395 171 282460257905 172 310251629752 173 340688364788 174 374014120577 175 410494277295 176 450417809402 177 494099321392 178 541881247720 179 594136233386 180 651269720248 181 713722741768 182 781974945414 183 856547873774 184 938008508462 185 1026973101768 186 1124111332123 187 1230150791152 188 1345881833359 189 1472162830769 190 1609925845406 191 1760182757788 192 1924031901299 193 2102665222759 194 2297376014364 195 2509567278510 196 2740760752433 197 2992606649179 198 3266894188424 199 3565562954054 200 3890715147999 201 4244628829123 202 4629772186049 203 5048818930258 204 5504664915798 205 6000446050609 206 6539557605815 207 7125675050712 208 7762776499508 209 8455166899179 210 9207504114085 211 10024827018094 212 10912585752623 213 11876674340562 214 12923465796355 215 14059849927938 216 15293274060833 217 16631786862100 218 18084085506033 219 19659566459352 220 21368380112469 221 23221489552554 222 25230733816197 223 27408895907450 224 29769775942872 225 32328269835249 226 35100453873895 227 38103675644020 228 41356651787596 229 44879573050453 230 48694217159527 231 52824070140272 232 57294456628146 233 62132679840273 234 67368171948797 235 73032655543736 236 79160317000261 237 85787992651419 238 92955368619542 239 100705195299950 240 109083517595027 241 118139921950933 242 127927801410574 243 138504640018846 244 149932317875755 245 162277438318659 246 175611678858572 247 190012167461840 248 205561885985815 249 222350102740598 250 240472836131973 251 260033351588292 252 281142694166005 253 303920259231638 254 328494403898836 255 355003102130374 256 383594646437394 257 414428399433280 258 447675598775576 259 483520219074832 260 522159894731862 261 563806907987336 262 608689246549313 263 657051735610781 264 709157249447564 265 765288007916960 266 825746963694685 267 890859286537475 268 960973951045884 269 1036465435002734 270 1117735535900303 271 1205215313523733 272 1299367167161148 273 1400687056652912 274 1509706876827405 275 1626996995699395 276 1753168967568236 277 1888878432591312 278 2034828215384651 279 2191771636104125 280 2360516048029252 281 2541926616819626 282 2736930357684349 283 2946520447435663 284 3171760829741190 285 3413791133173106 286 3673831922567419 287 3953190305792541 288 4253265919558618 289 4575557319037921 290 4921668797944844 291 5293317667546599 292 5692342024490507 293 6120709039558191 294 6580523801621199 295 7074038752829397 296 7603663753688191 297 8171976819261801 298 8781735569902953 299 9435889443009653 300 10137592715391915 301 10890218388476675 302 11697372992249685 303 12562912367510358 304 13490958489236220 305 14485917398209679 306 15552498312434347 307 16695733993788732 308 17921002450528748 309 19234050061455477 310 20641016212326587 311 22148459541206758 312 23763385895648595 313 25493278110363991 314 27346127721288558 315 29330468739324344 316 31455413614007795 317 33730691525933577 318 36166689155556656 319 38774494084373944 320 41565940994671473 321 44553660844475749 322 47751133204424434 323 51172741955352568 324 54833834557806049 325 58750785116806487 326 62941061479502282 327 67423296618098046 328 72217364564982025 329 77344461183919331 330 82827190078722588 331 88689653958194082 332 94957551796218488 333 101658282146720008 334 108821052993972688 335 116476998542553572 336 124659303375951188 337 133403334437649376 338 142746781316699696 339 152729805349113820 340 163395198076007348 341 174788549632797516 342 186958427678522256 343 199956567509619740 344 213838074041994146 345 228661636386404434 346 244489755784189040 347 261388987717054657 348 279430199053484297 349 298688841144217488 350 319245239834519036 351 341184903418754941 352 364598849622069367 353 389583952759301134 354 416243312289665673 355 444686644056096167 356 475030695575353254 357 507399686825897898 358 541925778063982773 359 578749566289615089 360 618020612079681746 361 659897998604412414 362 704550924751045305 363 752159334391570767 364 802914583948496016 365 857020150539695140 366 914692383116859777 367 976161299150575713 368 1041671429565035390 369 1111482714782900056 370 1185871454904603863 371 1265131317223249739 372 1349574404462067864 373 1439532387314914216 374 1535357705078740507 375 1637424838386094583 376 1746131658274170273 377 1861900856072525386 378 1985181458849852317 379 2116450435429731744 380 2256214398274547229 381 2405011406840959878 382 2563412878328177283 383 2732025612080740514 384 2911493934265719315 385 3102501969818767576 386 3305776049054092631 387 3522087256754877052 388 3752254132001832677 389 3997145527468663006 390 4257683637408986465 391 4534847204078491146 392 4829674912889855653 393 5143268987180837024 394 5476798994086675336 395 5831505873658630615 396 6208706204055349079 397 6609796716351798202 398 7036259073274661752 399 7489664926977443987 400 7971681271812269821 401 8484076108952352684 402 9028724440663353172 403 9607614613012729737 404 10222855026858605495 405 10876681238067636504 406 11571463469074394844 407 12309714555129037867 408 13094098349879452845 409 13927438616298434904 410 14812728430413320598 411 15753140126818712687 412 16752035816552691135 413 17812978509612219080 414 18939743876168153994 415 20136332682415111163 416 21406983938976915745 417 22756188801878515606 418 24188705268291326910 419 25709573711583259173 420 27324133302651404241 421 29038039367086483242 422 30857281730437820859 423 32788204106710473455 424 34837524588234815656 425 37012357298229845744 426 39320235270729650025 427 41769134626061529386 428 44367500113783098323 429 47124272098899666380 430 50048915071297324289 431 53151447762672800016 432 56442474959814578517 433 59933221107897296578 434 63635565802527323351 435 67562081274619065040 436 71726071977796674803 437 76141616393942193756 438 80823611178747233259 439 85787817775680760764 440 91050911633701869315 441 96630534171323508346 442 102545347637282970549 443 108815093026143106664 444 115460651215636452826 445 122504107501487377909 446 129968819714855182542 447 137879490117437759010 448 146262241279678719483 449 155144696158486162121 450 164556062602405216090 451 174527222524310453608 452 185090825994459462279 453 196281390520185318917 454 208135405792628775980 455 220691444195788717460 456 233990277388815563721 457 248074999288917153115 458 262991155799565776786 459 278786881646906641416 460 295513044706408312919 461 313223398221948543601 462 331974741340717938992 463 351827088409592088540 464 372843847502063413301 465 395092008669467266005 466 418642342436133233328 467 443569609085346426250 468 469952779311652516921 469 497875266845143744095 470 527425173685037814476 471 558695548613153951756 472 591784659692870168573 473 626796281495943847285 474 663839997838250552856 475 703031520846125767614 476 744493027217727309113 477 788353512588741405695 478 834749164958928845896 479 883823758185613558883 480 935729066602337561052 481 990625301875655512533 482 1048681573270604004656 483 1110076372555854769169 484 1174998084843077933156 485 1243645526721809549611 486 1316228513121255549872 487 1392968454404124333117 488 1474098985274997306108 489 1559866627167061589179 490 1650531485856419281848 491 1746367986142918052109 492 1847665645530685112318 493 1954729888940497125421 494 2067882906590081475652 495 2187464557287616560733 496 2313833319498319540149 497 2447367292664417913244 498 2588465251385228084412 499 2737547755196786962305 500 2895058316829885296037 501 3061464631971705488854 502 3237259873709893455980 503 3422964054999228502417 504 3619125462660415070341 505 3826322166598277859528 506 4045163608113290149838 507 4276292271376275795797 508 4520385442341728921071 509 4778157059591051155956 510 5050359661823548075692 511 5337786436950751705965 512 5641273377999180084159 513 5961701551288512954084 514 6299999482626929047840 515 6657145667553737609809 516 7034171211962031864505 517 7432162609751557991762 518 7852264664495151532972 519 8295683562451625485963 520 8763690104624665536971 521 9257623105952032580544 522 9778892970112981349821 523 10328985448865158270141 524 10909465595266405279698 525 11521981920602785267914 526 12168270765332774288465 527 12850160894870147288453 528 13569578331565677631292 529 14328551434811544896076 530 15129216241783680706567 531 15973822081957403519979 532 16864737479181945413368 533 17804456355781429899548 534 18795604553864934041484 535 19840946689778007848952 536 20943393358414221623520 537 22106008704929599823174 538 23332018382266956689218 539 24624817913803217631764 540 25987981481382673480858 541 27425271159994815299348 542 28940646621399265651464 543 30538275330094526536966 544 32222543256174150836730 545 33998066130816170737812 546 35869701271411679367980 547 37842560004659054283630 548 39922020717334464685738 549 42113742565899889875136 550 44423679877629985468148 551 46858097277532223404096 552 49423585577004103613566 553 52127078461920434576597 554 54975870019676650235225 555 57977633146634666163584 556 61140438879429942709360 557 64472776695706715580255 558 67983575832057132418851 559 71682227669253954750018 560 75578609237290680444206 561 79683107895282413313467 562 84006647243940889467527 563 88560714331123619059364 564 93357388213875853411930 565 98409369943441152162047 566 103730014042918380664091 567 109333361550596591921888 568 115234174705511435302940 569 121447973355445102709789 570 127991073171443910138899 571 134880625756961423511484 572 142134660743959259608372 573 149772129972720961034553 574 157812953856765815274087 575 166278070039099070022928 576 175189484451112576661473 577 184570324890765942787593 578 194444897242244091535538 579 204838744465114024735870 580 215778708487103540497019 581 227292995141010545501991 582 239411242292936372791666 583 252164591316033848281254 584 265585762071285429797201 585 279709131564493374276729 586 294570816456688201386582 587 310208759613560456327972 588 326662820888310852641653 589 343974872341513147095197 590 362188898111211644358320 591 381351099156550384527850 592 401510003108774211230402 593 422716579474474796346688 594 445024360447499394807408 595 468489567598019880571346 596 493171244719899247403596 597 519131397130717463802390 598 546435137732654891884316 599 575150840156907637833698 600 605350299329453982553134 601 637108899811834720166426 602 670505792287184954702884 603 705624078579093517779032 604 742551005609003195645023 605 781378168716837000200634 606 822201724789380251415527 607 865122615661704615416482 608 910246802278630143637623 609 957685510125927505710210 610 1007555486464709857954027 611 1059979269927299586559374 612 1115085473058828210232404 613 1173009078415989128162085 614 1233891748862766655027505 615 1297882152732666393778410 616 1365136304558029671419882 617 1435817922099489949364237 618 1510098800442585043024737 619 1588159203964041932839872 620 1670188277007370827070214 621 1756384474146213950295781 622 1846956010954467743879219 623 1942121336244614289408292 624 2042109626780040783164388 625 2147161305513480684978625 626 2257528584452167160327241 627 2373476033300941940596470 628 2495281175087508464314096 629 2623235110029359936963231 630 2757643168959756935431925 631 2898825597690586542139026 632 3047118273753122583811210 633 3202873457023745152654701 634 3366460575810693610208959 635 3538267050050053525508070 636 3718699153334551836101302 637 3908182915577499655765887 638 4107165068196529486994825 639 4316114033787779293125770 640 4535520962351043290223142 641 4765900816220309850923129 642 5007793505952218069666275 643 5261765079527471933584436 644 5528408967327349359685228 645 5808347285459334290515577 646 6102232200122794447014123 647 6410747355827746278593304 648 6734609370407321251738834 649 7074569399897813361075747 650 7431414776499397584977069 651 7805970722976023159618954 652 8199102147004875932283412 653 8611715519144455503644992 654 9044760838256020834388060 655 9499233688386231152836380 656 9976177391299570556984562 657 10476685259037930033835620 658 11001902951081880039490566 659 11553030940894066956329068 660 12131327096840188267150048 661 12738109382707541636444086 662 13374758683275618142694603 663 14042721760638051469510864 664 14743514347230893810713643 665 15478724381789137169160652 666 16250015394732125413144215 667 17059130049769519219559302 668 17907893848823317536251913 669 18798219007678660841549888 670 19732108510107323003793377 671 20711660348553545964525614 672 21739071959832814452778849 673 22816644864670963632864510 674 23946789520304347744752290 675 25132030395772386100672255 676 26375011279962388973478799 677 27678500832913928021299728 678 29045398391356962659794668 679 30478740039945308981413065 680 31981704960155722768816443 681 33557622069353779047662832 682 35209976963081823231393482 683 36942419174202541320373165 684 38758769763135186527144539 685 40663029254051289479279148 686 42659385932553898866960160 687 44752224521050224099000985 688 46946135248743206680261591 689 49245923333914311835312194 690 51656618896949036640204860 691 54183487323369662761247089 692 56832040096988088561357556 693 59608046124176662455404146 694 62517543571178376835905037 695 65566852237341207732840739 696 68762586488166503350779782 697 72111668773109910948852122 698 75621343754167239263799257 699 79299193072418810285222109 700 83153150780896268900287728 701 87191519473377587550470752 702 91422987140011305662992319 703 95856644782022152541649829 704 100502004819159487483274672 705 105369020325019917376763160 706 110468105126908589208539921 707 115810154808502681899749049 708 121406568655248325838852566 709 127269272584161463747048482 710 133410743101517061305501943 711 139844032333802730559666503 712 146582794179285526026418790 713 153641311629597834611311196 714 161034525312893465890182357 715 168778063312361968107521483 716 176888272316221713488301180 717 185382250157744436273917927 718 194277879806399858442642534 719 203593864873853168332860759 720 213349766701304969611767062 721 223566043097537624850815987 722 234264088800028611091912822 723 245466277734615715023769389 724 257196007152455966914280460 725 269477743726415713579547561 726 282337071692568954515544634 727 295800743126171045350959459 728 309896730445321394792340906 729 324654281239538384721805725 730 340103975524649238319912104 731 356277785529754042267198527 732 373209138126563976727955372 733 390932980016146706347361637 734 409485845793044841927802148 735 428905929011874723705187589 736 449233156386871174446615252 737 470509265260428354831397471 738 492777884482506819737668334 739 516084618848842103604706222 740 540477137252210842125664133 741 566005264707597162716089069 742 592721078418965879094495094 743 620679008062501392752657020 744 649935940468624085461446057 745 680551328892861821197978815 746 712587307073745914013178476 747 746108808284332032514994956 748 781183689592731024799806501 749 817882861556187158709742015 750 856280423582776967064852330 751 896453805204736571540879614 752 938483913517775485267083433 753 982455287051517577070334065 754 1028456256347442930664660081 755 1076579111532406289173027636 756 1126920277187997922414354626 757 1179580494828711158478333521 758 1234665013315108367840972725 759 1292283787541955600655102670 760 1352551685755647960226990504 761 1415588705870196672388971853 762 1481520201166619148088891491 763 1550477115776790592402390170 764 1622596230369706378567366458 765 1698020418475696031763049977 766 1776898913902450919028059273 767 1859387589715808445433379874 768 1945649249278106731031813634 769 2035853929857617658259355327 770 2130179219344116410514245719 771 2228810586628087085173913538 772 2331941726224432979994275588 773 2439774917745894508281476041 774 2552521400856716689901714889 775 2670401766363492666124746326 776 2793646364127582216870093062 777 2922495728512109033094920383 778 3057201022106323502896414553 779 3198024498501126844158785000 780 3345239984921837299000548468 781 3499133385557891527896800487 782 3660003206464168111739738575 783 3828161102945051133668402262 784 4003932450370278351538219531 785 4187656939411100998569702296 786 4379689196726383677319409244 787 4580399432171058565041072044 788 4790174113643886266036331438 789 5009416670737836864353210910 790 5238548228404662602186358858 791 5478008371895464623893669938 792 5728255944291339898185009516 793 5989769877992613440020443742 794 6263050061591801269549762172 795 6548618243614400536447701308 796 6847018974672957821211026900 797 7158820589643721410497922976 798 7484616231541638754848761506 799 7825024918838620758287863260 800 8180692658041968566757777140 801 8552293603424758941104416276 802 8940531265877928410183757876 803 9346139772934906135506914484 804 9769885182104047515363021354 805 10212566849731946755003103642 806 10675018857712093879906236492 807 11158111500448432304403204417 808 11662752834582315034617201009 809 12189890294094304668022980716 810 12740512373499374373860824366 811 13315650381965510113985664847 812 13916380271301661151515487865 813 14543824540881615821960435200 814 15199154222695879088614418738 815 15883590949854191384993871099 816 16598409111997156062714381899 817 17344938101216744718040854662 818 18124564652232443286499040632 819 18938735280722713096968377083 820 19788958823870504944980283275 821 20676809087347024765827200604 822 21603927603130060275096619912 823 22572026502732202531570642555 824 23582891510600508610859699099 825 24638385062642835976981305054 826 25740449555037531334259596404 827 26891110728692683912492066257 828 28092481194939074418925524165 829 29346764108267597859247561770 830 30656256992157655595486758156 831 32023355724288157269479829589 832 33450558687677718407004746553 833 34940471094565770937207208614 834 36495809490122022813856522792 835 38119406443358426305789423833 836 39814215432915975435032172685 837 41583315935708701367477662600 838 43429918726729637645487482460 839 45357371398658770473454187075 840 47369164110261577091284733461 841 49468935572929211399314109744 842 51660479285088264528130370254 843 53947750024599874098710314141 844 56334870609675366473332566157 845 58826138939259201042948047388 846 61426035324270377742904690600 847 64139230121551326203358595567 848 66970591682849300290086022605 849 69925194631650164659251970238 850 73008328481198917075227157344 851 76225506607576106771202459905 852 79582475592255279651820749594 853 83085224949144530822803088844 854 86739997251716030730191002150 855 90553298676451902966871017078 856 94531909979483993631522216300 857 98682897923979843599807480574 858 103013627176528552593875974886 859 107531772691509242164783325578 860 112245332603182557992011763548 861 117162641646033215765555672734 862 122292385124710147612346396706 863 127643613455761550206470204120 864 133225757304246320006877559354 865 139048643339222281924435244758 866 145122510633066621160103171484 867 151458027730576411413714379610 868 158066310414828546969023691976 869 164958940197850237568649005672 870 172147983565265077199568351854 871 179646012005237174270280465470 872 187466122853238616447082518182 873 195621960985415388079742099256 874 204127741394625577779849005860 875 212998272684573193576188817264 876 222248981518863100108304833410 877 231895938063259537915269765306 878 241955882460944487660765832821 879 252446252382144990804952107003 880 263385211691132704611308722988 881 274791680275296811544235570682 882 286685365082755368562817345865 883 299086792416802810856342456945 884 312017341537395253813981941158 885 325499279621853202918113886104 886 339555798139016123861828838226 887 354211050693217992090575327107 888 369490192396670491170368893989 889 385419420831144137568513917296 890 402026018662230570273779725054 891 419338397971954976242011087993 892 437386146378089675077100669419 893 456200075011201940708825404070 894 475812268423255014980631804774 895 496256136504474932929078571597 896 517566468488201346463824472619 897 539779489126562271368178109544 898 562932917123055021972266903708 899 587066025911483135144409319463 900 612219706874196589834390980591 901 638436535096215048997575716864 902 665760837755586321996137494300 903 694238765254250094920151518675 904 723918365197745731065745784751 905 754849659336328338811349536522 906 787084723584445289069057442740 907 820677771240082112075583945579 908 855685239530218617514886894947 909 892165879613549806526492635992 910 930180850176728571390982449120 911 969793814765685458794394056691 912 1011071042999082323010921395643 913 1054081515816669210768611693066 914 1098897034921245282092566079804 915 1145592336579083261101315646019 916 1194245209950071416610005840229 917 1244936620125466303920832653656 918 1297750836058042697881968854692 919 1352775563576583899082136824567 920 1410102083684085842910684493155 921 1469825396346762498217312357324 922 1532044369988948605285206958172 923 1596861896917309966513024606919 924 1664385054906402774671572817857 925 1734725275186583777538834662420 926 1807998517084574812105522255582 927 1884325449576641233775961103524 928 1963831640024367329808081199666 929 2046647750373416749210339814044 930 2132909741106466622763730904134 931 2222759083252715236672176542356 932 2316342978768000261498393297896 933 2413814589611643594422948231016 934 2515333275858676408294636993670 935 2621064843199111188773821262248 936 2731181800189434189186860821294 937 2845863625635510307594618698090 938 2965297046500642040155709977268 939 3089676326747624743991852670190 940 3219203567539312538901349241536 941 3354089019238474137206053098394 942 3494551405664597848336245838906 943 3640818261082822908583838000382 944 3793126280418353931162501960512 945 3951721683208581327470210525280 946 4116860591824708595170179638732 947 4288809424515003921063423928468 948 4467845303842876100111770508024 949 4654256481114851830003512873136 950 4848342777416232553864548206130 951 5050416041895764827300340006014 952 5260800627965100439217960721179 953 5479833888104184143006856596395 954 5707866687990021986675851465656 955 5945263940693587249139864972492 956 6192405161717950572657057377870 957 6449685045680114048655081033249 958 6717514065469525177334421586449 959 6996319094747886633541212219472 960 7286544054687703978892386233434 961 7588650585881069756889524683701 962 7903118746385514290967047935499 963 8230447736910408133171113416986 964 8571156654185427362465600074466 965 8925785273592041468486933822345 966 9294894862179906887823083065383 967 9679069023232501808054849131326 968 10078914573590376024824220005696 969 10495062454986071887550129650095 970 10928168680692159286066590816485 971 11378915318832982003378019054082 972 11848011513761699661760431597646 973 12336194546957096358453027513311 974 12844230938949483810982390249261 975 13372917593841925836063790195886 976 13923082988052027324039016611726 977 14495588404960742319881336435671 978 15091329217218142979044980916277 979 15711236218521937550323185902174 980 16356277006752817692813605168866 981 17027457420421543038363390141783 982 17725823030456126888910027950621 983 18452460689433667576591353097522 984 19208500140440375082018644656002 985 19995115687825275377895694685345 986 20813527932198042751767790940277 987 21665005572109524041914828004060 988 22550867274944893279520572079670 989 23472483619654129802823613553553 990 24431279114042770926358638323117 991 25428734289447779592065014243540 992 26466387875729020588945640755791 993 27545839059616393166239785732417 994 28668749829566265386002388721270 995 29836847410398643686731185629366 996 31051926791108642481822858736371 997 32315853349372451304625309165113 998 33630565576399294827936489122600 999 34998077905917013706323941193334 1000 36420483651220037384028404944463