1 0 2 0 3 1 4 1 5 3 6 3 7 7 8 14 9 22 10 26 11 40 12 45 13 69 14 71 15 112 16 215 17 281 18 353 19 458 20 563 21 728 22 874 23 1127 24 1447 25 1830 26 2180 27 2754 28 3206 29 4053 30 4580 31 5818 32 8317 33 10111 34 12246 35 14819 36 17849 37 21509 38 25759 39 30929 40 37082 41 44327 42 52662 43 62749 44 74151 45 88110 46 103510 47 122706 48 146761 49 173013 50 203202 51 238919 52 279541 53 327883 54 382059 55 447180 56 522727 57 610058 58 707028 59 823628 60 950083 61 1105121 62 1267388 63 1472731 64 1741566 65 2012494 66 2323392 67 2679561 68 3087479 69 3554089 70 4087456 71 4696693 72 5392271 73 6185177 74 7088476 75 8117240 76 9287043 77 10617815 78 12128068 79 13844554 80 15795452 81 18003303 82 20504207 83 23336421 84 26539564 85 30163261 86 34254770 87 38879481 88 44099917 89 49987733 90 56617789 91 64095975 92 72501039 93 81977409 94 92604184 95 104585883 96 118112256 97 133228882 98 150194040 99 169225779 100 190561100 101 214472934 102 241248995 103 271232566 104 304784981 105 342309325 106 384243568 107 431116621 108 483437308 109 541880704 110 607032674 111 679772131 112 760969388 113 851343860 114 951985129 115 1064078915 116 1188777176 117 1327579004 118 1481811999 119 1653406521 120 1844087416 121 2055885907 122 2290796624 123 2551813953 124 2840891924 125 3162078776 126 3517125540 127 3911767143 128 4351078472 129 4835271742 130 5371315144 131 5964539248 132 6620830377 133 7346629000 134 8149039671 135 9035835052 136 10015580656 137 11097643992 138 12292339783 139 13610947847 140 15065874039 141 16670685112 142 18440285128 143 20390974565 144 22540652397 145 24908855961 146 27517048503 147 30388667882 148 33549411305 149 37027347008 150 40853218929 151 45060608198 152 49686272037 153 54770319940 154 60356640512 155 66493149329 156 73232178223 157 80630899233 158 88751647730 159 97662597483 160 107438155370 161 118159064331 162 129913896445 163 142798987738 164 156919458911 165 172389783871 166 189334789811 167 207890387334 168 228204699983 169 250438892347 170 274768551594 171 301384736512 172 330495368541 173 362326728823 174 397124812606 175 435157435686 176 476715791754 177 522115765659 178 571701474583 179 625846622048 180 684957128792 181 749474149637 182 819876384035 183 896684293239 184 980462356142 185 1071823250049 186 1171431643797 187 1280009993692 188 1398339648419 189 1527271502473 190 1667723209789 191 1820696906348 192 1987276848171 193 2168627097277 194 2366022725461 195 2580840196589 196 2814570954823 197 3068829845762 198 3345365918162 199 3646072366589 200 3972998963852 201 4328363593111 202 4714566755011 203 5134205156901 204 5590088055351 205 6085253597116 206 6622987183752 207 7206841182202 208 7840656095065 209 8528581171303 210 9275102313211 211 10085065623623 212 10963706680971 213 11916680711990 214 12950094877319 215 14070544650711 216 15285150199905 217 16601597059338 218 18028180419519 219 19573854063993 220 21248274815063 221 23061866979545 222 25025865371503 223 27152400537007 224 29454549679606 225 31946390434013 226 34643125798231 227 37561133058282 228 40718062578786 229 44132933835679 230 47826237648768 231 51820049741560 232 56138146573795 233 60806133341177 234 65851581775971 235 71304181320615 236 77195884274904 237 83561095537263 238 90436822891601 239 97862916926369 240 105882242528429 241 114540880358734 242 123888434688651 243 133978250956280 244 144867675719229 245 156618395750730 246 169296688837122 247 182973856299594 248 197726483127240 249 213636886266193 250 230793487255817 251 249291384059695 252 269232567034851 253 290726823698384 254 313891722871209 255 338853995813224 256 365749566870526 257 394723676655101 258 425933084408844 259 459545750448163 260 495741934759822 261 534715062907585 262 576672674945120 263 621837416507567 264 670448123058122 265 722760953688324 266 779050629558071 267 839611730362718 268 904760108308168 269 974834369936433 270 1050197489914733 271 1131238503922222 272 1218374349840237 273 1312051800812119 274 1412749565165258 275 1520980492842983 276 1637293969320787 277 1762278433040885 278 1896564103558816 279 2040825852542307 280 2195786311649748 281 2362219145304943 282 2540952589980162 283 2732873183481999 284 2938929793798483 285 3160137867017925 286 3397584011724629 287 3652430835808909 288 3925922161481230 289 4219388528578903 290 4534253126884502 291 4872038056455700 292 5234371069720904 293 5622992691917837 294 6039763882029979 295 6486674127013552 296 6965850144130295 297 7479565078445048 298 8030248384811968 299 8620496275333953 300 9253082936461458 301 9930972392141357 302 10657331232024551 303 11435542077297816 304 12269218019098393 305 13162217894926632 306 14118662665017861 307 15142952738595050 308 16239786535305375 309 17414180132623007 310 18671488298551788 311 20017426761528369 312 21458096036304315 313 23000006654438761 314 24650106148733338 315 26415807631469174 316 28305020336801699 317 30326181985648660 318 32488293343078046 319 34800954861052222 320 37274405776731693 321 39919565526983607 322 42748078035921928 323 45772358543545260 324 49005643635172339 325 52462044228763105 326 56156602112743217 327 60105349839535472 328 64325374608983478 329 68834885945942778 330 73653287861588195 331 78801255302404471 332 84300815635700831 333 90175434980025335 334 96450110191154184 335 103151466320686749 336 110307860425030628 337 117949491545851828 338 126108517833272067 339 134819180622777232 340 144117936526825256 341 154043597378527454 342 164637479163663892 343 175943559808325601 344 188008647050195828 345 200882556285586007 346 214618299739091995 347 229272286867022846 348 244904537446993798 349 261578907342755517 350 279363328466924936 351 298330063045980860 352 318555973787804796 353 340122810048053140 354 363117512047061429 355 387632532917980647 356 413766180931245210 357 441622981927261285 358 471314064264204476 359 502957566501805716 360 536679070306496817 361 572612058893843255 362 610898403743495493 363 651688879988818351 364 695143713442168824 365 741433159867304468 366 790738119615856887 367 843250788528973995 368 899175348387699741 369 958728697903949437 370 1022141228350568146 371 1089657644407622566 372 1161537834816408418 373 1238057794085570653 374 1319510599660364636 375 1406207446494375190 376 1498478743523472217 377 1596675274423647927 378 1701169427841595797 379 1812356499605255222 380 1930656072082030356 381 2056513475068198349 382 2190401331886894219 383 2332821198007021424 384 2484305294265385412 385 2645418340688730933 386 2816759503217877256 387 2998964447736386658 388 3192707518433401754 389 3398704041358029203 390 3617712763867342279 391 3850538434667167042 392 4098034535626332647 393 4361106170762021970 394 4640713124699099227 395 4937873096787667367 396 5253665124415926587 397 5589233202594355912 398 5945790114705777445 399 6324621482502197173 400 6727090051740517638 401 7154640222653418033 402 7608802843338830693 403 8091200276483417005 404 8603551759346557908 405 9147679068857020450 406 9725512513737827425 407 10339097267119752937 408 10990600063771732690 409 11682316277188123476 410 12416677403142801774 411 13196258966917047094 412 14023788883502070128 413 14902156290293171752 414 15834420884454633338 415 16823822787105681112 416 17873792969688827428 417 18987964267330615981 418 20170183018803836507 419 21424521360253539168 420 22755290216575830955 421 24167053021437169657 422 25664640213829326238 423 27253164546222033131 424 28938037257076409542 425 30724985147086662491 426 32620068617393454973 427 34629700713886798718 428 36760667241797972877 429 39020148000203705233 430 41415739207035249514 431 43955477170451007670 432 46647863284212490775 433 49501890409388373499 434 52527070729074686173 435 55733465144602732224 436 59131714309102509781 437 62733071375975970351 438 66549436566832079639 439 70593393646427917782 440 74878248419336668505 441 79418069346309184512 442 84227730407461064325 443 89322956321085210211 444 94720370257356600908 445 100437544171215976692 446 106493051904165376757 447 112906525198122361530 448 119698712782718108802 449 126891542690979320848 450 134508188001568729536 451 142573136155343209925 452 151112262071908925070 453 160152905244545326977 454 169723951046441263749 455 179855916453941490382 456 190581040442635153818 457 201933379285097911413 458 213948907032699514700 459 226665621435797791133 460 240123655613858083217 461 254365395758507091111 462 269435605212820776743 463 285381555241827768559 464 302253162872543082173 465 320103136152959736112 466 338987127249458323685 467 358963893768095767749 468 380095468762986380749 469 402447339861577257432 470 426088638015383977961 471 451092336354827664408 472 477535459707895680137 473 505499305313936194102 474 535069675351070391213 475 566337121865268728763 476 599397204781228111102 477 634350763652713286759 478 671304203894584323584 479 710369798234480754357 480 751666004194926016727 481 795317798414691123316 482 841457028742689431727 483 890222784951793870566 484 941761789114729262599 485 996228806608304975556 486 1053787078861918475601 487 1114608778935889613336 488 1178875491155198931734 489 1246778716000736048753 490 1318520401611196491399 491 1394313503223374075115 492 1474382572038216469484 493 1558964374992830322525 494 1648308547061877471464 495 1742678277743466013891 496 1842351033502086149642 497 1947619317986584322183 498 2058791472040737417915 499 2176192515437139977977 500 2300165032570029027731 501 2431070104304992360580 502 2569288288368508354689 503 2715220650763655378628 504 2869289850793810727453 505 3031941282455823198150 506 3203644275079022200828 507 3384893356227169975157 508 3576209579963794915303 509 3778141924000811798742 510 3991268758889444641564 511 4216199393435920621746 512 4453575699570940946866 513 4704073821002175841550 514 4968405970488126318751 515 5247322318923878792952 516 5541612982013113934085 517 5852110108921301658992 518 6179690078238084803904 519 6525275806549652784019 520 6889839175409542381552 521 7274403582551733373250 522 7680046623716094324361 523 8107902911527474115954 524 8559167038437716719766 525 9035096690829005898817 526 9537015921990239988770 527 10066318591787500073818 528 10624471981512075012539 529 11213020592521695103388 530 11833590138006300400026 531 12487891737367521787268 532 13177726323474524579540 533 13904989273245567302244 534 14671675272840783166939 535 15479883428970761003423 536 16331822638729701428267 537 17229817230617210655063 538 18176312890390861303962 539 19173882885687454353038 540 20225234604409151004077 541 21333216422211708308454 542 22500824915577355641205 543 23731212437346369614067 544 25027695072821279130036 545 26393760995005382951770 546 27833079238879849352919 547 29349508915133986342073 548 30947108885217475036340 549 32630147920163233995364 550 34403115367205050812088 551 36270732348871284997680 552 38237963520943177106482 553 40310029416409244456050 554 42492419404397720610456 555 44790905293907017746987 556 47211555614160397516050 557 49760750604354432233088 558 52445197947746312578831 559 55271949286085136667379 560 58248417552751867787863 561 61382395164161775056352 562 64682073111542942856166 563 68156060996536235647886 564 71813408056839595154994 565 75663625229609054395061 566 79716708303343128424447 567 83983162210640877905169 568 88474026517495815884101 569 93200902166643652090428 570 98175979536033967118084 571 103412067875563706798142 572 108922626189067384567429 573 114721795630860400269883 574 120824433490320547459909 575 127246148840551949785085 576 134003339931725153564705 577 141113233412529912713790 578 148593925468119890132079 579 156464424966082817382524 580 164744698707340387453168 581 173455718882380095964176 582 182619512839056823657743 583 192259215272078129264133 584 202399122950629095318031 585 213064752104884206897985 586 224282898599046830510343 587 236081701023305130421633 588 248490706844586260365282 589 261540941761240641217134 590 275264982414934171109490 591 289697032618827120877820 592 304873003269975365507495 593 320830596120295386086519 594 337609391590065168512359 595 355250940815002701509611 596 373798862128436850612278 597 393298942187883249059892 598 413799241966727828783723 599 435350207840317344075696 600 458004788008144304359318 601 481818554503286358729435 602 506849831053734853093264 603 533159827070679857890379 604 560812778053476521572204 605 589876092712502315686648 606 620420507127059680752920 607 652520246268116078502732 608 686253193233019825831901 609 721701066553229756330904 610 758949605954969707008569 611 798088766967999183909615 612 839212924798226406866491 613 882421087896683260359871 614 927817121679723713461187 615 975509982873756788536896 616 1025613964982134982064686 617 1078248955392079996086181 618 1133540704665979602129446 619 1191621108583631730132929 620 1252628503530795472886477 621 1316707975853817936366129 622 1384011685831426891450015 623 1454699206941558048032812 624 1528937881135168258286159 625 1606903190858354672351155 626 1688779148601189575962297 627 1774758704783877333103557 628 1865044174831202615667672 629 1959847686321528897560631 630 2059391647140527094311751 631 2163909235608484422144696 632 2273644913597837195863408 633 2388854963699932248518254 634 2509808051552031339647079 635 2636785814481962382783619 636 2770083477684417573524209 637 2910010499193691306432102 638 3056891244979231158120650 639 3211065695545979203506916 640 3372890185488482409619483 641 3542738177508596708642338 642 3721001072479541451377325 643 3908089057205582486537862 644 4104431991606013700194966 645 4310480337124871461814804 646 4526706128254173780520010 647 4753603989138067267302657 648 4991692197319220371866256 649 5241513796775816319159412 650 5503637762499727150258519 651 5778660218961559002675004 652 6067205714919484304246389 653 6369928557132709815045777 654 6687514205661440168359346 655 7020680733548749460759573 656 7370180353811425546613563 657 7736801016790889034083708 658 8121368081058512886409905 659 8524746061205131300297798 660 8947840456000332813479393 661 9391599660555044583447213 662 9857016966290401424870984 663 10345132652677367511668068 664 10857036174895938648194687 665 11393868451739000286064331 666 11956824258286445500852269 667 12547154728067493578724839 668 13166169969647255449425951 669 13815241802783448909651728 670 14495806619536376938270554 671 15209368375944215416133124 672 15957501720133631302133621 673 16741855262985451978850019 674 17564154997755650259427196 675 18426207875324210437800832 676 19329905542049511414810728 677 20277228247502764877512176 678 21270248929688765090100809 679 22311137485682880549518564 680 23402165235974892358177086 681 24545709591163085107469285 682 25744258930034131499708960 683 27000417698448800319999433 684 28316911738879831296516556 685 29696593860867277804496457 686 31142449663120060112802667 687 32657603618448918799186930 688 34245325433219728686218988 689 35909036693513349042170263 690 37652317810725762533656319 691 39478915279883795689514467 692 41392749264546866726675688 693 43397921522754943038375067 694 45498723689129702795213994 695 47699645928878027447703813 696 50005385980149860477626707 697 52420858601901549191223074 698 54951205445179607744848160 699 57601805366500809954348088 700 60378285202834473537286835 701 63286531028521031767243686 702 66332699915362721972497046 703 69523232218023550223668672 704 72864864407855341215775521 705 76364642479247406969338050 706 80029935953661656565734966 707 83868452507581852366433990 708 87888253251761884158352967 709 92097768690318501289175629 710 96505815389469697843495502 711 101121613386982294854025238 712 105954804374756131289884765 713 111015470688345108113295858 714 116314155138696524373074941 715 121861881722882938587851278 716 127670177252209281648522793 717 133751093937700983995863557 718 140117232974725476838324796 719 146781769170263852551138049 720 153758476658245881527297729 721 161061755750279477568425898 722 168706660971164629988221389 723 176708930330666271725663839 724 185085015885255746612190419 725 193852115645795752715753925 726 203028206889569985660780403 727 212632080937520071649719580 728 222683379460186024314706489 729 233202632378520643064004233 730 244211297428606705636183693 731 255731801462210864791259701 732 267787583558210321772892229 733 280403140023083869966790236 734 293604071362025281548595374 735 307417131305664214659049131 736 321870277981032622448375845 737 336992727319136467437921367 738 352815008795455956864780196 739 369369023603738655489022619 740 386688105367749940683780463 741 404807083500032850114863147 742 423762349321394150845186657 743 443591925059596732675273038 744 464335535850798482560396456 745 486034684872448270710584472 746 508732731741838105466119107 747 532474974320122370377223983 748 557308734067567631510427342 749 583283445101886809241272579 750 610450747117966907601837217 751 638864582333908373770622784 752 668581296635294277163910252 753 699659745096778284746839139 754 732161402067670816279437934 755 766150476015982122888490077 756 801694029333610853978816359 757 838862103313805790119364781 758 877727848520950307979373474 759 918367660781873182308265751 760 960861323037560797304003896 761 1005292153304074176700029736 762 1051747159001957655849850519 763 1100317197924192799563931385 764 1151097146124113657859250624 765 1204186073016374953500040256 766 1259687423996378249672275678 767 1317709210896221355739090080 768 1378364210608578997366467313 769 1441770172223648126550378093 770 1508050033038752490738049582 771 1577332143815074048889336878 772 1649750503671651735806079606 773 1725445005022910006140121324 774 1804561688982956164491896074 775 1887253011677361609827773804 776 1973678121921532286406901424 777 2064003150743712843867681060 778 2158401513250589964729263341 779 2257054223353982965847544853 780 2360150221898687182160583662 781 2467886718753771981897527366 782 2580469549453004933585532254 783 2698113546994164480166367765 784 2821042929432312216465104918 785 2949491703928193388272353140 786 3083704087940340693018570199 787 3223934948277725160267440494 788 3370450258759473520418725501 789 3523527577258789108155398492 790 3683456542940343404346307384 791 3850539394533563994326636571 792 4025091510519029370404653817 793 4207441972141088280717280654 794 4397934150197476827880205418 795 4596926316595586652793919754 796 4804792281705797514995450879 797 5021922058584382849261760378 798 5248722555182613689350170094 799 5485618295704258476935766322 800 5733052172321422504452717675 801 5991486228508002426811525233 802 6261402475301701333072120879 803 6543303741858946450896896930 804 6837714561722963378438317169 805 7145182096283051986690326389 806 7466277096963606051180250064 807 7801594907743960700915446011 808 8151756509675604512488919135 809 8517409609130970421538203133 810 8899229771588828461902809098 811 9297921602834531195784159854 812 9714219979529959777728550537 813 10148891331187245215413776136 814 10602734975663191220955158699 815 11076584510377034355122706608 816 11571309261543787319994283815 817 12087815793808125625595054843 818 12627049482760689877927526973 819 13189996152918959195844652302 820 13777683783859651786307780226 821 14391184287298069418837421493 822 15031615358023124634057221812 823 15700142401714084440840332151 824 16397980542787591098459950838 825 17126396715550358417057396109 826 17886711842065410769961008155 827 18680303100276877490449246296 828 19508606286081561358163954026 829 20373118273183778131310836577 830 21275399574724765445688392707 831 22217077010838260627884444017 832 23199846486451169343984762514 833 24225475883821531494689394314 834 25295808074486832813084269209 835 26412764055483014097161980473 836 27578346214889968804203617054 837 28794641731961759722317817551 838 30063826117310982372019367216 839 31388166898835484452072776886 840 32770027459303858556283689736 841 34211871031752548278705175589 842 35716264859093977687513095687 843 37285884524590579748727176842 844 38923518460115987806580237814 845 40632072639400673751860864868 846 42414575463747094336643921187 847 44274182847997609941773707686 848 46214183514849300594061976004 849 48238004505931946889391203272 850 50349216918401212177280044219 851 52551541876147039010116127531 852 54848856745079917638857947911 853 57245201602333536236577151893 854 59744785969613964514465517281 855 62351995821331449987392349888 856 65071400878573831542536215443 857 67907762200418949874779124707 858 70866040084540107090550859448 859 73951402289532005955184267672 860 77169232591877674585873575981 861 80525139690988018274460917909 862 84024966476277979224266399857 863 87674799670795146667083924995 864 91480979866491345648990322639 865 95450111966823518214615486154 866 99589076052990565170149788505 867 103905038690755971018947426664 868 108405464695475636366865631771 869 113098129373644577850330731711 870 117991131259998859168670475191 871 123092905369958432774928312404 872 128412236987976529867925206627 873 133958276013169939667383535668 874 139740551884446204475036443704 875 145768989108216487057939805555 876 152053923412691097161900221331 877 158606118553696417423257111404 878 165436783797931931917115351153 879 172557592110602218615911674656 880 179980699075416049551763395544 881 187718762576041099638519462424 882 195784963269243383572359646569 883 204193025881123335504240244229 884 212957241359090878219002865261 885 222092489913497780834047734202 886 231614264984172822785713270889 887 241538698168481624492955439993 888 251882585148964518731100746306 889 262663412660090356120145256727 890 273899386535208029506315084601 891 285609460876378579826348175187 892 297813368391435715025883577859 893 310531651944349233676481559357 894 323785697366761254173685059731 895 337597767580427105226180010362 896 351991038082228660789435341194 897 366989633845435601723737913619 898 382618667692977386826227638767 899 398904280200653395819220963468 900 415873681190459054784047256566 901 433555192876539531087162146613 902 451978294728708525213888783997 903 471173670120985588371916580271 904 491173254835220446432727873072 905 512010287492584845146350194580 906 533719361988531136324126723999 907 556336482009740068071130628552 908 579899117714618242278511046388 909 604446264662056374189451963843 910 630018505076433611629306011983 911 656658071540248718775718604961 912 684408913209287275550075639557 913 713316764648893234122353190295 914 743429217393715213042438746653 915 774795794337240928934279413987 916 807468027061529837514718660851 917 841499536221802614336158305644 918 876946115104959930391690873923 919 913865816485680423484257583102 920 952319042908502961909440764160 921 992368640529229737339476928276 922 1034079996654109332427467944546 923 1077521141120571341393108419236 924 1122762851668802145068020763183 925 1169878763459173895724842802936 926 1218945482896482311362557129219 927 1270042705928112564192660557712 928 1323253340989653981275863314894 929 1378663636778122744607969548658 930 1436363315039845896898284586209 931 1496445708567209282035504745979 932 1559007904605896258839873978826 933 1624150893881942976242673409607 934 1691979725465930503399916132364 935 1762603667699924360125897635941 936 1836136375421380008664561750236 937 1912696063727159213939556113559 938 1992405688530070149959823827004 939 2075393134169954709477126112563 940 2161791408351324312313732653263 941 2251738844689892053410802420660 942 2345379313161090374402054813190 943 2442862438754801545532935354529 944 2544343828652090726770865925843 945 2649985308251720770258543504719 946 2759955166386673475385919920225 947 2874428410083806869890640109208 948 2993587029233173241134419976364 949 3117620271547411926944767314882 950 3246724928206047105872253382770 951 3381105630594468611941568651127 952 3520975158562887897547757933810 953 3666554760646647127887624829454 954 3818074486705953843157188858563 955 3975773533460423034708236081947 956 4139900603411771887540832458971 957 4310714277666637214261267020385 958 4488483403190813122665884093414 959 4673487495046245203691873637222 960 4866017154182911354693191464589 961 5066374501379277964398092677739 962 5274873627947390097984004760057 963 5491841063841846500450748569934 964 5717616263835974099251272766454 965 5952552112453464578848713342498 966 6197015448369619941833514714302 967 6451387609023188709961539976205 968 6716064996207615136988103139710 969 6991459663439386169427269844318 970 7277999925931103886190496636245 971 7576130994027952290686635227993 972 7886315630998429231214373298051 973 8209034836103596418024169016970 974 8544788553903729460672807238014 975 8894096410797147287886995278346 976 9257498479823236816301597951232 977 9635556074800288403751806165069 978 10028852574908795418790367603378 979 10437994280872373856641703141367 980 10863611303931504965523933368142 981 11306358488849924787297948288671 982 11766916372239763961664126036544 983 12245992177539511607697048499580 984 12744320848028628464108620674218 985 13262666119314202551059303868536 986 13801821632778520930804559812608 987 14362612091531863066845390495284 988 14945894460472306340603318078129 989 15552559212113915719421043545012 990 16183531619906475295761712997251 991 16839773100833956877505401587701 992 17522282609145324707601606338654 993 18232098083140097717818352607747 994 18970297947002453464591951679254 995 19738002669751617842028272755700 996 20536376383452971700630154640549 997 21366628562913781584419468841257 998 22230015769169865076550863998611 999 23127843459154899464605566725306 1000 24061467864032622473417271821047