1000
38130 769984 487578 532262 221297 183031 181270 740739 138322 904973 896544 209367 498608 621701 565472 804109 471874 846123 376873 534172 277561 988875 592741 865701 859 338325 827522 502698 537889 812040 439999 194719 916381 540539 337776 728351 431229 758967 915677 205276 97270 429235 774149 460319 731355 181795 460872 964428 746240 564848 501377 571711 565086 742305 52083 860073 763244 905748 587235 102341 280767 410312 422280 707264 83757 520963 795781 159747 262032 819810 90746 935204 116301 943681 610071 236487 190807 808235 740358 923988 440926 344339 930857 561805 62518 502727 887517 652598 589745 291195 723303 767655 605366 555154 519957 40466 27138 357731 392725 813455 130020 453416 844903 274017 129939 898737 352715 58556 625424 675860 11307 870323 880865 977121 16527 841165 199203 169956 769107 689461 511829 879618 364897 603951 428961 500330 795749 261752 444191 9111 810245 887788 998047 285427 754622 931642 609265 825736 755411 587548 260146 358821 175268 582650 297718 45772 553745 866333 847811 765878 276757 928086 930391 152222 818341 134455 370590 26609 816080 845991 28921 927100 989454 868847 558465 229659 670495 507350 991618 758080 54747 866596 544231 411301 602560 862535 258285 290947 778655 654238 421256 349146 794248 481866 77870 87008 123003 105254 745771 244346 602739 644171 980099 476935 173410 589340 860413 825624 448166 422693 493230 445053 225250 369553 610370 682567 405230 689669 658278 934064 324127 171373 304228 920191 985638 179231 91780 660564 616059 365271 41017 193406 259750 233489 369316 364084 892133 178435 50528 138455 499653 202322 718267 240641 61668 332688 807763 999892 474142 502946 693780 868566 717463 770848 75223 461319 124798 825711 309543 376858 13335 963914 552456 602078 883380 528218 675172 130776 47282 729801 932104 846110 624466 616541 802933 287145 863313 611763 917699 858410 28624 627664 315555 47865 686408 299704 861513 384735 970912 496571 375454 285276 576713 311391 299 700611 705703 452117 222320 177684 955830 323141 381262 131685 62919 676517 613851 721142 139251 416142 758295 915384 341645 11930 915401 119623 199038 975462 983942 325490 803898 913378 558814 306255 753537 560341 689800 848613 108501 607360 20669 153219 619346 450493 990652 272120 648097 749143 484377 344014 49786 982809 548322 226691 47112 554727 868598 678586 406817 647399 288593 939405 420577 496639 649220 515991 473259 740366 221936 878777 434887 649199 951266 799293 142805 969959 625137 742822 273019 31202 186322 379968 135496 52324 762008 549356 105259 170220 698266 634184 397124 864044 262444 910125 289434 665292 808711 542060 215025 811575 888104 358144 651809 988556 561636 300378 557224 494589 630735 10122 874266 808205 893923 920242 357584 736109 884294 128717 854471 876678 791995 913521 813419 557251 47918 77448 780095 266013 830642 167177 844094 872060 314510 317912 534955 101728 584392 640909 846835 889867 995716 830192 450087 331143 817603 563869 761228 420765 156951 971957 302680 996395 483859 460112 844786 280903 993414 990768 818075 765934 723755 395832 946284 525035 947594 238151 216632 207751 226609 796789 446856 24911 332365 411948 445170 182930 856700 499012 321673 566209 531949 698145 224643 282810 78104 424355 107674 241148 545817 287478 308082 776865 62174 308355 595066 963195 782010 365547 781222 832187 228734 164879 863939 52365 274360 630198 744837 252201 856846 524795 900228 744804 880635 334972 746573 110822 487744 990568 151726 912729 798403 412110 559159 215704 986656 907718 81202 810487 438550 68169 408538 513284 104657 625334 354662 281822 905692 412110 90372 205731 831331 408892 267096 318041 477304 947933 799182 155176 91934 204991 428027 139301 284032 418756 367403 114077 845881 485732 557324 454921 543429 15604 891626 166527 236005 672193 214574 988983 295206 456259 141573 83428 177366 292993 653298 974403 58220 973646 936110 378773 116415 278283 916350 243580 398155 416712 921093 567800 992763 448538 619653 110129 519696 928974 471373 947308 881591 662943 242605 606936 612891 12617 927123 854200 964762 589893 845242 381594 303125 174531 950078 223175 568622 992847 607223 441962 654748 229492 464704 759389 118054 717118 493538 232173 967237 954822 163729 376511 951191 83286 537603 677627 889860 966608 861839 16652 619472 972202 912581 29008 955480 411994 52956 208538 805942 451122 970370 264079 290866 396591 353893 537251 254467 578216 575057 9069 110875 439227 253242 589977 856298 246392 480531 643078 810013 617440 83858 869113 977930 170385 942999 339871 567772 139685 70571 135927 817469 91335 37376 465787 283734 704687 993336 743026 756672 519612 95409 855543 953625 913600 774173 833634 123537 562073 984110 181036 635200 417599 566182 47462 648392 344931 159501 543004 605401 781250 136225 91987 990188 266394 440529 461047 801511 229590 100527 120368 676140 23316 736825 301218 443984 974719 556440 814396 330008 943889 176126 209806 893718 912818 422631 179472 542450 402632 555451 354660 872091 824258 396626 703692 984952 329337 134953 635825 459892 104489 398816 199807 395040 888688 100448 359313 339182 724486 146756 52305 935812 961800 435213 506556 15868 520627 573152 179312 148478 371900 259936 13355 129244 750942 266311 727848 505702 274046 858139 800631 79682 188303 151093 604536 810671 133165 31433 894669 408988 575076 822402 326756 871526 513141 258964 46336 418574 534465 854043 442139 185963 903831 797377 913568 461656 419539 194887 734019 805994 861521 997412 477317 196142 372465 328487 869373 56204 37951 787294 677891 525033 776980 891959 614905 641630 770356 209152 823951 285420 445562 809953 461431 497402 928314 177469 639508 215658 590723 546664 931869 694475 788269 534851 652258 416330 913910 11883 664720 988533 123827 836515 564156 249908 95749 582934 552051 808986 600032 623531 467543 369992 185343 247573 268766 885222 668706 831360 299519 282120 304403 34266 4751 878275 678357 999134 742647 859679 304010 280080 396644 791905 954907 476243 681106 679396 82394 660427 338945 157105 66936 500860 854177 738696 680995 625534 933266 249453 101142 327029 286602 226894 425320 680943 593162 561492 957055 442112 48088 794020 444932 593351 564272 272828 766018 844755 285997 144354 801872 112951 273735 625107 595376 488644 22135 366863 172914 313114 390912 385307 28587 351558 859056 353667 341182 892272 893031 915492 649043 191428 70276 847085 820411 70792 251716 131957 139692 874940 267575 583589 835849 651524 945393 759104 685229 186044 619318 699194 957763 35573 413646 779111 291438 32377 294639 997873 380932 735188 343104 949870 964300 146669 554942 494337 444838 875373 971615 985069 379055 171693 756883 139538 695923 492968 587579 637562 372063 332633 794806 324836 734462 333077 708714 144685 437364 376207 699193 255248 890779 528682 143339 201830 910347 86965 596087 871285 534778 258223 588481 927045 937459 963446 703121 904985 878159 949544 11983 334362 172973 767390 925764 121028 549044 466115 84491
