3000 2999 2998 1 2 55714128 2 3 532302777 3 4 547053244 4 5 475897858 5 6 691794338 6 7 814244388 7 8 647065448 8 9 834157558 9 10 611904080 10 11 506854603 11 12 168866575 12 13 222863549 13 14 667550714 14 15 565779434 15 16 558385056 16 17 366605224 17 18 832562481 18 19 613342767 19 20 71998921 20 21 327433947 21 22 263259968 22 23 392604711 23 24 679832407 24 25 663909935 25 26 237675731 26 27 381192685 27 28 410687890 28 29 786596009 29 30 946463964 30 31 489121989 31 32 803187256 32 33 161152931 33 34 67937597 34 35 88759830 35 36 98521590 36 37 179982161 37 38 580167559 38 39 697971718 39 40 702712815 40 41 775777246 41 42 982946736 42 43 374111365 43 44 630780297 44 45 13213176 45 46 897327876 46 47 739641606 47 48 209831014 48 49 547232836 49 50 178588220 50 51 59984577 51 52 305613842 52 53 969616167 53 54 229706999 54 55 346209031 55 56 213160199 56 57 95410785 57 58 763745012 58 59 522663519 59 60 415700215 60 61 857214094 61 62 364173420 62 63 179799258 63 64 311346105 64 65 55984841 65 66 219934219 66 67 242750852 67 68 779292365 68 69 77739627 69 70 557901965 70 71 993296119 71 72 609096590 72 73 643171569 73 74 228932082 74 75 845313801 75 76 378071539 76 77 898305531 77 78 568608861 78 79 441717669 79 80 636443649 80 81 493982577 81 82 910416015 82 83 530349239 83 84 380692945 84 85 597976000 85 86 957415930 86 87 690005825 87 88 719054905 88 89 584609858 89 90 438296709 90 91 972798347 91 92 938003388 92 93 900671451 93 94 241109111 94 95 764722758 95 96 105287425 96 97 674140784 97 98 312639986 98 99 53456908 99 100 409059763 100 101 756008466 101 102 492401287 102 103 381558881 103 104 671340841 104 105 836443687 105 106 169823246 106 107 639653292 107 108 151002989 108 109 877968265 109 110 826317697 110 111 591399981 111 112 163615324 112 113 93372923 113 114 106267118 114 115 189089547 115 116 808786672 116 117 681395526 117 118 830548617 118 119 489284602 119 120 963153369 120 121 559828358 121 122 795842249 122 123 346783656 123 124 427047955 124 125 817832958 125 126 138631816 126 127 903553304 127 128 911169156 128 129 391953663 129 130 109447236 130 131 123510311 131 132 602840476 132 133 760479147 133 134 768066214 134 135 731179350 135 136 374311207 136 137 686279087 137 138 388802588 138 139 16262813 139 140 78675103 140 141 952411306 141 142 521429332 142 143 289300139 143 144 969688731 144 145 802802925 145 146 544319842 146 147 842122877 147 148 566827918 148 149 828390550 149 150 131870221 150 151 915542190 151 152 1807386 152 153 54579377 153 154 575926678 154 155 605222404 155 156 184919512 156 157 951165564 157 158 767295389 158 159 327607041 159 160 339301478 160 161 200054107 161 162 544715891 162 163 356220313 163 164 935255488 164 165 523805863 165 166 670600921 166 167 667704871 167 168 16528809 168 169 470191359 169 170 231312381 170 171 356090223 171 172 420786481 172 173 59413443 173 174 890792100 174 175 294829317 175 176 478664273 176 177 325550582 177 178 959547201 178 179 389566910 179 180 920873196 180 181 640917255 181 182 661811731 182 183 771035816 183 184 764872023 184 185 355410368 185 186 412430872 186 187 309414019 187 188 947849504 188 189 647801304 189 190 647033551 190 191 409387869 191 192 869037990 192 193 593811995 193 194 910769611 194 195 921316805 195 196 818368310 196 197 142109753 197 198 984261062 198 199 655540905 199 200 359914785 200 201 556154874 201 202 367847199 202 203 804175812 203 204 291293481 204 205 507864816 205 206 254896032 206 207 291950042 207 208 217109657 208 209 147118038 209 210 355756225 210 211 275796793 211 212 712607748 212 213 236108055 213 214 175983876 214 215 722912007 215 216 349472050 216 217 93013352 217 218 127932141 218 219 207008691 219 220 992109477 220 221 456968850 221 222 749117857 222 223 552312461 223 224 955419590 224 225 105221197 225 226 50972954 226 227 936239218 227 228 951671473 228 229 164879688 229 230 933190661 230 231 453291936 231 232 638430874 232 233 732953670 233 234 159876921 234 235 702314664 235 236 190180314 236 237 849758050 237 238 478894803 238 239 729155713 239 240 396169882 240 241 542655859 241 242 763662578 242 243 144004536 243 244 450003738 244 245 501398922 245 246 317165068 246 247 463427781 247 248 40682143 248 249 626831512 249 250 647886571 250 251 194797434 251 252 219302647 252 253 669631789 253 254 494209096 254 255 72395669 255 256 331359914 256 257 918128475 257 258 806787586 258 259 717541492 259 260 41878975 260 261 424863417 261 262 639091195 262 263 585747751 263 264 991848579 264 265 37662352 265 266 873358369 266 267 628508874 267 268 248711135 268 269 983730354 269 270 444043465 270 271 137186861 271 272 524002874 272 273 294603174 273 274 862382382 274 275 33007037 275 276 991876561 276 277 112358997 277 278 899320215 278 279 581795515 279 280 498041420 280 281 165314128 281 282 803164087 282 283 260774851 283 284 249583492 284 285 631884901 285 286 176851007 286 287 10073701 287 288 904910038 288 289 719447438 289 290 544882387 290 291 64948719 291 292 851141436 292 293 479545983 293 294 753520215 294 295 308985972 295 296 895737583 296 297 867278410 297 298 846874449 298 299 936627512 299 300 45176711 300 301 214338129 301 302 353796655 302 303 458321502 303 304 538145120 304 305 25320015 305 306 124527219 306 307 533954175 307 308 734139176 308 309 948485361 309 310 206968752 310 311 735195133 311 312 564200060 312 313 848523531 313 314 287315178 314 315 544425105 315 316 403023237 316 317 135903331 317 318 624566863 318 319 921511033 319 320 421242963 320 321 356784484 321 322 587921990 322 323 773823460 323 324 349221179 324 325 845815944 325 326 879124164 326 327 794777680 327 328 912181978 328 329 722597850 329 330 105365988 330 331 905246732 331 332 534379384 332 333 93024105 333 334 733155066 334 335 425889922 335 336 532861904 336 337 738023376 337 338 71922337 338 339 976467625 339 340 647663000 340 341 923961593 341 342 42349903 342 343 999920785 343 344 429918382 344 345 31861506 345 346 71682964 346 347 281697307 347 348 835833056 348 349 965612348 349 350 237182959 350 351 188045003 351 352 35465816 352 353 378656592 353 354 874724429 354 355 809751734 355 356 471440547 356 357 946459260 357 358 756150933 358 359 536085084 359 360 982219003 360 361 601568791 361 362 374046972 362 363 934669689 363 364 949883779 364 365 439618686 365 366 242377892 366 367 793537073 367 368 69528808 368 369 391853877 369 370 536847332 370 371 64477321 371 372 828750302 372 373 100075078 373 374 379201343 374 375 166671482 375 376 870930651 376 377 913763366 377 378 236971286 378 379 602846401 379 380 90094619 380 381 434034825 381 382 224937086 382 383 715952707 383 384 620626365 384 385 31608546 385 386 753677612 386 387 799455258 387 388 168460918 388 389 221741709 389 390 787765824 390 391 229562327 391 392 867742236 392 393 997167831 393 394 330892032 394 395 430646163 395 396 522217 396 397 199846164 397 398 819562623 398 399 652929703 399 400 17129668 400 401 846415887 401 402 11225346 402 403 542394243 403 404 180256066 404 405 599529459 405 406 62965818 406 407 85352056 407 408 941205071 408 409 94308030 409 410 267408790 410 411 671493574 411 412 277337681 412 413 2042584 413 414 155418508 414 415 260713109 415 416 460251928 416 417 800185565 417 418 179694779 418 419 313253562 419 420 228142226 420 421 114481588 421 422 107330821 422 423 580047941 423 424 800967373 424 425 372044116 425 426 818260518 426 427 293718614 427 428 145828405 428 429 234427452 429 430 17480818 430 431 163706520 431 432 163515195 432 433 840038652 433 434 240774490 434 435 744301394 435 436 658837321 436 437 397766266 437 438 31344957 438 439 963754018 439 440 581270038 440 441 550684823 441 442 329028270 442 443 361391363 443 444 798984730 444 445 528566024 445 446 691742600 446 447 923858535 447 448 138285986 448 449 664092670 449 450 247634255 450 451 250601197 451 452 881334531 452 453 331983223 453 454 283358133 454 455 803861695 455 456 675714027 456 457 841338145 457 458 429919544 458 459 493055627 459 460 980070355 460 461 103841510 461 462 482047464 462 463 207254044 463 464 256650128 464 465 947397656 465 466 902268999 466 467 545178772 467 468 334931465 468 469 435302715 469 470 560790601 470 471 791148104 471 472 365515267 472 473 276788841 473 474 707997240 474 475 226593894 475 476 761820479 476 477 856408362 477 478 879230919 478 479 767735361 479 480 821074996 480 481 323715169 481 482 476470948 482 483 164364707 483 484 814248373 484 485 23476223 485 486 400998064 486 487 898229687 487 488 222811768 488 489 363132148 489 490 794923715 490 491 640852662 491 492 983020194 492 493 562846246 493 494 43163149 494 495 157481772 495 496 964407311 496 497 914291261 497 498 128873262 498 499 183450326 499 500 285918918 500 501 17972065 501 502 493793008 502 503 991607640 503 504 815281994 504 505 642496204 505 506 382831012 506 507 376153119 507 508 958725944 508 509 662612397 509 510 498794933 510 511 224453988 511 512 576312568 512 513 409552732 513 514 861257467 514 515 473003176 515 516 427558175 516 517 227262620 517 518 656366940 518 519 710787941 519 520 511223371 520 521 507653535 521 522 260282787 522 523 21047102 523 524 255505023 524 525 892777263 525 526 372945431 526 527 357967273 527 528 91521224 528 529 115775048 529 530 723259182 530 531 362907700 531 532 600253409 532 533 184432875 533 534 579818361 534 535 92538805 535 536 511649295 536 537 273892006 537 538 432005082 538 539 392515728 539 540 766883587 540 541 457939950 541 542 35869939 542 543 948680947 543 544 194474165 544 545 248522966 545 546 641538693 546 547 761717385 547 548 22750641 548 549 644984750 549 550 597398422 550 551 209197487 551 552 366458627 552 553 32106528 553 554 530606928 554 555 741613939 555 556 972612863 556 557 877612668 557 558 630178820 558 559 72648982 559 560 471884415 560 561 721690862 561 562 859305689 562 563 531676759 563 564 571833699 564 565 808561039 565 566 557312753 566 567 408674184 567 568 848898768 568 569 804397829 569 570 918258997 570 571 274462429 571 572 198846238 572 573 662931201 573 574 259959033 574 575 305545555 575 576 651458112 576 577 697875492 577 578 553119905 578 579 762003372 579 580 843998769 580 581 995161230 581 582 894569056 582 583 448374535 583 584 399415436 584 585 380029189 585 586 999468316 586 587 858308379 587 588 665945791 588 589 711743854 589 590 216311312 590 591 953794632 591 592 828320717 592 593 60158149 593 594 381431802 594 595 733734607 595 596 282676260 596 597 27002866 597 598 179835156 598 599 949456712 599 600 542463517 600 601 487069105 601 602 897090711 602 603 576003359 603 604 879285134 604 605 673647080 605 606 907691055 606 607 351434825 607 608 330753323 608 609 573666071 609 610 61990525 610 611 328930458 611 612 507739741 612 613 701526115 613 614 789051214 614 615 826424000 615 616 978848488 616 617 279304681 617 618 921276337 618 619 510792081 619 620 643851313 620 621 238618707 621 622 331204810 622 623 249379328 623 624 429500008 624 625 30194461 625 626 996782072 626 627 635163434 627 628 125055885 628 629 557998561 629 630 462374715 630 631 232560234 631 632 778365225 632 633 778849736 633 634 565917178 634 635 425136851 635 636 178671449 636 637 101095937 637 638 878328740 638 639 453221717 639 640 879202111 640 641 247745048 641 642 333275609 642 643 529017501 643 644 254590765 644 645 118295617 645 646 914261726 646 647 760649409 647 648 127365849 648 649 966149005 649 650 668435550 650 651 994583502 651 652 422366107 652 653 752894778 653 654 546416976 654 655 158212142 655 656 853711790 656 657 528123798 657 658 518407177 658 659 671773348 659 660 147973482 660 661 713505293 661 662 128570924 662 663 643227993 663 664 716184363 664 665 652972548 665 666 35799638 666 667 437204698 667 668 227378178 668 669 144357660 669 670 664764214 670 671 748195661 671 672 974575335 672 673 333760477 673 674 953135840 674 675 579882403 675 676 694132536 676 677 509146805 677 678 507127896 678 679 445512514 679 680 594200258 680 681 161095632 681 682 399994306 682 683 98314536 683 684 738066139 684 685 902676718 685 686 130253962 686 687 325085363 687 688 894276446 688 689 367188244 689 690 52865077 690 691 840634293 691 692 706318465 692 693 30247265 693 694 454987537 694 695 153989765 695 696 308356725 696 697 263706754 697 698 31256104 698 699 560345778 699 700 56357998 700 701 137430169 701 702 631325059 702 703 132574512 703 704 793898130 704 705 224121563 705 706 119934684 706 707 505717181 707 708 220038778 708 709 141480319 709 710 32856690 710 711 838739383 711 712 762009707 712 713 278894370 713 714 665695573 714 715 686747329 715 716 875578412 716 717 295375180 717 718 19722905 718 719 316605787 719 720 940648664 720 721 996890079 721 722 156505822 722 723 576848036 723 724 875982454 724 725 418664361 725 726 192460923 726 727 337368640 727 728 695353142 728 729 69041688 729 730 29990983 730 731 366326356 731 732 132624458 732 733 33308173 733 734 684430595 734 735 891589038 735 736 635435103 736 737 495811529 737 738 419190119 738 739 665967106 739 740 522181047 740 741 584948424 741 742 613094991 742 743 622121957 743 744 359297564 744 745 693982818 745 746 561992545 746 747 34497828 747 748 150220138 748 749 144201327 749 750 844668755 750 751 696062897 751 752 581608165 752 753 646043620 753 754 467089041 754 755 12910126 755 756 163700795 756 757 46018929 757 758 730069719 758 759 855126886 759 760 100652291 760 761 268890330 761 762 72747798 762 763 105405069 763 764 850333698 764 765 394293630 765 766 315957200 766 767 572001382 767 768 730434166 768 769 148721397 769 770 201377006 770 771 992721956 771 772 537031287 772 773 271768336 773 774 180070320 774 775 669001336 775 776 876186928 776 777 146091487 777 778 520115948 778 779 896585802 779 780 5306750 780 781 776544665 781 782 541700101 782 783 404611702 783 784 731747615 784 785 218070720 785 786 588254103 786 787 63969458 787 788 885584448 788 789 239361307 789 790 713213833 790 791 796041143 791 792 320403412 792 793 137706960 793 794 435973827 794 795 97195317 795 796 13065421 796 797 669485820 797 798 59461190 798 799 485566147 799 800 712688826 800 801 746807377 801 802 846252400 802 803 670486211 803 804 766940339 804 805 873283690 805 806 220925670 806 807 181111727 807 808 118873922 808 809 362103668 809 810 110445457 810 811 36116619 811 812 839937775 812 813 352062954 813 814 367936313 814 815 35854970 815 816 787583847 816 817 527724920 817 818 409420653 818 819 357698888 819 820 36157953 820 821 836059114 821 822 163307510 822 823 343532683 823 824 267583164 824 825 767009536 825 826 150249019 826 827 596758927 827 828 172493177 828 829 142303168 829 830 790610949 830 831 156455102 831 832 699159554 832 833 776852472 833 834 502804702 834 835 24662940 835 836 643128024 836 837 585225693 837 838 170638326 838 839 548674733 839 840 461258491 840 841 479729179 841 842 603063514 842 843 592854647 843 844 798418413 844 845 711242309 845 846 117801814 846 847 54796546 847 848 20048500 848 849 4462796 849 850 800508147 850 851 303974680 851 852 597816723 852 853 115498965 853 854 578743913 854 855 816854634 855 856 643176715 856 857 575359393 857 858 486088565 858 859 731123513 859 860 101614692 860 861 783942062 861 862 246457333 862 863 498458483 863 864 250805158 864 865 397926002 865 866 747248028 866 867 69323630 867 868 591653225 868 869 37929273 869 870 18276444 870 871 529983347 871 872 909966160 872 873 809992337 873 874 906026408 874 875 254482947 875 876 332701121 876 877 101982041 877 878 724432552 878 879 444033172 879 880 427406261 880 881 645223877 881 882 736826390 882 883 392331097 883 884 946926879 884 885 875812478 885 886 634784696 886 887 595507770 887 888 933296118 888 889 914089958 889 890 53158266 890 891 224702179 891 892 539826657 892 893 387607417 893 894 123151399 894 895 608727032 895 896 142215294 896 897 833629007 897 898 577711044 898 899 795513190 899 900 576396367 900 901 33018814 901 902 809639305 902 903 692838357 903 904 610604610 904 905 676059932 905 906 382383485 906 907 543336250 907 908 683948508 908 909 858210210 909 910 748170157 910 911 522794120 911 912 25456641 912 913 214043500 913 914 416041224 914 915 648495238 915 916 771688034 916 917 747955674 917 918 993221564 918 919 381369219 919 920 26794399 920 921 627569123 921 922 190420871 922 923 708465512 923 924 765453331 924 925 553746508 925 926 64173276 926 927 761775589 927 928 724994761 928 929 264760669 929 930 170820830 930 931 279882325 931 932 639003783 932 933 45804967 933 934 193883899 934 935 483884671 935 936 343568748 936 937 588698331 937 938 489445631 938 939 609414614 939 940 11827821 940 941 531205196 941 942 969180016 942 943 319362557 943 944 990331367 944 945 973164137 945 946 970601541 946 947 974816751 947 948 527129404 948 949 947402462 949 950 932838084 950 951 706939181 951 952 235088381 952 953 108132110 953 954 729843506 954 955 518268977 955 956 88431280 956 957 394296467 957 958 644634779 958 959 128902470 959 960 134921023 960 961 856494741 961 962 533161676 962 963 245244785 963 964 131281683 964 965 788827076 965 966 845621278 966 967 134222835 967 968 109600917 968 969 924284170 969 970 131512117 970 971 584296073 971 972 923228650 972 973 533587808 973 974 349225422 974 975 843256599 975 976 147676692 976 977 315426183 977 978 403021361 978 979 95885772 979 980 444063588 980 981 563825405 981 982 546472555 982 983 568217454 983 984 628760052 984 985 580574204 985 986 425222242 986 987 28691423 987 988 98094781 988 989 766645124 989 990 961853980 990 991 521398761 991 992 617243541 992 993 530528327 993 994 62033502 994 995 369635027 995 996 515241046 996 997 960384905 997 998 267792613 998 999 959873302 999 1000 692417710 1000 1001 164597280 1001 1002 921696832 1002 1003 332384810 1003 1004 357900419 1004 1005 605518664 1005 1006 375382905 1006 1007 81070849 1007 1008 944149375 1008 1009 713255998 1009 1010 842752065 1010 1011 914452652 1011 1012 157972863 1012 1013 57928133 1013 1014 259060631 1014 1015 646001887 1015 1016 378928614 1016 1017 21689242 1017 1018 693138040 1018 1019 452914769 1019 1020 756531902 1020 1021 432648992 1021 1022 499068422 1022 1023 596479356 1023 1024 793489250 1024 1025 280192785 1025 1026 822982458 1026 1027 398992125 1027 1028 723114100 1028 1029 436207971 1029 1030 351636397 1030 1031 812375445 1031 1032 614072579 1032 1033 745775689 1033 1034 841331592 1034 1035 763213144 1035 1036 482742516 1036 1037 980601002 1037 1038 258603774 1038 1039 954198056 1039 1040 850597880 1040 1041 362612527 1041 1042 681946013 1042 1043 370912506 1043 1044 392957071 1044 1045 611474366 1045 1046 216547763 1046 1047 256446160 1047 1048 718906666 1048 1049 717185609 1049 1050 148107344 1050 1051 490862519 1051 1052 788980921 1052 1053 396830101 1053 1054 222152164 1054 1055 152131674 1055 1056 849661906 1056 1057 652277270 1057 1058 760832177 1058 1059 505507963 1059 1060 37575415 1060 1061 627423103 1061 1062 968839638 1062 1063 615955604 1063 1064 566587701 1064 1065 668341601 1065 1066 430187768 1066 1067 392357511 1067 1068 867177320 1068 1069 560287934 1069 1070 210235560 1070 1071 643675674 1071 1072 367805393 1072 1073 66547279 1073 1074 184839260 1074 1075 645765765 1075 1076 703871367 1076 1077 236383397 1077 1078 798734066 1078 1079 816478626 1079 1080 88514935 1080 1081 688481528 1081 1082 883489331 1082 1083 604427602 1083 1084 116189177 1084 1085 572381506 1085 1086 292943043 1086 1087 517126027 1087 1088 671984042 1088 1089 661679436 1089 1090 92983018 1090 1091 287912452 1091 1092 426095015 1092 1093 828495005 1093 1094 169338819 1094 1095 128760358 1095 1096 875231467 1096 1097 461768891 1097 1098 693458630 1098 1099 960257341 1099 1100 499057737 1100 1101 763338510 1101 1102 154841676 1102 1103 480704119 1103 1104 599216572 1104 1105 307822660 1105 1106 575944271 1106 1107 761529234 1107 1108 717059603 1108 1109 333922821 1109 1110 702336434 1110 1111 239390752 1111 1112 517367535 1112 1113 569173448 1113 1114 366015837 1114 1115 605016914 1115 1116 902647059 1116 1117 558276697 1117 1118 955024518 1118 1119 685195194 1119 1120 661920856 1120 1121 677262639 1121 1122 258829452 1122 1123 730308742 1123 1124 323855424 1124 1125 84014144 1125 1126 391708323 1126 1127 604448324 1127 1128 152240400 1128 1129 398632830 1129 1130 320026998 1130 1131 529218554 1131 1132 625286183 1132 1133 17338518 1133 1134 33707386 1134 1135 361472019 1135 1136 914124196 1136 1137 988626666 1137 1138 278234208 1138 1139 94928357 1139 1140 570605604 1140 1141 487076646 1141 1142 720748452 1142 1143 617570779 1143 1144 750965417 1144 1145 815729281 1145 1146 702225475 1146 1147 994255428 1147 1148 207350934 1148 1149 759463826 1149 1150 978977161 1150 1151 837208758 1151 1152 692152278 1152 1153 463916236 1153 1154 408646408 1154 1155 721270816 1155 1156 458854685 1156 1157 495876248 1157 1158 284443557 1158 1159 122328428 1159 1160 132642887 1160 1161 792235278 1161 1162 258983372 1162 1163 806959309 1163 1164 113455836 1164 1165 660736335 1165 1166 546567875 1166 1167 431803306 1167 1168 363592373 1168 1169 300173953 1169 1170 495378204 1170 1171 479400230 1171 1172 618286264 1172 1173 681483880 1173 1174 601321541 1174 1175 316534604 1175 1176 445286334 1176 1177 85238174 1177 1178 678022969 1178 1179 311629524 1179 1180 863454614 1180 1181 146033007 1181 1182 346778201 1182 1183 229643668 1183 1184 852135971 1184 1185 200757075 1185 1186 322915413 1186 1187 786679174 1187 1188 713803424 1188 1189 129951752 1189 1190 412510276 1190 1191 27929202 1191 1192 423410436 1192 1193 731404500 1193 1194 471638072 1194 1195 17464705 1195 1196 913125684 1196 1197 824876187 1197 1198 986916284 1198 1199 77510700 1199 1200 853088140 1200 1201 664973422 1201 1202 254458020 1202 1203 75434636 1203 1204 985757300 1204 1205 107799085 1205 1206 34522834 1206 1207 90099204 1207 1208 625948535 1208 1209 136198520 1209 1210 677264770 1210 1211 11169530 1211 1212 346913287 1212 1213 937838305 1213 1214 854528919 1214 1215 355951288 1215 1216 2132908 1216 1217 288629934 1217 1218 444443300 1218 1219 751755014 1219 1220 926693258 1220 1221 140312941 1221 1222 477413004 1222 1223 179833171 1223 1224 438107568 1224 1225 410123896 1225 1226 951656154 1226 1227 332389894 1227 1228 827579547 1228 1229 585167294 1229 1230 431234290 1230 1231 222779311 1231 1232 535778981 1232 1233 826590953 1233 1234 992193161 1234 1235 375647000 1235 1236 624173684 1236 1237 445150823 1237 1238 879883936 1238 1239 662683551 1239 1240 793793376 1240 1241 345296239 1241 1242 697570243 1242 1243 544965046 1243 1244 317932140 1244 1245 588129908 1245 1246 732621701 1246 1247 166122282 1247 1248 780935296 1248 1249 924657261 1249 1250 83876585 1250 1251 157088164 1251 1252 15857955 1252 1253 87445515 1253 1254 135823016 1254 1255 757419560 1255 1256 851438293 1256 1257 380207623 1257 1258 848892449 1258 1259 623426231 1259 1260 849168140 1260 1261 659712734 1261 1262 61593621 1262 1263 196167113 1263 1264 805753332 1264 1265 970344126 1265 1266 269735845 1266 1267 670673621 1267 1268 339968039 1268 1269 229535429 1269 1270 335458160 1270 1271 942150301 1271 1272 29112254 1272 1273 876047996 1273 1274 622540356 1274 1275 987009703 1275 1276 223681485 1276 1277 3255814 1277 1278 150170617 1278 1279 231845808 1279 1280 120433918 1280 1281 180740801 1281 1282 204232143 1282 1283 193231716 1283 1284 732211138 1284 1285 299344021 1285 1286 281910003 1286 1287 573899193 1287 1288 507419555 1288 1289 42511324 1289 1290 206228256 1290 1291 423161321 1291 1292 931050422 1292 1293 164797422 1293 1294 345946979 1294 1295 606885642 1295 1296 594093100 1296 1297 552213576 1297 1298 605951735 1298 1299 673345099 1299 1300 955259143 1300 1301 955398744 1301 1302 856611918 1302 1303 189240013 1303 1304 45227497 1304 1305 751794663 1305 1306 208889905 1306 1307 615746843 1307 1308 158401287 1308 1309 110927907 1309 1310 8376574 1310 1311 529922632 1311 1312 720373565 1312 1313 360445768 1313 1314 681210897 1314 1315 792441508 1315 1316 181595452 1316 1317 604527339 1317 1318 911180094 1318 1319 697039386 1319 1320 475684830 1320 1321 297580771 1321 1322 844570746 1322 1323 968632873 1323 1324 275069850 1324 1325 626132180 1325 1326 621544857 1326 1327 7792403 1327 1328 38929497 1328 1329 329318449 1329 1330 387493674 1330 1331 754895051 1331 1332 248673229 1332 1333 169157022 1333 1334 32875396 1334 1335 415487476 1335 1336 467417014 1336 1337 686351647 1337 1338 816593565 1338 1339 85986919 1339 1340 388720847 1340 1341 184895518 1341 1342 853656156 1342 1343 79822254 1343 1344 867580593 1344 1345 550802573 1345 1346 439109174 1346 1347 472003899 1347 1348 832028445 1348 1349 410258284 1349 1350 500940428 1350 1351 196117948 1351 1352 852294632 1352 1353 529699175 1353 1354 722947489 1354 1355 460301702 1355 1356 992159620 1356 1357 194657691 1357 1358 769592374 1358 1359 943871534 1359 1360 972680742 1360 1361 679410809 1361 1362 300202436 1362 1363 298890551 1363 1364 863938457 1364 1365 296334531 1365 1366 334630998 1366 1367 931896293 1367 1368 121765791 1368 1369 218390708 1369 1370 870586368 1370 1371 364227632 1371 1372 502547772 1372 1373 14474751 1373 1374 572948180 1374 1375 157264176 1375 1376 536795497 1376 1377 238018927 1377 1378 406448261 1378 1379 466428576 1379 1380 394058209 1380 1381 90141091 1381 1382 532683840 1382 1383 107951521 1383 1384 537780364 1384 1385 108826660 1385 1386 9973437 1386 1387 673319409 1387 1388 184602190 1388 1389 651974729 1389 1390 926610689 1390 1391 207871716 1391 1392 98838258 1392 1393 327159408 1393 1394 146707471 1394 1395 237105200 1395 1396 648143138 1396 1397 858821334 1397 1398 513173950 1398 1399 294416725 1399 1400 410474643 1400 1401 3523609 1401 1402 567303846 1402 1403 904597927 1403 1404 665358909 1404 1405 264889671 1405 1406 794157876 1406 1407 155433209 1407 1408 961365704 1408 1409 102697890 1409 1410 306758622 1410 1411 117637864 1411 1412 818750210 1412 1413 543911411 1413 1414 595450992 1414 1415 267268801 1415 1416 752794765 1416 1417 789202311 1417 1418 518301828 1418 1419 813187600 1419 1420 239214742 1420 1421 241361098 1421 1422 379879695 1422 1423 30073798 1423 1424 562919103 1424 1425 264652159 1425 1426 989392664 1426 1427 584833542 1427 1428 408439839 1428 1429 376247962 1429 1430 665158284 1430 1431 414191034 1431 1432 60520462 1432 1433 771175866 1433 1434 930238213 1434 1435 718618694 1435 1436 284873042 1436 1437 693732417 1437 1438 590843085 1438 1439 704387619 1439 1440 466729992 1440 1441 903087464 1441 1442 353157427 1442 1443 237706062 1443 1444 539803132 1444 1445 798736797 1445 1446 122903581 1446 1447 600000468 1447 1448 283686742 1448 1449 551633886 1449 1450 799908614 1450 1451 282726215 1451 1452 167005205 1452 1453 764192654 1453 1454 421648669 1454 1455 931620660 1455 1456 632808251 1456 1457 952677822 1457 1458 916124602 1458 1459 998568619 1459 1460 292668973 1460 1461 874053495 1461 1462 308946706 1462 1463 39279026 1463 1464 390559546 1464 1465 153542558 1465 1466 261632071 1466 1467 182134729 1467 1468 716968853 1468 1469 524049111 1469 1470 973088397 1470 1471 715573726 1471 1472 347957766 1472 1473 424633779 1473 1474 217875003 1474 1475 707409102 1475 1476 627533619 1476 1477 426830707 1477 1478 813648742 1478 1479 804579568 1479 1480 80382150 1480 1481 457581290 1481 1482 385765404 1482 1483 709845707 1483 1484 113787709 1484 1485 717590400 1485 1486 595636455 1486 1487 146209357 1487 1488 390704211 1488 1489 594005226 1489 1490 903770305 1490 1491 415522804 1491 1492 592425847 1492 1493 621646781 1493 1494 503048408 1494 1495 706712602 1495 1496 833598302 1496 1497 129125729 1497 1498 744251364 1498 1499 985425635 1499 1500 709072979 1500 1501 791996415 1501 1502 288916262 1502 1503 164867476 1503 1504 9662496 1504 1505 448726324 1505 1506 8675290 1506 1507 969012767 1507 1508 15806416 1508 1509 403257769 1509 1510 476293066 1510 1511 26818380 1511 1512 110039951 1512 1513 554497617 1513 1514 175040252 1514 1515 792546694 1515 1516 125854893 1516 1517 237478540 1517 1518 698787904 1518 1519 977172417 1519 1520 548427297 1520 1521 520367764 1521 1522 215858690 1522 1523 993920746 1523 1524 413621852 1524 1525 761101639 1525 1526 299708180 1526 1527 289379377 1527 1528 899825349 1528 1529 862775581 1529 1530 603759813 1530 1531 641003018 1531 1532 394803752 1532 1533 550680920 1533 1534 452745722 1534 1535 148576860 1535 1536 44136070 1536 1537 890314380 1537 1538 143245138 1538 1539 145263274 1539 1540 105509359 1540 1541 375092423 1541 1542 408689689 1542 1543 330259002 1543 1544 596861038 1544 1545 67588830 1545 1546 643392520 1546 1547 778121173 1547 1548 474789933 1548 1549 813508228 1549 1550 247368110 1550 1551 622913584 1551 1552 576148585 1552 1553 593068876 1553 1554 711139587 1554 1555 545695620 1555 1556 122744891 1556 1557 158838216 1557 1558 789665849 1558 1559 244492464 1559 1560 202077281 1560 1561 258761234 1561 1562 794649578 1562 1563 295557128 1563 1564 2377187 1564 1565 830002568 1565 1566 886202901 1566 1567 718648944 1567 1568 892768476 1568 1569 242025852 1569 1570 900511461 1570 1571 282397802 1571 1572 810856876 1572 1573 785716268 1573 1574 937434341 1574 1575 891648244 1575 1576 368444820 1576 1577 24027599 1577 1578 838873804 1578 1579 968843709 1579 1580 334402029 1580 1581 460377219 1581 1582 360797894 1582 1583 650830264 1583 1584 593787846 1584 1585 843614739 1585 1586 761819174 1586 1587 545527712 1587 1588 77926846 1588 1589 545018363 1589 1590 372602392 1590 1591 844749244 1591 1592 918685147 1592 1593 966563694 1593 1594 908543063 1594 1595 404036224 1595 1596 53841547 1596 1597 692031947 1597 1598 465632189 1598 1599 446970707 1599 1600 804845364 1600 1601 311107630 1601 1602 914046312 1602 1603 189991276 1603 1604 200429178 1604 1605 913766947 1605 1606 268141707 1606 1607 654267605 1607 1608 869698573 1608 1609 252745590 1609 1610 367172814 1610 1611 613256594 1611 1612 703266347 1612 1613 873833254 1613 1614 334215523 1614 1615 526726363 1615 1616 881238904 1616 1617 496857732 1617 1618 186953722 1618 1619 761164071 1619 1620 369037424 1620 1621 7561853 1621 1622 503756728 1622 1623 180779769 1623 1624 644655734 1624 1625 58571065 1625 1626 324981484 1626 1627 786312091 1627 1628 815539431 1628 1629 875094863 1629 1630 997650679 1630 1631 876029565 1631 1632 745191288 1632 1633 537414638 1633 1634 582261191 1634 1635 471959824 1635 1636 532841173 1636 1637 476455717 1637 1638 274372669 1638 1639 674287825 1639 1640 696873919 1640 1641 510254230 1641 1642 142028824 1642 1643 550479104 1643 1644 926179312 1644 1645 593615926 1645 1646 547648267 1646 1647 18328016 1647 1648 858991233 1648 1649 951338285 1649 1650 758161870 1650 1651 716909730 1651 1652 932557927 1652 1653 802674535 1653 1654 314148541 1654 1655 116967011 1655 1656 135377558 1656 1657 753064359 1657 1658 251022796 1658 1659 130136650 1659 1660 953923451 1660 1661 818214409 1661 1662 715888097 1662 1663 433030921 1663 1664 737135999 1664 1665 249831650 1665 1666 200315598 1666 1667 988095773 1667 1668 97841020 1668 1669 562401560 1669 1670 887302104 1670 1671 482997771 1671 1672 586509010 1672 1673 862213786 1673 1674 550889305 1674 1675 928392340 1675 1676 284941006 1676 1677 670149571 1677 1678 266030024 1678 1679 823287588 1679 1680 162754738 1680 1681 623525382 1681 1682 806730488 1682 1683 373210241 1683 1684 71104933 1684 1685 115144491 1685 1686 336600201 1686 1687 410345769 1687 1688 173908118 1688 1689 340716322 1689 1690 236731094 1690 1691 180658744 1691 1692 308401487 1692 1693 380812323 1693 1694 498696609 1694 1695 967466547 1695 1696 604882972 1696 1697 50596407 1697 1698 439400175 1698 1699 205663129 1699 1700 684547554 1700 1701 625818489 1701 1702 24899536 1702 1703 848037493 1703 1704 751751058 1704 1705 611942299 1705 1706 260097745 1706 1707 440261541 1707 1708 807919896 1708 1709 593590137 1709 1710 421411177 1710 1711 640655322 1711 1712 6734030 1712 1713 638653329 1713 1714 322115452 1714 1715 386955809 1715 1716 85066812 1716 1717 606325409 1717 1718 195744489 1718 1719 963390733 1719 1720 652009726 1720 1721 917932510 1721 1722 109104704 1722 1723 215195779 1723 1724 104504771 1724 1725 511415502 1725 1726 995720337 1726 1727 292478498 1727 1728 957965169 1728 1729 295224003 1729 1730 243930207 1730 1731 679539276 1731 1732 422009446 1732 1733 814242292 1733 1734 604399540 1734 1735 108772822 1735 1736 823363546 1736 1737 268522553 1737 1738 672664910 1738 1739 557604424 1739 1740 772280672 1740 1741 48424802 1741 1742 935012087 1742 1743 987840721 1743 1744 356851851 1744 1745 152058165 1745 1746 420597490 1746 1747 658328522 1747 1748 748717229 1748 1749 595492099 1749 1750 236646545 1750 1751 510793957 1751 1752 250479846 1752 1753 735821284 1753 1754 928400882 1754 1755 979303244 1755 1756 416338073 1756 1757 671048332 1757 1758 993859149 1758 1759 551568064 1759 1760 47228404 1760 1761 230496173 1761 1762 585008872 1762 1763 41340286 1763 1764 742024450 1764 1765 974283010 1765 1766 405679857 1766 1767 214922837 1767 1768 871921089 1768 1769 104855818 1769 1770 340708127 1770 1771 279101188 1771 1772 515881845 1772 1773 357667936 1773 1774 768347550 1774 1775 115903701 1775 1776 54636969 1776 1777 39766056 1777 1778 309010069 1778 1779 391696739 1779 1780 487674563 1780 1781 180589477 1781 1782 587022672 1782 1783 867547517 1783 1784 725154883 1784 1785 805355240 1785 1786 158938639 1786 1787 589937187 1787 1788 718517912 1788 1789 714942627 1789 1790 82389610 1790 1791 891932319 1791 1792 581097244 1792 1793 142166111 1793 1794 129301771 1794 1795 85468345 1795 1796 423296061 1796 1797 731302394 1797 1798 835538727 1798 1799 354021767 1799 1800 265751752 1800 1801 21593703 1801 1802 982933572 1802 1803 979124903 1803 1804 46334542 1804 1805 999462592 1805 1806 957774945 1806 1807 428284021 1807 1808 383102274 1808 1809 806946217 1809 1810 32003460 1810 1811 290576488 1811 1812 61190216 1812 1813 24186129 1813 1814 656008107 1814 1815 47415389 1815 1816 367871196 1816 1817 610226220 1817 1818 604106716 1818 1819 424556784 1819 1820 720421286 1820 1821 885683956 1821 1822 718646059 1822 1823 17085930 1823 1824 504989477 1824 1825 345376372 1825 1826 219207903 1826 1827 263607628 1827 1828 615483708 1828 1829 942894061 1829 1830 778288741 1830 1831 384774353 1831 1832 613368207 1832 1833 128836508 1833 1834 697124430 1834 1835 403634402 1835 1836 655804255 1836 1837 456745261 1837 1838 774313133 1838 1839 719074849 1839 1840 292676788 1840 1841 329681568 1841 1842 606763337 1842 1843 227627558 1843 1844 940742473 1844 1845 571999614 1845 1846 496757561 1846 1847 582623559 1847 1848 105100529 1848 1849 241602480 1849 1850 353122158 1850 1851 335059888 1851 1852 992019739 1852 1853 990718573 1853 1854 555957901 1854 1855 58117287 1855 1856 224990305 1856 1857 630673182 1857 1858 169026906 1858 1859 448130410 1859 1860 530204668 1860 1861 882050154 1861 1862 297954331 1862 1863 521409378 1863 1864 975069736 1864 1865 692713709 1865 1866 664402247 1866 1867 518510089 1867 1868 85125374 1868 1869 983601808 1869 1870 165240340 1870 1871 911743306 1871 1872 453301659 1872 1873 171353055 1873 1874 661284103 1874 1875 576640097 1875 1876 252171661 1876 1877 274595775 1877 1878 297156753 1878 1879 499062719 1879 1880 445305560 1880 1881 426089843 1881 1882 953375588 1882 1883 753747603 1883 1884 541800106 1884 1885 565465779 1885 1886 156985104 1886 1887 599930776 1887 1888 975133111 1888 1889 253776796 1889 1890 325285621 1890 1891 83400936 1891 1892 979257677 1892 1893 311437891 1893 1894 282320417 1894 1895 937741256 1895 1896 987216929 1896 1897 380947129 1897 1898 464695550 1898 1899 20776571 1899 1900 142738137 1900 1901 429704072 1901 1902 664693137 1902 1903 773549068 1903 1904 362830439 1904 1905 881759830 1905 1906 834825759 1906 1907 444343409 1907 1908 178616409 1908 1909 374933598 1909 1910 705821336 1910 1911 785995124 1911 1912 223314912 1912 1913 51731380 1913 1914 85198769 1914 1915 997721796 1915 1916 561262973 1916 1917 743417510 1917 1918 963708710 1918 1919 977348723 1919 1920 905159881 1920 1921 553903579 1921 1922 155758094 1922 1923 967921632 1923 1924 203874850 1924 1925 907476927 1925 1926 146992486 1926 1927 736704565 1927 1928 777856895 1928 1929 233213549 1929 1930 643227788 1930 1931 13584584 1931 1932 881096021 1932 1933 707245496 1933 1934 703276029 1934 1935 673816845 1935 1936 345323398 1936 1937 656277998 1937 1938 952305646 1938 1939 843648987 1939 1940 1892192 1940 1941 376220473 1941 1942 683008840 1942 1943 959796362 1943 1944 238134379 1944 1945 552811999 1945 1946 591854395 1946 1947 629629343 1947 1948 839529638 1948 1949 329544823 1949 1950 669070827 1950 1951 754104770 1951 1952 822800124 1952 1953 677593721 1953 1954 682347303 1954 1955 114883670 1955 1956 339383134 1956 1957 212547412 1957 1958 270735802 1958 1959 271728839 1959 1960 424946803 1960 1961 366219368 1961 1962 5819676 1962 1963 886023277 1963 1964 259518784 1964 1965 377056757 1965 1966 92224336 1966 1967 555463311 1967 1968 804087076 1968 1969 484158210 1969 1970 169000728 1970 1971 118128555 1971 1972 629910091 1972 1973 61664983 1973 1974 341410127 1974 1975 113053952 1975 1976 215553914 1976 1977 91384279 1977 1978 29955064 1978 1979 26118929 1979 1980 836081628 1980 1981 793147053 1981 1982 933653976 1982 1983 513651787 1983 1984 534836615 1984 1985 161142057 1985 1986 71452822 1986 1987 991810567 1987 1988 580098382 1988 1989 735796911 1989 1990 631102910 1990 1991 844453541 1991 1992 357766465 1992 1993 851281953 1993 1994 171780376 1994 1995 135786680 1995 1996 216353186 1996 1997 621764654 1997 1998 888359511 1998 1999 140256854 1999 2000 182041993 2000 2001 178036703 2001 2002 269564714 2002 2003 75960393 2003 2004 694447790 2004 2005 683905488 2005 2006 207326876 2006 2007 217299463 2007 2008 173545367 2008 2009 164288343 2009 2010 63981389 2010 2011 245599204 2011 2012 970118245 2012 2013 921049716 2013 2014 355467754 2014 2015 635193505 2015 2016 845172500 2016 2017 353534363 2017 2018 89905199 2018 2019 813295719 2019 2020 727323425 2020 2021 66312028 2021 2022 487784709 2022 2023 353236840 2023 2024 317984104 2024 2025 337102370 2025 2026 82982614 2026 2027 996901855 2027 2028 628331241 2028 2029 996218297 2029 2030 19790671 2030 2031 868897456 2031 2032 504824855 2032 2033 697800113 2033 2034 913719228 2034 2035 367990226 2035 2036 901021312 2036 2037 146988261 2037 2038 763620554 2038 2039 960788456 2039 2040 433721695 2040 2041 263449001 2041 2042 701283431 2042 2043 924317054 2043 2044 425219919 2044 2045 155735183 2045 2046 146666437 2046 2047 47032289 2047 2048 118605594 2048 2049 482777558 2049 2050 572905342 2050 2051 336280987 2051 2052 347419504 2052 2053 236627922 2053 2054 891779209 2054 2055 607202099 2055 2056 249268655 2056 2057 877383947 2057 2058 606515099 2058 2059 384757551 2059 2060 792203 2060 2061 693682177 2061 2062 500174888 2062 2063 145171431 2063 2064 409413010 2064 2065 501470906 2065 2066 912475372 2066 2067 645554890 2067 2068 133853804 2068 2069 638392617 2069 2070 650798239 2070 2071 390607877 2071 2072 827977226 2072 2073 208783383 2073 2074 921952818 2074 2075 283590962 2075 2076 203459691 2076 2077 813919263 2077 2078 44699816 2078 2079 155085102 2079 2080 537547531 2080 2081 129684111 2081 2082 544003560 2082 2083 160609277 2083 2084 464103195 2084 2085 405493780 2085 2086 150734592 2086 2087 88972509 2087 2088 896503072 2088 2089 710686094 2089 2090 370668636 2090 2091 975204901 2091 2092 183016126 2092 2093 972976391 2093 2094 295658319 2094 2095 244410609 2095 2096 615155392 2096 2097 3236498 2097 2098 398483353 2098 2099 64332944 2099 2100 225277634 2100 2101 999343163 2101 2102 332637529 2102 2103 230549719 2103 2104 371425761 2104 2105 707224339 2105 2106 876800255 2106 2107 83705226 2107 2108 816187116 2108 2109 731498451 2109 2110 727603226 2110 2111 336948077 2111 2112 498769847 2112 2113 795680618 2113 2114 304029488 2114 2115 187655823 2115 2116 111188191 2116 2117 265317079 2117 2118 680015098 2118 2119 727267199 2119 2120 403707445 2120 2121 627061954 2121 2122 137356602 2122 2123 936366496 2123 2124 685492418 2124 2125 259900449 2125 2126 760925109 2126 2127 514708808 2127 2128 45560061 2128 2129 725361358 2129 2130 909282076 2130 2131 898956657 2131 2132 19168079 2132 2133 203911105 2133 2134 53757217 2134 2135 656533399 2135 2136 782409732 2136 2137 122060408 2137 2138 390817843 2138 2139 383621935 2139 2140 207336992 2140 2141 954390285 2141 2142 123920675 2142 2143 844013010 2143 2144 653155037 2144 2145 304697128 2145 2146 721179882 2146 2147 382145206 2147 2148 739917125 2148 2149 856738064 2149 2150 600029685 2150 2151 648542103 2151 2152 509494268 2152 2153 795566481 2153 2154 241714553 2154 2155 218012627 2155 2156 257862413 2156 2157 489743038 2157 2158 869072005 2158 2159 826370106 2159 2160 44754031 2160 2161 135458965 2161 2162 219182815 2162 2163 644100383 2163 2164 540007234 2164 2165 137074869 2165 2166 485087319 2166 2167 890102952 2167 2168 682757932 2168 2169 128811399 2169 2170 789951327 2170 2171 921077822 2171 2172 939350638 2172 2173 730911533 2173 2174 86413213 2174 2175 230331958 2175 2176 342882915 2176 2177 296789383 2177 2178 885154495 2178 2179 455287059 2179 2180 785126039 2180 2181 821871682 2181 2182 60584256 2182 2183 494972671 2183 2184 211048341 2184 2185 241755103 2185 2186 858131721 2186 2187 451274444 2187 2188 299778893 2188 2189 297093691 2189 2190 151493684 2190 2191 30790277 2191 2192 706534066 2192 2193 600974265 2193 2194 790537195 2194 2195 657722465 2195 2196 256167694 2196 2197 255583599 2197 2198 164754724 2198 2199 887697531 2199 2200 294886312 2200 2201 337859381 2201 2202 4052097 2202 2203 461870483 2203 2204 882467004 2204 2205 115640363 2205 2206 345510735 2206 2207 40524995 2207 2208 562185962 2208 2209 76363032 2209 2210 717808567 2210 2211 633599193 2211 2212 134097040 2212 2213 81361441 2213 2214 827755736 2214 2215 589978799 2215 2216 118315688 2216 2217 456116327 2217 2218 755451079 2218 2219 373651608 2219 2220 40236494 2220 2221 216150262 2221 2222 510721843 2222 2223 457094361 2223 2224 62155103 2224 2225 300225001 2225 2226 680962225 2226 2227 375800190 2227 2228 557970466 2228 2229 357904198 2229 2230 88015172 2230 2231 469649064 2231 2232 549907157 2232 2233 601378674 2233 2234 351244682 2234 2235 929500220 2235 2236 181554381 2236 2237 34007368 2237 2238 838064611 2238 2239 433532549 2239 2240 494231705 2240 2241 858609821 2241 2242 428112921 2242 2243 207926756 2243 2244 391857288 2244 2245 802029201 2245 2246 948776145 2246 2247 800846819 2247 2248 603288295 2248 2249 754836609 2249 2250 852652300 2250 2251 661383330 2251 2252 242261266 2252 2253 592354927 2253 2254 875102080 2254 2255 208150859 2255 2256 691904038 2256 2257 935840278 2257 2258 217776434 2258 2259 77828217 2259 2260 465240993 2260 2261 765640977 2261 2262 79225605 2262 2263 704397012 2263 2264 418508614 2264 2265 451560146 2265 2266 250690716 2266 2267 838455036 2267 2268 801616664 2268 2269 949889879 2269 2270 94196280 2270 2271 902942260 2271 2272 255960107 2272 2273 833537214 2273 2274 622836336 2274 2275 619375551 2275 2276 895555443 2276 2277 131615317 2277 2278 358853639 2278 2279 346066647 2279 2280 736367015 2280 2281 59307982 2281 2282 31559033 2282 2283 63416129 2283 2284 754557983 2284 2285 33801355 2285 2286 571359690 2286 2287 220567202 2287 2288 365224440 2288 2289 458198209 2289 2290 924147237 2290 2291 153983569 2291 2292 817264610 2292 2293 432777666 2293 2294 332095844 2294 2295 628309489 2295 2296 26116004 2296 2297 717330948 2297 2298 14458359 2298 2299 733356837 2299 2300 162377391 2300 2301 340130399 2301 2302 301898201 2302 2303 751176291 2303 2304 232333701 2304 2305 165799139 2305 2306 717433671 2306 2307 381302539 2307 2308 130818523 2308 2309 975159658 2309 2310 114100688 2310 2311 159699765 2311 2312 790385492 2312 2313 150215514 2313 2314 658207575 2314 2315 643159437 2315 2316 368267092 2316 2317 199531032 2317 2318 758911799 2318 2319 179324616 2319 2320 776403443 2320 2321 846038538 2321 2322 987262658 2322 2323 659762702 2323 2324 987063878 2324 2325 940610144 2325 2326 216206134 2326 2327 101738103 2327 2328 254543580 2328 2329 986942878 2329 2330 154663961 2330 2331 367367100 2331 2332 935977535 2332 2333 796526995 2333 2334 364239973 2334 2335 140939334 2335 2336 465515083 2336 2337 525655451 2337 2338 129013735 2338 2339 719162221 2339 2340 152758954 2340 2341 928883702 2341 2342 873112198 2342 2343 423568679 2343 2344 66118955 2344 2345 407782023 2345 2346 424550067 2346 2347 593745559 2347 2348 767459022 2348 2349 316419667 2349 2350 883905766 2350 2351 639047443 2351 2352 5827015 2352 2353 622607847 2353 2354 761225364 2354 2355 559031392 2355 2356 977891830 2356 2357 937525720 2357 2358 622987512 2358 2359 501900400 2359 2360 675841734 2360 2361 510255125 2361 2362 867056385 2362 2363 552772098 2363 2364 362329123 2364 2365 424668757 2365 2366 316892634 2366 2367 341800804 2367 2368 985173273 2368 2369 75959214 2369 2370 207581203 2370 2371 746015064 2371 2372 83901450 2372 2373 446499143 2373 2374 873352561 2374 2375 130916885 2375 2376 783099532 2376 2377 264555558 2377 2378 38953807 2378 2379 401162340 2379 2380 993915427 2380 2381 55549163 2381 2382 192750851 2382 2383 957051902 2383 2384 994805473 2384 2385 749606279 2385 2386 739955077 2386 2387 188735116 2387 2388 584184270 2388 2389 717465810 2389 2390 848957375 2390 2391 895159564 2391 2392 225076961 2392 2393 403382212 2393 2394 792795110 2394 2395 854112407 2395 2396 927066003 2396 2397 965473141 2397 2398 138353305 2398 2399 547279030 2399 2400 877698194 2400 2401 35358976 2401 2402 942055455 2402 2403 562383118 2403 2404 419171716 2404 2405 25829187 2405 2406 925692470 2406 2407 154034080 2407 2408 550340676 2408 2409 590563753 2409 2410 244746071 2410 2411 410265838 2411 2412 315515532 2412 2413 794815191 2413 2414 848659807 2414 2415 190827513 2415 2416 409598261 2416 2417 561907030 2417 2418 247182544 2418 2419 253454631 2419 2420 610750874 2420 2421 365996597 2421 2422 731483153 2422 2423 666668586 2423 2424 892617392 2424 2425 976171121 2425 2426 221749607 2426 2427 400113507 2427 2428 830871343 2428 2429 973253249 2429 2430 245295134 2430 2431 697631429 2431 2432 734621633 2432 2433 744204 2433 2434 641757266 2434 2435 735503576 2435 2436 377500902 2436 2437 755088571 2437 2438 623068506 2438 2439 473939418 2439 2440 434740839 2440 2441 928075048 2441 2442 980749522 2442 2443 668994304 2443 2444 206839924 2444 2445 224518901 2445 2446 655297092 2446 2447 62023642 2447 2448 873277532 2448 2449 666765562 2449 2450 870959986 2450 2451 75050964 2451 2452 383943401 2452 2453 490167446 2453 2454 285730627 2454 2455 387245016 2455 2456 757282390 2456 2457 405586726 2457 2458 326655816 2458 2459 919314961 2459 2460 821357038 2460 2461 734986900 2461 2462 296918505 2462 2463 892915659 2463 2464 999231299 2464 2465 275736839 2465 2466 834925360 2466 2467 998640568 2467 2468 403103794 2468 2469 704704713 2469 2470 405099402 2470 2471 958536421 2471 2472 685659413 2472 2473 421390596 2473 2474 593113808 2474 2475 42848478 2475 2476 467891139 2476 2477 740275533 2477 2478 440991822 2478 2479 675179068 2479 2480 143806762 2480 2481 233105212 2481 2482 242626353 2482 2483 987390765 2483 2484 174102386 2484 2485 721407148 2485 2486 154094075 2486 2487 560878890 2487 2488 339790948 2488 2489 367048172 2489 2490 691519603 2490 2491 455103784 2491 2492 453750582 2492 2493 616751353 2493 2494 582864578 2494 2495 613938077 2495 2496 447498434 2496 2497 367809851 2497 2498 726250290 2498 2499 504523738 2499 2500 559489030 2500 2501 499504930 2501 2502 721347860 2502 2503 612734686 2503 2504 272228276 2504 2505 441143060 2505 2506 226346000 2506 2507 827250270 2507 2508 598343136 2508 2509 686079850 2509 2510 779423684 2510 2511 293043767 2511 2512 979000588 2512 2513 261586049 2513 2514 618507677 2514 2515 153546116 2515 2516 968224307 2516 2517 795239170 2517 2518 188490811 2518 2519 326715809 2519 2520 927720208 2520 2521 849799722 2521 2522 566634808 2522 2523 550509057 2523 2524 778823181 2524 2525 678962207 2525 2526 819788566 2526 2527 104495917 2527 2528 846784008 2528 2529 109499207 2529 2530 758707376 2530 2531 655211045 2531 2532 935485379 2532 2533 633673331 2533 2534 944741172 2534 2535 175989276 2535 2536 74548575 2536 2537 868600190 2537 2538 317950432 2538 2539 928574635 2539 2540 555102630 2540 2541 898406351 2541 2542 207953757 2542 2543 276248360 2543 2544 312365045 2544 2545 177566971 2545 2546 876242612 2546 2547 332540178 2547 2548 417531588 2548 2549 877982599 2549 2550 179612067 2550 2551 220210388 2551 2552 361456075 2552 2553 502209619 2553 2554 40424584 2554 2555 515986164 2555 2556 404397297 2556 2557 179965996 2557 2558 188810157 2558 2559 734317167 2559 2560 45486109 2560 2561 485159516 2561 2562 965228593 2562 2563 123376661 2563 2564 284133799 2564 2565 214570340 2565 2566 675241081 2566 2567 114805220 2567 2568 203147395 2568 2569 801287721 2569 2570 277007713 2570 2571 120918868 2571 2572 33807298 2572 2573 739401288 2573 2574 419629196 2574 2575 956932657 2575 2576 810230288 2576 2577 949463516 2577 2578 895707748 2578 2579 43466271 2579 2580 147897376 2580 2581 484479485 2581 2582 211819432 2582 2583 93673789 2583 2584 629713054 2584 2585 808358428 2585 2586 710075589 2586 2587 280214174 2587 2588 868858897 2588 2589 668645558 2589 2590 796153539 2590 2591 628593116 2591 2592 681705867 2592 2593 297247999 2593 2594 127601245 2594 2595 127923800 2595 2596 480560305 2596 2597 673204180 2597 2598 672379819 2598 2599 984575628 2599 2600 588155588 2600 2601 566512102 2601 2602 936876032 2602 2603 90102668 2603 2604 757212219 2604 2605 840556554 2605 2606 484338148 2606 2607 948911979 2607 2608 787378134 2608 2609 800478677 2609 2610 625201644 2610 2611 647763933 2611 2612 389310515 2612 2613 34980544 2613 2614 817329774 2614 2615 886283904 2615 2616 614995445 2616 2617 596403335 2617 2618 143784537 2618 2619 542212171 2619 2620 42135339 2620 2621 138981894 2621 2622 953932406 2622 2623 689244533 2623 2624 277116026 2624 2625 586790436 2625 2626 510285126 2626 2627 494940002 2627 2628 164765466 2628 2629 760439706 2629 2630 546624720 2630 2631 709621486 2631 2632 90158012 2632 2633 290631480 2633 2634 932033044 2634 2635 529760438 2635 2636 884341401 2636 2637 47775811 2637 2638 425851148 2638 2639 720442834 2639 2640 168862269 2640 2641 941569993 2641 2642 122614820 2642 2643 155459094 2643 2644 889530233 2644 2645 644897527 2645 2646 309948434 2646 2647 949583512 2647 2648 449235057 2648 2649 192053763 2649 2650 255664299 2650 2651 472815534 2651 2652 519146806 2652 2653 889231978 2653 2654 276667361 2654 2655 153183963 2655 2656 741531837 2656 2657 220367554 2657 2658 327468276 2658 2659 705070322 2659 2660 73780902 2660 2661 945878919 2661 2662 506875120 2662 2663 700426094 2663 2664 280862856 2664 2665 237543180 2665 2666 833697613 2666 2667 221031279 2667 2668 912932455 2668 2669 343921149 2669 2670 868149428 2670 2671 892410450 2671 2672 504886850 2672 2673 726509196 2673 2674 643210209 2674 2675 746985963 2675 2676 865656009 2676 2677 639418944 2677 2678 683974819 2678 2679 818186028 2679 2680 445484118 2680 2681 93532929 2681 2682 726668711 2682 2683 890614799 2683 2684 831406291 2684 2685 561790583 2685 2686 465365651 2686 2687 482428314 2687 2688 53599783 2688 2689 805792093 2689 2690 303584156 2690 2691 648013695 2691 2692 528444009 2692 2693 765022517 2693 2694 352829743 2694 2695 237519272 2695 2696 932401227 2696 2697 508878784 2697 2698 705405318 2698 2699 345346203 2699 2700 775580534 2700 2701 412861745 2701 2702 943010083 2702 2703 198588841 2703 2704 96264768 2704 2705 920735798 2705 2706 396383300 2706 2707 721473437 2707 2708 423025482 2708 2709 196698752 2709 2710 430635367 2710 2711 407983057 2711 2712 154111173 2712 2713 84333894 2713 2714 653126051 2714 2715 605495327 2715 2716 864951134 2716 2717 768613472 2717 2718 564351432 2718 2719 39591546 2719 2720 549840305 2720 2721 592494705 2721 2722 372038188 2722 2723 752775613 2723 2724 201781156 2724 2725 81867419 2725 2726 250962006 2726 2727 96302945 2727 2728 417994981 2728 2729 198976731 2729 2730 824639741 2730 2731 237330414 2731 2732 824639984 2732 2733 328156634 2733 2734 155638690 2734 2735 728106858 2735 2736 977324931 2736 2737 973714294 2737 2738 166261873 2738 2739 396087017 2739 2740 548502207 2740 2741 549766109 2741 2742 220688158 2742 2743 905979070 2743 2744 373414225 2744 2745 169999253 2745 2746 272261078 2746 2747 625620589 2747 2748 535946884 2748 2749 491609783 2749 2750 141821185 2750 2751 877999953 2751 2752 999387985 2752 2753 637731985 2753 2754 525783705 2754 2755 408448528 2755 2756 797466661 2756 2757 130364871 2757 2758 682068144 2758 2759 841778221 2759 2760 696448924 2760 2761 953072685 2761 2762 344870483 2762 2763 403620846 2763 2764 520579004 2764 2765 572419189 2765 2766 668878411 2766 2767 428856415 2767 2768 39955656 2768 2769 260226306 2769 2770 693390480 2770 2771 609122159 2771 2772 394389442 2772 2773 402147803 2773 2774 668841035 2774 2775 217220663 2775 2776 616893057 2776 2777 196635067 2777 2778 627040902 2778 2779 467044187 2779 2780 751236165 2780 2781 52793203 2781 2782 267065225 2782 2783 30158030 2783 2784 989292372 2784 2785 128738902 2785 2786 495931935 2786 2787 447325152 2787 2788 878838129 2788 2789 102299151 2789 2790 635365713 2790 2791 621752670 2791 2792 817308232 2792 2793 590658055 2793 2794 890125706 2794 2795 409412815 2795 2796 799925559 2796 2797 709527789 2797 2798 809836165 2798 2799 613574200 2799 2800 915871248 2800 2801 825736069 2801 2802 14581065 2802 2803 760886209 2803 2804 550416907 2804 2805 391162991 2805 2806 35622144 2806 2807 377416535 2807 2808 656006669 2808 2809 373789544 2809 2810 472722870 2810 2811 441888502 2811 2812 952767176 2812 2813 324190384 2813 2814 382909822 2814 2815 463020678 2815 2816 9014565 2816 2817 860693607 2817 2818 827789036 2818 2819 920644886 2819 2820 811141664 2820 2821 784573190 2821 2822 737388269 2822 2823 764336914 2823 2824 658116905 2824 2825 295345749 2825 2826 836705965 2826 2827 646517622 2827 2828 280639409 2828 2829 616002071 2829 2830 993924894 2830 2831 787110565 2831 2832 535902533 2832 2833 487474453 2833 2834 135422793 2834 2835 811470563 2835 2836 232863980 2836 2837 122533534 2837 2838 155093176 2838 2839 411452994 2839 2840 27246845 2840 2841 384290163 2841 2842 684329867 2842 2843 349114899 2843 2844 322862557 2844 2845 753244616 2845 2846 531657613 2846 2847 976582697 2847 2848 13953851 2848 2849 99275415 2849 2850 217770780 2850 2851 657117354 2851 2852 62652278 2852 2853 664750129 2853 2854 769719532 2854 2855 339371211 2855 2856 71103266 2856 2857 226209628 2857 2858 385319788 2858 2859 533334643 2859 2860 965724810 2860 2861 587042330 2861 2862 713829157 2862 2863 792655018 2863 2864 637655102 2864 2865 183326976 2865 2866 941826669 2866 2867 457854832 2867 2868 889475537 2868 2869 948625466 2869 2870 598638845 2870 2871 758805485 2871 2872 582637555 2872 2873 389149206 2873 2874 533064976 2874 2875 256551083 2875 2876 31970086 2876 2877 538274240 2877 2878 75779823 2878 2879 601921360 2879 2880 970115930 2880 2881 675098062 2881 2882 642668312 2882 2883 84796041 2883 2884 694194471 2884 2885 209159670 2885 2886 374862090 2886 2887 405957123 2887 2888 526461606 2888 2889 104962527 2889 2890 729215664 2890 2891 320479891 2891 2892 364449773 2892 2893 501418772 2893 2894 84604007 2894 2895 510280822 2895 2896 911592229 2896 2897 236160533 2897 2898 960134062 2898 2899 212285362 2899 2900 795200073 2900 2901 965487752 2901 2902 562552937 2902 2903 494824572 2903 2904 78594701 2904 2905 20784850 2905 2906 302048369 2906 2907 707340039 2907 2908 451305775 2908 2909 882099197 2909 2910 380395559 2910 2911 820501487 2911 2912 556385782 2912 2913 750779653 2913 2914 586897727 2914 2915 972484655 2915 2916 484016848 2916 2917 946196887 2917 2918 540172752 2918 2919 792999580 2919 2920 125213865 2920 2921 293945409 2921 2922 16287816 2922 2923 339010749 2923 2924 212375979 2924 2925 903294640 2925 2926 696306837 2926 2927 298197923 2927 2928 378529142 2928 2929 350572528 2929 2930 448071350 2930 2931 623071200 2931 2932 882086522 2932 2933 339333591 2933 2934 525410240 2934 2935 367675140 2935 2936 857930168 2936 2937 432701528 2937 2938 492420093 2938 2939 234221037 2939 2940 490038949 2940 2941 967588467 2941 2942 585112437 2942 2943 741195864 2943 2944 265230712 2944 2945 596386049 2945 2946 231672615 2946 2947 210873415 2947 2948 92326522 2948 2949 652641510 2949 2950 59387482 2950 2951 444389369 2951 2952 181414683 2952 2953 329214684 2953 2954 463976422 2954 2955 980488021 2955 2956 889252694 2956 2957 638723944 2957 2958 960343726 2958 2959 972440408 2959 2960 555325473 2960 2961 667185729 2961 2962 213243618 2962 2963 340045523 2963 2964 575064379 2964 2965 127732464 2965 2966 879767541 2966 2967 277571177 2967 2968 249053024 2968 2969 849654421 2969 2970 373595216 2970 2971 371483124 2971 2972 123149143 2972 2973 181823481 2973 2974 695865451 2974 2975 395215434 2975 2976 557093345 2976 2977 313350978 2977 2978 375798541 2978 2979 273604715 2979 2980 884599925 2980 2981 7918399 2981 2982 562933225 2982 2983 621746311 2983 2984 155220518 2984 2985 662156067 2985 2986 734796613 2986 2987 400587552 2987 2988 67429827 2988 2989 977020865 2989 2990 613912741 2990 2991 205682888 2991 2992 411252858 2992 2993 779407238 2993 2994 241723039 2994 2995 535514926 2995 2996 589963895 2996 2997 872563115 2997 2998 65026207 2998 2999 520452853 2999 3000 116715354