1000 2 49456 431257 385291 672627 422276 828480 129631 852689 41306 32775 4747 244157 356805 339094 242532 188732 555385 802975 923934 767465 39047 516833 435266 982926 667645 144058 84207 899651 611969 116463 369098 163181 765270 696219 247615 109569 123495 565845 107042 420233 494764 728473 562065 900675 218783 769871 550799 849689 717852 32945 249802 310195 10164 515433 831066 415953 843678 231254 377680 307874 938243 945430 826796 294180 317373 353904 598192 3709 404121 845077 116867 154840 412481 204144 843658 255264 523108 884622 608401 206451 359874 797526 175803 808049 570039 927020 551777 115561 956129 217278 9358 742898 898154 196000 925847 286329 240623 166741 45677 172696 848859 481553 168976 109683 396884 321697 453198 426593 324998 24548 426527 388333 311246 94122 525223 493578 40017 825738 590969 818422 152887 80448 976402 601227 645608 834586 7919 237972 39069 761926 269731 890764 763936 806124 92264 107301 662067 9059 551575 191724 436532 270477 177337 616182 32719 384273 512369 703407 514609 353074 14900 154425 642575 312689 361371 884324 481307 958532 459086 207512 697590 788468 506245 273348 370052 887131 196496 165545 29881 665959 226181 84211 621809 973893 258140 700633 678694 841815 937590 566669 256567 476801 773832 621882 656158 528741 399585 469384 706327 759450 279673 178200 299378 171172 400491 431842 423701 320747 552287 74124 383381 844470 855483 771602 632938 543921 913909 979324 366274 72600 984668 766669 711309 266370 768243 368598 578080 219279 879192 789037 97922 144240 779822 840016 652091 661577 840991 59023 879207 810981 464878 627755 962407 904982 813974 748722 869087 561120 12877 836547 947514 278050 254648 546950 630236 293616 456599 968204 611791 226196 581018 15738 771288 325854 551548 502509 559937 28362 591774 559248 218413 874282 683489 704732 983059 622968 926118 955961 234963 958279 977640 824266 830148 607741 966651 487764 974703 13316 465731 606261 626675 989088 266289 818101 208639 340604 448406 152047 250621 784058 852609 743937 58463 967046 289153 874842 177651 555662 98577 101284 509798 483500 854799 313695 435712 512408 265302 301701 882156 861822 921126 844327 505798 315465 658125 599581 61498 430180 341405 909092 389629 187360 505473 697728 848648 970375 809566 175275 9777 201966 155371 693723 377160 779153 512017 490549 606989 609686 144397 212682 696290 476614 890779 112071 223717 321421 539885 284779 989764 444625 644128 930126 93253 181267 773355 401388 507873 615597 112014 946557 515152 133148 755239 917876 117141 81053 356255 480741 82396 454589 151497 209602 52497 347459 226143 454165 454232 865211 791420 955064 686300 518925 587538 870099 986593 608171 463694 349087 915144 194194 336640 413134 426481 522824 397268 44443 596819 145841 932056 600184 767777 225001 833945 837326 792105 326942 951900 104834 114212 83530 814397 937123 672272 118020 32737 140909 398847 862666 318450 254288 103193 665951 309852 816725 112391 607180 3860 957488 887599 708882 156843 112751 487838 558410 55407 718186 811902 801957 756073 26321 819757 718878 714835 825680 850405 746833 297325 512349 272635 458020 42150 549418 971480 704643 306022 922914 227423 617035 68253 887834 429823 701256 808608 68336 319592 500828 780369 286486 773888 285174 936517 355927 256813 314732 585045 578609 929442 683601 234845 268749 134832 129762 380449 58808 910409 575752 749536 186130 37477 9247 773262 927753 451831 537140 666320 92448 710483 842921 552984 983202 696678 448600 635313 42489 681335 117545 103901 381653 757437 885522 490956 148038 188781 823990 311548 14976 620533 457388 963907 644397 188081 60379 895292 614762 646775 944404 497479 160259 370195 729611 153942 609093 120646 185116 130934 6203 228132 9284 852633 532092 245116 942779 356484 644298 931952 714299 480295 493865 592088 581888 828734 126367 142856 876820 533723 760792 98805 998198 542782 297722 594378 227017 546089 125161 364284 964209 848438 780885 309633 166324 763927 552686 448482 413768 805421 151486 791537 162072 820899 963469 690870 304964 757961 941439 779748 75610 751346 460803 392079 129619 197441 4787 970130 553766 256310 113894 980375 722024 102184 698116 826974 176332 211517 941742 830948 721043 69184 297970 866702 709233 418363 731930 924824 342226 642279 375588 516363 359106 567240 616618 536455 900410 136769 173193 671568 875199 178717 27653 838175 660338 62906 414438 954400 791281 148958 721198 155473 480107 70088 643864 149815 501773 573993 811518 356903 476083 933839 523155 366327 250520 926141 605043 58567 302904 219939 577284 842678 169678 163673 159469 260252 417029 371217 426819 584198 268109 392311 131596 268173 39210 486944 25231 531859 271550 962410 461853 675954 726243 192173 474871 761330 904050 981141 35219 150715 180660 162251 338514 114680 577496 290761 852736 695974 350201 332776 267988 95456 61889 629901 821303 775138 379666 405041 571550 666816 983555 589031 1594 643644 145450 421882 779110 477099 805127 814949 769247 587122 536998 94288 978856 29853 396184 511251 601943 544659 63369 816168 409857 730436 722500 225382 238738 793597 943827 629115 686783 233270 287575 515873 768998 240027 83164 721722 974774 301865 49285 496744 933455 898196 252853 987361 757824 957898 73 770466 254240 136203 749100 467947 532336 968285 114952 353009 393629 159496 375549 191312 568162 549348 667977 21701 840830 770261 497231 392569 392021 223358 143976 291596 804822 803144 713370 37181 408677 771320 518432 762296 665182 81541 164805 831036 27197 172042 317503 136432 595585 166401 486606 2758 692554 533456 819689 368975 488442 143253 134267 868728 850627 506201 574990 348708 739937 532720 704664 809211 968211 170934 295307 865676 705306 585444 365676 615531 395410 588542 230594 221319 344010 184738 948296 477352 292570 356342 245990 240836 583137 581269 258035 856184 473385 556897 834176 906523 230400 716795 426691 900437 610489 201710 545628 587336 974723 354677 680370 743705 739946 449879 966955 412181 414438 142978 355379 354554 43862 667803 184204 508772 237189 519131 183504 648165 754783 275837 535882 220746 667633 967758 820462 137831 230773 80998 325923 703650 708360 647125 392758 370973 29270 76786 434955 279529 908273 62224 409021 989121 332248 695407 989525 431893 644415 919729 365998 565445 102019 711274 787849 506769 708074 826477 921915 982446 217275 412127 114924 147297 724072 401844 203395 797711 176103 186 319807 954594 816825 662514 539536 310647 45850 489821 463894 264072 683979 435931 538368 638219 572450 674077 224777 322773 847739 22966 561398 377194 713246 375377 981864 412024 428198 965725 881066 970096 7281 148714 33407 913432 590279 978459 311449 256647 248276 741023 277935 175454 318402 471965 728947 607204 569195 179588 789035 547184 830196 738831 842934 667417 414644 630746 421273 120432 926265 956389 661763 140917 80467 612238 542186 129531 356007 539703 987434 867433 13655 630285 612180 908586 723623 658544 288906 455399 973641 466862 859536 211637 915652 953861 19232 310925 569872 399945 294650 29789 849028 388006 632849 116705 538877 191425 114588 789538 540222 472190 631904 837739 955912 322848 585051 383196 967400 832134 961606 67631 650200 820422 505907 205389 466021 654930 890378 532869 28256 789285 113808 766497 102071 575404 756935 580689 339651 734361 637968 610563 603782 558991 385827 497695 531567 957509 645138 221239 940950 437094 575634 418787 614367 586556 67855 683782 952215 222771 528081 561857 801273 920388 50291 234347 420910 110803 256975 279232 266975 552740 791453 452481 623866 440385 439745 654198 10585 916485 964927 185862 962023 348573 217552 385165 41346 153370 530199 890504 951410 932443 910395 999207 584662 237208 303548 71751 329960 148373 897913 820865 491784 929678 131116 355898 248425 962496 276794 796951 123546 353492 463044 850952 916050 641005 668782 446483 72473 451925 5494 962119 276247 293022 362692 669694 776749 804210 967005 385383 387567 464290 686690 642271 994901 587781 745666 733225 636189 855646 78074 541743 323215 959419 913392 281135 201005 66756 843590 384353 696323 964092 366324 763933 529174 196891 542806 979705 714053 702417 516555 799235 133075 53869 773454 722657 406272 483626 963093 794926 283513 716057 263078 176418 333507 918720 572317 577706 894869 385726 176281 227706 279678 783539 581679 970702 454334 735520 447322 609863 820734 950336 923878 711571 481306 456472 687351 321653 801058 188705 518366 873680 294316 722889 638084 978078 585109 75203 901562 314724 52407 406462 910131 962542 534432 590786 15676 680083 344702 270862 724333 257488 488433 342771 980159 83996 422610 939515 326635 405161 821671 200501 547906 343814 682326 195789 805702 255839 671427 757595 422407 238022 124796 698843 580248 593365 897433 145082 418892 763708 910725 852872 503527 955987 620841 958999 832988 706370 564597 291344 90969 37911 980979 390230 245849 733126 710505 940638 505113 113540 478772 542241 243940 474773 722150 45728 112788 650677 990453 872579 845373 461852 534508 523265 424552 177789 286464 121118 501591 613847 879417 716410 275006 287503 500537 499450 234549 958059 337149 33323 190260 235813 990539 103053 571497 821992 732815 992243 98249 159729 366117 751900 892639 287378 84438 328744 165483 929848 625417 712523 622788 812074 838227 454761 935492 327262 141986 138306 259373 625378 427461 679835 903 930397 69814 125153 226491 737060 481101 546540 251522 457330 876681 752918 324272 607275 924622 102754 974787 419156 449861 995670 227128 767555 291666 762580 776333 922206 273349 729385 380582 847984 478575 401083 575111 400144 996100 957031 232209 757493 353423 471315 262891 489596 361113 16590 100804 229733 359809 471302 887865 293798 298589 981816 371934 115522 944474 505557 728379 9912 516738 272518 777192 224430 123179 605089 464490 887218 118236 566443 233618 644102 141867 279923 361801 308866 381639 499005 947308 568559 264125 546328 472428 260046 811379 145973 815617 368372 750343 784119 287833 596133 494971 181873 186211 233217 188399 904192 435841 396187 738592 853700 526584 977471 886683 357867 830908 12917 31605 727788 568419 485438 609161 887421 961575 169229 23236 243247 531103 471641 204781 135775 53662 360334 587488 15563 772604 801780 774865 100704 30288 595857 406946 262231 44509 30014 247838 109695 192880 699215 215182 891062 339118 54677 277418 281436 962279 398431 352407 978682 894172 442667 181041 824860 763746 281119 61345 468169 462761 825861 5510 768692 810290 238566 950486 252717 35107 548472 933846 938015 773853 119927 358861 772061 908876 737600 296257 850775 409295 889200 96711 883425 656938 900915 29600 980704 484905 332429 683191 929011 821237 947560 149941 648182 754090 664590 719077 358558 559570 745303 584644 602560 91270 786318 600471 153513 381522 814592 867580 723381 313098 545945 576595 259716 426571 97674 876261 484833 253916 144621 78802 761773 748655 924558 412896 820321 589098 330458 26389 146004 952109 7913 877618 663658 623867 187612 17029 716554 377976 575432 978796 470017 681330 767539 160987 981066 460596 128594 966737 550518 534708 313222 24614 27955 619772 29346 271216 577622 98845 82915 402908 43928 558523 172878 17040 459864 559046 500767 511203 915266 793908 419669 423549 107778 553450 230915 742009 945408 897145 595152 380034 355342 601633 892711 694610 300574 43270 881094 800760 121133 377430 938229 670238 937686 471664 345269 702339 17548 724330 353041 191571 180811 662174 266067 851323 625682 235567 443098 758183 736312 633825 637037 955126 300557 260246 323876 154277 798146 312121 532163 257958 127380 756832 586723 733109 137978 669684 868708 216379 129270 861806 669408 956571 896810 531605 98123 649372 530232 500692 958090 283557 277942 286147 281067 313420 470052 190850 947703 901923 801013 858398 271185 461639 231585 367251 198616 939078 429725 222373 807905 553541 152302 54498 617059 191202 472290 604026 646320 662183 403485 580995 759822 869601 321007 993405 722167 763861 959658 465091 579241 833934 634560 120387 524801 683270 485950 518337 168546 178065 687548 972933 606171 338437 552885 615423 306426 878594 394491 506688 433193 115137 657485 818739 725893 353213 312953 983066 614736 883825 370374 853449 485211 356253 81917 757129 578677 986329 896442 526321 953405 470732 334635 14665 170126 700203 976640 858477 796705 247457 293176 315024 4490 500677 264204 72080 954945 89642 474266 421110 294314 261218 342392 406037 229196 454386 565304 976273 217167 944259 695891 139730 472763 882585 159009 80206 988406 507635 397729 163909 389439 365892 442853 743340 217571 424505 962827 806951 424499 718815 586163 942839 339220 534156 480557 802147 904090 322907 167613 345745 793401 400510 462136 410915 256941 103253 686469 519098 244332 96803 153374 889762 330156 61844 292882 449694 730369 284694 766004 154869 105831 783836 767880 714932 256568 145947 226556 632765 705752 792555 873752 773332 607241 92279 939130 685512 665426 716023 854645 862166 520622 508044 885720 461094 115147 965116 386401 796512 289410 558730 149235 330617 149413 845237 442864 455436 442435 92685 910711 454904 941090 871968 19076 448282 259134 14349 8446 611485 881412 995830 532110 817248 161134 617237 830473 914398 71741 813581 853624 498639 16158 591220 454890 731292 353966 846426 648998 58176 550216 774803 353806 447503 986058 660798 429343 764633 484695 539501 628810 158514 99160 409526 881420 76872 566002 689300 675689 953706 922639 795252 642341 389786 71734 584291 83578 304200 568231 541045 116665 300726 42884 738324 383661 259341 978112 964020 549710 661948 884811 68777 452855 10777 930655 997046 29914 220505 719450 312562 955357 208414 469566 928101 253855 652012 651504 504386 381974 557650 338542 317872 357387 614175 411669 419600 450895 199228 166704 656605 676273 373840 840198 785066 734292 415394 419585 508271 166136 787466 711819 447878 52659 966221 501946 793028 949796 826430 351495 953920 733673 388850 934706 580080