1 1 2 5 3 19 4 37 5 101 6 95 7 295 8 293 9 505 10 505 11 1211 12 703 13 2029 14 1475 15 1919 16 2341 17 4625 18 2525 19 6499 20 3737 21 5605 22 6055 23 11639 24 5567 25 12601 26 10145 27 13627 28 10915 29 23549 30 9595 31 28831 32 18725 33 23009 34 23125 35 29795 36 18685 37 49285 38 32495 39 38551 40 29593 41 67241 42 28025 43 77659 44 44807 45 51005 46 58195 47 101615 48 44479 49 101137 50 63005 51 87875 52 75073 53 146069 54 68135 55 122311 56 86435 57 123481 58 117745 59 201899 60 71003 61 223261 62 144155 63 148975 64 149797 65 204929 66 115045 67 296275 68 171125 69 221141 70 148975 71 352871 72 147965 73 383689 74 246425 75 239419 76 240463 77 357245 78 192755 79 486799 80 236441 81 367921 82 336205 83 564899 84 207385 85 467125 86 388295 87 447431 88 354823 89 697049 90 255025 91 598555 92 430643 93 547789 94 508075 95 656399 96 355775 97 903265 98 505685 99 611555 100 466237 101 1020101 102 439375 103 1082119 104 594497 105 566105 106 730345 107 1213595 108 504199 109 1283149 110 611555 111 936415 112 690595 113 1430129 114 617405 115 1175539 116 871313 117 1024645 118 1009495 119 1364375 120 562267 121 1611721 122 1116305 123 1277579 124 1066747 125 1575101 126 744875 127 2032255 128 1198373 129 1475521 130 1024645 131 2230931 132 851333 133 1917205 134 1481375 135 1376327 136 1355125 137 2552585 138 1105705 139 2666299 140 1102415 141 1930685 142 1764355 143 2457119 144 1182205 145 2378449 146 1918445 147 1921603 148 1823545 149 3285749 150 1197095 151 3420151 152 1904207 153 2335625 154 1786225 155 2911931 156 1426387 157 3845245 158 2433995 159 2775311 160 1891225 161 3433505 162 1839605 163 4304179 164 2487917 165 2323909 166 2824495 167 4629575 168 1642265 169 4457545 170 2335625 171 3281995 172 2873383 173 5147789 174 2237155 175 3717295 176 2834951 177 3836081 178 3485245 179 5703299 180 1887185 181 5896981 182 2992775 183 4241959 184 3410227 185 4977785 186 2738945 187 5600875 188 3759755 189 4019965 190 3281995 191 6931391 192 2846143 193 7151809 194 4516325 195 3893651 196 3742069 197 7606565 198 3057775 199 7840999 200 3692093 201 5629225 202 5100505 203 6946955 204 3251375 205 6791341 206 5410595 207 5877695 208 4749889 209 7870289 210 2830525 211 9349411 212 5404553 213 6704549 214 6067975 215 7843559 216 3992711 217 8505145 218 6415745 219 7290091 220 4525507 221 9384125 222 4682075 223 11039839 224 5523875 225 6363505 226 7150645 227 11645555 228 4568797 229 11956549 230 5877695 231 6787655 232 6899857 233 12595049 234 5123225 235 10263115 236 7470263 237 9249181 238 6821875 239 13594799 240 4492379 241 13939441 242 8058605 243 9933859 244 8260657 245 10214837 246 6387895 247 13186471 248 8447483 249 10733081 250 7875505 251 15750251 252 5512075 253 14094829 254 10161275 255 8875375 256 9586981 257 16908545 258 7377605 259 14539075 260 7582373 261 11892245 262 11154655 263 18122279 264 6741637 265 14752969 266 9586025 267 13243931 268 10962175 269 19392749 270 6881635 271 19829071 272 10827125 273 11372545 274 12762925 275 15259811 276 8182217 277 21177205 278 13331495 279 14559655 280 8729935 281 22109081 282 9653425 283 22585099 284 13056227 285 12471581 286 12285595 287 19836095 288 9456125 289 22722337 290 11892245 291 17162035 292 14196493 293 25067909 294 9608015 295 20391799 296 14440505 297 16502297 298 16428745 299 23615531 300 8858503 301 22909405 302 17100755 303 19381919 304 15214159 305 22549361 306 11678125 307 28840195 308 13218065 309 20560261 310 14559655 311 29983511 312 11295443 313 30566329 314 19226225 315 15046475 316 18011563 317 31754525 318 13876555 319 28517839 320 15129497 321 23058305 322 17167525 323 30057875 324 13613077 325 25567429 326 21520895 327 24379831 328 19701613 329 29976425 330 11619545 331 36155131 332 20901263 333 24888925 334 23147875 335 29923775 336 13121305 337 38159185 338 22287725 339 27172451 340 17283625 341 34914341 342 16409975 343 34689943 344 22754087 345 22335241 346 25738945 347 41661515 348 16554947 349 42386749 350 18586475 351 27649183 352 22675975 353 43862369 354 19180405 355 35639971 356 25790813 357 25923125 358 28516495 359 46139399 360 14944465 361 44576281 362 29484905 363 30622699 364 22146535 365 38752589 366 21209795 367 49296175 368 27246899 369 33956705 370 24888925 371 43090355 372 20268193 373 51755989 374 28004375 375 29926919 376 29773195 377 47780921 378 20099825 379 54296299 380 24286763 381 38612845 382 34656955 383 56035199 384 22769087 385 36081745 386 35759045 387 39217795 388 33420805 389 58712549 390 19468255 391 53830375 392 29633141 393 42387689 394 38032825 395 49166699 396 22627535 397 62413165 398 39204995 399 36426895 400 29498941 401 64320401 402 28146125 403 58498099 404 37743737 405 37160021 406 34734775 407 59684135 408 25747375 409 68250649 410 33956705 411 48499115 412 40038403 413 59560205 414 29388475 415 57054799 416 37993025 417 50659681 418 39351445 419 73384499 420 20945885 421 74441221 422 46747055 423 51315575 424 42798217 425 58279625 426 33522745 427 65861995 428 44903015 429 46685261 430 39217795 431 79877231 432 31900807 433 80995249 434 42525725 435 45190531 436 47476513 437 75641861 438 36450455 439 84411799 440 35837123 441 51074185 442 46920625 443 86742059 444 34647355 445 70401949 446 55199195 447 62429231 448 44190115 449 90317249 450 31817525 451 81428851 452 52914773 453 64982869 454 58227775 455 60454055 456 36179933 457 95235145 458 59782745 459 63024875 460 43494943 461 97759661 462 33938275 463 99038479 464 55128209 465 55326689 466 62975245 467 101629475 468 37911865 469 87401125 470 51315575 471 73059655 472 59156407 473 94045049 474 46245905 475 81893899 476 50481875 477 73764845 478 67973995 479 109672799 480 35933275 481 99999265 482 69697205 483 65236595 484 59633677 485 91229765 486 49669295 487 115264135 488 65415473 489 81779401 490 51074185 491 118129691 492 47270423 493 108914125 494 65932355 495 61767055 496 67493371 497 104096945 498 53665405 499 124002499 500 58278737 501 87961925 502 78751255 503 127010519 504 43649675 505 103030201 506 70474145 507 84693355 508 75193435 509 131613149 510 44376875 511 113188255 512 76695845 513 88561873 514 84542725 515 109294019 516 54594277 517 123055765 518 72695375 519 97807991 520 60044197 521 141149321 522 59461225 523 142782139 524 82544447 525 70628605 526 90611395 527 133343375 528 53864069 529 141611185 530 73764845 531 101958995 532 70936585 533 136431989 534 66219655 535 122573095 536 86808575 537 108362681 538 96963745 539 122476907 540 50924099 541 158047741 542 99145355 543 112042639 544 86603125 545 129598049 546 56862725 547 163368115 548 94445645 549 112746805 550 76299055 551 153044951 552 64794313 553 143605705 554 105886025 555 94577915 556 98653063 557 172498445 558 72798275 559 157570111 560 69750095 561 106416625 562 110545405 563 178136579 564 71435345 565 144443029 566 112925495 567 108536695 568 103391203 569 183896249 570 62357905 571 185843371 572 90913403 573 131696429 574 99180475 575 146663039 576 75647485 577 191767105 578 113611685 579 135884371 580 88002613 581 166645205 582 85810175 583 176889559 584 112420877 585 103489145 586 125339545 587 201917435 588 71099311 589 187372669 590 101958995 591 144524735 592 115376185 593 208176209 594 82511485 595 137801875 596 121572713 597 148978981 598 118077655 599 214562999 600 70149767 601 216720601 602 114547025 603 149618875 604 126545587 605 162783821 606 96909595 607 223280095 608 121693775 609 131992145 610 112746805 611 206176835 612 86418125 613 229970629 614 144200975 615 129035479 616 104672785 617 234504425 618 102801305 619 236793499 620 107741447 621 158604653 622 149917555 623 205629455 624 90247891 625 196887601 626 152831645 627 149535491 628 142274065 629 227943125 630 75232375 631 250841431 632 142632107 633 177638809 634 158772625 635 205257755 636 102686507 637 205206973 638 142589195 639 178199855 640 121035673 641 262963841 642 115291525 643 265434259 644 127039685 645 149027621 646 150289375 647 270421415 648 107800853 649 244499689 650 127837145 651 161597755 652 159254623 653 278018669 654 121899155 655 225324031 656 157411181 657 193762945 658 149882125 659 285756899 660 85984633 661 288367861 662 180775655 663 178298375 664 165515407 665 193637705 666 124444625 667 274086811 668 171294275 669 209756941 670 149618875 671 270369071 672 104953625 673 304368289 674 190795925 675 171713827 676 164929165 677 309830405 678 135862255 679 266463175 680 136867625 681 221265545 682 174571705 683 318145499 684 121433815 685 257811085 686 173449715 687 227174431 688 181799719 689 296374001 690 111676205 691 329461891 692 190468193 693 180408725 694 208307575 695 269296199 696 131097283 697 310989625 698 211933745 699 239305931 700 137539915 701 343980701 702 138245915 703 320303215 704 181404167 705 194999185 706 219311845 707 300929795 708 141934997 709 355898149 710 178199855 711 245833495 712 204235357 713 335564009 714 129615625 715 248169019 716 211022063 717 258301181 718 230696995 719 371177999 720 119402705 721 319225105 722 222881405 723 264849379 724 218188297 725 296740949 726 153113495 727 383712055 728 175376615 729 268214185 730 193762945 731 359172875 732 156952483 733 393295549 734 246480875 735 194081903 736 217940275 737 358789025 738 169783525 739 403037299 740 184178045 741 250542949 742 215451775 743 409620359 744 160502177 745 331860649 746 258779945 747 285273995 748 207232375 749 358010525 750 149634595 751 423000751 752 237880715 753 299254769 754 238904605 755 345435251 756 148738705 757 433225045 758 271481495 759 267801751 760 192324907 761 440131961 762 193064225 763 378528955 764 256461467 765 235898125 766 280175995 767 409653071 768 182152639 769 454165249 770 180408725 771 321262355 772 264616933 773 461292389 774 196088975 775 363299431 776 264656645 777 276242425 778 293562745 779 436999259 780 144065087 781 427326781 782 269151875 783 320902223 784 236761717 785 388369745 786 211938445 787 486824035 788 281442905 789 344323301 790 245833495 791 421888055 792 179185615 793 452996569 794 312065825 795 280306411 796 290116963 797 505626365 798 182134475 799 469969375 800 235953725 801 352009745 802 321602005 803 464647379 804 208281325 805 346784005 806 292490495 807 368462231 808 298889593 809 528820649 810 185800105 811 532754011 812 257037335 813 376752349 814 298420675 815 434722079 816 205715375 817 504705841 818 341253245 819 302270275 820 251279617 821 552713621 822 242495575 823 556764439 824 317060867 825 289936409 826 297801025 827 564925355 828 217474715 829 569035549 830 285273995 831 402366895 832 303938113 833 467758625 834 253298405 835 467587075 836 291200693 837 392880037 838 366922495 839 589885799 840 165868765 841 574335721 842 372206105 843 420072539 844 345928207 845 450212045 846 256577875 847 475457695 848 341947529 849 429116881 850 291398125 851 573628115 852 248068313 853 619922869 854 329309975 855 331481495 856 355583335 857 628688345 858 233426305 859 633101899 860 290211683 861 376885805 862 399386155 863 641990879 864 255165575 865 519926689 866 404976245 867 431724403 868 314690365 869 589513589 870 225952655 871 601141975 872 375962657 873 456148825 874 378209305 875 464654795 876 269733367 877 673757005 878 422058995 879 476290271 880 286330051 881 683021681 882 255370925 883 687685699 884 347212625 885 387444181 886 433710295 887 697077335 888 274369595 889 599515225 890 352009745 891 445552331 892 408474043 893 660395885 894 312146155 895 576033199 896 353520035 897 448695089 898 451586245 899 678941219 900 235449685 901 675569125 902 407144255 903 435278695 904 419027797 905 595595081 906 324914345 907 745319995 908 430885535 909 515151005 910 302270275 911 755228111 912 289069021 913 684092689 914 476175725 915 428437859 916 442392313 917 658124645 918 315124375 919 775306999 920 344432927 921 547963705 922 488798305 923 715975259 924 251143235 925 621040285 926 495192395 927 546470095 928 440955025 929 800902049 930 276633445 931 657289363 932 466016813 933 569686709 934 508147375 935 565688375 936 300220985 937 821778985 938 437005625 939 580760251 940 379735255 941 832352141 942 365298275 943 782617999 944 472645559 945 406016465 946 470225245 947 848381315 948 342219697 949 778504981 950 409469495 951 603335975 952 399761875 953 864614969 954 368824225 955 700070491 956 503007563 957 541838941 958 548363995 959 753012575 960 287460443 961 858903361 962 499996325 963 612865475 964 515759317 965 722332709 966 326182975 967 903295975 968 472234253 969 571099625 970 456148825 971 914555771 972 367552783 973 786558205 974 576320675 975 485781151 976 522654001 977 931620305 978 408897005 979 844126339 980 377948969 981 647990245 982 590648455 983 948895799 984 374330647 985 768263065 986 544570625 987 569552075 988 487899427 989 903873101 990 308835275 991 972260191 992 539860475 993 686947489 994 520484725 995 791940899 996 397123997 997 990032965 998 620012495 999 671606695 1000 461504593