1000 50
754214 186678 987017 554037 907383 807229 273451 167009 280915 466467 313720 697349 528965 318812 414188 747893 45156 464275 236703 395221 317822 551806 947403 813274 380313 839537 480665 78803 228483 549993 6104 499049 253023 509474 569438 160407 833055 842889 843768 113970 309356 157488 811319 838322 992652 741860 586215 554161 722487 339271 465734 556662 891077 413137 369936 787742 769026 366954 866545 997509 433299 389002 12910 686322 898476 582348 363081 731531 941589 206849 361853 250946 880690 173173 605620 389694 431385 708187 943855 670224 47458 409590 226886 454887 339079 113175 242629 108106 996481 625527 105615 429780 14529 634878 116102 429357 217226 479184 160888 158816 686033 522741 926114 566723 212266 48086 472770 160003 756273 416625 830228 320084 342567 573466 291323 681647 202993 50305 789753 199474 675832 411720 145606 206713 562950 261709 636070 780177 257245 313310 455345 943278 352403 897811 26354 564670 462249 15476 241025 734874 432101 587605 54958 291021 161072 862634 972668 880417 912939 278773 596244 105123 206845 741850 828188 769796 519911 980610 66325 777156 293920 38022 236787 162675 935833 779493 727345 398082 794969 484723 132956 743422 72328 704267 34443 233400 83253 523463 630170 512544 802236 226414 617667 9082 484616 962207 778878 4528 942817 845203 298036 753089 399577 51175 915764 335410 830668 159462 249844 141989 644185 899152 885412 716513 119771 436207 466266 203024 959671 96436 231920 761907 839202 849587 287341 323818 328146 66219 844698 270963 427774 659087 540404 827351 710262 456169 679113 540931 615631 445309 199272 776168 860814 601036 9033 980585 37244 475299 699962 513267 88087 931882 275174 443641 297822 562516 283812 142320 145087 128510 413284 89214 787597 953688 432917 14212 926209 628383 71495 58192 73692 270767 834360 934506 871804 843394 431444 425400 835045 647758 938667 923133 95992 730193 883126 910166 809061 166938 52487 470501 811801 982123 559715 115750 452163 508984 129962 894725 137367 201457 952917 211060 472225 303630 661918 860381 147024 609714 802133 498421 773824 740800 937906 386169 470993 821033 296335 796407 987971 865174 266908 316124 363649 826623 431875 815813 335607 561837 710538 472975 279647 179807 200387 751872 483437 862305 128605 146813 988372 930738 645235 762196 187890 99493 148365 175235 920526 961053 971642 424850 826227 238550 740974 189877 65173 172849 522042 917133 251039 748932 906460 530686 928739 106847 798910 928529 485504 443867 75342 473876 374605 236929 752425 78847 336423 417142 254082 773301 378195 225725 198151 720775 464275 939126 910652 45801 628327 949046 962934 395718 697978 385746 926404 143069 492593 241666 71598 494449 685533 146941 484678 576490 900222 237103 655337 236645 654245 909420 9947 32441 135145 724450 753216 115772 179928 180220 161573 808256 645618 640859 720326 343596 26605 163083 486665 35550 404749 558264 530000 90283 221557 14678 183125 121779 251781 838463 874777 422378 747883 884724 971171 399380 609174 724387 31504 789103 420959 193078 113711 66577 350289 834037 926525 376895 997120 413191 928797 918222 487807 458797 524857 225716 473475 707982 347495 241608 546445 738624 180339 810680 623348 151510 726412 748875 392250 757917 54330 813209 467347 684393 396139 817636 34782 322664 710883 548255 252207 639681 466477 256366 614830 991334 482082 604658 699316 345930 846266 762114 84554 26605 572794 224255 178116 299207 489482 86718 57124 60164 899927 524471 744557 812418 858459 779339 135083 569343 327594 903642 725376 310423 160009 340206 301757 158443 944864 517426 504373 307483 279540 105280 850440 852334 845887 544908 667893 335369 631626 241369 395533 47906 765840 656442 860324 140652 952133 511759 709995 796080 415402 951723 106503 91763 808281 924613 250206 753146 442039 270932 576981 237931 892564 427421 606617 738451 488682 274511 590172 120308 515880 502057 684566 798073 158499 544891 938725 626984 573002 165072 423064 988404 116795 529568 596519 925076 454181 363078 194574 412572 150362 771555 650503 42926 715329 257120 297729 720363 47983 404253 840671 563864 906310 41590 361937 581161 586481 817014 208145 159483 982086 631210 664240 98881 677130 777111 540309 647663 140189 734884 60235 290551 22791 227090 333477 738120 484210 147558 458483 48546 551811 815507 612410 974473 857097 490699 71986 959930 307713 796484 635765 806151 944046 816357 905032 621176 593469 445341 268839 733658 696577 845426 24210 719369 72516 874039 973841 73078 537950 948677 121624 89761 764184 734034 580587 137633 741085 168925 613915 565150 965409 249680 371301 909455 582390 276333 46983 175859 238027 315822 909517 450956 161248 450079 170325 233764 840471 660519 306843 378421 609196 428467 468182 889732 678854 565121 543717 936291 734047 157632 501442 699456 923664 872743 125264 506054 665429 172247 198265 903456 4422 624135 870764 682022 590566 41090 432139 431037 217961 255334 809458 827157 200153 793993 233241 879007 359114 776958 815299 609513 450942 833093 825322 890958 705836 950586 397013 371265 639185 111630 791073 159959 735765 661838 841982 326332 219280 274121 757369 437241 529455 83180 780750 729608 877173 13991 124968 752639 790949 456619 878505 758243 289712 703827 649201 511900 170765 562566 883166 809950 674197 674239 969910 926314 336077 328244 252646 71709 602365 526368 508950 648172 125900 289700 894132 519425 303691 535452 272064 610992 992071 150569 369235 798135 370748 18437 310036 541513 581003 709554 351464 771552 383793 837726 697867 236223 165970 466865 307932 284687 509585 333235 449211 635485 622935 343343 671262 442979 878796 943327 570323 387219 610248 939559 701707 980997 474348 528095 38862 571703 237649 906678 859608 137794 744404 557475 890369 426726 540692 714654 227765 50278 47889 676976 202115 187176 20320 873378 630155 415468 333057 200479 319039 459657 656390 20746 957006 647090 65193 995869 735145 302842 418899 594753 956989 679656 152228 363710 622734 209273 78364 850500 775903 642605 527476 494370 829782 64148 884100 976289 479616 217157 693120 315008 193167 865862 335754 666525 512952 400948 178746 248098 220142 597646 842851 693483 277302 511432 57194 900036 720705 135558 266888 12960 294516 794365 507330 640650 374865 391431 133291 370834 124940 826412 685842 318107 208626 537948 500985 237931 938896 679731 486029 675391 793729 845232 368874 71031 873016 426068 487420 110073 77979 754308 123033 372495 65025 630364 529497 956243 538147 662788 327077 663087 5552 529271 981195 214179 67219 998532 452110 522468 678263 454491 197859 471993 816075 566733 59376 205444 509154 63148 315517 587133 333809 954903 475980 915186 101619 5477 871429 639766 184617 714858 302853 190170 244129 800400 404349 827701 798932 372811 350169 993548 343654 548028 981893 159729 631113 41269 365173 656619 620770 197043 760104 954579 668298 236084 386117 769917 757913 257547 926035 458883 488757 745240 649053 732887 545641 569754 560588 860925