1000
332183 130500 165580 973632 483644 262286 460026 774037 236055 925771 214729 677333 702973 967602 993576 401837 844839 653796 759130 403519 309856 329941 799031 15751 35975 631636 457240 394316 943802 476277 934178 160202 50872 657810 987684 847794 951339 917209 55334 228137 920872 581011 604052 588617 388645 736161 1033149 383168 841294 105685 158794 319951 876882 951767 198176 853216 814104 216943 995719 942789 398334 372684 652599 464457 808096 218355 353230 920711 485926 211454 291203 393392 295114 530331 940330 617596 680814 294406 359247 931345 349611 626024 339786 126243 641322 601102 481255 499306 1046430 208565 1031173 965702 79023 730609 797925 606055 530802 238063 477549 972788 107872 302967 792193 321532 987840 649059 774495 697870 539347 57715 360970 653854 51514 948017 1032247 700992 214228 589383 682048 879661 309059 989086 1042763 873247 765803 231509 299009 718280 359083 511981 577185 256529 98735 868230 279158 710611 347835 614131 1020403 43247 642359 789624 745457 361644 946815 580774 1003440 838361 212837 536831 350655 552290 66205 246437 331948 914723 11635 114994 737560 1040839 675523 314705 545421 702312 857901 134472 267498 99404 527748 443322 296396 827248 1035362 613918 73984 5591 331845 257977 977651 483528 559191 866961 773328 653485 314467 296292 356528 715393 348010 1039552 82733 289310 805609 413957 103624 873370 1041167 691386 910852 464395 747697 279427 550013 938264 535351 1009316 331213 647552 459452 770610 863454 145792 715369 692196 304986 605257 136743 619777 785148 820808 102589 333697 877169 761112 38669 227396 790612 618498 515094 42852 599862 70741 198169 320868 317803 98740 397156 560651 242904 339790 638518 407584 882581 51519 659620 751318 774541 485752 990967 409910 497706 180863 740103 245902 745806 824508 700190 810887 1025269 317574 570423 516948 108391 578004 88981 960549 83597 456292 49504 784132 947704 623118 901596 961794 880200 178624 723900 837176 689522 938339 2527 968683 5593 252290 232242 496460 137382 780530 1015634 897498 50352 272742 546657 356863 138743 543596 239671 524450 755060 205210 535929 394760 68035 302769 587272 444152 798425 341922 152391 749064 741789 961559 833014 397981 895377 12523 23055 757657 73892 820973 1041316 965409 581263 735653 622395 981537 442651 195937 508609 550862 466466 152778 959161 161865 1008908 826194 357588 585419 175872 765089 136932 829736 538179 280826 455585 475729 679954 482278 549907 266450 601419 417840 16903 422142 865996 374691 603331 882034 648601 386059 901376 560599 1041769 328602 405239 213019 1038414 425904 488632 264290 628898 185626 543483 795394 554341 832184 761869 196060 387164 731368 1031902 511206 952723 237165 742038 278842 893814 362833 856513 427622 645482 151389 592462 435857 660619 445909 927273 150506 83391 178073 102291 1030783 254238 28830 695290 721163 693816 679590 351557 931673 56226 887854 287643 1002472 295752 267605 317752 938108 274218 703783 91347 339286 752453 225002 555514 1000913 12782 720802 895617 491469 1032759 656198 844485 193144 349726 879679 509640 193211 910159 616467 599010 646166 1042504 849753 890507 506926 1000544 130149 758040 972412 314298 79412 360178 891376 788295 275140 746350 905221 797933 765804 886654 353429 139631 31960 676016 239339 328928 467808 370553 950267 602088 635547 174940 933273 128471 609813 151902 741222 469347 146169 289032 410615 202070 590298 547927 1011338 884432 714223 917348 863533 992240 66762 276586 541689 677917 995201 388185 140188 310501 814662 707422 196887 515159 710627 220092 932466 745997 379966 282085 910919 126457 48445 183671 559656 971914 290576 504361 1013771 675804 1018640 591259 146069 612590 382206 677145 338489 405813 651115 300539 30448 163960 661578 57257 385008 60173 728948 253071 614133 465899 821759 481878 192405 523925 647437 199389 261177 580751 32312 834014 128223 901603 225851 722701 639697 993942 461853 684701 787220 108692 733824 585539 291392 538696 533255 568592 516750 579836 1031172 431453 389278 59477 962500 755035 73598 113319 247080 398030 15327 53083 782012 317016 852284 329587 1025993 644481 747945 446776 1017773 299327 146795 306052 393136 319714 759423 655233 21958 338902 808251 599803 182695 1015659 997060 380386 504507 219805 10348 945338 21526 637093 287219 317944 193411 129233 650578 102629 613423 756016 895921 88909 553329 920876 593398 913657 857273 256481 1047747 470249 321767 182397 603012 400821 681243 1000097 219936 342631 716413 360823 119719 169003 373829 503338 738137 478308 255919 1017239 814991 412181 819910 248576 522667 951158 84284 635552 834170 725572 454638 952237 201633 636410 109441 263534 636526 390236 956102 57227 266741 725956 601358 154524 818981 755829 416317 896305 839700 571629 303561 119231 753816 248966 347081 485557 251273 706135 930502 941202 889279 454025 253307 955039 1007925 983442 352280 31305 363111 370985 826267 517784 330482 555680 771625 948759 7838 216169 905165 408409 938265 933036 976458 325327 252529 615632 484822 557825 399863 791562 930519 758008 245633 3190 595533 926275 206939 81158 879948 1001598 871051 881660 1029778 532418 755212 16294 418242 669249 129963 890248 67888 298657 451609 327012 289885 687437 66247 103675 341062 625866 221092 216365 299234 667336 933878 290595 1001404 955491 410550 80068 1018175 168790 871045 674700 513038 967652 67269 343544 857850 284406 751175 525073 908685 638004 937423 717524 168185 821691 175859 439825 845963 853125 305482 719434 457548 973356 989081 340618 943478 993509 11473 254010 21512 260541 909535 476452 907654 829910 695885 542335 1005587 721239 853098 326889 847667 412824 333972 508589 875898 739444 1035784 325029 843227 542852 847098 81553 577210 770976 724671 315312 452678 484162 854913 610743 139975 322947 20548 456249 795205 821706 338946 807927 681478 394865 870946 199599 388320 866638 135058 41384 349739 398148 16079 168609 774828 35401 594742 184012 909263 633437 196273 1043043 282717 962633 592937 157848 173892 922776 450284 18373 426480 699436 1048003 56652 547891 741115 312645 642520 858102 64133 433796 398166 137146 813239 117616 4333 1032517 509634 666617 771585 844945 828882 885628 960438 312422 885780 370662 45413 1007836 367718 167967 165541 1034293 760102 515473 76684 182237 737850 16380 1011708 860928 887602 909498 987528 639467 360202 590762 554000 724955 669857 585475 592334 861380 674544 239138 671377 1020957 320344 853638 837819 222965 210283 186023 682212 460191 340737 830518 971136 652945 307254 375406 963516 149691 101548 18407 537096 411288 616221 607865 583133 779045 898548 399227 494657 744398 181187 266378 748956 245351 602559 780712 590205 989908 1015191 508184 714837 519889 392049 534673 990529 513128 712159 951693 15980 459715 204566 69298 135877 973943 714001 562207 815463 765595 958490 140244 524810 447030 745876 403185 761004 545764 882558 22317 946574 657983 274312 928550 806937 268086 281091 214359 677737 409033 948544 246632 57667 987183 622401 699874 365139 521918 980515 786507 863629 322742