1000 1000
24466 670 432 568 45 285 109 889 536 714 806 386 395 938 374 141 955 241 60 130 828 932 353 169 100 925 187 637 81 306 584 98 38 752 23 387 522 251 972 605 897 473 442 608 512 129 982 919 483 222 649 638 577 840 182 915 210 541 29 448 736 667 95 80 684 194 779 736 858 208 464 720 447 228 268 874 650 335 533 890 593 368 470 726 509 23 196 256 937 572 977 722 399 873 313 58 516 853 787 630 125 523 978 553 258 26 725 359 937 366 260 245 438 183 668 388 233 992 732 216 937 402 537 996 584 954 799 776 191 185 481 110 164 243 27 65 408 587 685 31 430 12 819 817 945 538 123 480 213 867 942 922 713 16 19 133 891 160 233 388 676 711 187 8 669 402 937 320 291 391 60 883 344 979 913 77 890 139 451 41 911 823 402 447 313 692 168 22 686 722 414 219 19 13 42 179 35 247 228 861 74 54 266 163 127 489 904 674 289 217 771 208 185 414 736 734 329 80 768 271 427 551 728 472 277 45 918 967 115 706 470 801 310 256 150 142 852 680 270 360 775 676 405 373 586 479 759 600 666 426 571 583 337 777 981 984 353 357 119 278 159 691 885 427 253 277 137 653 53 439 76 830 755 180 479 647 827 2 105 573 770 276 65 383 497 511 566 6 695 31 525 269 342 562 51 972 546 693 547 248 661 566 810 885 950 530 554 238 314 720 292 516 172 773 9 118 986 313 227 424 528 50 447 663 305 431 430 235 602 984 276 270 833 613 776 268 390 356 997 843 154 815 193 238 941 428 132 565 508 191 363 302 155 925 470 130 78 555 71 961 383 390 420 391 123 348 166 596 886 355 74 950 72 920 336 418 695 283 899 451 695 137 960 345 424 306 914 670 159 940 677 69 392 56 578 700 10 683 523 124 323 56 159 766 798 419 296 145 593 745 275 833 412 823 656 361 31 136 835 308 204 579 770 816 749 652 319 917 439 586 48 517 135 585 758 364 683 609 843 914 644 822 735 254 914 673 140 869 145 959 25 556 28 609 292 634 583 756 251 713 512 169 757 615 833 439 181 1000 543 768 559 94 863 354 486 51 386 791 60 494 317 151 547 485 911 916 772 130 797 702 182 321 728 296 554 361 705 875 245 257 587 162 917 460 346 477 703 352 939 497 112 267 108 456 898 424 61 374 626 17 911 196 424 228 348 976 999 875 584 52 197 975 22 965 509 733 501 463 67 4 381 328 111 397 389 146 150 956 615 765 86 182 222 308 793 179 958 271 699 919 149 193 327 19 144 339 278 201 513 880 530 416 216 266 531 964 112 630 807 994 99 859 575 154 337 408 840 246 677 390 687 890 88 588 657 277 250 658 58 95 645 897 244 19 573 49 194 455 237 378 645 169 508 639 567 101 408 463 86 452 713 758 579 599 937 892 180 660 27 284 263 56 706 48 632 270 811 555 509 462 573 695 639 138 759 304 956 366 131 505 91 686 43 781 111 27 241 593 160 105 859 720 966 363 814 166 88 880 682 954 308 827 471 486 39 885 470 736 223 397 51 934 383 251 730 317 907 497 159 243 829 571 826 990 591 169 635 684 274 354 403 556 238 187 827 717 363 345 880 798 968 819 720 982 457 315 838 205 942 271 92 226 922 811 401 566 914 569 377 864 823 452 349 427 837 361 850 494 564 782 230 570 678 432 768 945 83 536 591 196 546 253 519 830 681 528 751 368 598 764 94 36 871 957 824 310 527 106 291 679 634 718 383 580 427 139 373 487 763 824 374 796 469 757 768 567 312 59 741 532 661 362 620 431 521 213 828 933 317 289 982 42 532 926 667 804 173 485 22 568 506 651 267 956 744 196 639 389 296 924 626 410 5 914 563 40 919 54 754 7 103 180 532 645 956 977 802 738 997 725 515 748 288 978 276 844 363 701 549 776 545 202 894 570 119 308 145 993 639 565 225 390 132 691 860 154 872 461 741 22 331 684 197 956 821 557 339 76 597 501 689 40 546 766 657 260 146 610 600 713 66 933 258 689 774 143 966 64 449 994 827 281 494 898 955 414 856 163 87 252 912 239 332 398 221 439 260 249 816 57 471 760 784 756 564 496 283 496 859 471 663 449 333 353 392 774 989 947 346 364 313 652 586 961 524 288 760 678 438 447 743 228 383 222 344 266 15 316 500 653 161 535 385 258 225 527 351 128 580 980 979 682 735 772 556 355 395 592 324 354 855 519 897 641 503 323 876 648 947 403 921 87 971 16 833 572 401 844 748 417
800014782 121776 111260 114043 103780 93637 108351 117295 93626 110261 112354 103213 122185 125355 109909 93465 97784 117128 122947 103423 107634 95703 108635 118758 115311 97283 95662 116649 114230 121031 99160 95746 123743 112103 93795 95464 119006 110622 111592 103195 100413 112983 121463 124925 98857 92960 117433 121251 93232 122203 105300 117036 95177 120118 119823 121169 115349 122974 93239 99134 102372 110704 100417 93600 93051 117425 113328 113152 107925 122878 117818 113743 96295 123142 118566 118978 120168 107190 98808 115680 98193 108277 116048 98521 118241 122258 108816 96793 115429 94586 119997 98333 120822 95791 118568 96901 107011 100725 125261 112491 111505 113999 118907 115956 122879 122409 101301 100644 115727 125271 125017 101367 112546 116670 104959 108461 101571 106705 102820 103269 114663 121280 118792 97261 97651 103659 112468 106201 106623 116125 106496 105426 102106 109559 111860 94257 104014 118058 121581 118989 110373 113642 108323 120336 116715 115999 108841 110161 97910 120029 101396 117341 125476 108438 119519 112727 121700 105358 111630 106691 111736 112272 120978 104925 114553 111584 98797 116015 107931 110192 121750 93026 93106 113494 97183 100949 104437 100478 120469 100716 124162 119708 109224 100395 108067 118117 108043 97027 114896 113919 117918 100971 122741 96182 123083 124979 115061 98544 119725 102165 117870 124515 98424 106638 115391 109701 112405 120044 115527 122692 121356 111015 95856 105208 103335 96756 101484 106902 124501 101784 94399 118822 105548 109050 120574 100471 121458 115069 99542 123665 121470 122124 97615 114027 102490 113655 94546 96350 114380 108029 104810 96986 114518 107434 122055 117976 98651 102627 125320 122511 99458 114111 107066 118763 119392 102808 99483 117819 113489 124002 93604 118314 121510 98876 122567 122864 108038 101701 108662 109513 101390 111025 105956 94374 124475 122908 112143 110371 115210 98845 114174 107194 116061 122143 98375 121654 111137 104300 99797 100970 118062 103307 119784 121378 109678 103884 117597 122458 110658 124961 101680 96174 109601 94255 100415 113170 98947 93093 103505 109507 112637 116429 114262 94334 115117 115041 109041 111855 103128 120223 109619 93804 110034 103839 99242 115427 113694 94949 119194 109841 94679 107571 112778 110837 114766 105888 115714 111749 105461 118510 97684 118943 121212 105497 119577 110146 124473 115756 111165 115710 122829 109144 97598 100265 118533 111943 113904 125012 100862 112814 111621 107645 98701 105762 112523 118919 97757 113196 94390 106855 101978 104095 93152 118687 110798 99113 104654 108144 95178 115497 106549 103243 104520 112576 111228 117130 95886 114987 111556 118365 109142 117328 125222 98567 117291 111254 101179 95050 110102 100858 123362 108063 100730 119648 118077 97963 121917 114982 122877 100207 98088 106495 93920 119231 118673 123903 113015 101237 114231 101362 102445 105702 116077 118514 105349 123669 100987 116793 108707 121383 110145 103731 106254 117783 102685 104919 99252 120747 101903 122680 109871 123815 94491 114775 101702 119360 109807 121148 111543 100563 103366 93253 93748 106455 104332 111037 108971 118545 120131 116144 96458 125446 94117 108542 123843 98486 97547 98991 124236 96391 101517 109190 112874 110976 99947 101849 122480 101303 93100 99744 95938 123149 112900 113867 122335 116504 94459 106969 108063 109921 102732 104102 121017 109520 96139 119428 106375 103780 96523 109198 113678 107303 111103 111673 94137 117602 118751 95788 112997 104717 121614 105298 101410 104329 115641 121901 123704 108178 112130 103021 120681 117359 96606 109249 104822 117867 122683 125165 95717 114569 99559 111133 116224 114036 93357 119160 94753 94133 111169 92921 125229 112936 122462 102522 110943 103345 105901 109842 95815 95787 122601 113313 112658 120481 105537 95657 98315 105665 119805 99168 114274 104589 95333 114179 111916 119124 114398 105324 103596 114913 124503 123367 109777 118514 93411 106306 120831 106732 99495 103971 99091 102860 96247 103838 95905 124513 122044 93959 116095 102841 104217 97797 99464 105945 94030 95976 110490 101552 114396 94013 122849 116046 96490 119967 112472 123218 102887 116176 107916 93857 100977 98824 125348 96606 106869 123532 95646 94742 94616 103043 104155 115770 97750 96517 100318 110803 94569 100726 118609 115057 104173 93714 102472 124772 117441 114888 110538 105263 93360 116300 95118 102458 103633 122728 97794 118983 102315 107667 117649 120359 124317 122820 103718 94510 94590 120968 113644 104164 117376 108115 107097 124285 99674 97555 104042 95628 102566 108555 110896 117619 110727 108255 118667 97566 122256 106731 100406 122865 101089 107225 115459 119550 104339 121459 120168 96636 94039 115893 116795 96628 106073 98855 109242 103102 121963 116074 104142 107052 119647 102416 117393 124165 107700 111025 97037 102581 94838 113978 115783 103106 94047 125065 121468 101634 113218 100919 123050 123404 100522 108981 100434 124396 124094 120219 122492 100123 98919 111676 125437 99246 94133 98942 98037 97997 107647 95465 93083 100967 111946 110333 123453 96548 109932 115913 115842 101531 119922 96953 111603 119750 123582 112560 101305 118194 125301 122198 108456 107643 94616 96948 105597 103544 104048 101630 116068 119731 106288 115375 117438 101788 121814 95451 99872 116478 117074 117441 124831 114225 114922 113569 114763 105362 112349 123597 103929 99888 117830 121345 123974 94408 112708 101879 93912 111348 117848 114999 100583 115359 104462 110893 95740 106940 94176 102781 116729 119863 121687 119195 122458 94764 110195 123030 92858 109144 119373 123700 106137 116941 98555 102468 124508 103913 96436 108336 120213 106888 125492 111826 108677 118393 108130 105096 98016 111151 118577 101259 111567 105657 102340 95356 96059 122101 106453 98624 101449 103680 104023 111886 119073 111344 118618 116934 95220 123334 125232 115589 96573 99998 105678 98678 96071 106025 95604 105707 109295 101981 109457 93612 117163 114795 108257 103054 111819 104178 93144 112968 94719 103538 96323 104579 101658 116227 119597 118832 116501 116295 119807 107550 112215 93341 124140 115916 113715 97431 115852 105084 95155 125359 101063 116360 97684 99125 95477 118521 118161 105612 113987 108630 122085 99734 98649 102842 124427 124781 97338 96041 101832 121172 104299 118308 105835 115181 104279 106619 111188 121004 124658 112995 100019 121739 116381 108744 112530 118015 123466 102629 109590 118315 103136 94737 98817 125268 118497 125148 107388 123030 101962 103002 125460 120021 107962 101055 94978 121078 122071 113196 100527 116046 115693 123849 116087 122714 101593 109332 119725 108977 92966 99193 93920 94264 114549 114210 100957 124053 102946 109072 114933 122598 106788 96875 94721 104114 99637 124694 110499 124959 111156 113543 123470 96614 120519 116694 116104 119941 122692 124947 106990 117044 106450 103901