1000 1 1000
299890687 530448375 117474515 534773630 134745117 867893110 737407993 964657119 839401474 335278074 533064702 532670463 872413119 247050698 828399482 383770399 140808327 620493044 545061477 805298047 969932791 701351839 794720607 207565799 787726189 1055366 475841263 527826847 501443216 363158270 679707328 871497675 33554496 673197251 918552527 501380573 805289983 921033015 690573663 970943411 629109375 534728671 2491912 711981869 458881353 933560307 536472575 200252855 796504055 533442559 904836987 676424226 522123263 312855050 486500347 969339788 1048580 948068352 803415987 902660050 463601021 764892415 2424834 988998615 513277535 805305836 2909323 917613557 630714790 8712 872379327 790031535 801531875 16514 999290879 543849553 16386 517635407 513171047 524532056 476765494 800513527 536780139 657849789 268435456 168919841 971863995 777994191 994811399 44340746 871061536 972685311 805257151 805306239 791280169 985573127 901608947 805027839 578275022 464106679 769654738 536872012 16199621 768548819 971933177 803966972 128 131072 77614185 938426367 81688020 914309119 804118523 958725309 989716350 905900543 788512509 709362278 526385135 290767896 936352733 535478250 666172615 771030941 536866741 937426909 936867787 18194 997711613 906576316 454861002 796622715 218407936 783020404 774799322 528414462 103489572 192921403 16480 920929717 560340992 259779624 939519455 805287661 803209215 257332206 963632107 308901881 498556287 736100351 487768517 940308463 215556526 805043069 762950955 763885421 4458640 842992787 914350065 702882887 70497359 297277762 939257854 997384039 89642067 375552333 535133823 269763216 638940912 939391486 792182415 984544255 930577406 66092100 911801343 996145087 598728351 795869055 934524343 451866623 138452992 528347134 934803198 775946235 506236663 67680 536616789 449246572 354968704 939521916 537010176 971537918 939108223 528482299 796917691 586610670 461026375 630506486 871587701 805302110 532545397 757853151 533053430 738065919 56507635 60978607 857227922 528089015 36110376 935452525 996123927 595381919 996081147 33638400 916421059 453116452 339229965 4112 972029695 783806447 738196851 842510121 410127222 677311991 805222104 402653047 234879487 833226653 804249564 536821759 536870911 799080963 659373641 375377422 805172847 989855725 769439743 134222080 648863541 478121582 736663415 987234271 769654782 985005907 737927167 532278743 344663180 478035413 972781497 490726911 53792 997711871 533424615 344379424 805281759 536849917 527425503 145115302 750755839 127909315 532667903 889176063 532102329 486480542 536870903 938142070 435158654 623172391 507465215 360516 998244095 933740415 335464765 677494457 997310077 225564375 385353704 483212506 759168975 999726519 705593688 972947199 865578988 88279585 230651447 7588196 59350547 805302271 767509935 804712445 935325421 560433740 139594560 997162991 291517544 536875008 150458181 569050432 75702290 835581308 268796032 92907301 125831426 887942596 213335616 917749370 478418283 720969309 858438623 816537608 25147389 516843334 498790862 67586 815790580 736738815 671779110 258799202 64 846568008 524416 573137160 107476218 69676759 436633736 780873549 425113235 801103359 805287643 506937087 989462527 536723118 512617471 905871099 836970018 137887810 193270239 96435895 256 968726378 701632181 805297662 67110920 939442023 33554432 268436640 493092221 33579016 574165286 536870495 931043659 701644850 805279983 942601870 938999147 989790015 268697860 737076574 973078493 914094075 216504843 868153839 689955419 796913131 805200894 533118847 631502713 669969526 248721620 763363039 738131911 503316343 936621800 450542591 5205827 939382719 377410031 863436775 555294380 767361007 343818093 770441215 535276519 871366655 795992060 533767982 951483367 947253275 8003655 488669189 178731620 167204797 278021124 65560 256 796655615 935321567 938213375 934770683 803078143 939463423 538972761 535760179 803209191 536863703 931079916 929029092 801095677 939524094 842931629 805272566 25000702 996808870 535812031 951871439 928972671 796250040 502726110 935000061 151198209 973078335 477103553 989328503 535822253 271056916 985512958 989801983 469499903 770498555 394257407 939487230 962674586 436174845 752875199 790294767 776118352 393098471 859902504 860880862 808511300 858241390 810753225 68157440 205203489 898552830 233263592 139844441 371549221 887068124 69471752 999817215 249500456 912111358 801112063 996095807 603960949 469483509 2048 954568457 669440173 922476447 986838394 801106431 800123388 250342911 987659969 805043967 799014911 936840179 738189391 461007183 545325152 707739511 16420 617464315 83927056 262144 966750154 4194496 973637376 368453121 919637364 263510279 952331649 680472304 81447643 537235172 935194111 913161726 985241548 528416767 534445151 779340773 994728950 701955544 272224738 536543223 805304151 452982267 532627447 500988919 32768 803995639 172491264 696500504 238272636 485422807 832988487 65568 106957472 871626734 629707897 989855615 805296959 926799275 528473087 12763908 105929533 796327919 503275519 570556928 763359219 158969431 531083632 268238591 716032063 406927632 937672441 932429091 938995455 37602440 531365879 708886826 802903039 628620207 731453710 603971295 805271295 805008253 683407355 862910519 536838104 775812456 758480046 506804523 520026079 989661612 939360255 535797327 968814327 360648111 969815274 800890275 153220098 908991920 511700945 8389376 121274238 738197487 889190268 263978743 445158409 736100311 227238591 34298447 867607101 503167999 475239224 690762737 909897727 268435423 146870480 139023283 2228232 485378404 480301542 534511597 462864 872062806 845406660 16777217 16781376 50742279 864008189 805297407 939497471 67108864 898579393 937635258 805467538 922455551 486243007 187510737 651484392 360407037 975889345 435814245 549408996 354422017 285211305 536834015 771686362 297069805 2621510 683784659 262144 268505152 451326235 5242885 134086651 2162688 535558111 536859643 302260225 889159019 387969619 546706240 986689516 537534547 805273532 938233615 660673335 266347795 977072113 947898255 236953122 517660344 997864703 999283167 1181472 738187005 465204476 989312511 771751935 999718367 513390591 694751873 967437239 955973503 96935422 466988447 602053091 801111805 771735037 815238929 318762982 959047219 939388407 251641854 168838680 801073151 914356679 400556027 671022846 762247037 308577026 669877059 532672479 935290607 321336408 146352907 796487655 738181119 931002367 975560043 838789886 283248017 936968191 536834045 536869741 785632890 799473148 470946308 998210207 67110402 704117241 553085802 458756280 490733386 805174459 796655103 804519931 771751293 535739263 534724411 801079291 536862411 791539601 2105368 939515123 706752104 779436934 788495357 939294143 645573747 536796383 269615152 989790207 536863677 533594092 791726047 871592807 67108890 768859237 929630385 805306363 535559931 193047292 385859583 808469880 536346063 801046519 636415998 779253497 470426368 518909948 402513919 973012983 278560 916416511 921696244 80850264 999124820 549454340 939377663 603954043 955772637 726527805 324986242 989852665 939456511 536870911 178459196 784334449 5366406 166798137 769446455 188348911 277419008 510358582 517978610 34078784 289203338 670464479 517992397 834622974 800063487 704479083 673083625 361758689 663763438 255657316 761442456 939393023 503051743 603979844 328594265 904658929 4194304 346247172 901775356 536907784 375563748 640007108 959969644 460845055 928746764 666353147 798392313 5121 555745288 368340972 514849359 850362361 787480063 864932498 815800648 939392765 882321919 474920271 191881183 937160179 267373559 12582912 631263388 884540633 486818988 993778559 272899584 164356 570475520 939425275 871096143 849423020 736095182 938078705 381811305 513 515864059 568227773 273796999 973074295 935329791 870301694 402381873 920579071 519428015 16385 780709971 498104132 64 311883599 796835583 458718583 107335966 889056109 536864460 263796457 800815101 904229905 926119655 176622997 805287902 761151423 75546898 871229255 531627479 901224431 946770096 914133838 931134719 525597695 793378683 920911866 257 841912063 800579583 97853169 264109555 978181442 169700075 204082200 464186213 699819991 597606338 2885650 217701391 531869809 690078014 469760987 536803259 955239101 938475519 534509537 855315980 637219605 268435456 989724670 763361215 4194304 32 463791169 104646265 918289789 920649727 971862783 931135359 536862519 536859575 763230197 771751389 200758414 698880828 836222454 33587744 37552136 626948579 9175048 536875656 226671962 585637459 4210688 937426911 52562490 2099264 938440669 69208353 434790267 395526137 775431436 490664927 536739830 873000850 442735113 67108864 586582766 109052147 646043570 796653375 934281055 930868735 33685521 511218110 282202675 69244936 805232383 793769979 672669479 973045759 970915383 973012086 190184613 803204573 939489277 435087295 503283187 985661183 989327103 268439552 486538239 528212862 23459395 728940542 518362909 606225697 1280 536669943 939490269 779792303 268286570 937025534 496500206 1310736 989790143 989855734 989790191 972880756 720891885 738204354 431223979 802660333 973061535 922919509 864550731 931014511 536870913 67175424 800718255 201408544 493595086 7129899 804699115 996407293 48760832 189205684 981200877 972013167 264256 787479551 4227072 264240063 13172768 804691961 910205632 357948559 220830861 472449216 922599422 984144369 973068799 914948105 968924097 670433247 503046143 637895092 16778240 83895180 767553760 902901172 619483132 552931396 935163761 47912432 100382679 251913537 324953405 279068928 746586111 536879104 491748155 524802 771714751 804191743 721196793 477085688 397314 536592318 517437151 971954608 169561943