1 1 2 19 3 85 4 311 5 631 6 1615 7 2409 8 4991 9 6898 10 11989 11 14653 12 26435 13 28575 14 45771 15 53635 16 79887 17 83539 18 131062 19 130341 20 196241 21 204765 22 278407 23 279865 24 424235 25 394406 26 542925 27 558778 28 749199 29 707311 30 1019065 31 923553 32 1278255 33 1245505 34 1587241 35 1520079 36 2145278 37 1874199 38 2476479 39 2428875 40 3149321 41 2825803 42 3890535 43 3418845 44 4557083 45 4352638 46 5317435 47 4879729 48 6790395 49 5784066 50 7493714 51 7100815 52 8886825 53 7890535 54 10616782 55 9246043 56 12023319 57 11078985 58 13438909 59 12117421 60 16680485 61 13845903 62 17547507 63 16617282 64 20452207 65 18030825 66 23664595 67 20151189 68 25980629 69 23788525 70 28881501 71 25411753 72 34427918 73 28398315 74 35609781 75 33524510 76 40536051 77 35299077 78 46148625 79 38950161 80 50408697 81 45261139 82 53690257 83 47458405 84 63681915 85 52713109 86 64958055 87 60121435 88 73133123 89 62742331 90 82700122 91 68837175 92 87038015 93 78502005 94 92714851 95 82245171 96 108651675 97 88529379 98 109897254 99 101076394 100 122660266 101 104060503 102 134915485 103 112550985 104 142617825 105 129206715 106 149920165 107 131079709 108 173779958 109 141158271 110 175674817 111 159306915 112 192447783 113 163047475 114 210500715 115 176594815 116 219973721 117 197110350 118 230230999 119 201245451 120 267692285 121 214534706 122 263072157 123 240193255 124 287224983 125 246503906 126 315728358 127 260144769 128 327235567 129 290601825 130 342585675 131 294500053 132 387352055 133 313991469 134 382872591 135 352588918 136 416943149 137 352275499 138 451981975 139 373301181 140 472744569 141 414776965 142 482823307 143 418709475 144 551060526 145 446313241 146 539567985 147 491645610 148 582875889 149 492884551 150 636965690 151 519885753 152 650531931 153 576252022 154 670682463 155 582761943 156 755380125 157 607573359 158 740053059 159 670695475 160 806578905 161 674194785 162 859961641 163 705911925 164 878824733 165 785913655 166 901709695 167 777796489 168 1021982115 169 816130758 170 1001549071 171 899092218 172 1063260795 173 895745215 174 1142307265 175 950124054 176 1170584211 177 1029980785 178 1192104289 179 1026625861 180 1353670418 181 1073283303 182 1307906325 183 1176901755 184 1396806215 185 1182619569 186 1491538095 187 1224096967 188 1517595719 189 1346096202 190 1562658249 191 1330863553 192 1738437595 193 1387488195 194 1682058201 195 1532620125 196 1798844526 197 1506138679 198 1920451486 199 1568239401 200 1968480346 201 1712851065 202 1977149557 203 1703912199 204 2208353465 205 1783081693 206 2138468715 207 1930508770 208 2282771025 209 1909886673 210 2454927585 211 1982119653 212 2453956385 213 2159999005 214 2490514471 215 2157291195 216 2788860998 217 2224839177 218 2682007149 219 2413856775 220 2875519373 221 2387126925 222 3026831385 223 2472973665 224 3079316295 225 2720612588 226 3097902025 227 2655238069 228 3445564335 229 2750058711 230 3355301485 231 3000421545 232 3530189201 233 2947295755 234 3745096650 235 3079108999 236 3768517931 237 3310763685 238 3823663569 239 3262808881 240 4284739245 241 3373402803 242 4076159414 243 3666152623 244 4306075833 245 3649745646 246 4563671845 247 3724494075 248 4609453023 249 4033964425 250 4683574214 251 3969126253 252 5167974702 253 4100861845 254 4942750611 255 4480614265 256 5235769583 257 4362470659 258 5521434675 259 4514945391 260 5607586575 261 4879031278 262 5595501007 263 4784350825 264 6216315455 265 4978927585 266 5965837911 267 5333098135 268 6267019779 269 5236114591 270 6699189442 271 5393580753 272 6673680093 273 5851159875 274 6693234481 275 5779231118 276 7398231275 277 5887339719 278 7092722439 279 6370668594 280 7586714289 281 6234839803 282 7880762335 283 6414248205 284 7903055183 285 6990839535 286 7955480025 287 6807359427 288 8817402990 289 6977261126 290 8479951579 291 7524997215 292 8831875965 293 7370051095 294 9341266590 295 7646092651 296 9354127209 297 8187774034 298 9364806469 299 7997142375 300 10426122610 301 8235997605 302 9877829307 303 8845142755 304 10412551467 305 8736764793 306 10948788418 307 8882874309 308 10978012947 309 9566833725 310 11072476917 311 9354952153 312 12122515125 313 9597925275 314 11543893821 315 10485504942 316 12113500071 317 10098039439 318 12743214025 319 10364228083 320 12905342617 321 11141775265 322 12809700915 323 10888556799 324 14076214229 325 11270151450 326 13412326575 327 11998453035 328 14103582773 329 11755267161 330 14932359445 331 12003613053 332 14759563955 333 12928224702 334 14778133291 335 12715400259 336 16358061555 337 12897918099 338 15506484402 339 13859035375 340 16393776899 341 13532822109 342 17082752142 343 13887542866 344 17063455395 345 15010559275 346 17019159085 347 14498327629 348 18697766285 349 14835483951 350 18052357026 351 15967081350 352 18730270515 353 15527403235 354 19569634915 355 16034816143 356 19512864941 357 17105863335 358 19505891359 359 16610312521 360 21724016258 361 16986169842 362 20392382757 363 18235450010 364 21408361425 365 17919336765 366 22361133345 367 18141127089 368 22357575255 369 19492389094 370 22469771811 371 19008298815 372 24414123555 373 19356879015 374 23257842373 375 20952832010 376 24354727439 377 20211411825 378 25575827838 379 20632737261 380 25578248181 381 22112305365 382 25286407507 383 21517663105 384 27815023195 385 22273717587 386 26362275705 387 23583192810 388 27532636869 389 22898045431 390 29119782375 391 23379642235 392 28868273406 393 25032504505 394 28616634901 395 24577551591 396 31434758534 397 24840597279 398 29796548619 399 26689274865 400 31507912122 401 25856962003 402 32544170235 403 26390526975 404 32362816433 405 28559778709 406 32374331781 407 27462637947 408 35440167665 409 27982933371 410 33878552167 411 29943417415 412 35003356335 413 29190867189 414 36679666630 415 29946253555 416 36526136625 417 31730600385 418 36287846787 419 30821665141 420 40183288365 421 31414372503 422 37660273407 423 33660370642 424 39381660185 425 32948282834 426 41039981095 427 33354780327 428 40765789499 429 35590305375 430 40988532705 431 34507149553 432 44639098086 433 35152125555 434 42271944363 435 37936625485 436 43900222281 437 36477883965 438 45863278725 439 37141384281 440 46147000613 441 39898487268 442 45355411575 443 38513670445 444 49544450565 445 39590410861 446 46986499635 447 41895186835 448 49269366663 449 40642963651 450 51691639172 451 41406491359 452 50707764725 453 44190289005 454 50449523311 455 43436257425 456 55295214135 457 43617905259 458 52251115509 459 46679755342 460 54920987465 461 45165175903 462 57008009355 463 45954068625 464 56504953857 465 49534765155 466 55998619345 467 47562812389 468 61301318850 469 48544214301 470 58503070981 471 51643735515 472 60478048211 473 50096335785 474 62904510015 475 51407272446 476 62587335261 477 54428910430 478 61993368739 479 52643172961 480 68559206925 481 53555236425 482 64094653257 483 57306556725 484 66720293566 485 55862038149 486 69656899837 487 56249135049 488 69104901873 489 60002513625 490 69345167274 491 58120049053 492 74700102305 493 59088053629 494 70765387425 495 63779204614 496 73779878511 497 61216912977 498 76645324075 499 62001498501 500 76662714766 501 66112701565 502 75413398807 503 64013554585 504 82936854462 505 65662177393 506 77916375055 507 69371114430 508 80905023159 509 67122965071 510 85131671035 511 68411540835 512 83772314351 513 72831683298 514 82886942521 515 71019671535 516 90377167575 517 71502669037 518 85783962429 519 76138343275 520 89991847575 521 73680217003 522 92701594282 523 74818114365 524 91589516483 525 80760544590 526 90902665675 527 77152694067 528 99499657935 529 78317702018 530 94599624115 531 83585970058 532 97651346859 533 80747320725 534 101328864565 535 82711296379 536 100574584299 537 87263198185 538 99486177229 539 84753919098 540 109655153498 541 85662168303 542 102478034307 543 91229080755 544 106784144445 545 89070869001 546 111172037625 547 89526026229 548 109557680189 549 95509038894 550 109805391242 551 92191623051 552 118728528275 553 93830937849 554 111859454661 555 100522663365 556 116096667291 557 96254442559 558 121042703286 559 97693495875 560 121434551073 561 104048242195 562 118461956257 563 100469347525 564 128995636115 565 102882956725 566 121870715895 567 109034083851 568 126830059223 569 104821185691 570 132825951165 571 106302734253 572 130218646725 573 113123402005 574 129339829113 575 110380435190 576 141079323886 577 110841719619 578 132567961394 579 117936496575 580 138803417951 581 114327297645 582 142974947085 583 115620009355 584 141735990165 585 124376630850 586 140030970805 587 118727796349 588 152901784710 589 120376821573 590 145275760369 591 128021787715 592 149724135513 593 123657019795 594 155567706646 595 126985879581 596 153287095361 597 133300349085 598 151945705125 599 128738158201 600 167320829410 601 130466163003 602 156483954495 603 139002901722 604 161684469183 605 135371399486 606 168057712345 607 135754666209 608 166609034955 609 144832536915 610 165998531067 611 139438256175 612 179214378842 613 141202341975 614 168774611871 615 151561943905 616 176177693307 617 144924115339 618 181769840775 619 146812352541 620 181238964273 621 156382404970 622 177744090907 623 151146275379 624 194035537125 625 154064942031 626 182360580225 627 162340367205 628 188955314649 629 156568710261 630 199224593898 631 158532182553 632 194400253551 633 168480170505 634 191862749341 635 164151349239 636 208586292725 637 165279685950 638 196920333577 639 175290272194 640 206485642777 641 168823196803 642 211693730035 643 170940076245 644 209674578135 645 183369751575 646 206882579181 647 175233495529 648 225898344749 649 177556569913 650 214132877550 651 189111330045 652 219538608675 653 181824635935 654 227970607665 655 185829533443 656 225744924261 657 195891576870 658 223350076059 659 188599987621 660 244419146705 661 190899960903 662 228068648007 663 202905788625 664 236864899355 665 198128616939 666 245636269338 667 197951593015 668 241894708079 669 210202761525 670 241592604921 671 202884016659 672 261741885075 673 205144679715 674 245060443881 675 220385395868 676 253816665738 677 210065472919 678 263321672125 679 213267274011 680 263091127019 681 225695235865 682 257123620071 683 217611987805 684 279617679798 685 222285839869 686 263863314454 687 233754990435 688 273121270515 689 225472037625 690 285200626225 691 227988106053 692 278576761865 693 243493033146 694 275468224951 695 235553045211 696 300066082085 697 236064756817 698 281874195069 699 250520139175 700 295488580794 701 241474943503 702 303374545650 703 244284971859 704 299686189171 705 261724264915 706 295020661465 707 250681751727 708 320324024135 709 252688188471 710 304661506717 711 268678210578 712 313146974021 713 258470160345 714 325011403365 715 264205678725 716 319280642771 717 277338754885 718 315595937899 719 267248676241 720 347719191906 721 271135322865 722 322737226998 723 286739238255 724 333791107233 725 278967702266 726 346473550190 727 279342904569 728 343566340425 729 296958363556 730 340467398535 731 285606892455 732 366016445805 733 288679470255 734 344681414691 735 310228379910 736 357738835575 737 295275372417 738 370355392786 739 298248147381 740 367794685959 741 316581996375 742 361157677485 743 304758099145 744 391803506955 745 311010151681 746 367780701285 747 327368077690 748 380694156737 749 315771018981 750 398103808190 751 318097128753 752 389826910623 753 337375731505 754 384016824675 755 328047910143 756 418635918822 757 328385157159 758 392022007959 759 348573256825 760 410485648461 761 335381133403 762 420133801935 763 340050274839 764 413898564983 765 363615025882 766 408835598995 767 346255305075 768 445040414555 769 349707833091 770 423200634153 771 370810006015 772 431508828645 773 357040906615 774 448080663390 775 364254844518 776 441850130589 777 383770358235 778 435062863189 779 368317988823 780 476644858875 781 372358416709 782 444213202465 783 395229825958 784 462071680542 785 383378789529 786 475617585595 787 383617958949 788 468409129169 789 406669820125 790 466973480229 791 392781367275 792 504472282454 793 395646678225 794 471971348301 795 423208844725 796 487722453711 797 403490474479 798 507096222435 799 407647680931 800 504151441530 801 432796599238 802 491282278057 803 416120509695 804 532696681215 805 425416909335 806 501420012525 807 445069740235 808 519365970473 809 428345380171 810 542635795471 811 432596914653 812 529916693889 813 458454364005 814 521790120993 815 445430424675 816 567262807905 817 445615676145 818 531675734049 819 474838833150 820 554538406523 821 454331270503 822 568924930885 823 458774575065 824 561741966135 825 491234645030 826 554626476591 827 467758877869 828 600388227470 829 472300192911 830 568978817545 831 500423876115 832 584421815025 833 483195089574 834 602881407315 835 490789584559 836 593974755303 837 516061098234 838 585611637679 839 495504775081 840 644870714565 841 500267632262 842 596873077557 843 529961383255 844 616439212083 845 514978508298 846 639547042198 847 516814106754 848 630351169545 849 545211097425 850 626017373846 851 524522703135 852 671759690555 853 529414857735 854 633740826213 855 567327189558 856 654218827619 857 539415334459 858 676215802125 859 544468371021 860 670917561645 861 578625551295 862 655635841507 863 554680864225 864 714260772390 865 565215230665 866 667890385545 867 593067195710 868 691924984047 869 570736709133 870 720795884215 871 575820225675 872 704520930561 873 610675656342 874 693079795335 875 593827909554 876 750709457025 877 591559419519 878 705686301339 879 626454343075 880 738638637141 881 602425898803 882 758071258092 883 607914937605 884 742396473675 885 649917875335 886 731759738455 887 619005460249 888 795100812765 889 626688748521 890 752217806359 891 663211469767 892 769094809815 893 636028757589 894 796008549865 895 647800918291 896 788310480903 897 679757101875 898 772216309369 899 653239195983 900 846110514868 901 659167403365 902 786723335821 903 700059796425 904 813769947725 905 677241764193 906 839615491095 907 676751378109 908 825779039459 909 717809349694 910 825288891075 911 688768867153 912 885066874695 913 695408008465 914 828740199921 915 742625007405 916 855268259121 917 709450627677 918 886915351498 919 713283283641 920 881384721665 921 755044316265 922 858138342157 923 726140841975 924 933131100495 925 739195330794 926 873127303875 927 776376694530 928 904123822305 929 744839768611 930 941160537945 931 753900946506 932 916608979805 933 795170933005 934 903693435391 935 772405186177 936 983777756850 937 770829565899 938 922340071719 939 815823648375 940 957602898689 941 784076602303 942 981230974785 943 790843356595 944 968024411427 945 849386703462 946 951830379915 947 804266383429 948 1029647506035 949 811481851125 950 976738176474 951 858333352315 952 1004416045941 953 824843588635 954 1034149298170 955 839774901943 956 1014733561991 957 880959387055 958 1000220286259 959 848631677091 960 1096954122445 961 852920591106 962 1017549492075 963 904187832682 964 1049128271733 965 875505051045 966 1088824577775 967 874391438889 968 1070742717646 969 925527327915 970 1061378724831 971 888949152253 972 1140173465753 973 899282545029 974 1068733565931 975 957962873250 976 1106107652961 977 911125612819 978 1140047758875 979 919363376143 980 1135070895906 981 973709753358 982 1104280932007 983 933714432505 984 1198804535705 985 950373506449 986 1122673018951 987 999197708685 988 1158317657325 989 956815055925 990 1211804887666 991 964483091553 992 1180536240015 993 1020307109505 994 1163121346563 995 989559062031 996 1254562936175 997 988053893079 998 1178028471519 999 1047261168822 1000 1230300994846