1000
512615 885510 761579 907555 628780 632688 971327 536009 721886 613606 759016 920729 530646 852280 771956 809359 723840 720308 881690 502375 892586 992018 928478 919214 599755 685252 893992 805510 634942 929993 713174 636155 748446 732001 561198 893822 762686 623668 576457 527674 584504 819256 605527 521947 766779 616722 681048 629063 892792 913317 568439 946998 681792 827131 842411 645566 839182 541793 579193 771327 799775 616502 875429 685779 637553 628567 529654 816559 540369 640667 847334 526298 873028 610000 655345 528859 977180 981511 736890 907615 981470 832396 522749 915462 520386 560059 999820 861269 885222 730715 922872 512435 755618 830819 540481 568244 785101 788528 671037 883714 939066 757357 589805 748616 608636 779235 812950 651366 648847 569143 989471 582453 614569 788521 736992 557121 592632 799630 882332 661964 653586 518066 692788 555141 571502 605594 809102 974894 585315 870513 715999 936045 600069 867719 711281 919177 851572 815670 959383 982178 682846 572429 840339 848830 705846 537976 930101 654142 746860 974982 573138 651105 599043 865214 633265 808565 730521 543796 633620 854888 721484 978465 621752 947125 828741 686046 720733 770340 701138 903325 952251 996820 894299 754491 542607 659808 958121 782364 547569 621501 995457 835563 756993 939961 715434 928835 965190 564635 629830 818703 817933 915195 665960 661639 572075 523335 594502 746948 728695 542281 795702 921534 625720 553630 512393 948765 700953 726264 863276 668593 761456 506989 514877 951139 720213 647608 535653 560918 886011 998099 580647 673905 517495 620598 680156 914605 977308 903877 530835 905342 947266 982985 812692 944943 790521 893759 680378 558997 771612 516888 702255 788888 970384 991212 645635 711783 850675 900942 631662 808768 569739 666508 808254 923308 739326 693692 814547 677240 974350 960758 935288 836460 690104 848250 968601 743510 733945 641168 955567 559248 562385 758181 545067 680787 799533 887581 892310 827887 637819 834665 614484 914996 666949 510235 951993 951127 842008 614886 908673 834739 926668 698797 769469 535847 872432 901686 518981 782507 719849 802633 809333 993892 732636 934457 750782 827138 600650 642326 923540 830148 672651 591295 634204 817532 804777 852459 565269 711890 535683 622401 591133 717607 924288 755633 659049 819361 511034 914718 758453 722516 988650 767740 627113 977611 793289 787841 967531 656103 952046 834488 572028 569580 647736 821162 879970 649614 586920 899175 615553 730440 882060 712266 779594 601662 783798 901710 893762 823170 724259 666580 520691 919435 757327 808889 708408 695404 606831 818274 632509 541155 658585 675919 834540 717511 857203 682408 579992 739796 593641 739187 984375 601929 794407 638329 680779 708035 548352 540287 927406 503756 732015 944322 678441 924471 719422 581294 766779 902583 887315 783507 971975 801083 751706 511285 871904 765577 696741 840987 501544 611941 881764 844115 967326 991827 537554 912247 790479 703167 987664 707437 877837 637914 855774 542804 643504 984146 545042 622979 929850 924767 700353 699103 501245 699984 989403 818065 509008 525729 663604 970666 950963 985228 984673 568390 774063 635907 727898 803491 893543 698815 598009 572044 526978 822751 518571 764700 866750 540291 880854 854781 739308 657893 963116 838439 524705 947271 856233 706549 734808 630230 856610 753025 773642 774145 912319 649257 528305 840265 833394 839342 563885 752046 602229 935805 820814 975687 745004 920496 838105 730055 850086 580350 650904 568208 944347 732705 635799 697667 563317 919839 702316 531657 976135 877456 854045 588495 651211 706770 767832 981304 673561 804897 664482 865241 949725 733228 869390 834451 661231 828488 586561 885896 552532 986150 534448 692273 764345 670900 717034 551208 548339 833851 728612 502896 824121 541163 615694 733394 664425 743799 944489 505738 919480 743062 847372 986093 816459 531636 946815 957091 994977 814790 680175 535583 564548 641453 673817 636960 894972 699841 939980 553246 975544 957314 794834 637150 804071 949165 521175 709267 891597 646024 924179 930599 593796 954560 553656 507605 604961 531163 991260 721962 575522 713323 726061 902203 939050 998349 766946 579454 659653 624152 765268 694440 735740 931767 546185 847932 921051 814289 572136 711855 748924 681941 986872 843226 570716 997920 513497 768099 944320 564756 604959 827734 833719 865825 870399 904148 705518 891737 925836 767254 733379 506273 942595 910765 946298 531563 791932 869065 781689 857179 809287 632211 629168 502852 826598 901273 576007 689490 746123 551202 690185 598174 554209 793389 801973 621841 798431 655129 869996 539328 676547 518166 642694 666456 510716 583507 951150 663870 505401 754690 594177 806289 812402 556697 901654 642880 551451 832708 687003 603426 559821 585858 924773 729988 769370 958221 614258 838736 734461 964166 915086 541649 959205 720317 765717 682764 797453 539266 820793 868664 823983 879256 668268 897886 700314 766993 912267 518953 683585 935808 832596 571700 551942 546323 956861 691584 844861 981838 506109 881681 941856 835593 799958 882037 627996 832140 832121 891075 919687 549954 852285 818736 549129 937527 915279 876050 630923 740088 983456 930818 659221 579165 793244 684093 608900 552164 821786 847157 539167 844157 814623 623661 723044 969056 960342 926641 951172 882382 923143 885075 783363 832794 569245 819688 646357 944579 848086 992672 801189 648284 914232 561027 828638 701683 700966 788202 906172 668262 781452 693718 774835 845413 978459 945477 919519 759513 808529 924424 611041 970105 971584 516268 583489 550323 721858 809937 745242 735799 581130 507457 947135 859195 980169 974952 956180 812578 539341 989433 908295 904810 824325 861087 638472 606148 537838 735737 911833 797236 733374 507160 703981 764679 761806 893967 804134 810390 786869 860711 639425 966889 830417 687923 843846 935750 933404 620772 720252 991379 643517 651006 868870 717312 665426 611899 880752 567220 634548 890866 619603 867808 600296 689438 740428 505791 929736 885299 718431 666158 967586 676049 786609 613861 913512 809400 805471 636187 502632 829483 713323 887927 700197 893956 830562 506587 746350 841602 916407 989800 511934 815100 501509 952124 751275 868657 644880 503438 962860 615202 888575 616098 693879 592805 808559 973043 749541 655028 685219 914060 893120 814889 941923 722376 747653 597126 625096 618765 735246 578454 824234 955367 514906 920486 555292 726394 504851 825030 755901 637931 700229 966429 665821 603999 622182 580645 991103 661069 859199 515762 875364 918232 786688 673609 826646 785193 675715 897175 873261 845290 526829 983527 847091 865716 589936 626886 817758 562137 656132 721580 826115 859892 832457 579542 690492 518960 635490 742047 784129 614893 864736 690371 807241 992881 841723 885075 702147 937155 725777 688573 984909 922916 742377 850705 891901 942956 785059 861973 864771 526188 976784 604147 522208 690254 901718 852920 891969 695393 843362 812301 801593 591778 989969 985434 951248 677496 693174 811530 817145 609355 990796 623601 658951 533710 729728 606685 529646 729504 749872 561232