1000 2000 830 904 737041445 774 817 54540096 479 493 891822207 350 373 945557505 232 316 471512393 8 173 473739402 778 995 727237022 671 946 747927524 221 387 42873962 371 433 650100606 804 875 660882102 639 647 582831011 346 370 315406879 744 870 964207424 117 340 31719726 109 221 738217020 439 474 980003788 6 138 637728399 25 202 127905773 152 242 929800778 104 425 876234341 174 496 501646116 822 915 213886088 167 481 73829699 373 430 77305634 837 982 240702533 568 810 112409323 328 492 350283326 980 994 893229962 74 470 619116200 788 820 662265471 679 971 221790487 38 359 149953471 749 974 553154427 147 357 111862615 872 912 13403436 545 671 13232454 718 764 874204871 55 250 412567430 110 481 889806169 215 468 199780592 23 321 292442076 115 329 782394079 408 436 735602264 643 973 344450818 95 296 264207903 108 181 207316611 746 776 309582826 141 393 901974176 513 971 544123461 187 440 112813926 814 965 575897282 534 614 299701950 209 351 285430550 690 734 734112719 716 868 898801205 546 620 922930009 316 424 967616842 143 425 607916109 907 997 266514085 573 617 904618279 438 461 736219861 270 464 330435765 629 650 671360278 588 923 635122108 600 947 820167492 535 581 139586782 788 802 91498408 39 60 469646051 760 965 773672304 199 265 895861885 337 426 600688813 715 816 463010791 602 782 555130744 183 233 348105463 160 213 621799587 129 322 641955831 805 917 58934617 9 46 18604537 98 428 369839283 119 207 405148112 564 966 955738547 65 225 93187234 717 852 912404962 174 420 456348186 505 511 479076718 547 779 916580165 559 740 227676462 746 907 509241247 191 231 211816092 261 469 74135494 548 911 786185608 91 318 580139837 665 930 845585334 126 352 559408172 883 947 230324044 328 499 594155234 585 687 595713187 936 949 693944422 241 391 406447554 508 510 945193129 672 834 168125592 30 416 956341951 299 300 849752600 539 549 439158066 260 321 781574463 191 436 435588593 295 375 322770798 112 408 964797823 209 450 164410273 224 377 254669823 257 337 53760289 107 337 98094534 504 732 425321337 19 221 727273166 419 477 734224429 512 534 868005719 753 783 108685398 110 205 759714013 593 914 745367964 102 319 363415268 302 385 969114804 612 837 609431716 714 989 115273647 77 103 396373229 314 499 705932013 780 827 533098098 253 424 27594541 732 998 378006053 742 752 111529634 561 703 865678581 16 335 92560404 90 172 575559331 942 985 894272346 679 905 245955696 267 281 52441850 104 272 883259828 737 741 948290151 731 804 916968678 692 963 504708740 597 782 282561702 854 942 116692141 709 988 35349686 300 447 197086020 151 324 956330477 329 445 29384686 242 401 349166575 672 892 556550758 53 194 240288733 340 350 421652862 134 211 469091873 31 196 540683321 59 92 525734399 599 600 72730612 45 248 921366349 130 474 877442983 830 842 940124089 192 485 305332474 45 333 144303757 577 730 284072322 602 753 919245162 192 403 724770337 20 414 256284251 843 985 954187801 31 276 91234693 99 406 794321537 628 721 146976559 829 933 988463076 43 99 888519477 425 431 23062991 783 961 403220807 389 472 475961877 535 900 160061949 5 251 14148247 237 373 846982806 594 889 766351065 100 429 904664004 759 964 455974016 87 412 305119388 667 717 495987169 116 141 680894459 21 256 293091223 783 955 342929973 144 383 727454547 6 461 328210348 369 470 45241790 20 403 741455452 729 919 556190079 775 868 706628468 942 956 276601572 615 857 221076723 64 345 350177860 672 867 515041329 516 957 638168580 358 452 234463679 668 803 679511283 615 916 403174332 49 368 264189365 644 998 638862946 743 911 237796158 887 978 781217787 449 494 729243766 31 180 220074486 800 894 988325937 553 890 280374398 576 618 550646813 510 770 125746996 2 327 36211823 252 422 578275551 690 993 983238135 320 433 563046779 304 493 69457007 723 774 776771835 597 607 162507634 210 465 755325743 130 333 401589668 578 855 359326702 662 872 918371874 602 897 854872511 144 161 315752089 41 322 787642692 920 969 699879589 701 906 351697456 840 894 776594583 557 684 141914662 86 317 742625699 316 350 623732565 34 403 667958560 43 182 743734057 547 856 906874272 635 806 293916745 103 327 892997419 471 492 443381504 168 416 562463256 87 448 628000567 6 87 571194324 107 297 995792684 873 968 632303883 510 812 680276246 73 172 314165156 545 845 576734552 95 454 705483919 683 809 655366392 147 393 257622940 168 208 481825231 141 243 781407348 623 936 894789032 239 319 327818444 562 691 892558142 40 140 5000281 57 224 90131701 120 234 263265604 764 942 864174219 908 959 114682624 566 730 864235914 851 874 299156664 534 800 123795613 307 425 829204518 58 488 386531080 736 775 432663125 92 125 136362167 202 330 74700548 80 187 166736624 793 892 45914663 247 447 548713736 598 685 737388086 117 362 970895109 900 917 14463330 358 423 838772534 359 402 304163145 424 486 283650021 74 289 549747137 354 371 725643822 4 287 609024477 589 843 756404729 51 121 302030881 43 445 633644487 746 919 324919579 641 893 22839497 48 63 688369888 787 867 366285376 518 826 655432926 354 401 370865754 84 115 365182748 174 221 890347426 545 785 195646940 419 423 862433076 225 354 630601172 810 946 311502215 621 624 946734009 74 361 565311934 525 700 130217659 271 467 832065229 683 954 615095009 695 858 56326617 149 477 549905678 512 799 319263530 71 216 828274131 678 811 724188985 846 986 779624854 767 951 101838549 667 961 953329626 233 446 59401237 802 844 555448975 558 794 465345412 569 965 599423059 65 182 307156821 807 922 237037147 528 889 355438860 228 355 495352334 781 838 397751540 592 840 605890176 36 191 821291832 399 433 952354907 175 454 93670325 39 50 690917818 174 286 231497347 591 895 366745206 899 912 226642849 153 202 970719625 186 233 721664521 660 684 707768209 577 996 412787065 818 950 755275073 184 272 394079193 80 262 520550490 570 854 960510158 105 491 522636453 310 456 330446438 150 209 254778715 114 499 133006015 544 750 976701325 791 853 6949439 600 996 584407609 93 307 31803469 503 921 839908350 169 314 985382621 424 478 397960987 392 420 672859255 789 843 150466724 734 919 248897002 620 799 138686383 254 283 840322341 718 770 560796292 655 810 742574015 189 494 333007453 575 988 184069260 747 774 221040209 228 246 199203634 12 396 364415626 283 289 407915539 592 898 78031619 262 339 206847223 58 142 769714723 860 865 488135382 111 265 796793031 75 266 390757972 427 461 155729161 649 707 517170378 253 335 622314637 559 812 762227866 435 474 189833640 20 329 73948866 104 274 329363763 117 267 409687522 279 435 44250629 123 380 424397554 60 429 450045716 288 312 811104622 554 656 251335810 138 194 899279699 878 903 981537176 362 386 897672526 10 161 473565485 163 168 463447044 106 355 744340805 111 437 312179565 310 422 983548826 360 441 886325471 451 491 654050499 766 814 505320542 524 973 794986134 154 385 699644717 507 975 616965188 50 369 688870703 126 314 643561183 318 337 329188381 44 56 189480319 744 792 916494312 685 868 138649140 66 72 877938323 26 195 928460167 295 449 272776485 105 310 363830292 88 432 636797439 526 721 211183536 368 389 141090640 644 914 623736624 66 196 962317506 527 804 827727067 604 709 328145363 800 951 278244481 743 861 497615102 592 596 903749067 582 729 405902195 283 358 486451008 535 863 270006441 809 833 455585336 576 761 456812233 524 946 517874842 1 380 452884410 19 160 106947278 610 953 112327790 167 270 617979423 625 724 518175329 205 421 828751876 142 496 620152742 252 375 835850842 129 294 2286164 345 465 834736030 592 851 684692873 152 361 568651506 898 995 753507121 77 412 230334149 133 227 35053700 26 372 530140207 411 427 144584154 446 491 441504890 655 876 597297501 576 628 561343980 9 411 234464773 176 369 161292766 569 789 420743573 91 238 250572101 303 326 759996208 235 342 500787752 669 764 569046557 622 997 757541321 548 860 155981682 505 962 535208557 548 688 381989652 654 877 409768026 135 347 786623458 73 322 923479478 567 618 157190020 813 849 153519867 300 392 661636996 162 204 500699793 239 310 51740342 774 781 149251197 548 640 614195565 651 797 322556525 30 52 278925845 507 791 737421843 116 174 881701310 679 703 565822251 258 378 912229019 392 402 182080603 627 757 694175917 208 358 517964815 696 903 289895183 108 365 164404487 45 157 75679996 521 627 143647291 588 900 663886369 603 831 724279480 374 483 529646011 635 896 898380321 264 440 130718442 100 475 381803376 312 395 863233428 881 964 140862568 571 927 911693938 669 779 356939652 273 374 980929012 397 466 149317784 88 402 41017413 55 380 133902103 165 353 863516248 583 629 179808969 233 256 364605691 569 700 887470376 106 154 704292533 616 842 252090772 718 751 892965281 291 339 483071122 553 994 610891348 302 386 131089825 516 793 82260265 209 318 753743569 522 624 251919393 536 689 138510618 574 927 588859547 308 311 824275354 935 949 286659510 296 487 681604999 529 899 788435320 83 269 408966598 39 76 676316761 639 804 37353538 196 270 639688338 337 486 920514304 521 657 577290031 330 399 980409205 21 157 656443233 86 177 91051449 726 797 19606471 527 758 959529983 255 422 155423400 506 834 899321592 142 152 558851633 625 765 56956473 576 873 541292424 640 810 527139974 524 969 994765953 507 573 439868664 562 593 51379308 513 691 435503909 6 195 15062157 775 949 790546619 769 898 115770268 221 472 278665167 403 469 976829290 274 328 338158455 642 818 219178054 618 769 748670106 586 796 727216927 321 366 877433715 809 997 251925810 748 993 830386285 630 768 993323496 106 361 620229150 739 954 523043545 501 772 407443947 352 474 190643823 511 843 72607678 297 481 247097988 745 805 819943704 542 813 550438913 512 969 184197093 617 715 378689640 647 720 803045832 52 224 695849099 427 435 29810144 245 299 304524871 106 365 116095384 684 926 481205750 205 367 520729011 25 179 731796456 157 324 990250958 26 171 112045205 368 369 632829674 551 700 78120811 578 702 933419496 644 746 648020735 166 323 477800745 33 323 538091406 704 754 274294723 592 823 702267676 160 353 90616472 549 560 37333279 891 994 847875076 285 294 906256801 341 470 77560083 717 969 583366733 681 748 914798289 629 748 957049486 615 645 812717458 230 292 966491867 32 208 562956069 6 487 291979861 527 541 400473840 644 780 226362603 113 496 859461482 726 846 8523500 77 270 919463262 289 408 21803281 181 231 391617317 124 247 141282138 752 961 656910203 584 613 668004370 331 415 941466462 169 334 191260015 333 497 529950035 708 856 706734618 617 921 816644302 351 390 278161500 301 475 25116651 42 447 416123214 928 979 197957496 714 750 972782068 367 428 234887113 112 437 566041360 928 960 639898883 539 853 330962169 744 880 658820984 64 262 71290846 137 239 303709067 72 373 631219499 771 921 275876471 175 471 246663783 554 895 454735353 654 819 27921926 241 402 329833568 106 275 103108969 133 199 58361749 547 657 582831585 706 742 779183528 668 775 418979987 107 435 267607057 803 909 756413502 449 455 642103687 682 774 403089533 102 311 789545610 786 906 430799257 690 756 730605240 173 429 309147901 292 360 382022189 819 961 889090101 512 977 705639668 2 187 811200065 197 239 491047641 676 897 76620918 149 467 979268155 29 102 183894399 111 156 906790419 726 874 976747647 218 484 220805653 787 835 424635322 250 319 848753784 213 441 963497575 25 219 313339887 840 855 715078093 135 217 202783051 502 921 546670288 680 963 16421405 514 646 58420054 633 738 920403608 216 359 316749563 177 196 183756364 545 828 356998558 796 823 147839836 764 948 981098871 236 241 970703076 190 293 126422777 599 616 92079584 639 745 616453164 439 491 662125905 581 824 362089970 650 812 469799127 697 944 460873632 718 725 717212232 781 985 66249398 849 887 167637101 37 264 423284337 378 396 141446551 671 995 140790674 74 80 364138550 252 490 720715374 810 868 746595732 206 473 890116667 624 975 795068718 690 727 146364261 583 729 936991619 855 899 224799477 576 621 198664637 167 346 323772706 138 238 983795671 570 728 418200642 85 245 856438414 733 955 728032673 518 748 975618928 548 886 220687144 160 275 608333879 798 974 858844523 183 327 258867731 48 288 180305212 126 219 260878587 583 625 383454043 163 492 580546682 554 747 569958041 284 328 803635066 863 990 677790259 10 244 13718348 560 906 744528258 169 349 836932218 575 667 973936895 693 828 560505039 10 321 905169134 842 874 20272821 137 371 161453691 69 85 40528595 618 969 43334208 504 751 298273977 897 915 569743564 609 939 423309197 181 282 862271687 589 806 181277526 553 824 280477931 240 288 959596927 17 70 232686757 345 373 118284112 177 239 579755458 269 355 286159265 62 87 782751986 194 240 898282305 90 166 392622806 327 426 606864969 84 106 192544189 635 662 676135378 100 497 887440604 636 661 505836148 940 988 888006166 281 296 656974701 921 932 498994113 794 916 94040960 167 350 341104211 772 876 967595003 237 294 348377979 278 325 279861357 681 783 374338734 126 424 252497140 715 840 493028050 235 413 321203746 545 634 833459876 597 619 63788256 899 953 851332456 362 366 543655561 636 991 830204643 598 753 819938156 699 773 703865117 705 961 69078857 135 493 943987345 122 393 767848225 871 961 847267279 662 909 560154688 700 826 45561651 513 773 988192644 602 674 704932533 232 253 369807443 115 396 120358295 119 464 978024916 41 178 645080995 20 194 122859939 245 487 159399258 90 211 157949491 725 739 787787489 229 357 505749256 726 736 871866704 556 894 312121746 528 964 693102070 605 774 75978547 263 316 272252041 138 312 962293218 45 441 391878428 569 643 847124634 294 346 249617682 552 978 382863937 560 640 649592436 878 981 814703185 553 883 424367293 604 767 613979198 671 950 179636946 138 197 534334045 11 482 924156330 270 300 700468834 705 764 864736891 238 402 376185084 643 722 370869585 519 673 614022589 506 944 110072934 885 924 960020282 62 447 181106115 748 837 470390316 150 440 328181070 55 202 613029639 514 997 897798679 608 891 148432655 290 456 777262011 313 381 621722090 717 722 458848121 133 234 855125277 515 1000 758176483 231 259 299090056 541 957 905553359 218 251 629030878 558 849 41300793 69 492 880419876 70 195 189270981 322 366 864796784 726 812 730390715 715 844 203979559 203 427 564883829 448 473 789875773 204 288 262022189 155 247 343916003 74 210 868193321 675 723 816118664 682 853 629593988 908 946 498083392 701 861 914311863 575 916 906226300 117 162 34538681 920 969 477748459 382 397 418905381 866 905 992501484 562 822 923556249 510 604 402531320 583 968 456038258 619 998 550432611 213 400 175151223 526 899 758406274 148 426 936583570 330 410 670337858 388 473 968423277 134 215 671209072 25 178 171214800 46 149 481158647 609 791 531271525 781 879 770179110 797 916 515765745 76 174 13419761 82 325 604877418 4 198 384364556 40 390 543764260 853 890 542079229 123 320 58272359 677 753 546506883 8 282 505167607 338 367 80767758 956 964 921519819 737 790 259753171 562 922 141829193 117 391 370493059 240 309 649054862 607 755 694345125 480 481 103259118 616 868 38389063 215 419 281051449 685 700 97899698 93 296 695786209 665 980 825362097 892 917 882377707 770 991 348871442 524 743 538700580 727 770 660262031 25 406 384397175 545 922 317556377 558 955 496793933 330 421 600752189 219 431 262173654 141 207 800590291 253 268 311580452 72 455 649588971 361 478 885005110 206 482 971156506 753 955 762068030 690 810 697928373 790 812 704511814 187 479 527483643 682 697 420026206 787 915 351093709 622 972 100418494 827 909 475604366 611 910 464573106 695 721 777582322 126 137 376150149 653 916 283871352 59 87 943685311 620 678 565735980 714 965 30110329 690 798 990730708 93 343 506936722 106 432 381895896 526 658 458324132 234 309 710304014 87 229 164579059 163 349 24867158 166 263 468883409 378 423 99245884 117 291 269702386 624 765 230173644 770 908 933344914 818 855 557660864 251 282 111757252 352 451 595346524 123 200 331097885 670 758 240606654 23 305 479250621 554 876 273341594 854 896 660800273 732 840 429775401 526 955 98021757 642 675 646784521 624 896 452836978 714 778 824035896 625 698 100230381 240 249 72929883 211 327 492850805 552 601 379834594 593 907 881088369 585 853 22033070 197 437 642606473 606 607 544569955 778 816 844070823 63 320 893944242 652 803 125470112 936 992 979159913 387 400 562364653 298 332 493420142 110 263 25165160 96 382 255788786 109 464 497774459 587 754 917517449 162 309 721629589 200 393 416332349 216 353 924028795 794 818 885779826 16 202 663769693 245 331 519894893 42 87 912571893 552 710 666873726 344 440 91982777 542 945 707295108 521 787 237902013 613 777 781592710 711 902 636605100 582 764 413050596 79 155 716312187 248 324 166714263 890 986 248219021 158 216 40572893 681 901 395039481 55 138 519685491 252 259 436017949 75 214 153009705 273 346 246279584 3 212 636321428 129 274 208131425 157 277 683359802 547 747 507480986 337 494 664555494 710 843 345827902 624 731 235252931 611 978 738886563 527 746 384316597 4 284 195960314 596 706 354106437 578 836 847013053 589 732 298668177 154 323 391849831 552 648 599011680 32 340 885322035 827 833 678086596 761 887 750094550 742 797 870895051 404 435 1803091 826 891 610661008 53 115 537998572 513 957 507920581 316 319 435702184 71 268 119142627 162 485 504591649 594 783 150152309 585 980 196736959 26 241 8240453 581 811 236644836 144 196 844162004 123 187 437952812 889 905 792892574 544 869 116551159 910 974 808009960 678 726 634171972 88 256 770348165 413 476 645362553 7 298 104796987 579 704 763886071 632 635 158707567 80 417 445740313 617 888 869428129 206 472 76184394 172 389 139337948 112 227 618290587 531 898 25943705 865 917 171179819 540 675 640806991 184 303 765542543 147 330 91124758 68 177 677011331 686 993 633625072 606 959 726011042 541 656 910621465 701 851 867078822 582 912 897720958 806 895 701710057 510 739 371090433 228 411 382184038 805 865 311465353 542 854 467983126 714 812 988985408 508 608 762698728 447 475 376508871 527 786 566353873 532 604 366316281 2 236 460237786 524 797 758007904 286 361 703973157 86 183 439849855 153 491 447081386 5 18 272783436 276 316 758200096 277 348 355867800 575 893 498991033 325 397 69544003 519 880 392742386 566 956 368516479 626 797 992856938 91 243 539787604 560 914 488256148 780 960 422940125 652 660 922427089 838 840 889010887 687 898 708949343 158 437 724085999 37 467 232214806 188 413 993743406 643 917 191761356 167 373 436072276 214 376 630554308 739 861 424705610 787 911 593425207 556 686 93468644 481 482 143586660 179 316 268632750 286 369 521652938 437 492 377476679 170 242 686732004 401 478 933794861 4 289 708696187 434 455 668958350 535 659 910428247 146 283 779438792 787 890 431193705 320 449 485497121 573 686 125597458 290 413 430158243 643 941 630808788 65 233 894450801 620 872 301788161 747 994 415227535 639 959 297461572 526 862 90932137 889 968 596801560 582 997 279429890 159 424 363175628 330 470 31276272 77 93 111364661 579 642 186489946 553 900 133886855 293 378 92915310 86 338 953774070 947 963 653597046 517 582 687379821 816 856 97271610 713 924 379392125 211 296 350052062 803 956 859006124 757 772 672568901 730 893 545455341 841 904 159054191 550 771 384744727 192 294 295885157 614 840 555906251 208 287 975135786 561 823 890554879 65 224 32127214 634 757 39291184 315 456 654632062 34 158 702875633 868 935 870013596 75 307 573446606 552 923 535512336 51 378 572469412 673 677 358273057 175 324 200904133 637 851 261224987 37 83 616902257 339 458 946448986 608 709 802738186 653 986 851812972 753 839 98023114 264 364 965122340 19 334 447249719 507 650 970818892 528 599 839600779 609 850 874612773 918 922 348367280 622 682 184986934 257 421 182303510 545 785 562399286 615 846 130688354 370 426 443587216 952 1000 942069375 774 848 258683428 135 258 799014584 273 309 795494650 782 803 612058522 539 948 149028624 134 363 200347559 332 431 136496304 263 338 210798775 161 231 309199631 264 495 205267272 274 328 104535635 580 700 997329189 591 909 962465809 520 794 982171264 198 233 872383430 178 371 468498685 599 692 831228120 774 885 289506725 580 671 23538212 112 499 11910795 800 913 505067368 664 812 362223803 434 475 823515009 881 995 781276849 406 476 826910515 510 892 563373430 273 489 822289085 396 435 400158444 287 448 793671698 769 776 919818373 239 300 900564169 97 288 297797485 594 663 839243466 697 787 159542268 661 930 751390424 65 438 762297385 581 854 827274883 269 362 210052981 914 973 473935884 117 143 554647991 28 375 591249509 102 287 834037384 517 653 690014618 765 930 932074557 738 797 527395781 665 759 952957867 739 893 190710667 34 293 842048864 639 854 884491944 514 655 489522236 159 378 135978955 190 438 181139690 13 19 99640088 394 436 513462467 777 975 173977822 749 986 934219688 705 770 993975274 502 775 322361551 819 876 141945888 103 293 669789009 933 939 745380864 541 848 370092702 768 934 156020085 42 271 536072986 582 629 475248659 517 836 512718917 137 422 59878174 213 324 443594167 815 988 906789090 437 455 80218837 565 871 257558754 221 485 738662307 587 634 111563456 49 338 278308195 232 485 739935455 95 355 135753329 233 258 847701873 137 396 99305492 456 479 582140351 153 468 304641927 212 455 483230751 583 795 511986318 858 992 177360942 927 986 572169745 178 206 974504056 584 918 815829207 600 892 518057344 260 295 101758768 531 946 189754233 750 853 241740560 90 383 559444190 648 984 384605775 679 753 159092075 161 478 679016162 231 472 896434966 595 646 130017748 17 176 172947014 61 451 673540448 629 723 430493639 315 481 61685703 650 715 162610622 24 216 744838716 692 701 693463566 625 944 776449931 549 553 41007115 117 322 190033635 568 816 670289195 180 376 618403068 3 133 547456464 374 449 177640697 28 437 5456891 650 998 852277488 888 980 417855769 112 496 612141577 282 496 316691825 228 251 981116274 236 358 836133431 162 258 716080891 339 485 723150083 316 492 154408890 108 284 872426814 21 125 453291183 648 905 273572831 816 909 902685627 679 729 929988453 588 860 217326521 793 977 564145057 826 939 739244323 572 761 31924093 55 188 214437603 612 903 502998200 803 912 299483050 562 734 49264127 795 940 226134782 229 470 626833219 199 202 448261626 522 634 17996362 549 964 327820000 90 159 619871470 524 715 513031817 777 816 917431064 10 29 53238575 595 974 558966328 448 468 436155612 353 422 369628207 671 740 113406270 638 758 74993713 581 826 197385313 233 379 630560739 658 809 994979950 112 168 170024435 539 707 777734049 115 176 857696971 11 281 131919894 604 971 653428516 32 499 213371046 229 327 201410007 688 798 427089917 301 356 832742098 17 473 940230153 323 462 454148447 93 310 705080782 818 929 940116911 308 490 945430890 411 473 72626673 549 724 386747783 189 191 509213088 177 390 688338615 293 419 475700716 539 778 610950076 241 370 292468536 685 894 916657092 323 432 339059640 653 930 201654553 254 429 916879823 506 953 41477288 714 796 397843991 20 314 383842472 786 846 855736998 524 585 15068336 142 263 379507229 56 303 944194024 55 432 911953210 167 218 839966145 318 500 540592317 557 591 664674074 537 991 455511651 509 912 257709335 201 276 90202817 868 983 515152426 612 759 253323661 841 970 655291220 806 816 275023839 707 800 427985760 205 403 734940380 12 308 245993517 303 446 511544884 32 35 872784153 543 670 893823814 512 582 441665300 575 823 980382403 195 280 875508368 87 426 541607419 255 429 348047237 517 807 649748394 661 978 535512984 618 827 874976082 730 797 700651591 902 928 905221439 187 225 361008308 693 832 458226753 774 884 784355335 565 930 841761158 70 298 253356365 371 465 379887227 73 288 688944109 732 912 693780908 215 333 494050178 464 485 884253901 772 1000 352020097 2 63 88677315 579 814 247669808 887 974 881327759 634 741 910773984 814 941 985063611 251 289 178148583 523 756 825252587 3 156 505648264 628 782 325763051 249 452 980750397 516 636 654849180 627 644 197119361 52 252 540102715 612 816 314852731 341 475 214513739 653 923 383086690 103 111 474241760 543 850 412796848 532 567 706929479 97 213 172824706 33 298 741827396 216 273 407332509 548 744 21273155 264 395 138107335 54 339 302461890 175 343 901592262 647 723 879000282 758 785 978216702 531 702 559224386 231 235 211796463 76 396 362203908 680 713 576462823 511 719 936080884 811 865 804248782 216 334 509017669 94 341 117633281 680 900 812625750 762 977 288842031 153 154 579784775 736 978 825987656 939 977 57231944 570 895 344782554 139 498 815476753 551 709 630440929 293 426 351596800 76 168 61089906 316 370 653547566 919 977 56434878 668 920 127592232 32 291 300156951 26 53 76400214 522 782 688980718 716 960 447033182 124 421 135494447 9 292 25471391 694 696 205361267 606 961 197042198 265 388 239255444 667 755 554937689 274 405 139072831 50 477 365702965 614 723 104237291 97 154 957748048 848 935 720870537 628 848 217711980 246 325 705099159 31 470 310288896 845 869 365634241 608 929 185693178 543 863 652519362 221 460 849550239 673 683 363754673 171 481 455315492 97 164 650843859 618 720 20098019 704 981 101388008 640 753 698804761 267 292 988075429 15 76 605773419 630 823 610744699 572 624 706085126 722 834 213467417 653 780 265123575 561 891 409563454 246 341 819544023 855 905 357099514 29 204 829718983 205 254 121525150 598 807 963785754 51 417 664931715 195 423 660922411 50 342 278981519 200 243 362585306 608 637 58189459 93 130 103038193 341 379 847869788 65 89 626363046 47 393 520072960 332 481 118301981 544 620 984851845 90 304 640011620 29 295 603964009 32 217 960940281 531 611 835198093 244 492 528664484 899 930 396297811 599 962 968974096 239 240 310474734 81 494 371864492 637 699 965288387 92 108 572616405 299 365 452558930 13 421 196112141 624 916 644979038 642 960 643763697 288 490 670858953 579 893 482110876 298 420 728353901 534 543 324326621 421 478 364917933 244 399 785499913 121 281 678647312 569 773 30711018 23 32 438441704 572 605 520260520 517 666 700638739 741 856 618276384 67 470 204316908 150 307 49655662 563 806 270898758 75 248 136224712 914 987 193002435 117 333 28617330 664 727 842822003 8 102 735363425 867 891 678893212 676 839 592031255 610 917 842098743 597 706 795248939 98 248 652791954 785 876 722962596 929 945 74304853 517 985 675548122 571 883 525712321 567 884 873406344 106 493 580785825 89 384 945857695 593 848 496322571 71 299 511954389 594 846 482407452 824 933 518974714 391 435 975034345 668 895 36818149 662 747 34318285 692 852 573035218 81 337 522778686 20 114 406501413 381 433 265517592 33 388 744388551 859 943 755533390 90 279 797958953 679 852 832777715 555 711 694696773 535 970 494717280 688 872 384517614 375 470 45698728 810 959 944274976 250 431 598715784 566 773 198063811 6 182 248798087 299 325 600598510 24 332 962559110 584 938 140355747 900 957 723240896 89 490 714701282 44 389 82658909 688 850 779583573 621 656 564183346 512 837 19516850 619 675 313470488 719 965 719675119 138 210 303149884 13 393 204126220 290 458 101885782 37 69 905276722 9 116 920814955 56 70 731462880 90 377 359635029 656 790 392641857 98 399 281166856 709 802 155898438 333 392 557565064 188 431 202473974 670 847 939268058 34 159 943251542 621 847 919104688 430 460 543900691 39 468 228275786 680 904 523381314 806 811 987355432 783 951 288269125 643 997 282124104 671 702 636212687 9 15 79359522 513 707 676746941 425 441 406765188 526 663 713883581 435 449 611780178 250 405 806060886 95 152 851129832 68 494 875318518 761 851 90773209 774 815 324224560 141 431 587671304 751 753 123110730 504 557 891650450 589 978 480883397 750 761 292368764 359 374 217563667 507 605 868867837 548 680 715818094 591 957 214928895 922 966 747712187 653 792 170447705 913 938 781127717 726 727 651326987 105 326 464780028 156 461 996809660 748 920 322032936 191 435 847750591 313 391 443129395 756 962 916097451 515 785 976299455 348 417 110151233 590 925 278070179 92 117 271957604 544 684 874717013 49 447 80899063 95 164 431519105 85 198 438796203 554 925 570267165 541 598 922042923 556 614 748144960 121 325 70366651 423 480 155080428 122 426 670792419 109 286 15275954 844 1000 271277365 170 263 448817893 236 408 353600225 610 922 788992848 574 1000 43937351 17 92 903922770 145 250 405168663 879 999 410024692 643 665 144898624 685 734 577618316 803 820 717343717 912 998 320917298 718 829 278497833 699 909 447663044 318 474 840591956 11 413 417883444 745 808 56890036 109 343 168011057 395 413 85191206 889 916 224474271 336 487 555271609 512 691 462965492 128 133 81645770 170 201 221499859 748 834 382967154 390 487 715138043 530 983 12652375 155 288 679219862 77 83 364185681 52 451 91049148 206 269 12032647 96 405 737611248 66 453 890495401 108 187 541447704 208 256 513245322 444 471 364770838 188 270 106326266 643 700 602852743 626 884 870448590 604 906 156608618 419 439 55657445 618 721 189113871 640 861 859540900 100 263 793040389 691 709 601741097 617 913 392527633 773 872 79496529 118 375 834232202 565 931 589556024 348 450 365701556 641 818 678983263 533 720 503335599 68 104 687907580 543 948 327188751 735 778 738186822 114 131 755725050 812 935 632561232 550 915 843710000 74 141 446354012 78 363 128441815 823 871 601207028 91 313 703474551 95 287 693924010 857 863 749826344 223 350 631220692 529 678 893764949 701 924 829221714 564 828 719983548 228 256 713559485 317 341 782568169 333 335 545207898 181 328 151812472 60 409 697502569 517 813 927238836 562 999 567139985 678 794 262895462 44 360 472374172 147 330 75412593 3 106 12458021 867 958 514321787 24 290 424915164 231 383 893387997 387 448 541636738 77 352 157844227 59 63 21852506 165 469 696168222 531 682 979922217 696 932 31230626 667 941 653383980 852 908 398868797 700 896 10231467 358 465 574969407 163 300 773947608 665 952 915828228 532 734 907787947 832 966 162476577 591 911 539563564 558 845 774913139 228 415 601925308 271 471 596119515 914 976 565320537 89 289 237347966 532 671 235070561 887 937 66899104 634 723 284614335 749 880 791164352 695 992 583667250 753 780 569698166 920 956 21622483 685 860 602726287 724 835 812892044 398 463 427902836 115 416 767683292 503 961 359133980 132 246 204483368 734 746 763142963 13 223 130332711 360 483 343467384 699 772 723961009 742 786 579723994 717 832 494987967 170 184 293666575 780 895 613681219 689 836 447753817 16 219 783754864 144 203 11072780 920 956 576514704 772 928 734213175 709 940 699694891 625 671 194178832 101 373 377265865 682 738 926319431 761 811 76134407 203 464 721365510 630 936 950328155 878 932 509451589 69 291 142081370 798 974 65269151 268 360 150399454 650 930 600378220 503 545 941593203 267 351 257797301 126 360 341002346 906 913 437533729 69 384 960199766 172 398 344404775 640 851 552167486 631 878 773637279 583 781 481513122 73 347 666925080 99 412 765796848 519 651 330767297 100 130 837866480 813 956 524110414 588 774 163426747 16 361 881125791 636 816 723351014 642 792 764477301 691 775 483925712 857 930 34463172 684 924 104993816 631 817 704414343 418 421 798453200 501 950 662854332 778 803 562240634 640 690 60273028 152 484 354636081 210 357 89024215 63 152 701122618 317 468 487597906 24 181 169763268 502 754 827923398 696 764 526212809 584 909 602890969 779 817 783438987 197 264 335141603 520 961 655094787 316 480 239111071 264 360 615289847 42 247 817497143 77 199 221078996 190 249 360779513 243 292 857441142 604 704 92312562 20 373 515300982 623 955 337380195 150 477 273501927 886 888 536535176 214 323 444195033 343 491 79046239 218 397 119462399 174 300 788944780 817 996 907972827 684 846 622485805 78 346 160080865 188 270 918880740 730 794 432103758 95 209 488862501 508 608 900162090 77 101 170178528 426 449 81939642 79 338 443570189 219 433 216718226 538 990 844501403 335 357 292436858 278 344 530987841 211 270 613767715 240 257 453490144 10 192 713566951 247 429 239540768 18 174 234306565 275 462 158956532 181 345 223774076 545 655 617703210 195 203 263331911 633 642 933484507 669 828 429814450 695 915 24200104 715 998 196493967 96 358 442026403 393 407 23833333 71 305 293569062 950 1000 646095787 63 149 321886324 114 387 172389311 760 763 411975323 296 384 338698511 48 412 156403171 706 983 981055129 182 423 278233931 295 352 117182225 104 432 329831945 146 342 280600092 605 872 152028442 164 407 23551944 99 430 17488161 198 489 519992684 96 495 986919699 1 308 520848138 678 814 117113944 695 919 249216730 560 928 874082441 809 866 934251158 813 878 810825789 869 886 447904001 614 757 747417316 400 445 266002264 736 928 746284075 592 837 89572483 625 749 574958654 318 468 512405441 29 242 389299140 791 985 868783147 734 991 590733162 112 244 912552940 673 694 298843371 612 881 226054458 870 973 979604019 287 479 592439892 566 606 540421003 778 921 878913922 251 409 898999083 7 361 370099718 643 939 968258222 117 286 127091601 628 793 381439050 635 858 255020963 261 416 949476722 95 135 298056583 698 776 755591047 197 246 452732604 187 454 118183084 20 63 231368273 74 220 118950958 695 909 726192345 683 984 710360765 170 413 873347355 200 369 405930540 350 410 738043809 833 894 814163479 28 482 106643299 70 464 631393107 31 89 945071543 40 317 225266482 242 332 724031070 140 254 735178312 23 188 825777902 171 442 451426971 695 970 800011430 587 889 444616337 839 857 853825408 731 826 326365105 623 904 949448893 722 944 923137716 212 442 111361003 696 883 774291688 606 620 389647325 901 932 591589597 543 703 572670495 714 769 289724816 900 952 801969254 510 913 971676152 188 191 412739546 576 578 434529321 27 348 603945357 579 673 31122365 237 368 387408335 4 427 179212595 764 970 890849543 4 19 470888787 254 401 311617674 527 929 145079463 538 990 498828002 688 740 445060293 248 484 469323917 816 823 689906474 553 857 81638106 565 732 9767649 922 986 717120057 879 961 130736740 574 928 492568974 610 763 297351893 246 379 881832900 101 332 430287726 97 244 26388764 718 818 102851306 5 372 342550410 209 338 84182658 230 448 412574748 538 830 728715091 194 274 836695441 53 463 675144866 674 902 86297679 536 590 686846267 264 440 140176452 19 498 203054818 845 858 16841227 2 280 223431258 360 369 695050304 674 841 893609199 277 462 153591936 579 655 281751013 906 938 523369381 685 839 225023571 539 564 739442522 601 955 841770652 606 812 547116429 329 499 548633229 525 635 942766150 110 188 675503073 946 974 104524845 524 692 495485951 28 440 185255927 690 893 469723391 172 466 421279521 21 420 131998767 212 299 619099166 1 98 899301678 504 549 148924309 635 649 935162643 54 101 903320840 633 947 594519200 548 998 431800441 167 338 935230606 621 941 842576175 120 342 159313727 7 309 809454327 52 206 257605884 44 198 374411908 155 163 90680738 840 988 357312588 28 196 25739526 906 971 98961368 786 902 674015022 89 285 521890174 116 127 304666909 519 840 906606114 658 841 141678061 10 289 303709937 86 227 849229555 752 995 831781658 113 312 984011089 567 870 414491208 46 448 284526909 5 329 197787252 928 979 421509786 826 936 936441490 630 688 561474802 910 920 105090644 165 334 765900002 715 892 735850090 335 362 851518223 166 206 304350716 455 463 623226071 70 176 859381355 215 265 156817255 26 44 893958643 2 260 347762048 235 424 569089633 1 46 916919703 698 710 614368518 793 937 54690853 643 866 913658276 549 873 579553662 86 361 921348308 645 823 312048735 874 922 239844601 426 453 812360657 365 454 210444438 541 881 35252192 115 433 975672918 707 964 338704013 155 322 833409278 908 969 555391854 99 345 340325133 525 871 854818706 679 966 47162567 71 111 332814098 725 819 797037369 58 297 144061061 109 211 515442801 562 629 336971839 775 804 697536623 283 428 685768917 342 443 217778017 542 559 532899285 630 741 791241780 102 299 202591163 901 917 561544372 886 889 716658779