1 0 2 1 3 1 4 3 5 2 6 7 7 5 8 12 9 13 10 22 11 22 12 43 13 43 14 67 15 81 16 117 17 133 18 195 19 223 20 312 21 373 22 492 23 584 24 782 25 925 26 1190 27 1433 28 1820 29 2170 30 2748 31 3268 32 4075 33 4872 34 5997 35 7150 36 8781 37 10420 38 12669 39 15055 40 18198 41 21535 42 25925 43 30602 44 36624 45 43201 46 51428 47 60478 48 71802 49 84215 50 99537 51 116572 52 137282 53 160361 54 188326 55 219502 56 256953 57 298953 58 348914 59 405058 60 471679 61 546431 62 634585 63 733929 64 850311 65 981486 66 1134748 67 1307384 68 1508262 69 1734869 70 1997354 71 2293426 72 2635633 73 3021274 74 3465544 75 3966603 76 4541896 77 5190371 78 5933484 79 6770437 80 7727231 81 8804743 82 10033354 83 11416207 84 12990370 85 14760517 86 16771490 87 19032118 88 21595193 89 24474249 90 27733716 91 31391865 92 35526555 93 40164415 94 45397768 95 51263574 96 57873988 97 65276785 98 73607684 99 82931299 100 93409339 101 105126633 102 118279487 103 132975909 104 149453007 105 167851020 106 188453454 107 211440123 108 237154419 109 265821474 110 297856062 111 333544191 112 373382834 113 417731670 114 467191521 115 522209102 116 583508778 117 651648981 118 727498539 119 811751548 120 905456278 121 1009466814 122 1125045665 123 1253249308 124 1395591479 125 1553372432 126 1728414814 127 1922308935 128 2137245854 129 2375174800 130 2638721387 131 2930267304 132 3252966967 133 3609716094 134 4004299255 135 4440242470 136 4922074644 137 5454076888 138 6041678376 139 6690059017 140 7405718901 141 8194927825 142 9065452554 143 10024867197 144 11082460032 145 12247354032 146 13530645332 147 14943324216 148 16498624123 149 18209759964 150 20092521528 151 22162763988 152 24439307793 153 26941170545 154 29690753364 155 32710833525 156 36028075871 157 39669709069 158 43667444249 159 48053818427 160 52866496966 161 58144307113 162 63931980052 163 70275779505 164 77228780212 165 84846074777 166 93190569366 167 102327794696 168 112332286027 169 123281883820 170 135264828724 171 148373528183 172 162712344094 173 178390859362 174 195532450724 175 214266918603 176 234740001709 177 257105345409 178 281534948933 179 308210508919 180 337334915661 181 369122811719 182 403813344384 183 441659909288 184 482944151722 185 527964947984 186 577053815588 187 630562943494 188 688882266318 189 752426513963 190 821653972102 191 897052614562 192 979160754185 193 1068552044194 194 1165858354571 195 1271753616545 196 1386978965894 197 1512325521872 198 1648662081271 199 1796916586139 200 1958106792710 201 2133320415583 202 2323748872926 203 2530666231002 204 2755466390648 205 2999640574172 206 3264818514818 207 3552744494998 208 3865322703559 209 4204592006186 210 4572775983486 211 4972256159708 212 5405627444110 213 5875669880498 214 6385409778932 215 6938090251501 216 7537238713946 217 8186635954265 218 8890390975912 219 9652908736014 220 10478972775808 221 11373712027181 222 12342692182557 223 13391881364809 224 14527751508617 225 15757243178948 226 17087877676254 227 18527721597471 228 20085510957902 229 21770615410319 230 23593176121945 231 25564070150126 232 27695063140560 233 29998774765742 234 32488848060196 235 35179916052928 236 38087790069374 237 41229428419389 238 44623145300658 239 48288582895442 240 52246943392773 241 56520965006307 242 61135180328777 243 66115897673975 244 71491488169709 245 77292374484315 246 83551350214427 247 90303577118003 248 97586941194034 249 105442060669361 250 113912682378505 251 123045703583134 252 132891613632872 253 143504531730592 254 154942699997780 255 167268540704223 256 180549206006892 257 194856659272751 258 210268288572354 259 226867015711760 260 244741981988591 261 263988690370518 262 284709771278297 263 307015164798413 264 331022976483227 265 356859705556114 266 384661202682637 267 414572952437714 268 446751144330358 269 481363019771414 270 518588070597847 271 558618459974088 272 601660365179808 273 647934484933060 274 697677542881413 275 751142896475143 276 808602221365389 277 870346236485013 278 936686593048239 279 1007956734473819 280 1084514013758973 281 1166740710519854 282 1255046405560409 283 1349869177360446 284 1451678267253864 285 1560975483041837 286 1678298189167095 287 1804220950072741 288 1939358886345129 289 2084369591429864 290 2239956901115336 291 2406873124346292 292 2585923275507317 293 2777967666964447 294 2983926662536362 295 3204783681780476 296 3441590541668030 297 3695470932317549 298 3967626417992685 299 4259340453469194 300 4571985127373069 301 4907025792988333 302 5266028648970627 303 5650666071546165 304 6062725134400743 305 6504113742487184 306 6976870209192674 307 7483170299803315 308 8025338000488655 309 8605853597511002 310 9227365783634737 311 9892700917598193 312 10604876635582557 313 11367112448190099 314 12182845047545310 315 13055740423768999 316 13989711075202147 317 14988929852158732 318 16057849308145973 319 17201217498341103 320 18424099741316965 321 19731896633905407 322 21130368518696494 323 22625656012916833 324 24224307518466516 325 25933302592329032 326 27760082880092314 327 29712578702610302 328 31799243831925630 329 34029085719225142 330 36411704589511229 331 38957327780204768 332 41676853692059264 333 44581890773252397 334 47684806919831106 335 50998773710349117 336 54537821928106843 337 58316891716391832 338 62351894980103604 339 66659772222301042 340 71258562663272220 341 76167468617220065 342 81406934276231326 343 86998718580004131 344 92965983730436723 345 99333377633149901 346 106127133324214683 347 113375162198914445 348 121107165683042281 349 129354740599531489 350 138151504581432498 351 147533215101413613 352 157537910288123737 353 168206043334119846 354 179580640586303134 355 191707453240408929 356 204635134804422663 357 218415412229574682 358 233103285079168262 359 248757218510885437 360 265439366771965279 361 283215790720595305 362 302156708585230961 363 322336741047620064 364 343835192532621717 365 366736327243463707 366 391129684647445982 367 417110390238499457 368 444779509322556198 369 474244396745816598 370 505619093544993811 371 539024720389859283 372 574589922213879599 373 612451310659147680 374 652753962409737769 375 695651916567313857 376 741308733053750816 377 789898051552094203 378 841604217104470114 379 896622908006605363 380 955161836564589801 381 1017441454214971381 382 1083695736301468370 383 1154172973668616061 384 1229136651365052509 385 1308866337007928850 386 1393658664474930150 387 1483828330554498742 388 1579709195933907985 389 1681655402996838736 390 1790042607853835448 391 1905269233604374344 392 2027757848746249196 393 2157956571895511328 394 2296340613635150767 395 2443413850540218285 396 2599710549502378445 397 2765797130921410076 398 2942274096728776977 399 3129778004909553574 400 3328983624826653552 401 3540606147785843449 402 3765403595973970123 403 4004179296557777868 404 4257784573549161927 405 4527121516087939244 406 4813145985822468034 407 5116870713523118655 408 5439368658280125882 409 5781776470417472561 410 6145298242920219100 411 6531209382945229131 412 6940860800387776828 413 7375683235075083081 414 7837191932461522685 415 8326991478838518977 416 8846781019768374625 417 9398359661560295500 418 9983632294217210812 419 10604615623975709781 420 11263444669475204518 421 11962379497347014063 422 12703812467990535035 423 13490275754272194502 424 14324449421721566506 425 15209169819338400676 426 16147438588477163936 427 17142432024582482609 428 18197511119491635321 429 19316232003924072545 430 20502357139434256758 431 21759866963657591941 432 23092972361014897052 433 24506127646113094238 434 26004044456539293962 435 27591706224787007101 436 29274383652143113616 437 31057650836072783711 438 32947402501692044183 439 34949871969777343534 440 37071650341656709941 441 39319706513346921341 442 41701408530992702240 443 44224545879123111065 444 46897353247496003373 445 49728535346235059771 446 52727293351170221355 447 55903352526194117554 448 59266991643084701486 449 62829073721905287115 450 66601078753439414953 451 70595137902045765264 452 74824069894357534248 453 79301419066339794661 454 84041495821045339148 455 89059418942878708837 456 94371160570672877649 457 99993593247626940387 458 105944539903994920480 459 112242826161630212900 460 118908335873497859239 461 125962069257503197314 462 133426204598744586688 463 141324162848732833096 464 149680676161127652001 465 158521859660561518625 466 167875287554038693586 467 177770072848774544825 468 188236951860585799718 469 199308372743020130823 470 211018589301436208216 471 223403759287467448170 472 236502048523755900984 473 250353740019075229102 474 265001349515237187301 475 280489746589790468943 476 296866282854184972752 477 314180926334426066062 478 332486403679103857893 479 351838349244581298470 480 372295462814721895370 481 393919674967228608544 482 416776321964867235354 483 440934329145421106211 484 466466404818194402215 485 493449243602925100330 486 521963741357588375846 487 552095220593021720667 488 583933668669966696136 489 617573987638611839121 490 653116258176172993522 491 690666016445741670642 492 730334546503332813997 493 772239187040386084927 494 816503655273096177359 495 863258386730845002183 496 912640893953148056583 497 964796142814524177659 498 1019876949699160954713 499 1078044398214016540651 500 1139468278891040987096 501 1204327550538744628370 502 1272810826939721291552 503 1345116887529678894332 504 1421455216018724576657 505 1502046565569651513529 506 1587123554778664827697 507 1676931293056807017482 508 1771728039963821061963 509 1871785897082272701866 510 1977391537313032241731 511 2088846970175885765913 512 2206470348351651965796 513 2330596814052637352574 514 2461579390840442152874 515 2599789919490289281231 516 2745620043932797168591 517 2899482245894635815800 518 3061810934713663176260 519 3233063590983269798070 520 3413721970980937484924 521 3604293370582784961468 522 3805311956135756054138 523 4017340161051094497260 524 4240970156148962569757 525 4476825392596157605430 526 4725562226069176418779 527 4987871621082790487982 528 5264480944766258974794 529 5556155849147112892846 530 5863702251927336370484 531 6187968414955506487303 532 6529847131138770786576 533 6890278019170127033123 534 7270249937634598528374 535 7670803518072402940829 536 8093033829449728504308 537 8538093173851813912968 538 9007194026807969653131 539 9501612122339438459244 540 10022689697176394561895 541 10571838894554329665556 542 11150545343158727286062 543 11760371911995243345136 544 12402962657969063315287 545 13080046967372487531403 546 13793443909378702399560 547 14545066803222477250175 548 15336928018589972994454 549 16171144011446082097659 550 17049940616363873549617 551 17975658598207538528291 552 18950759485903549491943 553 19977831691856645419011 554 21059596941556366554811 555 22198917017726534928715 556 23398800845526108034638 557 24662411924052156097671 558 25993076132780280449156 559 27394289919203663985589 560 28869728898613729176412 561 30423256873417362495248 562 32058935305436310180752 563 33781033249856281815863 564 35594037786985230252103 565 37502664961912680773197 566 39511871271175678958745 567 41626865708114380094481 568 43853122409219800040606 569 46196393914934735050933 570 48662725090679311544544 571 51258467723544439858981 572 53990295844192247161517 573 56865221791613406559267 574 59890613074371049661741 575 63074210048438078898629 576 66424144469698645125323 577 69948958943951156147464 578 73657627337309083462340 579 77559576172867796515549 580 81664707081775366608243 581 85983420337940250883347 582 90526639550207291497054 583 95305837544964597506632 584 100333063519201360500217 585 105620971501109093211030 586 111182850204971435999649 587 117032654322008550577481 588 123185037341229049373193 589 129655385947013965452543 590 136459856095431520239970 591 143615410821597134208763 592 151139859888715054131976 593 159051901337293556346164 594 167371165054559416648119 595 176118258429383299726566 596 185314814222953481585772 597 194983540728032565482718 598 205148274358138615598133 599 215834034747784289977291 600 227067082517189242834948 601 238874979791746118658333 602 251286653642789568120638 603 264332462550023282217007 604 278044266066439613652886 605 292455497797183330735295 606 307601241888730489681119 607 323518313152046741090266 608 340245341032999637938679 609 357822857567123030449249 610 376293389550396329839836 611 395701555077912942816220 612 416094164702103146138381 613 437520327378627871794380 614 460031561473373915257111 615 483681911016511837828563 616 508528067500727110661081 617 534629497429190185067914 618 562048575936138267796000 619 590850726707159724731197 620 621104568550088657540617 621 652882068867224631409629 622 686258704410288935105368 623 721313629594757946254190 624 758129852788173900768402 625 796794420877510801139918 626 837398612566313770717125 627 880038140737869608110638 628 924813364374427762493885 629 971829510402914039459307 630 1021196905999918554819564 631 1073031221763862327529527 632 1127453726333660563127113 633 1184591552902826726697453 634 1244577978258973646605361 635 1307552714842610542847661 636 1373662216510290801426392 637 1443059998545233506079861 638 1515906972660433584450186 639 1592371797591265690490742 640 1672631246087840147062167 641 1756870588963091094957002 642 1845283997077843782237997 643 1938074961983367862036808 644 2035456736179911463054598 645 2137652793782304019138212 646 2244897312635172946933488 647 2357435678746057666279517 648 2475525014170412660658730 649 2599434729301186274757843 650 2729447100796468564494839 651 2865857876190154947126558 652 3008976906527374401387197 653 3159128808170466385935502 654 3316653655235027454867628 655 3481907703911992547310592 656 3655264150263404757856525 657 3837113922868199991024073 658 4027866512045051726067363 659 4227950837160070517018221 660 4437816153898033067790455 661 4657933003148498212634876 662 4888794203550432844439880 663 5130915889503440605767607 664 5384838596868636101587169 665 5651128398338355325280405 666 5930378090892892933128315 667 6223208437510189011016365 668 6530269465758914705690623 669 6852241825644632542664262 670 7189838209570329258566072 671 7543804837003297905242747 672 7914923006960715979724443 673 8304010721148380378057477 674 8711924381137963940263147 675 9139560562681703772021982 676 9587857870846768486922497 677 10057798879356586562684926 678 10550412158144192592621268 679 11066774392819268564910751 680 11608012600404934857521940 681 12175306445388673309099875 682 12769890660825050001649476 683 13393057578908142867049582 684 14046159776166209572490921 685 14730612838103535516480853 686 15447898248893008770540480 687 16199566411387840748351992 688 16987239803546239046064387 689 17812616277020583457569367 690 18677472504537794747237630 691 19583667582348685282511285 692 20533146794952176127324997 693 21527945548945268796229789 694 22570193483834131624254017 695 23662118767281252618218429 696 24806052583308086636340691 697 26004433821607596436833705 698 27259813977229482111875553 699 28574862269532133890681473 700 29952370990471836600091465 701 31395261091928327009664159 702 32906588023014837853704080 703 34489547827947877728999201 704 36147483516378358943331000 705 37883891717712691431546331 706 39702429632361273389916080 707 41606922292480279557683364 708 43601370146269357834702011 709 45689956979519550252534686 710 47877058189696237243806625 711 50167249427478806661919457 712 52565315622369289141965435 713 55076260408626553708944190 714 57705315969579950496092650 715 60457953318030605288754240 716 63339893032359837646076524 717 66357116467631234136546527 718 69515877463005878200941980 719 72822714566473189841565665 720 76284463800062746449767798 721 79908271988404797886107959 722 83701610675808946653368398 723 87672290656756044609985083 724 91828477147148478686161781 725 96178705623417165906619136 726 100731898359192233479761265 727 105497381689029860915932048 728 110484904031465918721778305 729 115704654703490145455359707 730 121167283561494020101721225 731 126883921503612067566164905 732 132866201871529575519880588 733 139126282789746221073734052 734 145676870483645722409689289 735 152531243617695171737346981 736 159703278698680232386605760 737 167207476588920813672440729 738 175058990178231825468216872 739 183273653263505581352439952 740 191868010688866637631318941 741 200859349799544812413023141 742 210265733266958571861871922 743 220106033342789376948800490 744 230399967604465523257238790 745 241168136254867328742390488 746 252432061044015737882000429 747 264214225881017168163770913 748 276538119209822221728492314 749 289428278222997879610552735 750 302910334993356086890479127 751 317011064604069970446441842 752 331758435363936494781474215 753 347181661195395499894310048 754 363311256289354592990381213 755 380179092122001410106472820 756 397818456935665954970935941 757 416264117787128444521963791 758 435552385274122964112654667 759 455721181052342169831704128 760 476810108263111239742776757 761 498860524993700036123656923 762 521915620900650421692458436 763 546020497128568015428761817 764 571222249665820479905760233 765 597570056280956381358238339 766 625115267193279090415426441 767 653911499633712412945475409 768 684014736462388637913075063 769 715483429012455588838244824 770 748378604340616370133800401 771 782763977068381392010693780 772 818706066009805738885373697 773 856274315785390496917042623 774 895541223634453737170861700 775 936582471642665221619936065 776 979477064614961266838735955 777 1024307473828974272613269459 778 1071159786918595430457520168 779 1120123864142788028655401686 780 1171293501310285725171989830 781 1224766599636945469285996950 782 1280645342829151520895732908 783 1339036381693499057543079693 784 1400051026590805140673731920 785 1463805448060089282719905665 786 1530420885957266555226197956 787 1600023867461724430037638447 788 1672746434324432492619914124 789 1748726379740573592021617728 790 1828107495251643310927355141 791 1911039828092299422898765830 792 1997679949420792586195936213 793 2088191233883231022982055497 794 2182744150987192303975367338 795 2281516568772802601285516847 796 2384694070296503573270903000 797 2492470283456627635617608567 798 2605047224718979967551405621 799 2722635657315936227132632165 800 2845455464523769466053148659 801 2973736038639766803996837728 802 3107716686314188380826269947 803 3247647050910641846837562710 804 3393787552604397737474294724 805 3546409846948514204177084928 806 3705797302676237894704313825 807 3872245499530474299681871140 808 4046062746952565781795029296 809 4227570624487100070533873148 810 4417104544803979042961283533 811 4615014340265809362906820114 812 4821664874016478022194474923 813 5037436676596159452632199112 814 5262726609139346860810051354 815 5497948554244657779628921116 816 5743534135660323431573542824 817 5999933467964442679725452224 818 6267615937478344534864500911 819 6547071015689847941034056318 820 6838809106526886528618013612 821 7143362428863965657648797080 822 7461285935712349778575939068 823 7793158271590736974876448656 824 8139582769646721976466527720 825 8501188490149396005211130876 826 8878631302052479669890453663 827 9272595009381976567759094310 828 9683792524287305958334014508 829 10112967088654393764736836436 830 10560893546270546575610989120 831 11028379667595799830861047816 832 11516267529293637968046517183 833 12025434950744646621666580570 834 12556796989872248303597928051 835 13111307500686617669656902856 836 13689960755066412551128514278 837 14293793131381709593682558703 838 14923884872683629334854325278 839 15581361917277264479861636788 840 16267397804625830524964362880 841 16983215659633076996430553151 842 17730090258492216228070201370 843 18509350179397398878345632441 844 19322380041565655029750737810 845 20170622836134361558572229840 846 21055582352662672588707907470 847 21978825705092634894108549984 848 22941985961201450982889446783 849 23946764879714615989362757977 850 24994935759438705512898800120 851 26088346404922735311758703164 852 27228922213360392367464349187 853 28418669387608434697293101482 854 29659678280415359108693104697 855 30954126875131338798915577687 856 32304284408405837013102638117 857 33712515140571244961133544177 858 35181282279664168086877507858 859 36713152065244190180784898496 860 38310798018442458705813189513 861 39977005364898224057188876984 862 41714675637534687965234900030 863 43526831466370314675173802053 864 45416621562877272141993961218 865 47387325906664015250852827650 866 49442361142598531406552372065 867 51585286196776317771096399925 868 53819808120102495865904335114 869 56149788168569010769912190725 870 58579248129700999378022426837 871 61112376904983874794620729418 872 63753537358505735320675957469 873 66507273442415169295276493692 874 69378317610249797426715051913 875 72371598529586599313257159132 876 75492249105955008448001768800 877 78745614830382124268849103548 878 82137262463466640213157358268 879 85672989069341715085821220251 880 89358831413454424705288769018 881 93201075738591131326182964286 882 97206267934188739389109606465 883 101381224114514605058715038299 884 105733041621955014480833260459 885 110269110472239303549439913740 886 114997125259133900617723222950 887 119925097536775604192898077485 888 125061368698574490390837676936 889 130414623372303533854589562496 890 135993903351811084933842792973 891 141808622086534770813071603267 892 147868579750876836324916004090 893 154183978916303493981405531374 894 160765440849979435592516542501 895 167624022464616071921540504918 896 174771233945232889616900813405 897 182219057079468684061508361450 898 189979964319177980137167331365 899 198066938602060764988534131941 900 206493493963255845283884069407 901 215273696967922304735070356698 902 224422188997105711638289632444 903 233954209420367601599400951832 904 243885619690025749222366517595 905 254232928393129178869654927575 906 265013317298765010628199399117 907 276244668439672607313889262739 908 287945592268725687983688578306 909 300135456932331311485398439854 910 312834418704500376732245844036 911 326063453626950933982297238047 912 339844390402441015417004549449 913 354199944590261942282886291755 914 369153754154797964351043148123 915 384730416419929828563957161138 916 400955526484184806604772263699 917 417855717153555587888583463636 918 435458700451196752046268012191 919 453793310765386998848188774185 920 472889549699605186768306125584 921 492778632690919601594589694316 922 513493037465536419016302256611 923 535066554402889854988578830539 924 557534338882503792705887220514 925 580932965690590620476710218794 926 605300485566416199412299371054 927 630676483971410573455663287592 928 657102142167299376159407999768 929 684620300692712821418226013561 930 713275525331274145686335749831 931 743114175667600275512773954991 932 774184476331460899110153501336 933 806536591034041069717035585728 934 840222699504354483969315762446 935 875297077437842075314897021466 936 911816179573602876949511193031 937 949838726021002199161961646327 938 989425791961148082853068181317 939 1030640900853359374891200039226 940 1073550121281853326173401572439 941 1118222167582872768952534162278 942 1164728504397963018506633322632 943 1213143455304487958270132772402 944 1263544315680379282145670316085 945 1316011469965908774919549226915 946 1370628513491623488045941171383 947 1427482379047827804665193578583 948 1486663468377825160691104206593 949 1548265788783858552928830063931 950 1612387095042032339678824867636 951 1679129036829742963830662105408 952 1748597311877042658535811445651 953 1820901825061163336836159565978 954 1896156853671918648435644686591 955 1974481219084105522735697124716 956 2055998465082155999213602462882 957 2140837043091338989622373474518 958 2229130504579627420376700901569 959 2321017700904089234362402601931 960 2416642990886213990222679087862 961 2516156456411076307263268094651 962 2619714126356583020760597107030 963 2727478209170343068319308483921 964 2839617334423896047795574235698 965 2956306803686190516176538203127 966 3077728851071314602951041088028 967 3204072913828564402889375064158 968 3335535913357029636443587670133 969 3472322547040956295866567880291 970 3614645591317295462245800526064 971 3762726216401999761215518476594 972 3916794313117912111503705814526 973 4077088832283395979743200339878 974 4243858137138357278226062393188 975 4417360369301851011500742375211 976 4597863828774274611216322235822 977 4785647368516023752729330408157 978 4981000804154699964428961904694 979 5184225339393263354125921809461 980 5395634007713245833072472574184 981 5615552130988980956305318443940 982 5844317795652148538303535002510 983 6082282347069424053956294095519 984 6329810902821104441762649750893 985 6587282885593847664307430623447 986 6855092576427612865243105918592 987 7133649689084059352418476117560 988 7423379966332617663448119326189 989 7724725798979664422018642992058 990 8038146868497340954486506987896 991 8364120814139972896392113557473 992 8703143925469467959075275114802 993 9055731861244847922052827397055 994 9422420395666972504164593796537 995 9803766193005828007815072117278 996 10200347611676319181327260937847 997 10612765538867541777134453485616 998 11041644256871938354002204034439 999 11487632342302703790116114936846 1000 11951403599432301306839759232310