1000 127 463964 380080 329187 153407 659756 241191 36529 144684 583363 419139 619784 292869 309735 425016 458826 248092 214711 535083 413753 125458 603989 109261 317578 12497 481437 609776 865560 723455 793209 195171 975288 629897 323916 460080 818037 471134 94092 850939 465219 960373 890984 951842 126775 581059 253504 683096 276402 376185 83363 163391 471117 399589 831234 752818 377006 977202 374462 458736 239562 311239 736018 26148 459882 93662 612633 400247 158628 454509 584829 585322 922535 734338 691480 207227 669711 667714 451352 750851 499517 506519 627107 720019 991123 679924 851224 260457 688024 133231 750704 98358 538500 395377 779209 534071 718072 702812 291588 884207 861011 727854 492357 845980 691728 166683 523466 306477 159160 104657 663654 132728 235998 457522 709900 969402 982921 184872 940183 838818 661618 160468 209644 248870 172506 95831 783916 545216 966445 177318 927287 817078 89862 396819 551486 873392 186509 150056 806684 860583 967677 322551 911359 550474 641250 564050 586113 862341 93733 351832 311597 404073 956598 974530 684351 650297 681827 121707 389695 785392 861790 224419 437607 20610 3525 999706 114773 289533 986521 327360 872937 817684 284276 376162 524641 430354 130424 413170 229498 477855 401035 44082 226268 273462 606164 206999 658075 67863 298394 90082 198530 394002 43870 257922 393493 650598 717898 616347 671952 609344 623834 92152 138668 923155 497114 151675 277166 86215 743718 230060 349460 949057 722962 340877 574470 769014 446241 866954 74984 245270 328303 816402 576667 762844 100368 60903 375761 318497 101698 429903 301772 44341 384360 600238 459383 327096 113053 969947 673202 485538 325540 129197 725337 946798 482189 435718 625848 917865 695391 207075 107687 400397 86916 448800 997058 895601 960406 375401 166641 761333 222599 113586 656582 556632 176641 2006 516288 989795 615262 190519 14948 665546 321550 811645 943394 846200 878478 107041 357803 690667 166827 423366 702698 109902 943278 607277 847207 807307 129175 526824 133433 213506 400093 664822 49110 637003 444578 357716 904488 101816 835509 348542 345528 462937 562150 790539 774767 123929 61636 501339 157584 959427 965186 70947 360931 815205 115336 869754 774907 780025 176055 621650 149738 242064 443372 873704 439170 240685 959390 75420 687511 712069 20671 929434 378120 113393 928918 477219 938966 912591 346937 245012 398416 892254 452047 757744 456934 34343 723683 766726 99714 981583 467773 135479 25901 973550 616478 677784 85639 982306 972325 997135 198746 776517 549490 116310 431499 195878 440472 499028 897383 577183 474383 217397 749852 50477 984295 628526 310228 694452 950971 879272 275758 425061 689910 406332 809080 196594 380259 438063 546082 547791 940707 732161 513252 442594 839172 772990 121242 85604 255773 411206 697574 372253 452914 462610 331413 272222 681805 298372 241066 933895 344687 872424 319177 184332 396023 789036 908566 526425 736615 169648 514802 947502 779984 582453 414794 477050 72349 765471 128565 79910 820075 277199 862927 671247 692784 582791 280640 432623 688074 779911 798684 411076 163100 829815 584022 676016 366196 779372 170217 521771 603252 836574 840991 536145 390232 975306 417262 783111 798851 97903 942671 144913 646214 769282 885733 148689 995510 541832 779676 138017 924900 496768 381224 853197 135927 637640 502459 449199 922573 568459 998891 868978 549090 675034 458924 693478 600808 648398 332269 649223 33822 438790 671688 918881 383248 627928 368676 522975 987053 352077 846927 544107 949490 24725 494370 674031 738735 841919 105425 110161 876874 171561 174689 579209 131811 639948 528859 751850 400060 532 862945 809240 233867 157602 994206 709242 816660 948818 904101 559266 425139 304997 712778 667634 480238 519618 482380 526408 628187 310454 923124 201450 7772 610091 411594 478213 255967 725283 982443 11819 625876 476638 233849 170996 252604 122956 990554 419530 19495 218906 456638 391878 440534 411785 540222 548371 764560 521511 155999 666916 918877 810980 439401 433283 602726 28689 985074 486134 596841 364770 667752 35891 697952 64097 297286 86447 16309 866711 523475 147143 385716 667392 940639 131532 218401 782916 947300 352662 958715 444184 33484 788018 583798 120627 574016 526157 427357 524273 805641 152873 478272 929113 999323 173899 80097 989385 23732 266025 110624 876406 442509 977378 391857 394418 61914 291539 28869 705040 401845 186133 299153 725015 964891 477534 741366 903274 198923 738200 486521 53372 914344 742375 774175 156737 623708 98677 29055 825568 134270 530171 335140 587992 437937 877441 874101 967956 745983 896251 846438 105092 854026 393270 634536 422909 815500 16615 755593 414001 542689 780829 380272 228092 569127 651402 337589 861834 58600 555341 953590 950547 93137 589969 95095 342265 721846 370581 802943 99972 333342 882122 462339 45954 920215 450688 705664 733907 581485 376322 18005 308155 408811 187424 815202 622897 1968 919126 331844 341760 774395 711523 197074 179099 309283 649537 934831 585518 304152 194383 256042 111864 895751 293666 151089 462519 656749 108997 493235 157657 409981 72252 654217 571964 48936 960321 906466 832800 275838 289025 21401 201035 445385 544965 455112 398590 282951 16217 740497 760917 670108 818366 448120 376153 648635 205062 213708 263717 80389 902555 780793 328177 903013 719702 398869 267835 79930 914400 437178 99558 723440 699843 182628 759367 33642 568433 151110 208325 262291 842874 663757 786017 379048 11175 804310 680768 328786 618285 883144 80586 983095 487393 982761 310051 265400 99683 873471 90951 320170 880749 700833 111008 375459 472262 60408 631024 563945 890284 653826 402914 974151 726257 616774 395743 900266 662136 865655 765256 326594 818448 112743 719036 759799 875008 183882 824924 830927 153052 758085 365373 617470 59857 300970 885095 561247 913823 776285 659226 708852 401482 51668 780821 394185 309597 816187 68055 934698 858248 292075 683804 162526 603039 323490 676055 935889 206831 114702 970704 338086 139126 491124 98871 691244 608160 587556 446516 589511 545187 553854 166041 489057 11792 211956 743189 193884 622255 389048 703609 131017 670543 625636 794274 298380 965148 603485 798592 424974 995604 642117 760917 231815 510673 372346 448198 259992 574684 279833 109084 634576 711540 807184 852377 669203 559231 42187 891387 912055 430518 312273 500254 141317 639475 728327 764524 360961 173435 765311 416042 739569 82902 537032 281078 134570 95034 825500 228021 837591 311094 556796 400812 382013 910375 623181 987453 63343 94137 661913 70065 926387 685502 876628 988557 43505 509005 464487 679971 929107 896066 820427 358809 972126 938145 872231 37105 237212 393349 907547 456541 408079 430724 204694 564116 768241 473360 230060 952119 173566 357364 25420 69227 372368 476886 640277 945250 659319 793676 651747 602361 256612 447765 432766 262149 141314 783151 884735 280750 433997 284090 782369 665367 626676 624590 869784 391313 636653 981402 460294 738850 353808 102592 135972 195382