3000 2999 2997 1 2 307988980 2 3 320708828 3 4 135796395 4 5 645618939 5 6 471100355 6 7 91517452 7 8 79560360 8 9 704154364 9 10 886392730 10 11 759458273 11 12 143258910 12 13 40655676 13 14 823520715 14 15 818288259 15 16 559774429 16 17 465113527 17 18 573304737 18 19 97437652 19 20 878377099 20 21 239627600 21 22 198549444 22 23 385957047 23 24 59206947 24 25 457213712 25 26 828707029 26 27 589642999 27 28 962893136 28 29 282901346 29 30 945556951 30 31 200026831 31 32 366142846 32 33 9913956 33 34 168312223 34 35 911453744 35 36 732701941 36 37 468961975 37 38 507139868 38 39 904683708 39 40 376827378 40 41 263496364 41 42 86504269 42 43 114167381 43 44 951228910 44 45 903651197 45 46 344839945 46 47 27203867 47 48 810919561 48 49 800128433 49 50 954674960 50 51 685278685 51 52 405712235 52 53 832099171 53 54 42550383 54 55 841427278 55 56 797957813 56 57 695811695 57 58 740028073 58 59 584651703 59 60 497518369 60 61 102246202 61 62 984873538 62 63 735603252 63 64 373017711 64 65 786854953 65 66 5421783 66 67 776168245 67 68 438615659 68 69 356157452 69 70 669488773 70 71 156657802 71 72 182621190 72 73 101829065 73 74 356135779 74 75 821343292 75 76 201798780 76 77 324002982 77 78 259442753 78 79 61928929 79 80 412138521 80 81 698168417 81 82 476423704 82 83 919041974 83 84 768336860 84 85 297008780 85 86 417198438 86 87 491516611 87 88 789733376 88 89 144561476 89 90 618987718 90 91 839517807 91 92 60017445 92 93 667519515 93 94 261082922 94 95 44883760 95 96 874869792 96 97 470971671 97 98 18748342 98 99 664556122 99 100 821161052 100 101 355940308 101 102 89243964 102 103 703230745 103 104 774693099 104 105 639705284 105 106 995209552 106 107 8119418 107 108 48591917 108 109 466729623 109 110 826441480 110 111 370751651 111 112 663564214 112 113 965065554 113 114 760813347 114 115 59326769 115 116 102970856 116 117 131579634 117 118 51125348 118 119 677733878 119 120 588629016 120 121 763613757 121 122 723478825 122 123 270295598 123 124 462342551 124 125 299621284 125 126 987372169 126 127 125038361 127 128 350085070 128 129 165437825 129 130 182659649 130 131 680908014 131 132 825559825 132 133 28720797 133 134 344135407 134 135 714345258 135 136 271561913 136 137 355768400 137 138 982612243 138 139 769033265 139 140 582610619 140 141 176549513 141 142 666893885 142 143 649109421 143 144 626050564 144 145 665105940 145 146 108393257 146 147 176751557 147 148 930879709 148 149 283704389 149 150 363318280 150 151 22245564 151 152 9860623 152 153 714181752 153 154 51304861 154 155 10325969 155 156 605613457 156 157 361807834 157 158 567087168 158 159 778025233 159 160 696598620 160 161 851812816 161 162 176033534 162 163 208888023 163 164 140042587 164 165 713658631 165 166 168668894 166 167 291346146 167 168 743862654 168 169 880897817 169 170 733087807 170 171 916717841 171 172 545442542 172 173 680091229 173 174 214632381 174 175 381912411 175 176 330566459 176 177 418065138 177 178 703728051 178 179 253480304 179 180 498915555 180 181 215508985 181 182 3615693 182 183 246679912 183 184 764355469 184 185 759135787 185 186 813634746 186 187 370248837 187 188 111807472 188 189 817007891 189 190 755203312 190 191 8138940 191 192 350624150 192 193 672388647 193 194 493231044 194 195 58457263 195 196 82849613 196 197 573025469 197 198 756643389 198 199 397367547 199 200 912963583 200 201 37409404 201 202 562916983 202 203 929806358 203 204 52404781 204 205 405771751 205 206 937296017 206 207 70979939 207 208 150387650 208 209 531939534 209 210 867963853 210 211 172162508 211 212 159524131 212 213 741921530 213 214 645600996 214 215 389784318 215 216 833646478 216 217 230124904 217 218 251745601 218 219 609304761 219 220 333915793 220 221 660777864 221 222 612846994 222 223 777147714 223 224 229074881 224 225 112080195 225 226 198374058 226 227 799213422 227 228 202758962 228 229 867510596 229 230 314166450 230 231 2112745 231 232 944304370 232 233 240158028 233 234 503945597 234 235 448819490 235 236 213347499 236 237 810072626 237 238 742384634 238 239 124743383 239 240 196897132 240 241 463064955 241 242 32279746 242 243 499892792 243 244 831168385 244 245 535284369 245 246 338412497 246 247 958316475 247 248 78565502 248 249 114724772 249 250 527549778 250 251 685015932 251 252 710460251 252 253 888915994 253 254 799178131 254 255 551121742 255 256 581079737 256 257 460613812 257 258 725283864 258 259 722269026 259 260 970300739 260 261 993296190 261 262 150010315 262 263 759741330 263 264 287667248 264 265 391726578 265 266 588402257 266 267 643207499 267 268 42745828 268 269 664258155 269 270 386752119 270 271 688899605 271 272 262044342 272 273 239621697 273 274 870433227 274 275 153273025 275 276 587783628 276 277 451860808 277 278 534143790 278 279 678688291 279 280 891779369 280 281 53267127 281 282 504927659 282 283 501549550 283 284 628056030 284 285 416237372 285 286 200447119 286 287 289788692 287 288 853075660 288 289 731982994 289 290 713365519 290 291 776985068 291 292 983716501 292 293 418442910 293 294 964827051 294 295 680308870 295 296 429965877 296 297 735087887 297 298 960366112 298 299 671274353 299 300 110000017 300 301 649421760 301 302 395524716 302 303 498682009 303 304 726858025 304 305 418712425 305 306 274079498 306 307 983400395 307 308 306819042 308 309 475287072 309 310 668981960 310 311 877987872 311 312 816505638 312 313 435310039 313 314 948533942 314 315 760343555 315 316 210066728 316 317 603429496 317 318 61707578 318 319 901594592 319 320 105731397 320 321 54341019 321 322 968536641 322 323 15755114 323 324 922206342 324 325 125021154 325 326 756344976 326 327 13899145 327 328 722061378 328 329 407012338 329 330 754702392 330 331 134800095 331 332 577540320 332 333 30843662 333 334 203684904 334 335 209798902 335 336 11441338 336 337 80240977 337 338 833509596 338 339 196446216 339 340 533852446 340 341 202957192 341 342 356075572 342 343 994342249 343 344 72544622 344 345 167033514 345 346 932258911 346 347 410750101 347 348 219151463 348 349 803548917 349 350 147512822 350 351 949952722 351 352 474696574 352 353 301894821 353 354 359073061 354 355 389897089 355 356 206286950 356 357 885739524 357 358 21380329 358 359 550856196 359 360 647870546 360 361 162488712 361 362 307812670 362 363 467238020 363 364 361388810 364 365 109260709 365 366 485530450 366 367 33572483 367 368 349400662 368 369 795857212 369 370 416765223 370 371 372583792 371 372 287679048 372 373 839648809 373 374 179170106 374 375 836462878 375 376 274956262 376 377 318170673 377 378 743907485 378 379 661619670 379 380 364234595 380 381 970892978 381 382 422641536 382 383 961467813 383 384 820623514 384 385 563300998 385 386 131092746 386 387 489162164 387 388 370315808 388 389 982013895 389 390 522114246 390 391 129806271 391 392 337709677 392 393 546970467 393 394 243707652 394 395 243532299 395 396 590149055 396 397 311144898 397 398 672306988 398 399 966895007 399 400 34985617 400 401 542632578 401 402 840135792 402 403 932269305 403 404 757002038 404 405 977670892 405 406 63052393 406 407 575421317 407 408 377545303 408 409 747899681 409 410 679792406 410 411 163504405 411 412 844251668 412 413 687735626 413 414 409736070 414 415 160365837 415 416 122705064 416 417 631555140 417 418 824341305 418 419 264802401 419 420 843315140 420 421 916573978 421 422 211373170 422 423 516210835 423 424 847054124 424 425 559975212 425 426 706820629 426 427 411371757 427 428 500453982 428 429 894825724 429 430 643702188 430 431 926581082 431 432 465163116 432 433 918638486 433 434 40024963 434 435 960229602 435 436 99891947 436 437 452767897 437 438 849749236 438 439 97421249 439 440 96042244 440 441 682767589 441 442 889993506 442 443 758994343 443 444 285424099 444 445 567654797 445 446 84446845 446 447 912585696 447 448 864890731 448 449 197019806 449 450 405057674 450 451 555576386 451 452 548508246 452 453 851871867 453 454 760774112 454 455 469983359 455 456 526791586 456 457 755229155 457 458 43967279 458 459 253159962 459 460 151205062 460 461 599420182 461 462 698618931 462 463 500359020 463 464 832394604 464 465 57879970 465 466 75276417 466 467 596304354 467 468 835988836 468 469 291790687 469 470 347666776 470 471 172733051 471 472 434000430 472 473 493133053 473 474 908261092 474 475 565148947 475 476 587927402 476 477 517608375 477 478 525218782 478 479 430715635 479 480 561535510 480 481 695358850 481 482 155966824 482 483 23780205 483 484 910903904 484 485 490807426 485 486 322781343 486 487 902035865 487 488 454567129 488 489 401277114 489 490 782131549 490 491 522479698 491 492 232038233 492 493 898620123 493 494 671953831 494 495 402267735 495 496 480906096 496 497 24990269 497 498 432022970 498 499 445502097 499 500 545431172 500 501 200350699 501 502 514585773 502 503 895364211 503 504 295856012 504 505 997159128 505 506 711574979 506 507 850852989 507 508 295773800 508 509 150335792 509 510 183487055 510 511 585497308 511 512 238087386 512 513 793995978 513 514 336792132 514 515 523695148 515 516 949513509 516 517 441441977 517 518 292697433 518 519 739143773 519 520 326169152 520 521 253962242 521 522 357415125 522 523 789479859 523 524 532748727 524 525 442759015 525 526 764070908 526 527 514219495 527 528 468304671 528 529 509974114 529 530 86267755 530 531 699414324 531 532 54449966 532 533 111613208 533 534 784101067 534 535 607804049 535 536 537330686 536 537 197810674 537 538 694999087 538 539 876489738 539 540 423509329 540 541 62042996 541 542 507525885 542 543 639527593 543 544 84011357 544 545 156869853 545 546 812020635 546 547 743800132 547 548 807439016 548 549 682076930 549 550 884160850 550 551 91288503 551 552 427076022 552 553 833997080 553 554 690660430 554 555 57396164 555 556 745801181 556 557 749193154 557 558 362438531 558 559 903930164 559 560 278058729 560 561 226853928 561 562 405235591 562 563 359141802 563 564 884320461 564 565 312414630 565 566 537323664 566 567 964077363 567 568 154125541 568 569 196981388 569 570 381230310 570 571 979625756 571 572 304238592 572 573 340787194 573 574 800228696 574 575 223384704 575 576 264813864 576 577 949666463 577 578 62032337 578 579 341672915 579 580 387483344 580 581 614012316 581 582 195112339 582 583 344030107 583 584 967177881 584 585 804467078 585 586 239361299 586 587 767040575 587 588 951209409 588 589 274037642 589 590 531134833 590 591 74182904 591 592 847349801 592 593 96841388 593 594 455238035 594 595 134774756 595 596 724524545 596 597 20052776 597 598 91405113 598 599 255806994 599 600 288043001 600 601 421973902 601 602 914310038 602 603 991010983 603 604 527902839 604 605 969252538 605 606 874089845 606 607 507428121 607 608 125658139 608 609 34154464 609 610 767610813 610 611 648418294 611 612 43812446 612 613 72465447 613 614 679472500 614 615 701437901 615 616 542172352 616 617 468142394 617 618 618125458 618 619 662454937 619 620 719707365 620 621 820607933 621 622 863748080 622 623 307093960 623 624 854626522 624 625 211429226 625 626 611581024 626 627 362493158 627 628 514678645 628 629 39681741 629 630 800650454 630 631 655343833 631 632 902755480 632 633 509676995 633 634 830696989 634 635 801768728 635 636 440856740 636 637 503613826 637 638 544196771 638 639 932112116 639 640 802596997 640 641 176105451 641 642 787029928 642 643 367188670 643 644 387165128 644 645 884324102 645 646 380273448 646 647 9028960 647 648 962901451 648 649 985358554 649 650 985895515 650 651 619545974 651 652 548177721 652 653 595835491 653 654 991040698 654 655 270023318 655 656 807111457 656 657 302141857 657 658 201366450 658 659 39446704 659 660 47350195 660 661 960267469 661 662 663621348 662 663 398569361 663 664 557572246 664 665 56456359 665 666 923176215 666 667 666272386 667 668 526438632 668 669 745780714 669 670 962551227 670 671 460318221 671 672 289551059 672 673 926870497 673 674 594523419 674 675 609479647 675 676 985187016 676 677 981006355 677 678 568790814 678 679 839867593 679 680 316906588 680 681 587696922 681 682 699879097 682 683 693650657 683 684 615747259 684 685 296847506 685 686 716692469 686 687 534647237 687 688 706879693 688 689 147791916 689 690 892700824 690 691 860127487 691 692 495791843 692 693 627513314 693 694 908862835 694 695 870502020 695 696 516187166 696 697 101204805 697 698 312346183 698 699 457772375 699 700 381920093 700 701 869458418 701 702 949714517 702 703 356442187 703 704 514187232 704 705 243478307 705 706 617884545 706 707 474771173 707 708 372801918 708 709 112667233 709 710 415316514 710 711 50495583 711 712 836939391 712 713 219029847 713 714 89320809 714 715 578222281 715 716 868108567 716 717 941811395 717 718 847608939 718 719 209051723 719 720 205951104 720 721 568064133 721 722 54229452 722 723 365653637 723 724 282786226 724 725 835970266 725 726 422955018 726 727 840068119 727 728 201768386 728 729 929765026 729 730 465442403 730 731 273336380 731 732 124053460 732 733 774184669 733 734 202740836 734 735 518466193 735 736 698985662 736 737 608007476 737 738 945821712 738 739 820904180 739 740 940909115 740 741 837434804 741 742 953118377 742 743 43409287 743 744 636310985 744 745 88738197 745 746 368610516 746 747 687105824 747 748 648503609 748 749 573228304 749 750 412744715 750 751 994138928 751 752 235966850 752 753 808345446 753 754 971776884 754 755 10260600 755 756 691863725 756 757 551393815 757 758 770779074 758 759 425592350 759 760 544512469 760 761 97135651 761 762 978577903 762 763 215263197 763 764 15331268 764 765 188592259 765 766 701729178 766 767 600053754 767 768 80836912 768 769 681955158 769 770 554349006 770 771 56240934 771 772 325032398 772 773 156597208 773 774 459861157 774 775 157979562 775 776 811295288 776 777 954783961 777 778 445925097 778 779 899832397 779 780 812555953 780 781 931373551 781 782 494975942 782 783 178852736 783 784 95862562 784 785 505705131 785 786 600777137 786 787 825383337 787 788 3022535 788 789 543741470 789 790 840700012 790 791 129789108 791 792 859572423 792 793 927589953 793 794 145443287 794 795 195619957 795 796 786815677 796 797 948016416 797 798 116771957 798 799 482935310 799 800 763963932 800 801 831273506 801 802 798346276 802 803 398169702 803 804 790893024 804 805 734150026 805 806 298787844 806 807 926156474 807 808 96550090 808 809 316916368 809 810 728159115 810 811 721766725 811 812 912482761 812 813 761831710 813 814 519092918 814 815 245897867 815 816 615109237 816 817 359473444 817 818 542121306 818 819 806722881 819 820 29407156 820 821 48185240 821 822 886302105 822 823 81802460 823 824 84868223 824 825 423443213 825 826 228304240 826 827 994281140 827 828 976128703 828 829 733852655 829 830 199796588 830 831 787590745 831 832 23151228 832 833 91209769 833 834 474181523 834 835 738653410 835 836 323402663 836 837 641704338 837 838 193401643 838 839 684787780 839 840 530561978 840 841 714584979 841 842 741213614 842 843 783040735 843 844 416874956 844 845 340765806 845 846 197789955 846 847 750423515 847 848 153606674 848 849 951141698 849 850 909165157 850 851 138825913 851 852 699348042 852 853 119534032 853 854 415841276 854 855 551394792 855 856 669393900 856 857 27021402 857 858 231320598 858 859 495395447 859 860 361289454 860 861 18346407 861 862 998116358 862 863 169217254 863 864 103759156 864 865 416143140 865 866 866265365 866 867 164187283 867 868 124234532 868 869 997962290 869 870 942619486 870 871 790530376 871 872 562752190 872 873 368408666 873 874 318037754 874 875 186788910 875 876 126768977 876 877 428736531 877 878 285135962 878 879 377419024 879 880 907380637 880 881 249724101 881 882 381163343 882 883 671162034 883 884 88627690 884 885 212743631 885 886 287637891 886 887 413876068 887 888 656916879 888 889 914827381 889 890 870276465 890 891 813050081 891 892 693310067 892 893 176202085 893 894 834093496 894 895 418291549 895 896 229135054 896 897 47264012 897 898 218439403 898 899 403981079 899 900 474379177 900 901 736871550 901 902 39091290 902 903 289598808 903 904 921306036 904 905 413628621 905 906 38668106 906 907 101738466 907 908 995402439 908 909 734581962 909 910 68159630 910 911 128973705 911 912 56146963 912 913 108915947 913 914 235913150 914 915 63344091 915 916 38360809 916 917 315003208 917 918 222996503 918 919 794209274 919 920 927493670 920 921 66574272 921 922 697303791 922 923 901079691 923 924 536201171 924 925 329157831 925 926 843845589 926 927 158629123 927 928 164394558 928 929 316876975 929 930 995682605 930 931 28251998 931 932 380002552 932 933 534115932 933 934 178075629 934 935 129286162 935 936 993796874 936 937 309670004 937 938 824679869 938 939 393842748 939 940 231926361 940 941 380667833 941 942 9522538 942 943 333555753 943 944 940832743 944 945 799946683 945 946 705338547 946 947 837467227 947 948 904668065 948 949 42145966 949 950 739913897 950 951 345000534 951 952 916065502 952 953 11961218 953 954 787735701 954 955 805357086 955 956 186183882 956 957 995603793 957 958 904461777 958 959 577552457 959 960 281385049 960 961 873132541 961 962 832143956 962 963 888632384 963 964 946045106 964 965 803973768 965 966 777259885 966 967 686868489 967 968 136581066 968 969 907091671 969 970 920826519 970 971 917124312 971 972 361541770 972 973 610340023 973 974 139133632 974 975 190735263 975 976 571833887 976 977 89854195 977 978 602743682 978 979 910590685 979 980 802748628 980 981 511003946 981 982 82522758 982 983 441816913 983 984 177081638 984 985 482595347 985 986 216081896 986 987 458067937 987 988 23569947 988 989 999161077 989 990 484196009 990 991 4407458 991 992 985262783 992 993 987954944 993 994 695704582 994 995 727938743 995 996 279247057 996 997 695044679 997 998 166762982 998 999 327845600 999 1000 290507134 1000 1001 781835355 1001 1002 579797100 1002 1003 911846054 1003 1004 344946245 1004 1005 117438597 1005 1006 237698732 1006 1007 946591777 1007 1008 819501049 1008 1009 680723359 1009 1010 941780091 1010 1011 366707813 1011 1012 472460261 1012 1013 885021071 1013 1014 627343712 1014 1015 874519687 1015 1016 62718729 1016 1017 698508385 1017 1018 380946598 1018 1019 13980495 1019 1020 560487299 1020 1021 820573440 1021 1022 878890643 1022 1023 735679356 1023 1024 446687753 1024 1025 130480017 1025 1026 347184307 1026 1027 305246382 1027 1028 75140499 1028 1029 685602669 1029 1030 787284813 1030 1031 719338740 1031 1032 730584854 1032 1033 461872825 1033 1034 672432119 1034 1035 955451634 1035 1036 619859306 1036 1037 694261667 1037 1038 506345286 1038 1039 762712751 1039 1040 833465164 1040 1041 905101626 1041 1042 4142493 1042 1043 577181433 1043 1044 627195776 1044 1045 870763302 1045 1046 234423669 1046 1047 698502927 1047 1048 323750291 1048 1049 578268383 1049 1050 808538439 1050 1051 379779502 1051 1052 258042694 1052 1053 854174412 1053 1054 142757978 1054 1055 734431807 1055 1056 939633307 1056 1057 859173195 1057 1058 88982348 1058 1059 773535600 1059 1060 45791410 1060 1061 885674884 1061 1062 14472185 1062 1063 392472706 1063 1064 74454212 1064 1065 957549310 1065 1066 146531491 1066 1067 17092644 1067 1068 87540837 1068 1069 970930557 1069 1070 796341080 1070 1071 141397228 1071 1072 893702222 1072 1073 677237065 1073 1074 698434830 1074 1075 970504222 1075 1076 906877199 1076 1077 443323325 1077 1078 28381974 1078 1079 281246205 1079 1080 353994432 1080 1081 928170266 1081 1082 372790295 1082 1083 969367217 1083 1084 530050500 1084 1085 497913523 1085 1086 470969553 1086 1087 102321990 1087 1088 268287758 1088 1089 708319722 1089 1090 179948494 1090 1091 355558373 1091 1092 639347366 1092 1093 962674065 1093 1094 92836101 1094 1095 8899307 1095 1096 403832215 1096 1097 575369503 1097 1098 892117900 1098 1099 429388218 1099 1100 820363248 1100 1101 426796941 1101 1102 10287723 1102 1103 485568537 1103 1104 167353060 1104 1105 7890896 1105 1106 893256844 1106 1107 36077640 1107 1108 104408337 1108 1109 820922099 1109 1110 911285710 1110 1111 129854885 1111 1112 295693022 1112 1113 45557200 1113 1114 841981752 1114 1115 869598196 1115 1116 798853226 1116 1117 471291466 1117 1118 341504847 1118 1119 775984400 1119 1120 669601002 1120 1121 630890352 1121 1122 544618153 1122 1123 146639976 1123 1124 268285328 1124 1125 756871936 1125 1126 959951080 1126 1127 919002662 1127 1128 562358466 1128 1129 316525855 1129 1130 459443720 1130 1131 558589805 1131 1132 940412447 1132 1133 492923405 1133 1134 496784885 1134 1135 660064003 1135 1136 979657906 1136 1137 389949974 1137 1138 203471062 1138 1139 813008713 1139 1140 531968396 1140 1141 668388979 1141 1142 249177642 1142 1143 535257277 1143 1144 536206580 1144 1145 87800728 1145 1146 932939341 1146 1147 734787671 1147 1148 490943163 1148 1149 916099098 1149 1150 860945433 1150 1151 116593030 1151 1152 863354284 1152 1153 894507580 1153 1154 17238185 1154 1155 871580098 1155 1156 578211874 1156 1157 500252181 1157 1158 65425209 1158 1159 798271438 1159 1160 97609141 1160 1161 711701599 1161 1162 309784361 1162 1163 458041996 1163 1164 452700684 1164 1165 758805470 1165 1166 747893281 1166 1167 673431420 1167 1168 670215894 1168 1169 327444330 1169 1170 29534286 1170 1171 295961299 1171 1172 199936724 1172 1173 221262491 1173 1174 274416329 1174 1175 248428340 1175 1176 859298317 1176 1177 698169105 1177 1178 989182489 1178 1179 817554189 1179 1180 957986597 1180 1181 977598046 1181 1182 483436751 1182 1183 441464209 1183 1184 695445960 1184 1185 507079824 1185 1186 86504528 1186 1187 450403661 1187 1188 676726337 1188 1189 54657374 1189 1190 592099433 1190 1191 816445479 1191 1192 953130477 1192 1193 827578552 1193 1194 274882686 1194 1195 362166326 1195 1196 328853824 1196 1197 992177418 1197 1198 242460686 1198 1199 926317371 1199 1200 608623964 1200 1201 697979300 1201 1202 666488873 1202 1203 102062674 1203 1204 271741152 1204 1205 92341897 1205 1206 897496906 1206 1207 625247699 1207 1208 428332740 1208 1209 115929376 1209 1210 789160079 1210 1211 607247052 1211 1212 94511573 1212 1213 512795359 1213 1214 784559368 1214 1215 329149850 1215 1216 900918334 1216 1217 675309423 1217 1218 988484623 1218 1219 927966063 1219 1220 200182861 1220 1221 730098654 1221 1222 660744255 1222 1223 906112537 1223 1224 912479958 1224 1225 4663271 1225 1226 820054101 1226 1227 781635981 1227 1228 959663654 1228 1229 749845115 1229 1230 830904292 1230 1231 44062162 1231 1232 276188689 1232 1233 628423115 1233 1234 561324177 1234 1235 853525521 1235 1236 779541356 1236 1237 141418321 1237 1238 244034227 1238 1239 515931427 1239 1240 96318460 1240 1241 902267929 1241 1242 869162959 1242 1243 982091588 1243 1244 496394414 1244 1245 372912461 1245 1246 508854106 1246 1247 970870445 1247 1248 143974192 1248 1249 652901724 1249 1250 209772494 1250 1251 388601501 1251 1252 248017351 1252 1253 441561775 1253 1254 398070570 1254 1255 61212496 1255 1256 74858888 1256 1257 20655527 1257 1258 394181838 1258 1259 99239386 1259 1260 79706143 1260 1261 91533771 1261 1262 990646639 1262 1263 118536974 1263 1264 574080826 1264 1265 525198111 1265 1266 917566265 1266 1267 723023788 1267 1268 391702127 1268 1269 988928250 1269 1270 404378773 1270 1271 955599360 1271 1272 239326622 1272 1273 187565190 1273 1274 912078090 1274 1275 103180410 1275 1276 455717209 1276 1277 988521279 1277 1278 374805544 1278 1279 20715487 1279 1280 628918540 1280 1281 311052872 1281 1282 67435477 1282 1283 845125794 1283 1284 281676964 1284 1285 376776859 1285 1286 699564789 1286 1287 545964688 1287 1288 156425125 1288 1289 657022675 1289 1290 693562197 1290 1291 885387016 1291 1292 350027636 1292 1293 129429587 1293 1294 283049963 1294 1295 767053133 1295 1296 103194861 1296 1297 3811873 1297 1298 373212975 1298 1299 426495654 1299 1300 959656001 1300 1301 280789633 1301 1302 687336614 1302 1303 75448053 1303 1304 710141055 1304 1305 823186075 1305 1306 664546763 1306 1307 385015540 1307 1308 27232836 1308 1309 674704971 1309 1310 919469324 1310 1311 355889682 1311 1312 882574221 1312 1313 449620100 1313 1314 207681259 1314 1315 20816356 1315 1316 692203181 1316 1317 199832673 1317 1318 898432325 1318 1319 697347401 1319 1320 797236825 1320 1321 759783114 1321 1322 802798768 1322 1323 694436127 1323 1324 670465249 1324 1325 194830527 1325 1326 755153917 1326 1327 986506908 1327 1328 30861434 1328 1329 264516164 1329 1330 434832860 1330 1331 314634058 1331 1332 549226166 1332 1333 181875689 1333 1334 854294175 1334 1335 480152225 1335 1336 316346132 1336 1337 866373365 1337 1338 795965463 1338 1339 60404546 1339 1340 695700660 1340 1341 231245359 1341 1342 43377051 1342 1343 805536718 1343 1344 727941411 1344 1345 92489767 1345 1346 601194337 1346 1347 255132244 1347 1348 546423528 1348 1349 539388064 1349 1350 806962095 1350 1351 883183024 1351 1352 38347603 1352 1353 766288949 1353 1354 765515961 1354 1355 468359748 1355 1356 701141432 1356 1357 873247458 1357 1358 860799531 1358 1359 523539481 1359 1360 818615830 1360 1361 867058190 1361 1362 581960277 1362 1363 589224609 1363 1364 769298891 1364 1365 770382677 1365 1366 151596740 1366 1367 544046157 1367 1368 159676603 1368 1369 93247840 1369 1370 50033788 1370 1371 78297404 1371 1372 963233049 1372 1373 243741423 1373 1374 802182101 1374 1375 957871885 1375 1376 258053589 1376 1377 308379128 1377 1378 625203183 1378 1379 491241429 1379 1380 457393058 1380 1381 209462740 1381 1382 91899436 1382 1383 910690979 1383 1384 354357258 1384 1385 64590120 1385 1386 240728162 1386 1387 193829041 1387 1388 618118398 1388 1389 829100175 1389 1390 596711119 1390 1391 771988043 1391 1392 717458024 1392 1393 250451867 1393 1394 384033096 1394 1395 502522395 1395 1396 829549483 1396 1397 814507120 1397 1398 881436590 1398 1399 486487841 1399 1400 710499017 1400 1401 448954615 1401 1402 828549536 1402 1403 463960958 1403 1404 100927597 1404 1405 150831547 1405 1406 480283984 1406 1407 965213663 1407 1408 859429892 1408 1409 301338211 1409 1410 44823923 1410 1411 949510532 1411 1412 347877324 1412 1413 936146514 1413 1414 901535980 1414 1415 318501458 1415 1416 503514563 1416 1417 668330494 1417 1418 527904031 1418 1419 219770972 1419 1420 655330721 1420 1421 142887832 1421 1422 827751310 1422 1423 32946418 1423 1424 368211951 1424 1425 488559308 1425 1426 921031813 1426 1427 143359675 1427 1428 824750778 1428 1429 747627867 1429 1430 392208646 1430 1431 621619621 1431 1432 852357074 1432 1433 673150328 1433 1434 782667028 1434 1435 43354096 1435 1436 821615899 1436 1437 695782893 1437 1438 419749265 1438 1439 131127667 1439 1440 821031810 1440 1441 165642199 1441 1442 46637485 1442 1443 698935462 1443 1444 694099556 1444 1445 103330608 1445 1446 532397019 1446 1447 625196509 1447 1448 707778166 1448 1449 929579118 1449 1450 871379494 1450 1451 830579601 1451 1452 347901103 1452 1453 815887908 1453 1454 181791275 1454 1455 209032664 1455 1456 209805267 1456 1457 401365704 1457 1458 739568311 1458 1459 11105015 1459 1460 343855773 1460 1461 601504399 1461 1462 421570301 1462 1463 670564622 1463 1464 532760201 1464 1465 270032757 1465 1466 128984948 1466 1467 609240817 1467 1468 971797819 1468 1469 195429209 1469 1470 563649611 1470 1471 394935319 1471 1472 864411791 1472 1473 590076844 1473 1474 480510270 1474 1475 673019082 1475 1476 245220039 1476 1477 732632769 1477 1478 531456041 1478 1479 794419337 1479 1480 421870721 1480 1481 658995107 1481 1482 66164294 1482 1483 966244559 1483 1484 520287004 1484 1485 311860809 1485 1486 153742628 1486 1487 288596824 1487 1488 561459065 1488 1489 16240668 1489 1490 996592543 1490 1491 116032022 1491 1492 781573575 1492 1493 469968495 1493 1494 427185239 1494 1495 535415285 1495 1496 501051370 1496 1497 450454887 1497 1498 856349093 1498 1499 435046816 1499 1500 501291824 1500 1501 906674039 1501 1502 953253351 1502 1503 159475118 1503 1504 723829059 1504 1505 22142424 1505 1506 614164336 1506 1507 688293805 1507 1508 416783724 1508 1509 469182464 1509 1510 112944861 1510 1511 440494351 1511 1512 429030449 1512 1513 410007173 1513 1514 450643634 1514 1515 162500376 1515 1516 240512533 1516 1517 743300875 1517 1518 221817994 1518 1519 999972854 1519 1520 674542877 1520 1521 589434835 1521 1522 447134104 1522 1523 252675324 1523 1524 785657670 1524 1525 66328505 1525 1526 477914721 1526 1527 500115881 1527 1528 849059965 1528 1529 976153991 1529 1530 104580572 1530 1531 602421224 1531 1532 191018174 1532 1533 390096996 1533 1534 989924013 1534 1535 186255990 1535 1536 896741754 1536 1537 105052985 1537 1538 351155265 1538 1539 246719936 1539 1540 267318132 1540 1541 442331089 1541 1542 887981682 1542 1543 74748141 1543 1544 440328607 1544 1545 80927730 1545 1546 570841758 1546 1547 264539573 1547 1548 307201866 1548 1549 504446852 1549 1550 738670844 1550 1551 435513989 1551 1552 751283808 1552 1553 667226628 1553 1554 322940688 1554 1555 815358996 1555 1556 261401229 1556 1557 633386397 1557 1558 775340050 1558 1559 924944336 1559 1560 61854241 1560 1561 404397409 1561 1562 387681214 1562 1563 914427197 1563 1564 297510391 1564 1565 648994583 1565 1566 435370175 1566 1567 410519764 1567 1568 399922956 1568 1569 166807683 1569 1570 662795631 1570 1571 310521432 1571 1572 787404730 1572 1573 238952469 1573 1574 203593737 1574 1575 364499416 1575 1576 132220543 1576 1577 884906989 1577 1578 169966670 1578 1579 314097831 1579 1580 374480072 1580 1581 331089676 1581 1582 855478465 1582 1583 159076075 1583 1584 839823692 1584 1585 850821743 1585 1586 342635121 1586 1587 350305745 1587 1588 754555492 1588 1589 860814084 1589 1590 763289739 1590 1591 95823183 1591 1592 360598843 1592 1593 263859682 1593 1594 63717285 1594 1595 922731177 1595 1596 211131173 1596 1597 650346906 1597 1598 76800783 1598 1599 857905829 1599 1600 692084311 1600 1601 431436388 1601 1602 126984141 1602 1603 160380668 1603 1604 529548928 1604 1605 33504793 1605 1606 633128173 1606 1607 579018951 1607 1608 844250045 1608 1609 422399032 1609 1610 720885751 1610 1611 844868141 1611 1612 250926311 1612 1613 441761917 1613 1614 977404470 1614 1615 10404426 1615 1616 343033625 1616 1617 240478622 1617 1618 355574616 1618 1619 344434012 1619 1620 235208876 1620 1621 639074350 1621 1622 956685667 1622 1623 499525876 1623 1624 546803345 1624 1625 298459904 1625 1626 105502614 1626 1627 927683654 1627 1628 459617721 1628 1629 253102987 1629 1630 270935222 1630 1631 330411108 1631 1632 903614414 1632 1633 139171993 1633 1634 127502891 1634 1635 316163383 1635 1636 499341211 1636 1637 286496059 1637 1638 805584798 1638 1639 784752200 1639 1640 591125266 1640 1641 598267300 1641 1642 48217031 1642 1643 342258731 1643 1644 498181993 1644 1645 928354 1645 1646 605599880 1646 1647 197612894 1647 1648 262357184 1648 1649 330026307 1649 1650 510323399 1650 1651 391117724 1651 1652 793301996 1652 1653 538866817 1653 1654 913314135 1654 1655 218601782 1655 1656 406718693 1656 1657 591992270 1657 1658 874891164 1658 1659 357924944 1659 1660 593581356 1660 1661 896617191 1661 1662 418732659 1662 1663 305751261 1663 1664 754248866 1664 1665 415760678 1665 1666 429192546 1666 1667 936341890 1667 1668 38399421 1668 1669 42999349 1669 1670 53325921 1670 1671 36012697 1671 1672 183461220 1672 1673 915003869 1673 1674 401699903 1674 1675 351592557 1675 1676 913722108 1676 1677 466712499 1677 1678 569234677 1678 1679 199566513 1679 1680 482313109 1680 1681 93262080 1681 1682 99744323 1682 1683 65834952 1683 1684 239819777 1684 1685 778652227 1685 1686 755669242 1686 1687 360710502 1687 1688 178009180 1688 1689 500676982 1689 1690 642353489 1690 1691 187657339 1691 1692 855535735 1692 1693 500011124 1693 1694 661862257 1694 1695 665843254 1695 1696 946249458 1696 1697 549379271 1697 1698 99726928 1698 1699 832767101 1699 1700 492679731 1700 1701 174183116 1701 1702 246360692 1702 1703 4420825 1703 1704 363306462 1704 1705 304788323 1705 1706 723158107 1706 1707 250109326 1707 1708 462126662 1708 1709 397146429 1709 1710 726455993 1710 1711 476202043 1711 1712 529492758 1712 1713 687952040 1713 1714 870492972 1714 1715 153596481 1715 1716 73426200 1716 1717 142826237 1717 1718 938022204 1718 1719 352547792 1719 1720 663244237 1720 1721 574161590 1721 1722 315938917 1722 1723 149004152 1723 1724 923496639 1724 1725 777937039 1725 1726 930689766 1726 1727 100529935 1727 1728 990956719 1728 1729 251119539 1729 1730 462245647 1730 1731 494022510 1731 1732 988251564 1732 1733 500799664 1733 1734 396622682 1734 1735 983900867 1735 1736 654981388 1736 1737 74950966 1737 1738 664756344 1738 1739 87065907 1739 1740 388535981 1740 1741 103342405 1741 1742 127241515 1742 1743 917067066 1743 1744 952085893 1744 1745 786524528 1745 1746 325464207 1746 1747 743491581 1747 1748 838584559 1748 1749 200576003 1749 1750 533874805 1750 1751 837336284 1751 1752 151198257 1752 1753 166922444 1753 1754 506202875 1754 1755 697725445 1755 1756 910808230 1756 1757 438011645 1757 1758 703441862 1758 1759 678811683 1759 1760 380461708 1760 1761 323191593 1761 1762 898530015 1762 1763 101553460 1763 1764 24593004 1764 1765 986167148 1765 1766 660718887 1766 1767 559559801 1767 1768 509067554 1768 1769 683817384 1769 1770 446894200 1770 1771 49616262 1771 1772 392685192 1772 1773 714748393 1773 1774 290108762 1774 1775 64733305 1775 1776 21585603 1776 1777 381544170 1777 1778 129897055 1778 1779 142127943 1779 1780 208444969 1780 1781 476277937 1781 1782 678785308 1782 1783 116234802 1783 1784 222470094 1784 1785 97910613 1785 1786 136520900 1786 1787 193971031 1787 1788 356256938 1788 1789 581525472 1789 1790 526197346 1790 1791 106564451 1791 1792 755301736 1792 1793 703622322 1793 1794 290900838 1794 1795 284335309 1795 1796 390832054 1796 1797 128305053 1797 1798 765899712 1798 1799 877779139 1799 1800 649506176 1800 1801 572710736 1801 1802 159634999 1802 1803 38067714 1803 1804 423522517 1804 1805 174489336 1805 1806 214038827 1806 1807 666932826 1807 1808 578152724 1808 1809 320905184 1809 1810 158199711 1810 1811 469682815 1811 1812 784256406 1812 1813 506194427 1813 1814 710187313 1814 1815 578125302 1815 1816 980050735 1816 1817 117782536 1817 1818 482095142 1818 1819 399804636 1819 1820 136680150 1820 1821 1268024 1821 1822 726252567 1822 1823 463438614 1823 1824 299981437 1824 1825 430819880 1825 1826 912786564 1826 1827 215390514 1827 1828 168376721 1828 1829 692939484 1829 1830 930152612 1830 1831 576446228 1831 1832 515966410 1832 1833 493606734 1833 1834 957503531 1834 1835 740067672 1835 1836 189891603 1836 1837 832946109 1837 1838 261608018 1838 1839 358328153 1839 1840 452470477 1840 1841 721286674 1841 1842 580826552 1842 1843 732770683 1843 1844 742594637 1844 1845 462447508 1845 1846 552019792 1846 1847 856681886 1847 1848 616009295 1848 1849 140902165 1849 1850 61938039 1850 1851 790524260 1851 1852 987341283 1852 1853 167451603 1853 1854 850626431 1854 1855 189542723 1855 1856 105890692 1856 1857 727393238 1857 1858 319288337 1858 1859 712711289 1859 1860 58036981 1860 1861 892427735 1861 1862 379328195 1862 1863 207357600 1863 1864 222342160 1864 1865 447131086 1865 1866 236123637 1866 1867 434104417 1867 1868 38888711 1868 1869 616322988 1869 1870 930812175 1870 1871 543658507 1871 1872 626059276 1872 1873 554991957 1873 1874 384976374 1874 1875 852413719 1875 1876 67269395 1876 1877 67859003 1877 1878 34752923 1878 1879 589797975 1879 1880 405835183 1880 1881 846367896 1881 1882 267707821 1882 1883 630670523 1883 1884 719110937 1884 1885 970397767 1885 1886 466804591 1886 1887 4589760 1887 1888 329995072 1888 1889 607559588 1889 1890 392437366 1890 1891 64287322 1891 1892 260950446 1892 1893 614104744 1893 1894 384434095 1894 1895 794624406 1895 1896 789605818 1896 1897 78486423 1897 1898 152763560 1898 1899 564628909 1899 1900 291009642 1900 1901 305304339 1901 1902 318536769 1902 1903 666469041 1903 1904 515249027 1904 1905 865679190 1905 1906 458821380 1906 1907 791214468 1907 1908 523947892 1908 1909 298779598 1909 1910 449477774 1910 1911 866123734 1911 1912 914858013 1912 1913 37963631 1913 1914 623958011 1914 1915 922190510 1915 1916 348351802 1916 1917 389320356 1917 1918 737316312 1918 1919 137821646 1919 1920 245367476 1920 1921 515941550 1921 1922 333411062 1922 1923 816735270 1923 1924 422978071 1924 1925 574002766 1925 1926 722827192 1926 1927 945320551 1927 1928 322485472 1928 1929 449396649 1929 1930 427990985 1930 1931 612078673 1931 1932 148494063 1932 1933 958574469 1933 1934 921040706 1934 1935 176711871 1935 1936 646388445 1936 1937 586264793 1937 1938 680073366 1938 1939 537329067 1939 1940 940774308 1940 1941 738085403 1941 1942 533599826 1942 1943 335356637 1943 1944 644108072 1944 1945 3454657 1945 1946 827714022 1946 1947 425826005 1947 1948 909029105 1948 1949 174056310 1949 1950 762379754 1950 1951 108671721 1951 1952 407127864 1952 1953 363314882 1953 1954 853973760 1954 1955 318257442 1955 1956 308217433 1956 1957 357033947 1957 1958 66840809 1958 1959 674588169 1959 1960 247111421 1960 1961 972585684 1961 1962 228826457 1962 1963 598325237 1963 1964 904977168 1964 1965 772970938 1965 1966 991012479 1966 1967 568412457 1967 1968 650817466 1968 1969 70606636 1969 1970 709015110 1970 1971 246575322 1971 1972 691781811 1972 1973 373092637 1973 1974 114999847 1974 1975 576431789 1975 1976 829985272 1976 1977 300740775 1977 1978 55369523 1978 1979 598653025 1979 1980 865765492 1980 1981 290956016 1981 1982 507757109 1982 1983 843309066 1983 1984 495922456 1984 1985 518852245 1985 1986 269697159 1986 1987 820313174 1987 1988 819144024 1988 1989 562106831 1989 1990 567407769 1990 1991 528290006 1991 1992 752422187 1992 1993 809460997 1993 1994 880949273 1994 1995 881843106 1995 1996 870085978 1996 1997 13649227 1997 1998 69085874 1998 1999 584434353 1999 2000 834246972 2000 2001 175563221 2001 2002 147722722 2002 2003 468776159 2003 2004 152689525 2004 2005 110181927 2005 2006 590496532 2006 2007 242924783 2007 2008 911260899 2008 2009 838791045 2009 2010 970621556 2010 2011 663128419 2011 2012 13409442 2012 2013 598580402 2013 2014 465283799 2014 2015 137644010 2015 2016 467890903 2016 2017 39386426 2017 2018 303687741 2018 2019 340859071 2019 2020 919741951 2020 2021 979229813 2021 2022 772544414 2022 2023 64867173 2023 2024 459936915 2024 2025 853040607 2025 2026 232454754 2026 2027 997513390 2027 2028 303769792 2028 2029 240815693 2029 2030 449420096 2030 2031 700203150 2031 2032 522880502 2032 2033 762067459 2033 2034 707623066 2034 2035 641122461 2035 2036 216238305 2036 2037 391492318 2037 2038 857975425 2038 2039 728683076 2039 2040 432309715 2040 2041 612011409 2041 2042 6820298 2042 2043 71111377 2043 2044 261572717 2044 2045 751271690 2045 2046 745390795 2046 2047 402180267 2047 2048 25388006 2048 2049 937837555 2049 2050 134262707 2050 2051 793452959 2051 2052 521378299 2052 2053 990632020 2053 2054 619628675 2054 2055 929328216 2055 2056 775969907 2056 2057 482318165 2057 2058 51962029 2058 2059 7612653 2059 2060 335816526 2060 2061 731609377 2061 2062 467197511 2062 2063 591533717 2063 2064 310914442 2064 2065 558900967 2065 2066 379637996 2066 2067 502977142 2067 2068 754047633 2068 2069 253049082 2069 2070 930739760 2070 2071 87652762 2071 2072 58603586 2072 2073 157326850 2073 2074 220360602 2074 2075 329404104 2075 2076 679308046 2076 2077 757367509 2077 2078 559389695 2078 2079 342313948 2079 2080 670750920 2080 2081 972093361 2081 2082 37792041 2082 2083 172920086 2083 2084 429865392 2084 2085 642459427 2085 2086 971548589 2086 2087 875881191 2087 2088 5655373 2088 2089 585910833 2089 2090 715545127 2090 2091 435929683 2091 2092 859952404 2092 2093 878644996 2093 2094 140549616 2094 2095 968050537 2095 2096 621351658 2096 2097 511430413 2097 2098 537426128 2098 2099 172088618 2099 2100 155743684 2100 2101 612325102 2101 2102 475102544 2102 2103 890692282 2103 2104 439064173 2104 2105 662119478 2105 2106 443031560 2106 2107 743991321 2107 2108 591380216 2108 2109 537317982 2109 2110 458203282 2110 2111 253545274 2111 2112 354663322 2112 2113 761700601 2113 2114 545860360 2114 2115 949121402 2115 2116 360454487 2116 2117 951015932 2117 2118 502087809 2118 2119 775060229 2119 2120 701033935 2120 2121 720260313 2121 2122 49593986 2122 2123 752868773 2123 2124 153012809 2124 2125 533448096 2125 2126 63653561 2126 2127 918736693 2127 2128 321721143 2128 2129 819886926 2129 2130 70932727 2130 2131 773897366 2131 2132 78276474 2132 2133 121172250 2133 2134 799065356 2134 2135 288144188 2135 2136 156314182 2136 2137 629375962 2137 2138 661408676 2138 2139 425100290 2139 2140 510228528 2140 2141 143314765 2141 2142 448694270 2142 2143 70641 2143 2144 607573983 2144 2145 748042196 2145 2146 950393743 2146 2147 176990812 2147 2148 175882104 2148 2149 654671498 2149 2150 860032893 2150 2151 22920706 2151 2152 487123020 2152 2153 307523687 2153 2154 352009123 2154 2155 869018117 2155 2156 406009811 2156 2157 192139542 2157 2158 758322085 2158 2159 601158857 2159 2160 472954326 2160 2161 82618541 2161 2162 93484911 2162 2163 422145 2163 2164 294344028 2164 2165 197170359 2165 2166 234196116 2166 2167 184084673 2167 2168 886061855 2168 2169 668054316 2169 2170 605197110 2170 2171 6268668 2171 2172 431314737 2172 2173 688246777 2173 2174 444816187 2174 2175 867986053 2175 2176 723882365 2176 2177 50366889 2177 2178 458437898 2178 2179 724855651 2179 2180 810153428 2180 2181 309804969 2181 2182 589755151 2182 2183 873284851 2183 2184 604726639 2184 2185 288181409 2185 2186 842089432 2186 2187 853381192 2187 2188 597825328 2188 2189 289328271 2189 2190 654469929 2190 2191 618059988 2191 2192 328572928 2192 2193 804452909 2193 2194 332935599 2194 2195 368555351 2195 2196 374430709 2196 2197 158807238 2197 2198 176028039 2198 2199 753459162 2199 2200 531532222 2200 2201 463474693 2201 2202 366206245 2202 2203 449468958 2203 2204 114686137 2204 2205 633860021 2205 2206 609450136 2206 2207 206278538 2207 2208 584791031 2208 2209 129781522 2209 2210 703277824 2210 2211 565433691 2211 2212 729862297 2212 2213 493861015 2213 2214 788660472 2214 2215 636724162 2215 2216 251105102 2216 2217 837509365 2217 2218 564875681 2218 2219 441150760 2219 2220 609948959 2220 2221 539236936 2221 2222 382048657 2222 2223 593711490 2223 2224 770034355 2224 2225 605812826 2225 2226 336191571 2226 2227 954160141 2227 2228 38228652 2228 2229 900957628 2229 2230 78269184 2230 2231 479454827 2231 2232 125368219 2232 2233 387381043 2233 2234 806671560 2234 2235 275173114 2235 2236 82315177 2236 2237 934104245 2237 2238 22331591 2238 2239 803580924 2239 2240 885397913 2240 2241 292547817 2241 2242 186834987 2242 2243 938889278 2243 2244 205956882 2244 2245 841830815 2245 2246 11026129 2246 2247 116277986 2247 2248 464748616 2248 2249 855284015 2249 2250 908654694 2250 2251 443536262 2251 2252 109144596 2252 2253 252946886 2253 2254 371631579 2254 2255 547145585 2255 2256 445124184 2256 2257 589730922 2257 2258 484342843 2258 2259 841232634 2259 2260 860291779 2260 2261 579302540 2261 2262 821527030 2262 2263 662912737 2263 2264 433611004 2264 2265 327977015 2265 2266 214881995 2266 2267 638211374 2267 2268 961987866 2268 2269 841539131 2269 2270 228353599 2270 2271 179960456 2271 2272 722384062 2272 2273 402886170 2273 2274 772818637 2274 2275 957360196 2275 2276 218056510 2276 2277 748747229 2277 2278 912961378 2278 2279 167378745 2279 2280 592798141 2280 2281 17864861 2281 2282 266985395 2282 2283 728662660 2283 2284 442654735 2284 2285 213930529 2285 2286 518785322 2286 2287 763838282 2287 2288 351503496 2288 2289 329370656 2289 2290 462196182 2290 2291 126016933 2291 2292 55835332 2292 2293 171450537 2293 2294 7189202 2294 2295 912705540 2295 2296 559841959 2296 2297 462124058 2297 2298 894806036 2298 2299 35647989 2299 2300 721976040 2300 2301 849456197 2301 2302 485185832 2302 2303 192231083 2303 2304 802004617 2304 2305 180411183 2305 2306 295645280 2306 2307 762867117 2307 2308 441782640 2308 2309 674334504 2309 2310 819829343 2310 2311 469152297 2311 2312 321067626 2312 2313 29447497 2313 2314 819091312 2314 2315 102890568 2315 2316 823402264 2316 2317 892820509 2317 2318 184378499 2318 2319 932252 2319 2320 50763383 2320 2321 367112886 2321 2322 786709002 2322 2323 189321170 2323 2324 832473305 2324 2325 470678485 2325 2326 71201190 2326 2327 479822521 2327 2328 775765978 2328 2329 575786263 2329 2330 590022037 2330 2331 922344697 2331 2332 436764042 2332 2333 67643842 2333 2334 416043298 2334 2335 681019077 2335 2336 64139549 2336 2337 789348060 2337 2338 258142672 2338 2339 582287545 2339 2340 608083607 2340 2341 291606961 2341 2342 259436567 2342 2343 522243314 2343 2344 600087480 2344 2345 653946998 2345 2346 269497324 2346 2347 627328444 2347 2348 831064323 2348 2349 314446830 2349 2350 411157328 2350 2351 251971509 2351 2352 902135969 2352 2353 986284546 2353 2354 625775950 2354 2355 451956156 2355 2356 367887445 2356 2357 91765449 2357 2358 765279908 2358 2359 92789637 2359 2360 988389660 2360 2361 663467792 2361 2362 249671478 2362 2363 587612536 2363 2364 540681921 2364 2365 889716627 2365 2366 534588422 2366 2367 814861315 2367 2368 77303036 2368 2369 71937536 2369 2370 90457563 2370 2371 73624705 2371 2372 79991908 2372 2373 850292383 2373 2374 545935097 2374 2375 904827068 2375 2376 752656354 2376 2377 619837615 2377 2378 725750069 2378 2379 128580117 2379 2380 120933301 2380 2381 424169261 2381 2382 137101437 2382 2383 225297488 2383 2384 664698377 2384 2385 705264714 2385 2386 280021170 2386 2387 786436814 2387 2388 916396174 2388 2389 982275871 2389 2390 450760130 2390 2391 684815386 2391 2392 387619222 2392 2393 224175374 2393 2394 935843334 2394 2395 258554153 2395 2396 501099996 2396 2397 123559592 2397 2398 164743144 2398 2399 607230082 2399 2400 374245514 2400 2401 497476128 2401 2402 467208566 2402 2403 567079758 2403 2404 691144926 2404 2405 135334979 2405 2406 478047406 2406 2407 408668811 2407 2408 109953340 2408 2409 316714917 2409 2410 579765954 2410 2411 143893122 2411 2412 125587541 2412 2413 312613048 2413 2414 204844847 2414 2415 809073704 2415 2416 931825519 2416 2417 78820039 2417 2418 336724242 2418 2419 12771333 2419 2420 493892631 2420 2421 484199472 2421 2422 201500812 2422 2423 297559663 2423 2424 308085568 2424 2425 733539745 2425 2426 803202506 2426 2427 444218672 2427 2428 80339637 2428 2429 162661686 2429 2430 508178140 2430 2431 489758945 2431 2432 307794664 2432 2433 839815332 2433 2434 368514212 2434 2435 209331054 2435 2436 479157300 2436 2437 417672063 2437 2438 413740587 2438 2439 217823170 2439 2440 394955868 2440 2441 593917431 2441 2442 914942459 2442 2443 487766214 2443 2444 107604070 2444 2445 721864334 2445 2446 702130702 2446 2447 618833744 2447 2448 554715851 2448 2449 132371732 2449 2450 701328218 2450 2451 215630273 2451 2452 575645924 2452 2453 837309914 2453 2454 613501632 2454 2455 60032002 2455 2456 905856712 2456 2457 59312023 2457 2458 469266825 2458 2459 974057803 2459 2460 197406084 2460 2461 153073703 2461 2462 265741607 2462 2463 327534261 2463 2464 577167495 2464 2465 63260308 2465 2466 996713395 2466 2467 184879074 2467 2468 849253332 2468 2469 431929251 2469 2470 145090404 2470 2471 731036536 2471 2472 970292493 2472 2473 288294798 2473 2474 29828217 2474 2475 830571754 2475 2476 862792590 2476 2477 121797293 2477 2478 610064115 2478 2479 121562919 2479 2480 682075951 2480 2481 834270627 2481 2482 860863991 2482 2483 267854297 2483 2484 76016968 2484 2485 845913767 2485 2486 756084359 2486 2487 325403436 2487 2488 962384006 2488 2489 191140867 2489 2490 473575216 2490 2491 247465026 2491 2492 620188252 2492 2493 953775962 2493 2494 254806798 2494 2495 410099505 2495 2496 840797963 2496 2497 622034414 2497 2498 554996041 2498 2499 104082970 2499 2500 815223567 2500 2501 729054354 2501 2502 230909847 2502 2503 378550690 2503 2504 116094182 2504 2505 928628405 2505 2506 849172566 2506 2507 771794243 2507 2508 319302578 2508 2509 35997080 2509 2510 674329005 2510 2511 26279771 2511 2512 190334177 2512 2513 471310779 2513 2514 326360128 2514 2515 65807456 2515 2516 179665533 2516 2517 575612502 2517 2518 562008463 2518 2519 55993138 2519 2520 440186386 2520 2521 751295235 2521 2522 241031660 2522 2523 203878537 2523 2524 323328567 2524 2525 596388217 2525 2526 338723351 2526 2527 502459277 2527 2528 66042043 2528 2529 512673650 2529 2530 835106935 2530 2531 932036485 2531 2532 186519406 2532 2533 976368302 2533 2534 463117303 2534 2535 971611303 2535 2536 794040201 2536 2537 577870097 2537 2538 236760187 2538 2539 867562510 2539 2540 331076026 2540 2541 143585000 2541 2542 262442238 2542 2543 163273424 2543 2544 907454281 2544 2545 521781066 2545 2546 115031055 2546 2547 18424576 2547 2548 632155288 2548 2549 776372562 2549 2550 32479889 2550 2551 251325906 2551 2552 398437158 2552 2553 471705647 2553 2554 59985640 2554 2555 978187435 2555 2556 824134131 2556 2557 683780789 2557 2558 727868718 2558 2559 482504183 2559 2560 69538196 2560 2561 57630642 2561 2562 723907314 2562 2563 185071920 2563 2564 180811203 2564 2565 301580820 2565 2566 480652708 2566 2567 276692690 2567 2568 566359378 2568 2569 596271639 2569 2570 805069511 2570 2571 795577135 2571 2572 438004220 2572 2573 571517862 2573 2574 396204743 2574 2575 856953930 2575 2576 964303640 2576 2577 887395748 2577 2578 235194290 2578 2579 933581579 2579 2580 959180710 2580 2581 929705493 2581 2582 26056977 2582 2583 925003726 2583 2584 883101858 2584 2585 170262957 2585 2586 943246255 2586 2587 502344702 2587 2588 579529622 2588 2589 105614711 2589 2590 981023053 2590 2591 956336200 2591 2592 397090322 2592 2593 526899579 2593 2594 447082125 2594 2595 921586579 2595 2596 899000380 2596 2597 691419153 2597 2598 725388334 2598 2599 693031251 2599 2600 259321787 2600 2601 788839704 2601 2602 581860218 2602 2603 267224470 2603 2604 486639704 2604 2605 759965844 2605 2606 715400256 2606 2607 123215836 2607 2608 588257287 2608 2609 26850636 2609 2610 619949431 2610 2611 827485072 2611 2612 236335976 2612 2613 762699420 2613 2614 165967612 2614 2615 676241713 2615 2616 115163534 2616 2617 923405061 2617 2618 525603401 2618 2619 679291364 2619 2620 736773532 2620 2621 762730792 2621 2622 463928128 2622 2623 21496051 2623 2624 13074922 2624 2625 768868738 2625 2626 234440118 2626 2627 882920444 2627 2628 329657699 2628 2629 669800534 2629 2630 206871963 2630 2631 980857791 2631 2632 710579329 2632 2633 320703429 2633 2634 800974548 2634 2635 244970016 2635 2636 596138877 2636 2637 303131721 2637 2638 161483260 2638 2639 839387306 2639 2640 977938182 2640 2641 828531446 2641 2642 54626414 2642 2643 129048889 2643 2644 763425578 2644 2645 622728311 2645 2646 488293597 2646 2647 55827661 2647 2648 894677245 2648 2649 900643600 2649 2650 885576436 2650 2651 419792396 2651 2652 276643569 2652 2653 899130622 2653 2654 127744878 2654 2655 408786034 2655 2656 205486645 2656 2657 983680776 2657 2658 367803206 2658 2659 984679070 2659 2660 769374891 2660 2661 931677345 2661 2662 426381258 2662 2663 524265826 2663 2664 416538179 2664 2665 840761945 2665 2666 36865017 2666 2667 332772059 2667 2668 312921076 2668 2669 79446969 2669 2670 178563416 2670 2671 37843194 2671 2672 253630955 2672 2673 24714519 2673 2674 328531613 2674 2675 31232332 2675 2676 753894556 2676 2677 717341809 2677 2678 923173646 2678 2679 966088104 2679 2680 659430808 2680 2681 11597565 2681 2682 290062509 2682 2683 518269031 2683 2684 671126893 2684 2685 587801307 2685 2686 942768811 2686 2687 534831727 2687 2688 342403490 2688 2689 976320067 2689 2690 291047636 2690 2691 42808331 2691 2692 416336101 2692 2693 346050171 2693 2694 612782099 2694 2695 634110601 2695 2696 167532628 2696 2697 829282573 2697 2698 706006385 2698 2699 807885906 2699 2700 313794398 2700 2701 521175660 2701 2702 740908140 2702 2703 710952013 2703 2704 202955505 2704 2705 12319572 2705 2706 845192531 2706 2707 38774 2707 2708 233927517 2708 2709 789880332 2709 2710 519251185 2710 2711 308886954 2711 2712 627626582 2712 2713 492245307 2713 2714 234983781 2714 2715 954771730 2715 2716 556138776 2716 2717 446376036 2717 2718 666975785 2718 2719 728762021 2719 2720 628262912 2720 2721 585551521 2721 2722 152056427 2722 2723 434038826 2723 2724 153753399 2724 2725 48298844 2725 2726 722863516 2726 2727 597446016 2727 2728 72319290 2728 2729 605062228 2729 2730 995710386 2730 2731 261057486 2731 2732 333126635 2732 2733 20507488 2733 2734 354037323 2734 2735 380657690 2735 2736 741564510 2736 2737 369731903 2737 2738 276549409 2738 2739 228979317 2739 2740 820653179 2740 2741 798230939 2741 2742 391577709 2742 2743 290340012 2743 2744 354115951 2744 2745 672482520 2745 2746 832273763 2746 2747 775610183 2747 2748 910750848 2748 2749 696757647 2749 2750 763124501 2750 2751 843328331 2751 2752 46718186 2752 2753 220074038 2753 2754 484704737 2754 2755 382189718 2755 2756 821307271 2756 2757 164945883 2757 2758 59387092 2758 2759 446458118 2759 2760 294399436 2760 2761 320692189 2761 2762 303555175 2762 2763 339528797 2763 2764 989703863 2764 2765 79939133 2765 2766 269771266 2766 2767 237658440 2767 2768 349470977 2768 2769 87981950 2769 2770 781986614 2770 2771 474514712 2771 2772 982025695 2772 2773 551548069 2773 2774 628413588 2774 2775 823436426 2775 2776 877429876 2776 2777 39788384 2777 2778 604894760 2778 2779 973120962 2779 2780 822051798 2780 2781 242513813 2781 2782 995256151 2782 2783 897402811 2783 2784 428658477 2784 2785 11436494 2785 2786 521813952 2786 2787 166713801 2787 2788 522981999 2788 2789 389905547 2789 2790 795297621 2790 2791 853483568 2791 2792 194596534 2792 2793 351703302 2793 2794 372867657 2794 2795 108068896 2795 2796 261843351 2796 2797 117999086 2797 2798 405351832 2798 2799 155214478 2799 2800 37073129 2800 2801 940697699 2801 2802 374996614 2802 2803 970128570 2803 2804 677039000 2804 2805 556915379 2805 2806 378030554 2806 2807 361392736 2807 2808 717145376 2808 2809 731251878 2809 2810 650941334 2810 2811 639500105 2811 2812 450718994 2812 2813 641870131 2813 2814 635088978 2814 2815 866137587 2815 2816 709425593 2816 2817 525707695 2817 2818 255748766 2818 2819 220817895 2819 2820 182118658 2820 2821 818106732 2821 2822 828672 2822 2823 262611242 2823 2824 282323464 2824 2825 464069500 2825 2826 397456077 2826 2827 916062012 2827 2828 465598611 2828 2829 505771282 2829 2830 986155167 2830 2831 198779694 2831 2832 605667082 2832 2833 580749848 2833 2834 878413315 2834 2835 608818170 2835 2836 814947584 2836 2837 93541169 2837 2838 204052444 2838 2839 61762385 2839 2840 885503643 2840 2841 781295914 2841 2842 370123684 2842 2843 99554083 2843 2844 360752748 2844 2845 70550208 2845 2846 113435548 2846 2847 929024742 2847 2848 456938481 2848 2849 454279671 2849 2850 222180382 2850 2851 303319430 2851 2852 468971571 2852 2853 548790798 2853 2854 387888784 2854 2855 780308302 2855 2856 282326127 2856 2857 173161501 2857 2858 452619477 2858 2859 672291090 2859 2860 953825569 2860 2861 220599295 2861 2862 185801437 2862 2863 56484969 2863 2864 488873805 2864 2865 189116907 2865 2866 219748610 2866 2867 860172409 2867 2868 69493598 2868 2869 319927815 2869 2870 289849447 2870 2871 325766178 2871 2872 267390716 2872 2873 640921196 2873 2874 282047560 2874 2875 270843068 2875 2876 13271282 2876 2877 214880012 2877 2878 610019891 2878 2879 376351637 2879 2880 740956971 2880 2881 734186741 2881 2882 178512352 2882 2883 525795788 2883 2884 30605446 2884 2885 923048449 2885 2886 493265351 2886 2887 678324156 2887 2888 849141824 2888 2889 960689975 2889 2890 443221157 2890 2891 595790952 2891 2892 434114031 2892 2893 724141381 2893 2894 735553816 2894 2895 403255328 2895 2896 155059835 2896 2897 895382587 2897 2898 232843469 2898 2899 742014815 2899 2900 809451433 2900 2901 621416515 2901 2902 11565320 2902 2903 355048618 2903 2904 293493946 2904 2905 143017135 2905 2906 962672918 2906 2907 122002546 2907 2908 214092588 2908 2909 160114659 2909 2910 837227255 2910 2911 115110411 2911 2912 487026468 2912 2913 679262688 2913 2914 397342230 2914 2915 643974212 2915 2916 112844038 2916 2917 328575853 2917 2918 141260851 2918 2919 208582055 2919 2920 687903783 2920 2921 689061860 2921 2922 24143457 2922 2923 232747598 2923 2924 322207898 2924 2925 687237526 2925 2926 488330795 2926 2927 192058208 2927 2928 359985703 2928 2929 217934044 2929 2930 334451922 2930 2931 827631655 2931 2932 850841690 2932 2933 584604091 2933 2934 563348658 2934 2935 309481167 2935 2936 691125687 2936 2937 382613043 2937 2938 136132286 2938 2939 132236811 2939 2940 726900516 2940 2941 388839994 2941 2942 128517085 2942 2943 470729694 2943 2944 488242255 2944 2945 24539035 2945 2946 123906820 2946 2947 774836803 2947 2948 236580890 2948 2949 21631839 2949 2950 966975899 2950 2951 595638423 2951 2952 461897251 2952 2953 292973166 2953 2954 80191476 2954 2955 865168072 2955 2956 109618069 2956 2957 973121983 2957 2958 891155508 2958 2959 979109369 2959 2960 819521747 2960 2961 347440004 2961 2962 756422333 2962 2963 237762591 2963 2964 931042351 2964 2965 441104897 2965 2966 401181883 2966 2967 793333338 2967 2968 246987394 2968 2969 547231188 2969 2970 644990989 2970 2971 817436058 2971 2972 476819497 2972 2973 396909158 2973 2974 426358221 2974 2975 300610909 2975 2976 452599201 2976 2977 913403773 2977 2978 87084414 2978 2979 286025366 2979 2980 743737787 2980 2981 406739437 2981 2982 771997393 2982 2983 361119914 2983 2984 428532603 2984 2985 611970414 2985 2986 573052436 2986 2987 108059795 2987 2988 858659219 2988 2989 407814537 2989 2990 182825272 2990 2991 549450279 2991 2992 54088567 2992 2993 507976109 2993 2994 452648829 2994 2995 428728861 2995 2996 121411166 2996 2997 438587836 2997 2998 69874241 2998 2999 195974227 2999 3000 10096013