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