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