1000 401 666614 859763 463405 228610 567078 993316 278623 630258 706442 228671 504462 423667 971047 650799 845724 106543 449743 80075 701461 482894 932144 263284 301343 559242 77810 691430 39503 293131 623900 74572 299299 347552 976822 86854 203875 44741 147408 277017 478798 524130 456301 749897 844219 738259 527254 857642 588603 889137 885186 939022 9812 462154 418927 631995 572973 254280 345927 140553 951676 542307 638192 793897 408683 406976 182517 31470 140234 220468 499071 743687 121910 592312 290161 912037 516431 507077 92246 969971 478922 854962 331139 771809 332753 91716 893937 904352 981629 117598 145041 389394 758770 794130 122300 136090 192371 684433 427866 743753 573853 319729 720799 172451 974429 286893 254544 638978 919827 673018 72526 913429 20282 176833 622636 886261 100789 852168 946388 902388 305126 324013 734247 946852 647651 577778 792723 463023 423773 437060 854682 119314 181457 546303 540162 666668 315358 135149 208071 383014 949950 254492 214522 249764 346351 961833 59256 142017 690082 848503 474015 406684 903285 848951 342239 711875 976990 454805 287421 693378 925999 445143 221904 612801 771727 565599 474524 360242 81805 781030 958909 711336 812947 884937 868711 364034 881131 625 637525 173826 316915 546528 876360 789327 172313 107696 644872 678255 864149 181124 592010 270733 321237 905071 155734 620780 37646 834444 991055 17128 652890 703814 267581 221454 733030 868870 489817 812183 422333 323065 489778 925601 366269 485186 167194 999340 60985 79049 75147 369611 802171 113317 268185 461516 154192 689881 923076 663810 595223 844238 895093 172933 262045 244668 235275 612470 504981 429735 810668 42873 267309 936428 254340 909371 491848 842662 571190 333138 820625 514851 950235 942710 134329 790489 750445 360049 601082 584751 407797 174790 262559 117123 792485 768241 300550 29897 988439 145975 289263 382097 483073 881201 876413 290747 901970 462063 370121 539699 143943 927638 592185 136641 372221 278642 643432 438084 227542 158120 851909 990065 964061 75423 677774 602301 15564 191823 994544 814203 812077 673142 681306 319538 441445 209104 682673 599486 228643 276507 683696 704969 789264 842946 64063 243118 460707 499146 549175 250867 445282 194839 258115 916023 747368 283171 22420 187139 391073 1949 441270 117110 492671 717577 926108 635945 565727 323908 639095 682595 634586 910792 891330 977572 569142 679710 891793 669444 700183 167935 149844 384570 544971 910191 122786 995664 598965 537244 638738 65509 496314 614680 77711 544513 482871 566332 329906 230971 243350 201409 892863 21193 757962 665705 18556 622350 434618 597801 973551 318644 383867 105020 980123 24326 370803 182927 32694 3106 170856 849378 639863 15027 663159 519557 725018 393896 972746 319891 637288 997990 660576 809822 383751 78269 411525 967847 870685 211060 482959 541482 169350 27427 779499 790632 529525 240678 362782 1054 556193 751988 782953 90754 285498 600191 123973 687055 957938 570489 467721 513254 690909 409160 698010 955020 861036 140108 190763 400379 538975 603722 786546 292795 629699 382926 134615 755419 847960 86139 153345 8419 166348 793898 737181 327945 363352 735697 624053 411577 605655 597709 978130 902336 437796 52413 894410 567310 576718 138566 918175 845395 606818 26865 39009 120662 530441 403850 961441 581724 543673 411126 952011 560363 689574 661300 380229 774931 450633 829663 470415 437302 838723 183069 352182 463364 835179 598074 899516 450265 251059 453483 636267 354709 754535 942680 316202 590796 838447 541938 612425 614213 43493 331122 13539 686700 639927 833313 740720 726582 153752 872326 491842 829466 345247 627334 694395 646400 547462 547493 409680 388497 74047 605187 827785 83671 526222 42752 488854 769341 585367 635641 235886 442952 503190 171416 926650 372355 942609 534746 785484 952890 154429 548154 393543 741522 188913 404566 284196 317217 167687 586168 311757 295865 680331 931436 836338 69363 358722 938920 42659 774775 558382 598941 755206 844900 796272 139005 303757 414321 429876 228473 461472 912896 988921 526631 251432 933543 992221 736580 601199 545064 90975 218545 476034 887807 64717 861987 774449 97938 996247 427747 711191 824300 284978 742672 296245 272997 566398 674654 567148 248086 175716 650033 71634 170565 80812 416216 438727 701390 880536 862340 819057 234678 766557 533475 897745 291804 383960 78995 238706 249765 291341 638787 798951 344134 250219 513525 100527 940649 902632 477364 774873 202230 975160 772331 297751 868666 86837 978720 887527 940174 436363 801217 138232 406330 416862 464423 569193 181700 417882 982446 278479 56717 991419 694310 762451 630993 111938 988725 965765 634741 695100 544387 541702 767398 762228 229480 235061 85405 498369 680868 848995 317676 218718 111669 557899 87394 85245 806626 854990 794165 679355 413799 215591 971634 70422 105743 285804 940941 381418 575286 73555 806459 962560 639351 20225 920861 634706 764256 374073 617163 668573 876578 214671 365719 203422 492342 941966 333429 811388 947153 388828 211213 711738 826705 471801 684179 912338 479888 464198 833296 645911 801698 235146 153012 923086 249329 967034 50430 589075 504204 328734 514853 195492 859245 139565 896124 729322 113111 556015 803986 931343 669593 179047 580927 790124 721247 536668 747486 526174 940791 75251 849527 940249 294182 271196 424048 560567 909097 796241 655573 110745 944350 226712 732139 955609 144349 74000 691912 803755 787491 529993 782897 612886 507217 947309 598359 209706 729796 976542 277997 633005 555562 188163 626440 391467 767380 236168 735459 783369 355281 438561 283422 70084 641478 421647 573316 324361 677985 218887 868696 479801 602095 921260 595624 942208 368147 526176 742788 427264 427658 991559 782599 646488 375250 473934 403657 653487 716138 919048 799877 922598 28361 947489 460646 638609 593330 102786 180139 410162 963331 46323 885096 40356 229 822829 900557 704219 512803 586854 379738 953829 633095 319795 976661 220130 304164 968556 347185 636450 966218 894489 311630 799295 14901 372548 284161 271510 381486 10472 748200 129122 701176 426059 113175 853535 324701 971837 961242 543480 404219 314890 873119 612140 350394 44632 773374 267358 175262 917388 649615 942310 999778 90212 350223 341037 552035 258306 214633 732543 840304 28026 914879 119592 807504 33047 241597 265248 359964 910403 927836 316514 665338 333552 137862 117288 325289 212868 615229 157795 850830 372125 329819 571350 263544 84669 651262 664227 249117 499088 324546 107092 259726 653689 466009 73230 670434 552721 750691 115494 634579 683522 525716 243258 708659 188889 203038 547174 199107 602676 819742 568459 341520 138505 726626 223529 876742 301215 158024 83673 547270 453067 629223 308100 442689 681580 215340 111309 842375 79109 234060 272302 985745 613449 391958 868334 826400 909869 718874 344941 181939 34047 303216 156949 788177 39454 900451 196398 281087 60822 607208 615163 602402 701685 301948 256290 889811 959167 766596 392311 54501 266938 940425 724099 831305