3000 2999 100 1 2 471346306 2 3 470151143 3 4 70960878 4 5 99701338 5 6 272085046 6 7 118210817 7 8 117324411 8 9 568520461 9 10 145702601 10 11 462074055 11 12 513377059 12 13 578785771 13 14 739836237 14 15 9863668 15 16 121371522 16 17 146577570 17 18 319481399 18 19 434184484 19 20 492502159 20 21 586201254 21 22 115487690 22 23 430012283 23 24 804587519 24 25 775709182 25 26 105846694 26 27 639065433 27 28 712578140 28 29 582787850 29 30 634747799 30 31 432934758 31 32 729053193 32 33 141220166 33 34 337350625 34 35 237504496 35 36 854654805 36 37 615804454 37 38 357964632 38 39 884534759 39 40 154878201 40 41 173681747 41 42 381478049 42 43 738578086 43 44 940190781 44 45 656576202 45 46 224701743 46 47 822656235 47 48 112246248 48 49 327518411 49 50 444264222 50 51 730094814 51 52 842105941 52 53 956786085 53 54 718990654 54 55 53710556 55 56 124054986 56 57 89602598 57 58 337816239 58 59 232903188 59 60 707814562 60 61 992271997 61 62 91264022 62 63 731604017 63 64 645463580 64 65 757128257 65 66 563250297 66 67 765598257 67 68 383804350 68 69 970915466 69 70 398777277 70 71 20760149 71 72 203470695 72 73 811775037 73 74 922456249 74 75 834407729 75 76 39333360 76 77 817656934 77 78 353295094 78 79 273749987 79 80 167118462 80 81 113150142 81 82 346617862 82 83 448166752 83 84 429815912 84 85 329611339 85 86 360735357 86 87 834481898 87 88 606747583 88 89 203576358 89 90 111507089 90 91 762887070 91 92 778564734 92 93 541325912 93 94 153115722 94 95 817240873 95 96 291635279 96 97 174188766 97 98 493598053 98 99 333679515 99 100 685930744 100 101 864533708 101 102 798201035 102 103 150756436 103 104 727421792 104 105 833132942 105 106 414954409 106 107 760936474 107 108 474049858 108 109 994531913 109 110 637701163 110 111 173505613 111 112 537340781 112 113 136844640 113 114 947074010 114 115 609916721 115 116 376531637 116 117 394814482 117 118 678298000 118 119 927309675 119 120 875918714 120 121 768690240 121 122 662041876 122 123 138495111 123 124 168873938 124 125 548239436 125 126 543803990 126 127 787266742 127 128 481052246 128 129 702557470 129 130 942203464 130 131 939587477 131 132 516572550 132 133 582595136 133 134 413919574 134 135 143844904 135 136 67467226 136 137 540375593 137 138 116440452 138 139 639239141 139 140 429043814 140 141 855164055 141 142 22293027 142 143 773128941 143 144 394251816 144 145 81036053 145 146 642629936 146 147 137592662 147 148 158657009 148 149 71661980 149 150 580526665 150 151 70566819 151 152 540819694 152 153 492893526 153 154 16260693 154 155 689825747 155 156 796780925 156 157 269993103 157 158 50595482 158 159 645472931 159 160 993184354 160 161 391401141 161 162 493100580 162 163 939640094 163 164 624557706 164 165 818419763 165 166 278030869 166 167 634580935 167 168 880498675 168 169 979631200 169 170 881611664 170 171 194606964 171 172 847482418 172 173 50134052 173 174 325689922 174 175 190911131 175 176 742087376 176 177 377983185 177 178 398818191 178 179 943308415 179 180 459919062 180 181 692042257 181 182 247168076 182 183 395735120 183 184 653883827 184 185 299219728 185 186 177390408 186 187 996427419 187 188 378703787 188 189 921278993 189 190 692595778 190 191 722145612 191 192 647379826 192 193 856487758 193 194 857258038 194 195 892966496 195 196 515196443 196 197 189706959 197 198 58373711 198 199 273365041 199 200 2391796 200 201 657673988 201 202 456604127 202 203 540756181 203 204 608226123 204 205 647021742 205 206 558758566 206 207 991885320 207 208 258721933 208 209 241481219 209 210 646996041 210 211 702506196 211 212 203164167 212 213 520843057 213 214 435231915 214 215 396886184 215 216 4069927 216 217 611090133 217 218 563374204 218 219 139607521 219 220 141962636 220 221 694003842 221 222 833879824 222 223 351614008 223 224 870921776 224 225 106860593 225 226 212831051 226 227 990007243 227 228 729706146 228 229 705374566 229 230 220158393 230 231 550846662 231 232 732577643 232 233 123561442 233 234 608488378 234 235 758639022 235 236 595851923 236 237 876871167 237 238 429561306 238 239 198917948 239 240 142314155 240 241 554916159 241 242 773864238 242 243 971812715 243 244 358550588 244 245 889192421 245 246 344060903 246 247 296950155 247 248 111160322 248 249 177913914 249 250 916971272 250 251 686309237 251 252 901277987 252 253 423004884 253 254 535795451 254 255 445255965 255 256 417767883 256 257 402103631 257 258 128296890 258 259 713292339 259 260 191736123 260 261 121666766 261 262 722368556 262 263 133307099 263 264 293499428 264 265 936824958 265 266 738660128 266 267 200202098 267 268 856518219 268 269 898921534 269 270 576748618 270 271 191629052 271 272 532262161 272 273 194335579 273 274 316289244 274 275 923384512 275 276 247144094 276 277 830652349 277 278 866453744 278 279 421492138 279 280 850168189 280 281 36962944 281 282 577676775 282 283 165265431 283 284 737706767 284 285 221882043 285 286 115385181 286 287 870606883 287 288 806323845 288 289 563003215 289 290 557775324 290 291 163925511 291 292 380966826 292 293 569420657 293 294 693359270 294 295 663605360 295 296 620820159 296 297 61390905 297 298 890177221 298 299 189646962 299 300 576683196 300 301 405808591 301 302 800839100 302 303 596259847 303 304 283255794 304 305 945344960 305 306 408691466 306 307 796198948 307 308 913557689 308 309 991651641 309 310 187005490 310 311 590875705 311 312 203725298 312 313 568644165 313 314 860163711 314 315 221841546 315 316 148850890 316 317 446810724 317 318 252795917 318 319 134640346 319 320 554199827 320 321 970174534 321 322 464224769 322 323 821059510 323 324 869567952 324 325 640896293 325 326 370917848 326 327 77027931 327 328 653865424 328 329 486141375 329 330 919422429 330 331 491848516 331 332 818821233 332 333 884404975 333 334 911809716 334 335 982227284 335 336 94101638 336 337 614936084 337 338 265029533 338 339 67690835 339 340 428692492 340 341 670019730 341 342 606326731 342 343 906921624 343 344 530687326 344 345 328061155 345 346 697869940 346 347 707446381 347 348 117032510 348 349 933917375 349 350 432385421 350 351 332286393 351 352 613738494 352 353 480302897 353 354 711145648 354 355 919252945 355 356 837393318 356 357 294797629 357 358 423880584 358 359 969627517 359 360 660091743 360 361 75173202 361 362 869228844 362 363 76080570 363 364 613548114 364 365 812804231 365 366 579956179 366 367 512098953 367 368 909990574 368 369 483711394 369 370 325145171 370 371 684270025 371 372 95132341 372 373 88189606 373 374 895736823 374 375 608987742 375 376 919116014 376 377 82074077 377 378 666802034 378 379 54248181 379 380 417716378 380 381 433057578 381 382 453151328 382 383 338021214 383 384 498590714 384 385 892655063 385 386 540692577 386 387 104169730 387 388 816733963 388 389 354176782 389 390 556841577 390 391 20800010 391 392 998737576 392 393 74658412 393 394 211297403 394 395 596170227 395 396 207592458 396 397 490928475 397 398 167115311 398 399 422380299 399 400 693636968 400 401 242105732 401 402 318697427 402 403 834861037 403 404 48031982 404 405 580895185 405 406 489424812 406 407 885666456 407 408 721264844 408 409 761238045 409 410 509728602 410 411 134243116 411 412 631249003 412 413 316269435 413 414 678067545 414 415 340300864 415 416 303756475 416 417 570851616 417 418 458619556 418 419 617050024 419 420 622941678 420 421 361027188 421 422 75264556 422 423 274105003 423 424 67894941 424 425 659409446 425 426 798326911 426 427 597478525 427 428 850240136 428 429 260562746 429 430 589617759 430 431 810049510 431 432 424903442 432 433 659277175 433 434 782362859 434 435 369000371 435 436 937575859 436 437 764849964 437 438 78506487 438 439 82049187 439 440 679895366 440 441 546165793 441 442 903465806 442 443 528591979 443 444 144569335 444 445 774174816 445 446 958752530 446 447 347398322 447 448 689850533 448 449 914926607 449 450 861282915 450 451 243293900 451 452 978555579 452 453 781260163 453 454 169736309 454 455 194013824 455 456 513112816 456 457 656030470 457 458 274186016 458 459 535904945 459 460 28631130 460 461 293961017 461 462 148816528 462 463 865083075 463 464 645033758 464 465 31351116 465 466 941804342 466 467 874198978 467 468 377814466 468 469 794418371 469 470 895857295 470 471 44807842 471 472 991676019 472 473 36167346 473 474 209741387 474 475 264799313 475 476 411449413 476 477 275681606 477 478 43935078 478 479 504834843 479 480 701053694 480 481 248458842 481 482 374967890 482 483 41387149 483 484 287823433 484 485 267605288 485 486 200765890 486 487 550597499 487 488 740440212 488 489 717672732 489 490 105360917 490 491 579018782 491 492 164610438 492 493 723966916 493 494 395134301 494 495 944549461 495 496 89052704 496 497 168606180 497 498 936429580 498 499 280836108 499 500 418384295 500 501 7116858 501 502 362668474 502 503 25694443 503 504 818292207 504 505 899854230 505 506 433021700 506 507 307935949 507 508 93550566 508 509 981878143 509 510 917110230 510 511 112730892 511 512 553562172 512 513 304874387 513 514 3029551 514 515 658389736 515 516 836583607 516 517 969454971 517 518 326613660 518 519 921306588 519 520 489559795 520 521 240570472 521 522 528111820 522 523 763727257 523 524 766224654 524 525 316734917 525 526 974941971 526 527 448681490 527 528 181893464 528 529 790145686 529 530 110812962 530 531 505978548 531 532 600898710 532 533 502488313 533 534 658398825 534 535 832216307 535 536 720582095 536 537 997157382 537 538 257094272 538 539 955345284 539 540 105898100 540 541 234729047 541 542 797042294 542 543 943904937 543 544 789259397 544 545 172127220 545 546 430469591 546 547 17116307 547 548 171729076 548 549 72118117 549 550 522893565 550 551 958052061 551 552 814556967 552 553 685144727 553 554 901324536 554 555 810320393 555 556 657227354 556 557 144530766 557 558 408135042 558 559 949791024 559 560 428334256 560 561 395035415 561 562 193125572 562 563 873945983 563 564 476068355 564 565 840927512 565 566 894390614 566 567 623190491 567 568 787882402 568 569 718633524 569 570 31291101 570 571 949327304 571 572 117472701 572 573 722497077 573 574 146238197 574 575 681026065 575 576 465762197 576 577 423078441 577 578 632128110 578 579 489614267 579 580 412413929 580 581 455328031 581 582 602764652 582 583 877781550 583 584 393559275 584 585 743323089 585 586 163011863 586 587 654652736 587 588 466099234 588 589 839220982 589 590 761076716 590 591 982723888 591 592 55628671 592 593 381783746 593 594 713894624 594 595 971875512 595 596 521808957 596 597 208272580 597 598 418184056 598 599 144609183 599 600 714857225 600 601 108513987 601 602 714761388 602 603 952319897 603 604 104670162 604 605 704320258 605 606 166006374 606 607 950467489 607 608 627578207 608 609 322949858 609 610 473784170 610 611 615708883 611 612 461463150 612 613 525620087 613 614 801987326 614 615 429761077 615 616 546443345 616 617 519797576 617 618 857311240 618 619 515179284 619 620 304464515 620 621 713156694 621 622 808226189 622 623 381049031 623 624 373876871 624 625 759403816 625 626 546590868 626 627 811000132 627 628 965221016 628 629 325490078 629 630 282781505 630 631 770978029 631 632 277516558 632 633 522917307 633 634 368417137 634 635 832374461 635 636 210761310 636 637 547983643 637 638 864762590 638 639 109721396 639 640 947546014 640 641 458980609 641 642 225107225 642 643 20833287 643 644 506956235 644 645 629031157 645 646 543647541 646 647 812352002 647 648 84174306 648 649 90491388 649 650 434053970 650 651 541703712 651 652 511842136 652 653 116663097 653 654 681106107 654 655 941485344 655 656 658098252 656 657 422489141 657 658 733727165 658 659 569979778 659 660 381605823 660 661 63478418 661 662 246981246 662 663 661366481 663 664 231792240 664 665 793845008 665 666 780309445 666 667 946090806 667 668 573354930 668 669 924801787 669 670 43390754 670 671 88662010 671 672 624460632 672 673 63251509 673 674 961335596 674 675 216969113 675 676 71871180 676 677 74613211 677 678 876148706 678 679 200285567 679 680 485254463 680 681 912383383 681 682 450132275 682 683 161052002 683 684 176469754 684 685 387133314 685 686 989321626 686 687 434707515 687 688 786643412 688 689 213920435 689 690 228606688 690 691 74325218 691 692 384901308 692 693 625029225 693 694 26058501 694 695 95334981 695 696 753423478 696 697 338848721 697 698 300268345 698 699 320125764 699 700 416572259 700 701 50370676 701 702 664008453 702 703 291630637 703 704 344871032 704 705 329409855 705 706 571305351 706 707 532635599 707 708 444479825 708 709 652890160 709 710 338838234 710 711 131916349 711 712 399107934 712 713 746987675 713 714 876498324 714 715 799577377 715 716 594864187 716 717 137615382 717 718 117963881 718 719 144731065 719 720 87715102 720 721 383397895 721 722 936705004 722 723 194048627 723 724 499444586 724 725 956480118 725 726 430338081 726 727 501233248 727 728 407156084 728 729 140915743 729 730 567327961 730 731 776544245 731 732 80652113 732 733 276349161 733 734 420439660 734 735 434870462 735 736 424553946 736 737 74509053 737 738 884706433 738 739 859317351 739 740 824503565 740 741 974677069 741 742 275718916 742 743 919327867 743 744 684268760 744 745 534611953 745 746 961219103 746 747 767099306 747 748 981020108 748 749 787856239 749 750 437609328 750 751 446873125 751 752 682149317 752 753 557439306 753 754 665211211 754 755 851323876 755 756 335583732 756 757 773873650 757 758 853166702 758 759 376733147 759 760 905096073 760 761 643736939 761 762 186577736 762 763 691209844 763 764 807290253 764 765 667265133 765 766 53437688 766 767 321231729 767 768 335374964 768 769 602800308 769 770 314901663 770 771 304654083 771 772 89480948 772 773 213813932 773 774 861144932 774 775 840809061 775 776 508513706 776 777 42224369 777 778 408006759 778 779 275980593 779 780 851092493 780 781 109665024 781 782 597723982 782 783 828748411 783 784 85508579 784 785 497176559 785 786 393064610 786 787 626168419 787 788 432553201 788 789 437054771 789 790 440965584 790 791 52964584 791 792 731606475 792 793 892271433 793 794 355852388 794 795 439465929 795 796 971489165 796 797 196397256 797 798 410378152 798 799 993009178 799 800 318564684 800 801 744937395 801 802 851682228 802 803 996988914 803 804 528578210 804 805 513397147 805 806 203546387 806 807 969927647 807 808 231107743 808 809 414450897 809 810 37505593 810 811 728205 811 812 155989356 812 813 409330970 813 814 372500152 814 815 166491558 815 816 697368945 816 817 791271200 817 818 533400418 818 819 357029001 819 820 405726999 820 821 47868241 821 822 489990923 822 823 885135812 823 824 663867159 824 825 257022607 825 826 515300933 826 827 833790049 827 828 311558767 828 829 58929076 829 830 105831106 830 831 983378384 831 832 962971617 832 833 244034189 833 834 34475880 834 835 4363221 835 836 791679525 836 837 368689465 837 838 594789568 838 839 528729858 839 840 845186619 840 841 344895820 841 842 424181415 842 843 69565987 843 844 846663735 844 845 449890371 845 846 673230829 846 847 560139766 847 848 962947074 848 849 796101972 849 850 530671819 850 851 399253856 851 852 529349249 852 853 639302809 853 854 603156720 854 855 110784548 855 856 596685865 856 857 12266230 857 858 220513877 858 859 820247081 859 860 799449515 860 861 724837737 861 862 370481754 862 863 287186432 863 864 104394224 864 865 736456449 865 866 922407504 866 867 36356492 867 868 808865525 868 869 719673586 869 870 256582949 870 871 542117307 871 872 816800573 872 873 498382601 873 874 945978910 874 875 262288074 875 876 384141039 876 877 521323237 877 878 51302533 878 879 781996078 879 880 699430891 880 881 447358832 881 882 124805782 882 883 606024612 883 884 828814596 884 885 391578104 885 886 458380687 886 887 457849558 887 888 634461548 888 889 740236522 889 890 812792231 890 891 215581741 891 892 739751993 892 893 215510183 893 894 931889435 894 895 470742995 895 896 236829496 896 897 527524034 897 898 529273062 898 899 380823592 899 900 285006931 900 901 940005316 901 902 171947408 902 903 8555543 903 904 256575036 904 905 202007158 905 906 968933185 906 907 787620274 907 908 269021896 908 909 218240176 909 910 219829039 910 911 13162063 911 912 703232868 912 913 214575439 913 914 40304545 914 915 900391117 915 916 891418933 916 917 258150725 917 918 372615838 918 919 499574261 919 920 105148362 920 921 432057143 921 922 215719163 922 923 111443347 923 924 44611504 924 925 993275246 925 926 695363619 926 927 894294686 927 928 102984386 928 929 923177344 929 930 841511793 930 931 720181080 931 932 777527255 932 933 67501604 933 934 643830030 934 935 813440455 935 936 417870755 936 937 610478397 937 938 585249152 938 939 772577842 939 940 341287729 940 941 267764490 941 942 278525912 942 943 186210541 943 944 949994874 944 945 678840264 945 946 950655412 946 947 395445940 947 948 966638417 948 949 118073739 949 950 704701904 950 951 189775208 951 952 120927241 952 953 459731063 953 954 4330924 954 955 661450626 955 956 987038472 956 957 408201929 957 958 59447059 958 959 642457568 959 960 970759010 960 961 730442092 961 962 206743113 962 963 243078048 963 964 685870867 964 965 409491370 965 966 190036953 966 967 444275415 967 968 561796919 968 969 222154668 969 970 639474186 970 971 845179712 971 972 943387463 972 973 921424285 973 974 189146700 974 975 148393935 975 976 433295300 976 977 897431795 977 978 90326246 978 979 655051224 979 980 822492720 980 981 959865857 981 982 843248777 982 983 474211989 983 984 273522761 984 985 100174053 985 986 24133165 986 987 991292216 987 988 769033083 988 989 520485270 989 990 321985686 990 991 928629087 991 992 934346767 992 993 873878224 993 994 742356125 994 995 676540976 995 996 137174828 996 997 702011623 997 998 674213634 998 999 431027624 999 1000 351470739 1000 1001 852022475 1001 1002 617433023 1002 1003 69448556 1003 1004 814787911 1004 1005 380549787 1005 1006 351147369 1006 1007 79163077 1007 1008 604861420 1008 1009 281637552 1009 1010 312783004 1010 1011 507630418 1011 1012 464794297 1012 1013 438269953 1013 1014 937507381 1014 1015 548816236 1015 1016 847149898 1016 1017 678302729 1017 1018 754825826 1018 1019 256628850 1019 1020 494517725 1020 1021 264880988 1021 1022 216442879 1022 1023 392941114 1023 1024 963017326 1024 1025 679211990 1025 1026 804027746 1026 1027 893415268 1027 1028 156127543 1028 1029 774284794 1029 1030 945864558 1030 1031 686193211 1031 1032 221776705 1032 1033 600444236 1033 1034 24084179 1034 1035 140528038 1035 1036 269671378 1036 1037 751148486 1037 1038 146774103 1038 1039 725183059 1039 1040 847904737 1040 1041 520909677 1041 1042 747358960 1042 1043 173373032 1043 1044 388513441 1044 1045 430953041 1045 1046 650867228 1046 1047 910928615 1047 1048 198729637 1048 1049 371807764 1049 1050 484474521 1050 1051 340846941 1051 1052 720796992 1052 1053 355748738 1053 1054 364891388 1054 1055 145584735 1055 1056 332976804 1056 1057 486360578 1057 1058 32777082 1058 1059 110872949 1059 1060 759872029 1060 1061 788023452 1061 1062 752516206 1062 1063 652678190 1063 1064 206776106 1064 1065 605840042 1065 1066 586138133 1066 1067 5850296 1067 1068 161739163 1068 1069 717369126 1069 1070 209660563 1070 1071 625922391 1071 1072 86988770 1072 1073 924219503 1073 1074 56240480 1074 1075 934920705 1075 1076 792906119 1076 1077 25952487 1077 1078 307019463 1078 1079 748395437 1079 1080 599589870 1080 1081 71147446 1081 1082 111416726 1082 1083 636790558 1083 1084 269296557 1084 1085 300796255 1085 1086 811757303 1086 1087 993711734 1087 1088 53100910 1088 1089 362000110 1089 1090 758473742 1090 1091 139934667 1091 1092 207941320 1092 1093 709632774 1093 1094 535211122 1094 1095 283176915 1095 1096 764447642 1096 1097 152531553 1097 1098 405117325 1098 1099 624843077 1099 1100 490077204 1100 1101 697032260 1101 1102 893493947 1102 1103 630359111 1103 1104 857834542 1104 1105 998569450 1105 1106 254362222 1106 1107 951639837 1107 1108 740204878 1108 1109 69210226 1109 1110 723318528 1110 1111 434927804 1111 1112 212154563 1112 1113 940402048 1113 1114 304813538 1114 1115 478996585 1115 1116 316176991 1116 1117 180402802 1117 1118 911870649 1118 1119 765656376 1119 1120 477181796 1120 1121 284612973 1121 1122 712786595 1122 1123 659155743 1123 1124 583226012 1124 1125 582200066 1125 1126 261212568 1126 1127 459059125 1127 1128 72861061 1128 1129 202864764 1129 1130 357566955 1130 1131 81135757 1131 1132 383853736 1132 1133 294178798 1133 1134 999290153 1134 1135 423543050 1135 1136 902706689 1136 1137 561093557 1137 1138 605525149 1138 1139 518792088 1139 1140 261948659 1140 1141 248375490 1141 1142 352851597 1142 1143 11966749 1143 1144 920604930 1144 1145 528498963 1145 1146 352512224 1146 1147 439266220 1147 1148 105649406 1148 1149 377513368 1149 1150 987504118 1150 1151 564490256 1151 1152 23171275 1152 1153 84495151 1153 1154 855080171 1154 1155 598802889 1155 1156 5900518 1156 1157 552098561 1157 1158 411720868 1158 1159 491042557 1159 1160 822476311 1160 1161 966537764 1161 1162 457464494 1162 1163 929326555 1163 1164 25450150 1164 1165 506166330 1165 1166 779726401 1166 1167 809756795 1167 1168 377181334 1168 1169 647574098 1169 1170 120781036 1170 1171 354381496 1171 1172 945683560 1172 1173 357986414 1173 1174 76666095 1174 1175 197090941 1175 1176 197096919 1176 1177 151023585 1177 1178 473001360 1178 1179 326286061 1179 1180 29834484 1180 1181 734827039 1181 1182 133352113 1182 1183 750450626 1183 1184 160563537 1184 1185 765473023 1185 1186 1640778 1186 1187 715661360 1187 1188 38377501 1188 1189 367522603 1189 1190 936612708 1190 1191 818865419 1191 1192 807418269 1192 1193 149986373 1193 1194 986907273 1194 1195 334768374 1195 1196 322906059 1196 1197 21710944 1197 1198 30239699 1198 1199 110469645 1199 1200 989608223 1200 1201 226336518 1201 1202 957608406 1202 1203 596442509 1203 1204 548405139 1204 1205 41379132 1205 1206 964301479 1206 1207 256791302 1207 1208 724239174 1208 1209 324129703 1209 1210 241141648 1210 1211 215805235 1211 1212 431573808 1212 1213 378733476 1213 1214 735575996 1214 1215 764258388 1215 1216 393854836 1216 1217 623956346 1217 1218 104280250 1218 1219 527522729 1219 1220 775381908 1220 1221 261591601 1221 1222 711382369 1222 1223 429019132 1223 1224 21700395 1224 1225 484983521 1225 1226 900439735 1226 1227 241851296 1227 1228 752230301 1228 1229 529912699 1229 1230 526510111 1230 1231 913679165 1231 1232 57450459 1232 1233 725508545 1233 1234 864529553 1234 1235 541476127 1235 1236 677364688 1236 1237 390809618 1237 1238 717282077 1238 1239 190247947 1239 1240 969424521 1240 1241 522967568 1241 1242 445064845 1242 1243 749735691 1243 1244 54769910 1244 1245 611162259 1245 1246 236467241 1246 1247 102566998 1247 1248 744487646 1248 1249 274829580 1249 1250 665739691 1250 1251 814412362 1251 1252 671967389 1252 1253 296864020 1253 1254 259439773 1254 1255 900996919 1255 1256 376193641 1256 1257 782707984 1257 1258 757623251 1258 1259 860833280 1259 1260 409501274 1260 1261 467337582 1261 1262 723650336 1262 1263 268355306 1263 1264 323482734 1264 1265 188696958 1265 1266 403309611 1266 1267 94966535 1267 1268 653314727 1268 1269 571575274 1269 1270 638322779 1270 1271 960141369 1271 1272 515373903 1272 1273 649224916 1273 1274 657282031 1274 1275 676241755 1275 1276 421801867 1276 1277 579371051 1277 1278 460263478 1278 1279 188509934 1279 1280 643205096 1280 1281 849467565 1281 1282 879668747 1282 1283 362389492 1283 1284 812507979 1284 1285 902996446 1285 1286 38872446 1286 1287 969340143 1287 1288 611703086 1288 1289 89663108 1289 1290 979436306 1290 1291 848205774 1291 1292 633224546 1292 1293 276479603 1293 1294 597959032 1294 1295 556971769 1295 1296 681566702 1296 1297 519723107 1297 1298 846654974 1298 1299 602450026 1299 1300 428199553 1300 1301 374852829 1301 1302 792159637 1302 1303 797030645 1303 1304 14338960 1304 1305 293790333 1305 1306 567708072 1306 1307 182863120 1307 1308 772532288 1308 1309 434084685 1309 1310 938972370 1310 1311 683761566 1311 1312 146756134 1312 1313 298370060 1313 1314 93893750 1314 1315 178926130 1315 1316 904116139 1316 1317 771424557 1317 1318 555095309 1318 1319 668662580 1319 1320 993797052 1320 1321 716052732 1321 1322 447969871 1322 1323 988868347 1323 1324 294847481 1324 1325 697331909 1325 1326 238762357 1326 1327 733197773 1327 1328 143045227 1328 1329 328718079 1329 1330 37011893 1330 1331 915987413 1331 1332 129278864 1332 1333 768878469 1333 1334 142334040 1334 1335 257636402 1335 1336 674721031 1336 1337 340853247 1337 1338 544694393 1338 1339 249803564 1339 1340 319892180 1340 1341 989816927 1341 1342 786335836 1342 1343 234522497 1343 1344 47447377 1344 1345 795830152 1345 1346 312817768 1346 1347 604446942 1347 1348 608977330 1348 1349 884160521 1349 1350 236719554 1350 1351 277613417 1351 1352 164060979 1352 1353 828119302 1353 1354 721675400 1354 1355 753922171 1355 1356 3770080 1356 1357 357943607 1357 1358 973472167 1358 1359 560532075 1359 1360 793280513 1360 1361 326032474 1361 1362 984343429 1362 1363 974496543 1363 1364 359945444 1364 1365 33244479 1365 1366 577781786 1366 1367 549434295 1367 1368 698545797 1368 1369 859804439 1369 1370 258312625 1370 1371 439971451 1371 1372 170491018 1372 1373 799504666 1373 1374 843311451 1374 1375 138060863 1375 1376 237794571 1376 1377 326255349 1377 1378 798126372 1378 1379 317995399 1379 1380 744150116 1380 1381 454315617 1381 1382 503459494 1382 1383 381228714 1383 1384 401205521 1384 1385 738129505 1385 1386 776176311 1386 1387 911291554 1387 1388 715239960 1388 1389 575541314 1389 1390 146601075 1390 1391 980570415 1391 1392 444448819 1392 1393 731725622 1393 1394 92320502 1394 1395 889715803 1395 1396 731458188 1396 1397 150102210 1397 1398 165698911 1398 1399 115253824 1399 1400 887690901 1400 1401 636264181 1401 1402 83567152 1402 1403 250328482 1403 1404 971908656 1404 1405 154862500 1405 1406 691861819 1406 1407 965316082 1407 1408 988385866 1408 1409 800450845 1409 1410 407224101 1410 1411 713677311 1411 1412 192023150 1412 1413 924420949 1413 1414 392089666 1414 1415 309612591 1415 1416 570684787 1416 1417 757812659 1417 1418 901935004 1418 1419 368492124 1419 1420 278878550 1420 1421 898723704 1421 1422 134608403 1422 1423 476406088 1423 1424 882939938 1424 1425 328574665 1425 1426 846862238 1426 1427 570682815 1427 1428 91591691 1428 1429 943778394 1429 1430 450839727 1430 1431 157084488 1431 1432 192360603 1432 1433 985549753 1433 1434 283447733 1434 1435 280023687 1435 1436 283119364 1436 1437 701345332 1437 1438 400865586 1438 1439 311506324 1439 1440 138298984 1440 1441 211438382 1441 1442 354102190 1442 1443 177417798 1443 1444 602263656 1444 1445 676010427 1445 1446 840480837 1446 1447 412169844 1447 1448 757316230 1448 1449 794859095 1449 1450 844804102 1450 1451 363293610 1451 1452 822329537 1452 1453 284742744 1453 1454 611756346 1454 1455 252549015 1455 1456 691918528 1456 1457 878251902 1457 1458 644955933 1458 1459 889174709 1459 1460 709939867 1460 1461 902849410 1461 1462 941014663 1462 1463 930294841 1463 1464 937059198 1464 1465 368993884 1465 1466 31568602 1466 1467 461259428 1467 1468 916355119 1468 1469 692353092 1469 1470 73393502 1470 1471 957239651 1471 1472 43916419 1472 1473 672597425 1473 1474 237037335 1474 1475 254215842 1475 1476 30819064 1476 1477 538169725 1477 1478 351096720 1478 1479 269173575 1479 1480 297353900 1480 1481 350915396 1481 1482 527740323 1482 1483 709284844 1483 1484 750780116 1484 1485 947727408 1485 1486 503504450 1486 1487 834241965 1487 1488 353361476 1488 1489 573072902 1489 1490 113601861 1490 1491 353402434 1491 1492 804449566 1492 1493 427007470 1493 1494 793191863 1494 1495 953324727 1495 1496 158617510 1496 1497 958136379 1497 1498 213022157 1498 1499 367118240 1499 1500 477807089 1500 1501 876352681 1501 1502 507561873 1502 1503 312072245 1503 1504 763142807 1504 1505 449222681 1505 1506 63708315 1506 1507 327410259 1507 1508 721731397 1508 1509 109774288 1509 1510 961500640 1510 1511 708684838 1511 1512 137493747 1512 1513 41477529 1513 1514 169411637 1514 1515 467407903 1515 1516 410619886 1516 1517 763589125 1517 1518 84896865 1518 1519 883751429 1519 1520 382825601 1520 1521 86310611 1521 1522 560402653 1522 1523 825296675 1523 1524 670273599 1524 1525 876114282 1525 1526 896124714 1526 1527 285642655 1527 1528 813254640 1528 1529 916279170 1529 1530 249652431 1530 1531 103880427 1531 1532 643311126 1532 1533 560287715 1533 1534 68015956 1534 1535 668331034 1535 1536 866560838 1536 1537 875013506 1537 1538 707011256 1538 1539 436002328 1539 1540 274764119 1540 1541 232779064 1541 1542 810647637 1542 1543 540092228 1543 1544 592675292 1544 1545 805032166 1545 1546 971697596 1546 1547 483060983 1547 1548 117455343 1548 1549 65060268 1549 1550 798886628 1550 1551 374204263 1551 1552 655660710 1552 1553 588688218 1553 1554 205226669 1554 1555 52433227 1555 1556 235208854 1556 1557 268527157 1557 1558 521636010 1558 1559 929810277 1559 1560 129953130 1560 1561 956534208 1561 1562 414987766 1562 1563 288835757 1563 1564 901251731 1564 1565 376602326 1565 1566 574424395 1566 1567 547047426 1567 1568 797498482 1568 1569 553092734 1569 1570 268306502 1570 1571 935946708 1571 1572 893567658 1572 1573 120910866 1573 1574 383785685 1574 1575 143284205 1575 1576 16931392 1576 1577 584004580 1577 1578 783300003 1578 1579 969453412 1579 1580 36424133 1580 1581 227361063 1581 1582 721101553 1582 1583 406033576 1583 1584 800791828 1584 1585 921950892 1585 1586 216767648 1586 1587 162049321 1587 1588 996277602 1588 1589 692279391 1589 1590 305292230 1590 1591 323344097 1591 1592 875564406 1592 1593 678902270 1593 1594 524644174 1594 1595 439460462 1595 1596 304185067 1596 1597 286236398 1597 1598 793220255 1598 1599 113674409 1599 1600 348481241 1600 1601 389935581 1601 1602 839661270 1602 1603 320452856 1603 1604 726707900 1604 1605 50298311 1605 1606 103913050 1606 1607 216564746 1607 1608 989117687 1608 1609 558089269 1609 1610 868052755 1610 1611 995826032 1611 1612 573009828 1612 1613 87884299 1613 1614 35598818 1614 1615 540249280 1615 1616 790889344 1616 1617 450154794 1617 1618 209516816 1618 1619 218653046 1619 1620 790311478 1620 1621 881696160 1621 1622 334244225 1622 1623 630650566 1623 1624 339050609 1624 1625 264137499 1625 1626 810954483 1626 1627 532300754 1627 1628 328626118 1628 1629 840592855 1629 1630 593359062 1630 1631 814364549 1631 1632 830367458 1632 1633 180853692 1633 1634 987045664 1634 1635 218016096 1635 1636 483815805 1636 1637 977232869 1637 1638 66249399 1638 1639 862181983 1639 1640 127006934 1640 1641 555090196 1641 1642 668172189 1642 1643 31498625 1643 1644 933050363 1644 1645 617613806 1645 1646 850444746 1646 1647 535024355 1647 1648 204652737 1648 1649 78340969 1649 1650 778813994 1650 1651 167669756 1651 1652 622669368 1652 1653 119386722 1653 1654 714837978 1654 1655 717451356 1655 1656 346421057 1656 1657 376188840 1657 1658 761148802 1658 1659 245023840 1659 1660 479323234 1660 1661 7238854 1661 1662 182055003 1662 1663 219220650 1663 1664 962147616 1664 1665 216693481 1665 1666 839464536 1666 1667 869275608 1667 1668 70940540 1668 1669 930514128 1669 1670 367825450 1670 1671 187593086 1671 1672 274040428 1672 1673 298564654 1673 1674 190535709 1674 1675 856110421 1675 1676 178013480 1676 1677 559598094 1677 1678 386858676 1678 1679 986289330 1679 1680 660426375 1680 1681 94949130 1681 1682 20603678 1682 1683 899248647 1683 1684 670155436 1684 1685 711229061 1685 1686 916418548 1686 1687 599358176 1687 1688 24810114 1688 1689 691622708 1689 1690 797134667 1690 1691 55938341 1691 1692 343690028 1692 1693 395316103 1693 1694 113288152 1694 1695 455708911 1695 1696 127549936 1696 1697 813338567 1697 1698 461498888 1698 1699 178972472 1699 1700 286791331 1700 1701 327900103 1701 1702 190698029 1702 1703 463068962 1703 1704 986846756 1704 1705 737238602 1705 1706 424944594 1706 1707 892259296 1707 1708 590509310 1708 1709 176388593 1709 1710 513874991 1710 1711 703532869 1711 1712 299296817 1712 1713 843904991 1713 1714 285304248 1714 1715 83313383 1715 1716 966248458 1716 1717 96303595 1717 1718 834029776 1718 1719 753093103 1719 1720 305165615 1720 1721 850467969 1721 1722 414185883 1722 1723 712108929 1723 1724 552230327 1724 1725 28056598 1725 1726 646046448 1726 1727 178750914 1727 1728 337743478 1728 1729 258161733 1729 1730 636364682 1730 1731 304970326 1731 1732 700625035 1732 1733 448940200 1733 1734 850783712 1734 1735 62428827 1735 1736 976988789 1736 1737 802903244 1737 1738 839288538 1738 1739 646347871 1739 1740 288536693 1740 1741 765285653 1741 1742 471185931 1742 1743 829805965 1743 1744 192089482 1744 1745 789861944 1745 1746 664794394 1746 1747 279745761 1747 1748 952227145 1748 1749 19087509 1749 1750 79789395 1750 1751 368453929 1751 1752 56932057 1752 1753 253613110 1753 1754 622932109 1754 1755 740444254 1755 1756 690044301 1756 1757 315413004 1757 1758 562022857 1758 1759 140163757 1759 1760 411069554 1760 1761 225958856 1761 1762 973768614 1762 1763 916548164 1763 1764 723531423 1764 1765 888837907 1765 1766 149187373 1766 1767 3443914 1767 1768 294805015 1768 1769 310504698 1769 1770 336072489 1770 1771 128167959 1771 1772 854382381 1772 1773 271853823 1773 1774 72099772 1774 1775 407932943 1775 1776 632383842 1776 1777 504060440 1777 1778 356091451 1778 1779 646754424 1779 1780 8008147 1780 1781 714471376 1781 1782 323947686 1782 1783 580173804 1783 1784 85776963 1784 1785 993811852 1785 1786 293580994 1786 1787 879312362 1787 1788 564762305 1788 1789 418670056 1789 1790 892583125 1790 1791 803097606 1791 1792 126570998 1792 1793 31316032 1793 1794 720595454 1794 1795 123345473 1795 1796 396974605 1796 1797 71700043 1797 1798 79942702 1798 1799 219773555 1799 1800 972738111 1800 1801 938197985 1801 1802 821543879 1802 1803 716313317 1803 1804 170333434 1804 1805 164499677 1805 1806 280815311 1806 1807 110295547 1807 1808 804877485 1808 1809 420884253 1809 1810 807768846 1810 1811 794928435 1811 1812 57756838 1812 1813 836043856 1813 1814 322906712 1814 1815 419869657 1815 1816 134732773 1816 1817 850434281 1817 1818 441405448 1818 1819 140561421 1819 1820 555007504 1820 1821 24673028 1821 1822 903082614 1822 1823 602351782 1823 1824 940984747 1824 1825 751687222 1825 1826 753770865 1826 1827 96556490 1827 1828 405591335 1828 1829 21110071 1829 1830 79137459 1830 1831 170921856 1831 1832 804607909 1832 1833 450336890 1833 1834 311930742 1834 1835 899029464 1835 1836 353814126 1836 1837 684264223 1837 1838 818244511 1838 1839 894970119 1839 1840 995098449 1840 1841 880554777 1841 1842 274364466 1842 1843 816731820 1843 1844 721660861 1844 1845 810724931 1845 1846 770194543 1846 1847 211811949 1847 1848 380162240 1848 1849 319740071 1849 1850 4306345 1850 1851 539991744 1851 1852 520512502 1852 1853 256260718 1853 1854 574666979 1854 1855 130895063 1855 1856 794448523 1856 1857 404589131 1857 1858 3703834 1858 1859 764679886 1859 1860 158952911 1860 1861 918215465 1861 1862 328103000 1862 1863 562355023 1863 1864 437660652 1864 1865 506887955 1865 1866 391573230 1866 1867 43281728 1867 1868 797303979 1868 1869 977375547 1869 1870 789051984 1870 1871 956076700 1871 1872 644261600 1872 1873 117625880 1873 1874 518750349 1874 1875 259908191 1875 1876 305189286 1876 1877 570528105 1877 1878 438044571 1878 1879 205371661 1879 1880 155662289 1880 1881 678430745 1881 1882 334192552 1882 1883 948474204 1883 1884 993934572 1884 1885 20985498 1885 1886 976856953 1886 1887 183127810 1887 1888 125786715 1888 1889 393558702 1889 1890 37672457 1890 1891 737792800 1891 1892 641878354 1892 1893 960877172 1893 1894 659671027 1894 1895 179941754 1895 1896 557074868 1896 1897 619408035 1897 1898 693280289 1898 1899 736332358 1899 1900 335086690 1900 1901 684342423 1901 1902 296432635 1902 1903 903870663 1903 1904 10449539 1904 1905 692105569 1905 1906 438344407 1906 1907 178975211 1907 1908 371809815 1908 1909 500907304 1909 1910 816449970 1910 1911 281957363 1911 1912 894796362 1912 1913 412194186 1913 1914 612543469 1914 1915 964210777 1915 1916 738778085 1916 1917 902837756 1917 1918 116880068 1918 1919 513282983 1919 1920 913757542 1920 1921 112365315 1921 1922 798005217 1922 1923 688151272 1923 1924 586225327 1924 1925 583942878 1925 1926 343370207 1926 1927 472503174 1927 1928 942414564 1928 1929 696339984 1929 1930 848685340 1930 1931 747126814 1931 1932 558686163 1932 1933 86169473 1933 1934 673656879 1934 1935 224779884 1935 1936 455205373 1936 1937 266574018 1937 1938 817179145 1938 1939 17828965 1939 1940 304844613 1940 1941 388985767 1941 1942 155353700 1942 1943 15456939 1943 1944 661244273 1944 1945 724745852 1945 1946 752891879 1946 1947 250197456 1947 1948 94554348 1948 1949 474378902 1949 1950 784935713 1950 1951 222764976 1951 1952 751276225 1952 1953 166382517 1953 1954 693698296 1954 1955 437448500 1955 1956 607745785 1956 1957 639432227 1957 1958 307872328 1958 1959 564502605 1959 1960 314858393 1960 1961 534821982 1961 1962 199018302 1962 1963 657457484 1963 1964 579806679 1964 1965 177823497 1965 1966 353535385 1966 1967 643180585 1967 1968 861563758 1968 1969 487971263 1969 1970 671543952 1970 1971 881677492 1971 1972 847866298 1972 1973 684487909 1973 1974 110848444 1974 1975 698893436 1975 1976 867231907 1976 1977 158764687 1977 1978 485209346 1978 1979 727336912 1979 1980 992763107 1980 1981 109815645 1981 1982 409432130 1982 1983 511782126 1983 1984 552240376 1984 1985 448335547 1985 1986 814411475 1986 1987 499113394 1987 1988 528154538 1988 1989 790725079 1989 1990 967139862 1990 1991 543049304 1991 1992 763960169 1992 1993 187779158 1993 1994 108608263 1994 1995 190013519 1995 1996 925259976 1996 1997 454986960 1997 1998 713735004 1998 1999 291401882 1999 2000 333660184 2000 2001 590738597 2001 2002 551408741 2002 2003 884026748 2003 2004 659799090 2004 2005 179857117 2005 2006 941195980 2006 2007 963576905 2007 2008 820645392 2008 2009 954019960 2009 2010 832509782 2010 2011 461387579 2011 2012 897438968 2012 2013 802788045 2013 2014 689348013 2014 2015 701242439 2015 2016 624634303 2016 2017 419178863 2017 2018 240115577 2018 2019 579070923 2019 2020 565928146 2020 2021 144174434 2021 2022 581080498 2022 2023 573328684 2023 2024 895563679 2024 2025 193090116 2025 2026 338056808 2026 2027 810667277 2027 2028 189263595 2028 2029 511727261 2029 2030 951557357 2030 2031 435927249 2031 2032 81213775 2032 2033 669761320 2033 2034 819557102 2034 2035 770506280 2035 2036 558335015 2036 2037 310398384 2037 2038 609260214 2038 2039 505466774 2039 2040 816114822 2040 2041 73360988 2041 2042 346507285 2042 2043 896153978 2043 2044 179014661 2044 2045 841895461 2045 2046 41016085 2046 2047 536371804 2047 2048 374335368 2048 2049 380943912 2049 2050 818553375 2050 2051 561544672 2051 2052 309524156 2052 2053 200020145 2053 2054 430923510 2054 2055 143421645 2055 2056 662919204 2056 2057 740326138 2057 2058 456433139 2058 2059 433755446 2059 2060 92657658 2060 2061 855612901 2061 2062 413179353 2062 2063 299734918 2063 2064 53809574 2064 2065 199429774 2065 2066 725636967 2066 2067 425231282 2067 2068 402753699 2068 2069 472512649 2069 2070 324538893 2070 2071 647350525 2071 2072 199479682 2072 2073 166933437 2073 2074 604349883 2074 2075 999203943 2075 2076 119537417 2076 2077 123997148 2077 2078 101204948 2078 2079 714470835 2079 2080 824538995 2080 2081 945119102 2081 2082 33611585 2082 2083 755859220 2083 2084 921598939 2084 2085 144852185 2085 2086 258304930 2086 2087 502732211 2087 2088 846466591 2088 2089 538887584 2089 2090 936600928 2090 2091 636610670 2091 2092 899480948 2092 2093 234401886 2093 2094 294754110 2094 2095 361509003 2095 2096 158181902 2096 2097 567039004 2097 2098 412350199 2098 2099 417516508 2099 2100 748827040 2100 2101 800625455 2101 2102 614322707 2102 2103 910401428 2103 2104 304589446 2104 2105 132623055 2105 2106 378580920 2106 2107 610646513 2107 2108 105074 2108 2109 721318770 2109 2110 87364942 2110 2111 736979330 2111 2112 15784621 2112 2113 371025772 2113 2114 795899149 2114 2115 428220958 2115 2116 244423917 2116 2117 910130344 2117 2118 301228768 2118 2119 336047343 2119 2120 108307283 2120 2121 892280896 2121 2122 107972763 2122 2123 614738277 2123 2124 338985377 2124 2125 252492443 2125 2126 173964241 2126 2127 548412675 2127 2128 548575763 2128 2129 435438991 2129 2130 44347249 2130 2131 386079997 2131 2132 5690635 2132 2133 773030422 2133 2134 625834931 2134 2135 701726862 2135 2136 998421934 2136 2137 304350092 2137 2138 645545831 2138 2139 515304056 2139 2140 536740552 2140 2141 546415454 2141 2142 403129789 2142 2143 419848186 2143 2144 567986513 2144 2145 465238472 2145 2146 93427703 2146 2147 572843534 2147 2148 837212780 2148 2149 726828063 2149 2150 15044949 2150 2151 766128747 2151 2152 803729540 2152 2153 777980577 2153 2154 232752690 2154 2155 754239586 2155 2156 111445075 2156 2157 452231251 2157 2158 892804906 2158 2159 396502162 2159 2160 939888896 2160 2161 43382717 2161 2162 293412386 2162 2163 785143499 2163 2164 86829401 2164 2165 723580209 2165 2166 125268306 2166 2167 234271222 2167 2168 661048118 2168 2169 68196934 2169 2170 951472180 2170 2171 105126621 2171 2172 824580602 2172 2173 626635041 2173 2174 765641517 2174 2175 438896497 2175 2176 8026389 2176 2177 693555154 2177 2178 399816887 2178 2179 689327268 2179 2180 752936270 2180 2181 806773882 2181 2182 474716497 2182 2183 583590451 2183 2184 979220485 2184 2185 814769050 2185 2186 217304229 2186 2187 678975906 2187 2188 404692000 2188 2189 626978474 2189 2190 605391020 2190 2191 557930021 2191 2192 137902937 2192 2193 731668702 2193 2194 878750297 2194 2195 297778533 2195 2196 936224374 2196 2197 269161246 2197 2198 689756323 2198 2199 324954820 2199 2200 671995491 2200 2201 13487126 2201 2202 209081393 2202 2203 232032446 2203 2204 326995179 2204 2205 875371882 2205 2206 601194402 2206 2207 287373418 2207 2208 485596947 2208 2209 807181831 2209 2210 241535606 2210 2211 613894944 2211 2212 330225939 2212 2213 319270805 2213 2214 219430044 2214 2215 959156277 2215 2216 968368625 2216 2217 360770825 2217 2218 944053912 2218 2219 430307042 2219 2220 699881148 2220 2221 590668374 2221 2222 949859920 2222 2223 609247299 2223 2224 979056483 2224 2225 719484739 2225 2226 749753460 2226 2227 682158459 2227 2228 552378672 2228 2229 142302040 2229 2230 5218440 2230 2231 56018932 2231 2232 88764132 2232 2233 542748402 2233 2234 855875472 2234 2235 273918404 2235 2236 831945839 2236 2237 447020406 2237 2238 564948311 2238 2239 842867243 2239 2240 866566220 2240 2241 11460770 2241 2242 799450203 2242 2243 147080249 2243 2244 792700535 2244 2245 33966847 2245 2246 772305496 2246 2247 485894029 2247 2248 10681612 2248 2249 2357619 2249 2250 547095407 2250 2251 66728759 2251 2252 269720051 2252 2253 478909119 2253 2254 991822192 2254 2255 502331733 2255 2256 758084817 2256 2257 751229247 2257 2258 608924211 2258 2259 437760579 2259 2260 267459225 2260 2261 524594347 2261 2262 520222173 2262 2263 131170123 2263 2264 681180461 2264 2265 189285169 2265 2266 748031234 2266 2267 406996500 2267 2268 497491131 2268 2269 549298194 2269 2270 146966444 2270 2271 409429788 2271 2272 99581074 2272 2273 232698190 2273 2274 621533692 2274 2275 338525818 2275 2276 96433948 2276 2277 697384552 2277 2278 960589405 2278 2279 338806879 2279 2280 818048966 2280 2281 687403959 2281 2282 271470915 2282 2283 282828809 2283 2284 863668476 2284 2285 829267220 2285 2286 760833303 2286 2287 454918434 2287 2288 36856917 2288 2289 896221780 2289 2290 588467658 2290 2291 580460237 2291 2292 526306658 2292 2293 30341031 2293 2294 85987644 2294 2295 518927146 2295 2296 562910711 2296 2297 404837896 2297 2298 643792159 2298 2299 926248575 2299 2300 524565544 2300 2301 841049963 2301 2302 999726798 2302 2303 948526445 2303 2304 327883217 2304 2305 136328438 2305 2306 404417992 2306 2307 937713947 2307 2308 764142922 2308 2309 736281243 2309 2310 327474097 2310 2311 45577405 2311 2312 460160773 2312 2313 130189407 2313 2314 164939235 2314 2315 751364238 2315 2316 172504861 2316 2317 354223201 2317 2318 17159782 2318 2319 639343933 2319 2320 996830478 2320 2321 727463485 2321 2322 703197574 2322 2323 89772168 2323 2324 146330097 2324 2325 465002961 2325 2326 784343715 2326 2327 778649111 2327 2328 367394266 2328 2329 335329173 2329 2330 102760219 2330 2331 284519934 2331 2332 596432275 2332 2333 302866600 2333 2334 380642752 2334 2335 684729279 2335 2336 182557301 2336 2337 940005431 2337 2338 16569280 2338 2339 935291734 2339 2340 81749533 2340 2341 928502243 2341 2342 7930897 2342 2343 398538588 2343 2344 566220145 2344 2345 957185470 2345 2346 782753909 2346 2347 140812040 2347 2348 797157694 2348 2349 399176026 2349 2350 168393951 2350 2351 14678111 2351 2352 589214323 2352 2353 328897921 2353 2354 660135243 2354 2355 149987417 2355 2356 24849713 2356 2357 566651001 2357 2358 75518857 2358 2359 633163656 2359 2360 892586884 2360 2361 911455442 2361 2362 996291343 2362 2363 813249227 2363 2364 210375175 2364 2365 972922065 2365 2366 4557633 2366 2367 272315846 2367 2368 165334063 2368 2369 669027710 2369 2370 27347330 2370 2371 625834534 2371 2372 572710225 2372 2373 79216811 2373 2374 75987678 2374 2375 715218412 2375 2376 561317807 2376 2377 581341740 2377 2378 340098977 2378 2379 186270699 2379 2380 906419230 2380 2381 175095229 2381 2382 226389101 2382 2383 195435923 2383 2384 272802179 2384 2385 253486823 2385 2386 919497787 2386 2387 894164598 2387 2388 185523902 2388 2389 12816709 2389 2390 908433343 2390 2391 863888130 2391 2392 744410635 2392 2393 763188064 2393 2394 243146749 2394 2395 810881362 2395 2396 35450654 2396 2397 707317513 2397 2398 316883425 2398 2399 331247328 2399 2400 428006890 2400 2401 48743762 2401 2402 3057433 2402 2403 159666009 2403 2404 750893069 2404 2405 874815666 2405 2406 204983437 2406 2407 684634840 2407 2408 851081548 2408 2409 315628406 2409 2410 999065086 2410 2411 83454281 2411 2412 816209460 2412 2413 575465096 2413 2414 90369752 2414 2415 878047073 2415 2416 762788718 2416 2417 516540133 2417 2418 643020370 2418 2419 126845305 2419 2420 721838915 2420 2421 229461723 2421 2422 750752630 2422 2423 618255719 2423 2424 585600719 2424 2425 78484627 2425 2426 914954193 2426 2427 979476833 2427 2428 291150130 2428 2429 929878793 2429 2430 467389235 2430 2431 679071835 2431 2432 160393675 2432 2433 24644532 2433 2434 118277887 2434 2435 836478125 2435 2436 41881904 2436 2437 624378867 2437 2438 869096670 2438 2439 495285736 2439 2440 408617878 2440 2441 315620180 2441 2442 854754837 2442 2443 722255106 2443 2444 922205864 2444 2445 283301853 2445 2446 474797827 2446 2447 587512997 2447 2448 975132123 2448 2449 649678534 2449 2450 630802739 2450 2451 456991712 2451 2452 704747262 2452 2453 324489470 2453 2454 532707931 2454 2455 681027379 2455 2456 883860823 2456 2457 422259625 2457 2458 203854417 2458 2459 615172049 2459 2460 113898323 2460 2461 708236589 2461 2462 986161325 2462 2463 969101830 2463 2464 116808073 2464 2465 271731829 2465 2466 885898466 2466 2467 547790436 2467 2468 80991205 2468 2469 393923378 2469 2470 617002585 2470 2471 564391120 2471 2472 258095700 2472 2473 567230019 2473 2474 57160233 2474 2475 869413046 2475 2476 936913928 2476 2477 459471408 2477 2478 505814133 2478 2479 382006120 2479 2480 939838927 2480 2481 242953059 2481 2482 779985748 2482 2483 530587288 2483 2484 661976841 2484 2485 196185525 2485 2486 483607563 2486 2487 461182112 2487 2488 487804855 2488 2489 851248389 2489 2490 910002303 2490 2491 207739195 2491 2492 267007142 2492 2493 210790817 2493 2494 7741966 2494 2495 828251966 2495 2496 790090937 2496 2497 315117161 2497 2498 537684014 2498 2499 714160609 2499 2500 336395175 2500 2501 136173362 2501 2502 981428217 2502 2503 352328447 2503 2504 521697654 2504 2505 731646667 2505 2506 22843212 2506 2507 114295667 2507 2508 959753810 2508 2509 126940472 2509 2510 933389734 2510 2511 907328636 2511 2512 401391159 2512 2513 70097005 2513 2514 412782064 2514 2515 686003076 2515 2516 514738593 2516 2517 32737565 2517 2518 12787154 2518 2519 554501890 2519 2520 273605430 2520 2521 529372415 2521 2522 566779084 2522 2523 76551305 2523 2524 936855408 2524 2525 655774429 2525 2526 282785668 2526 2527 674455073 2527 2528 502614451 2528 2529 404787349 2529 2530 675497121 2530 2531 302640674 2531 2532 442719960 2532 2533 995657645 2533 2534 687921051 2534 2535 840207036 2535 2536 205355569 2536 2537 861987343 2537 2538 512911979 2538 2539 437312933 2539 2540 737014426 2540 2541 248345040 2541 2542 740289037 2542 2543 522672674 2543 2544 993509152 2544 2545 331478925 2545 2546 477673729 2546 2547 7725835 2547 2548 252051229 2548 2549 345104824 2549 2550 122547614 2550 2551 376298947 2551 2552 68579220 2552 2553 591170333 2553 2554 966447164 2554 2555 961002570 2555 2556 488390648 2556 2557 49073576 2557 2558 575388809 2558 2559 988404288 2559 2560 431042905 2560 2561 362009225 2561 2562 920702727 2562 2563 546845213 2563 2564 69593067 2564 2565 513391331 2565 2566 317578564 2566 2567 18391880 2567 2568 774624359 2568 2569 59031994 2569 2570 366799286 2570 2571 481699572 2571 2572 720294743 2572 2573 350058190 2573 2574 149220189 2574 2575 366881379 2575 2576 765110405 2576 2577 537938693 2577 2578 443023509 2578 2579 209265972 2579 2580 978747879 2580 2581 4486168 2581 2582 293877019 2582 2583 942818479 2583 2584 235337923 2584 2585 67583261 2585 2586 465991177 2586 2587 746860843 2587 2588 533785582 2588 2589 216015825 2589 2590 500219657 2590 2591 681388459 2591 2592 775814368 2592 2593 798763404 2593 2594 354324784 2594 2595 81639974 2595 2596 396738880 2596 2597 941451804 2597 2598 461667578 2598 2599 242417179 2599 2600 405018411 2600 2601 574786254 2601 2602 782627519 2602 2603 51569556 2603 2604 611393207 2604 2605 340706515 2605 2606 963559676 2606 2607 65610959 2607 2608 514866195 2608 2609 323772717 2609 2610 875055135 2610 2611 414445374 2611 2612 621398880 2612 2613 447626366 2613 2614 880067825 2614 2615 675450535 2615 2616 66805289 2616 2617 961305083 2617 2618 800918944 2618 2619 347416684 2619 2620 309760129 2620 2621 27259776 2621 2622 666090344 2622 2623 24518373 2623 2624 13653432 2624 2625 150206 2625 2626 689907934 2626 2627 232648425 2627 2628 558442681 2628 2629 92095375 2629 2630 459583193 2630 2631 939935596 2631 2632 310876675 2632 2633 168195946 2633 2634 29185533 2634 2635 953996098 2635 2636 42582850 2636 2637 191750130 2637 2638 45582053 2638 2639 291831554 2639 2640 168198313 2640 2641 654651116 2641 2642 12553007 2642 2643 303029185 2643 2644 622464409 2644 2645 753902478 2645 2646 603310659 2646 2647 500550820 2647 2648 332450052 2648 2649 818036396 2649 2650 906524201 2650 2651 839334057 2651 2652 864336986 2652 2653 230485218 2653 2654 351906421 2654 2655 942667368 2655 2656 172398991 2656 2657 583701059 2657 2658 648009893 2658 2659 598331063 2659 2660 649187921 2660 2661 486003219 2661 2662 705640462 2662 2663 338501893 2663 2664 270519485 2664 2665 994592787 2665 2666 962678923 2666 2667 904196161 2667 2668 926682812 2668 2669 665889997 2669 2670 816121873 2670 2671 254549155 2671 2672 511775512 2672 2673 339458794 2673 2674 543613529 2674 2675 320186138 2675 2676 685216318 2676 2677 796630164 2677 2678 826036012 2678 2679 337813402 2679 2680 8074631 2680 2681 413890304 2681 2682 794136621 2682 2683 512271282 2683 2684 804761975 2684 2685 900184189 2685 2686 336273522 2686 2687 749487713 2687 2688 552598343 2688 2689 417620334 2689 2690 696079662 2690 2691 55197693 2691 2692 948101066 2692 2693 23856360 2693 2694 337962558 2694 2695 390037072 2695 2696 982810912 2696 2697 326602162 2697 2698 337310463 2698 2699 857816413 2699 2700 406408191 2700 2701 766532986 2701 2702 540182705 2702 2703 804049915 2703 2704 253209831 2704 2705 151945969 2705 2706 255256814 2706 2707 73957314 2707 2708 877678636 2708 2709 311353875 2709 2710 890430408 2710 2711 116320287 2711 2712 438772385 2712 2713 659908740 2713 2714 911733629 2714 2715 664004231 2715 2716 757431011 2716 2717 437396502 2717 2718 350228425 2718 2719 922564415 2719 2720 312900455 2720 2721 863111977 2721 2722 307319419 2722 2723 347958337 2723 2724 909215399 2724 2725 205013207 2725 2726 528564886 2726 2727 687275482 2727 2728 358807160 2728 2729 294951847 2729 2730 678528542 2730 2731 645709101 2731 2732 61765870 2732 2733 414960013 2733 2734 177697529 2734 2735 806459638 2735 2736 60839606 2736 2737 366493480 2737 2738 165629922 2738 2739 529065554 2739 2740 887599839 2740 2741 361827445 2741 2742 382162369 2742 2743 553593730 2743 2744 134744471 2744 2745 632559210 2745 2746 664467131 2746 2747 903957183 2747 2748 600457486 2748 2749 861937119 2749 2750 291837778 2750 2751 727666400 2751 2752 786885079 2752 2753 279627469 2753 2754 707121758 2754 2755 10747104 2755 2756 524193522 2756 2757 576526263 2757 2758 277985543 2758 2759 639657997 2759 2760 897143396 2760 2761 354201407 2761 2762 561657320 2762 2763 844479500 2763 2764 381626303 2764 2765 529246518 2765 2766 768899938 2766 2767 362164284 2767 2768 658986946 2768 2769 989649677 2769 2770 159939730 2770 2771 888461131 2771 2772 887463250 2772 2773 661134819 2773 2774 387723840 2774 2775 516125915 2775 2776 238063779 2776 2777 813944231 2777 2778 23397941 2778 2779 362194558 2779 2780 786629388 2780 2781 244690998 2781 2782 234591252 2782 2783 477613684 2783 2784 154697635 2784 2785 340847847 2785 2786 733121162 2786 2787 830887795 2787 2788 515416852 2788 2789 232124736 2789 2790 866648413 2790 2791 731136716 2791 2792 162676328 2792 2793 503491225 2793 2794 219323272 2794 2795 215162885 2795 2796 992771457 2796 2797 475882421 2797 2798 811681414 2798 2799 390436971 2799 2800 896361290 2800 2801 170217477 2801 2802 564069814 2802 2803 180333286 2803 2804 579433167 2804 2805 566563630 2805 2806 454105127 2806 2807 770127514 2807 2808 156538595 2808 2809 566837405 2809 2810 659559418 2810 2811 400713048 2811 2812 513944138 2812 2813 612383230 2813 2814 67969529 2814 2815 730362601 2815 2816 443656512 2816 2817 923657514 2817 2818 170528437 2818 2819 728006885 2819 2820 632456057 2820 2821 115438898 2821 2822 189554176 2822 2823 214086998 2823 2824 753166992 2824 2825 201384935 2825 2826 271143584 2826 2827 698261778 2827 2828 720830492 2828 2829 808923085 2829 2830 674581761 2830 2831 819924647 2831 2832 788385824 2832 2833 582862590 2833 2834 835478337 2834 2835 217237601 2835 2836 838447414 2836 2837 163168948 2837 2838 3292254 2838 2839 823309150 2839 2840 92831262 2840 2841 655762243 2841 2842 575830294 2842 2843 192255062 2843 2844 249307707 2844 2845 901369265 2845 2846 103689922 2846 2847 580992084 2847 2848 150719334 2848 2849 788163255 2849 2850 63825704 2850 2851 294291074 2851 2852 543475790 2852 2853 566042597 2853 2854 728171518 2854 2855 996816669 2855 2856 1241993 2856 2857 200408289 2857 2858 226921980 2858 2859 946191239 2859 2860 149334332 2860 2861 443695823 2861 2862 684749724 2862 2863 727712635 2863 2864 758990691 2864 2865 813319629 2865 2866 216879985 2866 2867 134839131 2867 2868 741378750 2868 2869 106501781 2869 2870 743180833 2870 2871 126280613 2871 2872 451585625 2872 2873 984119878 2873 2874 66413057 2874 2875 248353156 2875 2876 383921590 2876 2877 420535427 2877 2878 992977304 2878 2879 637497883 2879 2880 914213886 2880 2881 914110300 2881 2882 834877931 2882 2883 492134483 2883 2884 866142191 2884 2885 473767259 2885 2886 441497693 2886 2887 433898199 2887 2888 525994574 2888 2889 354485982 2889 2890 311295276 2890 2891 229587754 2891 2892 485291253 2892 2893 897965603 2893 2894 956252063 2894 2895 394605138 2895 2896 259825687 2896 2897 539936741 2897 2898 325379371 2898 2899 545549756 2899 2900 784878099 2900 2901 378884606 2901 2902 675530293 2902 2903 178316241 2903 2904 381039244 2904 2905 558115572 2905 2906 775959601 2906 2907 597102457 2907 2908 992546754 2908 2909 385314933 2909 2910 862375311 2910 2911 594683451 2911 2912 388236216 2912 2913 24792361 2913 2914 670331722 2914 2915 410064976 2915 2916 740555512 2916 2917 616095202 2917 2918 615662058 2918 2919 167718711 2919 2920 159879432 2920 2921 296530685 2921 2922 738491865 2922 2923 245864403 2923 2924 216556761 2924 2925 337820792 2925 2926 143755103 2926 2927 517538072 2927 2928 173264131 2928 2929 725608940 2929 2930 611426560 2930 2931 405894132 2931 2932 155211675 2932 2933 745475678 2933 2934 226933747 2934 2935 829201149 2935 2936 616822984 2936 2937 322054396 2937 2938 25133142 2938 2939 652567336 2939 2940 292465519 2940 2941 845719330 2941 2942 585766032 2942 2943 536532207 2943 2944 191876437 2944 2945 379108722 2945 2946 122931037 2946 2947 940340885 2947 2948 28202289 2948 2949 911059169 2949 2950 171184775 2950 2951 476028523 2951 2952 757442283 2952 2953 793568232 2953 2954 540736478 2954 2955 987390071 2955 2956 366875879 2956 2957 662624224 2957 2958 572060417 2958 2959 762727369 2959 2960 839587445 2960 2961 253641556 2961 2962 91725416 2962 2963 754297460 2963 2964 662578451 2964 2965 69426463 2965 2966 978915707 2966 2967 170955875 2967 2968 567030991 2968 2969 318189001 2969 2970 919938969 2970 2971 754010418 2971 2972 57134103 2972 2973 186862072 2973 2974 271323956 2974 2975 106673578 2975 2976 833830572 2976 2977 550123893 2977 2978 612888345 2978 2979 699973335 2979 2980 325392309 2980 2981 20242650 2981 2982 20884941 2982 2983 45514952 2983 2984 93894614 2984 2985 539212051 2985 2986 684139235 2986 2987 267462403 2987 2988 127325213 2988 2989 826134923 2989 2990 975300066 2990 2991 238794481 2991 2992 88435950 2992 2993 42419316 2993 2994 104481134 2994 2995 425984680 2995 2996 614052162 2996 2997 315867538 2997 2998 365226678 2998 2999 309794446 2999 3000 440305963