3000 2999 10 1 2 621662131 2 3 669747432 3 4 12801423 4 5 853048352 5 6 415303569 6 7 87168418 7 8 694378055 8 9 831286175 9 10 915674660 10 11 191181574 11 12 449000331 12 13 946569950 13 14 688075083 14 15 93419829 15 16 48097958 16 17 386318113 17 18 696567419 18 19 787795241 19 20 920893826 20 21 358899845 21 22 321930915 22 23 358524362 23 24 313269194 24 25 124428803 25 26 258167505 26 27 243821958 27 28 225514294 28 29 873784954 29 30 340967421 30 31 554281356 31 32 41135631 32 33 491953441 33 34 816534985 34 35 89100653 35 36 220762355 36 37 53762938 37 38 250716583 38 39 452503821 39 40 300889363 40 41 750271806 41 42 749296194 42 43 793673617 43 44 699693317 44 45 236079303 45 46 512631886 46 47 827408797 47 48 548832891 48 49 228307991 49 50 575641250 50 51 247496492 51 52 336694938 52 53 962440967 53 54 543981482 54 55 811052908 55 56 365628807 56 57 469410692 57 58 647178975 58 59 259615114 59 60 719349776 60 61 8393991 61 62 735227857 62 63 354174412 63 64 24019419 64 65 24444470 65 66 873387521 66 67 390398877 67 68 425119348 68 69 58484030 69 70 833335063 70 71 680563285 71 72 811845738 72 73 179188740 73 74 98989565 74 75 880241013 75 76 514254608 76 77 252854560 77 78 266780061 78 79 837074961 79 80 902873013 80 81 305902937 81 82 579831733 82 83 430078927 83 84 552628087 84 85 627375480 85 86 14726459 86 87 947688974 87 88 464325822 88 89 484885304 89 90 515486059 90 91 991009571 91 92 821231196 92 93 709969753 93 94 692113774 94 95 411514814 95 96 84436543 96 97 52220011 97 98 525274065 98 99 737286952 99 100 650172831 100 101 586518325 101 102 511518701 102 103 365183954 103 104 5431141 104 105 405229693 105 106 892808924 106 107 521570664 107 108 946312116 108 109 80638937 109 110 570265294 110 111 829354213 111 112 280333886 112 113 683520680 113 114 194078831 114 115 260778238 115 116 232280141 116 117 866543251 117 118 523670696 118 119 268545189 119 120 123031850 120 121 626973986 121 122 306774467 122 123 567591406 123 124 319556495 124 125 559256805 125 126 984087668 126 127 600972726 127 128 809500108 128 129 649229149 129 130 386815616 130 131 337834143 131 132 872990784 132 133 278011274 133 134 790693753 134 135 608420776 135 136 718192868 136 137 253683474 137 138 177084324 138 139 249142375 139 140 304173569 140 141 925688843 141 142 255242491 142 143 618119910 143 144 256951653 144 145 27231309 145 146 736191768 146 147 32626788 147 148 538870775 148 149 604727427 149 150 372549110 150 151 662273993 151 152 33254436 152 153 446706687 153 154 871242811 154 155 13902636 155 156 853076509 156 157 997780152 157 158 938369071 158 159 577438471 159 160 562542164 160 161 383775889 161 162 606586888 162 163 88758421 163 164 262389156 164 165 871968955 165 166 18303727 166 167 62184313 167 168 31427776 168 169 825501113 169 170 814027534 170 171 88443590 171 172 563040223 172 173 506409407 173 174 264591499 174 175 760375395 175 176 657421754 176 177 173730472 177 178 772528250 178 179 404776048 179 180 593506795 180 181 498017738 181 182 979873131 182 183 910293845 183 184 236460880 184 185 67084523 185 186 264434402 186 187 895113737 187 188 198576367 188 189 955795358 189 190 603379079 190 191 279300582 191 192 457764136 192 193 732049754 193 194 496730939 194 195 775709882 195 196 948778603 196 197 916290668 197 198 617793265 198 199 783436431 199 200 737620900 200 201 701322005 201 202 870706215 202 203 905856677 203 204 495945538 204 205 102283470 205 206 596880896 206 207 191939969 207 208 552029411 208 209 431440812 209 210 883763200 210 211 767145949 211 212 40477283 212 213 980169282 213 214 992824556 214 215 463206426 215 216 404478444 216 217 289650227 217 218 149761399 218 219 463767139 219 220 998500841 220 221 444099825 221 222 569139485 222 223 990418948 223 224 968957830 224 225 189830529 225 226 474255481 226 227 852720675 227 228 759440224 228 229 566268557 229 230 176838470 230 231 46040773 231 232 365641047 232 233 164238609 233 234 164112133 234 235 23303393 235 236 108976033 236 237 930235655 237 238 215719269 238 239 96340512 239 240 349544629 240 241 802290365 241 242 977620020 242 243 904394233 243 244 551236751 244 245 914652853 245 246 583597522 246 247 438036863 247 248 856503753 248 249 435554125 249 250 823052872 250 251 988167038 251 252 698640469 252 253 661268176 253 254 309072291 254 255 715865206 255 256 379806020 256 257 403992120 257 258 564504383 258 259 55776908 259 260 60913691 260 261 877532907 261 262 447173411 262 263 60413210 263 264 362794655 264 265 193745226 265 266 676406319 266 267 511416265 267 268 33239204 268 269 825410764 269 270 859268466 270 271 389996928 271 272 917321453 272 273 354191289 273 274 733615069 274 275 56151851 275 276 707870041 276 277 420698247 277 278 467646467 278 279 821778471 279 280 116928213 280 281 969117892 281 282 155799086 282 283 838168183 283 284 317709393 284 285 903966004 285 286 253142470 286 287 898388235 287 288 459967166 288 289 296667903 289 290 694660575 290 291 624430416 291 292 21283200 292 293 604898126 293 294 856257760 294 295 491201713 295 296 526396377 296 297 33590971 297 298 283057408 298 299 608003600 299 300 825571522 300 301 67346363 301 302 130278606 302 303 281145897 303 304 575490484 304 305 932043189 305 306 811502024 306 307 254244062 307 308 433183180 308 309 711421602 309 310 635735899 310 311 905217074 311 312 412786911 312 313 472126653 313 314 946244838 314 315 115841254 315 316 836354707 316 317 596713122 317 318 315624931 318 319 294951162 319 320 340061130 320 321 215153511 321 322 425729614 322 323 589461213 323 324 632774152 324 325 774268036 325 326 158443529 326 327 899811499 327 328 135807280 328 329 910831166 329 330 777657594 330 331 599430654 331 332 161109202 332 333 258199847 333 334 758398131 334 335 357523398 335 336 188558884 336 337 543467396 337 338 982823824 338 339 903256910 339 340 317425285 340 341 373714686 341 342 431619874 342 343 516441974 343 344 679119945 344 345 462471115 345 346 327200411 346 347 581571573 347 348 183121615 348 349 841089399 349 350 540457273 350 351 882812299 351 352 731636239 352 353 883504126 353 354 942056321 354 355 11902227 355 356 514086259 356 357 187601643 357 358 255836732 358 359 823970802 359 360 915426915 360 361 259244570 361 362 931625745 362 363 954082729 363 364 887773036 364 365 260972696 365 366 235459776 366 367 121527947 367 368 231017484 368 369 545337766 369 370 944490745 370 371 699700616 371 372 468577052 372 373 682004957 373 374 513620439 374 375 837071143 375 376 422254554 376 377 71049835 377 378 676891900 378 379 502954898 379 380 980580242 380 381 969493627 381 382 936033865 382 383 277522891 383 384 583843817 384 385 266761907 385 386 900207162 386 387 727824381 387 388 560914374 388 389 275263703 389 390 28345821 390 391 190280941 391 392 227593437 392 393 743927691 393 394 201107565 394 395 663016591 395 396 263151577 396 397 662053429 397 398 190483599 398 399 621330869 399 400 289193766 400 401 123421441 401 402 344664872 402 403 669925602 403 404 670287960 404 405 521354713 405 406 981665341 406 407 595161147 407 408 889348709 408 409 552145057 409 410 31580536 410 411 442674426 411 412 263494636 412 413 817922513 413 414 95716832 414 415 661808267 415 416 823818052 416 417 59430345 417 418 606321046 418 419 342426415 419 420 108616712 420 421 376970831 421 422 487128297 422 423 825802308 423 424 666906143 424 425 208250970 425 426 844666568 426 427 862834390 427 428 565546352 428 429 816680882 429 430 310788961 430 431 325331437 431 432 46255621 432 433 22625276 433 434 80265469 434 435 944225888 435 436 237995268 436 437 614780326 437 438 574757656 438 439 520339317 439 440 276351586 440 441 197710184 441 442 187931628 442 443 593906484 443 444 485105532 444 445 526219742 445 446 287322574 446 447 157581145 447 448 863720445 448 449 80492003 449 450 217730677 450 451 765681098 451 452 241808442 452 453 852279262 453 454 809831802 454 455 590958198 455 456 705311623 456 457 830736786 457 458 959894618 458 459 328992299 459 460 931949833 460 461 905067408 461 462 699685014 462 463 676773141 463 464 343695785 464 465 158602044 465 466 455120890 466 467 42735316 467 468 329096485 468 469 694353785 469 470 342609658 470 471 418852408 471 472 928923200 472 473 20398068 473 474 841744695 474 475 786934428 475 476 7465738 476 477 170335777 477 478 984407772 478 479 702822042 479 480 365282903 480 481 873080759 481 482 189558260 482 483 857971719 483 484 175425500 484 485 820319083 485 486 674421046 486 487 958513590 487 488 383734220 488 489 639023905 489 490 570619944 490 491 129280478 491 492 39471347 492 493 63668309 493 494 807186424 494 495 530611335 495 496 804539843 496 497 163919004 497 498 294952353 498 499 849628669 499 500 640110274 500 501 354194314 501 502 900983857 502 503 632109305 503 504 917349074 504 505 323521553 505 506 561505446 506 507 748907154 507 508 271235381 508 509 518649683 509 510 570846282 510 511 427911344 511 512 53925042 512 513 65405919 513 514 281579476 514 515 452953459 515 516 431648532 516 517 865516271 517 518 315765018 518 519 92315128 519 520 327599401 520 521 352790843 521 522 63780835 522 523 923395532 523 524 92986598 524 525 149880555 525 526 917540776 526 527 125108336 527 528 519754355 528 529 729654421 529 530 33239742 530 531 614603513 531 532 778707946 532 533 560135457 533 534 997572647 534 535 856445478 535 536 965323560 536 537 981008813 537 538 159181969 538 539 385859299 539 540 379225161 540 541 968314017 541 542 426423077 542 543 714018261 543 544 499561460 544 545 83379574 545 546 250676876 546 547 338312151 547 548 870313208 548 549 490484174 549 550 320719977 550 551 685019111 551 552 524449702 552 553 496412355 553 554 339649124 554 555 433420196 555 556 952058639 556 557 407074968 557 558 149255002 558 559 141711932 559 560 135837319 560 561 632208242 561 562 399163804 562 563 74269570 563 564 668983853 564 565 538050154 565 566 118001652 566 567 857395939 567 568 801075553 568 569 786762060 569 570 9269629 570 571 80854562 571 572 591375001 572 573 891390094 573 574 96119290 574 575 267405455 575 576 831658229 576 577 292673937 577 578 459586831 578 579 13833119 579 580 980526833 580 581 160549097 581 582 46786704 582 583 26112139 583 584 310536241 584 585 281081581 585 586 975268382 586 587 639751706 587 588 925909859 588 589 995801961 589 590 1011333 590 591 163580429 591 592 87800403 592 593 374040408 593 594 998265523 594 595 450345590 595 596 30221477 596 597 962785501 597 598 477993717 598 599 110915681 599 600 199118799 600 601 896499662 601 602 226405171 602 603 61346854 603 604 484741814 604 605 33354932 605 606 186196165 606 607 827444544 607 608 253680157 608 609 994417134 609 610 838383599 610 611 223707964 611 612 301631733 612 613 796292045 613 614 61696906 614 615 323669945 615 616 980545266 616 617 882341884 617 618 900544723 618 619 615064107 619 620 933626358 620 621 34550396 621 622 226009679 622 623 35228116 623 624 33168703 624 625 924547868 625 626 738109981 626 627 493166498 627 628 562175664 628 629 389407061 629 630 106861518 630 631 942810563 631 632 550572053 632 633 866627075 633 634 442480438 634 635 184960426 635 636 277688316 636 637 10187825 637 638 251660242 638 639 909284399 639 640 969247277 640 641 498459917 641 642 728223445 642 643 937745363 643 644 450354630 644 645 19477754 645 646 712180689 646 647 912726817 647 648 241006840 648 649 452897732 649 650 949864959 650 651 864055087 651 652 301772376 652 653 272400367 653 654 498768427 654 655 810368068 655 656 351037922 656 657 492171048 657 658 702005567 658 659 555406996 659 660 806762385 660 661 101879261 661 662 548638569 662 663 256938790 663 664 842629524 664 665 402644460 665 666 45369558 666 667 415064109 667 668 505390694 668 669 157303680 669 670 553255287 670 671 581101867 671 672 951047846 672 673 451710311 673 674 827224336 674 675 15622402 675 676 504716862 676 677 357860167 677 678 610171780 678 679 263457335 679 680 372209755 680 681 505630940 681 682 254379582 682 683 33843048 683 684 297021593 684 685 49158476 685 686 901265521 686 687 286764000 687 688 253954046 688 689 742217878 689 690 469776044 690 691 105916797 691 692 695866837 692 693 692622105 693 694 627691011 694 695 645664153 695 696 678531404 696 697 452865948 697 698 81708782 698 699 947907556 699 700 586001116 700 701 25838952 701 702 868653504 702 703 101279821 703 704 745820752 704 705 614525584 705 706 978976961 706 707 943918106 707 708 43665781 708 709 886039633 709 710 776405483 710 711 246010717 711 712 825736084 712 713 858303550 713 714 940298732 714 715 271551888 715 716 50942656 716 717 65647239 717 718 815422542 718 719 783114380 719 720 618194196 720 721 669533112 721 722 788140100 722 723 103154370 723 724 873275318 724 725 532602587 725 726 147705292 726 727 382166993 727 728 716413103 728 729 491613593 729 730 610980263 730 731 196593341 731 732 650952262 732 733 378358918 733 734 937502262 734 735 615416088 735 736 345604373 736 737 923652922 737 738 815494753 738 739 660975488 739 740 28382763 740 741 396844151 741 742 341902267 742 743 398228202 743 744 112660095 744 745 72010752 745 746 30832564 746 747 82750626 747 748 473584738 748 749 498716197 749 750 72805211 750 751 447703519 751 752 933316627 752 753 147419116 753 754 889745731 754 755 456712450 755 756 490995057 756 757 318836702 757 758 959789956 758 759 832389739 759 760 120234699 760 761 55761771 761 762 287329753 762 763 190444280 763 764 208601811 764 765 375282938 765 766 826548711 766 767 113693723 767 768 520762290 768 769 178266257 769 770 926841757 770 771 951690647 771 772 302622005 772 773 136432414 773 774 55448502 774 775 146917591 775 776 821249120 776 777 224416347 777 778 925972971 778 779 824404147 779 780 117488501 780 781 979332582 781 782 497692192 782 783 534985728 783 784 222291514 784 785 907235615 785 786 347624438 786 787 19901294 787 788 682364496 788 789 55364667 789 790 492252678 790 791 10852256 791 792 252105029 792 793 101462074 793 794 757998755 794 795 10301830 795 796 194648542 796 797 735842223 797 798 285049895 798 799 76062085 799 800 440355321 800 801 782565061 801 802 551320041 802 803 319819929 803 804 177565665 804 805 886984739 805 806 174252587 806 807 208814192 807 808 474307264 808 809 992995890 809 810 383384850 810 811 310059242 811 812 497300281 812 813 860131764 813 814 614498658 814 815 834932147 815 816 391298474 816 817 255409801 817 818 459031682 818 819 221335813 819 820 282836766 820 821 368679586 821 822 578563262 822 823 235589235 823 824 316738808 824 825 562736757 825 826 804710880 826 827 848570917 827 828 342433437 828 829 980517691 829 830 771099873 830 831 724340919 831 832 57569476 832 833 328944824 833 834 651351037 834 835 532628423 835 836 756093956 836 837 680743373 837 838 989576786 838 839 619680195 839 840 278229843 840 841 569264907 841 842 494193724 842 843 120431942 843 844 76114368 844 845 633417940 845 846 424225291 846 847 66503203 847 848 698413643 848 849 69858603 849 850 213004391 850 851 972916353 851 852 641697634 852 853 151363748 853 854 515655006 854 855 916060192 855 856 408528506 856 857 702197772 857 858 381824442 858 859 258051124 859 860 486858687 860 861 581269222 861 862 238007428 862 863 362644460 863 864 134642094 864 865 320582307 865 866 727378899 866 867 753542267 867 868 463038236 868 869 148064199 869 870 764621020 870 871 87471213 871 872 424707853 872 873 968707789 873 874 411168437 874 875 761155683 875 876 704601328 876 877 371244982 877 878 863020937 878 879 936641713 879 880 930722531 880 881 980230190 881 882 685188698 882 883 248903907 883 884 358637167 884 885 646320838 885 886 39917492 886 887 7362825 887 888 982718365 888 889 712562250 889 890 925713479 890 891 904662453 891 892 441602725 892 893 722507206 893 894 547329735 894 895 610179316 895 896 389855658 896 897 980971507 897 898 926102661 898 899 441117506 899 900 755479885 900 901 131426969 901 902 181850223 902 903 934052071 903 904 400139290 904 905 767421867 905 906 106536606 906 907 630963810 907 908 840203165 908 909 492969566 909 910 824152938 910 911 267819956 911 912 71096738 912 913 389930073 913 914 976213796 914 915 895928314 915 916 108442951 916 917 307789810 917 918 61391928 918 919 549323821 919 920 465801118 920 921 638721657 921 922 60792494 922 923 296440707 923 924 684855071 924 925 266563532 925 926 755288932 926 927 767626133 927 928 298980482 928 929 34452952 929 930 767785393 930 931 244007638 931 932 771939322 932 933 58324137 933 934 792737214 934 935 911777856 935 936 927890026 936 937 86184945 937 938 473109106 938 939 438920636 939 940 358966980 940 941 517972804 941 942 641303631 942 943 844635336 943 944 512878248 944 945 994216699 945 946 441487722 946 947 630019383 947 948 167255170 948 949 271650032 949 950 158672850 950 951 901399321 951 952 333984112 952 953 682072670 953 954 849155328 954 955 333106046 955 956 595284294 956 957 647235504 957 958 655514498 958 959 644846767 959 960 802643291 960 961 390074551 961 962 438122064 962 963 30470418 963 964 823736949 964 965 492510208 965 966 33037108 966 967 538658227 967 968 903064968 968 969 707949948 969 970 702205149 970 971 440531798 971 972 536935218 972 973 605951411 973 974 515081359 974 975 276112123 975 976 749891841 976 977 403531703 977 978 501646111 978 979 648102790 979 980 301540349 980 981 495371064 981 982 982691124 982 983 337501131 983 984 670431819 984 985 652259843 985 986 515065638 986 987 12925273 987 988 637962564 988 989 119922544 989 990 836665013 990 991 229262298 991 992 639784769 992 993 168152662 993 994 779644645 994 995 596466004 995 996 288755277 996 997 531846867 997 998 492711966 998 999 231071220 999 1000 999528904 1000 1001 59935681 1001 1002 336540470 1002 1003 957723239 1003 1004 829528586 1004 1005 320033283 1005 1006 247550587 1006 1007 632037933 1007 1008 591737025 1008 1009 460868053 1009 1010 878701153 1010 1011 551994124 1011 1012 54444063 1012 1013 986972647 1013 1014 93776241 1014 1015 517820953 1015 1016 625730289 1016 1017 290498613 1017 1018 124320300 1018 1019 624661146 1019 1020 228490714 1020 1021 606593034 1021 1022 675396455 1022 1023 913765218 1023 1024 557948299 1024 1025 81909128 1025 1026 208125909 1026 1027 498735995 1027 1028 836201951 1028 1029 491223945 1029 1030 51387115 1030 1031 195965011 1031 1032 561244086 1032 1033 125603544 1033 1034 104683129 1034 1035 135251067 1035 1036 862243881 1036 1037 894071928 1037 1038 402247212 1038 1039 626661592 1039 1040 773156494 1040 1041 144452396 1041 1042 913898063 1042 1043 893453662 1043 1044 97764332 1044 1045 166862310 1045 1046 127287299 1046 1047 556370406 1047 1048 667184186 1048 1049 576728036 1049 1050 188836838 1050 1051 232878295 1051 1052 429111767 1052 1053 11105707 1053 1054 879293401 1054 1055 993152951 1055 1056 851613608 1056 1057 505069277 1057 1058 389621478 1058 1059 878727937 1059 1060 490704985 1060 1061 175101697 1061 1062 581306641 1062 1063 220388534 1063 1064 971560685 1064 1065 960557193 1065 1066 863965158 1066 1067 108251925 1067 1068 402173041 1068 1069 875448377 1069 1070 680059951 1070 1071 671015925 1071 1072 433742184 1072 1073 164981962 1073 1074 832753194 1074 1075 722724263 1075 1076 720857780 1076 1077 346585857 1077 1078 417839206 1078 1079 568119444 1079 1080 890957834 1080 1081 296468469 1081 1082 904160652 1082 1083 111875399 1083 1084 166128124 1084 1085 279627671 1085 1086 43181102 1086 1087 235273565 1087 1088 843465471 1088 1089 811087854 1089 1090 335338983 1090 1091 271442712 1091 1092 11620476 1092 1093 619513872 1093 1094 694315284 1094 1095 550682659 1095 1096 283019712 1096 1097 338280476 1097 1098 666025361 1098 1099 408671936 1099 1100 458226901 1100 1101 225488785 1101 1102 177872623 1102 1103 820046811 1103 1104 888312228 1104 1105 603811767 1105 1106 956561621 1106 1107 835678831 1107 1108 641927381 1108 1109 292722772 1109 1110 206248740 1110 1111 203054033 1111 1112 477780068 1112 1113 285236644 1113 1114 86651160 1114 1115 687118818 1115 1116 127773602 1116 1117 437477064 1117 1118 16951701 1118 1119 722799889 1119 1120 467634691 1120 1121 157506849 1121 1122 647278260 1122 1123 411181021 1123 1124 623020385 1124 1125 984158906 1125 1126 806857245 1126 1127 909830700 1127 1128 950738768 1128 1129 812919854 1129 1130 340544587 1130 1131 651997072 1131 1132 868404534 1132 1133 516776466 1133 1134 502499715 1134 1135 740296185 1135 1136 775141972 1136 1137 166301535 1137 1138 59958804 1138 1139 78589640 1139 1140 582079057 1140 1141 199983237 1141 1142 683713504 1142 1143 824703895 1143 1144 776519152 1144 1145 275119924 1145 1146 446988250 1146 1147 992324449 1147 1148 202974699 1148 1149 720934256 1149 1150 808354968 1150 1151 766904769 1151 1152 538239330 1152 1153 827982593 1153 1154 969811798 1154 1155 274914159 1155 1156 752581966 1156 1157 472009777 1157 1158 990402844 1158 1159 299082096 1159 1160 280178236 1160 1161 255086296 1161 1162 604699165 1162 1163 498728554 1163 1164 617600501 1164 1165 398470079 1165 1166 110054471 1166 1167 778927776 1167 1168 248507697 1168 1169 675797587 1169 1170 976500626 1170 1171 804965410 1171 1172 787585676 1172 1173 194823992 1173 1174 987780259 1174 1175 902688905 1175 1176 332952156 1176 1177 237382666 1177 1178 109846085 1178 1179 359901213 1179 1180 773178749 1180 1181 775621293 1181 1182 710189554 1182 1183 538837807 1183 1184 683738790 1184 1185 389740343 1185 1186 495910002 1186 1187 824373526 1187 1188 366503128 1188 1189 975196795 1189 1190 970276507 1190 1191 293905604 1191 1192 626389231 1192 1193 702572339 1193 1194 693092406 1194 1195 844561156 1195 1196 373270473 1196 1197 369472258 1197 1198 859215954 1198 1199 81869506 1199 1200 517556178 1200 1201 916889686 1201 1202 353128376 1202 1203 752304584 1203 1204 79659985 1204 1205 292734207 1205 1206 511268179 1206 1207 417345874 1207 1208 701910502 1208 1209 115162424 1209 1210 112383189 1210 1211 453481714 1211 1212 118644786 1212 1213 506731338 1213 1214 723649606 1214 1215 665134138 1215 1216 264413622 1216 1217 980233422 1217 1218 734127623 1218 1219 732770892 1219 1220 899395602 1220 1221 897669991 1221 1222 996648957 1222 1223 304875368 1223 1224 323523190 1224 1225 564880469 1225 1226 761610406 1226 1227 778287199 1227 1228 46527739 1228 1229 918801456 1229 1230 99010439 1230 1231 445736516 1231 1232 635162888 1232 1233 774028219 1233 1234 747751383 1234 1235 429941066 1235 1236 7284576 1236 1237 510660460 1237 1238 16379634 1238 1239 143319062 1239 1240 752320867 1240 1241 957639683 1241 1242 361389190 1242 1243 139379174 1243 1244 501571896 1244 1245 89564973 1245 1246 558785983 1246 1247 408523566 1247 1248 637233133 1248 1249 472395991 1249 1250 483582342 1250 1251 321708172 1251 1252 287545282 1252 1253 189695092 1253 1254 942510296 1254 1255 888851733 1255 1256 118444968 1256 1257 34954441 1257 1258 991610818 1258 1259 642392622 1259 1260 135195917 1260 1261 457750612 1261 1262 608069772 1262 1263 28029195 1263 1264 44276314 1264 1265 272968434 1265 1266 967904706 1266 1267 837668203 1267 1268 454875533 1268 1269 130935307 1269 1270 648587755 1270 1271 465337173 1271 1272 924627281 1272 1273 782280086 1273 1274 589325953 1274 1275 447295171 1275 1276 544671023 1276 1277 261663753 1277 1278 676075470 1278 1279 373994511 1279 1280 653554651 1280 1281 222727829 1281 1282 297331078 1282 1283 246042058 1283 1284 829606708 1284 1285 557970455 1285 1286 691135142 1286 1287 253718670 1287 1288 847354753 1288 1289 532959107 1289 1290 877570271 1290 1291 663588147 1291 1292 637503311 1292 1293 78714948 1293 1294 642852012 1294 1295 14789175 1295 1296 296419731 1296 1297 673188582 1297 1298 674261467 1298 1299 590564458 1299 1300 913187634 1300 1301 399445084 1301 1302 748486903 1302 1303 298564336 1303 1304 375022884 1304 1305 159189423 1305 1306 60299948 1306 1307 143247668 1307 1308 394173167 1308 1309 898354665 1309 1310 602950132 1310 1311 226794876 1311 1312 305261109 1312 1313 468357941 1313 1314 38474493 1314 1315 516463911 1315 1316 406354790 1316 1317 93137587 1317 1318 416831528 1318 1319 736745606 1319 1320 308491669 1320 1321 593915611 1321 1322 410221870 1322 1323 645822037 1323 1324 599597416 1324 1325 548588683 1325 1326 308116573 1326 1327 272653525 1327 1328 330471210 1328 1329 525009070 1329 1330 780828672 1330 1331 513584263 1331 1332 610245627 1332 1333 582407307 1333 1334 704932317 1334 1335 750482054 1335 1336 660842535 1336 1337 607918247 1337 1338 80820952 1338 1339 492004993 1339 1340 379281555 1340 1341 469311576 1341 1342 242583733 1342 1343 855522389 1343 1344 485518675 1344 1345 309342184 1345 1346 979986939 1346 1347 713835331 1347 1348 40011609 1348 1349 575347554 1349 1350 786857460 1350 1351 338013513 1351 1352 676283388 1352 1353 823744208 1353 1354 328931652 1354 1355 714215272 1355 1356 906518560 1356 1357 276584425 1357 1358 580025774 1358 1359 376504498 1359 1360 51157529 1360 1361 426744353 1361 1362 536295862 1362 1363 539813719 1363 1364 79770727 1364 1365 749051118 1365 1366 865767564 1366 1367 726329950 1367 1368 205842009 1368 1369 641335239 1369 1370 7472977 1370 1371 844521731 1371 1372 748143718 1372 1373 756380439 1373 1374 670016454 1374 1375 974509531 1375 1376 482731957 1376 1377 876561192 1377 1378 984934740 1378 1379 433270778 1379 1380 446916257 1380 1381 786606582 1381 1382 147249368 1382 1383 423983829 1383 1384 620734458 1384 1385 289527090 1385 1386 109224112 1386 1387 560370009 1387 1388 389724768 1388 1389 642701132 1389 1390 960286499 1390 1391 912245811 1391 1392 819585272 1392 1393 822632122 1393 1394 137211736 1394 1395 890347401 1395 1396 13732306 1396 1397 114170997 1397 1398 522270920 1398 1399 97197506 1399 1400 196623916 1400 1401 151236848 1401 1402 952836086 1402 1403 192755074 1403 1404 222939460 1404 1405 469737021 1405 1406 963288495 1406 1407 788069264 1407 1408 517004706 1408 1409 548839549 1409 1410 282616042 1410 1411 488900058 1411 1412 565644326 1412 1413 948068619 1413 1414 263729695 1414 1415 394123876 1415 1416 393457575 1416 1417 877289124 1417 1418 202453218 1418 1419 85576349 1419 1420 761108235 1420 1421 279333012 1421 1422 815146997 1422 1423 11211903 1423 1424 215088015 1424 1425 517484250 1425 1426 109276040 1426 1427 197489979 1427 1428 555558065 1428 1429 350343637 1429 1430 690765138 1430 1431 481522294 1431 1432 867138490 1432 1433 759059540 1433 1434 126083025 1434 1435 298114742 1435 1436 378066375 1436 1437 780721961 1437 1438 228343375 1438 1439 718582598 1439 1440 520130730 1440 1441 548175146 1441 1442 572670829 1442 1443 178077256 1443 1444 197660818 1444 1445 297771113 1445 1446 434263581 1446 1447 32523821 1447 1448 937870283 1448 1449 549256956 1449 1450 964407173 1450 1451 239565294 1451 1452 917367745 1452 1453 152261329 1453 1454 942189108 1454 1455 264853255 1455 1456 538915131 1456 1457 494028715 1457 1458 954296724 1458 1459 568431871 1459 1460 860900385 1460 1461 65864891 1461 1462 12240508 1462 1463 751105374 1463 1464 652480226 1464 1465 104255369 1465 1466 990203616 1466 1467 637722201 1467 1468 16671918 1468 1469 692535228 1469 1470 948453271 1470 1471 724694953 1471 1472 127064740 1472 1473 288136815 1473 1474 376043258 1474 1475 706011796 1475 1476 781627200 1476 1477 825685949 1477 1478 934702005 1478 1479 317084865 1479 1480 604556356 1480 1481 789589580 1481 1482 785310403 1482 1483 633583732 1483 1484 537615126 1484 1485 791028421 1485 1486 737152423 1486 1487 491322249 1487 1488 840237433 1488 1489 693713085 1489 1490 418427845 1490 1491 439289769 1491 1492 774569095 1492 1493 354819633 1493 1494 12897919 1494 1495 67027636 1495 1496 25163969 1496 1497 89972842 1497 1498 69027269 1498 1499 972584223 1499 1500 660784916 1500 1501 216124315 1501 1502 296254507 1502 1503 406823313 1503 1504 361835209 1504 1505 645313379 1505 1506 732173365 1506 1507 883376960 1507 1508 330034008 1508 1509 746285932 1509 1510 175844060 1510 1511 788123841 1511 1512 959728692 1512 1513 35609501 1513 1514 376562704 1514 1515 397320860 1515 1516 556344562 1516 1517 265748129 1517 1518 165553175 1518 1519 103535716 1519 1520 349418670 1520 1521 813149083 1521 1522 903021928 1522 1523 730106932 1523 1524 192450216 1524 1525 172770254 1525 1526 912016525 1526 1527 191721006 1527 1528 999748888 1528 1529 946329618 1529 1530 467045004 1530 1531 380455418 1531 1532 695936015 1532 1533 807080856 1533 1534 767259717 1534 1535 534461529 1535 1536 837386679 1536 1537 634529289 1537 1538 57255512 1538 1539 398170091 1539 1540 501057757 1540 1541 96174309 1541 1542 805262263 1542 1543 223085345 1543 1544 773473042 1544 1545 902964923 1545 1546 44635091 1546 1547 859566399 1547 1548 653798068 1548 1549 594209595 1549 1550 5923330 1550 1551 352068938 1551 1552 785540102 1552 1553 573133502 1553 1554 197316923 1554 1555 979735574 1555 1556 491033347 1556 1557 366562631 1557 1558 241010645 1558 1559 729936582 1559 1560 856986624 1560 1561 858230127 1561 1562 494884028 1562 1563 457208014 1563 1564 514875975 1564 1565 691634071 1565 1566 137442932 1566 1567 414120476 1567 1568 265980125 1568 1569 523092778 1569 1570 955517806 1570 1571 852142681 1571 1572 604813278 1572 1573 13127500 1573 1574 16291648 1574 1575 846107989 1575 1576 839300223 1576 1577 794986465 1577 1578 595397265 1578 1579 56663345 1579 1580 72314906 1580 1581 77836325 1581 1582 344291470 1582 1583 12768607 1583 1584 986868894 1584 1585 510787593 1585 1586 909022976 1586 1587 847589759 1587 1588 816269411 1588 1589 165647838 1589 1590 860543044 1590 1591 566591187 1591 1592 582956698 1592 1593 908575055 1593 1594 12862250 1594 1595 91790149 1595 1596 50940957 1596 1597 898307731 1597 1598 525415657 1598 1599 448983418 1599 1600 614128473 1600 1601 489675292 1601 1602 664193750 1602 1603 387535383 1603 1604 477104989 1604 1605 492641570 1605 1606 962724965 1606 1607 475187669 1607 1608 309268349 1608 1609 694067485 1609 1610 280260162 1610 1611 584317038 1611 1612 158038610 1612 1613 405613932 1613 1614 747088002 1614 1615 84931753 1615 1616 777911597 1616 1617 195433149 1617 1618 959820047 1618 1619 567384540 1619 1620 760703895 1620 1621 114365379 1621 1622 878641103 1622 1623 278202224 1623 1624 529815724 1624 1625 203717644 1625 1626 412388717 1626 1627 692458327 1627 1628 452400472 1628 1629 920471968 1629 1630 683641994 1630 1631 272794218 1631 1632 947508469 1632 1633 300432379 1633 1634 369088021 1634 1635 982898217 1635 1636 310639929 1636 1637 461944984 1637 1638 531866842 1638 1639 54404729 1639 1640 55449914 1640 1641 39109957 1641 1642 544891122 1642 1643 640156100 1643 1644 55439853 1644 1645 674422290 1645 1646 532273981 1646 1647 126282853 1647 1648 988359880 1648 1649 978512193 1649 1650 845757623 1650 1651 161183531 1651 1652 884715173 1652 1653 273632217 1653 1654 177091337 1654 1655 615661609 1655 1656 842991431 1656 1657 62379356 1657 1658 658367188 1658 1659 354880112 1659 1660 81314896 1660 1661 856574258 1661 1662 914340955 1662 1663 238007279 1663 1664 740406858 1664 1665 503912115 1665 1666 758970553 1666 1667 717684770 1667 1668 565367919 1668 1669 779461677 1669 1670 711671739 1670 1671 977743337 1671 1672 353885460 1672 1673 513358341 1673 1674 860701015 1674 1675 13238387 1675 1676 501954226 1676 1677 412475892 1677 1678 356714701 1678 1679 91720537 1679 1680 161893778 1680 1681 331236979 1681 1682 197623751 1682 1683 327358997 1683 1684 941772850 1684 1685 631711890 1685 1686 152751317 1686 1687 15488925 1687 1688 699455937 1688 1689 442684515 1689 1690 484931828 1690 1691 708797468 1691 1692 888519506 1692 1693 53432483 1693 1694 669059203 1694 1695 336754743 1695 1696 23957653 1696 1697 345712210 1697 1698 987131414 1698 1699 274512579 1699 1700 595702386 1700 1701 564464221 1701 1702 409784522 1702 1703 959266999 1703 1704 229132927 1704 1705 162926058 1705 1706 152053340 1706 1707 363810614 1707 1708 995752589 1708 1709 36414062 1709 1710 498800750 1710 1711 384632143 1711 1712 790475006 1712 1713 950968793 1713 1714 521681296 1714 1715 574804702 1715 1716 251795932 1716 1717 147975955 1717 1718 87057186 1718 1719 368992554 1719 1720 154553966 1720 1721 909934510 1721 1722 347200736 1722 1723 430462267 1723 1724 368206608 1724 1725 449807093 1725 1726 385097815 1726 1727 930569848 1727 1728 265620547 1728 1729 507354868 1729 1730 451618471 1730 1731 425702859 1731 1732 156082047 1732 1733 176560314 1733 1734 950307769 1734 1735 719776998 1735 1736 980798349 1736 1737 869797418 1737 1738 413641617 1738 1739 443886587 1739 1740 816324857 1740 1741 173571622 1741 1742 111867533 1742 1743 248057409 1743 1744 770794363 1744 1745 58879465 1745 1746 658709130 1746 1747 889145403 1747 1748 489337098 1748 1749 411686291 1749 1750 831336235 1750 1751 235894683 1751 1752 45705225 1752 1753 442849526 1753 1754 484826397 1754 1755 904118476 1755 1756 613941099 1756 1757 278363683 1757 1758 86712533 1758 1759 264961737 1759 1760 644842440 1760 1761 643320834 1761 1762 843796312 1762 1763 789985575 1763 1764 131925950 1764 1765 576645353 1765 1766 8815585 1766 1767 519271183 1767 1768 859690285 1768 1769 283705498 1769 1770 453308062 1770 1771 198572913 1771 1772 557743742 1772 1773 224763072 1773 1774 442300419 1774 1775 364403801 1775 1776 535358360 1776 1777 67299162 1777 1778 429191976 1778 1779 930018477 1779 1780 190541709 1780 1781 855696678 1781 1782 384756822 1782 1783 609083323 1783 1784 299268343 1784 1785 977281087 1785 1786 942165506 1786 1787 362875829 1787 1788 92281257 1788 1789 968215752 1789 1790 218466422 1790 1791 689092066 1791 1792 661055664 1792 1793 210751861 1793 1794 749937503 1794 1795 747226914 1795 1796 446164381 1796 1797 334311330 1797 1798 596051832 1798 1799 476714831 1799 1800 650207042 1800 1801 680992383 1801 1802 484972760 1802 1803 535801535 1803 1804 908819464 1804 1805 338240872 1805 1806 186315732 1806 1807 343943141 1807 1808 845801968 1808 1809 698458450 1809 1810 734083218 1810 1811 175945495 1811 1812 321866276 1812 1813 128763745 1813 1814 98279723 1814 1815 644433514 1815 1816 291448889 1816 1817 497133207 1817 1818 159833212 1818 1819 354280889 1819 1820 137783044 1820 1821 378422440 1821 1822 162686858 1822 1823 323581125 1823 1824 423565590 1824 1825 3226601 1825 1826 693212047 1826 1827 515072374 1827 1828 92657877 1828 1829 532131430 1829 1830 195902629 1830 1831 919094336 1831 1832 288061496 1832 1833 588333074 1833 1834 282035982 1834 1835 923277473 1835 1836 591214622 1836 1837 754493465 1837 1838 961242910 1838 1839 618741702 1839 1840 727131468 1840 1841 559325637 1841 1842 567592781 1842 1843 936628993 1843 1844 110413264 1844 1845 799831485 1845 1846 246554150 1846 1847 314969912 1847 1848 49890200 1848 1849 607401804 1849 1850 408085394 1850 1851 961332858 1851 1852 2994284 1852 1853 82906294 1853 1854 439841358 1854 1855 539854173 1855 1856 618460358 1856 1857 470573379 1857 1858 259529 1858 1859 410113948 1859 1860 988836321 1860 1861 196947176 1861 1862 102017424 1862 1863 627776212 1863 1864 334571248 1864 1865 560847509 1865 1866 189285578 1866 1867 769726681 1867 1868 354746738 1868 1869 665259290 1869 1870 682227167 1870 1871 760144819 1871 1872 928409757 1872 1873 387824311 1873 1874 173796917 1874 1875 540002616 1875 1876 250097143 1876 1877 1021758 1877 1878 571890194 1878 1879 352193607 1879 1880 732919556 1880 1881 395423463 1881 1882 961012901 1882 1883 923060638 1883 1884 142660634 1884 1885 509458864 1885 1886 496025632 1886 1887 69220441 1887 1888 692875344 1888 1889 802365295 1889 1890 588191742 1890 1891 141660168 1891 1892 251998357 1892 1893 320349814 1893 1894 465221474 1894 1895 270992491 1895 1896 753593820 1896 1897 831768289 1897 1898 793409440 1898 1899 660506317 1899 1900 625128565 1900 1901 134146174 1901 1902 714588884 1902 1903 238288634 1903 1904 553757815 1904 1905 772141402 1905 1906 102839984 1906 1907 849586141 1907 1908 737473370 1908 1909 894140132 1909 1910 869289812 1910 1911 629913531 1911 1912 213137057 1912 1913 987770304 1913 1914 44362838 1914 1915 297698310 1915 1916 873659316 1916 1917 705937963 1917 1918 22342113 1918 1919 86283487 1919 1920 240694534 1920 1921 675018233 1921 1922 215664683 1922 1923 931110663 1923 1924 389432193 1924 1925 579097564 1925 1926 35317841 1926 1927 68537755 1927 1928 664572773 1928 1929 528055684 1929 1930 856367757 1930 1931 72198695 1931 1932 970376189 1932 1933 869641546 1933 1934 28263668 1934 1935 196910117 1935 1936 687376290 1936 1937 145157540 1937 1938 371107332 1938 1939 306649570 1939 1940 953843471 1940 1941 38771175 1941 1942 613143090 1942 1943 872454221 1943 1944 129362952 1944 1945 353161029 1945 1946 918144319 1946 1947 383690715 1947 1948 761835827 1948 1949 986421698 1949 1950 463070332 1950 1951 924478205 1951 1952 771032479 1952 1953 507273658 1953 1954 284460095 1954 1955 441296161 1955 1956 407590360 1956 1957 110642416 1957 1958 588979094 1958 1959 212325597 1959 1960 500473007 1960 1961 546245004 1961 1962 232927820 1962 1963 446332899 1963 1964 958080373 1964 1965 861776106 1965 1966 260753797 1966 1967 195797493 1967 1968 901749441 1968 1969 243208162 1969 1970 883345772 1970 1971 299724391 1971 1972 930159903 1972 1973 741291900 1973 1974 739077375 1974 1975 398387999 1975 1976 519060718 1976 1977 361453247 1977 1978 594031733 1978 1979 846090684 1979 1980 773458391 1980 1981 303500711 1981 1982 445880904 1982 1983 658110675 1983 1984 130284522 1984 1985 733013300 1985 1986 76688725 1986 1987 321566806 1987 1988 828971167 1988 1989 513517288 1989 1990 726303756 1990 1991 325990312 1991 1992 938846749 1992 1993 894624580 1993 1994 346551890 1994 1995 459921418 1995 1996 919276789 1996 1997 477294888 1997 1998 917733392 1998 1999 325284023 1999 2000 235837568 2000 2001 364358072 2001 2002 739435585 2002 2003 186328141 2003 2004 728041216 2004 2005 636181142 2005 2006 257590839 2006 2007 494238123 2007 2008 342175519 2008 2009 730688497 2009 2010 768843738 2010 2011 20226426 2011 2012 669174189 2012 2013 303848951 2013 2014 433141664 2014 2015 597139612 2015 2016 481259807 2016 2017 344613228 2017 2018 808255358 2018 2019 435851814 2019 2020 761873425 2020 2021 715580766 2021 2022 881701350 2022 2023 26183740 2023 2024 361991245 2024 2025 601273738 2025 2026 234051829 2026 2027 612986493 2027 2028 736149509 2028 2029 369568327 2029 2030 641140393 2030 2031 277971215 2031 2032 295885265 2032 2033 229055916 2033 2034 798485811 2034 2035 866896128 2035 2036 221635301 2036 2037 840461687 2037 2038 521584808 2038 2039 833038200 2039 2040 416463736 2040 2041 792640136 2041 2042 560802988 2042 2043 39470362 2043 2044 336051590 2044 2045 590722076 2045 2046 788104381 2046 2047 448987522 2047 2048 456846624 2048 2049 548966931 2049 2050 916036847 2050 2051 21562990 2051 2052 947368045 2052 2053 953478221 2053 2054 495933434 2054 2055 744815939 2055 2056 397240787 2056 2057 635129180 2057 2058 606233988 2058 2059 128210770 2059 2060 365447304 2060 2061 316715183 2061 2062 670549556 2062 2063 102368034 2063 2064 595345088 2064 2065 949971203 2065 2066 433815716 2066 2067 13838757 2067 2068 258938544 2068 2069 140172639 2069 2070 478003051 2070 2071 618937402 2071 2072 810717939 2072 2073 601456863 2073 2074 169681266 2074 2075 893761065 2075 2076 891328145 2076 2077 674811533 2077 2078 351573099 2078 2079 263476140 2079 2080 87058560 2080 2081 954487637 2081 2082 666016798 2082 2083 265062565 2083 2084 658332448 2084 2085 933638769 2085 2086 74209055 2086 2087 398846136 2087 2088 990636301 2088 2089 852210980 2089 2090 444402269 2090 2091 948244804 2091 2092 876381521 2092 2093 242970269 2093 2094 177570310 2094 2095 906965195 2095 2096 469721256 2096 2097 845207132 2097 2098 725224391 2098 2099 644190582 2099 2100 403120420 2100 2101 555725439 2101 2102 174167114 2102 2103 270943282 2103 2104 649515141 2104 2105 467272455 2105 2106 785841471 2106 2107 116869002 2107 2108 973716626 2108 2109 12431209 2109 2110 723768296 2110 2111 984585580 2111 2112 834013517 2112 2113 336513825 2113 2114 603945206 2114 2115 130023794 2115 2116 891095664 2116 2117 742220163 2117 2118 354972317 2118 2119 928054836 2119 2120 679780541 2120 2121 73315361 2121 2122 385932473 2122 2123 641014270 2123 2124 14844191 2124 2125 71739616 2125 2126 978743808 2126 2127 456217184 2127 2128 333739473 2128 2129 33653814 2129 2130 330730413 2130 2131 932611397 2131 2132 911015865 2132 2133 626126624 2133 2134 203596102 2134 2135 957534536 2135 2136 998431178 2136 2137 297778803 2137 2138 443997311 2138 2139 458488399 2139 2140 501704698 2140 2141 47037389 2141 2142 140927569 2142 2143 924909530 2143 2144 203279543 2144 2145 467746185 2145 2146 215238199 2146 2147 920910551 2147 2148 582617650 2148 2149 138318780 2149 2150 326016523 2150 2151 732778929 2151 2152 490509453 2152 2153 37021759 2153 2154 389681270 2154 2155 445147972 2155 2156 992140960 2156 2157 950363268 2157 2158 768369447 2158 2159 759074810 2159 2160 857420808 2160 2161 812619234 2161 2162 409687809 2162 2163 384197087 2163 2164 336008121 2164 2165 140118722 2165 2166 450092 2166 2167 925290024 2167 2168 698389972 2168 2169 681028959 2169 2170 530509609 2170 2171 169114515 2171 2172 795036953 2172 2173 213093088 2173 2174 609807719 2174 2175 205499082 2175 2176 379110645 2176 2177 742485038 2177 2178 289492143 2178 2179 679066321 2179 2180 593403218 2180 2181 503306550 2181 2182 201934130 2182 2183 891409759 2183 2184 998062433 2184 2185 832433800 2185 2186 243215274 2186 2187 279062649 2187 2188 96738713 2188 2189 167354549 2189 2190 618092621 2190 2191 162037949 2191 2192 924810427 2192 2193 395337143 2193 2194 398178367 2194 2195 455771294 2195 2196 282860012 2196 2197 589530168 2197 2198 445216915 2198 2199 485108318 2199 2200 905943324 2200 2201 263876732 2201 2202 308784083 2202 2203 923951130 2203 2204 340266897 2204 2205 314165862 2205 2206 311646978 2206 2207 926218914 2207 2208 687271688 2208 2209 995949161 2209 2210 822649979 2210 2211 152633039 2211 2212 127158245 2212 2213 46469312 2213 2214 498120547 2214 2215 867458369 2215 2216 145646768 2216 2217 915558590 2217 2218 638082417 2218 2219 246893646 2219 2220 977312425 2220 2221 585243757 2221 2222 492977337 2222 2223 404458057 2223 2224 479629336 2224 2225 935126906 2225 2226 862634831 2226 2227 358611828 2227 2228 72866242 2228 2229 500652224 2229 2230 736259844 2230 2231 999919010 2231 2232 102450552 2232 2233 494215279 2233 2234 224115532 2234 2235 408402286 2235 2236 834271177 2236 2237 757940440 2237 2238 941589824 2238 2239 888805649 2239 2240 809844951 2240 2241 906254809 2241 2242 517493182 2242 2243 631543012 2243 2244 602885191 2244 2245 781390560 2245 2246 66282414 2246 2247 500409938 2247 2248 866831773 2248 2249 286614624 2249 2250 924716858 2250 2251 45801465 2251 2252 428581704 2252 2253 13093905 2253 2254 481019391 2254 2255 739603029 2255 2256 178435212 2256 2257 145487501 2257 2258 722179019 2258 2259 568279308 2259 2260 537292303 2260 2261 429145582 2261 2262 871415174 2262 2263 626252256 2263 2264 670008223 2264 2265 627957634 2265 2266 287849774 2266 2267 132065633 2267 2268 622266874 2268 2269 262292682 2269 2270 897699252 2270 2271 534927555 2271 2272 324713785 2272 2273 780155551 2273 2274 426829939 2274 2275 221376714 2275 2276 368871899 2276 2277 955793520 2277 2278 99135566 2278 2279 492599777 2279 2280 61974122 2280 2281 718825894 2281 2282 588571748 2282 2283 571268427 2283 2284 575677900 2284 2285 189983528 2285 2286 340189298 2286 2287 279416689 2287 2288 450069545 2288 2289 95524090 2289 2290 316337862 2290 2291 797651801 2291 2292 357931635 2292 2293 670132224 2293 2294 34282972 2294 2295 87231287 2295 2296 148355734 2296 2297 868003809 2297 2298 899986839 2298 2299 715648542 2299 2300 515522110 2300 2301 828509959 2301 2302 832486941 2302 2303 937981647 2303 2304 942496320 2304 2305 147399874 2305 2306 958364239 2306 2307 21923762 2307 2308 499618982 2308 2309 24411532 2309 2310 464967652 2310 2311 204626914 2311 2312 456881498 2312 2313 346855271 2313 2314 132477217 2314 2315 895445347 2315 2316 494445 2316 2317 614946915 2317 2318 880643127 2318 2319 734731375 2319 2320 59891973 2320 2321 939703612 2321 2322 974195769 2322 2323 324475885 2323 2324 947223009 2324 2325 113873951 2325 2326 889744824 2326 2327 139356931 2327 2328 360559242 2328 2329 523296141 2329 2330 503792892 2330 2331 602953154 2331 2332 61058073 2332 2333 764371289 2333 2334 461267712 2334 2335 331884703 2335 2336 549167051 2336 2337 416021325 2337 2338 992414532 2338 2339 941153332 2339 2340 69499111 2340 2341 685229642 2341 2342 831047385 2342 2343 378507935 2343 2344 237214663 2344 2345 9965252 2345 2346 444730629 2346 2347 926154655 2347 2348 97436128 2348 2349 357807188 2349 2350 15570900 2350 2351 553420789 2351 2352 782470646 2352 2353 263097869 2353 2354 258422861 2354 2355 581830959 2355 2356 233035309 2356 2357 224290502 2357 2358 262948527 2358 2359 610672042 2359 2360 834038194 2360 2361 270270483 2361 2362 907466750 2362 2363 195157284 2363 2364 856344213 2364 2365 552103258 2365 2366 658035723 2366 2367 619861854 2367 2368 444363840 2368 2369 18433474 2369 2370 947950458 2370 2371 653621860 2371 2372 941850004 2372 2373 571745610 2373 2374 857336943 2374 2375 566191339 2375 2376 202364577 2376 2377 321651446 2377 2378 958791125 2378 2379 109256914 2379 2380 739941411 2380 2381 286325195 2381 2382 544851412 2382 2383 473525500 2383 2384 146648491 2384 2385 315761719 2385 2386 762659677 2386 2387 371850764 2387 2388 687926882 2388 2389 104941517 2389 2390 673144801 2390 2391 158396985 2391 2392 864689951 2392 2393 252021244 2393 2394 67048818 2394 2395 847738732 2395 2396 721604584 2396 2397 261162454 2397 2398 672798137 2398 2399 774716669 2399 2400 723762701 2400 2401 482162681 2401 2402 394437508 2402 2403 169149136 2403 2404 757008689 2404 2405 410415330 2405 2406 155863580 2406 2407 769997153 2407 2408 322024868 2408 2409 790376446 2409 2410 392846830 2410 2411 823828912 2411 2412 364259126 2412 2413 436080215 2413 2414 425469384 2414 2415 213996127 2415 2416 509596089 2416 2417 136291511 2417 2418 268596504 2418 2419 265656984 2419 2420 85839067 2420 2421 672075443 2421 2422 219508566 2422 2423 844455576 2423 2424 582733566 2424 2425 690663767 2425 2426 143355172 2426 2427 739087017 2427 2428 636219005 2428 2429 968310794 2429 2430 81682524 2430 2431 200712735 2431 2432 800880256 2432 2433 253878785 2433 2434 957684627 2434 2435 990165757 2435 2436 76189530 2436 2437 7012668 2437 2438 442422360 2438 2439 219569418 2439 2440 3948265 2440 2441 104750577 2441 2442 987177223 2442 2443 671207492 2443 2444 938568208 2444 2445 909579006 2445 2446 987197112 2446 2447 802150006 2447 2448 618025287 2448 2449 83872272 2449 2450 789837700 2450 2451 861892519 2451 2452 771064252 2452 2453 521677089 2453 2454 540823414 2454 2455 574516003 2455 2456 152129172 2456 2457 624029586 2457 2458 457175711 2458 2459 372117283 2459 2460 533150287 2460 2461 799600864 2461 2462 6720582 2462 2463 811810587 2463 2464 136749641 2464 2465 884003590 2465 2466 584627515 2466 2467 528417953 2467 2468 741828188 2468 2469 41945711 2469 2470 506274124 2470 2471 142099189 2471 2472 325801879 2472 2473 753365457 2473 2474 846102833 2474 2475 422095706 2475 2476 10555965 2476 2477 861045602 2477 2478 401399566 2478 2479 945092321 2479 2480 833228457 2480 2481 923896912 2481 2482 470036959 2482 2483 216218674 2483 2484 228869202 2484 2485 543846608 2485 2486 373594499 2486 2487 21479731 2487 2488 212254751 2488 2489 436535076 2489 2490 595653094 2490 2491 485116143 2491 2492 804112663 2492 2493 663052780 2493 2494 493168780 2494 2495 277785300 2495 2496 153650910 2496 2497 768659388 2497 2498 964709130 2498 2499 842795794 2499 2500 960728096 2500 2501 541579681 2501 2502 341709761 2502 2503 269310503 2503 2504 783775314 2504 2505 168182984 2505 2506 442186353 2506 2507 825916813 2507 2508 581989877 2508 2509 154124520 2509 2510 350100816 2510 2511 476049931 2511 2512 847025802 2512 2513 257694912 2513 2514 969122140 2514 2515 612216175 2515 2516 380271625 2516 2517 33368605 2517 2518 640513452 2518 2519 638746290 2519 2520 435604724 2520 2521 254925277 2521 2522 124527116 2522 2523 506361862 2523 2524 455671216 2524 2525 323307518 2525 2526 173076352 2526 2527 923093752 2527 2528 365188120 2528 2529 490178344 2529 2530 223259631 2530 2531 499732699 2531 2532 577531263 2532 2533 587294189 2533 2534 152933628 2534 2535 178464448 2535 2536 365959361 2536 2537 872106414 2537 2538 422805513 2538 2539 185355780 2539 2540 869928722 2540 2541 84613776 2541 2542 716935778 2542 2543 518032332 2543 2544 453015555 2544 2545 111974814 2545 2546 852933373 2546 2547 6028774 2547 2548 129943575 2548 2549 246768410 2549 2550 618678308 2550 2551 605462311 2551 2552 820320761 2552 2553 790375926 2553 2554 876166774 2554 2555 323322126 2555 2556 59065787 2556 2557 852594890 2557 2558 339400071 2558 2559 969390592 2559 2560 92671652 2560 2561 485435654 2561 2562 561501555 2562 2563 931309182 2563 2564 561445327 2564 2565 614128172 2565 2566 759262613 2566 2567 422575234 2567 2568 989202253 2568 2569 472317260 2569 2570 670964605 2570 2571 207848588 2571 2572 572874089 2572 2573 703503896 2573 2574 27552513 2574 2575 323171658 2575 2576 378134534 2576 2577 387754403 2577 2578 605817195 2578 2579 968169955 2579 2580 728887760 2580 2581 559103200 2581 2582 721536899 2582 2583 919296991 2583 2584 265542272 2584 2585 344348599 2585 2586 47597663 2586 2587 722250463 2587 2588 827426713 2588 2589 574569206 2589 2590 183706457 2590 2591 565842102 2591 2592 90583817 2592 2593 259213686 2593 2594 782890791 2594 2595 627940293 2595 2596 464924583 2596 2597 878742080 2597 2598 829798842 2598 2599 907122934 2599 2600 75116555 2600 2601 66320209 2601 2602 214282192 2602 2603 150753979 2603 2604 351851602 2604 2605 205795620 2605 2606 690636126 2606 2607 456598158 2607 2608 499503167 2608 2609 590690164 2609 2610 520050054 2610 2611 333297375 2611 2612 4772681 2612 2613 202503815 2613 2614 14312825 2614 2615 953396978 2615 2616 482068984 2616 2617 502195521 2617 2618 228120902 2618 2619 155335919 2619 2620 3378884 2620 2621 17932124 2621 2622 197844618 2622 2623 895441842 2623 2624 524123931 2624 2625 598681924 2625 2626 146540098 2626 2627 452974382 2627 2628 392574082 2628 2629 5974977 2629 2630 567498110 2630 2631 277109715 2631 2632 229645500 2632 2633 810277514 2633 2634 931092132 2634 2635 88765651 2635 2636 418052227 2636 2637 936263762 2637 2638 154593992 2638 2639 498784730 2639 2640 800511562 2640 2641 975137242 2641 2642 46587887 2642 2643 805528515 2643 2644 998041254 2644 2645 581361842 2645 2646 481104233 2646 2647 826679827 2647 2648 561066273 2648 2649 947140615 2649 2650 962848578 2650 2651 109233 2651 2652 163754222 2652 2653 845290018 2653 2654 5721625 2654 2655 770046736 2655 2656 378216650 2656 2657 855594421 2657 2658 224872480 2658 2659 610975325 2659 2660 790509221 2660 2661 826024095 2661 2662 354003019 2662 2663 815685355 2663 2664 996985634 2664 2665 471668228 2665 2666 367246750 2666 2667 155626147 2667 2668 917953573 2668 2669 666563713 2669 2670 90798724 2670 2671 42799129 2671 2672 614540647 2672 2673 215411529 2673 2674 25624812 2674 2675 248151958 2675 2676 323466049 2676 2677 826419588 2677 2678 101818047 2678 2679 209900616 2679 2680 290282516 2680 2681 772988146 2681 2682 139098416 2682 2683 674741742 2683 2684 762934584 2684 2685 605559346 2685 2686 399230511 2686 2687 493443455 2687 2688 199645389 2688 2689 262357081 2689 2690 715204711 2690 2691 698221276 2691 2692 659831039 2692 2693 477694958 2693 2694 952834060 2694 2695 713192820 2695 2696 547616500 2696 2697 221857466 2697 2698 164832254 2698 2699 973226768 2699 2700 468833681 2700 2701 100589163 2701 2702 88118597 2702 2703 288344744 2703 2704 350729108 2704 2705 147668324 2705 2706 578382621 2706 2707 531309309 2707 2708 772935338 2708 2709 886256679 2709 2710 739301646 2710 2711 803792622 2711 2712 467125302 2712 2713 345907117 2713 2714 761793809 2714 2715 180778370 2715 2716 295766489 2716 2717 555679919 2717 2718 286081961 2718 2719 314706682 2719 2720 483340013 2720 2721 158905181 2721 2722 757033524 2722 2723 494416686 2723 2724 824438334 2724 2725 502862024 2725 2726 583542458 2726 2727 449409258 2727 2728 211879651 2728 2729 23900442 2729 2730 81728950 2730 2731 291814707 2731 2732 677874183 2732 2733 198147741 2733 2734 407567719 2734 2735 767049313 2735 2736 160405775 2736 2737 682447440 2737 2738 171125198 2738 2739 937888971 2739 2740 910725799 2740 2741 460190085 2741 2742 486648613 2742 2743 519433572 2743 2744 729396638 2744 2745 780624231 2745 2746 969818111 2746 2747 205965893 2747 2748 161735910 2748 2749 179877353 2749 2750 626583428 2750 2751 74925551 2751 2752 697136734 2752 2753 792814441 2753 2754 750335769 2754 2755 204557253 2755 2756 129408421 2756 2757 189800471 2757 2758 746804997 2758 2759 114030760 2759 2760 71665149 2760 2761 642898802 2761 2762 976760188 2762 2763 100732117 2763 2764 387114026 2764 2765 790671456 2765 2766 383603549 2766 2767 117546476 2767 2768 941392040 2768 2769 260675548 2769 2770 275864607 2770 2771 977568702 2771 2772 553368093 2772 2773 992857799 2773 2774 431586545 2774 2775 415118019 2775 2776 95344996 2776 2777 561876522 2777 2778 996564187 2778 2779 82373415 2779 2780 373982262 2780 2781 511604118 2781 2782 379534450 2782 2783 249980667 2783 2784 227268213 2784 2785 105515948 2785 2786 334803255 2786 2787 233292172 2787 2788 903452692 2788 2789 240043705 2789 2790 313848974 2790 2791 68840401 2791 2792 704499621 2792 2793 799237497 2793 2794 627712598 2794 2795 580393982 2795 2796 389469568 2796 2797 903726077 2797 2798 324998441 2798 2799 482120757 2799 2800 285191053 2800 2801 328245927 2801 2802 778106417 2802 2803 2815068 2803 2804 524524463 2804 2805 40373585 2805 2806 604928677 2806 2807 685018889 2807 2808 201952973 2808 2809 418146445 2809 2810 104508639 2810 2811 464065946 2811 2812 823198334 2812 2813 330944775 2813 2814 120279324 2814 2815 690733410 2815 2816 591309137 2816 2817 829083399 2817 2818 127937999 2818 2819 75106302 2819 2820 578163638 2820 2821 774078483 2821 2822 526044357 2822 2823 959588235 2823 2824 303724721 2824 2825 535461130 2825 2826 535731037 2826 2827 465126983 2827 2828 802078794 2828 2829 734536069 2829 2830 756119915 2830 2831 630207933 2831 2832 726900522 2832 2833 31414899 2833 2834 120080226 2834 2835 781056398 2835 2836 912746148 2836 2837 563135374 2837 2838 573688957 2838 2839 296353070 2839 2840 255433043 2840 2841 294202311 2841 2842 579348113 2842 2843 485928827 2843 2844 16351552 2844 2845 38630487 2845 2846 784267121 2846 2847 107007885 2847 2848 303824416 2848 2849 789961023 2849 2850 824864969 2850 2851 753008661 2851 2852 383866056 2852 2853 866017278 2853 2854 481097900 2854 2855 649745017 2855 2856 976295858 2856 2857 290077293 2857 2858 747210438 2858 2859 543930704 2859 2860 755128236 2860 2861 10269816 2861 2862 53586645 2862 2863 705159534 2863 2864 120221798 2864 2865 732732545 2865 2866 328840033 2866 2867 699999098 2867 2868 423264351 2868 2869 10356072 2869 2870 425009714 2870 2871 994603681 2871 2872 947623190 2872 2873 751591986 2873 2874 220447391 2874 2875 583409739 2875 2876 710668707 2876 2877 559798973 2877 2878 399695973 2878 2879 586074979 2879 2880 163083135 2880 2881 66533309 2881 2882 891919135 2882 2883 531336673 2883 2884 870267971 2884 2885 212101712 2885 2886 225416404 2886 2887 121247989 2887 2888 938224009 2888 2889 507893567 2889 2890 599488427 2890 2891 772520909 2891 2892 681121519 2892 2893 848105427 2893 2894 658987705 2894 2895 967154435 2895 2896 563257938 2896 2897 65554427 2897 2898 376508582 2898 2899 249291158 2899 2900 754448405 2900 2901 112268127 2901 2902 595967995 2902 2903 32514375 2903 2904 672885500 2904 2905 706780497 2905 2906 599423404 2906 2907 349114940 2907 2908 331523171 2908 2909 32043226 2909 2910 274921579 2910 2911 836260109 2911 2912 336360504 2912 2913 655954533 2913 2914 435325706 2914 2915 408481779 2915 2916 278784836 2916 2917 854517442 2917 2918 162933060 2918 2919 975818901 2919 2920 491522807 2920 2921 822837786 2921 2922 87230465 2922 2923 424125070 2923 2924 647499174 2924 2925 580259036 2925 2926 992188193 2926 2927 946145746 2927 2928 525105548 2928 2929 350755408 2929 2930 888039890 2930 2931 710663732 2931 2932 164178935 2932 2933 583070221 2933 2934 498443567 2934 2935 540047255 2935 2936 933282380 2936 2937 716969340 2937 2938 658799093 2938 2939 496000470 2939 2940 154478237 2940 2941 29881159 2941 2942 663867373 2942 2943 209860954 2943 2944 736825299 2944 2945 738471228 2945 2946 597946154 2946 2947 930671820 2947 2948 824221303 2948 2949 473680607 2949 2950 505093603 2950 2951 48315559 2951 2952 674946010 2952 2953 356138349 2953 2954 123409428 2954 2955 95087777 2955 2956 528620558 2956 2957 44698319 2957 2958 237255224 2958 2959 155142440 2959 2960 554188555 2960 2961 725384115 2961 2962 935985707 2962 2963 859699463 2963 2964 204271226 2964 2965 727430666 2965 2966 243383854 2966 2967 526099204 2967 2968 852898254 2968 2969 401628175 2969 2970 959024781 2970 2971 26339287 2971 2972 816716314 2972 2973 668199236 2973 2974 912758043 2974 2975 121317352 2975 2976 830807113 2976 2977 462599095 2977 2978 565179186 2978 2979 321062154 2979 2980 586451081 2980 2981 9043184 2981 2982 104502562 2982 2983 272645801 2983 2984 86327960 2984 2985 894650592 2985 2986 50163671 2986 2987 533557916 2987 2988 201683447 2988 2989 90698597 2989 2990 816190405 2990 2991 225248693 2991 2992 510484499 2992 2993 173884200 2993 2994 846904043 2994 2995 446343435 2995 2996 68719456 2996 2997 300245725 2997 2998 329239170 2998 2999 934692624 2999 3000 344434306