1000
27344 145576 762886 127591 1032779 920683 488236 519763 133955 244136 281758 553715 391028 970437 552618 235602 616607 431928 388606 103252 160996 788462 50474 573413 58087 569275 490587 1014229 733163 301844 441781 689296 739132 877951 308432 430108 998406 940968 796209 990999 533355 259079 344979 106638 808153 631512 749689 796074 775427 806340 696545 506561 833818 223526 427815 481822 297782 275787 222423 377971 253243 420455 585901 98716 575087 956440 649635 850098 574976 441678 268708 162905 924072 929967 646955 858007 1043750 111223 803872 802303 528730 510524 931841 992645 428578 367600 154696 185287 710833 621516 36231 13726 257635 628322 724392 413906 925342 998209 342568 246986 302780 609246 54092 486002 677665 45471 980852 15879 268317 543213 910795 718167 411666 501929 104882 949609 747894 621535 1038063 745011 525983 219941 135269 714003 833837 270144 537877 279505 186179 168342 116658 839017 463052 326456 531667 412144 613817 692184 740142 735078 404132 474311 969637 981688 94356 199166 20767 1029840 456541 394456 540526 436969 571534 473658 866659 149017 639740 385397 11719 8477 804513 226799 670406 221313 132074 700365 490805 973099 681434 195262 740975 177182 951047 991383 195209 304991 493759 530001 434189 549601 914537 44384 490274 992961 631683 887922 252634 239616 483179 480995 675957 900430 955431 742217 701189 40755 374917 812456 429365 365597 592161 445824 593179 902125 725243 765790 561281 792403 268575 287009 838865 674198 648298 682779 48691 405538 1004724 780964 3740 192752 684162 490349 74286 110081 980603 184682 787745 430995 1014686 705393 1003664 633887 887620 443537 243736 336155 571478 966647 342204 291169 274841 84845 656279 978781 191375 744357 879756 884066 244434 920455 562713 431257 223640 606540 330338 744609 603414 842113 737001 450691 260946 813369 318311 633714 925760 606384 353154 264874 484631 659490 497544 251605 614806 604985 777427 268908 38437 785545 840170 708743 78248 363873 464026 814661 54440 504480 1039929 305545 725845 409473 684401 325050 675664 87154 741071 144386 438133 760809 311217 49021 437917 595742 944608 503031 246024 693827 858841 252736 294182 528432 828064 300742 389401 54352 293939 89996 760795 83745 142618 291501 195947 122977 1022003 198505 197176 201078 379414 684301 349387 217923 836103 866155 78599 514031 135403 557494 679152 467961 498070 957905 420611 814954 91903 281858 157530 939470 1022668 644429 475096 155344 336849 42336 371266 793681 668065 295901 566726 243403 953933 342413 881585 844960 921046 891655 402134 922143 939379 1002136 930428 810688 419461 754138 395317 999619 828778 502163 567741 596954 2302 645946 963323 793822 285255 522654 17456 146702 912972 696638 1019741 702820 230538 246345 1024461 982105 499775 343920 863112 572079 366054 34449 1032176 645371 167733 468940 761940 567013 658377 604615 1020699 573606 71821 417295 254686 278365 346146 472731 688903 419851 773659 207757 659588 167712 560384 701592 891373 23301 134611 88175 737218 402377 469092 515838 571762 293815 334682 150167 822787 1026729 808771 597 203580 134354 282259 413235 67642 518193 89708 724038 209072 481596 560278 197099 739647 1010138 922454 63696 270546 502592 931788 126165 306 267149 176534 710762 23081 500019 777872 623563 670296 732755 810862 120908 741770 577758 815268 542521 4461 243954 264111 160842 191890 803787 746680 252872 955570 792830 1026987 1032584 697964 37241 732143 485750 915446 847300 172232 680500 405318 63873 372482 644793 607114 898425 401628 660457 339151 544770 980440 297751 810227 1039503 1014063 737766 586158 237063 412843 499684 837586 215571 429408 366546 413845 979115 736789 432994 151586 873218 262156 608943 718868 785801 712380 468279 821383 591190 738973 157004 877428 725356 972267 60129 200404 931962 323125 788998 168052 844379 903133 536642 40173 634440 581894 595549 458657 968411 613549 741034 462344 968929 925771 1007393 479848 124270 97151 2454 448450 147489 763579 179996 378163 833730 643243 558676 68600 999554 341403 860807 544412 611927 212220 500029 168551 674367 467744 236711 398349 397416 500393 104678 153130 379750 384197 805964 159380 906953 968252 869177 991950 753363 676071 264853 584477 230088 396647 75786 640159 13142 384544 213749 690633 977522 882855 121498 711328 649371 35273 847424 620276 265624 909859 914272 351869 861547 530933 901239 222022 641626 1041505 20851 576490 984699 626439 63181 96480 23355 1009967 868905 1029829 1015009 832917 623832 985447 314794 152813 52762 964859 922799 241697 62319 74566 578350 618329 335493 456333 333323 799201 658732 861253 164805 452852 122767 721189 743840 242266 328309 594139 626672 238275 776947 726878 196767 663980 368548 733904 286423 734526 51065 494724 1003002 518793 249042 636904 644961 922021 908384 1000729 283820 635597 35822 103882 222243 317381 523326 368922 1032863 264060 126503 619122 376962 864643 394180 974473 238436 380199 397871 755432 795211 361171 731146 672207 262066 996007 643485 588247 674520 301011 990849 119353 827105 410864 84329 505503 319148 384425 565770 955481 824044 258111 411251 487079 241773 431319 12735 1004505 32150 850069 12301 388012 764996 775204 310622 568709 114973 145624 345646 501821 498860 1022931 936372 995472 124665 988300 205570 82105 530457 249950 995670 843170 880131 10424 300878 603827 988467 542441 612807 426727 1010635 768292 871691 86387 223084 260113 370035 363144 154018 850316 940794 609804 250648 972604 611307 162611 37769 749631 571454 497392 177306 1013187 435330 665212 829986 551591 318269 527851 1003897 1044950 636561 7148 746587 53389 1861 835397 539895 328922 583849 962069 196467 903868 660688 738172 358940 898865 735256 200421 891966 892235 1017900 334491 772542 17245 550961 805170 120100 765717 430119 991614 489806 807450 693818 365558 870931 305371 48302 117289 692908 619617 1032933 318339 563698 1004964 4445 85790 852467 538257 277935 746487 934363 402274 251694 421022 306017 401890 846767 156676 713210 338885 589238 295746 365828 318765 622831 507100 528781 646019 843507 147593 1032768 227052 796906 811029 179487 578884 426283 190171 550637 515359 334376 899233 26559 1031876 320382 401675 967008 316249 1028344 484863 596803 156705 783398 776895 515911 866759 1012999 348470 612505 980891 852590 726833 235900 892401 691830 103605 822915 753025 331078 949842 664173 989350 910026 462611 258085 1006571 78970 622901 296065 133488 800933 787932 413027 1009433 606607 1017681 844346 394061 1035947 625520 815046 399157 446485 523850 226116 564896 704083 122640 957813 578703 665060 817263 180558 724563 620720 269737 181319 861697 581853 254987 740052 831720 257984 721578 845277 272129 735467 1036491 641512 716295 673001 662905 450227 163600 467969 1026917 602282 757411 825580 494736 633590 45720 407500 602726 6501 535332 407686 899467 697370 610332 958717 239361 164116 489748 127250 744509 340114 654693 300859 238180 790086 351073 743732 480898 601846 940938 574687 374358 943391 617870 530600 658638 220658 133230 93498