1000 999 228137386659982800
728005418 809828535 135886727 573779623 718115526 7141601 839927402 585804835 552974346 23145143 748804046 374618425 404366326 520288629 716581268 767691118 608776282 885151356 791670670 238752397 672291354 389179275 782717375 818935006 751025514 661774601 788398239 766435695 508488210 165879864 689419092 482252879 635747754 870375299 458661882 519627469 365499871 385650865 2003931 134116797 98695852 869948718 324695479 406198706 168789153 166895689 672538109 100629829 153229087 807524720 734063887 855071052 383380122 840092789 168119682 977199907 623352021 838724556 727377499 95092454 859088169 991414986 534055762 514416052 197283517 294413799 739090 979720685 348066510 327283964 123912567 455614836 619485929 128321413 1956814 456625646 120331052 115645152 751705368 825962241 923815560 383640204 811057222 187479189 441382145 977547882 144870526 354460438 22504427 704268543 563758420 888800175 358740526 942776751 443696913 790332047 816149123 462463235 94998767 890018600 403555253 712377060 365335387 599707242 591725793 363071197 993155121 804921100 244721589 697211996 983607043 47133123 544880820 871737584 270774098 644621705 994103151 666388620 654543058 386863575 703064781 7503810 750148010 102727914 878416708 119368713 758420657 803020801 339236125 501212664 552992690 682575772 227725491 211768711 840747432 66653630 404672692 616932948 622547714 952292396 685424222 497855963 576125920 738861740 895602626 348192701 415385683 366058310 910571525 740153850 265553568 591738502 413250457 179352886 411145597 98167223 914226312 702429431 703966802 102729000 938271401 661944804 270660474 713534059 162265064 17628167 978289279 606723217 908930 32521484 269538912 454693998 794005317 278045823 33344973 421940443 224851924 858929169 19732329 41044718 105748705 22525396 673664007 488183875 226123377 63761018 775983342 729562422 576199195 526274457 168840213 819897638 985615176 497726441 30208614 112201396 108100468 421117827 748821502 464540673 422989931 618345508 898514539 372780275 573589132 994608487 472295660 756416879 546434825 138513166 820331189 693765024 429156901 710363962 994472744 652678190 567405428 408630445 345162267 170942600 935642653 389559055 372684312 238933786 842417435 892705062 794357400 890042774 894304631 274681627 367146055 329560879 348519055 876852923 459745603 900564185 734431826 86556083 815294300 968806794 799075201 140818387 125850197 997970556 449295856 705120588 835708961 995572584 932719298 929575665 683517222 625958091 579824303 899579001 66320509 23265316 929281089 733650619 487817775 518825523 459193874 881930224 755089785 880587068 317794575 643433459 365062920 756691266 724365496 696619140 205286206 388856907 862403421 983112064 793688682 282684578 322755681 861259562 697357075 274148111 206538363 408047717 980416046 544863009 147416048 747449079 83450211 835741028 324072154 55923656 35048779 130674603 923582307 516348704 688122292 952198982 203427337 578963691 915054043 316487500 808405980 633553656 912938672 912088787 983353531 111023413 76739861 488676146 400337818 779635701 547340319 819911237 528484543 23763498 294999379 112573096 775543296 549458346 622720745 636674042 767125765 872224621 444919308 627473692 858424204 586634188 934919448 745960047 908991391 860639940 609998810 96557081 171432415 359645233 785944019 93424704 813926333 405109267 780526709 808468300 34342331 941505227 521817443 490269225 315737518 73576798 938084021 355755138 51386623 224476080 892751153 681235719 50634469 248585930 630252691 794375079 388880555 882210581 755367877 935907286 634738672 138748572 357347111 897307336 94131426 603888973 585692872 928732595 504275585 347395896 636701354 483344913 633232098 655478990 221782273 574121435 130905961 802777890 658723956 779941838 921196813 557729323 418231898 834001321 734091927 399535872 611419390 606325357 405542114 855237658 684222940 599787163 102986524 852764565 817985505 97200249 72178947 958943086 654036909 857387597 394356521 54955973 256277972 151337119 459196208 354012957 162762008 508133499 170921486 733414039 293900464 295178668 260383818 337401402 953624709 413655298 560861756 68781869 763202415 823876236 132721232 164038650 157081979 309549534 826777923 768332493 587421735 206916172 141241444 613239731 64887972 856173869 144602580 749635291 117100563 28002328 745124550 195753175 8219080 423276329 200367039 923044060 413417354 329548605 645659350 115534077 112782288 854404657 939592181 434781299 406681093 552568102 926663957 371267031 105821380 446355648 477547653 567930214 736916507 450220898 741793572 575463740 178828236 94844274 228189858 34696601 22724487 785666459 936195523 12899102 190766897 724227846 983951515 752765200 460929824 893950879 499930322 304022932 634034780 555889238 209468384 584748529 29803231 932064602 302795090 412839121 703500757 833491039 926531843 469876351 43555805 975780569 212624227 304301865 911380805 600441918 468833715 139555103 612102225 467788360 923522118 790098706 153923444 888769840 972252354 945160277 522155412 470634483 960024668 858765087 836032586 424291985 600296479 980720327 209567263 113066056 451699493 169638406 267637968 806181341 228661979 523340600 655585675 96433106 528572737 358117018 894809903 151407792 939285799 175401101 588954767 630097727 551266929 344025041 259942575 883822793 738022996 44620746 73227013 363220314 403097494 152922814 52090809 462612994 756504785 813259797 548104164 528914192 553869999 187046551 782247380 423828568 856580143 640362161 41760070 870465390 115295454 430930096 710307242 822971369 624839967 661278979 292395619 756089248 522249315 252186748 122631940 514927343 671659377 367577231 330486675 883147507 308264607 565488018 181615304 658647497 666415638 793301243 50181199 343509203 819413009 925387173 982557441 591727346 994630430 159534090 72833327 696790220 915040859 285078153 94914263 668317447 553598905 308706209 6069228 698332811 581540412 144213556 369274001 46182084 883992121 626473413 226089310 933724638 800398231 913668281 482612121 106515718 396928014 974598297 532546942 306756783 234636138 484661838 59863672 698496714 328849864 411536995 308737892 609473804 578409942 451625799 659022036 938197291 343308567 800610184 472355658 765928737 752368669 482497047 326202744 57633127 507570893 298413706 272482950 964806459 547844766 756207957 456424524 340037338 814367449 74565136 456622482 388446661 412160730 79985076 620536919 52278528 390600780 260914909 974702599 897080654 68165489 868742152 619277251 396398966 8104792 472832470 826774685 572937857 576134180 745842503 545323480 884656632 731056971 331163648 294945579 376289834 938264532 401465989 601898751 594280548 382366359 949856894 594470060 777350454 700193409 928934134 986903231 321044660 564908749 780748951 948258103 149615282 285091659 828191726 450624963 144289031 856734364 400769453 604282373 133301194 20275315 992649955 133784017 35842968 334536661 523780933 560220526 381726155 620443993 953360233 349762003 469234883 372546409 964592389 224921323 269773857 245579391 213669684 885318609 569207046 185621864 358074544 620943124 784543320 760608132 865816088 957044468 495405309 768045827 243490347 204930978 938780190 781480744 133370891 990732163 599307621 684063882 216113531 357736813 479533886 61648206 345738529 458623208 505842457 200433005 533651140 427071087 841333670 772775668 739662734 686110636 394739991 404616766 79545930 564049342 610679137 433946172 467217318 585762166 980553850 67436205 939827314 375688084 117074076 690166885 969211871 958691087 482279552 398573962 294696385 700923722 400896932 560436689 277057741 609261663 567574149 369723077 460083931 595406680 246191333 786036224 507264804 278986864 160655365 560150896 913607812 145001301 722162923 870612371 426983865 263958377 278821021 414050746 283819425 896568828 776174692 219852361 705398656 851894931 417070602 805019893 362290999 248520484 194945563 595593988 969302413 437943895 145527335 629903760 504703082 886877638 299820798 365774788 234934550 715577405 336027890 881195292 622896766 670883322 683095064 11012009 680083311 200553197 458958983 881132618 76124376 703536889 891550358 549286644 770160652 258537009 427914530 633838827 549670141 66829083 415202757 257362694 730188930 755977968 409703712 836234222 231401105 610315737 23054609 825937502 395920517 286486835 680088829 949110628 443023704 160654795 219869703 501065374 270537706 553655330 27069270 266158718 126783288 493363370 444338259 557138054 513069221 217718791 66446567 776520076 345068084 471256911 291310529 675253751 533788362 395696714 586342542 44166655 389407344 294251441 603591231 690920944 444947087 652916082 890955078 529948775 793331763 353929962 787321816 455073939 829170248 705611049 138548267 711348853 617313759 91854129 261146809 825443616 142953065 601021495 920651899 713284857 132772346 718593504 393258287 485497847 632371591 320118917 883489170 722974179 967028520 934942575 130661798 70848153 538155606 992184090 69694189 470228037 537261613 956456310 545416875 626869670 340637099 717512225 324510247 706097742 925178863 541009581 932528874 591434464 888202362 90514656 75336446 299206992 883442033 941876974 880616751 349920038 532101592 587863489 45251917 613883322 464012247 786478897 219460712 824313977 657428729 49582668 121467666 609001758 818818664 223832974 498077088 56009721 387145010 674221353 876137577 704538667 933979782 791525183 976304132 293404648 885043191 862759458 566915470 683984563 870995383 610901146 787513057 267555748 626652893 516970526 985348830 67151781 320021919 418464537 398944676 238352304 144504216 257604902 547634901 515672850 699932163 952624980 86098903 11675051 737187325 773936227 488189968 239240747 289764550 486766341 10396457 851462742 691487744 780511261 614374220 760230721 110823406 987040514 367447910 477297554 526549942 973335485 102816613 779010499 865739679 173564742 923596921 49790046 605580115 249765834 974865239