1000 1000
15 892 19 797 190 0 74 13 771 550 916 272 951 528 997 362 620 67 269 134 396 819 126 761 225 232 500 417 519 497 772 886 389 144 36 579 144 462 944 915 364 212 539 667 741 889 30 713 956 651 847 705 470 325 466 47 557 318 816 429 815 588 667 204 84 55 135 229 518 79 496 234 644 36 902 385 925 284 98 233 935 298 290 405 623 109 804 533 427 620 962 243 560 981 799 645 37 935 874 555 366 370 141 10 758 43 747 35 327 846 621 614 496 911 371 471 20 175 4 800 795 318 43 356 300 842 353 337 129 227 244 848 949 385 858 708 781 606 95 460 804 716 427 300 628 798 123 0 974 128 800 121 798 195 477 98 390 830 787 519 409 383 719 711 121 930 771 254 536 866 66 692 583 493 344 211 292 467 563 618 947 364 739 746 911 217 196 301 399 336 173 161 719 892 872 192 822 995 446 710 861 513 754 444 6 98 7 650 918 571 268 217 287 8 963 198 577 512 852 328 200 25 489 919 269 713 464 444 708 910 154 922 423 261 366 782 359 726 432 629 297 701 847 936 709 162 134 638 674 338 966 874 363 456 146 985 521 610 429 582 872 935 504 648 196 222 430 556 948 862 185 597 915 32 885 976 547 20 614 221 358 581 448 74 389 946 59 910 908 488 844 780 423 700 428 620 275 210 528 575 425 65 173 340 450 58 317 997 430 931 570 141 864 18 567 253 316 626 516 576 466 360 709 241 413 489 213 688 700 741 263 125 159 788 465 609 199 134 606 629 418 528 122 282 899 689 536 215 667 404 792 485 116 853 727 529 342 940 569 42 34 833 519 193 973 337 154 172 471 112 154 241 640 276 524 539 318 412 107 337 816 251 823 284 104 550 814 446 842 735 841 228 568 360 421 894 49 927 66 873 39 220 114 32 849 990 571 519 402 678 856 570 929 679 855 385 581 21 832 424 756 25 652 677 737 426 571 787 353 637 660 745 210 126 777 411 117 700 930 871 379 138 442 660 818 649 398 751 670 230 175 778 607 180 455 344 958 26 483 663 16 495 760 578 622 537 341 739 238 271 610 969 409 404 981 579 53 379 331 75 961 858 854 568 390 309 265 348 688 748 364 56 596 124 986 218 662 327 309 252 598 271 221 359 676 202 939 81 582 622 157 543 480 11 464 871 672 729 571 712 829 935 768 425 412 106 995 426 433 304 678 383 928 251 95 604 453 34 685 387 8 194 283 488 205 747 711 230 828 283 942 9 570 63 787 982 169 782 408 955 439 438 338 367 689 433 323 495 819 360 882 179 555 517 668 112 264 731 342 444 14 285 806 937 700 593 271 869 375 32 824 166 470 515 533 160 300 208 655 472 569 889 651 124 407 671 236 23 403 579 820 769 216 626 58 916 219 330 137 946 362 314 113 184 181 998 696 481 207 351 305 128 593 309 252 352 332 840 375 735 771 195 857 987 821 915 255 392 245 745 339 959 59 804 144 592 802 840 73 361 544 731 489 137 392 93 841 724 934 216 460 57 764 669 45 937 584 652 330 830 749 21 141 808 825 285 400 979 126 826 693 22 909 182 511 301 628 352 25 562 920 837 619 684 506 16 622 91 21 304 273 770 325 414 931 502 52 683 481 530 509 174 552 770 709 63 71 337 767 449 251 687 286 222 724 145 591 346 236 612 2 861 734 679 627 17 181 679 701 14 209 562 541 113 333 250 528 756 939 295 205 190 335 844 764 59 341 355 757 577 319 759 790 406 438 417 423 971 449 124 985 658 687 526 772 372 128 300 128 67 948 686 609 283 882 374 342 223 81 99 152 753 210 942 511 0 711 934 971 160 411 308 171 98 835 943 822 963 595 950 383 543 988 992 178 870 718 520 93 152 971 245 257 181 539 768 533 251 54 504 763 465 165 934 915 352 229 737 667 825 40 50 720 28 395 899 899 465 771 992 969 743 590 226 276 129 346 810 732 401 666 496 866 831 430 782 183 660 871 851 837 911 253 557 940 648 808 191 466 580 183 435 675 125 14 951 255 360 761 339 113 780 835 332 963 618 466 147 630 337 350 467 249 955 376 541 956 537 732 422 117 267 209 792 393 223 95 0 936 209 339 49 989 527 733 952 497 199 451 127 537 153 946 138 109 322 679 65 211 763 839 328 30 48 472 775 624 920 127 560 129 819 961 118 346 695 422 843 894 226 322 783 379 268 273 840 942 952 257 154 67 96 834 450 497 659 225 121 579 353 681 708 524 994 178 222 689 600 65 936 
178 739 71 910 7 345 102 949 649 360 455 717 808 290 167 305 949 744 778 528 449 459 236 973 806 766 195 847 718 612 783 897 351 855 807 358 552 261 660 201 621 115 918 782 405 437 439 706 182 218 234 631 29 822 605 835 588 800 683 307 765 818 556 116 25 715 827 577 976 839 779 950 954 49 732 712 487 171 770 21 389 5 652 419 179 609 606 120 762 289 779 527 460 687 995 485 402 822 415 730 661 194 680 968 595 764 32 434 936 154 455 677 511 460 448 691 421 55 163 183 696 942 62 156 629 58 994 383 232 409 113 246 955 794 566 550 910 950 985 846 104 792 876 616 252 676 659 674 83 822 209 780 764 272 288 745 682 634 128 266 43 241 512 350 387 430 901 298 380 238 496 485 382 724 453 987 401 112 661 484 934 222 616 50 846 257 795 528 243 275 147 287 868 659 989 256 90 242 906 470 480 754 307 215 479 760 202 232 872 215 716 806 437 685 208 284 294 3 164 537 278 311 176 147 323 166 755 765 408 661 235 241 415 895 456 246 7 658 478 880 873 547 38 662 584 247 298 878 602 463 767 881 126 944 380 449 462 135 214 870 148 802 463 915 49 919 514 56 929 992 288 154 539 679 817 475 926 115 353 880 930 473 113 57 417 493 858 231 980 425 101 480 579 565 748 628 836 262 684 118 254 325 272 146 4 441 621 282 557 327 162 839 800 276 248 569 121 107 800 102 532 901 934 463 818 682 91 7 944 127 125 199 452 397 345 456 191 318 738 748 645 253 939 445 529 188 14 650 295 814 104 179 68 39 642 238 721 85 597 666 212 722 217 665 472 914 473 663 232 564 763 878 817 702 323 698 242 690 700 537 856 805 68 276 196 62 515 917 147 112 935 360 187 152 377 11 66 202 26 299 118 789 529 935 843 204 985 86 894 686 975 103 491 396 379 687 458 246 956 958 711 892 670 898 396 399 261 463 601 287 114 720 428 643 7 271 847 345 709 94 31 37 197 874 433 928 913 243 175 869 201 886 113 223 136 510 622 397 325 224 684 791 296 112 434 655 735 633 0 797 79 383 834 628 257 619 557 170 862 732 392 416 970 857 639 458 719 262 855 44 838 891 835 486 355 621 493 442 607 846 239 686 229 425 667 487 44 224 9 907 308 753 675 278 963 314 736 682 928 943 79 118 186 266 604 893 888 98 687 847 944 927 885 525 352 552 364 749 776 726 8 436 479 683 66 442 349 154 477 278 97 556 396 635 822 353 880 62 803 568 909 99 495 147 624 199 699 989 300 828 715 308 264 546 343 331 341 693 485 818 323 935 374 71 922 548 424 803 611 579 371 872 678 218 19 655 769 71 996 70 899 63 378 515 961 74 198 654 767 36 472 90 323 198 161 245 99 938 400 710 517 771 582 548 341 954 555 111 25 903 533 924 966 263 791 279 337 990 934 104 378 406 546 701 957 708 298 56 998 699 118 867 822 700 415 164 654 322 627 31 225 160 955 543 423 99 823 761 441 757 217 819 163 764 872 472 824 170 880 822 221 998 689 396 699 457 560 705 779 539 737 5 699 44 548 474 495 723 587 936 480 805 107 996 569 979 468 393 502 349 215 75 347 256 471 398 713 383 456 493 922 545 850 973 941 750 448 437 474 35 725 954 192 833 302 761 812 771 506 666 472 721 742 171 330 565 922 43 949 378 888 223 275 90 197 216 841 997 5 667 384 731 973 929 916 276 690 728 399 197 747 871 270 841 42 600 406 964 996 355 694 884 931 969 975 480 538 168 829 895 835 565 978 160 494 894 436 185 975 835 734 722 58 356 563 453 309 321 417 305 29 464 189 960 785 516 440 675 684 269 571 871 834 549 32 329 444 820 866 771 8 952 493 66 308 408 519 617 729 289 922 758 753 464 70 890 980 510 566 17 131 489 888 318 390 272 999 186 93 865 957 101 817 802 519 477 210 39 95 292 680 369 50 785 833 121 675 814 983 593 183 467 82 71 785 825 696 784 11 789 1 321 242 170 123 761 647 334 152 94 626 832 464 28 617 297 501 645 463 485 238 646 304 673 70 89 498 766 225 861 907 226 182 501 748 306 614 747 992 119 194 970 951 658 998 921 307 852 918 123 689 156 121 993 181 191 82 31 309 659 893 568 237 75 421 985 733 36 84 725 155 278 695 458 288 46 731 596 898 649 719 939 158 192 932 339 736 366 371 45 25 616 966 262 691 387 599 777 775 35 502 930 314 550 741 602 596 472 550 846