1000
501584 535135 125600 87225 670666 358218 366715 107837 781483 614185 471361 332285 295527 572144 343426 821751 977463 99134 286625 687358 95518 849530 888969 199950 407995 385077 560531 166510 482772 960012 396443 932548 146734 955550 286920 619812 111909 198190 446269 458759 75270 646192 782692 325117 839033 178552 780795 839919 248339 470939 818666 642383 993202 192887 91400 695046 571570 10670 562940 730454 960423 130215 618113 198877 791721 364405 336744 326348 80136 959207 561710 142430 799405 662948 182811 587086 854192 773112 308341 56038 244333 145086 246227 993957 468342 397166 466620 394897 463045 796246 967794 319324 626220 558526 717250 787120 719137 549666 89887 655934 695830 618687 475121 344277 756013 50074 474820 508694 168523 868399 363929 34442 662101 979859 735690 948986 430489 385103 503276 117747 48599 947734 679760 831447 846740 452836 608286 644423 539701 939921 564299 73288 157596 544667 901714 15345 575343 333815 164942 996067 187659 867610 838551 605085 526422 474154 656564 730002 867308 470046 643139 447454 122545 811694 306626 680762 566687 911653 658774 983553 192257 604387 981039 58759 742169 495820 509822 872313 715768 181041 462526 470960 895368 64568 76324 863551 190201 767500 581475 575170 844602 355979 281106 733509 307322 875310 159301 796828 308882 924114 689391 282904 943767 252901 764312 108319 804409 621433 920905 397480 463786 399248 280054 870752 853540 643720 874487 171043 334470 640046 286186 738269 506284 137504 765201 91020 53490 766390 251830 624845 174283 369978 973945 286498 389331 235928 541432 733561 777298 461427 709551 838771 934023 936554 233122 648441 202189 680143 483409 154397 968381 512572 749574 488712 74405 299856 396573 400727 639734 253360 301369 125616 841968 19633 239357 3972 452162 544555 142842 461712 171946 946341 403467 209733 69228 881707 640455 772662 659455 139533 606579 706060 429218 446477 153651 111530 849137 718876 429489 308990 172869 245285 728210 775592 569132 534087 665688 710598 383605 810493 602116 835614 577583 397345 483485 289545 640275 464075 523906 727659 521603 878211 400617 984122 382384 143789 883544 907385 208771 661056 71352 227800 587827 791845 655766 566834 191109 464978 886115 947271 763127 306088 155944 413743 661570 526228 383570 623004 246164 53654 608452 513317 663025 643128 475257 412285 821411 947156 527515 192560 609733 783496 482683 334765 647676 83350 910573 7035 121348 254567 986938 520507 498320 944298 244147 770189 169390 435409 490806 520537 314015 161064 322188 645139 536227 71859 893371 679881 67952 839858 876939 298961 586564 133928 777128 573125 943594 450728 22297 119507 351429 235737 507589 502452 824905 278716 509673 494681 924652 617930 145403 58190 99080 437549 796345 154247 171857 692597 170949 741865 771788 445794 926328 574130 751939 150703 21462 651744 894898 365537 223723 443193 451051 632000 440623 230873 306720 503554 798584 192561 829088 957455 640694 77643 684733 674981 865272 587401 178677 924169 277106 818821 910827 29493 873312 381217 796651 662803 235576 45104 749024 439964 450767 32658 568042 557494 231717 309162 835737 453649 160079 484805 862559 728279 223143 186190 982473 805854 66441 6975 743577 76024 634085 396950 791094 496103 118650 99011 489625 889831 392502 993320 581537 426812 342465 458091 428354 16977 779672 606344 632046 604468 846479 8004 83044 595319 92329 756760 731926 903288 640457 990970 631571 348232 117252 228088 46747 391402 266219 121922 677900 442020 418379 502132 296113 219519 240983 805307 336065 905835 436421 257050 243865 72098 313223 414384 626655 614116 400967 927904 500834 181029 531046 633020 185800 831495 55097 329691 640068 901791 123031 859985 286653 320219 192485 342899 624573 852136 191603 675752 173378 10080 7015 661561 547539 613256 218884 371790 707623 230837 254891 603791 685081 993446 385056 542371 327528 507131 229236 984833 861461 854298 699215 738854 319177 915909 547216 52608 126851 499352 942744 186485 400618 6348 749635 485765 747534 625276 425155 563694 618309 282276 713060 454225 508654 835534 552463 843907 556142 247093 874411 742227 329457 716573 208030 199818 856895 11196 268092 933873 191007 476469 945943 970196 56236 461898 375583 661182 376443 146123 996857 689193 729195 995845 787559 914633 23689 342915 86368 178127 949161 813954 678490 416202 990709 596894 65854 699781 59351 778810 93764 54932 33230 239423 355860 175206 756813 834615 49288 384956 294982 854388 201933 463010 488891 989591 443597 186060 110428 291834 742995 701161 162221 860909 782461 86716 119999 244157 892199 711283 164218 782106 716004 249645 697832 384773 30287 465451 697048 473015 388304 119854 691998 69283 511452 615488 424125 272179 599510 235180 477246 599157 981697 84762 429089 931783 780441 99346 320231 47894 509692 722486 487288 975059 779707 117501 57243 649696 530134 20499 649770 616227 463311 594269 84455 750651 599610 892601 139762 242904 126759 794299 660644 322386 964950 516304 561654 461024 719672 65302 522437 38256 944094 237159 422486 702279 882897 23611 812032 912006 119441 535540 965933 394015 798108 802223 317448 498949 343724 55945 318783 691675 849926 361336 25247 659635 558353 698795 949931 773706 100522 861412 985774 886015 424284 774729 441857 698991 576722 98715 490883 190131 765371 221389 574608 826767 369630 3355 564193 555271 824240 882743 722294 799042 546726 199845 763799 949650 330633 850861 562059 85528 876478 630134 297513 902576 382267 870216 95569 91053 365453 239171 450606 643132 138211 804485 983004 825489 607926 722936 326035 801331 324728 165841 189533 136168 947988 338998 897177 671804 553636 706754 944302 502811 454158 779549 373070 39966 453180 74288 11920 394943 706490 106970 876141 570689 611375 526894 276443 191820 396177 751862 432440 759463 331881 713709 637853 664848 737677 573596 274381 446092 202345 516356 221052 22505 693307 983363 455974 890837 475276 953229 897332 517765 10350 129723 780545 413111 261401 146310 118380 618019 70686 146648 41000 592638 535516 350446 62742 737495 552875 464062 572534 33129 954855 45163 94820 532182 906783 180905 117871 688459 489939 88943 536350 757250 640689 500667 5010 751328 867952 936044 750391 686974 420884 229435 637437 104437 828582 915773 537807 97156 983794 336448 296885 334166 192393 574308 846250 810041 860586 577136 258553 306739 741676 78968 791645 801751 914271 178664 218840 306900 913815 685036 992179 872193 689319 587998 35588 739079 307147 265037 214780 877492 573766 282429 780808 391073 999310 900541 334102 524905 773826 642628 105918 260204 678117 536463 604013 730249 100999 888202 919478 942011 584905 697857 241571 537814 571675 75728 377425 581402 270402 269210 323522 602800 819253 159303 185802 386341 163080 336243 995271 236223 318750 113598 215998 704003 950019 90211 992374 12345 423891 119394 432483 659466 770259 794692 474518 938596 216753 811642 133038 356870 220672 814886 172013 187994 169840 589995