1000 499 1500
922719375 894875932 854481639 917453985 322080508 340539908 432396554 126843799 908541520 853873212 971935550 372895470 431921080 564401656 748923476 449794055 485234258 803545481 259765438 731490158 204428695 903559460 638616378 381062857 677803447 543804620 507991438 553076332 584469156 100218291 729202855 956750280 858863660 636622296 542453807 37042747 197392580 696674055 547474325 398008947 967358441 349962592 323248594 5770972 439138919 61717057 249908411 680204897 443985756 817082163 533991167 344380661 113663041 374696153 134698228 939148682 473566120 91763185 359468857 456374963 956601151 352576844 799838997 51268419 124110763 143202501 759610992 988146703 972162910 83139292 511923971 722258568 121787951 183394756 443163899 10955188 924762990 950552744 44207006 122046662 837721685 195254450 40208514 740969877 201063980 703233866 196404783 159090181 76619153 978358477 343754980 477854582 380416177 860989742 323214611 50729847 8614097 292392279 118813161 786779727 29628351 282255149 289153515 836103158 705925415 463594589 749123868 644095184 88395420 968921985 504333622 187592262 913414131 587338439 8080370 41299531 611382673 315956661 866268132 183896669 185854662 256014513 874568263 642773735 656344332 937783156 776063058 464254762 526239763 976765770 547073578 659807261 96160510 61650864 210560324 882567151 195050397 812562904 442987161 901062080 367831961 111188288 822098806 403875660 730969180 634968001 72509432 19394477 469476365 425222092 116360622 870235907 790268261 88976402 754258660 603367025 692823880 500532699 844981543 766320745 5910582 748054333 873738714 796166331 934576550 118418387 376606853 946360847 21793658 31946281 652743736 664361510 524860207 229993999 456031875 140079945 253625790 439704863 450502042 708033295 773787340 32943349 875577779 106952482 615538354 180555345 862102101 272113151 805358397 578340912 688794858 689346356 236655296 653181419 10960582 802253441 270483593 88464017 443659344 415471172 503206698 105000494 131579128 624609360 550696945 301236240 322459471 640657772 773806425 341444823 347006764 770195491 521169130 685096177 400466534 683771300 559713023 683177811 623864219 839563075 440089630 337147492 271348319 463722174 471592803 24379638 681626937 320628142 676625481 466547956 812077061 229109355 84543740 860557713 178316323 28410996 90593264 174678509 468359687 182667766 711816095 113602787 861988083 109340825 604084101 991237662 942628181 967028298 762287569 292166948 209437710 368637292 736919117 245477020 105302464 959505303 2037299 5706098 468441672 587869787 667822600 426877281 10078089 656471667 635249563 916044143 83287300 93960040 197563304 318369775 790259878 148033741 783855576 861947733 736532106 562217188 605822002 529491821 140158481 423250259 493059892 243859338 640077336 510526236 99770820 685859754 70488458 691253989 522433966 138474193 554833559 933175314 728243126 482291868 512631425 546545911 997938040 7851316 931244474 239800159 260871636 752184201 307057825 54245212 455420443 817311880 349698424 335635288 418880194 477019896 287445009 842729194 109096216 183048011 618251630 297747810 203859524 918706863 981993087 65774895 598227210 34984757 750606573 479363717 619427614 986173015 131155903 866355625 35597529 995905054 397737450 289476899 833978083 220415123 820475183 781748221 991734034 876629238 993558772 556385385 584852094 758029273 385151088 428874419 324390160 478691430 857719200 139322450 288810529 206006086 145655181 442779885 513887476 205741442 769612656 170919728 925056936 995506388 255021709 112208053 967283636 996803257 994167538 89591701 179408021 783485073 946317514 815471113 728683503 129724189 17668846 220674488 530489904 981313596 412983867 115617320 891914031 635312099 819440121 130345252 565509895 33770291 254075220 1073059 709046434 611854899 904474023 474628004 736535544 445014765 574786114 937259484 8642627 46973875 117898500 852865061 117846437 883155382 8428902 372435117 942798940 287788809 137453762 513291119 112990448 592096488 173005351 572681104 604971867 617788367 58414920 970517550 101276064 16628059 579090019 866094288 540794720 267442090 68135109 52990135 170694426 530307254 637893520 39429018 726357982 107088902 254230793 544372166 522422180 878915016 810849966 405180069 221189549 859558640 57150400 69430689 211949548 612829338 866865841 180544586 982271259 968149886 850509980 904217893 992950592 468591133 185919772 844118578 662142568 416106740 442652570 253964542 54271101 899382231 824902045 154990475 515154635 75600155 746467220 548066054 145705703 17278562 560173457 590703858 301431114 107292310 741505326 592101059 822154069 622690638 144951545 924621409 58416302 130951008 917825980 871990923 339723411 975452926 660195946 116056079 225394688 283696764 332342041 50984406 493249213 408604071 19717147 124558676 202819126 437251205 86581287 486414098 32561737 774081781 443811664 581348179 401958324 415380861 791644554 510565781 693737212 786989005 330258389 96647315 35474174 483346343 595386484 582656879 16379888 107037975 691263413 588170419 264994510 548038480 288491685 793782539 585611791 804124725 151787933 70189548 144703099 632513401 157389139 147015130 467600879 28881410 472583127 911500962 241485478 289514660 504373515 258165743 815365438 215135667 849139717 103729451 942516927 207693131 906099022 813650505 365201201 582452474 78463405 235833801 645731604 29807754 428567873 645100879 379361587 855438078 923499844 911660563 848678627 101125533 166513116 781708398 702619352 887086959 82735254 233965802 820092486 154416473 84967682 498761780 525227975 160126446 117004357 233525102 347671347 25854 52281170 284959892 457839806 364329143 392294184 344416022 25451909 792215712 488447387 26733525 593026684 999129708 202295902 120257188 790991668 675665422 95020831 559970934 891677801 140492952 124888092 79576056 728313154 589508704 208578076 290810351 844509372 598449753 754337640 707348329 995137002 832945970 572725254 904458463 70109505 731769560 278911078 241667520 22787050 199459174 223766016 997627916 882409117 153308430 402843317 108532156 572006116 328953171 644370284 403341955 107250632 785469219 976191335 466323376 759064550 195406135 810239402 792761579 879828250 665417297 506356809 46174715 917389807 914313594 251702670 473437600 914255214 903429820 656508768 691960768 835938861 989643045 215574920 611206809 389615575 692288471 31846330 892076596 272368172 446144969 144517458 769232752 408566270 462838677 518510881 175153626 611698161 827114938 335192042 779576330 740685123 356587788 143189377 94889189 693326808 101089869 518282138 651977075 439864114 133534231 202702719 83052062 1789946 456029132 876293038 947734286 694416347 674386931 153892964 63450198 840602954 459768542 262748211 562170150 687649701 180055099 944679481 477299234 690434053 976116185 534526085 531123425 214617096 773669971 91646106 780925135 855222181 813527364 354635578 155109168 304371137 137691697 978298624 892665848 331821548 820248853 659943881 383739329 667460639 732277111 848414963 567513157 135834617 231507585 526474776 853360364 729092397 428968676 337919020 311526466 138234922 788746225 666759848 726401979 812880440 637120803 21140107 908284400 725444493 995914152 764861780 754331476 231982947 296192595 156219284 446243352 131859442 943828495 807527099 507414351 356547233 388644640 138559789 408117225 20640717 282433182 123826993 514448195 66752266 224840422 940983875 489804198 90242585 875986180 204868204 54725277 44323057 472925664 583573110 823925127 274992325 493207786 504217072 180690860 746459198 627985525 58141565 495589824 914510784 902987384 985118781 648930490 543712991 592316041 137461900 395012202 651129489 662126529 965975829 646079516 788769224 390299926 217541209 469604374 771769677 989345187 34670753 171630414 581316775 17735904 689984226 910180626 423918264 545644497 398552605 213524692 924325544 752903066 120416346 287018722 936676150 239883072 909536404 833050175 975368522 521567594 41526962 582578496 467560329 353286509 653423466 731462442 319103696 889850051 922277586 9285542 884058686 183207949 649344142 414505740 132359562 109290764 684544196 164054019 129132248 469646894 952926646 980539899 145906254 422732951 710919318 800662068 147142301 716088548 26055088 660793432 355319156 13279669 586898409 304830734 729058318 570362055 62748542 758320741 119883157 417218704 533548755 945545085 85498645 51246995 465942406 487073452 13459111 903871353 239290648 206792862 217072485 30996619 492805158 267367975 352387776 64069996 523159233 473793369 135189924 135912905 238129313 108395136 653220184 724552995 643040537 376889432 678082248 943888411 409959938 835624791 364612921 295762315 320856494 434392779 376150798 446313228 237372656 711991541 358172916 698940186 471263319 960877746 264821665 70359794 236401465 312203828 565628075 91143281 522861243 321242149 681503173 170826622 547080987 393164800 627664450 332652175 921838566 516538388 226295675 541069188 536596069 509357732 558435962 365085573 273665866 672112159 952988697 329737936 341592515 24603268 59637951 116659279 654515372 564798190 427680470 195938800 64489237 302847477 729159661 215080406 849369808 507665002 645205494 506414065 135534921 449691854 597428443 994018966 859953669 502447855 401046629 614172997 689867810 184054365 631224370 382353060 674882692 386944479 282055119 612002374 25738074 730897126 167312740 112066783 342113472 463920147 788787060 80415026 298273322 724811657 139096041 163337474 634603871 653806043 215685727 222437394 238621643 687326278 971553447 876919376 678424684 245460335 281101612 739685060 684672033 692623324 265296625 949315492 27796844 863447097 162833278 257895692 103757110 5304926 828233226 894593880 805509209 454369153 523543642 59038370 483120191 872947523 372079495 910785326 802386504 315185683 921978923 466811688 852794956 255195511 888029703 590940765 634362986 336781210