1000 123
985881 432497 780440 566542 973470 47716 878935 742592 94165 414400 503400 958400 635499 729582 525364 561488 640306 548716 938266 699109 17458 824348 701568 167184 349466 159677 566028 635850 797445 52447 31504 994524 69024 820500 786171 631691 741955 889630 584190 789390 566946 551565 948097 736336 260590 183752 644780 136019 358013 643841 552398 564655 222394 166268 407105 117412 26149 162525 37176 599800 385923 169127 173271 803936 147371 292670 784106 706367 887075 263862 330416 179332 973700 926900 609667 334864 818011 64919 793352 984312 772800 411714 515158 17143 164915 149296 321036 343471 704692 285492 253084 395909 855254 228121 735702 453416 131566 387005 725811 699749 284195 130467 388732 231741 24624 247118 843664 222708 315503 652272 731616 990275 423280 353165 421800 350535 261039 936044 409174 32850 492750 600754 873451 565200 259000 693560 405860 491260 948398 537724 827258 645233 943042 968994 905034 397969 406846 332469 260883 125745 279770 429005 580232 676938 191900 769032 442380 855589 434836 534273 743505 804825 947520 560067 72004 969516 740096 600848 77995 194348 625609 277780 601528 936904 979786 120632 661504 167656 389424 323886 818748 281862 459742 272412 149454 329304 49672 665811 392472 5175 600093 482421 94869 819708 646438 943398 861404 631561 191061 964574 349005 447214 793546 927077 182015 772018 591721 938262 259818 513912 330848 536151 340263 179827 722799 871416 875511 53781 158335 765273 81952 859077 894400 16510 676260 441116 391240 364694 811276 426645 338821 523418 885725 719585 723150 973773 616255 736258 768930 906954 629344 408818 333416 386971 999212 890908 525684 82857 614718 574002 42960 631609 277706 817582 132274 393214 415581 429843 489883 448487 150007 645954 505175 507716 493089 10490 231829 17905 879138 2106 604260 220816 475968 347874 393828 331002 391604 778295 700040 944796 130076 412456 5147 255075 416713 553268 598700 880299 1869 946515 660380 295805 556035 242080 247656 733788 671117 106523 220734 705024 953210 233712 3857 910178 777502 16416 390792 605042 764951 689442 200709 508063 57961 558227 187150 981160 197904 118944 68971 875738 416905 951509 819036 215764 735007 512965 128625 318302 654139 630091 244902 414474 731612 17493 413952 91232 801982 343539 937251 569820 440762 108262 72039 863247 431046 830351 727672 794871 98541 568757 317073 377797 531650 579250 782666 116900 905275 129029 272300 949004 454471 678020 148045 631770 858690 504378 518492 959112 940774 915343 473902 169598 5495 970541 181181 799282 493280 218504 461838 760180 686199 217507 229845 181005 942150 262290 707355 176364 472395 29869 161833 595792 871640 116504 662475 958238 934749 960502 674389 403841 661410 325450 585925 425942 834227 459546 75637 532950 609562 403892 44160 576787 62225 314178 20425 727990 339485 778385 16684 597915 702177 727264 34256 91935 528660 655740 663480 363600 586980 502335 786595 257335 313845 309925 588049 285131 603152 13552 677754 20034 931014 574478 262460 58197 117747 583065 881685 3213 922698 698796 53424 115606 172032 856368 444035 734029 655120 274764 809766 264634 187270 53319 703330 897480 921405 402783 310368 698044 741272 576353 632499 536935 67620 720545 731815 588990 289367 472265 868985 924305 159045 34114 29670 655627 622965 877415 550228 883318 620404 227384 248368 695052 948537 982034 716392 560538 225884 107429 459277 658510 317961 417039 363136 46592 816704 422016 316709 800778 410292 125815 146502 863520 953120 583625 935660 19803 632466 528777 473150 814629 741239 912363 131576 413490 48509 593222 364683 448609 314433 18645 588399 547853 761909 422895 222937 630795 969217 983730 645414 53823 949242 956232 215118 574362 202251 1377 219402 705024 447541 227088 718493 431680 38000 876660 475570 687990 148155 288010 692532 759583 770108 524763 234024 207235 312528 991020 433621 383807 507079 214124 747842 392229 471242 378100 461890 473720 214370 546841 473942 178092 318288 241979 166288 480776 37960 94572 375136 666216 835312 869706 556947 659554 959823 704007 865345 83825 6523 199320 68172 344149 187473 62348 18447 625339 537744 402831 660257 700506 332618 188405 247962 266747 859909 602225 855933 952068 892944 236739 791440 203216 164528 953206 51754 297868 513924 601997 26216 441152 865468 147737 522682 623176 41724 606936 959376 986976 582961 354568 617560 402620 451335 356115 492473 589200 410800 792567 81328 454896 607091 825084 572598 55224 775024 658676 74576 608631 527635 488062 463888 483638 298654 983575 144767 195920 628366 111744 60768 219018 210388 260148 666163 396469 389999 88409 901392 61823 883395 908300 58421 977349 77855 894815 782285 168714 612556 68804 417186 75999 603847 517213 554144 430050 726889 696315 897310 359386 776741 5884 980048 55898 101499 222121 659153 45904 579130 646431 56020 364665 405237 860275 116788 538384 364180 275816 548872 1824 675562 548568 214936 298583 763666 404412 122476 246962 368013 768490 299885 309875 598645 697805 665645 189860 690119 679715 696130 207030 816730 937665 116888 679045 252000 871610 190445 145125 751545 234783 161356 53783 226400 993467 984789 442688 325577 49020 743337 678261 21033 575271 226197 850815 475272 348496 100269 216863 367087 157323 525097 935694 868502 472013 25878 876447 799432 758763 111111 19591 247148 837618 84966 594701 801450 369352 321331 840849 871320 423717 932823 322989 183032 552932 377420 118027 998910 472032 254364 38768 547916 101844 679650 750858 812747 635076 455 545012 637023 781830 241605 8968 448872 183726 528134 283374 676202 294606 799465 443484 238329 613116 734227 968184 314921 246582 946073 663955 420546 45787 585947 862078 873259 215038 86510 156562 515690 425537 298072 374736 616535 801864 71982 166405 334414 45566 220945 16641 764067 915559 823297 603652 529451 198947 85297 723221 191915 337045 187813 451714 744201 454656 379461 200915 797220 532098 189630 838215 887173 333512 985008 276342 368104 604310 939395 435269 35887 865073 686075 551200 664181 78720 428890 723520 691832 26928 886580 804816 260820 87220 520136 505154 45548 641745 345548 493724 78994 693046 721808 529536 38415 770073 898517 222596 499893 793713 957223 427293 28171 275418 596700 663867 410499 518976 555652 388178 502652 292247 265000 690911 788875 887750 162975 507313 464062 231663 858529 874905 679242 724505 218080 964782 286324 570204 119991 103053 721811 540594 826298 62140 508928 166992 352313 478682 820846 620801 371804 190851 568852 336114 954789 225178 211154 525389 441339 419181 110050 905200 839480 438630 207576 710208 123930 989655 8670 685465 552783 16575 519025 916678 391666 899111 987256 843101 575228 743373 789955 778629 621552 629004 688 131566 224460 262066 567762 491267 344095 478406 705004 909189 367213 736953 418418 440230 807707 987279 911981 166858 526180 629755 366196 842023 81510 539881 515280 718200 158634 118062 322182 620627 874440 883050 38402 646141