1000 103 670737224 725487311 939213258 31763625 728362801 797721215 169410803 561157100 182224931 956836906 163958933 12515072 583439615 380776427 487654656 995177898 896518939 252958058 32674820 982938457 786483885 104714083 844269712 465876139 599514057 425863640 799801657 59771901 380879471 202337635 211961184 6317790 56201735 719050833 152667693 583448341 484261880 626404251 40861034 693172825 811613370 25682949 228593534 461861741 225793459 927544008 144450109 217537676 451211460 729647281 526309711 55788777 733074923 186069115 200630792 176527623 297736181 415346238 407773923 50488216 571817460 376800242 993001638 721913346 333358208 128967689 300317364 693089615 606617566 914458125 1116295 218727488 791564610 301367541 379409933 342926003 229164812 284651258 985615284 476988646 270502847 23010248 393858577 80292941 724695417 889561126 244037974 806476971 448851646 794358650 509284324 198949224 821817039 489420949 941441374 51647969 653728542 971286349 995133915 298202708 18872468 694428660 908601913 32869137 718804519 355526710 101384482 953982370 902764531 539556949 204378266 945797069 827989327 221122286 704935890 860843648 355791828 506087840 456978252 556317825 380415279 995467788 86101522 728907944 293876254 630119997 566699223 841849538 162120814 623337165 526739845 585117492 347666925 999624121 247003268 477496724 560259157 227755300 574340589 506541563 619951542 61189868 974855459 874563488 991914215 637261242 308568530 947512622 538555139 628344209 460050119 896014787 180637439 344923327 961566800 905363613 214985964 59994240 266764550 96041868 534461857 78438615 705895803 230800682 803178735 414286535 963841555 628300744 153725912 507164315 197804629 850452323 922554055 739097392 650218158 39214121 781300272 756901301 851974736 359861421 138092034 64964431 936795840 735795238 869720060 554663622 75895032 41320366 606163222 846805096 4993739 945757576 412329867 111956272 437814545 591447886 405821308 823730500 804506914 846243349 796778611 846335084 139378828 586247044 440848975 363681921 496374303 716889389 407890672 172591855 224846913 3517448 870146285 847020986 888563598 341371478 609016372 977602105 530201976 638483139 280678596 568331198 928742744 575251178 220695778 842113610 82887778 904441669 276878479 230651775 661770135 774466984 209867056 423990511 110262847 749729360 897548020 710442931 849902214 937168020 804955112 517538118 864394562 471162864 645310230 419181733 147228861 384124676 81143081 529114508 903514352 766010783 2151897 511515547 727822744 180407998 137774843 788261132 882038459 304138908 707583529 370624402 923052283 562125172 872867659 152282935 177226368 50705058 49955528 477211675 843179608 349982778 273197721 929452839 468941226 609658884 410237921 134109307 999612425 511323314 263919099 384752396 469246468 749602363 291736303 649230342 832142863 372270597 71787663 606110656 239856141 512647335 898337607 732389401 330383733 542063909 847802338 167167850 23462643 749104938 419271083 870210291 179926812 934946694 682920465 71000556 857495058 713555276 462246001 66448290 348938852 252872907 749673612 80487576 125689269 238365823 54327998 310972370 170367238 254701088 989936148 559162501 186781204 34913666 342437774 468570992 207793983 90829851 789601306 849280740 22504458 802955784 290461280 519934289 900397697 88269076 795414490 296730195 403804242 379549866 806627623 855466900 792225422 384691248 580199421 780677458 205294795 12882743 558908876 987167972 587884515 239471351 459799662 348700925 861512220 49407539 624111230 779729610 590368971 37496396 302544537 505259470 182299198 482959085 634126346 415365716 111608400 285771019 749613327 294460263 100828586 173646946 224549502 956473403 464465571 804564756 224953122 450138079 498449101 905488461 756773557 5043756 70965242 364442889 640832537 781132814 486658158 831001683 864183067 910685284 922665896 21906164 516079656 170668372 865055564 815893016 57722709 431687556 263669731 202640580 909347567 470838653 686389740 277266141 39415728 312764769 921493204 865903518 913969638 776528065 396865304 396231173 827305398 282954789 992185829 750154105 688478858 918968609 34934508 259017089 147917769 985105427 511019596 802469355 993253662 900717131 537813421 768152480 505380410 768877353 658905743 764584252 178271118 742109219 924787768 995448390 225761245 395795312 360846850 988603470 746145672 878150460 970620708 686422736 149598495 444066016 347942763 694091912 147995344 709986480 962732592 842741449 220761166 401828154 852174898 31034736 989329980 247423838 818667104 69294842 486285856 308130322 314673102 850113443 770251012 218859125 978765029 45192943 979474666 691624179 606407825 3791535 860879025 671693890 760390597 462583905 201018641 177090963 184554629 262825355 600137225 154246411 843331603 305945968 194148318 837342006 818239956 957392545 802845497 272348720 808797088 693640857 407539935 518647725 746690299 695947300 52027521 434026600 83393449 531153130 957954529 288631688 339726697 548541918 29516068 851827313 734200495 643286908 621726471 729408051 365225766 105563427 684349693 418227616 638424056 351301930 698010775 330778623 415191368 379409968 897680733 184703975 38598933 707296983 234801272 548999333 443558210 160816498 639138641 70205133 128964939 933400600 713974732 927812111 319452556 988910397 615487591 576461254 64728828 593805806 751828941 591593621 924968709 495374437 854988485 976094431 863646808 428034446 986607192 605752124 304607734 157483713 782446333 344089994 787341384 437058936 505611515 608708715 454719006 508013273 207537289 806015125 732681993 505703198 373243440 846031610 576327006 548430631 615979871 209549739 17722672 309827172 179504671 815955199 585905140 990522360 937148503 165793589 693205311 155042599 634310349 740601844 558247186 433747609 260256448 567839510 208389676 240774603 578180499 902776424 519174598 667716353 210045089 276802216 253402993 170111120 198312781 485906211 930797064 993994972 887016 99748155 14589350 153171159 529865682 211176535 804837092 705203825 443498830 453120907 287932077 369851930 447400511 52211403 995809198 796718860 18178794 7277381 103366650 540015646 484292225 586829558 955522675 956097193 949781355 48287576 332258901 559026854 452139310 186527205 482002580 110472291 461987379 858751316 677278415 698936423 354612011 62542886 988895298 93714054 909357219 776012070 104016247 907214901 640906145 943882490 159253135 694815942 426753160 160846233 881155520 241606902 244484993 260414287 874786122 730747686 588970411 325277334 729093923 789369627 568192650 652066057 37612081 533232216 668006198 643613500 686148204 478900732 206878090 30049223 460390711 336783066 188393692 806448253 599167796 24313832 829001197 663395477 19094845 468824386 741665075 427688413 380685153 484487602 906932699 469167350 600401364 809546899 79816860 69508319 847611729 375230284 576869399 162962959 796020886 727992393 967338883 860417022 400769646 402424099 41987798 55264980 57300864 49542709 827756638 798915737 752180832 294399329 832226452 53869678 62563190 384366298 414206825 520983525 449311617 830558752 270513177 224516331 495329277 187811570 486067896 86165345 435877353 633456444 652719725 436356076 771791941 508360573 114943161 982474348 734651987 663303770 855755168 672485750 621799529 732500191 988429941 969889369 675981164 913410297 614535406 172941126 374519935 362088967 528266533 118283028 352587022 38919371 43944970 982662094 956469283 665676039 481590291 678705999 966306979 667086811 783165708 170069731 387523644 923230712 641815944 701265732 171916105 139226928 627306634 68508962 984969311 969105654 338481359 331321724 992197712 460274070 725026022 723211252 310153339 741356498 23071794 296071257 784749270 255444722 100367747 581921392 308141658 986096504 4082806 581011696 607445151 40464435 251725651 669965605 861809041 973501992 508996969 184098002 413273972 790759599 1454132 430719298 177657028 335507431 942591067 465171898 753104034 73759268 814113235 259818554 165940024 241583122 619104126 439381940 289706736 446801877 137069878 715617831 749478939 665553046 572548004 608543739 410672229 854581045 681719625 523786790 383662672 41424291 673552400 950853593 333607001 763405488 361993570 65963241 153429757 778648230 796539077 694068356 707616728 533594533 747566857 800974376 936267043 78693438 916188961 645497377 287807920 467403327 146872184 671483511 168287689 902169064 253227029 25692750 296014941 824461998 215723207 278306266 949271568 996059261 246338111 702030089 360670858 17466040 678425855 403181131 411709357 480657898 241676399 279630891 309455645 490677100 741804554 246581689 581391251 580025734 386820169 855434522 201428047 540014261 761485416 302195837 199081353 677825230 773569380 366818065 989544384 697705268 862072983 371918964 990554708 620763348 43055575 96073382 384626187 900360772 906825576 76987875 842293734 742883210 547791066 272171885 749053847 580789811 223261325 68917009 85302854 761191881 172861654 632654504 203242641 976884541 445740523 281278598 121672438 462692059 398632731 195084891 268260058 362529192 886615884 245070688 36917165 99075127 422459388 480995261 380311744 659226225 460825360 285552283 713647132 409298616 108045293 323621750 40785928 621336943 411665376 280305736 649965291 40703362 454551806 486079583 271787883 588780881 105970474 3747343 47046957 805705083 389383976 67883249 173426287 632173179 605168609 412617588 762445119 998583258 934546315 9109170 87099909 503383211 562083302 233964475 776286035 523510108 330407899 341488747 865587339 732488937 147299913 624081751 717767320 368951826 126248844 262407040 943489035 265460141 470189133 450478398 135557652 312034200 593237481 54834356 294452048 728143493 575893159 466786238 806814474 645247084 271298045 921764568 488470119 401660008 704069952 286212844 931527270 323813280 864209668 516597779 571224735 902700362 453697934 534125564 579472794 496617402