1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 2 28 2 29 3 30 3 31 4 32 4 33 5 34 5 35 6 36 7 37 8 38 9 39 11 40 12 41 14 42 16 43 18 44 20 45 24 46 26 47 30 48 34 49 39 50 43 51 50 52 55 53 63 54 71 55 80 56 89 57 102 58 113 59 128 60 143 61 161 62 179 63 203 64 225 65 253 66 282 67 316 68 351 69 395 70 437 71 489 72 544 73 607 74 673 75 752 76 832 77 927 78 1028 79 1143 80 1264 81 1407 82 1554 83 1725 84 1908 85 2114 86 2334 87 2587 88 2853 89 3157 90 3483 91 3848 92 4240 93 4685 94 5157 95 5689 96 6263 97 6902 98 7590 99 8363 100 9188 101 10111 102 11108 103 12212 104 13404 105 14731 106 16156 107 17738 108 19450 109 21337 110 23376 111 25633 112 28064 113 30748 114 33653 115 36843 116 40295 117 44097 118 48198 119 52706 120 57585 121 62929 122 68711 123 75053 124 81902 125 89402 126 97521 127 106387 128 115981 129 126469 130 137798 131 150168 132 163553 133 178137 134 193911 135 211107 136 229684 137 249917 138 271797 139 295588 140 321305 141 349277 142 379486 143 412315 144 447795 145 486300 146 527899 147 573051 148 621794 149 674663 150 731755 151 793616 152 860399 153 932758 154 1010822 155 1095350 156 1186563 157 1285246 158 1391697 159 1506852 160 1631002 161 1765232 162 1909958 163 2066320 164 2234856 165 2416910 166 2613044 167 2824808 168 3052944 169 3299111 170 3564224 171 3850231 172 4158122 173 4490132 174 4847512 175 5232681 176 5647160 177 6093767 178 6574171 179 7091606 180 7648120 181 8247253 182 8891449 183 9584807 184 10330053 185 11131875 186 11993554 187 12920264 188 13915875 189 14986356 190 16136043 191 17371764 192 18698670 193 20124332 194 21654776 195 23298702 196 25062913 197 26957336 198 28989956 199 31171842 200 33512273 201 36023943 202 38717341 203 41606929 204 44704936 205 48027539 206 51588877 207 55407453 208 59499275 209 63885401 210 68584367 211 73619802 212 79013053 213 84791073 214 90978053 215 97604627 216 104698689 217 112294667 218 120424555 219 129127566 220 138439960 221 148406266 222 159068111 223 170475599 224 182676353 225 195727333 226 209682503 227 224606471 228 240560987 229 257618809 230 275850381 231 295338308 232 316162387 233 338416198 234 362190792 235 387591592 236 414722266 237 443702327 238 474649105 239 507697870 240 542982178 241 580654447 242 620866420 243 663790657 244 709598789 245 758485916 246 810646998 247 866301838 248 925671552 249 989004695 250 1056551132 251 1128591627 252 1205409484 253 1287320903 254 1374646682 255 1467743967 256 1566974976 257 1672742728 258 1785457193 259 1905572093 260 2033550969 261 2169905752 262 2315159324 263 2469888813 264 2634685166 265 2810197755 266 2997093838 267 3196105324 268 3407984200 269 3633554818 270 3873665827 271 4129244246 272 4401247104 273 4690718171 274 4998734985 275 5326472061 276 5675143911 277 6046070449 278 6440619614 279 6860276129 280 7306578756 281 7781196703 282 8285862206 283 8822449801 284 9392908389 285 9999344551 286 10643948550 287 11329086612 288 12057221585 289 12831008863 290 13653216322 291 14526825367 292 15454943854 293 16440917703 294 17488237786 295 18600656146 296 19782092041 297 21036754376 298 22369039844 299 23783667936 300 25285572155 301 26880040894 302 28572607605 303 30369199442 304 32276018558 305 34299705524 306 36447212941 307 38725976247 308 41143786192 309 43708969254 310 46430250134 311 49316949888 312 52378839747 313 55626348588 314 59070415634 315 62722709848 316 66595471640 317 70701753228 318 75055250860 319 79670557106 320 84562991958 321 89748869981 322 95245319328 323 101070574058 324 107243782926 325 113785316635 326 120716575944 327 128060317394 328 135840448409 329 144082383242 330 152812827166 331 162060151560 332 171854177879 333 182226575832 334 193210633711 335 204841692994 336 217156907524 337 230195702185 338 243999533048 339 258612375112 340 274080468377 341 290452849732 342 307781087960 343 326119846362 344 345526620577 345 366062337533 346 387791079619 347 410780737330 348 435102723276 349 460832663955 350 488050119298 351 516839320482 352 547288876879 353 579492579490 354 613549099842 355 649562843317 356 687643657905 357 727907745494 358 770477360707 359 815481803008 360 863057110929 361 913347118027 362 966503163071 363 1022685219686 364 1082061601229 365 1144810190013 366 1211118143630 367 1281183205925 368 1355213438251 369 1433428624157 370 1516060002604 371 1603351796595 372 1695560956676 373 1792958794470 374 1895830764007 375 2004478214804 376 2119218186566 377 2240385316560 378 2368331658217 379 2503428723693 380 2646067358056 381 2796659934849 382 2955640260247 383 3123465962282 384 3300618438528 385 3487605419296 386 3684960996109 387 3893248381123 388 4113059989766 389 4345020444032 390 4589786726470 391 4848051408503 392 5120542919522 393 5408029027471 394 5711317196636 395 6031258376655 396 6368747471089 397 6724727417106 398 7100189816722 399 7496179341912 400 7913794502431 401 8354192442708 402 8818589874868 403 9308268252532 404 9824574931236 405 10368928762126 406 10942821455966 407 11547823676167 408 12185586643204 409 12857848716524 410 13566437314087 411 14313276037966 412 15100386888854 413 15929898030163 414 16804046345946 415 17725185839973 416 18695790627592 417 19718464038812 418 20795942030323 419 21931103107972 420 23126972221513 421 24386731512751 422 25713724803690 423 27111469258470 424 28583660461240 425 30134185131394 426 31767126873131 427 33486779965013 428 35297655916988 429 37204498446777 430 39212290855031 431 41326272359908 432 43551946397176 433 45895098353509 434 48361804960331 435 50958453570016 436 53691752674830 437 56568752936465 438 59596858969757 439 62783852194817 440 66137904095082 441 69667601076766 442 73381959261883 443 77290451615979 444 81403024459081 445 85730126967933 446 90282729667807 447 95072356547317 448 100111105631590 449 105411684034496 450 110987430852158 451 116852355310730 452 123021162310908 453 129509293977090 454 136332958009040 455 143509173039057 456 151055800103131 457 158991592032187 458 167336228460868 459 176110369648662 460 185335695256016 461 195034963105856 462 205232052135419 463 215952026415996 464 227221182811569 465 239067120766503 466 251518795000735 467 264606591710154 468 278362386831134 469 292819629092557 470 308013404525685 471 323980527027389 472 340759609577472 473 358391163128332 474 376917675226149 475 396383717826071 476 416836034180265 477 438323656430174 478 460898001399671 479 484612999001106 480 509525197840722 481 535693905247333 482 563181303794555 483 592052604053669 484 622376172903742 485 654223700326722 486 687670340688023 487 722794894659203 488 759679964884210 489 798412154453659 490 839082238133281 491 881785379072342 492 926621317133132 493 973694605278075 494 1023114816818072 495 1074996803319537 496 1129460922348712 497 1186633319047267 498 1246646176373866 499 1309638022264566 500 1375754004706111 501 1445146226860064 502 1517974049068970 503 1594404454693972 504 1674612381654228 505 1758781121504013 506 1847102683507804 507 1939778230031491 508 2037018475936157 509 2139044163804930 510 2246086502029762 511 2358387683195155 512 2476201364719439 513 2599793234364364 514 2729441537103105 515 2865437692269682 516 3008086871027963 517 3157708669509582 518 3314637741852517 519 3479224534452823 520 3651835979395857 521 3832856295609268 522 4022687748352125 523 4221751522949661 524 4430488556733639 525 4649360491967956 526 4878850586556290 527 5119464753583624 528 5371732558119088 529 5636208350772804 530 5913472358818346 531 6204131922286733 532 6508822687653118 533 6828209955991345 534 7162989988696513 535 7513891477317294 536 7881676971891736 537 8267144483433425 538 8671129045615325 539 9094504462129647 540 9538185013945029 541 10003127364011940 542 10490332423692128 543 11000847428939826 544 11535767979847845 545 12096240303974917 546 12683463484774855 547 13298691928216498 548 13943237797569155 549 14618473701489815 550 15325835353238537 551 16066824500328363 552 16843011828480060 553 17656040153697560 554 18507627593404635 555 19399571044305195 556 20333749644082073 557 21312128560797135 558 22336762771288112 559 23409801189028750 560 24533490788025735 561 25710181099134781 562 26942328709649219 563 28232502161069549 564 29583386857983435 565 30997790401964831 566 32478647946687977 567 34029028006445975 568 35652138296419210 569 37351332058064964 570 39130114427689892 571 40992149323321765 572 42941266388932979 573 44981468492135993 574 47116939294157886 575 49352051412430379 576 51691374671673708 577 54139684988690993 578 56701973365199215 579 59383455558034835 580 62189581878123006 581 65126047715243871 582 68198804214091933 583 71414069727138751 584 74778341445381585 585 78298407860191349 586 81981361431401498 587 85834612146519479 588 89865901317001719 589 94083316329067129 590 98495305667382124 591 103110694960912964 592 107938703339968502 593 112988960889959124 594 118271526458007494 595 123796906635247200 596 129576075139773091 597 135620493459627074 598 141942131947733855 599 148553492269622123 600 155467630358852322 601 162698180823717711 602 170259381924999526 603 178166102110335575 604 186433867187766717 605 195078889171465751 606 204118095840680031 607 213569162093836200 608 223450542099300573 609 233781503373000785 610 244582161742576530 611 255873518382598103 612 267677497833953064 613 280016988248038652 614 292915882724461893 615 306399123038359031 616 320492744579123759 617 335223923858901006 618 350621027360541044 619 366713663147693905 620 383532733956982221 621 401110493258743007 622 419480602953769326 623 438678194263904785 624 458739930425749860 625 479704072819135459 626 501610549084009497 627 524501024930817294 628 548418978139398877 629 573409776533351411 630 599520758360081520 631 626801316948239920 632 655302988010747091 633 685079541549664449 634 716187076665845121 635 748684121323609897 636 782631735301390379 637 818093618475964074 638 855136222602292738 639 893828868834039174 640 934243869074301238 641 976456653509659898 642 1020545902337326259 643 1066593684150497026 644 1114685598915322013 645 1164910928116999005 646 1217362789928227651 647 1272138302101791629 648 1329338750352448452 649 1389069765058868238 650 1451441503966490927 651 1516568843851834452 652 1584571578740751656 653 1655574627784275708 654 1729708250287707971 655 1807108271145254312 656 1887916314083200392 657 1972280046113952619 658 2060353430506983463 659 2152296991844017588 660 2248278090358441492 661 2348471209297871882 662 2453058252408521748 663 2562228855453926556 664 2676180708760829596 665 2795119894895315274 666 2919261238346461602 667 3048828671518919538 668 3184055613801499692 669 3325185368214384231 670 3472471532287209221 671 3626178427890952959 672 3786581546550758636 673 3953968015192191037 674 4128637078729066545 675 4310900604678863640 676 4501083606090148704 677 4699524788223179373 678 4906577115133621731 679 5122608401866680816 680 5348001928284132134 681 5583157080502982754 682 5828490015836135974 683 6084434357509800672 684 6351441914904664759 685 6629983435904641238 686 6920549386965090383 687 7223650767800333282 688 7539819956162764794 689 7869611589957397925 690 8213603482012999647 691 8572397575113226253 692 8946620932467427457 693 9336926771593108942 694 9743995536644180996 695 10168536017557534077 696 10611286510894843223 697 11073016031171258343 698 11554525567402113507 699 12056649394089987281 700 12580256431234085818 701 13126251663051595454 702 13695577609832265380 703 14289215863105365025 704 14908188678393232255 705 15553560636234763754 706 16226440365603709024 707 16927982340951410601 708 17659388746838403120 709 18421911421957377158 710 19216853876367902715 711 20045573394336900109 712 20909483216460432942 713 21810054814100808712 714 22748820249659607110 715 23727374636392457797 716 24747378691151106280 717 25810561394453861632 718 26918722751136250625 719 28073736666734347448 720 29277553932710263962 721 30532205336461909740 722 31839804889108351813 723 33202553187811895144 724 34622740905514361985 725 36102752425732785205 726 37645069615171888529 727 39252275752728675722 728 40927059607555933739 729 42672219685726791877 730 44490668638084843192 731 46385437849864559618 732 48359682204581291784 733 50416685043873621020 734 52559863315748416609 735 54792772934055110879 736 57119114341604128307 737 59542738300988221721 738 62067651905488027506 739 64698024835419735241 740 67438195852317175055 741 70292679557662204563 742 73266173408587121319 743 76363565018722662397 744 79589939736654892514 745 82950588531705048342 746 86451016179590334807 747 90096949779290744625 748 93894347593803966716 749 97849408247846387423 750 101968580275322993657 751 106258572051454918226 752 110726362102596320504 753 115379209830547408106 754 120224666644645162858 755 125270587540500411558 756 130525143118940572447 757 135996832086207037142 758 141694494229328738082 759 147627323910009198290 760 153804884071366617429 761 160237120803322747356 762 166934378461440680384 763 173907415387609459383 764 181167420227940932242 765 188726028899012359017 766 196595342198460274042 767 204787944113996541181 768 213316920827553674176 769 222195880471742300473 770 231438973636159421722 771 241060914684007009599 772 251077003877489980214 773 261503150375969921317 774 272355896106359882625 775 283652440573465510909 776 295410666610935561536 777 307649167144459122466 778 320387272969179604123 779 333645081617181438200 780 347443487318443463853 781 361804212135591599411 782 376749838277469283000 783 392303841676585281342 784 408490626837249549832 785 425335563044526475280 786 442865021942764840044 787 461106416579217747847 788 480088241923709631690 789 499840116965555858574 790 520392828401105835731 791 541778376019218322643 792 564030019800660009438 793 587182328845222114577 794 611271232145475691972 795 636334071327825988276 796 662409655382992729510 797 689538317513935985240 798 717761974126830069047 799 747124186100931278022 800 777670222366801688234 801 809447125937027982128 802 842503782423109640571 803 876890991191543026213 804 912661539197336299700 805 949870277657438829690 806 988574201607357540584 807 1028832532513475304672 808 1070706803989828232240 809 1114260950802605326341 810 1159561401217059401191 811 1206677172881536410484 812 1255679972309835656156 813 1306644298168757735432 814 1359647548439141086925 815 1414770131670259745783 816 1472095582403543061920 817 1531710680999354913538 818 1593705577951186498321 819 1658173922935732761683 820 1725212998692311179345 821 1794923859995873341219 822 1867411477826898686675 823 1942784889019238650154 824 2021157351499939927422 825 2102646505419998686109 826 2187374540301707171141 827 2275468368520697511844 828 2367059805260895076764 829 2462285755280907026331 830 2561288406643734541717 831 2664215431770063961940 832 2771220195981820386594 833 2882461973919508256703 834 2998106174015974508482 835 3118324571434937826142 836 3243295549674263965804 837 3373204351268756256449 838 3508243337811183994194 839 3648612259754612819604 840 3794518536234955427487 841 3946177545406996438641 842 4103812925554727122232 843 4267656887501405027550 844 4437950538603835323768 845 4614944218890721851389 846 4798897849655065291921 847 4990081295097206153022 848 5188774737356097936670 849 5395269065564576466144 850 5609866279295989124172 851 5832879907079881014623 852 6064635440386152747465 853 6305470783800150914795 854 6555736721822783764761 855 6815797403065853153891 856 7086030842314069816491 857 7366829441275035141810 858 7658600528528863200203 859 7961766919553282693745 860 8276767497379340347761 861 8604057814811738082634 862 8944110718815718655469 863 9297416998066818403672 864 9664486054315717162480 865 10045846598631026610334 866 10442047373226558806907 867 10853657900006895007423 868 11281269256596252097962 869 11725494881060432177518 870 12186971406149680575239 871 12666359524353383293791 872 13164344884662180860041 873 13681639022415034467373 874 14218980323199699297415 875 14777135022276822152703 876 15356898240574414731255 877 15959095058821934216953 878 16584581630955081321086 879 17234246338466248142477 880 17909010986922417924399 881 18609832046438556186085 882 19337701937425692076703 883 20093650363522578803178 884 20878745693134987634069 885 21694096391620559346734 886 22540852505655938646668 887 23420207201962179619240 888 24333398362046103380719 889 25281710235281123425575 890 26266475152115346370378 891 27289075299888008941201 892 28350944563181819033881 893 29453570431360816028846 894 30598495975371301885358 895 31787321896635576889448 896 33021708650277283394152 897 34303378645700465995569 898 35634118526934266123806 899 37015781535971157750574 900 38450289961696357619116 901 39939637677856244093457 902 41485892772862969266407 903 43091200275118014067375 904 44757784976866015703652 905 46487954360512900975839 906 48284101630649313234589 907 50148708855981908689224 908 52084350224660145503842 909 54093695417488006649785 910 56179513102772851843098 911 58344674557607662511485 912 60592157419622526701175 913 62925049574329526115311 914 65346553182401342532699 915 67859988852358035279499 916 70468799963328802611112 917 73176557143737800543177 918 75986962910930770120541 919 78903856477991897549774 920 81931218733143109227645 921 85073177398402929373680 922 88334012373299577462711 923 91718161270772798649585 924 95230225151490355563144 925 98874974464202441161429 926 102657355198822438653091 927 106582495260379454259609 928 110655711071026677311969 929 114882514408809313367195 930 119268619490907065465257 931 123819950310651540587823 932 128542648236602721656619 933 133443079883622281391503 934 138527845264837630506432 935 143803786235115933278192 936 149277995235594982731369 937 154957824350618352603836 938 160850894687321500371473 939 166965106089994164510670 940 173308647200215196389868 941 179890005875716773419316 942 186717979979776554563236 943 193801688554983301021167 944 201150583394034135623499 945 208774461022358206909051 946 216683475106145321791154 947 224888149301588937625004 948 233399390559907258889277 949 242228502905035894431969 950 251387201699610878712899 951 260887628417293539950432 952 270742365938185374619511 953 280964454386622055192496 954 291567407529303302436677 955 302565229754369998639874 956 313972433650679171639802 957 325804058209300608987468 958 338075687667870396516474 959 350803471021334447607233 960 364004142221198766086455 961 377695041088431861174586 962 391894134963721640130558 963 406620041121954345150927 964 421892049976314255875066 965 437730149100711829625018 966 454155048097753566739423 967 471188204342926835092127 968 488851849634154523313231 969 507169017779492011881956 970 526163573154198118246442 971 545860240262195270031145 972 566284634335371537006086 973 587463293008135224654374 974 609423709103050476929505 975 632194364567522763603666 976 655804765599903382183641 977 680285479007714562119444 978 705668169839080807705748 979 731985640332986528292396 980 759271870232350761474439 981 787562058508655475347462 982 816892666545224340746671 983 847301462831217103421023 984 878827569216756803098618 985 911511508784809498513834 986 945395255393783850999955 987 980522284950265520845770 988 1016937628469648543897575 989 1054687926988131848956937 990 1093821488387898869059219 991 1134388346203276199803288 992 1176440320474024681269914 993 1220031080718179331209693 994 1265216211095224811742665 995 1312053277836956678369392 996 1360601899021766065258328 997 1410923816774965531029242 998 1463082971976184875591893 999 1517145581562077771245214 1000 1573180218511021585792226