3000 2999 1000 1 2 470451820 2 3 120922396 3 4 148610101 4 5 939171580 5 6 612311867 6 7 722636174 7 8 852335207 8 9 193260778 9 10 582744299 10 11 260973709 11 12 726112510 12 13 663796071 13 14 703490731 14 15 677541136 15 16 67433692 16 17 99859024 17 18 872141042 18 19 326148808 19 20 229930840 20 21 363898147 21 22 440350884 22 23 462455746 23 24 712401661 24 25 819539870 25 26 389290144 26 27 273053585 27 28 71147110 28 29 81754614 29 30 276730486 30 31 604102938 31 32 166998851 32 33 970010800 33 34 752404534 34 35 918913788 35 36 366861176 36 37 2418208 37 38 358532451 38 39 473898138 39 40 434697828 40 41 971028348 41 42 894519559 42 43 91303998 43 44 652444572 44 45 796920544 45 46 922596107 46 47 917213084 47 48 57690961 48 49 140600760 49 50 61037207 50 51 493329678 51 52 996126559 52 53 700030162 53 54 64250819 54 55 932777496 55 56 460688512 56 57 518627137 57 58 575392406 58 59 566507986 59 60 981996001 60 61 803992900 61 62 27708820 62 63 404722537 63 64 950379520 64 65 194440895 65 66 812155882 66 67 535873897 67 68 39145357 68 69 137815283 69 70 387313315 70 71 824926349 71 72 497042617 72 73 646240690 73 74 265294012 74 75 613163092 75 76 106063675 76 77 904272823 77 78 675378812 78 79 737965657 79 80 25673551 80 81 932853866 81 82 126301376 82 83 411332885 83 84 349240304 84 85 596916172 85 86 431448964 86 87 896363734 87 88 674827658 88 89 21283470 89 90 835656022 90 91 724415635 91 92 352026795 92 93 472646840 93 94 85702388 94 95 690117028 95 96 506382636 96 97 760338832 97 98 600750940 98 99 755594745 99 100 911487601 100 101 918790554 101 102 444994428 102 103 609709595 103 104 921620426 104 105 973726995 105 106 918533010 106 107 282806883 107 108 781596782 108 109 299821249 109 110 438158873 110 111 681029553 111 112 567870750 112 113 267367019 113 114 266913338 114 115 769494024 115 116 485837712 116 117 975556793 117 118 843444007 118 119 889129583 119 120 920929774 120 121 748400787 121 122 812918152 122 123 974533673 123 124 406768014 124 125 740576715 125 126 123090620 126 127 557298716 127 128 765202265 128 129 973468411 129 130 981482981 130 131 706500766 131 132 684422081 132 133 671057163 133 134 726607366 134 135 164673032 135 136 75647889 136 137 514919835 137 138 74744634 138 139 490318814 139 140 386900998 140 141 602267200 141 142 928320745 142 143 132062671 143 144 378057225 144 145 836746423 145 146 612910232 146 147 817144809 147 148 962878401 148 149 573055287 149 150 386126365 150 151 904357545 151 152 119492544 152 153 753789374 153 154 408957314 154 155 735126744 155 156 122832750 156 157 993191762 157 158 636506462 158 159 605842680 159 160 715874902 160 161 719294144 161 162 311504375 162 163 151179429 163 164 956563170 164 165 978010060 165 166 334024589 166 167 568697879 167 168 916347577 168 169 920290691 169 170 84248897 170 171 695859890 171 172 259959213 172 173 803741856 173 174 398785058 174 175 809329267 175 176 560764255 176 177 975210449 177 178 618409866 178 179 774678954 179 180 774654124 180 181 413573206 181 182 344553528 182 183 136210151 183 184 229101698 184 185 393172079 185 186 999663125 186 187 140814708 187 188 326246776 188 189 757968569 189 190 579389076 190 191 908643093 191 192 836964315 192 193 78218316 193 194 159660276 194 195 236490209 195 196 508013847 196 197 146295177 197 198 804124239 198 199 377122231 199 200 686398283 200 201 232339267 201 202 753891136 202 203 361087442 203 204 511537738 204 205 219724938 205 206 677628802 206 207 166814829 207 208 770749120 208 209 634679096 209 210 801816210 210 211 990122766 211 212 423982245 212 213 961655441 213 214 139826022 214 215 198641219 215 216 874323845 216 217 599433928 217 218 439963198 218 219 106725505 219 220 435324362 220 221 450897255 221 222 111468669 222 223 682319579 223 224 558822035 224 225 72009480 225 226 22165018 226 227 60648522 227 228 706883314 228 229 308850906 229 230 225266865 230 231 724550967 231 232 171532231 232 233 854594790 233 234 951940585 234 235 110597419 235 236 79754596 236 237 849997989 237 238 945041825 238 239 688957104 239 240 193437375 240 241 179016875 241 242 437900985 242 243 721289556 243 244 973174354 244 245 702722434 245 246 713014906 246 247 629511115 247 248 208191123 248 249 521137554 249 250 262765731 250 251 990728244 251 252 731267595 252 253 716000785 253 254 668658292 254 255 551981334 255 256 269415941 256 257 19171338 257 258 609655999 258 259 882277686 259 260 969709039 260 261 606906406 261 262 847377973 262 263 568769043 263 264 193719268 264 265 920425690 265 266 925514152 266 267 698375187 267 268 345600587 268 269 830088866 269 270 227123836 270 271 864119997 271 272 368973770 272 273 255370152 273 274 403894718 274 275 16361938 275 276 868704986 276 277 517319385 277 278 319598610 278 279 281941524 279 280 721245596 280 281 92622261 281 282 921346925 282 283 4636181 283 284 940871371 284 285 858855740 285 286 105307086 286 287 619867037 287 288 875175514 288 289 853989707 289 290 558359471 290 291 665925115 291 292 601573982 292 293 293515323 293 294 627981307 294 295 85126012 295 296 422515864 296 297 111538854 297 298 251287980 298 299 367896570 299 300 973691555 300 301 967145289 301 302 299821829 302 303 882856076 303 304 515353270 304 305 118859525 305 306 935937129 306 307 319334491 307 308 121546007 308 309 826219264 309 310 430985431 310 311 101587604 311 312 97161757 312 313 604910824 313 314 285503865 314 315 285961952 315 316 81031000 316 317 780015633 317 318 666798226 318 319 365613695 319 320 960594003 320 321 695635696 321 322 727088130 322 323 615874061 323 324 826348524 324 325 642626385 325 326 685362420 326 327 810322200 327 328 480899848 328 329 31827779 329 330 47874356 330 331 10808536 331 332 503915068 332 333 394207853 333 334 897167834 334 335 572856817 335 336 95041232 336 337 595812839 337 338 187524325 338 339 446923749 339 340 288225205 340 341 423193429 341 342 277026585 342 343 43886048 343 344 775832194 344 345 593404650 345 346 903736627 346 347 70113707 347 348 86815724 348 349 131241018 349 350 681373448 350 351 737039847 351 352 21352430 352 353 488114668 353 354 270989200 354 355 729414734 355 356 407702963 356 357 375865324 357 358 770263157 358 359 603128439 359 360 325519133 360 361 11361389 361 362 510240238 362 363 986616941 363 364 813495756 364 365 699390503 365 366 752587768 366 367 15945516 367 368 278394240 368 369 831529116 369 370 629273989 370 371 288658935 371 372 80396570 372 373 233524974 373 374 195818471 374 375 769902104 375 376 352299143 376 377 155119017 377 378 289816086 378 379 304983397 379 380 640137247 380 381 183208464 381 382 630317728 382 383 195305700 383 384 707095965 384 385 361208978 385 386 150400558 386 387 987419019 387 388 694203067 388 389 243760220 389 390 378476206 390 391 798218528 391 392 544510472 392 393 417347362 393 394 402728255 394 395 308844971 395 396 703949683 396 397 162363909 397 398 554038394 398 399 119720717 399 400 288694955 400 401 856309699 401 402 523379719 402 403 912800066 403 404 909243652 404 405 66006881 405 406 790051953 406 407 3213367 407 408 229395251 408 409 144799775 409 410 773262061 410 411 137492850 411 412 851281466 412 413 72446784 413 414 523599019 414 415 589049540 415 416 205069137 416 417 812090040 417 418 496296871 418 419 998403073 419 420 372939434 420 421 674217735 421 422 100757694 422 423 793327561 423 424 189037693 424 425 618760320 425 426 375494129 426 427 54037690 427 428 552185543 428 429 568615891 429 430 937960297 430 431 943977584 431 432 391069973 432 433 940989281 433 434 325132857 434 435 215780224 435 436 223857724 436 437 6059415 437 438 23264477 438 439 573006777 439 440 23696463 440 441 372954395 441 442 599942627 442 443 253749189 443 444 17782856 444 445 104463400 445 446 903523175 446 447 14387966 447 448 977020948 448 449 618223019 449 450 958320872 450 451 216072153 451 452 717404598 452 453 734512827 453 454 619788855 454 455 148433648 455 456 384090252 456 457 2305974 457 458 905731754 458 459 820278009 459 460 766465714 460 461 481452643 461 462 117869883 462 463 417800546 463 464 529604367 464 465 571646342 465 466 766194350 466 467 688196430 467 468 719632132 468 469 114272980 469 470 923199892 470 471 634190603 471 472 230897423 472 473 56534338 473 474 787059378 474 475 107974798 475 476 949177566 476 477 256288499 477 478 222962969 478 479 441041161 479 480 871101166 480 481 262721668 481 482 243465274 482 483 140142242 483 484 266803619 484 485 815969575 485 486 442293501 486 487 142448415 487 488 218119084 488 489 903438430 489 490 645037553 490 491 844321581 491 492 260415620 492 493 126671190 493 494 743787678 494 495 430997069 495 496 815140116 496 497 784581086 497 498 923119452 498 499 425114741 499 500 905222402 500 501 220046313 501 502 387555773 502 503 591534804 503 504 944980503 504 505 135095589 505 506 477946479 506 507 6712454 507 508 687665056 508 509 702836226 509 510 474884795 510 511 684223326 511 512 795990665 512 513 357052840 513 514 544551512 514 515 162491286 515 516 487006811 516 517 260601596 517 518 917480090 518 519 225316331 519 520 486500563 520 521 840070620 521 522 890542150 522 523 443084528 523 524 477785582 524 525 843389034 525 526 200787056 526 527 403132920 527 528 2908120 528 529 129958791 529 530 836336315 530 531 98045199 531 532 483031225 532 533 778589015 533 534 699201334 534 535 358219816 535 536 975980024 536 537 542188159 537 538 769436280 538 539 931253443 539 540 928447006 540 541 273240593 541 542 478109079 542 543 4786816 543 544 774589789 544 545 101506008 545 546 259529872 546 547 432655552 547 548 1289473 548 549 555522403 549 550 837103597 550 551 58033872 551 552 72195743 552 553 238870877 553 554 702211751 554 555 859844748 555 556 246330130 556 557 634348027 557 558 707385525 558 559 243771166 559 560 308609297 560 561 231203982 561 562 129598517 562 563 227040740 563 564 59391338 564 565 534273080 565 566 256923446 566 567 76355440 567 568 505783227 568 569 748553248 569 570 479323816 570 571 518143597 571 572 757933248 572 573 263181326 573 574 297865290 574 575 28298312 575 576 908049908 576 577 154024218 577 578 132239077 578 579 16240925 579 580 847396336 580 581 136766916 581 582 473695989 582 583 27881705 583 584 728175914 584 585 371608094 585 586 992326552 586 587 420299584 587 588 197803496 588 589 199250973 589 590 936941849 590 591 782328294 591 592 492211300 592 593 571029880 593 594 483173933 594 595 598539389 595 596 689009560 596 597 837346728 597 598 430793929 598 599 389755224 599 600 17887916 600 601 307912208 601 602 123356318 602 603 555175162 603 604 542563895 604 605 881312050 605 606 543231849 606 607 293724858 607 608 912397360 608 609 505719774 609 610 831686223 610 611 641978139 611 612 546855388 612 613 43343512 613 614 299132973 614 615 832152516 615 616 522709973 616 617 662812429 617 618 47641445 618 619 752527720 619 620 201340391 620 621 497429490 621 622 166113998 622 623 647290008 623 624 705242834 624 625 50244151 625 626 618410320 626 627 129207129 627 628 376182942 628 629 586145286 629 630 978638167 630 631 927790903 631 632 170895070 632 633 731618859 633 634 801338817 634 635 962246934 635 636 107224613 636 637 480542842 637 638 768553065 638 639 523724927 639 640 353434425 640 641 742690280 641 642 221772141 642 643 815545955 643 644 619504162 644 645 475821469 645 646 609799845 646 647 511600415 647 648 39835621 648 649 541934224 649 650 603301942 650 651 694973097 651 652 772176490 652 653 125259453 653 654 136463428 654 655 157086549 655 656 377955967 656 657 847778310 657 658 80679876 658 659 806092613 659 660 781612708 660 661 790163567 661 662 752112747 662 663 164744168 663 664 825420616 664 665 982171602 665 666 41275196 666 667 630364957 667 668 54562002 668 669 6263170 669 670 582317187 670 671 3872172 671 672 912145005 672 673 167893631 673 674 627569628 674 675 261571269 675 676 216674124 676 677 921160821 677 678 644198438 678 679 722378293 679 680 172183336 680 681 421898257 681 682 736410418 682 683 834606925 683 684 774246808 684 685 65431524 685 686 183041150 686 687 936455835 687 688 200974009 688 689 628110267 689 690 339943671 690 691 791396748 691 692 316886841 692 693 874949665 693 694 17503073 694 695 390353723 695 696 351958008 696 697 598882798 697 698 637933601 698 699 106021213 699 700 621400510 700 701 199000220 701 702 874202936 702 703 576738710 703 704 715005216 704 705 772094535 705 706 966685469 706 707 785257470 707 708 725542845 708 709 655595381 709 710 86116735 710 711 48534193 711 712 990166239 712 713 629091341 713 714 422158283 714 715 344956494 715 716 757274595 716 717 845272546 717 718 406230930 718 719 191186639 719 720 470655285 720 721 686920076 721 722 789364404 722 723 809632316 723 724 620357938 724 725 664913335 725 726 508734629 726 727 935710529 727 728 665984623 728 729 964673147 729 730 139432490 730 731 381755056 731 732 567910142 732 733 743331647 733 734 85118452 734 735 599212761 735 736 111286600 736 737 756734820 737 738 749525099 738 739 88978808 739 740 885815522 740 741 925116269 741 742 420651033 742 743 280281730 743 744 499822889 744 745 435557784 745 746 590296328 746 747 769195936 747 748 531476084 748 749 761283872 749 750 408666116 750 751 142655340 751 752 125239135 752 753 728197693 753 754 736553533 754 755 862607752 755 756 442602612 756 757 967231358 757 758 801037824 758 759 213547468 759 760 369602678 760 761 520720664 761 762 742430871 762 763 349997897 763 764 196460443 764 765 775549120 765 766 348608582 766 767 443586945 767 768 198978883 768 769 427230147 769 770 783321733 770 771 830939499 771 772 390411570 772 773 111749173 773 774 781639519 774 775 948760750 775 776 787306562 776 777 163776981 777 778 36115976 778 779 713669567 779 780 966771168 780 781 845284859 781 782 973497273 782 783 720942257 783 784 763181992 784 785 486244299 785 786 452147690 786 787 114653066 787 788 382851782 788 789 854929797 789 790 484219183 790 791 967691656 791 792 10909802 792 793 560723467 793 794 46399277 794 795 964933549 795 796 219239379 796 797 219793851 797 798 148460885 798 799 39348057 799 800 288451034 800 801 650840526 801 802 984473217 802 803 363719592 803 804 149165861 804 805 591601265 805 806 318517134 806 807 302658183 807 808 182203044 808 809 526305774 809 810 467059924 810 811 234361046 811 812 936716882 812 813 201293580 813 814 750557613 814 815 277359127 815 816 889251824 816 817 239541773 817 818 458313522 818 819 695277090 819 820 673696029 820 821 132870191 821 822 101681301 822 823 52121980 823 824 134105655 824 825 312737103 825 826 762080030 826 827 443727043 827 828 734769644 828 829 921259433 829 830 420805056 830 831 240968000 831 832 890259804 832 833 487350202 833 834 323239511 834 835 508547231 835 836 389191404 836 837 653669958 837 838 884644481 838 839 432685498 839 840 911677354 840 841 501350934 841 842 601099409 842 843 125598552 843 844 603214361 844 845 805954885 845 846 324806998 846 847 609965847 847 848 835177995 848 849 880600652 849 850 694096037 850 851 539709106 851 852 865223347 852 853 92778195 853 854 436774019 854 855 804039333 855 856 355902182 856 857 29011546 857 858 24698374 858 859 691877736 859 860 128124302 860 861 86196090 861 862 347491064 862 863 834298451 863 864 465133834 864 865 161439966 865 866 214875947 866 867 5553553 867 868 283328175 868 869 625572210 869 870 692081897 870 871 660737859 871 872 965552217 872 873 825581397 873 874 941265410 874 875 555431108 875 876 271244173 876 877 453151724 877 878 521058165 878 879 507769352 879 880 57006866 880 881 240715191 881 882 59548445 882 883 607824086 883 884 565604205 884 885 611355554 885 886 209956308 886 887 244585178 887 888 203792860 888 889 397882365 889 890 211889017 890 891 916823509 891 892 396662692 892 893 738129597 893 894 663313646 894 895 741079594 895 896 692713044 896 897 552068021 897 898 826378156 898 899 753380885 899 900 353475067 900 901 553355378 901 902 899070311 902 903 395678020 903 904 473020569 904 905 870452828 905 906 495024956 906 907 609382952 907 908 878810664 908 909 253716385 909 910 640003028 910 911 806571314 911 912 301500500 912 913 302575688 913 914 644561790 914 915 915097293 915 916 204052110 916 917 637214150 917 918 197386942 918 919 712158122 919 920 867007610 920 921 331716244 921 922 545833500 922 923 802061398 923 924 294305862 924 925 240895196 925 926 586194455 926 927 257019660 927 928 702709987 928 929 828770369 929 930 82580746 930 931 166288402 931 932 537992327 932 933 683789436 933 934 823169833 934 935 221831330 935 936 904234127 936 937 494850962 937 938 692278972 938 939 288691683 939 940 709830970 940 941 439479931 941 942 430129801 942 943 277818666 943 944 434129993 944 945 221687955 945 946 945230259 946 947 192139803 947 948 874252833 948 949 707354696 949 950 910228220 950 951 493103508 951 952 72149910 952 953 770860791 953 954 240437046 954 955 232557594 955 956 43066978 956 957 393529310 957 958 73046789 958 959 512753593 959 960 833814388 960 961 745170050 961 962 406488927 962 963 844105574 963 964 41308492 964 965 753100504 965 966 62645210 966 967 979610977 967 968 879948222 968 969 307322752 969 970 14332403 970 971 368523699 971 972 646059845 972 973 814585105 973 974 402962135 974 975 799695873 975 976 474936975 976 977 189226142 977 978 293208181 978 979 178602574 979 980 94833913 980 981 664712721 981 982 501430345 982 983 498531587 983 984 347098623 984 985 185314775 985 986 86574371 986 987 497447748 987 988 134448081 988 989 146757169 989 990 15048711 990 991 751799300 991 992 699500051 992 993 207058464 993 994 299075956 994 995 849712411 995 996 799810541 996 997 340755224 997 998 222736578 998 999 971322880 999 1000 445227838 1000 1001 293907876 1001 1002 707368995 1002 1003 249210608 1003 1004 895265902 1004 1005 25971661 1005 1006 588409066 1006 1007 17349734 1007 1008 756052884 1008 1009 204891824 1009 1010 125292357 1010 1011 930056722 1011 1012 777913605 1012 1013 193102687 1013 1014 296936688 1014 1015 429952292 1015 1016 625232691 1016 1017 90628757 1017 1018 472466757 1018 1019 823706717 1019 1020 178086425 1020 1021 937522383 1021 1022 484457915 1022 1023 486090754 1023 1024 418408084 1024 1025 616685055 1025 1026 377002219 1026 1027 226126992 1027 1028 617179862 1028 1029 266187693 1029 1030 781126331 1030 1031 260268359 1031 1032 328326513 1032 1033 941507499 1033 1034 759098154 1034 1035 972876857 1035 1036 194417104 1036 1037 946784034 1037 1038 765757565 1038 1039 544907820 1039 1040 712689071 1040 1041 111070234 1041 1042 941122318 1042 1043 557594618 1043 1044 672730033 1044 1045 889734697 1045 1046 615020477 1046 1047 310949333 1047 1048 388642296 1048 1049 415689843 1049 1050 570469301 1050 1051 137185131 1051 1052 269942417 1052 1053 904390605 1053 1054 370573995 1054 1055 177446922 1055 1056 979276375 1056 1057 384496246 1057 1058 662753217 1058 1059 495261208 1059 1060 102338233 1060 1061 980382580 1061 1062 124713853 1062 1063 848235119 1063 1064 333641410 1064 1065 445078799 1065 1066 700909955 1066 1067 615635070 1067 1068 4213271 1068 1069 159741529 1069 1070 667557345 1070 1071 540489100 1071 1072 186550623 1072 1073 425794367 1073 1074 416291227 1074 1075 825712851 1075 1076 841559530 1076 1077 951513158 1077 1078 804896499 1078 1079 301222223 1079 1080 556493554 1080 1081 139910749 1081 1082 343880680 1082 1083 865718791 1083 1084 439890592 1084 1085 650057629 1085 1086 472077649 1086 1087 850578614 1087 1088 335198463 1088 1089 819991463 1089 1090 431864982 1090 1091 144079871 1091 1092 469542718 1092 1093 829149228 1093 1094 659166469 1094 1095 772268221 1095 1096 436576676 1096 1097 42602889 1097 1098 420166354 1098 1099 157199480 1099 1100 811791377 1100 1101 823518602 1101 1102 972376494 1102 1103 785811701 1103 1104 472532780 1104 1105 710718032 1105 1106 235620610 1106 1107 560516837 1107 1108 109856302 1108 1109 563619661 1109 1110 733383624 1110 1111 438441405 1111 1112 589529418 1112 1113 352395371 1113 1114 574144006 1114 1115 342913189 1115 1116 477086540 1116 1117 344882664 1117 1118 800326282 1118 1119 582993530 1119 1120 978623310 1120 1121 737554969 1121 1122 200984548 1122 1123 842122239 1123 1124 226812447 1124 1125 208965804 1125 1126 123522184 1126 1127 934072304 1127 1128 103632101 1128 1129 407147845 1129 1130 747615791 1130 1131 131450516 1131 1132 402505941 1132 1133 620462505 1133 1134 193482834 1134 1135 917854264 1135 1136 577387043 1136 1137 64193789 1137 1138 639974477 1138 1139 117992460 1139 1140 524777172 1140 1141 891231024 1141 1142 868593027 1142 1143 938908314 1143 1144 644477617 1144 1145 281787655 1145 1146 850309023 1146 1147 734513124 1147 1148 291285079 1148 1149 484590278 1149 1150 62033653 1150 1151 900869912 1151 1152 801452396 1152 1153 51747192 1153 1154 633378290 1154 1155 856063980 1155 1156 222377180 1156 1157 832629538 1157 1158 621398958 1158 1159 451263137 1159 1160 716061676 1160 1161 283746088 1161 1162 209055657 1162 1163 385115825 1163 1164 75765353 1164 1165 163233684 1165 1166 571158097 1166 1167 415913674 1167 1168 519541419 1168 1169 582650195 1169 1170 343573656 1170 1171 415736406 1171 1172 286645577 1172 1173 420771960 1173 1174 753049198 1174 1175 604635266 1175 1176 326158456 1176 1177 738646358 1177 1178 822610083 1178 1179 658345069 1179 1180 841787044 1180 1181 818924997 1181 1182 188157212 1182 1183 807263440 1183 1184 64602104 1184 1185 49234290 1185 1186 619409191 1186 1187 239065830 1187 1188 46191613 1188 1189 497522656 1189 1190 222904560 1190 1191 960315384 1191 1192 531296090 1192 1193 816790015 1193 1194 978747917 1194 1195 183304580 1195 1196 192617402 1196 1197 460239207 1197 1198 852146484 1198 1199 258792969 1199 1200 414322635 1200 1201 638267697 1201 1202 379324172 1202 1203 53939314 1203 1204 464376162 1204 1205 45219954 1205 1206 460574240 1206 1207 678506524 1207 1208 188581307 1208 1209 101805141 1209 1210 769546630 1210 1211 554589662 1211 1212 538458580 1212 1213 683554082 1213 1214 597314452 1214 1215 71603486 1215 1216 925480211 1216 1217 855296726 1217 1218 657782144 1218 1219 570650044 1219 1220 710340697 1220 1221 503051543 1221 1222 939703720 1222 1223 777649835 1223 1224 36066412 1224 1225 168608074 1225 1226 286734183 1226 1227 158341639 1227 1228 11258511 1228 1229 628469552 1229 1230 746906896 1230 1231 896904506 1231 1232 937591861 1232 1233 465227063 1233 1234 23902576 1234 1235 329059167 1235 1236 865398796 1236 1237 610477771 1237 1238 197968717 1238 1239 102900980 1239 1240 311677635 1240 1241 268940357 1241 1242 319247048 1242 1243 704495258 1243 1244 746445890 1244 1245 603955513 1245 1246 162426075 1246 1247 616051561 1247 1248 63564795 1248 1249 919864578 1249 1250 345612013 1250 1251 611424856 1251 1252 915082257 1252 1253 503255799 1253 1254 938955458 1254 1255 353807188 1255 1256 571873935 1256 1257 417916565 1257 1258 232969254 1258 1259 707011249 1259 1260 462462430 1260 1261 7156994 1261 1262 225450585 1262 1263 669945624 1263 1264 79809040 1264 1265 523083893 1265 1266 372304768 1266 1267 993033490 1267 1268 455850823 1268 1269 108109216 1269 1270 783239903 1270 1271 689612676 1271 1272 152452970 1272 1273 469058881 1273 1274 811140403 1274 1275 660951444 1275 1276 539713288 1276 1277 292724635 1277 1278 899176753 1278 1279 471157 1279 1280 299993457 1280 1281 121814521 1281 1282 375898154 1282 1283 585548630 1283 1284 343075911 1284 1285 272699017 1285 1286 516698217 1286 1287 279587261 1287 1288 681599232 1288 1289 209046938 1289 1290 596766237 1290 1291 549993142 1291 1292 890032012 1292 1293 543057918 1293 1294 799658843 1294 1295 917349170 1295 1296 661825261 1296 1297 592542598 1297 1298 641594424 1298 1299 749039000 1299 1300 472250594 1300 1301 293662454 1301 1302 924864429 1302 1303 975867011 1303 1304 846203577 1304 1305 967526832 1305 1306 83258808 1306 1307 850293566 1307 1308 644810545 1308 1309 224440358 1309 1310 739257724 1310 1311 711550666 1311 1312 291822699 1312 1313 515617797 1313 1314 11746809 1314 1315 418357529 1315 1316 985773202 1316 1317 524747688 1317 1318 526383646 1318 1319 406905878 1319 1320 78337156 1320 1321 501645767 1321 1322 702962196 1322 1323 809520078 1323 1324 399923923 1324 1325 555625666 1325 1326 390478168 1326 1327 840934279 1327 1328 388474480 1328 1329 527193350 1329 1330 483827833 1330 1331 902747114 1331 1332 867979253 1332 1333 464024968 1333 1334 560903280 1334 1335 215864411 1335 1336 702752142 1336 1337 346969711 1337 1338 835697047 1338 1339 66412905 1339 1340 981464453 1340 1341 181642190 1341 1342 353601608 1342 1343 511854177 1343 1344 269422442 1344 1345 657041551 1345 1346 703860499 1346 1347 314817533 1347 1348 194790875 1348 1349 8236907 1349 1350 560621723 1350 1351 872662586 1351 1352 505571062 1352 1353 176329749 1353 1354 453396237 1354 1355 679752519 1355 1356 944628854 1356 1357 352421182 1357 1358 585897881 1358 1359 109780944 1359 1360 4545555 1360 1361 65131873 1361 1362 573765915 1362 1363 311702437 1363 1364 201446284 1364 1365 39517059 1365 1366 9704320 1366 1367 858283582 1367 1368 569660641 1368 1369 148602816 1369 1370 653633784 1370 1371 800276487 1371 1372 952310478 1372 1373 284543119 1373 1374 885078712 1374 1375 903794473 1375 1376 721507885 1376 1377 156065615 1377 1378 348673608 1378 1379 940197158 1379 1380 624203047 1380 1381 100582029 1381 1382 136978205 1382 1383 422595661 1383 1384 469441972 1384 1385 948887533 1385 1386 866098985 1386 1387 288843226 1387 1388 640029060 1388 1389 471586722 1389 1390 945086267 1390 1391 124840313 1391 1392 655653915 1392 1393 534045164 1393 1394 105837366 1394 1395 520046137 1395 1396 711477960 1396 1397 331325802 1397 1398 872620934 1398 1399 205017979 1399 1400 459590069 1400 1401 868118049 1401 1402 883085707 1402 1403 239635179 1403 1404 248034158 1404 1405 183783777 1405 1406 518889890 1406 1407 338973525 1407 1408 781711585 1408 1409 917020948 1409 1410 728800468 1410 1411 512295701 1411 1412 691881252 1412 1413 721109770 1413 1414 948294955 1414 1415 446619279 1415 1416 950476994 1416 1417 223791995 1417 1418 565578386 1418 1419 509086990 1419 1420 7189222 1420 1421 265651097 1421 1422 740460195 1422 1423 5598328 1423 1424 851514988 1424 1425 161821875 1425 1426 881570055 1426 1427 701755904 1427 1428 261542661 1428 1429 362675643 1429 1430 167694020 1430 1431 481882389 1431 1432 314445601 1432 1433 622321234 1433 1434 696287107 1434 1435 78534790 1435 1436 648054493 1436 1437 901965498 1437 1438 121981292 1438 1439 499763241 1439 1440 415561356 1440 1441 9018385 1441 1442 463931332 1442 1443 347172274 1443 1444 958781785 1444 1445 21143674 1445 1446 284238524 1446 1447 757345822 1447 1448 727156101 1448 1449 458682710 1449 1450 402641248 1450 1451 227199595 1451 1452 528242203 1452 1453 502955596 1453 1454 752675023 1454 1455 478876322 1455 1456 117192587 1456 1457 37430384 1457 1458 724856200 1458 1459 986241789 1459 1460 474770307 1460 1461 777215442 1461 1462 946378380 1462 1463 55078087 1463 1464 747596069 1464 1465 559726640 1465 1466 243506482 1466 1467 500071775 1467 1468 78308074 1468 1469 171023563 1469 1470 232881031 1470 1471 987341659 1471 1472 849864211 1472 1473 601482071 1473 1474 998484424 1474 1475 171440071 1475 1476 378540043 1476 1477 606431229 1477 1478 190048718 1478 1479 203678425 1479 1480 824411738 1480 1481 176739573 1481 1482 204325096 1482 1483 848012728 1483 1484 257226774 1484 1485 233297209 1485 1486 370990283 1486 1487 586657820 1487 1488 416276216 1488 1489 88908384 1489 1490 796216248 1490 1491 226324359 1491 1492 806981923 1492 1493 577489165 1493 1494 156462009 1494 1495 710144313 1495 1496 970987480 1496 1497 631457929 1497 1498 387703673 1498 1499 299991811 1499 1500 880296162 1500 1501 980452579 1501 1502 157608250 1502 1503 629471394 1503 1504 769683249 1504 1505 883613833 1505 1506 295415750 1506 1507 63234231 1507 1508 715494900 1508 1509 725519553 1509 1510 989153370 1510 1511 477379401 1511 1512 796690330 1512 1513 852614046 1513 1514 694342590 1514 1515 806518003 1515 1516 344269596 1516 1517 804996680 1517 1518 917574987 1518 1519 794220232 1519 1520 256851723 1520 1521 670707561 1521 1522 11326479 1522 1523 737177881 1523 1524 363587683 1524 1525 185173229 1525 1526 302436290 1526 1527 571768827 1527 1528 995317784 1528 1529 412566510 1529 1530 766409930 1530 1531 135794854 1531 1532 668593662 1532 1533 243015632 1533 1534 252542899 1534 1535 76677167 1535 1536 655916832 1536 1537 684043120 1537 1538 733357491 1538 1539 394648733 1539 1540 858324670 1540 1541 338531537 1541 1542 220370275 1542 1543 266513947 1543 1544 551249647 1544 1545 997160141 1545 1546 373645878 1546 1547 567247475 1547 1548 757349656 1548 1549 214889105 1549 1550 803686138 1550 1551 395346562 1551 1552 941626382 1552 1553 922768241 1553 1554 938795889 1554 1555 60311780 1555 1556 772542572 1556 1557 941440516 1557 1558 394743822 1558 1559 311704672 1559 1560 638483122 1560 1561 423773337 1561 1562 629253096 1562 1563 590567818 1563 1564 964999512 1564 1565 21870026 1565 1566 974789483 1566 1567 175616551 1567 1568 90771959 1568 1569 935384679 1569 1570 480991430 1570 1571 488944917 1571 1572 560744875 1572 1573 92837955 1573 1574 793821526 1574 1575 219324214 1575 1576 424684844 1576 1577 211167332 1577 1578 192856412 1578 1579 467211199 1579 1580 792084914 1580 1581 230264079 1581 1582 791280958 1582 1583 227182631 1583 1584 325349427 1584 1585 846700328 1585 1586 587502313 1586 1587 490713665 1587 1588 75090286 1588 1589 736046907 1589 1590 953384417 1590 1591 780862019 1591 1592 339034510 1592 1593 974429466 1593 1594 845175244 1594 1595 810961980 1595 1596 735776993 1596 1597 511895675 1597 1598 941410907 1598 1599 386460694 1599 1600 751413502 1600 1601 884023705 1601 1602 505369630 1602 1603 15862006 1603 1604 868057004 1604 1605 947938413 1605 1606 698660116 1606 1607 545127681 1607 1608 462275201 1608 1609 440189244 1609 1610 934685393 1610 1611 784593218 1611 1612 64409627 1612 1613 570428490 1613 1614 803654476 1614 1615 84881316 1615 1616 752423674 1616 1617 770325676 1617 1618 727499331 1618 1619 573210393 1619 1620 708689401 1620 1621 533800507 1621 1622 652005707 1622 1623 798136797 1623 1624 848862311 1624 1625 944869029 1625 1626 714503287 1626 1627 763076565 1627 1628 828609990 1628 1629 141564317 1629 1630 354041764 1630 1631 927166225 1631 1632 323784480 1632 1633 780345394 1633 1634 336076896 1634 1635 910205553 1635 1636 29233664 1636 1637 830888253 1637 1638 280448117 1638 1639 147218531 1639 1640 376093460 1640 1641 542650101 1641 1642 669764373 1642 1643 451315293 1643 1644 939555229 1644 1645 289063184 1645 1646 955348828 1646 1647 928624412 1647 1648 609717984 1648 1649 216442637 1649 1650 969759533 1650 1651 258189600 1651 1652 260961855 1652 1653 196953593 1653 1654 374428397 1654 1655 591684513 1655 1656 992361237 1656 1657 795123194 1657 1658 96122513 1658 1659 919675431 1659 1660 846988828 1660 1661 763108366 1661 1662 442899066 1662 1663 393627581 1663 1664 760264300 1664 1665 498639880 1665 1666 457888993 1666 1667 14594171 1667 1668 952578365 1668 1669 439902761 1669 1670 507179117 1670 1671 849869745 1671 1672 7766475 1672 1673 811252823 1673 1674 431674852 1674 1675 466600109 1675 1676 703459154 1676 1677 236809980 1677 1678 41064189 1678 1679 757085738 1679 1680 664109369 1680 1681 531718526 1681 1682 486271571 1682 1683 894957141 1683 1684 546685014 1684 1685 292790902 1685 1686 54962044 1686 1687 448806432 1687 1688 685628112 1688 1689 436149276 1689 1690 531694422 1690 1691 110904218 1691 1692 917419614 1692 1693 716931445 1693 1694 763816681 1694 1695 74664843 1695 1696 43221912 1696 1697 859718300 1697 1698 516768028 1698 1699 402661492 1699 1700 688459476 1700 1701 396388137 1701 1702 651416537 1702 1703 535789160 1703 1704 3538526 1704 1705 258155235 1705 1706 864416734 1706 1707 639642128 1707 1708 697750931 1708 1709 320129313 1709 1710 811602375 1710 1711 675164193 1711 1712 283385332 1712 1713 308008414 1713 1714 867042533 1714 1715 449680276 1715 1716 886063558 1716 1717 991913022 1717 1718 807729945 1718 1719 825778076 1719 1720 16306945 1720 1721 612605093 1721 1722 434786288 1722 1723 926771362 1723 1724 237517351 1724 1725 4453016 1725 1726 868545155 1726 1727 652627890 1727 1728 865995338 1728 1729 379668715 1729 1730 685892136 1730 1731 409970861 1731 1732 866677442 1732 1733 967640775 1733 1734 746296004 1734 1735 2976863 1735 1736 123122858 1736 1737 85754519 1737 1738 778546858 1738 1739 583571233 1739 1740 141245878 1740 1741 853867568 1741 1742 888861129 1742 1743 857494609 1743 1744 920027822 1744 1745 829397234 1745 1746 606355397 1746 1747 41539423 1747 1748 753219610 1748 1749 614998054 1749 1750 340452786 1750 1751 970286597 1751 1752 588114826 1752 1753 884074881 1753 1754 662233455 1754 1755 434868115 1755 1756 488316287 1756 1757 171889821 1757 1758 707597672 1758 1759 707245561 1759 1760 692993415 1760 1761 241278267 1761 1762 237796989 1762 1763 801119134 1763 1764 772724235 1764 1765 635087899 1765 1766 66140036 1766 1767 305337235 1767 1768 451916187 1768 1769 511507479 1769 1770 162792778 1770 1771 562416048 1771 1772 176248250 1772 1773 411795286 1773 1774 943475454 1774 1775 220009926 1775 1776 250846020 1776 1777 408249706 1777 1778 2066535 1778 1779 256426474 1779 1780 699678071 1780 1781 352468146 1781 1782 119046489 1782 1783 38468798 1783 1784 165737041 1784 1785 656258089 1785 1786 311620539 1786 1787 609090817 1787 1788 656986142 1788 1789 124193067 1789 1790 600423712 1790 1791 32786972 1791 1792 80022435 1792 1793 206758232 1793 1794 675852251 1794 1795 454991073 1795 1796 224528017 1796 1797 647386276 1797 1798 995726649 1798 1799 799588486 1799 1800 20165408 1800 1801 472006009 1801 1802 762237941 1802 1803 423650804 1803 1804 345046355 1804 1805 272473983 1805 1806 880050160 1806 1807 510185737 1807 1808 804394767 1808 1809 125490550 1809 1810 588991456 1810 1811 961995750 1811 1812 215353588 1812 1813 212665282 1813 1814 221691841 1814 1815 20673709 1815 1816 809260732 1816 1817 237913322 1817 1818 142080271 1818 1819 830252035 1819 1820 311366610 1820 1821 440329091 1821 1822 562946916 1822 1823 850715444 1823 1824 111295181 1824 1825 130504559 1825 1826 891613130 1826 1827 455695402 1827 1828 139234543 1828 1829 226215209 1829 1830 457539713 1830 1831 933077077 1831 1832 180175537 1832 1833 27570904 1833 1834 552011534 1834 1835 353415763 1835 1836 92828455 1836 1837 533471484 1837 1838 354152812 1838 1839 810892346 1839 1840 573312898 1840 1841 577473748 1841 1842 129274465 1842 1843 98361990 1843 1844 628771503 1844 1845 499878992 1845 1846 995918572 1846 1847 288048026 1847 1848 884454686 1848 1849 798011310 1849 1850 278115034 1850 1851 738924532 1851 1852 48861853 1852 1853 9518772 1853 1854 694515832 1854 1855 530493682 1855 1856 512580194 1856 1857 813507977 1857 1858 829950307 1858 1859 255001147 1859 1860 859163943 1860 1861 987649327 1861 1862 2764923 1862 1863 862240716 1863 1864 715026288 1864 1865 946319776 1865 1866 919726838 1866 1867 981039263 1867 1868 651264488 1868 1869 538841477 1869 1870 810707089 1870 1871 905951737 1871 1872 692211689 1872 1873 288301965 1873 1874 776250081 1874 1875 948644689 1875 1876 19820571 1876 1877 143050096 1877 1878 137276871 1878 1879 55461080 1879 1880 764395316 1880 1881 520734849 1881 1882 153033985 1882 1883 487226025 1883 1884 318611677 1884 1885 366148585 1885 1886 112223966 1886 1887 123157135 1887 1888 990157493 1888 1889 337574533 1889 1890 154835978 1890 1891 553750382 1891 1892 23661662 1892 1893 387517063 1893 1894 396838734 1894 1895 687254037 1895 1896 435901377 1896 1897 948699580 1897 1898 682867978 1898 1899 568488816 1899 1900 796850683 1900 1901 818868135 1901 1902 318758033 1902 1903 223771520 1903 1904 327283635 1904 1905 623723223 1905 1906 406774500 1906 1907 21711253 1907 1908 536236514 1908 1909 964260981 1909 1910 585387272 1910 1911 388480855 1911 1912 256083382 1912 1913 179958646 1913 1914 191920727 1914 1915 677586558 1915 1916 144380201 1916 1917 824177145 1917 1918 420894145 1918 1919 954711669 1919 1920 946125159 1920 1921 390164363 1921 1922 839205096 1922 1923 980045776 1923 1924 88682118 1924 1925 61715790 1925 1926 496842212 1926 1927 184611271 1927 1928 89732067 1928 1929 962036660 1929 1930 263863668 1930 1931 170862453 1931 1932 852923051 1932 1933 710933978 1933 1934 750536784 1934 1935 386556877 1935 1936 98787446 1936 1937 344358014 1937 1938 294429082 1938 1939 571927578 1939 1940 838620685 1940 1941 622572191 1941 1942 185259634 1942 1943 189115184 1943 1944 855922252 1944 1945 200625072 1945 1946 498367145 1946 1947 597479732 1947 1948 669247779 1948 1949 337785208 1949 1950 513974925 1950 1951 574313477 1951 1952 109661366 1952 1953 964923785 1953 1954 258798050 1954 1955 537437254 1955 1956 857840804 1956 1957 935903834 1957 1958 215183346 1958 1959 60901130 1959 1960 157692773 1960 1961 922811908 1961 1962 644101308 1962 1963 519676954 1963 1964 862585805 1964 1965 440029845 1965 1966 19354440 1966 1967 138318053 1967 1968 228010669 1968 1969 807348757 1969 1970 920153370 1970 1971 243941381 1971 1972 299159193 1972 1973 134402579 1973 1974 544080069 1974 1975 286126442 1975 1976 255387587 1976 1977 988921066 1977 1978 647572374 1978 1979 188877093 1979 1980 349532678 1980 1981 364756629 1981 1982 544972401 1982 1983 768482003 1983 1984 545157887 1984 1985 306647852 1985 1986 478546874 1986 1987 530515364 1987 1988 261945430 1988 1989 981598459 1989 1990 360286314 1990 1991 994411271 1991 1992 592481818 1992 1993 460345405 1993 1994 865126465 1994 1995 536804852 1995 1996 20670282 1996 1997 737281146 1997 1998 816031002 1998 1999 949410005 1999 2000 935819130 2000 2001 244101978 2001 2002 793856530 2002 2003 866761833 2003 2004 387422693 2004 2005 85568386 2005 2006 780094775 2006 2007 964142911 2007 2008 845496184 2008 2009 660546789 2009 2010 926572740 2010 2011 253577015 2011 2012 151965926 2012 2013 443018611 2013 2014 843022482 2014 2015 587911142 2015 2016 381221705 2016 2017 132074675 2017 2018 564075741 2018 2019 595496318 2019 2020 104122179 2020 2021 16930255 2021 2022 292291058 2022 2023 722406439 2023 2024 559220662 2024 2025 94253257 2025 2026 172323958 2026 2027 494588295 2027 2028 239158299 2028 2029 129559244 2029 2030 452558416 2030 2031 430346883 2031 2032 382075293 2032 2033 849139764 2033 2034 997459041 2034 2035 633618992 2035 2036 502249421 2036 2037 164469221 2037 2038 255655855 2038 2039 997311575 2039 2040 563479687 2040 2041 15631897 2041 2042 504073725 2042 2043 879344533 2043 2044 498509558 2044 2045 480998159 2045 2046 537930001 2046 2047 423345894 2047 2048 121758720 2048 2049 868035911 2049 2050 624926374 2050 2051 766041600 2051 2052 391851950 2052 2053 968775616 2053 2054 717224727 2054 2055 558633237 2055 2056 622373096 2056 2057 35748366 2057 2058 83731296 2058 2059 383973386 2059 2060 136835884 2060 2061 96106791 2061 2062 477113952 2062 2063 325007718 2063 2064 243129586 2064 2065 608936018 2065 2066 941848159 2066 2067 662865111 2067 2068 646857187 2068 2069 82324914 2069 2070 23651551 2070 2071 166383121 2071 2072 850597744 2072 2073 5615324 2073 2074 573848499 2074 2075 41029150 2075 2076 829098559 2076 2077 130737433 2077 2078 402382514 2078 2079 298479041 2079 2080 933650203 2080 2081 326262131 2081 2082 278772067 2082 2083 945166548 2083 2084 531317169 2084 2085 700840432 2085 2086 490186564 2086 2087 776078800 2087 2088 222316261 2088 2089 927815131 2089 2090 576519863 2090 2091 827073231 2091 2092 966836541 2092 2093 762185354 2093 2094 152604252 2094 2095 855012950 2095 2096 82840610 2096 2097 502004538 2097 2098 39884902 2098 2099 843291203 2099 2100 847986818 2100 2101 919108817 2101 2102 440219980 2102 2103 483748477 2103 2104 285078711 2104 2105 79948480 2105 2106 905811213 2106 2107 472305974 2107 2108 98997412 2108 2109 999387859 2109 2110 58831546 2110 2111 130734673 2111 2112 177578429 2112 2113 793403101 2113 2114 532449814 2114 2115 790273657 2115 2116 639338660 2116 2117 921214773 2117 2118 42252609 2118 2119 478638348 2119 2120 740724679 2120 2121 544274362 2121 2122 493898530 2122 2123 579909798 2123 2124 724348454 2124 2125 43316327 2125 2126 373779712 2126 2127 173230152 2127 2128 109900175 2128 2129 411777328 2129 2130 35677477 2130 2131 134840529 2131 2132 530744757 2132 2133 856780521 2133 2134 898686217 2134 2135 502602879 2135 2136 834029322 2136 2137 33686323 2137 2138 593310054 2138 2139 502498446 2139 2140 241027203 2140 2141 470493438 2141 2142 637403389 2142 2143 147017870 2143 2144 531482263 2144 2145 122961999 2145 2146 901171749 2146 2147 692300743 2147 2148 898212242 2148 2149 212990101 2149 2150 42561467 2150 2151 474285795 2151 2152 744732569 2152 2153 198063642 2153 2154 821508775 2154 2155 760265641 2155 2156 378086037 2156 2157 24708324 2157 2158 76398511 2158 2159 820887260 2159 2160 633620985 2160 2161 476282466 2161 2162 181718448 2162 2163 484790 2163 2164 856199946 2164 2165 436018456 2165 2166 13276111 2166 2167 456443446 2167 2168 342240099 2168 2169 371894847 2169 2170 547330245 2170 2171 840798619 2171 2172 330651497 2172 2173 528216627 2173 2174 581688671 2174 2175 623926207 2175 2176 438075294 2176 2177 548346234 2177 2178 938280290 2178 2179 856972863 2179 2180 241331050 2180 2181 328628680 2181 2182 823871716 2182 2183 91524014 2183 2184 864350353 2184 2185 355904896 2185 2186 968746805 2186 2187 155091608 2187 2188 829856342 2188 2189 524739123 2189 2190 53751847 2190 2191 235671627 2191 2192 142431011 2192 2193 811617433 2193 2194 617888006 2194 2195 494906395 2195 2196 537071249 2196 2197 445741151 2197 2198 822190707 2198 2199 705612549 2199 2200 807219720 2200 2201 523952825 2201 2202 804173964 2202 2203 45248707 2203 2204 100727067 2204 2205 912300284 2205 2206 455688170 2206 2207 331609472 2207 2208 458840660 2208 2209 788059178 2209 2210 571772776 2210 2211 795703671 2211 2212 307537870 2212 2213 194671900 2213 2214 921392641 2214 2215 663810089 2215 2216 574642400 2216 2217 103142731 2217 2218 425465047 2218 2219 499516731 2219 2220 11813620 2220 2221 956393530 2221 2222 136982864 2222 2223 957168873 2223 2224 455581572 2224 2225 165827931 2225 2226 575556651 2226 2227 586716390 2227 2228 119548286 2228 2229 136494033 2229 2230 951284835 2230 2231 65230096 2231 2232 928720008 2232 2233 580428022 2233 2234 243218111 2234 2235 970374740 2235 2236 816125685 2236 2237 49084702 2237 2238 709075761 2238 2239 203701278 2239 2240 279713684 2240 2241 884308332 2241 2242 718626056 2242 2243 153168506 2243 2244 875141851 2244 2245 291870902 2245 2246 966528811 2246 2247 111915712 2247 2248 882736303 2248 2249 846665348 2249 2250 828956658 2250 2251 787997035 2251 2252 787145427 2252 2253 458858039 2253 2254 332569249 2254 2255 210225416 2255 2256 133478378 2256 2257 498616391 2257 2258 1725058 2258 2259 905520714 2259 2260 81430314 2260 2261 939845541 2261 2262 859079070 2262 2263 594574138 2263 2264 1318047 2264 2265 884414783 2265 2266 801992983 2266 2267 376290722 2267 2268 616536869 2268 2269 308672524 2269 2270 284000948 2270 2271 534761145 2271 2272 562227371 2272 2273 712338742 2273 2274 64572674 2274 2275 281314739 2275 2276 57796213 2276 2277 612501221 2277 2278 783299031 2278 2279 558726915 2279 2280 371307537 2280 2281 948554532 2281 2282 663419312 2282 2283 924882561 2283 2284 591564359 2284 2285 54659105 2285 2286 542816960 2286 2287 444860334 2287 2288 469463350 2288 2289 117015871 2289 2290 285525401 2290 2291 650108948 2291 2292 15343116 2292 2293 135540042 2293 2294 553591923 2294 2295 400781260 2295 2296 31886945 2296 2297 745735110 2297 2298 824278813 2298 2299 196458009 2299 2300 832497969 2300 2301 155729760 2301 2302 900007805 2302 2303 592127026 2303 2304 232029044 2304 2305 637628294 2305 2306 273120965 2306 2307 928810526 2307 2308 132769884 2308 2309 302992658 2309 2310 180368693 2310 2311 48799671 2311 2312 345221418 2312 2313 946998817 2313 2314 878736518 2314 2315 305781712 2315 2316 973791918 2316 2317 87942403 2317 2318 923672826 2318 2319 660631129 2319 2320 431359563 2320 2321 483569406 2321 2322 110041411 2322 2323 936975104 2323 2324 633875461 2324 2325 345226616 2325 2326 205625088 2326 2327 478376967 2327 2328 638283443 2328 2329 785625897 2329 2330 607948072 2330 2331 157450080 2331 2332 56026596 2332 2333 148370108 2333 2334 140118135 2334 2335 856665838 2335 2336 246879513 2336 2337 253723955 2337 2338 199544125 2338 2339 269617157 2339 2340 369322195 2340 2341 861131879 2341 2342 294216458 2342 2343 79024585 2343 2344 749062314 2344 2345 43558386 2345 2346 341241227 2346 2347 284479866 2347 2348 826852848 2348 2349 323655053 2349 2350 277966676 2350 2351 817702351 2351 2352 341809710 2352 2353 744716066 2353 2354 479870784 2354 2355 744182295 2355 2356 284126035 2356 2357 742176657 2357 2358 587745653 2358 2359 842944734 2359 2360 461379407 2360 2361 987874781 2361 2362 878221114 2362 2363 638633160 2363 2364 677076209 2364 2365 280665072 2365 2366 77094858 2366 2367 630801045 2367 2368 728116324 2368 2369 691052880 2369 2370 646327454 2370 2371 134112250 2371 2372 796535535 2372 2373 420366353 2373 2374 367315215 2374 2375 21917490 2375 2376 144551272 2376 2377 2565545 2377 2378 517862464 2378 2379 199269042 2379 2380 33658746 2380 2381 844124269 2381 2382 631169484 2382 2383 620010633 2383 2384 548931812 2384 2385 840088816 2385 2386 458823595 2386 2387 349335214 2387 2388 335792746 2388 2389 142528929 2389 2390 994570792 2390 2391 656155250 2391 2392 692827996 2392 2393 535180945 2393 2394 192034170 2394 2395 806175508 2395 2396 784059840 2396 2397 818310995 2397 2398 43567362 2398 2399 20172147 2399 2400 891973918 2400 2401 146252028 2401 2402 458328096 2402 2403 236123870 2403 2404 154830825 2404 2405 599020106 2405 2406 696949938 2406 2407 952527623 2407 2408 85148037 2408 2409 898675169 2409 2410 164546347 2410 2411 290154263 2411 2412 140756729 2412 2413 864378032 2413 2414 369610315 2414 2415 873956315 2415 2416 574640691 2416 2417 148244595 2417 2418 936767616 2418 2419 874698011 2419 2420 851187186 2420 2421 183992913 2421 2422 692848345 2422 2423 995577867 2423 2424 235097684 2424 2425 439529893 2425 2426 329513379 2426 2427 833992411 2427 2428 791546876 2428 2429 151574234 2429 2430 169731234 2430 2431 474932585 2431 2432 924041183 2432 2433 873433199 2433 2434 698068246 2434 2435 120094124 2435 2436 522847258 2436 2437 392885863 2437 2438 521049014 2438 2439 349353685 2439 2440 534487561 2440 2441 152964310 2441 2442 185674303 2442 2443 614568003 2443 2444 901910689 2444 2445 43757799 2445 2446 768360578 2446 2447 21602861 2447 2448 688084779 2448 2449 656249248 2449 2450 449123549 2450 2451 343182377 2451 2452 55639238 2452 2453 887018848 2453 2454 870156633 2454 2455 713869909 2455 2456 451168202 2456 2457 20866520 2457 2458 724792963 2458 2459 962020924 2459 2460 972826906 2460 2461 647232778 2461 2462 704124570 2462 2463 213341864 2463 2464 808412652 2464 2465 687177507 2465 2466 500480257 2466 2467 109812098 2467 2468 955529293 2468 2469 500791298 2469 2470 605585237 2470 2471 819594453 2471 2472 800377214 2472 2473 462221641 2473 2474 82353186 2474 2475 785945713 2475 2476 728426822 2476 2477 591365763 2477 2478 332191294 2478 2479 271321919 2479 2480 631245279 2480 2481 169072077 2481 2482 776273858 2482 2483 867543169 2483 2484 826072721 2484 2485 432976038 2485 2486 982699364 2486 2487 802019464 2487 2488 375976558 2488 2489 836210936 2489 2490 881736622 2490 2491 155022148 2491 2492 958235700 2492 2493 121451193 2493 2494 28924310 2494 2495 294314589 2495 2496 746725204 2496 2497 285932720 2497 2498 622464737 2498 2499 807851443 2499 2500 306910395 2500 2501 356004151 2501 2502 158175980 2502 2503 926522853 2503 2504 806105632 2504 2505 241093437 2505 2506 335331315 2506 2507 649605198 2507 2508 173398269 2508 2509 746706861 2509 2510 163711457 2510 2511 550428065 2511 2512 648098380 2512 2513 454525342 2513 2514 702674856 2514 2515 246493486 2515 2516 595552577 2516 2517 931916996 2517 2518 641083477 2518 2519 604676485 2519 2520 663306961 2520 2521 577016143 2521 2522 518909663 2522 2523 44813285 2523 2524 962797748 2524 2525 915250036 2525 2526 362269237 2526 2527 860439426 2527 2528 477605764 2528 2529 256074494 2529 2530 272836382 2530 2531 382074187 2531 2532 262108860 2532 2533 230476861 2533 2534 313534992 2534 2535 164233362 2535 2536 809083886 2536 2537 539400669 2537 2538 761973497 2538 2539 135549705 2539 2540 603081272 2540 2541 714906219 2541 2542 156231684 2542 2543 527711520 2543 2544 939753072 2544 2545 580284076 2545 2546 591026997 2546 2547 224723366 2547 2548 820860655 2548 2549 942538629 2549 2550 265689652 2550 2551 871397311 2551 2552 852295327 2552 2553 350253976 2553 2554 596626595 2554 2555 971142148 2555 2556 328136311 2556 2557 707252798 2557 2558 761572651 2558 2559 648458695 2559 2560 342062225 2560 2561 865460628 2561 2562 15803170 2562 2563 156430964 2563 2564 92665577 2564 2565 274337709 2565 2566 980289750 2566 2567 417092882 2567 2568 664015796 2568 2569 763294949 2569 2570 925080185 2570 2571 714486761 2571 2572 702206299 2572 2573 749563221 2573 2574 141543849 2574 2575 102607422 2575 2576 213959698 2576 2577 952188314 2577 2578 536315450 2578 2579 554899737 2579 2580 119313776 2580 2581 39924194 2581 2582 803188457 2582 2583 148550543 2583 2584 680570036 2584 2585 959730656 2585 2586 517988958 2586 2587 88498414 2587 2588 120791336 2588 2589 667483338 2589 2590 245924339 2590 2591 600700711 2591 2592 493521559 2592 2593 690164306 2593 2594 836242093 2594 2595 18915931 2595 2596 876369624 2596 2597 350090741 2597 2598 685325247 2598 2599 634258995 2599 2600 669747991 2600 2601 398092000 2601 2602 480071973 2602 2603 387638492 2603 2604 491245646 2604 2605 350180479 2605 2606 630169713 2606 2607 249969058 2607 2608 211809492 2608 2609 286518691 2609 2610 326344488 2610 2611 446147852 2611 2612 383173680 2612 2613 603658050 2613 2614 98534206 2614 2615 673420318 2615 2616 735968293 2616 2617 901043842 2617 2618 324051796 2618 2619 244298597 2619 2620 238999286 2620 2621 500367576 2621 2622 762477697 2622 2623 107382030 2623 2624 957043099 2624 2625 55203413 2625 2626 624301260 2626 2627 578244346 2627 2628 247168510 2628 2629 701450616 2629 2630 226474722 2630 2631 956461410 2631 2632 14029457 2632 2633 929563291 2633 2634 798367354 2634 2635 330364572 2635 2636 513422388 2636 2637 883171973 2637 2638 540052100 2638 2639 270853381 2639 2640 201624604 2640 2641 234994157 2641 2642 248028921 2642 2643 581626699 2643 2644 38791480 2644 2645 178638609 2645 2646 633633023 2646 2647 912119245 2647 2648 862170258 2648 2649 503425470 2649 2650 51729410 2650 2651 241265168 2651 2652 945531099 2652 2653 561403873 2653 2654 131042234 2654 2655 190300158 2655 2656 616951529 2656 2657 824153296 2657 2658 972444458 2658 2659 821619627 2659 2660 204174604 2660 2661 981699379 2661 2662 73039170 2662 2663 91692622 2663 2664 132610431 2664 2665 113731984 2665 2666 565471140 2666 2667 962011868 2667 2668 787494906 2668 2669 189645681 2669 2670 747521411 2670 2671 439306819 2671 2672 183333988 2672 2673 386507059 2673 2674 663105192 2674 2675 63147840 2675 2676 609207462 2676 2677 138514030 2677 2678 102661263 2678 2679 698608605 2679 2680 100954523 2680 2681 735379708 2681 2682 735237550 2682 2683 245318282 2683 2684 255414563 2684 2685 611739304 2685 2686 953856213 2686 2687 447166807 2687 2688 412946805 2688 2689 547457200 2689 2690 368768972 2690 2691 717880535 2691 2692 445789832 2692 2693 934248298 2693 2694 634321470 2694 2695 488262578 2695 2696 520244844 2696 2697 60512430 2697 2698 912831159 2698 2699 787440030 2699 2700 512103491 2700 2701 415154678 2701 2702 234664361 2702 2703 814269588 2703 2704 974492832 2704 2705 373023923 2705 2706 927916430 2706 2707 157145575 2707 2708 933785208 2708 2709 442862962 2709 2710 771498465 2710 2711 556316673 2711 2712 87828556 2712 2713 350246521 2713 2714 773906486 2714 2715 162750217 2715 2716 216523395 2716 2717 230659963 2717 2718 476478051 2718 2719 817336878 2719 2720 210403827 2720 2721 553098998 2721 2722 513043420 2722 2723 1489811 2723 2724 465151102 2724 2725 939341101 2725 2726 454873117 2726 2727 828105943 2727 2728 546733529 2728 2729 460855997 2729 2730 866701888 2730 2731 770390080 2731 2732 33708648 2732 2733 886467807 2733 2734 378109358 2734 2735 67948163 2735 2736 749533765 2736 2737 767333177 2737 2738 749680114 2738 2739 445910834 2739 2740 392803936 2740 2741 689465185 2741 2742 209702313 2742 2743 81908674 2743 2744 782030272 2744 2745 241172463 2745 2746 870743702 2746 2747 153690424 2747 2748 690952424 2748 2749 49936189 2749 2750 287089776 2750 2751 285573972 2751 2752 510461886 2752 2753 248127264 2753 2754 956133666 2754 2755 361683448 2755 2756 597678687 2756 2757 206331633 2757 2758 182717134 2758 2759 323833375 2759 2760 822439448 2760 2761 464862857 2761 2762 103997718 2762 2763 720113487 2763 2764 546118711 2764 2765 608730485 2765 2766 219131132 2766 2767 626719334 2767 2768 243044311 2768 2769 626137090 2769 2770 380094954 2770 2771 154121340 2771 2772 38822710 2772 2773 534676787 2773 2774 111604719 2774 2775 999740673 2775 2776 616590536 2776 2777 510375785 2777 2778 752051240 2778 2779 705244017 2779 2780 807551847 2780 2781 264206255 2781 2782 855581498 2782 2783 906276022 2783 2784 904662951 2784 2785 40888827 2785 2786 91193882 2786 2787 147043400 2787 2788 954985973 2788 2789 949898288 2789 2790 223125990 2790 2791 223823813 2791 2792 545813423 2792 2793 695142769 2793 2794 212491676 2794 2795 623496457 2795 2796 865434589 2796 2797 588376105 2797 2798 214450126 2798 2799 446909963 2799 2800 560275130 2800 2801 285245850 2801 2802 560046284 2802 2803 915344711 2803 2804 377234621 2804 2805 51747267 2805 2806 458315087 2806 2807 436491729 2807 2808 595324007 2808 2809 180200812 2809 2810 782469862 2810 2811 353095518 2811 2812 309897735 2812 2813 145689203 2813 2814 958573173 2814 2815 726357513 2815 2816 513396071 2816 2817 399960860 2817 2818 585275863 2818 2819 973200098 2819 2820 814532297 2820 2821 470015717 2821 2822 68078749 2822 2823 357956634 2823 2824 202441191 2824 2825 493310512 2825 2826 436717359 2826 2827 40600837 2827 2828 404239924 2828 2829 704016129 2829 2830 632909428 2830 2831 701665676 2831 2832 714075312 2832 2833 988866291 2833 2834 187737101 2834 2835 685391944 2835 2836 460982449 2836 2837 625892002 2837 2838 651696585 2838 2839 428440705 2839 2840 933827091 2840 2841 620247282 2841 2842 339929119 2842 2843 938992521 2843 2844 271551629 2844 2845 242897657 2845 2846 151318232 2846 2847 117988276 2847 2848 335988768 2848 2849 969362570 2849 2850 822265801 2850 2851 626645239 2851 2852 104573791 2852 2853 499756478 2853 2854 52274972 2854 2855 681519253 2855 2856 466825442 2856 2857 463653791 2857 2858 310588083 2858 2859 746670744 2859 2860 458270907 2860 2861 972309289 2861 2862 507598117 2862 2863 86875435 2863 2864 635448260 2864 2865 706672294 2865 2866 107594096 2866 2867 879695890 2867 2868 748148850 2868 2869 336631301 2869 2870 192214451 2870 2871 969790943 2871 2872 109086695 2872 2873 461451915 2873 2874 366172917 2874 2875 917523236 2875 2876 342020132 2876 2877 299114196 2877 2878 121265815 2878 2879 731614665 2879 2880 965485160 2880 2881 567724264 2881 2882 969749585 2882 2883 703138808 2883 2884 779698422 2884 2885 634829015 2885 2886 670108774 2886 2887 964458072 2887 2888 962993968 2888 2889 36741827 2889 2890 734213941 2890 2891 156916546 2891 2892 535935087 2892 2893 77326050 2893 2894 813027857 2894 2895 86827604 2895 2896 613059206 2896 2897 560492363 2897 2898 258618264 2898 2899 49269186 2899 2900 15874063 2900 2901 6086975 2901 2902 636280884 2902 2903 421140124 2903 2904 360673221 2904 2905 91828789 2905 2906 485450693 2906 2907 591822991 2907 2908 245462283 2908 2909 972038384 2909 2910 833812591 2910 2911 645138429 2911 2912 82647154 2912 2913 994027825 2913 2914 572996931 2914 2915 321467723 2915 2916 43866728 2916 2917 40098426 2917 2918 85647749 2918 2919 707987666 2919 2920 182939917 2920 2921 793063413 2921 2922 121206073 2922 2923 290691352 2923 2924 166903196 2924 2925 127355945 2925 2926 422656423 2926 2927 223802713 2927 2928 487393170 2928 2929 242403349 2929 2930 879524520 2930 2931 290024128 2931 2932 173579260 2932 2933 334824365 2933 2934 320836831 2934 2935 679104750 2935 2936 314296598 2936 2937 692328064 2937 2938 112390295 2938 2939 521364590 2939 2940 664180295 2940 2941 857569924 2941 2942 64651561 2942 2943 963308983 2943 2944 255459735 2944 2945 216255878 2945 2946 483008934 2946 2947 449274413 2947 2948 884992335 2948 2949 431790141 2949 2950 919879315 2950 2951 344524447 2951 2952 904146487 2952 2953 739244439 2953 2954 928343304 2954 2955 966494238 2955 2956 477929855 2956 2957 323793006 2957 2958 114855656 2958 2959 436157760 2959 2960 985946948 2960 2961 294041833 2961 2962 435621931 2962 2963 7584785 2963 2964 883455793 2964 2965 665002354 2965 2966 935783255 2966 2967 442648728 2967 2968 117658946 2968 2969 907395919 2969 2970 848155918 2970 2971 778786817 2971 2972 311881892 2972 2973 475824351 2973 2974 819658944 2974 2975 165256812 2975 2976 538798265 2976 2977 466790016 2977 2978 132084561 2978 2979 747816503 2979 2980 414966983 2980 2981 930899444 2981 2982 760451213 2982 2983 367212656 2983 2984 19324444 2984 2985 394308199 2985 2986 232837134 2986 2987 794271916 2987 2988 837894899 2988 2989 566488057 2989 2990 818276376 2990 2991 680867250 2991 2992 441893224 2992 2993 544841718 2993 2994 818322481 2994 2995 157522278 2995 2996 597005864 2996 2997 702914627 2997 2998 295250607 2998 2999 149321868 2999 3000 483909136