0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 21 9 30 10 41 11 55 12 75 13 99 14 131 15 172 16 223 17 288 18 372 19 474 20 603 21 764 22 962 23 1206 24 1509 25 1876 26 2326 27 2878 28 3543 29 4351 30 5330 31 6506 32 7921 33 9623 34 11655 35 14085 36 16987 37 20434 38 24529 39 29392 40 35138 41 41930 42 49947 43 59381 44 70474 45 83512 46 98779 47 116662 48 137572 49 161979 50 190433 51 223588 52 262123 53 306902 54 358865 55 419077 56 488775 57 569402 58 662501 59 769952 60 893820 61 1036455 62 1200542 63 1389185 64 1605745 65 1854226 66 2139035 67 2465191 68 2838360 69 3265046 70 3752368 71 4308627 72 4943015 73 5665924 74 6489060 75 7425729 76 8490595 77 9700511 78 11074165 79 12632623 80 14399489 81 16401448 82 18667970 83 21232604 84 24132555 85 27409602 86 31110391 87 35287392 88 39998630 89 45309631 90 51293052 91 58030148 92 65611447 93 74138264 94 83722703 95 94490546 96 106581163 97 120149923 98 135369444 99 152432219 100 171551061 101 192963651 102 216932990 103 243751387 104 273742855 105 307267503 106 344723092 107 386552056 108 433243277 109 485338596 110 543437378 111 608203768 112 680370477 113 760749705 114 850237569 115 949824802 116 1060605054 117 1183787083 118 1320702460 119 1472823077 120 1641770192 121 1829332247 122 2037479620 123 2268384985 124 2524438260 125 2808274467 126 3122791414 127 3471178982 128 3856945215 129 4283950047 130 4756432957 131 5279057682 132 5856944927 133 6495720641 134 7201561133 135 7981249055 136 8842222651 137 9792648096 138 10841477627 139 11998529188 140 13274563277 141 14681375537 142 16231882603 143 17940238845 144 19821937788 145 21893942504 146 24174815565 147 26684871005 148 29446321267 149 32483465793 150 35822864213 151 39493549511 152 43527244716 153 47958611636 154 52825498144 155 58169242775 156 64034965586 157 70471915172 158 77533826467 159 85279325791 160 93772341851 161 103082595958 162 113286084867 163 124465642212 164 136711524967 165 150122068599 166 164804363102 167 180875039286 168 198461061134 169 217700630247 170 238744138086 171 261755220904 172 286911860048 173 314407638923 174 344453030262 175 377276845376 176 413127768970 177 452276048002 178 495015267495 179 541664350599 180 592569632472 181 648107169567 182 708685196721 183 774746814922 184 846772835558 185 925284947968 186 1010849034693 187 1104078831958 188 1205639835853 189 1316253557932 190 1436702046435 191 1567832880676 192 1710564431577 193 1865891633540 194 2034892155886 195 2218733103677 196 2418678158132 197 2636095411964 198 2872465662831 199 3129391466042 200 3408606827828 201 3711987699988 202 4041563186926 203 4399527778790 204 4788254345800 205 5210308264407 206 5668462555021 207 6165714235175 208 6705301804746 209 7290724255964 210 7925761313097 211 8614495366307 212 9361334983976 213 10171040266636 214 11048749978097 215 12000010944560 216 13030809409234 217 14147604921104 218 15357366668034 219 16667612592741 220 18086451269838 221 19622627161598 222 21285568937626 223 23085441587204 224 25033202284056 225 27140660450354 226 29420542068612 227 31886559031959 228 34553483236180 229 37437226346935 230 40554925285928 231 43925034037914 232 47567421943604 233 51503479498340 234 55756231425968 235 60350458226332 236 65312826392135 237 70672028106676 238 76458930781389 239 82706737761667 240 89451160103234 241 96730600980149 242 104586353156192 243 113062810639350 244 122207695170137 245 132072299303777 246 142711746217552 247 154185268307687 248 166556505370506 249 179893823933187 250 194270658827183 251 209765879361998 252 226464180618309 253 244456502612413 254 263840478692045 255 284720915357418 256 307210305276651 257 331429376681410 258 357507680282153 259 385584217416727 260 415808111630975 261 448339326807871 262 483349434600034 263 521022435531601 264 561555635856984 265 605160585248096 266 652064078749784 267 702509227452575 268 756756602088440 269 815085455578900 270 877795028070872 271 945205941436318 272 1017661688510424 273 1095530223429016 274 1179205659401319 275 1269110082294930 276 1365695485739755 277 1469445837418303 278 1580879284486664 279 1700550507261536 280 1829053230576332 281 1967022904541414 282 2115139563600104 283 2274130877378746 284 2444775405137324 285 2627906066951394 286 2824413845460065 287 3035251734675371 288 3261438949426002 289 3504065414348988 290 3764296549821001 291 4043378373688071 292 4342642939005340 293 4663514131042322 294 5007513843932485 295 5376268563560322 296 5771516382090515 297 6195114471224671 298 6649047043500641 299 7135433834519738 300 7656539136276796 301 8214781419102199 302 8812743579059889 303 9453183849658433 304 10139047420174310 305 10873478807121397 306 11659835023138174 307 12501699596232422 308 13402897492556186 309 14367510998330944 310 15399896621694588 311 16504703080339958 312 17686890439362567 313 18951750474093597 314 20304928334266916 315 21752445589003034 316 23300724739536803 317 24956615292938439 318 26727421489891977 319 28620931792180922 320 30645450239020344 321 32809829785582005 322 35123507747599675 323 37596543483951783 324 40239658450943157 325 43064278777424339 326 46082580516229166 327 49307537733137559 328 52752973609383928 329 56433614744054460 330 60365148847557311 331 64564286036519753 332 69048823950818460 333 73837716921513047 334 78951149438968988 335 84410614184109280 336 90238994894910105 337 96460654364496316 338 103101527883136292 339 110189222447991234 340 117753122092669817 341 125824499706995250 342 134436635732830105 343 143624944152807053 344 153427106212649371 345 163883212334336162 346 175035912716030640 347 186930577139611062 348 199615464531006051 349 213141902858712224 350 227564479990596891 351 242941246153069691 352 259333928689355212 353 276808159847928454 354 295433718368956655 355 315284785689363538 356 336440217636827438 357 358983832517728176 358 383004716575561669 359 408597547843909752 360 435862939472212558 361 464907803672518318 362 495845737505744543 363 528797431775967786 364 563891104398283367 365 601262959671869362 366 641057674968214130 367 683428916437882399 368 728539885437842216 369 776563897453233288 370 827684995418718894 371 882098599436819871 372 940012195002121764 373 1001646061966061626 374 1067234046614203567 375 1137024379330788168 376 1211280540502761069 377 1290282177444242171 378 1374326075279616138 379 1463727184893576491 380 1558819711246372863 381 1659958265498947022 382 1767519084632372928 383 1881901322425550547 384 2003528415875040744 385 2132849531371901835 386 2270341095212044155 387 2416508413224176924 388 2571887384622964990 389 2737046315445258881 390 2912587837232705677 391 3099150936938638967 392 3297413104396123059 393 3508092603976916217 394 3731950877507569187 395 3969795085856924738 396 4222480797031499350 397 4490914829044102070 398 4776058256312325467 399 5078929588754696769 400 5400608133340985753 401 5742237548336083850 402 6105029601057998575 403 6490268140555695292 404 6899313297283020544 405 7333605922419769903 406 7794672280284534966 407 8284129007952623520 408 8803688356989086676 409 9355163733005724447 410 9940475549663803441 411 10561657414544697032 412 11220862665379928960 413 11920371276055517894 414 12662597152894743692 415 13450095842813211309 416 14285572676180873296 417 15171891368335646775 418 16112083105133752225 419 17109356139193639966 420 18167105924975519897 421 19288925822324121644 422 20478618399785649161 423 21740207370543732118 424 23077950195758540187 425 24496351391840482284 426 26000176580209852623 427 27594467320117213956 428 29284556767379193235 429 31076086203996752853 430 32975022486232646476 431 34987676461119159896 432 37120722404108932751 433 39381218533333848607 434 41776628659020590583 435 44314845029510803129 436 47004212438843829559 437 49853553664132686873 438 52872196304678253120 439 56070001098504880664 440 59457391796165149731 441 63045386675629374094 442 66845631786792974821 443 70870436018597730901 444 75132808086785385703 445 79646495545372407423 446 84426025930551070405 447 89486750151136898407 448 94844888246018484090 449 100517577635137199029 450 106522923997304522351 451 112880054915030615797 452 119609176434102485823 453 126731632693019394493 454 134269968785896782287 455 142247997030690832734 456 150690866823734515895 457 159625138270858254343 458 169078859795543836685 459 179081649934564526955 460 189664783542967008694 461 200861282641412526158 462 212706012151192535830 463 225235780774763470509 464 238489447293314455224 465 252508032566430983012 466 267334837534194304053 467 283015567537142026974 468 299598463286040744752 469 317134438830305202756 470 335677226892238196035 471 355283531952573365109 472 376013191493251338219 473 397929345823707438866 474 421098616939123036630 475 445591296881806842444 476 471481546101446863777 477 498847602334659089908 478 527772000551601972648 479 558341804544818284221 480 590648850765176170808 481 624790005040290692305 482 660867432843693471813 483 698988883816234292803 484 739267991277723616647 485 781824587503631572564 486 826785035581412523772 487 874282578701937581312 488 924457707785472358669 489 977458548386243960690 490 1033441267868381119512 491 1092570503895377282689 492 1155019815328345761746 493 1220972156683114231235 494 1290620377354880236755 495 1364167746878940628442 496 1441828507560976177625 497 1523828455876468016305 498 1610405554109704879432 499 1701810573776068529266 500 1798307772449508390929 501 1900175605697117087052 502 2007707475909222631680 503 2121212519901756805785 504 2241016437262119380566 505 2367462361507499895291 506 2500911776228775361918 507 2641745478499955982706 508 2790364591948200693613 509 2947191631997310500750 510 3112671625923322717105 511 3287273290491095188386 512 3471490270079282316652 513 3665842438343586987590 514 3870877266621011741895 515 4087171262434889964554 516 4315331481627570736704 517 4555997117820988070078 518 4809841173089315850284 519 5077572213917593271154 520 5359936216723012304419 521 5657718507424478317083 522 5971745799767858876351 523 6302888337344703054105 524 6652062144486258331403 525 7020231391466736234820 526 7408410879718576619691 527 7817668653039946898107 528 8249128741068766100057 529 8703974041603234580169 530 9183449348672184900487 531 9688864533593180217912 532 10221597886612133023014 533 10783099627086233252061 534 11374895590561318042254 535 11998591101499894224602 536 12655875040843883166658 537 13348524118039586079359 538 14078407357622900707900 539 14847490810950200697726 540 15657842504175156697024 541 16511637634107822445224 542 17411164024157790354389 543 18358827853150009055275 544 19357159670423310091183 545 20408820711266245268497 546 21516609527424854657499 547 22683468948125383362092 548 23912493387801429155532 549 25206936517490411288718 550 26570219317684073730887 551 28005938531268986141900 552 29517875536090045361754 553 31110005657604915310546 554 32786507943081526156619 555 34551775419814011857486 556 36410425860912715381627 557 38367313083346612878414 558 40427538804098393663185 559 42596465081524746462420 560 44879727370310460960628 561 47283248219753477726354 562 49813251646539774448950 563 52476278214645802065969 564 55279200856561495882283 565 58229241471649096794562 566 61333988339157760991500 567 64601414385188797077359 568 68039896344775428086747 569 71658234862186352250370 570 75465675574606665224347 571 79471931226482500351452 572 83687204864055409772225 573 88122214161945503116687 574 92788216936096631300057 575 97697037899952793384122 576 102861096723418784067786 577 108293437456958722405949 578 114007759386125127245247 579 120018449384873995540518 580 126340615839240386097980 581 132990124216302855975434 582 139983634356884471697624 583 147338639574111224345139 584 155073507643801005717909 585 163207523776672234889179 586 171760935666578582580141 587 180755000713371816783901 588 190212035523604512966854 589 200155467797096023317437 590 210609890712428789039457 591 221601119929701410423908 592 233156253334383967322774 593 245303733651875079277084 594 258073414068391198040456 595 271496627000114323610924 596 285606256159120386891338 597 300436812071490069593958 598 316024511210218393119276 599 332407358913062788266268 600 349625236263350989253987 601 367719991119998032097865 602 386735533491598225109665 603 406717935458446308507498 604 427715535855762538430460 605 449779049941221928348819 606 472961684280176560007406 607 497319257092700827375219 608 522910324317833127723722 609 549796311662117641229843 610 578041652911837409074878 611 607713934801147381339400 612 638884048741732191195029 613 671626349733619162127157 614 706018822791432722830942 615 742143257235667365743963 616 780085429214566171630492 617 819935292838893708590859 618 861787180329367234222382 619 905740011594752821521548 620 951897513677715527555212 621 1000368450525423306578578 622 1051266863562741901486879 623 1104712323567597206055752 624 1160830194370819371497623 625 1219751908926518367287402 626 1281615258323860688786032 627 1346564694337014383039634 628 1414751646137121811832729 629 1486334851818424919391085 630 1561480705420221691608414 631 1640363620157181254075292 632 1723166408602793566508764 633 1810080680604377906206450 634 1901307259743261917757842 635 1997056619190454198944651 636 2097549337846506462874710 637 2203016577694312635667853 638 2313700583335448943702744 639 2429855204724331258580697 640 2551746444160120547401185 641 2679653028643937629747572 642 2813867008758720741662677 643 2954694385281004052190559 644 3102455764788166855433177 645 3257487045581326140689198 646 3420140135303219755273363 647 3590783701692160249309502 648 3769803957977631201259853 649 3957605484490397893179509 650 4154612088130301300959128 651 4361267701408242699872604 652 4578037322855486757899372 653 4805408000673339676276508 654 5043889861579738520260046 655 5294017186896393648882689 656 5556349538011089154674897 657 5831472933444637503907843 658 6120001079851095437872006 659 6422576659383230997436557 660 6739872675963181355812853 661 7072593863110867663176900 662 7421478156100320196627250 663 7787298231336721853618149 664 8170863115975053876899320 665 8573019870934813117292260 666 8994655350604725099600550 667 9436698042676856816543625 668 9900119991701387426052291 669 10385938810111678863339364 670 10895219780634632243245108 671 11429078054173756925102417 672 11988680947432357896391606 673 12575250344731978643883153 674 13190065208677153433664296 675 13834464204521843154573812 676 14509848443306178625712835 677 15217684349054516509699315 678 15959506655557866870453360 679 16736921538505771074764910 680 17551609888985230215095475 681 18405330734627608734179165 682 19299924814959210442077200 683 20237318317797732403319925 684 21219526783835712873856360 685 22248659186863797357798189 686 23326922197411817981157714 687 24456624637924725141133503 688 25640182137944120128441043 689 26880121998134913528265027 690 28179088272381300243253330 691 29539847077577324433109899 692 30965292141155635917579528 693 32458450596834163542234415 694 34022489039515329291288874 695 35660719850746647015420871 696 37376607806646111549468269 697 39173776980711384283111247 698 41056017954469454698522231 699 43027295349483935652463400 700 45091755694821643646196960 701 47253735644689362562155596 702 49517770561586956675791897 703 51888603480985201610942481 704 54371194474227133594110002 705 56970730427071343771446140 706 59692635252045966162224545 707 62542580553564110827564392 708 65526496765566753453918636 709 68650584782308805152028550 710 71921328103789870654862360 711 75345505518254326223071962 712 78930204345147674994698757 713 82682834262918971825393827 714 86611141747104415386597965 715 90723225145216538552246663 716 95027550416098817668740579 717 99532967562588620064373269 718 104248727787564538193757461 719 109184501404739032416287513 720 114350396536896373779228061 721 119756978635671159096576965 722 125415290858416708355342856 723 131336875339227595438331084 724 137533795392759301558364267 725 144018658691132756011048113 726 150804641455925405130355978 727 157905513709036029588440253 728 165335665628071008471397414 729 173110135053837882068360318 730 181244636199551508081143495 731 189755589613461748732294824 732 198660153448803304058152695 733 207976256097251367629847484 734 217722630244445240978866298 735 227918848408619480502489908 736 238585360025963083957735383 737 249743530149015420061179767 738 261415679827207868558890981 739 273625128241576765838718364 740 286396236668711291561907458 741 299754454352163983252618748 742 313726366362847283062603587 743 328339743533371761751178954 744 343623594554856452717024337 745 359608220328464563537018151 746 376325270667795063717057456 747 393807803452298168491659597 748 412090346336087632299177844 749 431208961120901275753356795 750 451201310906520852913513724 751 472106730136710246446228546 752 493966297663675044775001467 753 516822912959194342348749182 754 540721375605935988933107266 755 565708468208047498797394268 756 591833042865925899708803007 757 619146111366119910111802866 758 647700939243617030720927181 759 677553143880326036928311470 760 708760796810393092837307161 761 741384530410097507057823299 762 775487649157472921554790419 763 811136245654502863460965076 764 848399321612758740453724057 765 887348914011695763597184769 766 928060226647511901735313837 767 970611767299519858570955721 768 1015085490750397169420941907 769 1061566947906479316494532744 770 1110145441274461167351331385 771 1160914187061488610025974588 772 1213970484176672511512421238 773 1269415890423557676413639692 774 1327356406185049106995923141 775 1387902665914754928955515077 776 1451170137761669859502044428 777 1517279331668614801295245456 778 1586356016298889034667717020 779 1658531445160202660198934640 780 1733942592310161995621605895 781 1812732398043402817934497376 782 1895050024976930829184173531 783 1981051124967360533817978397 784 2070898117311570438994400479 785 2164760478700840903975487868 786 2262815045417840682701675132 787 2365246328285908654493296657 788 2472246840900970061404269277 789 2584017441698163430323664661 790 2700767690427869877030308288 791 2822716219639364583824964012 792 2950091121794788090478816675 793 3083130352661599826436248820 794 3222082151658167806771482415 795 3367205479854706632820297628 796 3518770476360444321391030182 797 3677058933857719930564085347 798 3842364794074735122703843805 799 4014994664020950640697932477 800 4195268353842683132362787213 801 4383519437191369356333978414 802 4580095835033278032319547744 803 4785360423867218643763445109 804 4999691669356079922920708884 805 5223484286418887721254248474 806 5457149926872565234021599122 807 5701117895756771804333544579 808 5955835897521158114583994902 809 6221770813302173840871580674 810 6499409510566272260286717838 811 6789259686448049392095514895 812 7091850746165611779372686448 813 7407734717951367211123015360 814 7737487205994562216177967669 815 8081708382952335171568422654 816 8441024023648906477536778192 817 8816086581647881239883451465 818 9207576310450594080933786264 819 9616202431144081034732046692 820 10042704348395727331886924302 821 10487852916768020680083347777 822 10952451759406252861621021596 823 11437338641234575994825367524 824 11943386898881657554269432224 825 12471506929646417139325932575 826 13022647741907102514004405425 827 13597798569473408971257307139 828 14197990552481609263989403321 829 14824298487536889272139881548 830 15477842649915432545919175703 831 16159790690751424296406906090 832 16871359612251220702469707422 833 17613817824098623871699752776 834 18388487284341697590381901680 835 19196745728183039956039904363 836 20040028988232090651661097089 837 20919833409920093046514714902 838 21837718365925965269280552922 839 22795308873614774903009308938 840 23794298319649985745540486682 841 24836451296106385183634439142 842 25923606552582850708539122379 843 27057680068993124792257669122 844 28240668253898802422317207196 845 29474651273442064680722365100 846 30761796516136598513729094786 847 32104362198983919230634019148 848 33504701120599263052107122751 849 34965264567256656458997226035 850 36488606377997026857261101246 851 38077387175186632995039894476 852 39734378767166018322372623115 853 41462468729892491592185240294 854 43264665174752197573871068689 855 45144101710001550190584613463 856 47104042603592572707674925728 857 49147888155442947716081379349 858 51279180287529766801112580245 859 53501608360516543237125222044 860 55819015225966487112375762304 861 58235403523551833070545662713 862 60754942233039670970325395610 863 63381973491219788256422061274 864 66121019684340043287680795377 865 68976790827030322921296059265 866 71954192239127790244657650895 867 75058332532264514591508383947 868 78294531918544338298606261803 869 81668330854119634337257396035 870 85185499030981137013623743646 871 88852044730795998473879600467 872 92674224555171379444966652549 873 96658553547283991801526636533 874 100811815720400874702234883170 875 105141075009424131145695944446 876 109653686662223239950778594996 877 114357309088173780810191534391 878 119259916182001893731003762061 879 124369810141740497850343401584 880 129695634800337217777183228268 881 135246389491216139159039707685 882 141031443468887014003234331252 883 147060550906517472455423358381 884 153343866493237326474415401427 885 159891961654830368298135567688 886 166715841422389418383359364021 887 173826961974466049388647027910 888 181237248879238744213762144118 889 188959116064253623452991215665 890 197005485542361740358128512726 891 205389807923587780504421906251 892 214126083743818370285140104440 893 223228885642395695663993595496 894 232713381421945428454909806144 895 242595358025058778911066827273 896 252891246463788633236275823328 897 263618147739311049976532088105 898 274793859790547811446459862013 899 286436905512045251383911302284 900 298566561882961284237909688321 901 311202890250628595181925120519 902 324366767813839544212242461904 903 338079920352739804406850392119 904 352364956254025496411506129664 905 367245401882015082872184176400 906 382745738348115130712302932543 907 398891439733220911291082284845 908 415709012819691463730157330109 909 433226038391717071054930132553 910 451471214165158079965710424021 911 470474399410280723295714457326 912 490266661333251290631026701040 913 510880323284777963866105932228 914 532349014866913340465219053810 915 554707724011753683404835446352 916 577992851108596975986469202949 917 602242265259054763362143404693 918 627495362742656520536361205146 919 653793127778644032735646513805 920 681178195672931294334479537074 921 709694918442607169375649985491 922 739389433013888121356361447859 923 770309732093091484527180735473 924 802505737814000968008480225351 925 836029378268940491453806034973 926 870934667034965368424028772307 927 907277785810826797096160962525 928 945117170284772311200878398314 929 984513599357817211859322710363 930 1025530287851866192228314561578 931 1068232982836986753400685026194 932 1112690063717243195564375189893 933 1158972646219798797954901878301 934 1207154690437491375341574779760 935 1257313113080791068733910157052 936 1309527904100966620610767262021 937 1363882247852425403812169933421 938 1420462648968561308202242114115 939 1479359063132051729264763117259 940 1540665032927399151763096961785 941 1604477828970623294784451123871 942 1670898596518385936634266829828 943 1740032507766482166801224664853 944 1811988920055569068803569775492 945 1886881540210236243694532479789 946 1964828595246063048624974418266 947 2045953009688166244315883616866 948 2130382589753930633497043703640 949 2218250214662146367863776645214 950 2309694035340662478906386376639 951 2404857680814919881218020921326 952 2503890472570362116194269557634 953 2606947647192752439969763695397 954 2714190587601866016688440422163 955 2825787063205890986762846841373 956 2941911479316177608288401069167 957 3062745136174736653134217323768 958 3188476497960123500268531713757 959 3319301472151070225090078640578 960 3455423699641462385181494569009 961 3597054856015018749455692034896 962 3744414964403340173157481601652 963 3897732720366868148942240672852 964 4057245829254754951510886564856 965 4223201356516717163208211360689 966 4395856091457644922460581159895 967 4575476924944093479519471258877 968 4762341241590815397831618718201 969 4956737326975225690570144226694 970 5158964790448153907668342734131 971 5369335004130453176179373196918 972 5588171558707033891181985621164 973 5815810736652697590223361736391 974 6052602003547793966230177995199 975 6298908518166241490835416475608 976 6555107662043871337843072912468 977 6821591589261407944527756267139 978 7098767797203721534834832045015 979 7387059719085313381164777733124 980 7686907339061359873141224114043 981 7998767830774084276674202758978 982 8323116220215784438336795126274 983 8660446073822561038901298332911 984 9011270212746706195929617901572 985 9376121454290869631403716021160 986 9755553381523564162804516773509 987 10150141142133350465807652746501 988 10560482277618201074820926006158 989 10987197583947135324701323768059 990 11430932004873292066522672306386 991 11892355559121219035806346378786 992 12372164302716362124677234851783 993 12871081327771591908623427368725 994 13389857799094168043719242310756 995 13929274030026876127596230753400 996 14490140598989240044546717571951 997 15073299508238781705964163587808 998 15679625386428337789089228954481 999 16310026736593520350983787226243 1000 16965447231264598340990362164213