4 1 5 1 6 2 7 3 8 5 9 4 10 7 11 9 12 11 13 15 14 18 15 23 16 34 17 46 18 54 19 79 20 93 21 130 22 158 23 214 24 253 25 331 26 394 27 510 28 596 29 767 30 900 31 1129 32 1329 33 1649 34 1951 35 2371 36 2831 37 3438 38 4095 39 4917 40 5847 41 6998 42 8361 43 9908 44 11819 45 13950 46 16662 47 19531 48 23241 49 27170 50 32289 51 37586 52 44470 53 51651 54 60958 55 70565 56 82998 57 95905 58 112489 59 129607 60 151438 61 174340 62 203173 63 233333 64 271143 65 311190 66 360400 67 413221 68 477315 69 546520 70 629823 71 720434 72 827951 73 946466 74 1085473 75 1239198 76 1418183 77 1617492 78 1847171 79 2105169 80 2399519 81 2731235 82 3107698 83 3533972 84 4013610 85 4559534 86 5170124 87 5866417 88 6642114 89 7528292 90 8510733 91 9635793 92 10879040 93 12301794 94 13870646 95 15667621 96 17643423 97 19906182 98 22390340 99 25232978 100 28351418 101 31913843 102 35818252 103 40275938 104 45158491 105 50721194 106 56814544 107 63745455 108 71338310 109 79954821 110 89397804 111 100094218 112 111821158 113 125071294 114 139607513 115 155998915 116 173991715 117 194229740 118 216461243 119 241416759 120 268846273 121 299563658 122 333349960 123 371111469 124 412668494 125 459011404 126 510045546 127 566849760 128 629434561 129 698957528 130 775587358 131 860569082 132 954274949 133 1058001831 134 1172413389 135 1298873428 136 1438385008 137 1592348417 138 1762228766 139 1949454898 140 2156046665 141 2383435926 142 2634335666 143 2910180164 144 3214519897 145 3548738864 146 3917419484 147 4321916537 148 4768010368 149 5256985959 150 5796091158 151 6386548450 152 7037307668 153 7749508723 154 8534132738 155 9392269290 156 10337242880 157 11370108812 158 12506935344 159 13748825274 160 15114995997 161 16606675702 162 18246712659 163 20036610019 164 22003389264 165 24148987629 166 26505212246 167 29074700557 168 31894656825 169 34968810645 170 38340484115 171 42014919169 172 46042413984 173 50430256634 174 55236572368 175 60471493921 176 66201962525 177 72441829322 178 79267974688 179 86699041604 180 94823027487 181 103664945960 182 113325142383 183 123836491922 184 135313463472 185 147798878088 186 161422697698 187 176240283369 188 192399055438 189 209969820451 190 229119532457 191 249937872501 192 272613621594 193 297259881883 194 324089710673 195 353244138336 196 384964071044 197 419424427566 198 456896659137 199 497596667006 200 541830647930 201 589863332488 202 642040170397 203 698683603436 204 760183537884 205 826931812717 206 899368188260 207 977965504984 208 1063221423323 209 1155704602504 210 1255977501138 211 1364721418660 212 1482573629198 213 1610347140439 214 1748765064502 215 1898793371414 216 2061254116439 217 2237292814211 218 2427844639955 219 2634262100988 220 2857613109358 221 3099490677172 222 3361114604212 223 3644355849923 224 3950611936317 225 4282074690647 226 4640347935441 227 5027991734536 228 5446850801300 229 5899910865236 230 6389295987202 231 6918478060399 232 7489910295269 233 8107622907605 234 8774450730242 235 9495062760769 236 10272741820594 237 11112887673747 238 12019305758128 239 12998228498459 240 14054073586758 241 15194025998298 242 16423216834377 243 17749913683713 244 19180084708659 245 20723232252688 246 22386298532466 247 24180189509067 248 26112987331562 249 28197195466027 250 30442223395048 251 32862387886974 252 35468647652283 253 38277382460951 254 41301352019545 255 44559275219538 256 48066011156744 257 51842936351919 258 55907346207561 259 60283630951558 260 64991917908958 261 70060019587506 262 75511344622514 263 81377584632919 264 87685954228644 265 94472547690173 266 101768981144288 267 109616340862171 268 118051334341692 269 127120712711101 270 136867061726155 271 147343554106153 272 158599560551333 273 170695542935923 274 183688686458465 275 197647719918088 276 212638828759574 277 228740123490028 278 246028138016153 279 264591627329429 280 284519014905999 281 305911139483496 282 328870070861005 283 353510359418444 284 379949722651041 285 408318283222755 286 438751678600225 287 471397711313672 288 506412531486616 289 543964016301814 290 584231770538966 291 627406474978663 292 673694522514460 293 723312498750693 294 776497378957622 295 833495172449002 296 894577730439850 297 960024495121746 298 1030147061303940 299 1105262860449383 300 1185728742255461 301 1271905296412457 302 1364200872307861 303 1463025111284350 304 1568844905208493 305 1682125629358634 306 1803400711387551 307 1933198857409329 308 2072129034352984 309 2220791907395086 310 2379882173645067 311 2550082265067705 312 2732184096882429 313 2926962979776139 314 3135321036676441 315 3358139104754226 316 3596444124791310 317 3851236777898681 318 4123685357097384 319 4414926653248423 320 4726288890935138 321 5059063388785172 322 5414759299189755 323 5794843387132841 324 6201029321471617 325 6634982962921109 326 7098649141447954 327 7593919660413457 328 8123000426308859 329 8688039520442875 330 9291537694879060 331 9935933713805134 332 10624061068238047 333 11358688053466974 334 12143023660059484 335 12980209728795196 336 13873878713954485 337 14827595676985982 338 15845470619909555 339 16931548035625269 340 18090476152603234 341 19326842290070613 342 20645901251373176 343 22052854896020508 344 23553641256996274 345 25154157492506739 346 26861111236772531 347 28681186221498756 348 30621956456668061 349 32690995039263823 350 34896851328339834 351 37248103756952024 352 39754399227671639 353 42425452017151140 354 45272143986775149 355 48305472490203159 356 51537708379440872 357 54981297524871703 358 58650073076861470 359 62558115870472443 360 66721015434533531 361 71154697121725079 362 75876725055341759 363 80905104871644112 364 86259619856664182 365 91960620707009416 366 98030384508985167 367 104491904910204427 368 111370260506321338 369 118691421968208901 370 126483615085627012 371 134776163064521022 372 143600825829680058 373 152990700331053440 374 162981515048966049 375 173610613393335515 376 184918179013270891 377 196946331642697171 378 209740255754485082 379 223347442094127223 380 237818686939277242 381 253207517748020629 382 269571027980489199 383 286969528324316424 384 305467176135305388 385 325131901148146472 386 346035784151495691 387 368255309940825617 388 391871444737291722 389 416970275739187112 390 443642731907549903 391 471985675651769230 392 502101203955992812 393 534098265329996149 394 568091474693028171 395 604203333567642556 396 642562483851314618 397 683306619722221425 398 726580099214115824 399 772537641949506300 400 821341210775186315 401 873164598255878007 402 928189484187287713 403 986611022439998549 404 1048632970400687664 405 1114474397453948294 406 1184363778421189504 407 1258546951135090855 408 1337280056100353158 409 1420838883746552597 410 1509510535410643635 411 1603604307541296747 412 1703441942413488222 413 1809370206505946583 414 1921749592893304105 415 2040968760916350873 416 2167431542426869747 417 2301573420074193520 418 2443846687177238624 419 2594739147934811322 420 2754757272170615425 421 2924447313794754017 422 3104376296866957658 423 3295155754180858957 424 3497420377926828897 425 3711854588096040370 426 3939168678484026391 427 4180128432627626121 428 4435528591055709788 429 4706225739045727700 430 4993108924991551745 431 5297136045955414718 432 5619301446417679700 433 5960676034888980454 434 6322371696038642821 435 6705585371154948616 436 7111560124516138423 437 7541633419613648345 438 7997194689788051281 439 8479738041984158277 440 8990816191373719758 441 9532097818850687778 442 10105317749140790351 443 10712339178552261710 444 11355099994562479805 445 12035680081780170081 446 12756243704796086252 447 13519112085097984885 448 14326701800807339421 449 15181602806855584696 450 16086512839473836227 451 17044321032063701968 452 18058038353418727688 453 19130886941027695309 454 20266226652123105586 455 21467650203599736325 456 22738905971144203697 457 24083998984925815973 458 25507110173981993220 459 27012703223856695696 460 28605440539932312237 461 30290295915513882585 462 32072467568376296199 463 33957496513057533963 464 35951177121204941895 465 38059681017516198364 466 40289465716677363858 467 42647403791412147192 468 45140690260622382998 469 47776976684298576156 470 50564278103512354884 471 53511111629060174400 472 56626403884350515546 473 59919633538738919547 474 63400740359366705605 475 67080271030902160317 476 70969291107697928276 477 75079533321190270352 478 79423313907416669081 479 84013682476580402936 480 88864344413872036932 481 93989811213256149109 482 99405330874029573977 483 105127037450630893449 484 111171891628524111574 485 117557828044606420759 486 124303708490139672283 487 131429465376283317439 488 138956070326049631046 489 146905671931945564819 490 155301582798875550246 491 164168409543336070939 492 173532061717381312125 493 183419871727728001441 494 193860629428920020158 495 204884689420063146748 496 216524035507294437248 497 228812372544708989131 498 241785225375512951194 499 255480012127155193823 500 269936182728114483126 501 285195270242672022868 502 301301074509760110766 503 318299687842972133855 504 336239729889357893273 505 355172343650646618606 506 375151488183261631168 507 396233900622018271351 508 418479453943033900208 509 441951080298018001860 510 466715201642649663640 511 492841609387395185362 512 520403976385250467013 513 549479687514945199988 514 580150442139786402776 515 612502029963522375916 516 646625033832889362189 517 682614544788021431442 518 720570975779378696786 519 760599709578656871871 520 802812034783501464286 521 847324719873376061368 522 894261083627222465215 523 943750488362032408224 524 995929557786797968500 525 1050941582107305862335 526 1108937897110870478005 527 1170077193667826192087 528 1234527072794700932709 529 1302463251759612086945 530 1374071310711157627425 531 1449545787530407337007 532 1529092132590586651799 533 1612925684293082251592 534 1701273849389693870637 535 1794374951178317443849 536 1892480653864193724033 537 1995854675316067466014 538 2104775474791253674977 539 2219534822400300613301 540 2340440770589282477612 541 2467816072535167808039 542 2602001458651234342861 543 2743353896615753947034 544 2892250195209216977754 545 3049085099025921118601 546 3214275242792652810075 547 3388257074569101187049 548 3571491184747655311034 549 3764460052208288013200 550 3967672772958222916038 551 4181662624873273618140 552 4406992221935777659109 553 4644250894236606402662 554 4894060294460331804834 555 5157071591465517428230 556 5433971556569214613903 557 5725479570584713127870 558 6032354218023827915891 559 6355390109701110738164 560 6695425013758054438712 561 7053336498132629548880 562 7430049627711034754556 563 7826533433909082528965 564 8243809207887921819652 565 8682946807459401138085 566 9145073576479492401936 567 9631370503116180791379 568 10143081795974256282783 569 10681510911640653682783 570 11248030818022490779324 571 11844079913985430122421 572 12471173010544143652632 573 13130897170401339950495 574 13824923437298692454846 575 14555002629368842468331 576 15322977846814706427318 577 16130780259372304422599 578 16980442421741437777065 579 17874094103034876977637 580 18813976438982645877873 581 19802437859113823939157 582 20841949103635106090365 583 21935099313498383027056 584 23084611938957311977957 585 24293341067402266628884 586 25564288249179795073391 587 26900599149364095050276 588 28305581315134385803992 589 29782701249678995012041 590 31335603143410937318587 591 32968106481835677791056 592 34684225761337822424103 593 36488168757195448615774 594 38384357242233344248589 595 40377426057694366735200 596 42472244850881207173019 597 44673918108836602962876 598 46987807928494224430927 599 49419535192483372574087 600 51975003382777563900914 601 54660401098781357926533 602 57482226922215899554715 603 60447293500556544266108 604 63562753468394810581294 605 66836105343575596183345 606 70275220506832142815192 607 73888351185261427456428 608 77684158488980608737353 609 81671722785188111587989 610 85860572787511703745172 611 90260698655295549381158 612 94882582128362295954663 613 99737212720106837747193 614 104836118887026805248062 615 110191387720768814090736 616 115815697139685996729481 617 121722339523879433493701 618 127925254913314096723795 619 134439059072766405519587 620 141279077679097652305615 621 148461379348147148939345 622 156002810792713562878411 623 163921035392100386080505 624 172234569301781906117455 625 180962826199059855617964 626 190126154325318710549639 627 199745888097168481687749 628 209844386064419817569542 629 220445090135759129927934 630 231572564438133412739214 631 243252562970790474005399 632 255512069356028375798346 633 268379373803821766738882 634 281884113750963613663539 635 296057361091236131131416 636 310931663708483302322788 637 326541144006236397946207 638 342921541351244901329389 639 360110323019192393421379 640 378146727580372861559163 641 397071889466643004042660 642 416928883348668799679682 643 437762863624091512454396 644 459621109857150430006992 645 482553182588483504687508 646 506610969935608526143280 647 531848861230469390771871 648 558323794910471755855168 649 586095451604751937529328 650 615226303483003672107352 651 645781828530716099415064 652 677830561568105579810281 653 711444331582521632591071 654 746698314681810259851771 655 783671296487785274848237 656 822445727347662901700889 657 863108011936740502896345 658 905748567123239734583913 659 950462141078886575220197 660 997347874271888240580517 661 1046509650548007129735809 662 1098056161818865117778135 663 1152101293745277627264243 664 1208764194793916857377502 665 1268169699336774624236460 666 1330448401869865895523692 667 1395737120534196384204580 668 1464178977424675575649042 669 1535923905742630906006342 670 1611128737279986752111567 671 1689957756625944108948660 672 1772582797083590702546589 673 1859183845585187472553412 674 1949949148495101818252926 675 2045075871126797777128382 676 2144770215105787343185747 677 2249248136639458335517908 678 2358735477361604019269091 679 2473468745776253911182706 680 2593695263778175080691387 681 2719674015982344906443960 682 2851675814426209581844675 683 2989984220797556156045554 684 3134895732163982401812480 685 3286720781441273517281520 686 3445783947378389677002881 687 3612425038947969785667878 688 3786999333236855914609383 689 3969878749809450931521439 690 4161452120625147229996900 691 4362126460810984610595753 692 4572327275241991374105633 693 4792499932577617384541821 694 5023110013719519451695943 695 5264644796400625228807608 696 5517613651363213089434103 697 5782549645266184465723320 698 6060009991127024729752881 699 6350577777806997439762121 700 6654862482025394269254436 701 6973501833222846546270431 702 7307162395304504854853612 703 7656541576247891927571770 704 8022368288652715183050129 705 8405405114078128671913052 706 8806449052500644428160707 707 9226333852012257586747381 708 9665930858396024782812098 709 10126151521528588179614544 710 10607948357508486002960110 711 11112317643851546927820512 712 11640300507935880412472413 713 12192985823897826958119760 714 12771511442622152965064800 715 13377067304109547219187379 716 14010896825824217657301144 717 14674300245253335427331322 718 15368636185169284719668447 719 16095325242102886780813895 720 16855851748961124301892296 721 17651767626242041186829895 722 18484694364517801338034124 723 19356327156388539299497514 724 20268437123574207467475447 725 21222875748896000482185580 726 22221577375168434075501813 727 23266563957868595319293764 728 24359947865658739981073930 729 25503936975919052529527890 730 26700837809619278867686408 731 27953060993504625304190590 732 29263124765145326839873652 733 30633660827350328589758838 734 32067418262621720648725957 735 33567269807277657377227726 736 35136216218195027881088427 737 36777392996232867247797350 738 38494075252135387715650275 739 40289684911106084736964172 740 42167796129032906500798827 741 44132143012564224599410785 742 46186625641488090217262453 743 48335318341347330380405387 744 50582476372825737098941243 745 52932544796909659282998960 746 55390165897594702064004327 747 57960188682800778307981879 748 60647677112575646132712855 749 63457920282510223645821766 750 66396441535986139465158399 751 69469009380653339586272987 752 72681647570108835215868509 753 76040646808221200459677142 754 79552575893044080728386619 755 83224294268336055392866192 756 87062964330475610340732450 757 91076064891563803372870393 758 95271404758737431300425772 759 99657137178701409704424300 760 104241774808089084405198818 761 109034205215301314547797893 762 114043707370585179203649353 763 119279968287586144685254007 764 124753101172565481949793556 765 130473663295284163562714614 766 136452675948398022156510883 767 142701643645118692505525025 768 149232576052290889038705185 769 156058008620896373941121980 770 163191026669790037765542281 771 170645287564484351201124559 772 178435047142953771413557211 773 186575183568460586079411100 774 195081226304433462891042841 775 203969381778304466002880421 776 213256565129185864465651631 777 222960427832033827309347067 778 233099392459878474261741902 779 243692682431054510783019017 780 254760360047077376223728289 781 266323358540426590692605628 782 278403523670019067155202539 783 291023648263082543600934060 784 304207517672520600449196745 785 317979947024041649497483674 786 332366830863810304799133461 787 347395183341161741763355224 788 363093192400767834463347752 789 379490263152305055257380256 790 396617076989185584275554538 791 414505638419438314807198216 792 433189339522895805832388312 793 452703010542617083887362985 794 473082990124565832662411829 795 494367179996196438249944592 796 516595121467104320350615940 797 539808054551275900218397032 798 564049001244302427583044077 799 589362829478281077379062602 800 615796343730980046375540529 801 643398354237924430379821668 802 672219775531725227015594105 803 702313701374547844348702520 804 733735511871770153618891971 805 766542954630252408322764669 806 800796261139953799817900635 807 836558234709354113117235915 808 873894376861705398630377605 809 912872982649088117124946052 810 953565277867088036991841305 811 996045522403445338415257169 812 1040391159136240219066194588 813 1086682926032515177357550246 814 1135005017660994363103578582 815 1185445206820631978590750463 816 1238095019669699586885960931 817 1293049867734536922917116028 818 1350409237733044325086382289 819 1410276834890323536010523526 820 1472760788616420489165295708 821 1537973808138710791020186894 822 1606033405281800270602761065 823 1677062063516791063302780820 824 1751187479185846798559310895 825 1828542745166674557063717391 826 1909266611986050718505910490 827 1993503687404433698873499709 828 2081404718972149769795507015 829 2173126810954837037163162998 830 2268833730003744689987775614 831 2368696140968335915110461991 832 2472891937478720777142255613 833 2581606498328138590264637055 834 2695033044901804420366123410 835 2813372919959869309373803316 836 2936835973993492091485168071 837 3065640868399322046520545632 838 3200015493001344788969667731 839 3340197295781824758568369694 840 3486433733977181247935911268 841 3638982632718827098975807685 842 3798112672294059461882316971 843 3964103778254448035462087650 844 4137247647629362180347547304 845 4317848173280790066561392243 846 4506222012068891828958549895 847 4702699046471672363568431833 848 4907622997929927660735595178 849 5121351929009524930447639408 850 5344258905398655187661110288 851 5576732542171146443346274871 852 5819177718173368934259216159 853 6072016170250667960679083658 854 6335687264046130363418345616 855 6610648640380724176205539358 856 6897377046793007720322591950 857 7196369040618751354736630717 858 7508141885931300452123495374 859 7833234318250541413183710583 860 8172207511899901559374597989 861 8525645911689565476345683773 862 8894158276090039742630598716 863 9278378581683117444094196310 864 9678967147965758003089618197 865 10096611620846828775226043838 866 10532028185341050844656238911 867 10985962634913003841501658323 868 11459191678801775228149990373 869 11952524104578776814897332452 870 12466802187362063331880524301 871 13002902953564791074142910765 872 13561739699817121050352859853 873 14144263366540587067718476507 874 14751464174998143379602322117 875 15384373120040493786667665850 876 16044063734354794255019997236 877 16731653710495641754910247777 878 17448306802103709762346252054 879 18195234586161320005012804840 880 18973698511708342216331087265 881 19785011814154034338524178684 882 20630541722832717122202405504 883 21511711540165619895525442019 884 22430003020278348023120464314 885 23386958626843093117974952607 886 24384184095928478204522847931 887 25423350887470298649771681135 888 26506198946547775406576239951 889 27634539364635236234471586315 890 28810257354602539299905200864 891 30035315139198121559178049746 892 31311755156262589777318992929 893 32641703193291298414969744222 894 34027371840634723617617909471 895 35471063892495144302149635754 896 36975176067273766224491120162 897 38542202696977565308741977782 898 40174739735368548195994623368 899 41875488759503636363353107984 900 43647261287955186602117934316 901 45492983120086888728217618602 902 47415698988355140011821268491 903 49418577262948594809951864450 904 51504914964058624460928647386 905 53678142861688427513043161659 906 55941830875806746233617179467 907 58299693603478097575095167297 908 60755596137000343835643393684 909 63313560053030358150699760077 910 65977769681164394707674619451 911 68752578592449080386438434065 912 71642516353408350567110922244 913 74652295554250202356345708108 914 77786819086088384219961020799 915 81051187752298123204804638823 916 84450708109642650840570346806 917 87990900709609986907961120368 918 91677508547348088466606876839 919 95516505983450681330828671194 920 99514107848050882159968690694 921 103676779097432034111701520876 922 108011244624345914367263421605 923 112524499708028447116786900167 924 117223820585817755725757734533 925 122116775759673179530093311961 926 127211237388490984930679141936 927 132515393519084555133331694178 928 138037760363259194455938072876 929 143787195526433096548232363264 930 149772911238559892255088618853 931 156004488659185712443497254530 932 162491892136730669199450330303 933 169245484674810402549499926906 934 176276043300233385848335656597 935 183594775781901875778883630702 936 191213337194185889107589189367 937 199143847986687383566720934681 938 207398911836446021533361052017 939 215991635174341471889455726378 940 224935646426913063421632167466 941 234245117113221522811400193370 942 243934782584959789192985929703 943 254019964816244971515318590176 944 264516594759209524428931433196 945 275441236958483365348190431634 946 286811113648626635166721360375 947 298644131335045100060074371291 948 310958906769511808229232746443 949 323774795649980962402781686889 950 337111920621095878089026391125 951 350991202256887597894940405945 952 365434389244645269320044476036 953 380464091826857533198163359686 954 396103814339184395976077112306 955 412377991301293451227732981670 956 429312022492993476456386803892 957 446932311897891345532894173851 958 465266305516094230045606796754 959 484342533379948228819688501938 960 504190650317170718600543095126 961 524841481274397939247377635050 962 546327065261249237078064065257 963 568680704235098960159556266444 964 591937010474498007028726651279 965 616131959297575715920466174440 966 641302940132538239824304396889 967 667488813362506010144510834257 968 694729965381585058487979811216 969 723068369880845289839852939496 970 752547647200824040238994732201 971 783213130396872279153119697355 972 815111929223025030659616970026 973 848293001340194897537585596197 974 882807221292251391075872972148 975 918707457247660922110604818462 976 956048645356504446849935546183 977 994887872445275112248690225504 978 1035284456173566231561462842049 979 1077300034133003021577883270800 980 1120998650254619913128932497093 981 1166446850796462389140934191849 982 1213713777487404428776741072325 983 1262871270923994094738016446312 984 1313993970973828909580250966872 985 1367159428140902217203897843573 986 1422448211791841197503140650902 987 1479944030090546929447997030303 988 1539733846653829188485781322271 989 1601908009700715046768932942760 990 1666560377790496029757089814807 991 1733788458879949271921496604161 992 1803693545846800624218952556347 993 1876380866199478906533668839676 994 1951959728142739396880218542820 995 2030543681739731311266576289315 996 2112250676334307522250192928726 997 2197203234024387323008252156744 998 2285528619317583671319447884804 999 2377359025838399298410690454361 1000 2472831759160566618231209054357