2000 30
965243 11654 735992 158012 986340 16880 879492 681351 857343 999817 239715 338078 708195 280581 263314 228609 857837 874533 797616 223391 924839 511370 231386 455537 419875 78959 564692 359964 569616 930218 645571 405100 863574 995173 490257 945025 18750 140318 172194 938065 690485 719083 286617 494985 887065 99875 116221 47416 468662 840483 554991 401459 502057 179211 948133 353801 235260 311233 824933 318267 904807 336177 441548 74201 907472 796152 474447 115400 492483 376148 840003 927984 741106 287212 41378 893940 944500 158375 499926 480971 976429 43048 61706 843749 569581 462289 777749 593341 692428 255625 84930 8925 333105 648500 379789 347328 618555 705201 595454 311738 821743 800704 893498 892580 15037 669165 348085 388445 518089 143885 249433 986260 331004 913004 684410 314816 318703 604861 702080 340036 59060 172222 860675 728861 108271 835114 575863 334809 893954 128755 98201 343605 737735 547763 484211 906746 393934 788136 4580 782946 155479 655687 838497 655753 578823 550020 751415 368781 233543 557094 520351 116240 530081 466878 156455 707568 778504 338759 865415 987264 662192 407831 272420 129918 273007 998818 60422 916230 697195 783905 99266 646117 205162 676950 794198 721482 535310 884600 229317 157054 865494 55696 417994 419896 877219 372286 569341 501284 478815 473307 468258 596322 432443 423072 924831 976439 247074 947258 23813 332492 899076 169067 669008 994094 611998 459523 30492 451042 463891 788788 390355 805740 405209 635336 758749 166070 953509 450116 479521 972597 571138 519872 213597 220034 760545 505935 658655 695409 682350 323382 862929 449786 175927 867219 901433 120503 885158 688335 269928 575144 921993 151862 660038 240441 149360 950432 995207 655123 792349 395021 428397 615021 813855 700843 469745 627654 402689 810157 868981 773696 321576 381022 979907 378200 664700 96458 131724 225598 672894 227858 656896 72763 691454 702094 256608 238816 250947 493845 184977 234421 804382 936414 160856 519484 658823 949284 559611 531285 771631 788659 712204 622547 811305 42076 767448 222326 353455 393687 519931 590074 586790 316611 361037 655984 931316 381202 8016 853708 887203 840791 636019 417284 65302 920708 436414 122573 624868 44321 388888 603248 802765 359128 195962 343800 820399 90859 139029 347718 952049 883276 967197 48215 501170 145231 585439 792993 481970 690125 681210 506840 389845 239682 720399 981456 968034 924056 847924 655997 495530 120693 798682 183475 930538 857486 283271 906572 756120 811843 108481 271762 155066 941389 243909 443949 752255 397106 631893 624681 379540 927223 668648 739869 731579 619788 169409 914620 942558 102286 367886 187226 132044 579160 433329 133305 481870 695619 135904 646019 659129 832148 998796 880705 373942 83073 333447 169138 852876 366042 560586 726410 460606 998038 658991 596493 166024 240274 688519 439557 579617 879243 676980 837759 366844 67773 277167 905111 240069 122709 68700 999785 209270 76403 358531 43337 730207 688521 422713 725485 17949 796617 642116 752603 142484 952170 985656 479923 319823 516816 708675 461513 543626 952942 708634 387744 909581 787734 21022 493379 301344 305079 369849 836091 610177 246139 67241 150140 375135 541774 497992 426359 528139 309625 951650 219685 368985 658644 838364 403849 634397 253928 11044 968915 67563 762098 31659 299098 515300 899259 803753 299246 7994 753245 745797 933089 133193 668963 617435 877417 847594 767763 849925 81656 987118 603700 895702 150541 516395 887213 965854 611587 893564 23196 104476 255386 874326 713259 426218 915519 515266 145364 942281 738733 994665 780819 504181 894774 132444 7616 263937 951090 88067 757477 538424 131860 208624 719028 388760 879577 50785 575124 851543 238343 277297 579306 173793 647043 922534 319475 170093 879111 53634 852045 420596 798933 375783 958958 656159 596373 73343 580764 236466 710502 318366 229033 140560 254521 124927 279361 536794 857210 776516 362008 924768 351022 426796 545490 598907 492612 663008 197285 212375 335928 439389 253121 568232 73465 423436 458275 604139 143002 655590 462116 925152 137996 400924 782931 935266 810291 889945 438059 225732 257980 635570 662670 424477 191012 874894 325202 240086 833082 776287 671342 795368 620243 621555 391038 174282 930380 107028 772574 317539 749435 898488 783650 23567 872672 231420 265985 985665 842372 159889 850838 259154 626249 815567 70835 183837 127231 142726 905114 31114 317163 848589 21440 458997 832899 914743 823031 53538 40117 741221 459921 489547 679380 804719 277395 959383 298623 871379 77939 37354 600228 748602 636079 64808 931378 923220 903662 705324 6687 442815 187079 229107 478338 854640 643620 978667 352315 92187 800104 881390 505356 232605 639771 254613 399713 590327 723621 738059 99183 399811 511080 310465 67140 260840 437056 632184 979826 203863 567895 209692 131802 282410 423958 846426 311729 947948 781884 400557 877755 272955 16495 458257 621626 686631 15416 13757 684456 923328 490827 767134 175553 143470 465397 961269 116036 532406 687100 22994 807542 193949 830087 600362 51761 211015 424436 56252 737697 424148 130465 216729 682516 432126 525270 197224 276439 235174 444055 138893 27169 952224 970116 38061 892803 294762 535227 514364 79337 341042 426027 549089 543511 363947 516656 118630 701792 589776 187192 456654 503535 494061 228919 486125 558101 986414 862995 765610 357313 518773 325055 596421 788971 783748 947537 764543 782655 460293 227483 376844 522647 478127 498237 11597 980631 380200 328978 846322 390861 779027 103383 531826 45405 504823 793728 267021 646860 737812 409242 180622 710739 870712 938547 984599 875264 359961 753478 792270 448354 894655 129113 745301 702037 229855 128148 679860 86981 306716 910459 737888 388883 443988 277122 743542 560183 623624 232437 927788 260231 694688 984780 885976 48081 542177 716209 451082 268147 223744 357862 654119 540166 843845 272261 663466 971954 342667 384050 332905 74676 192487 781997 315021 255315 830180 4189 326286 179203 363403 135761 701921 272893 676560 135907 854580 114117 784595 152251 435456 604298 91015 540279 632397 419109 740802 537537 43367 765698 973610 146260 166950 584625 633660 452976 177954 492457 346678 530854 929186 435928 996718 930019 208370 498962 125940 144156 556936 47787 764062 706285 978919 753668 839688 326556 985236 225273 915129 922590 754243 797738 200830 809330 211233 221524 88272 806120 753034 438752 42782 142772 814506 655170 278502 919606 556393 38413 988344 338536 458656 895779 929122 266957 889512 262292 22760 73233 161311 575349 268165 840596 387259 72528 494611 93488 7946 926877 101578 113866 259871 120027 434365 668618 391402 546508 51533 162426 264231 627105 743400 960896 471139 182651 353784 379405 907217 672889 485500 482145 732870 707488 915221 505042 756244 964672 904586 157147 971216 550959 899124 897079 852472 797575 735152 999798 583250 261439 572305 603577 844357 616968 421509 743892 480733 233872 966899 665955 598686 793537 555771 461021 55289 626128 274880 605987 903729 703747 733327 99388 650284 907541 532029 677118 294199 697854 255227 522669 768424 524516 621905 183164 566702 641965 689528 196667 529322 520596 553473 182841 846753 599557 303349 986779 615077 321674 409754 352591 238084 149011 90967 69662 686988 359501 369589 387500 956306 923111 262855 685658 966003 855965 481710 812255 215364 721849 257145 725438 311051 898619 123600 323025 204335 490757 59110 160425 245154 34352 705846 845034 963999 444466 360905 588940 347680 10719 391992 790252 255156 277008 344947 815977 352980 323593 239337 156802 875222 943208 803637 563497 309438 624423 556687 256781 683806 875929 666746 337492 953556 896658 640623 302136 213842 888101 278638 85166 277519 838422 815401 905088 892472 722583 604893 800802 563726 972556 298124 42821 755456 529480 904457 462598 590648 150269 429839 170980 12258 103844 699266 885365 61258 816236 540392 458427 39332 993197 646666 146179 501261 341568 346183 79037 960931 454631 126558 216407 346521 996389 576717 403455 859650 10737 669221 46220 563393 655084 709544 628038 429044 985117 813754 62650 9608 119073 402147 155029 293016 52581 296094 211230 171956 903293 715319 876358 404573 169943 174820 654234 236394 116146 389810 372967 288139 419884 760794 663449 272638 401320 943281 969884 350791 248746 201815 409035 895723 101841 546753 745805 57252 698338 99113 273360 449634 336004 281811 154583 393659 872132 850806 375306 101951 645860 490514 757810 493423 316683 74845 420854 109746 164463 279787 472785 410847 412500 63094 148492 93177 218848 352545 459906 712645 366 237702 996059 606058 231822 891282 759223 599848 997759 379443 507846 236252 827769 188152 610635 805048 992904 566806 349639 240579 387270 101777 954492 144861 913159 391244 84934 896564 969452 103439 934130 176002 547650 389636 147990 221049 853089 560975 493312 170196 695063 486911 648135 678606 966922 642883 629031 306768 150795 957053 305433 893585 753497 100826 836639 216946 377525 174260 390601 737099 436145 779230 794749 294553 733939 465999 972816 786513 106405 648297 67368 701782 65684 160905 884900 542854 873391 7920 516768 49960 783806 395112 275311 417886 89640 576720 717193 807756 619856 347985 938367 945622 720515 876217 231712 789146 636185 53601 409158 647742 990165 925661 998393 973746 220590 909606 520380 752730 554216 487705 204724 938623 865493 381125 444902 851500 426936 232221 176759 201535 729859 622012 819518 501321 748645 431279 818900 661924 699055 892888 374573 959297 578002 68718 926660 18459 748115 838957 487430 44435 11818 572962 641672 910024 935838 457372 860200 472380 370458 486778 138124 475430 638262 148366 71118 596522 993509 931842 997875 675066 785624 764845 586198 541834 468881 754391 298416 843785 872209 756055 373766 572213 321858 503133 69952 4013 267394 206470 998081 443751 505701 891758 558869 119486 222854 99341 316758 199142 288957 264307 799199 794446 748245 267725 112301 475132 217793 954268 708247 460396 914688 140871 24117 528992 979969 323973 494273 195938 427458 591432 4233 29643 934882 905687 257755 858119 491267 57673 77730 153454 592352 102769 544816 555256 493411 220672 174446 321695 510887 348352 871881 968423 229197 915613 653392 537260 359293 986704 742285 760056 502054 511595 319484 385630 682546 764483 121415 177711 123725 777752 765870 443361 160087 933386 540153 890548 325104 464880 718546 433079 59150 609511 40529 680678 499788 669162 200017 213834 376556 980324 693905 181938 275132 566340 961004 604577 278621 962665 181850 196250 244652 735649 813354 416102 943219 48717 834368 947841 157601 250927 163106 335387 139656 211113 57774 775120 833411 578590 720428 576791 558629 876910 942004 287887 535801 651080 818407 961509 194951 330490 822316 503506 996884 268271 367766 208613 460479 589845 359544 996003 960434 266211 287985 62485 282726 849963 254945 701216 398621 695442 850876 274065 976898 156900 116090 131137 887981 952828 988528 886483 563274 811420 324920 484076 782771 803678 447425 607814 622809 375899 358083 445456 83593 90233 986820 184358 576129 209675 171192 684448 771582 712321 292894 78257 803725 429759 990929 956976 578450 166684 972258 888367 201902 171518 297003 833654 285221 943430 136329 794211 465643 390130 335993 852832 702270 6243 561570 906818 257288 58374 864035 969933 762677 802024 79398 449746 770716 523362 899973 188266 616345 695509 288592 940459 406336 763216 394478 55170 847536 73354 705305 963341 304226 850462 678445 879279 65338 408323 137943 319148 245100 519513 857961 462096 231423 988424 845742 526653 863040 586052 402270 528191 112214 997595 337221 745176 598619 957555 649531 71671 34780 408112 163977 285225 832600 623008 276345 623760 306772 739812 265605 823241 774999 387988 29481 582847 436225 696051 207964 508091 745992 578674 689585 212865 973040 276728 813446 235170 285405 976386 544620 274443 211708 32012 134892 260159 312520 615669 994338 2360 298224 881717 42515 949540 53700 176777 454864 245973 753061 734058 61321 985889 893675 254386 728946 391007 281588 811876 958020 377524 590766 858958 821413 224970 646930 303753 168548 436338 344508 575985 138532 987999 326615 800232 128046 507788 719210 420782 735101 380373 257721 473905 482907 903646 166572 673335 983200 614096 486205 542673 302543 279627 298588 43737 895952 978686 833711 972181 789854 234038 464849 556994 598100 568934 279258 425004 695464 538983 239307 998168 34868 884300 50191 211081 212892 563691 578468 858543 934514 479917 501256 179905 131586 335008 981580 453548 104964 656548 211318 590801 505407 755697 207448 578280 758341 628815 200464 260313 168378 11206 579176 382371 332040 495506 749249 88728 847820 872880 315192 568707 405798 592528 157248 237421 921232 95720 116919 82140 397459 798654 207486 241523 507370 578254 385068 923309 220920 858007 643965 602552 358301 992206 891382 213084 657065 306621 600551 518905 200604 416812 264398 975473 683233 387315 405451 255726 676399 188554 389646 421970 493041 775942 50340 308167 391997 434019 591751 78300 905557 330778 748826 504866 489702 93503 292226 780316 929145 947582 415360 146308 359977 139963 125473 937650 691966 43783 883563 394106 176652 658643 355975 148561 834007 180211 192350 454372 521682 403552 924502 47973 922026 432190 391584 502751 133869 415242 354146 491883 382876 47368 607752 326631 292237 26884 75091 247799 368401 229186 322101 367814 561220 450895 705608 800510 912348 806040 950042 345656 178053 755190 457759 873784 419660 718411 646249 716749 296288 25902 837794 346626 426348 32981 794099 394124 21362 184213 577821 142548 954539 441320 763667 668015 159557 224204 155540 893990 529585 497860 769601 58923 711998 67865 566080 908592 6675 246961 374401 261746 462271 679936 81348 262989 59007 201442 905326 36293 773162 670859 562052 377053 901885 507331 497583 922140 693311 649017 841090 763942 350227 839812 512212 387309 794167 625022 952040 907770 964880 26780 468072 385978 549409 655599 374372
