1000 1040 1 757 59516440 1 965 648284414 2 629 401122994 2 710 908626707 3 193 349561276 3 505 635259605 3 677 602521731 4 93 484729330 4 488 804945056 5 148 589243861 5 286 986973640 6 60 530183784 6 728 888702996 7 499 594560229 7 972 498756046 8 84 885645796 8 824 162946354 9 478 30313938 9 521 75172981 10 63 856331819 10 245 382039603 11 139 214199364 11 254 823843323 11 697 736416123 12 761 367737551 12 950 886040759 13 34 311773290 13 850 338189040 14 435 104638506 14 935 429225512 15 24 289233013 15 602 671907656 16 120 272263010 16 311 726861931 17 583 811039417 17 901 436003148 18 810 724578015 18 887 338475563 19 423 861833619 19 752 827335169 20 46 486463705 20 955 483034116 21 495 573825096 21 801 762449004 22 328 59497372 22 780 238585910 23 249 147140888 23 959 884588148 24 644 662860732 25 201 769630345 25 553 626155767 26 114 536056291 26 743 58869367 26 979 849921432 27 67 176634389 27 68 987526072 28 675 14743974 28 737 845452421 28 751 69598975 29 796 319799869 29 897 173671754 30 211 770232659 30 649 703422561 31 209 660412208 31 517 903363713 32 99 616054508 32 197 434401560 32 253 102732949 32 640 486793043 33 107 372185828 33 514 100678957 34 255 535249694 35 234 234766835 35 335 724242131 36 621 568377171 36 624 524204488 37 108 567865896 37 300 908969755 38 388 765660006 38 831 307511640 39 244 231196457 39 306 124631177 40 252 490501653 40 869 201059891 41 754 425811038 41 949 465702347 42 284 359352998 42 968 199224605 43 248 761927687 43 299 132570357 44 171 967010231 44 219 778490136 45 486 72654865 45 664 977285190 46 840 276242575 47 446 65403755 47 497 111101264 48 175 44908639 48 322 190089787 49 770 306782980 49 779 975201424 50 109 622387531 50 845 906361624 51 210 148564263 51 467 624579769 52 278 398115298 52 663 730127006 53 762 152333111 53 867 697909362 54 416 274259322 54 471 795895955 55 220 919883939 55 312 617398630 56 733 387629311 56 908 623767282 57 833 882801356 57 887 263608990 58 212 280479496 58 693 397521499 59 156 306331898 59 598 429274810 60 298 49803504 61 271 595336381 61 327 955968037 62 520 695549418 62 805 479163414 63 544 337155887 64 642 20086822 64 961 934355506 65 534 530520464 65 692 467296419 66 615 611505102 66 632 248445746 67 325 239198433 68 963 561795742 69 655 306878228 69 837 878452652 70 504 727556120 70 847 602396245 71 221 582389511 71 484 264568303 72 665 160589368 72 861 752008393 73 178 794831860 73 548 777437479 73 806 168057244 74 102 545684068 74 859 200518916 75 171 255151170 75 863 629335439 76 154 542896285 76 718 664804415 77 156 949924115 77 330 203779940 78 289 980874402 78 812 245522859 79 510 760337297 79 514 562475227 80 816 860836532 80 985 123889759 81 354 838329613 81 794 96854020 82 164 561894849 82 773 303655583 83 418 678359931 83 573 20121753 84 950 49954778 85 269 626005770 85 293 432789393 86 764 654698069 86 815 926247391 87 339 717040312 87 345 179308047 87 659 218635340 88 280 344449372 88 597 919129262 89 632 294000108 89 777 204732537 90 663 751599208 90 892 284869327 91 137 852492559 91 181 614929211 92 281 380136745 92 297 936455638 92 929 529763833 93 385 877335830 94 292 239766141 94 753 31385640 95 282 838230194 95 827 455654213 96 713 365981796 96 756 422635658 97 642 239036769 97 853 966717285 98 543 780001860 98 846 38446395 99 130 212689677 100 364 488331246 100 460 702164713 101 454 419145634 101 735 39089728 102 791 949555483 103 168 720217132 103 739 989004811 104 676 788895629 104 873 564644771 105 239 112621555 105 566 644479524 106 716 280479633 106 780 510158999 107 361 562252906 108 910 215924199 109 731 112766415 110 333 780532594 110 434 769061814 111 297 108545957 111 682 203194097 112 435 938290918 112 541 646854027 113 553 309457221 113 768 4428714 114 185 434671710 114 428 798339236 115 705 665347767 115 939 234333507 116 873 531230623 116 952 18713119 117 176 575059518 117 209 793617955 118 202 973524870 118 401 415602351 119 904 650641970 119 932 559794889 120 849 172664093 121 296 207462633 121 301 575152302 122 572 36143840 122 877 559131057 122 898 351367631 123 571 107313424 123 736 687335505 123 842 727249309 124 370 591903187 124 619 249730253 125 706 545532726 125 765 130338410 126 293 875601398 126 945 518685348 127 271 745652124 127 448 599613969 127 993 458813453 128 145 253916411 128 652 732095419 129 461 762232315 129 503 344749592 130 877 976612013 131 148 993315777 131 405 332923842 131 683 7015490 132 607 660919186 132 981 465068652 133 400 477290520 133 947 7042140 134 186 55829278 134 684 995465738 135 618 435520617 135 914 790230348 136 138 632864123 136 238 215720146 137 250 508316789 138 405 292595941 139 492 978857286 140 630 137588485 140 868 688156178 141 392 806772176 141 610 340759143 142 511 668753720 142 580 901327171 143 217 381782685 143 864 306174940 144 219 593757190 144 387 810190838 144 997 139391620 145 631 854136672 146 749 636889638 146 969 900095447 147 526 147702218 147 709 17864897 149 793 633054348 149 836 293184803 150 376 893040194 150 939 444362028 151 319 438444030 151 581 37325539 152 212 61645101 152 573 819595915 153 260 240492511 153 801 294049545 154 223 609426790 154 550 618969599 155 529 659841085 155 767 647969583 157 480 694896150 157 775 963840969 158 496 419534177 158 786 312684847 159 170 678788866 159 230 122595909 160 509 379710885 160 879 881228234 161 346 562298990 161 694 267029547 162 269 74910764 162 909 856404245 163 308 378039314 163 584 438337068 164 918 797904326 165 806 213255113 165 999 604252717 166 262 139243743 166 279 876522289 167 464 828492563 167 575 800944131 168 657 545779206 169 321 382985132 169 759 839982511 170 348 409946947 171 338 222332503 172 401 244324954 172 900 49035104 173 261 867881510 173 483 112311375 174 615 467190983 174 759 619772590 175 315 909004255 175 494 950019733 176 415 486853018 177 526 366890626 177 566 106662984 178 456 394648952 178 692 158470213 179 204 513404617 179 666 273782816 180 454 804012311 180 934 281824722 181 559 18085477 182 272 28080653 182 966 460979920 183 344 218150659 183 938 861866712 184 374 778620968 184 892 159010316 185 346 730493920 186 852 812215616 187 215 122609165 187 356 374409429 188 259 802833743 188 623 46256774 189 415 605304196 189 977 777916257 190 512 198295933 190 987 920881968 191 787 52748937 191 960 839673956 192 522 163204344 192 777 416318386 193 1000 635130992 194 349 292422139 194 503 948962310 195 764 749376844 195 982 98153142 196 491 961502542 196 812 194498265 197 353 543595311 197 414 84090480 198 284 18748657 198 520 318336576 199 685 875698339 199 745 242567620 200 336 394233345 200 702 539636919 201 761 602375310 202 540 360434670 203 524 425464726 203 655 966397578 204 973 352665115 205 294 768089073 205 917 853320070 206 485 903772501 206 883 255431059 207 390 136867645 207 445 17092401 208 278 373651735 208 875 294764988 210 707 452397093 211 387 738302895 213 324 985488145 213 798 319276583 214 441 173273261 214 591 697080799 215 277 136495105 216 250 38491412 216 785 803357909 216 967 419009883 217 326 789970189 218 235 227658678 218 638 153224962 219 511 705255453 220 587 396308505 221 510 715765639 222 576 20156457 222 807 9026710 223 783 327318194 223 848 900397277 224 358 17538178 224 536 899772909 225 536 334392737 225 723 838992753 226 452 352094565 226 574 947575971 227 416 785952905 227 967 407851504 228 384 199890422 228 758 319200348 229 530 174005589 229 795 564182563 230 487 258369167 231 474 315396100 231 601 996948225 232 449 264982317 232 711 66279203 233 353 963495083 233 660 379435332 234 548 663221031 235 688 168469506 236 262 7414394 236 828 815938553 237 547 632472885 237 883 728370268 238 310 853070163 239 771 925673738 240 685 671412900 240 989 513536579 241 343 992034134 241 384 261213800 242 247 93703942 242 725 816315318 243 378 46761525 243 498 204530108 244 701 835405785 245 577 411104556 246 359 879566410 246 906 668705452 246 985 181709259 247 905 681619766 248 579 8497005 249 304 517355208 250 610 683391961 251 602 596340634 251 942 226383778 252 742 974408341 253 914 516462407 254 285 315276637 255 373 338293552 256 440 372658994 256 669 182361195 257 360 938455151 257 994 75052035 258 512 722255382 258 781 217637877 259 604 329573904 260 734 436988811 261 402 643341220 263 545 713503336 263 858 8438621 264 270 284165779 264 611 173546620 264 630 944395867 265 532 566513553 265 682 74262883 266 670 954392970 266 860 862485159 267 286 403691417 267 830 503345561 268 360 46679448 268 399 340734182 270 653 29293950 270 817 150994647 271 925 321925296 272 349 640370996 273 381 413623781 273 940 612171527 274 389 323959012 274 525 738126950 275 342 71882799 275 733 917409859 276 502 346289856 276 729 495033641 277 646 414630269 279 612 429016650 280 629 6270616 281 758 127577960 282 613 506132901 283 560 586889467 283 800 398045592 285 717 643282375 287 674 280447464 287 741 16031326 288 698 39889885 288 721 158318732 289 365 182475209 290 406 797677010 290 593 757226166 291 811 400438956 291 876 468337389 292 422 873832457 294 750 879183386 295 694 898849204 295 855 629854599 296 754 487896621 297 836 22302054 298 980 166398082 299 432 30262833 300 921 712821081 301 843 282000805 302 458 826492775 302 461 119094162 303 715 9962559 303 899 930030583 304 469 682425252 305 330 770619538 305 689 575390003 306 734 837813098 307 527 140844921 307 888 195647246 308 548 91073673 309 813 635852622 309 814 971877076 310 338 965614998 311 603 342230061 311 672 411068388 312 699 423095290 313 439 804698311 314 618 119284007 314 799 790009596 315 369 267147178 315 519 344271696 316 542 347113336 316 874 382824651 317 476 742011993 317 919 160955028 318 687 460593736 318 918 373999628 319 427 670900645 320 555 493575941 320 736 701340177 321 438 347567209 322 557 569829514 323 369 587767584 323 457 579274328 323 676 349716391 324 447 66057 325 358 92612857 326 882 681457624 327 622 609061910 328 681 741814093 329 354 562246712 329 963 868124421 331 385 498777754 331 938 916899261 332 739 732947626 332 962 397520225 333 871 451294737 334 745 348895563 334 915 227535354 335 428 801680772 336 534 151996642 337 707 932436777 337 711 97120210 337 858 537528759 338 782 239411724 339 686 170723269 340 623 446050737 340 931 281256274 341 371 58684539 341 755 827763844 342 408 6545150 343 697 248649038 344 437 832370402 345 462 956165297 346 468 526471760 347 396 317453899 347 559 569560419 348 666 429500016 350 568 783920589 350 924 994292179 351 634 61390514 351 893 428842545 352 609 313740570 352 784 526593658 355 713 928427766 355 968 72421713 356 763 456292672 356 919 544422642 357 398 764552265 357 657 68889230 359 941 300920349 361 528 1910560 362 450 495259544 362 832 20965576 363 473 65242802 363 945 648419531 364 958 801894654 365 940 757650097 366 423 956900524 366 612 25234574 367 481 512991803 367 723 392098628 368 524 92207731 368 876 3505036 370 476 961529857 370 920 465806820 371 452 614998582 372 469 535778861 372 943 866386228 373 920 526854802 374 572 376712872 375 789 351711820 375 824 687908344 375 826 788860768 376 595 782083432 377 551 288429966 377 850 635856585 378 495 602031475 379 457 560175465 379 834 481593084 380 470 880085352 380 775 170675321 381 936 895984269 382 841 689750787 382 874 636634397 383 941 905750921 383 955 553873146 386 928 40258082 386 996 441941767 388 797 346119115 389 518 550532864 390 616 74156911 391 403 61932272 391 473 404789425 392 700 287513675 393 427 46741528 393 956 859786565 394 633 62955204 394 724 805400846 395 537 12888116 395 952 715314976 396 611 18175766 397 588 675837460 397 625 999296416 398 712 322946014 399 647 907816402 400 504 206888409 402 624 529811995 403 884 122375385 404 456 661163456 404 672 268795959 406 627 620754103 407 466 339650261 407 516 909527410 408 899 946206750 409 816 361479457 409 944 996925753 410 561 203767922 410 651 152066099 411 578 455693999 411 697 653680702 412 603 176572596 412 971 650302880 413 607 575960407 413 986 173026024 414 633 373733262 417 453 217658253 417 593 12344083 418 617 437630195 419 421 146893859 419 492 537630321 420 656 300091797 420 975 355766103 421 641 743194832 422 959 721307272 424 508 464530612 424 706 692222775 425 552 918180337 425 613 690580974 426 489 187532229 426 531 726853848 429 755 545781180 429 826 432770512 430 622 497933118 430 927 633398444 431 527 929854158 431 774 744566778 431 907 86675101 432 562 93845174 433 743 750619774 433 969 293382192 434 474 169337063 436 562 862000960 436 578 986310003 437 690 183727434 438 848 430406569 439 681 212553642 440 482 441581553 441 640 56831889 442 465 102399457 442 773 472331887 443 487 81988470 443 966 123510265 444 724 657060748 444 990 480273623 445 522 579502332 446 751 175920293 447 678 374229651 448 840 680704227 449 459 916184037 450 627 474851787 451 679 538528569 451 708 735773359 453 693 313409932 455 647 254799782 455 678 457456411 456 590 540539790 458 902 365990698 459 644 291303167 460 985 437063161 462 549 296276433 463 658 579988380 463 800 878863819 464 696 319191529 465 805 137761764 465 847 347861723 466 643 92003272 467 501 421417148 468 719 139381951 468 983 274878558 470 565 326353584 471 944 829441380 472 747 389419816 472 890 545864732 475 527 36968622 475 650 989926612 477 729 617271972 477 875 509937907 478 748 770664201 479 481 501851233 479 951 498147840 480 554 52675531 482 582 275691623 483 854 647294628 484 746 334347812 485 671 418851495 486 584 244619772 488 979 732711593 489 814 71076198 490 808 471283684 490 948 756288988 491 934 570904152 493 505 560399554 493 981 336055909 494 843 260821645 494 922 345266122 496 996 104913259 497 686 303684452 498 554 402496903 499 888 653350795 500 679 710125917 500 978 364657713 501 740 365722485 502 871 918622814 506 668 446091004 506 742 208375165 506 828 503747769 507 660 330487851 507 988 469659738 508 563 376293808 509 995 449797458 513 592 458689956 513 600 404868579 515 539 90937748 515 705 390313783 516 991 749870954 517 722 131420817 518 730 806360327 519 915 38392123 521 677 364395330 523 716 644560003 523 856 833797012 525 927 601626286 528 564 535150523 529 776 713267007 529 991 484959056 530 595 927050493 531 547 987439750 532 823 605926727 533 805 595967440 533 909 420703537 535 650 704525997 535 894 411411051 537 674 244525972 538 670 445078862 538 691 372534077 539 925 329134765 540 746 507027627 540 920 596623812 541 736 658270950 542 557 692421637 543 998 787300619 544 913 421750238 545 709 905415741 546 637 438875928 546 922 754303476 549 717 216230613 550 834 656824328 551 683 882849725 551 804 520913038 552 575 1488904 555 960 445629847 556 675 998304084 556 859 839314356 558 794 143799434 558 977 517051184 560 908 872291008 561 786 186069945 563 683 328279617 564 605 272215056 565 704 754311639 567 808 260395133 567 857 875222117 568 829 186848266 569 894 133058149 569 910 865353188 570 620 59973271 570 815 769595596 571 826 645451554 572 748 824089343 574 984 410028787 576 662 814008876 577 664 756643698 579 810 634188187 580 695 581967364 581 823 769193913 582 594 362411209 583 919 679872408 585 789 88440557 585 845 290082847 586 645 222929491 586 732 266222663 587 783 582797233 588 943 365163919 589 684 892592964 589 872 775555494 590 954 219912815 590 972 513251057 591 862 19741487 592 725 628032774 594 962 304757974 596 831 929027878 596 884 695933016 597 687 690340831 598 750 94752131 599 626 289383357 599 703 688429943 600 772 791882266 601 765 930109280 603 710 59562314 604 838 961613257 605 776 2254078 606 796 643201426 606 819 663232036 608 722 152918409 608 893 86899863 609 930 908149074 614 913 680722673 614 964 461130794 616 727 937874203 617 896 589934549 618 763 205083649 619 907 733955028 620 742 73698922 621 911 621025431 625 821 998546694 626 903 889560204 628 668 233614470 628 900 717892285 631 904 121986940 634 825 474921547 635 768 273407597 635 917 380518574 636 822 674545776 636 866 659311992 637 989 656243584 638 851 582609817 639 799 747256172 639 933 764859546 640 922 240407513 641 680 297046526 643 704 80802536 645 998 216945356 646 792 22796561 648 833 517941349 648 926 500472551 649 667 743421647 651 870 623068197 652 942 557279679 653 676 36375446 654 895 303583481 654 974 572525440 656 659 783110501 658 774 623258007 659 809 946850917 661 781 75469110 661 948 226201606 662 886 958451831 665 970 795739696 667 975 114844519 669 790 231861185 671 818 214908936 673 691 385789264 673 964 127355130 674 895 671969131 677 865 447183344 680 994 366570446 688 701 41585900 689 854 588181251 690 844 719192373 695 879 590797741 696 982 392434481 698 819 317198000 699 792 629629499 700 949 392322352 701 719 272599775 702 997 962741949 703 711 192569183 708 738 374739642 712 889 965448801 714 811 236981963 714 896 319297471 715 744 828101781 718 756 521315641 719 837 489556912 720 889 732838291 720 931 112334449 721 882 235294157 726 885 933419424 726 958 993958875 727 767 734151858 728 790 841978154 730 771 970576105 731 916 655279770 732 817 232876947 735 923 918226065 737 803 356408064 738 752 372509194 740 807 321003194 741 895 149109010 744 987 165731442 746 835 11713643 747 901 854904496 749 762 405752478 751 933 552505676 753 870 466616854 757 947 767402736 760 880 781751947 760 993 808027101 763 849 183000677 766 872 718567831 766 906 443230305 769 897 642306834 769 957 502725489 770 797 855723982 772 793 936564910 776 923 122405406 778 782 285752729 778 862 932056822 779 983 561129518 784 785 451558741 787 846 87621397 788 903 931368345 788 986 229504395 791 928 418199485 795 878 224257370 798 851 642841241 802 864 402201343 802 935 536916921 803 951 802370782 804 865 323411016 804 954 562648855 809 886 298119426 813 976 389757553 818 972 600703391 818 979 432821351 820 905 910223633 820 965 332245412 822 956 593594445 825 855 52601091 827 844 248178152 829 932 876466423 830 842 160591029 832 878 591701757 835 988 864255916 838 976 920850401 839 902 95594206 839 916 365494696 841 861 264316246 852 929 536936749 853 953 988516212 856 984 374070572 857 970 157966637 860 890 655781110 863 971 152949019 866 926 521785779 867 980 803713235 868 992 115924462 869 995 96542486 880 881 751970059 881 891 451663657 885 912 888686389 891 946 321371518 898 930 956731872 911 957 418461382 912 961 244582323 921 1000 775342241 922 934 422588331 924 978 810301786 936 953 93560589 937 946 873428025 937 992 965177877 973 999 695228765 974 990 107299984