1 0 2 1 3 0 4 1 5 0 6 2 7 1 8 4 9 2 10 6 11 4 12 9 13 6 14 16 15 9 16 23 17 18 18 34 19 27 20 51 21 40 22 75 23 63 24 103 25 90 26 152 27 130 28 208 29 191 30 286 31 267 32 402 33 368 34 546 35 518 36 730 37 709 38 998 39 954 40 1322 41 1305 42 1751 43 1740 44 2330 45 2299 46 3056 47 3074 48 3968 49 4031 50 5202 51 5249 52 6721 53 6877 54 8642 55 8888 56 11147 57 11432 58 14248 59 14747 60 18097 61 18838 62 23093 63 23938 64 29186 65 30489 66 36765 67 38543 68 46358 69 48502 70 58104 71 61113 72 72543 73 76520 74 90678 75 95449 76 112700 77 119160 78 139669 79 147970 80 173094 81 183164 82 213663 83 226742 84 262897 85 279492 86 323549 87 343567 88 396625 89 422209 90 485059 91 516985 92 592983 93 631453 94 722675 95 770891 96 878641 97 938288 98 1067856 99 1139413 100 1294108 101 1382834 102 1565302 103 1673758 104 1891940 105 2021806 106 2281422 107 2440539 108 2745804 109 2939073 110 3302549 111 3532966 112 3963617 113 4243579 114 4749131 115 5086550 116 5685748 117 6086939 118 6794438 119 7278025 120 8106442 121 8686188 122 9664528 123 10350915 124 11502019 125 12324430 126 13669724 127 14649942 128 16232401 129 17389689 130 19246134 131 20624489 132 22788997 133 24424212 134 26962429 135 28886244 136 31854776 137 34135223 138 37589203 139 40282301 140 44319473 141 47479012 142 52188133 143 55915369 144 61382675 145 65767623 146 72140391 147 77268830 148 84681629 149 90708085 150 99297494 151 106360568 152 116344519 153 124582649 154 136168204 155 145811682 156 159208597 157 170473966 158 186006676 159 199110004 160 217090628 161 232378630 162 253131202 163 270932309 164 294934419 165 315588436 166 343312177 167 367332261 168 399267289 169 427156489 170 464009143 171 496287359 172 538761139 173 576191649 174 625029358 175 668368065 176 724602524 177 774647152 178 839327029 179 897200000 180 971435765 181 1038274991 182 1123580119 183 1200585763 184 1298507729 185 1387335508 186 1499532252 187 1601871354 188 1730540425 189 1848198676 190 1995622867 191 2131016803 192 2299644321 193 2455279876 194 2648305159 195 2826868847 196 3047627719 197 3252649860 198 3504748276 199 3739909576 200 4027959591 201 4297243816 202 4626113012 203 4934633295 204 5309589991 205 5662745713 206 6090441138 207 6494078949 208 6981560994 209 7443086290 210 7998032127 211 8525295636 212 9157242914 213 9758799958 214 10477935590 215 11164440131 216 11981869405 217 12764712745 218 13694086602 219 14585689634 220 15641642479 221 16657307467 222 17855856858 223 19011992448 224 20372585918 225 21687171572 226 23230775496 227 24725666532 228 26475240440 229 28174018145 230 30157210907 231 32085721168 232 34332414747 233 36521803209 234 39064813573 235 41548770476 236 44427231479 237 47242794406 238 50499170442 239 53690515699 240 57371469855 241 60986589937 242 65147383982 243 69239044156 244 73939756573 245 78570468237 246 83877240660 247 89115025550 248 95105580945 249 101025380670 250 107784476563 251 114474359569 252 122095326196 253 129651412425 254 138243305006 255 146771508827 256 156453408653 257 166077492040 258 176980679677 259 187835877782 260 200112826042 261 212348347227 262 226165887250 263 239954966113 264 255497034024 265 271029383867 266 288508608191 267 305993519710 268 325642755509 269 345322098224 270 367398287257 271 389537135724 272 414335822024 273 439226827236 274 467072129174 275 495051794402 276 526301324222 277 557738961201 278 592802452751 279 628105712353 280 667432798112 281 707068612008 282 751155584636 283 795636629942 284 845049816685 285 894942255207 286 950303698922 287 1006253338259 288 1068249487305 289 1130966063899 290 1200377722959 291 1270644777543 292 1348329837232 293 1427038255925 294 1513943577123 295 1602072680611 296 1699271669985 297 1797902768547 298 1906575447355 299 2016933830523 300 2138382267237 301 2261815580413 302 2397511811917 303 2535507486881 304 2687069960571 305 2841308971511 306 3010523446986 307 3182854684865 308 3371734386849 309 3564198428921 310 3774957496268 311 3989853943291 312 4224934543873 313 4464793359489 314 4726942330552 315 4994554662166 316 5286792854780 317 5585296910456 318 5910955667810 319 6243803676678 320 6606621208541 321 6977621059699 322 7381708808559 323 7795131746774 324 8245021930591 325 8705566943749 326 9206335128855 327 9719182937792 328 10276410566148 329 10847360851525 330 11467198946819 331 12102630847994 332 12791954091533 333 13498898646137 334 14265266390339 335 15051578977396 336 15903318322859 337 16777638366676 338 17724039927046 339 18695885152396 340 19747162436385 341 20827148281388 342 21994548168804 343 23194346189358 344 24490395392023 345 25822859134265 346 27261326179686 347 28740766984476 348 30336806336926 349 31978956197743 350 33749421386627 351 35571596791665 352 37535006352273 353 39556458924771 354 41733187347579 355 43975072556074 356 46387744828431 357 48873339268688 358 51546808887168 359 54301951789177 360 57263549988888 361 60316627825830 362 63596664275772 363 66978893596306 364 70610651495649 365 74356640168540 366 78376704939062 367 82524457689577 368 86973348479778 369 91564640455674 370 96486837178032 371 101567921375728 372 107012292816897 373 112633944669060 374 118654549978245 375 124872553602298 376 131528712836239 377 138404759477375 378 145761616012878 379 153363400548569 380 161492933239072 381 169894793504108 382 178875956793385 383 188160007251591 384 198079463008854 385 208335775044531 386 219289176836586 387 230616609303513 388 242708836631712 389 255216475589615 390 268562592222641 391 282370041727104 392 297096918175341 393 312335388006948 394 328582076108486 395 345396200586302 396 363315178178576 397 381863472023630 398 401622701379108 399 422078971064617 400 443862461400472 401 466418114237742 402 490427545154355 403 515292262923564 404 541749587076815 405 569153168197466 406 598301441304003 407 628496719123875 408 660602204374523 409 693866032651098 410 729221502850164 411 765857141398281 412 804783063305881 413 845123881948846 414 887971152791839 415 932382026534304 416 979536150886976 417 1028416561970688 418 1080299327571045 419 1134088049699467 420 1191161067963745 421 1250338130098553 422 1313108133178814 423 1378198828736731 424 1447219992591320 425 1518800823598019 426 1594679357347675 427 1673380740880023 428 1756781588838537 429 1843293054132364 430 1934943098838249 431 2030020806461995 432 2130714791750430 433 2235185251138036 434 2345794279682526 435 2460561052680027 436 2582036939546087 437 2708090176382974 438 2841473104015678 439 2979894576717999 440 3126323847992480 441 3278295612991048 442 3439015544288659 443 3605832005975602 444 3782201785327953 445 3965276493561944 446 4158783807990792 447 4359660604871736 448 4571929537547803 449 4792297849549819 450 5025101585433565 451 5266805505616669 452 5522083571138412 453 5787136221279906 454 6067005033600784 455 6357607908080994 456 6664377098979855 457 6982932171552890 458 7319126422727299 459 7668254586756587 460 8036627615132808 461 8419193187618233 462 8822748723901811 463 9241875456686333 464 9683894860431919 465 10142989634527139 466 10627050382330137 467 11129834190434648 468 11659836765917856 469 12210365844920059 470 12790568692224255 471 13393264875014795 472 14028308693043660 473 14687998624973443 474 15382940834976631 475 16104883693432490 476 16865242619748336 477 17655169005134395 478 18486955723939318 479 19351117218705174 480 20260879637535786 481 21206085095407538 482 22200963823828747 483 23234629073977668 484 24322398976426459 485 25452609498644166 486 26641736049317570 487 27877294244044884 488 29177004096116451 489 30527492808825236 490 31947827893901907 491 33423689560528829 492 34975578988474041 493 36588177102360921 494 38283526319214971 495 40045226435403224 496 41896987376229733 497 43821257096013782 498 45843519878736893 499 47945008450717728 500 50153113894922131 501 52447755480628777 502 54858385899221884 503 57363525720312848 504 59994821642594319 505 62729318897313944 506 65601021072253191 507 68585380313447575 508 71718946823786972 509 74975477144435577 510 78394231907764123 511 81947179540839724 512 85676491333706109 513 89552206727455096 514 93619639983958155 515 97846778439562417 516 102282281861819429 517 106891974108340829 518 111728106337080456 519 116754170620944496 520 122026293858348118 521 127505488818122287 522 133252008217588295 523 139224251669855843 524 145486899524889134 525 151995537550214044 526 158819621483221762 527 165911746779017656 528 173346453118238812 529 181073185205145355 530 189171936775944436 531 197588762831781694 532 206409536302593988 533 215576711879608263 534 225182421944455735 535 235165328933496841 536 245624278329525399 537 256493856390553089 538 267880141042118109 539 279713391463523560 540 292107386306280331 541 304987828648127109 542 318476753432776929 543 332494970817491459 544 347173406222015836 545 362427678694405332 546 378398180183826514 547 394995065938805949 548 412368874487851400 549 430423898578508716 550 449321597187022889 551 468960046857696790 552 489512335158620281 553 510869998647814743 554 533218585258439934 555 556442620439860442 556 580741056449773483 557 605990989150035850 558 632405644763745430 559 659854306008907958 560 688565489931215916 561 718400110680535644 562 749603126815828869 563 782026589858079473 564 815932967152803578 565 851164994563780683 566 888003890431991909 567 926282421456540435 568 966301959132529063 569 1007884719304979888 570 1051353535215479856 571 1096519538143607840 572 1143728539882576919 573 1192779820129605735 574 1244043876791671506 575 1297307454764356423 576 1352967341523932199 577 1410797120428231146 578 1471221719346030555 579 1534000661882330231 580 1599589094993609078 581 1667731682458642322 582 1738915753405590784 583 1812870377946789991 584 1890117324771084039 585 1970369021321107133 586 2054184204915499421 587 2141257726001923833 588 2232187692420752349 589 2326650521465087811 590 2425286442984465066 591 2527752219146665710 592 2634733277712747265 593 2745865638256188568 594 2861882862924636231 595 2982399233188510110 596 3108199797836714687 597 3238875681147624239 598 3375267157543632995 599 3516940932474871138 600 3664796093911517970 601 3818373775666329011 602 3978635961022720452 603 4145096569048079081 604 4318785021758984242 605 4499186565376643502 606 4687402441295808565 607 4882887893307320701 608 5086820950066023356 609 5298624957176740671 610 5519560248727788320 611 5749016593419780279 612 5988341976305735139 613 6236891063096297698 614 6496105532819917783 615 6765302768679183547 616 7046024843382596049 617 7337549933699486855 618 7641527024473879299 619 7957193343097110820 620 8286312134268841028 621 8628077180715614332 622 8984374117459932084 623 9354351087941879765 624 9740024062004193835 625 10140493564936196977 626 10557914830830406650 627 10991337922425096271 628 11443067201444387704 629 11912099778663841829 630 12400898819721211074 631 12908406250903801739 632 13437254889010002872 633 13986328250039691307 634 14558440762410035590 635 15152414724881474907 636 15771257956988189032 637 16413729040762955838 638 17083042357275335000 639 17777889133608749230 640 18501704810884414352 641 19253110118913690133 642 20035775890150899734 643 20848249582514148306 644 21694453404697620381 645 22572857466076509903 646 23487652919486850934 647 24437229036124963729 648 25426063340185212499 649 26452461216867293725 650 27521205953447485596 651 28630514514373819193 652 29785497230168325930 653 30984278806959984462 654 32232317798578693795 655 33527643345900021691 656 34876085741723079924 657 36275573561580255832 658 37732334603953092527 659 39244192707008852805 660 40817798903724100468 661 42450868762798582260 662 44150505055688571057 663 45914309624534540737 664 47749868168556946934 665 49654664332884482228 666 51636797982385719881 667 53693630866359395124 668 55833811552964532554 669 58054574015269063448 670 60365153263557542415 671 62762650790035698952 672 65256925956443305967 673 67844944003326659517 674 70537230474762568287 675 73330608121329666850 676 76236314318952848715 677 79251024495344372088 678 82386733840721026807 679 85639966757101300326 680 89023526894901911695 681 92533781146665506778 682 96184396821632027921 683 99971578499535693221 684 103909912898896696700 685 107995438855128504573 686 112243723789822729034 687 116650634236336582642 688 121232785044126196656 689 125985865901568370123 690 130927606647171058561 691 136053517246540110679 692 141382516681558634007 693 146909928817550725427 694 152655942409809100575 695 158615691262577648399 696 164810715744041278539 697 171235957663170937220 698 177914398679500603307 699 184840782767495524402 700 192039630281763796656 701 199505484428751443846 702 207264503348522650177 703 215311029012323674292 704 223672965761204509529 705 232344449528610179515 706 241355248484249502837 707 250699291216560127466 708 260408329652537740128 709 270476086736361027736 710 280936429170831784758 711 291782871163974292967 712 303051536203152612805 713 314735730881910909602 714 326873980558379221858 715 339459389001355939851 716 352533041720613786967 717 366087839185378462100 718 380167598444902229550 719 394765021275532738344 720 409926831717726668472 721 425645541942087131562 722 441970974127462706761 723 458895454176760507088 724 476472109191891530860 725 494693088285401275868 726 513615035566476236583 727 533229938306551815133 728 553598188384244174418 729 574711619953102836497 730 596634622074355536864 731 619358891926638176133 732 642953072020825482465 733 667408745394826453645 734 692799086499214760510 735 719115580379385481181 736 746436234168222266290 737 774752460047786479209 738 804147407363316114045 739 834612448742813781940 740 866236211724591306420 741 899010055595657484946 742 933028448611144981246 743 968282773803635064362 744 1004873713869175189805 745 1042792722681845516776 746 1082147102580164291897 747 1122928417941149580535 748 1165251027616867499210 749 1209106659329589275796 750 1254617179501239191403 751 1301774544284826728659 752 1350708616200445495044 753 1401411637268903689553 754 1454021992414570012296 755 1508532282943608050818 756 1565089960376852952711 757 1623688073708310132894 758 1684483729849540570793 759 1747470506189249201652 760 1812815798898668929838 761 1880513813860761720409 762 1950742892818574921730 763 2023497988581484092240 764 2098969097880374874355 765 2177152031390119175815 766 2258249204015423840939 767 2342257418771090765407 768 2429392299985580192947 769 2519651799924183140602 770 2613265606807946881262 771 2710232972096818625886 772 2810798566528483747519 773 2914963119284207823989 774 3022987237199805864362 775 3134873333148847017879 776 3250898978925075298191 777 3371068471079950381557 778 3495677451756967751456 779 3624732335881892252573 780 3758547984762367143196 781 3897133199969512112200 782 4040823300418818575406 783 4189629738172451587910 784 4343909619507830454057 785 4503677352996746857851 786 4669313215801140482622 787 4840834920072871369603 788 5018647404118130064387 789 5202772028653027395031 790 5393639992311227424518 791 5591276700589155107526 792 5796141278057176767835 793 6008263621399970309627 794 6228132573832146354654 795 6455782970869468791559 796 6691735297026397048969 797 6936029836547459993726 798 7189220719752400844262 799 7451354250842221950132 800 7723020361815044377358 801 8004271953898444789847 802 8295737071647692130971 803 8597475866019456613093 804 8910156905662729701576 805 9233848318891582296181 806 9569261790239007346749 807 9916474165063874470887 808 10276243020481985797395 809 10648654750480099394834 810 11034515724971672866996 811 11433922809630868302198 812 11847734282062926613279 813 12276058423033832914414 814 12719808753279139140685 815 13179106023683669067359 816 13654922484860956419736 817 14147392524492042868028 818 14657550865470627206044 819 15185546730152454512544 820 15732481319172024135274 821 16298520023019151450988 822 16884834710538479655904 823 17491608409995385999449 824 18120088153391681315369 825 18770476121728629953573 826 19444099318828316164888 827 20141180758010788327082 828 20863132449461781229157 829 21610200084442993999605 830 22383886076634873934390 831 23184460704328799277698 832 24013522555963941226426 833 24871368605806793494319 834 25759699663650915881466 835 26678841710988465742315 836 27630604257374000415393 837 28615344689448598833860 838 29634988141044964419085 839 30689926044409292732412 840 31782206417341402068475 841 32912257624526667454925 842 34082258341615936596060 843 35292676868670802650673 844 36545830845001643175563 845 37842231803235989573656 846 39184345059584739276497 847 40572728976275124204191 848 42010005871969633738921 849 43496784688814564581401 850 45035854707612095103639 851 46627879557583135618411 852 48275825936054033639362 853 49980416631202638900551 854 51744806940325285875612 855 53569783482403177448607 856 55458702094100604526099 857 57412418329646833463752 858 59434501104358777580394 859 61525880455496784421646 860 63690351784382200195210 861 65928925417481376214725 862 68245637550480726076201 863 70641585129412542228874 864 73121060179369079766212 865 75685253134906830814820 866 78338727919007295424716 867 81082775654875514175770 868 83922249305684130933711 869 86858548518338625184999 870 89896833317775830553006 871 93038620363519212464853 872 96289395994124220741529 873 99650802792241818304218 874 103128673941436697178621 875 106724787626660042601635 876 110445345470761187673459 877 114292271733511730021263 878 118272159535727151760751 879 122387090218024291768477 880 126644072982379127340091 881 131045358186455626597544 882 135598396980108164476603 883 140305621636158044169202 884 145174952862033424029895 885 150209018415556063532504 886 155416237987463008203650 887 160799449515438160560862 888 166367602647865302327670 889 172123761362744076586662 890 178077438314668218450078 891 184231940224311704608312 892 190597377964095078159448 893 197177319059775971544980 894 203982509679900512862143 895 211016797629143229259400 896 218291603918684469797887 897 225811077156996802733088 898 233587355320257800141898 899 241624909988886827187343 900 249936640474692098747353 901 258527365206256738688089 902 267410792138202200386558 903 276592111730871314771616 904 286085890955881831895984 905 295897719473429478514063 906 306043076351853898102210 907 316527979684940192392551 908 327368877210845217729871 909 338572246311755483154965 910 350155563619764075331189 911 362125799055492899947788 912 374501521622461347819876 913 387290229526307309018349 914 400511651774507858793193 915 414173852608377926440649 916 428297793017440778642487 917 442892143918840753115949 918 457979174171269112059941 919 473568205023151056808890 920 489682894030856579897974 921 506333258900622692457947 922 523544431886085698031865 923 541327176761582182943718 924 559708191171134895779726 925 578699038207076130824570 926 598328077472380014969197 927 618607727666627215979279 928 639568113072630539552976 929 661222568484523749166782 930 683603091217183298510632 931 706723997036856164636107 932 730619271627718623328208 933 755304280335725638703363 934 780815119869682175043618 935 807168278818738013844217 936 834402094323716428900334 937 862534257172932616895527 938 891605482649071800886590 939 921634747263598790941964 940 952665290853974648035458 941 984717465264583746856762 942 1017837189390862446273803 943 1052046286395844109808975 944 1087393518602853429743695 945 1123902282062885823985584 946 1161624357244769078213749 947 1200584821978038452487363 948 1240838659282339040798037 949 1282412745332904049798857 950 1325365461828726312108587 951 1369725606670377579363140 952 1415555168665293283696742 953 1462884999621847654584459 954 1511780915478081029727611 955 1562275963369230195400505 956 1614440020312550706413021 957 1668308478487220987114749 958 1723955524556711335435021 959 1781419056039365526874117 960 1840777831676858399644869 961 1902072425728872708286715 962 1965386447987362783292560 963 2030763330946840300268476 964 2098291831790740172979982 965 2168018435446533986850797 966 2240037359402432438714230 967 2314398348564670989768759 968 2391201413279824563048135 969 2470499778232796258112017 970 2552399599814357421515740 971 2636957817537943194542813 972 2724287106820985744303568 973 2814448373086235357678843 974 2907561207076439663613941 975 3003690746063724110924749 976 3102963916917492006878921 977 3205450372994652510104346 978 3311284821727611532517513 979 3420541736035233421753089 980 3533364076023416321136790 981 3649831455644729972490039 982 3770095588880678770355347 983 3894241574125856678129611 984 4022430408641956984377644 985 4154753041756122056856657 986 4291380316253523359042076 987 4432409420648051979245030 988 4578021640023225473903922 989 4728320816622227890790552 990 4883499308235994657374756 991 5043668053052088245734594 992 5209031150936202384525885 993 5379707104526308572110334 994 5555912466108034273616938 995 5737773802761745796956749 996 5925520869629629461958372 997 6119288831383117679566404 998 6319321442664271394439739 999 6525763030607618971863424 1000 6738872194613567520037471