1000 0 0 1 2 1
751103 789683 573261 759320 204083 582213 998020 554041 172192 585984 170816 847474 615253 414729 199132 178154 149919 538838 317239 368381 986579 413192 537094 224263 126174 269494 869912 557220 415697 808534 970368 676497 775318 982926 962490 851147 497757 819335 585660 832866 793514 731538 599186 791222 497956 827259 791875 123151 775028 43573 503864 498326 202189 773178 660717 379737 585595 574249 871042 545214 411478 204424 741682 722368 955161 514796 675070 396770 701438 962935 80764 84002 966738 757878 451008 256417 685993 166968 834616 124108 945390 880638 212150 366837 551698 668540 227943 281483 180699 542385 527146 803539 97874 945292 240326 613539 388429 497527 75738 251509 231028 107855 713212 980203 75439 256726 248622 412695 658793 427052 908548 209325 395896 605640 801482 141540 354476 896752 496065 531364 479194 464026 413619 945206 528765 792495 976605 368726 545413 123821 799189 540636 458955 782736 377387 19675 492490 92656 171749 222374 427885 940428 518622 93020 266698 887432 90681 262912 258259 429829 510830 552469 939776 976142 576654 667934 385542 971064 380348 598491 652087 538678 502176 600971 158673 115187 80917 229833 50199 214945 516246 373588 538236 473806 538047 317761 98972 216087 439135 190595 257632 579515 723245 334089 389401 303315 785360 778450 105281 144052 253877 223244 277043 675552 111412 76286 410594 115348 491708 396670 602937 389863 45869 602175 709356 392872 920509 408284 967334 260459 892147 266762 649901 544308 697558 780814 93052 757733 410714 554276 661394 894044 735005 17388 613491 581137 958867 562652 247420 462098 617385 613135 760763 632222 184654 629036 486210 139552 798464 290353 639439 802639 582619 983823 845616 668718 172561 980237 910454 987069 995344 579887 750204 624844 626052 901336 905235 772923 69553 218107 457546 165573 801066 344668 345280 934773 790432 865225 880329 112300 125596 587010 996191 252227 139892 8735 434101 184010 614199 322679 267533 11488 293423 483235 345121 627016 648868 583951 962288 136658 483426 605955 398461 287851 791131 198486 448046 501811 966681 323659 469444 12291 968832 191249 578765 391317 755282 574662 793138 336392 604549 344469 24016 347596 690866 914332 656740 822867 795256 920110 477188 799512 419211 402736 501005 682355 65998 640029 182683 428624 571231 480928 940300 237978 380155 919826 688258 855993 707697 991006 479284 422667 897343 727944 412117 340344 682596 825913 592935 568497 948010 749750 292716 939251 208880 361232 188203 698946 822781 276514 640750 335470 579386 218879 97110 490537 459259 990522 125097 234631 188453 750179 935856 689038 462085 782951 550809 604639 395275 251188 207584 202174 715737 635730 554373 715810 103929 515540 956431 611245 955863 606148 903099 831907 685134 338885 984175 876404 419077 507877 284451 130548 118909 811156 719410 399542 118042 320004 380289 95110 583079 726929 824527 306483 462733 903719 586440 208653 917830 363423 356891 834649 213621 429863 386075 640726 896547 945046 562420 421539 548783 883388 646192 325836 307180 855831 240495 639438 24203 6504 986765 977935 307134 319111 271160 285228 797605 824556 859206 449537 836540 770906 918728 350759 490444 760135 586495 721912 557186 357234 102627 940361 678113 415308 346238 262865 864109 712107 796421 27420 777585 167235 635217 462758 387151 239721 163339 947474 84646 497429 664180 744408 257567 918092 999432 801456 567474 949163 179954 604547 766299 938797 215298 685312 647509 580670 864463 431709 791525 970700 89751 487803 602709 338526 379084 975008 884256 521969 554945 729794 126180 777215 179635 318736 366873 638238 95376 682610 306331 943886 696039 540631 159466 491109 846424 470811 410655 418479 855285 986951 849842 648996 352259 153550 837345 268248 191331 242831 618159 443375 29064 922752 611285 438314 21868 25503 10693 527412 564053 187366 228910 643538 69590 252960 835937 669536 314489 647605 807992 665016 86362 998469 716103 531424 319278 595652 381228 427197 482951 107616 357970 263630 153846 189404 531766 335602 562864 90182 667009 262155 128318 811598 229598 480794 278929 832588 917021 177147 532719 931807 52453 100035 146579 361597 793169 992924 288117 78143 90625 464939 934889 363049 182649 33774 837163 787549 609471 984232 965956 526698 375770 146518 886412 197183 283253 62868 550916 871239 81772 767613 111614 155664 342036 427052 548574 566410 662674 266657 928573 653516 898045 691322 827067 109767 667591 272749 516091 413006 613954 531096 570361 658828 96456 597794 918745 552205 123315 628721 896637 266253 93947 144003 29937 652096 305635 750606 428267 573776 472458 180527 537955 746752 400500 80701 230751 141455 344719 739576 164040 681129 975044 977079 733127 759749 518591 887264 966004 98348 140608 530549 444649 901374 151100 702434 606170 414294 367730 482192 331066 614520 479372 547500 526810 475877 238482 811852 491399 233966 789430 18730 542873 189435 943796 432073 891774 601967 17618 757005 108599 76464 521536 521579 530826 126902 888811 503528 45556 289444 449235 920066 553836 357494 279987 713978 710946 39391 301022 632647 257190 505771 788665 997414 268443 34776 501307 448231 370581 491429 444007 478300 379236 869183 14476 629224 797993 887888 632807 910635 666581 205204 715378 347544 123486 617558 7206 135374 274430 8286 714343 305895 198365 506240 177068 807139 102614 814673 898633 361929 347821 394356 757236 501210 858323 198856 546583 157978 775735 214078 759421 951609 740020 366314 860593 223829 727203 290044 998353 190858 514570 321810 655263 962669 736623 514789 260083 178390 726778 403722 824851 239586 699040 682229 95560 356266 60067 291399 347733 135254 333361 791271 659918 55333 226805 700431 984571 799470 552840 346528 769526 660630 327646 291705 735736 464080 476666 854309 839587 691414 643546 654465 790267 870542 18472 288502 385693 526296 583377 350664 798046 314278 547493 422734 937110 184129 430483 346757 333012 405488 287584 747880 274850 113342 10964 375720 548544 426931 391462 836981 702521 784677 246522 894465 224710 835484 181666 617424 218852 249815 876923 537030 452182 80017 612224 572013 723014 832416 669537 6469 5609 226899 860042 308958 997660 74173 40611 465401 95963 95533 599984 336964 749066 783407 519821 815312 671254 248538 334125 277662 328035 236131 892936 346368 879745 671428 473104 330162 620440 637728 889961 786004 729564 561957 698147 373829 632830 111778 681126 179442 358205 477009 75197 82407 861575 705874 404083 711804 625262 884107 92145 965484 12444 497279 18780 712574 153896 597425 356995 321673 53424 419270 928737 970571 896586 114174 314542 465336 890173 524854 602306 668638 625330 815669 870539 881930 5764 811772 920421 436478 984468 337814 407516 581574 782825 742567 239457 325234 70717 388983 534234 637602 299993 781809 472608 115337 168339 728843 71628 803596 497334 914822 393478 98722 428818 761082 250992 854003 129523 119369 717456 604685 758506 643313 765464 303701 485416 568064 164582 957298 250409 912571