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