1000 1 256151 291307 445089 962511 100482 630987 548234 517663 856297 86293 39210 817947 895784 851550 377150 255941 596151 712891 490344 217879 527923 205339 599931 696778 228478 236897 136889 449870 497157 507674 651037 280886 886454 11754 770915 291762 743289 228327 962198 606628 726779 136168 302578 578880 771051 849426 601615 524491 819422 161168 476405 899065 356876 417647 220592 638495 710185 951233 78220 972341 453412 641532 409606 198788 841524 14357 644272 958444 660646 980268 609257 622647 968906 504639 242968 421542 671882 481481 438536 191654 120069 444002 142631 203660 62597 849331 730257 370788 246032 4789 763619 380465 218811 177064 185892 202707 240430 766836 772464 595 470857 858664 276890 359642 629501 536348 255752 640384 676144 941322 311385 184096 801840 299199 659312 597031 680300 364827 194575 54330 288393 520324 889344 584201 553684 3216 819027 405428 749971 118096 25318 461308 454314 255735 991891 966594 245687 359565 125618 500221 659887 353816 878712 868874 325330 370263 128338 152917 662772 887229 335447 72822 224626 612315 175728 387864 650993 897114 914172 434271 433453 23794 665572 103555 607810 601499 186326 678566 776319 208640 22316 5189 949630 545581 568017 986104 300317 532833 690357 132659 392325 192170 305788 693519 126613 324114 166774 879009 447486 562958 802168 756852 398309 723414 759807 169698 149755 950642 843773 821529 716558 662216 284918 37062 435365 458029 75397 518158 921125 509096 955023 452421 433142 980929 592103 753455 413062 39705 701083 674063 371264 412394 514440 500319 244193 318624 984671 234370 812802 731137 668456 29225 481274 70429 416378 838708 185382 901132 872792 416033 782077 322858 765190 710091 384854 596729 601609 915429 312049 603518 328730 233494 562625 147566 792944 203191 633565 531759 204482 919710 338281 241805 356557 66540 166604 735237 813161 72349 50981 863873 540850 925676 231129 119869 886697 954482 405755 784705 261315 792360 118230 322266 129981 58143 321343 123055 158873 59607 432839 398266 113420 765602 490952 1742 632089 12037 824175 239878 804262 103156 471119 712667 709991 52719 603296 436786 676050 452211 202013 462449 535366 566397 374474 631740 572299 99235 852363 950876 217562 397834 304574 751080 674391 564456 721652 225427 957522 615338 628737 139887 5802 696404 479704 545394 232101 214650 181649 777790 86746 470470 769433 884723 210581 865781 765147 498109 601762 378412 183128 185476 246158 84305 755436 518903 716458 16040 317398 657642 572145 692405 833192 806265 780021 60341 347616 87108 324006 908875 81387 345046 379486 828915 791974 825890 39781 731062 550037 104351 631155 618639 869071 177079 125392 692576 885059 713330 796749 242283 130967 517968 809976 111509 413117 745163 364561 98201 764218 371367 12190 886570 636753 469048 421125 71488 965965 327723 263900 226035 184751 211577 461732 957172 616271 412099 1039 426919 578242 721608 55202 982025 768009 909029 50748 479009 120529 210480 438413 971522 866036 334744 526649 764450 788361 517259 398806 667183 475760 356383 504262 597866 647857 963927 741393 203121 913567 999310 893133 995765 707855 683722 269992 785252 371168 260350 100710 271063 38812 108259 341690 524809 866077 830629 968865 509830 934813 553584 830326 413974 687471 727508 911874 131076 454691 928680 465199 258891 766134 505042 477921 275301 942771 819516 295897 983468 232384 483421 637216 32480 959657 637678 33186 36123 765679 465452 552337 147600 222502 661072 151545 293678 166408 58127 532521 105627 52206 964670 695234 185131 565599 385595 495251 944320 990879 41751 527972 312558 127413 589067 235692 763263 576273 673968 878958 801683 416735 761193 786002 976011 19080 239783 520856 528362 301713 271466 209218 729258 149997 912627 361988 869586 390413 607566 699178 708477 614029 148933 69721 411789 803215 426483 887957 649219 287117 867186 721000 853347 582209 923591 900266 666739 323871 649384 708979 606018 712193 811808 512477 768143 901961 315501 448848 624310 232661 527699 877357 466641 937945 338122 38726 743786 835739 648877 766898 204565 371450 222092 875431 370666 201129 714266 705095 605024 540450 760450 543552 84632 951921 782719 107386 925569 807587 83524 57259 265911 138027 572685 85058 37015 840562 874894 553063 90060 468003 403732 687037 90524 557407 74627 724047 87817 913041 162080 22255 651514 448364 421124 872194 340146 89997 348119 888751 868917 793650 878600 836488 146561 902033 469517 281712 464840 166925 731863 491453 531824 924772 683089 73873 909521 448157 678399 593218 412638 655810 593897 237917 809339 789907 372222 228433 761219 513243 202894 307209 177897 750539 546605 602347 643713 906980 342922 433192 595641 267069 385512 511924 284153 937158 130032 883546 112842 46516 703724 305741 493969 889138 130887 541772 953876 976390 654248 146857 522724 160103 16690 184552 738744 653892 254104 280823 35166 178674 820217 764487 248763 667570 917918 961627 166784 365673 861467 302454 56754 972509 595301 951392 657837 756341 10355 271988 182693 100442 460138 659164 743873 561026 531182 577823 998154 592078 114065 500241 962272 206110 514057 194402 365493 996742 105036 414788 547569 248178 74420 886008 7690 706885 851952 633854 843008 876045 302853 95150 836105 468015 993429 645670 911516 187196 935206 676632 474519 338757 566706 611543 288003 205726 169943 601735 326128 560605 951783 999984 711060 238729 715580 724531 858807 615885 806535 566739 636671 774755 618291 172878 377506 407917 807130 85296 64313 214054 728352 582256 324958 806152 383836 326258 626545 117684 55473 861672 796254 908830 164258 633890 132246 575777 824646 68281 345429 664019 186449 992955 362313 193289 521349 64467 180603 598801 651673 202652 458325 339252 962421 104481 677424 220156 948451 176183 187986 943386 260989 246442 81420 113441 126441 806753 130482 423365 914439 581063 589800 333723 405009 190 872567 924301 494892 332748 8944 886185 412384 851084 308695 848627 20450 559606 858619 9104 941609 178783 473733 723329 137812 685731 466473 804837 659727 212045 780378 254841 748881 266398 901361 517232 67044 321524 980314 299721 375001 270768 815190 152884 29342 826198 644797 740931 146542 88976 581283 547682 5770 733201 760101 895440 411142 949324 159536 631893 72596 149615 50216 378493 82704 291876 139832 677595 244850 149085 727680 418193 547800 307090 468497 477122 13050 788208 116509 202471 698066 933965 215546 794847 540675 77111 312050 984634 33554 535528 831920 312862 721626 96983 130933 155292 749337 689895 663782 118180 200344 507820 741593 235885 45516 699518 736461 892032 665247 816091 536542 753535 861218 613921 356050 10583 691262 164926 559429 463715 200009 691910 650677 243382 705813 666411 678689 370816 233932 327104 523233 571953 166388 359208 718581 774083 762234 7914 768520 744381 980804 306874 75757 418485 614080 534947 434463 374123 270837 690598 624496 999619 692861 424756 987223 905938 471758 268062 118934 872004 609312 918051 737493 281296 603939 323889 227176 567490 914132 896217 57567 155180 297436 294602 763280 747984 929190 732477 262417 579639 3956 225454 661744 425145 802188 174152 957254 476507 915809 472612 423322 879894 619749 401908 963709 123099 920064 15637 900067 355887 455246 993815 968928 321157 951801 936454 943433 304210 155872 459710 76826 63820 635492 493165 102630 206662 115174 491225 16830 552981 777098 12594 996055 338842 138436 861147 509837 93260 20277 434903 924426 307479 799372 238670 259653 450279 419826 59986 36239 920865 89912 207730 752091 617573 437844 184046 53352 123158 725399 324381 492092 558728 48398 676011 12800 280329 871184 278126 529781 912429 465311 826267 78260 155099 759009 858749 892046 610597 448072 795224 930088 449196 451430 962182 778080 461094 7476 576583 812277 62305 629331 792165 970931 800490 574333 387287 709864 187386 560965 884892 266701 757089 20223 582366 840633 293277 427886 248828 751317 855899 758450 764909 413151 581601 690940 67688 283735 97739 410824 792820 924092 171454 640715 11223 642203 904809 243768 460197 52790 371159 975489 178789 366627 157722 439180 574182 588926 742805 795542 167301 883483 619653 790019 189611 304868 873924 793462 69078 836260 842902 500943 777817 767851 995186 557103 390435 812889 799095 551694 537411 729423 88918 890842 65649 525662 707994 591598 600065 438613 384132 321559 606861 16423 751659 758839 713812 199903 176926 62524 581508 86759 93273 75144 455639 555825 649448 30318 797615 478030 79847 693078 197407 229959 220248 473132 134531 790130 19666 757309 764221 489543 865584 290737 44536 998007 536737 92402 732003 775129 106780 603980 749050 486719 926073 228499 824003 846046 276426 103848 367213 848848 210593 951137 754466 268250 619777 565598 490213 163485 629842 652485 123547 64716 314503 332879 42104 3231 454052 505527 607486 204833 916709 147990 529541 797677 814481 74643 689779 708709 658176 966137 76985 843554 482541 27403 927799 216218 624512 845120 288884 570760 139256 152202 25308 64159 40139 753893 382629 150766 796788 19094 868099 353883 148093 672419 683397 296100 885272 961485 795795 152127 286036 909785 445231 519407 426270 3447 563006 605090 686268 483836 215159 151293 701333 890499 550013 221133 900927 180023 618690 128711 538457 911234 698112 28568 385025 545669 225739 180122 412028 786107 485977 983998 802325 231397 947153 344489 163333 157412 381180 280734 122186 626750 728434 843371 300293 239871 8541 680080 648258 432189 519678 208567 342150 83972 983199 474523 431819 742462 378341 519788 799428 328665 791541 526433 472943 834315 527492 580335 507181 217155 690566 149328 359920 213044 559986 39699 773355 659318 478559 70533 176750 908650 998890 821484 494148 639927 281876 660240 857963 732786 961819 701312 875382 430655 15339 209888 334283 471629 255687 225361 608111 645062 671875 22906 560768 67446 425431 343989 380463 331537 439927 194791 907451 750022 934715 794141 292933 779575 569103 447496 413811 533798 586099 729451 361473 426456 628764 493522 789478 507601 803694 953906 565657 662058 145831 94435 542540 949719 628461 782096 810728 248854 907022 747965 712582 977638 455341 543003 901756 464219 639205 159455 565347 651936 179459 714806 319206 166445 604333 695974 824738 297912 155134 718704 903374 942541 246636 590394 800017 628821 396288 708766 342689 632679 488417 911814 803142 959089 665354 899100 684225 539117 562308 591020 390023 259627 716339 979270 192185 703137 81416 787392 534970 598405 110573 346157 444067 270009 478919 649163 374869 373317 265698 954138 510540 369613 127603 103801 79708 916353 469176 705307 265579 923039 383951 92953 264602 899092 7738 81609 107848 775605 347371 41195 131636 408249 379752 320743 244505 68219 202033 267161 132833 295308 339391 927779 342383 277638 200754 406778 549305 780990 56507 942314 473775 341237 933195 462522 997141 924361 706897 369588 872894 465003 599564 915809 936400 769006 255467 810102 203029 469834 272362 424100 970952 91021 672887 59451 433400 254469 823813 363052 129344 807185 992032 426157 608552 887078 624104 218603 549313 600922 845338 28690 205551 478834 155219 110487 186224 897143 823557 479066 847827 683699 301383 990571 283237 866502 695438 674037 599262 850578 437713 557209 861750 965371 731270 743575 118132 302311 159976 186742 767956 984181 108183 910051 715901 726433 379819 121338 417258 677886 606305 914434 888244 16742 616548 872350 949116 59562 709028 353439 449069 228296 466200 4059 799053 4855 715272 313663 998504 997260 47845 475794 846468 774191 100432 493865 497958 839940 322686 399580 349590 777955 530371 695188 339903 979901 233822 912052 479426 543599 40614 196287 867190 53774 893353 764888 379822 727111 937552 742790 814729 741158 867986 766033 29449 759348 186339 269660 201416 45858 711747 771181 409307 826208 670982 185532 870389 25976 661908 633780 792401 587956 859701 554565 84348 531164 321599 632834 550289 383159 779147 36264 480387 448556 986591 253315 83651 296124 997154 64139 2515 612939 612491 885471 423151 582784 10637 519474 298951 822978 910264 466578 187125 146529 908037 950416 310120 316570 786645 406037 409571 711047 890151 59215 883861 733058 761300 582038 993704 415693 655180 657135 38376 831143 334988 973477 704752 154921 485974 954448 470017 171165 661835 21761 786233 509768 777295 444049 482337 449437 527479 559859 151123 85571 426130 720104 564850 168100 114515 2288 781620 566256 174780 546116 974054 838351 590942 737347 472259 492214 87978 139382 872463 166156 93322 227409 823073 714860 79507 104462 529566 239884 424124 25443 575388 415734 207959 870696 205441 65022 551063 534471 33891 549450 260056 395897 230563 213587 713425 550300 636539 648278 492096 70105 913027 453968 926638 920010 764573 826438 769278 843742 648790 924452 771241 523850 604705 825582 2751 974361 932910 559616 272690 185454 67704 526401 586948 903355 532312 524383 841084 287759 201978 729602 572540 157852 634846 113175 447556 804573 447955 384010 805552 50187 882227 278101 924913 528598 951403 330255 674074 404095 632644 103019 491065 706075 313110 540137 738059 751409 98734 879376 387965 30719 212947 527752 654178 920094 643333 606707 507378 782890 2251 343397 59855 821278 123787 876033 444667 742123 667543 137825 708549 661631 84703 527715 135777 763525 783123 998859 976919 262024 254562 271928 955274 873116 432883 944964 442992 356692 951576 716891 646598 463400 219981 784153 928044 631824 508877 84643 665987 420624 601982 224736 779257 656743 458133 392999 647465 361707 227979 971031 740645 469525 432749 298108 817065 89292 487319 166811 50468 394233 221418 481218 177232 125050 588722 123677 970721 416907 54400 537060 729789 519597 422350 80025 22578 130156 766192 512635 549718 5900 341214 850841 28321 203331 639796 722360 180059 604783 414076 143151 416018 344769 948824 809830 616774 290852 122093 11980 176335 785670 563123 422070 83502 993491 672749 923543 830113 494786 103431 42870