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