1000 643189585 831941236 1000
621444125 324708497 619770455 112615814 800909697 461794889 380815971 872773343 314541774 472606930 636420887 783552328 794270098 539204140 23007446 139105268 406306323 866123427 218553206 804461683 30473072 117201808 568299563 477252115 324883663 342559946 1371621 504272660 266392137 823001194 238905634 566320974 509103320 924666398 602756477 847754443 728675882 830068563 908575832 751544833 788955207 332394050 941849309 559391132 3365764 733837532 608832409 960478738 131583470 688974106 355991724 263481532 222845016 144720350 289709029 794231057 956775473 167842781 213866739 644407521 797190432 229133797 613563914 565994354 388310098 125022256 190433671 868082870 938648598 452132530 120563607 161730307 560731277 215220994 856801416 309820560 580058171 535681247 943278508 957610205 238531396 718962253 781854728 179994309 433651370 892827898 216515080 57918121 619784362 346359167 504102978 635780637 760297217 787634872 690101999 230653521 385761418 239038839 657622166 631163079 462411203 1778731 904111085 874478053 938732521 788884568 218906201 517041299 120543110 890987455 422702460 484357750 563957103 507962489 4330781 846742495 900743426 108799658 13543392 844830259 974047679 551508275 660165876 433624109 434660675 676347857 747505834 551233894 343620106 639611565 722194703 348808880 874240076 269861364 74499090 123256235 319580920 339929696 891908055 862832728 746341531 310146196 684321709 546308461 239979681 364226307 149422782 940322134 661956268 459971395 871865195 83675463 805476486 980139740 935312673 219807474 632351081 28057767 194237855 380502351 970471121 569840085 598993201 949150701 867310194 837184948 254582698 983997268 270534535 651065852 513600382 271117964 793072240 807899381 899546712 396730510 986716265 871552124 190600284 447122090 735702583 816231685 280401162 49474795 446724982 503959368 369611014 455880157 829896429 163011744 623006466 813161516 219686710 750162583 106057750 101194046 248325575 13781964 778993702 413103981 223994722 140476269 900141836 735303167 545689510 574696863 622482461 596152473 449667035 558920258 679321034 251825969 822542972 53769648 689608775 285455372 169986612 811754180 188910675 440366283 871125679 539531933 163515280 495993026 697028958 442411124 572650016 580871688 249809357 215341617 736620127 131257937 586450093 590523547 333596625 752424284 537502635 416833742 633062086 166767147 389288697 466208296 468761599 432443776 997898590 908077690 969206827 795695700 876976837 95705081 50053167 503738371 950281729 549153370 809733414 585626462 706401036 118878015 823023201 608785686 175205277 475018905 372287015 334272377 298628090 373033994 3838144 83193604 223065037 621387827 452241431 877112487 228082580 125628971 469707402 222435848 784026539 174391384 754562959 586607542 15543420 319005232 328026295 547426619 779250188 428896889 441169074 541343853 551683662 386669714 472384182 113920721 183903353 634694241 754842241 373908237 738604943 204072324 312173612 399355666 10548166 115641891 120569905 267580793 399647939 627821587 136521577 867443259 926133160 558555067 983998435 290139901 519703996 849085229 546626294 213098198 612449220 544928872 675547475 180387442 598586760 560539351 62886242 367123373 522020583 55507065 899355463 403634038 308343446 450273517 14644997 251603804 309841288 928433667 568478973 271370514 742721200 666518615 903676359 10489112 196854733 338947730 494141249 712717397 82256787 584100667 832176638 905520585 941616032 933671887 560412986 551226791 224231582 900148415 845876420 303256203 848317893 534903621 758620208 519432020 572943488 144538071 447362943 488743257 182979027 131932688 115830091 62430238 219256909 266368293 422255086 481527293 237106538 393685560 276107319 897307896 349905417 521903010 226941301 271505641 866317042 251406637 217280989 45657206 709007666 978835485 489535358 610918652 590476260 612577436 552371537 136624781 592684027 137553582 96923485 126674548 862850865 882735015 236638612 45446043 381216595 89868147 732951191 744476348 100519993 443650792 375647163 973696587 19422552 17325523 206039295 85067084 572122112 298323748 626667117 60705514 222849876 226393967 736131111 502309016 549432361 130026033 282942615 887744250 674980620 316931869 914486126 227866506 789032144 551732386 131832159 573722835 358129621 761636236 743948911 899571149 807443169 748192796 285844170 262055254 947444207 103561350 20130363 102344941 640638688 805181788 322117748 26733355 483432068 38405258 158343685 550091968 478622647 810845097 326159763 315144580 940290961 138031657 615728842 904702827 82467612 906210972 733790283 888451886 757067217 188124450 711719572 386949620 881797030 578052069 105121461 471112176 210143946 352451333 889672111 864294146 612331917 720900998 80345415 671926168 520364633 141242826 898763453 117398379 650842890 508504638 526294436 191693106 560570445 496718129 182623757 603360739 266167642 271130796 577898413 743842136 178745548 920553309 193546358 569663927 859539569 159059620 771651455 492268355 373500820 333598365 781676868 411918356 698289994 161806706 771019043 600738106 210989574 606285827 36006180 639237436 876651137 355858641 174230795 203027283 794728819 732726819 194690018 463804724 874116288 336831692 363362355 661358643 79372835 431909864 614374194 685720588 434947697 131617494 187073651 230801552 726226385 463553373 944627325 4857407 34069266 297770139 985845469 194735861 160546202 798079798 144314227 980184129 607608369 789124701 653793450 706451081 959984330 412011205 111319490 488420296 123682617 7464995 910136245 133868940 446171154 859440180 636112344 966587648 798569011 850324353 971488716 492690074 300265012 358198248 841299998 696742941 921857758 642575827 76680432 277849230 108835015 607780087 453972060 972764855 465930180 89433281 940351093 74936761 769490584 681739860 102845258 869665597 696004103 397550718 813308415 541134556 255254453 463023495 628893963 980084237 2465348 632931349 116954035 698937643 309425214 377928890 667985034 853710148 968228635 461350109 421582872 994795057 286606087 182692391 683150553 190042392 734307658 994038923 463163831 840037468 952246104 278407467 901181282 390500019 423802504 719177855 110518652 987379735 211340759 66192778 105499103 375681925 484208101 196290007 511274260 904424576 774603769 719685872 58817379 701228039 149413543 785050664 206999486 116869868 358093101 147836192 44316171 718819118 523668430 907334410 288068329 62540148 992772456 652481028 123410997 773173803 308575830 60984111 610270764 438849282 207313759 30138658 808042944 91184583 309712749 915570745 203447039 540435255 313262605 448450017 505593379 988879900 728551973 895013647 445168120 107583498 912173818 19619999 114600185 866228162 905092527 189704571 425259228 506284586 794844294 526039901 254174098 559099606 472388996 194829619 662603488 600379700 629719277 892484526 887904413 145623094 429741908 684751298 250209616 500043689 57036891 841337281 249624902 336431902 86551169 819085170 994291726 417056558 82954901 506142607 556078485 162274054 35802291 433692080 503299045 8972185 471666408 935186582 248079684 135756740 937730281 50364240 363241568 778783585 102893033 598878199 90045507 492615240 834896301 443998215 846084810 584441462 117467262 734817647 975497862 228672015 368586605 418498866 701513743 656273377 510653053 127483342 497599514 853727186 180844478 763789644 429055168 953880580 905491608 454599593 782302155 183698730 416829354 559304567 695943053 445216788 925546574 363488980 642061371 20153028 483284000 771043449 879409798 184291315 712720634 31921075 700346001 357386406 81581789 449597773 468575648 528390790 819135588 767916825 1376111 579736090 491166594 109814693 967100881 834533050 781289599 345547618 823042641 935505363 237122833 667564029 220330054 825426956 206506678 424180400 628033390 475069128 142643153 811730822 870066189 986302906 366686755 699983025 699291312 884830979 30025384 496169657 444432301 625567044 899123022 791965445 459598412 245587362 123240406 53542917 100166329 942062481 920947466 375683712 514242210 320902925 10289437 62150882 892829735 247381135 206412159 983083214 347404334 890355571 540046307 218664510 749907956 121500652 878260093 188552203 384763075 639757214 20899431 143177339 126118512 107488401 523825286 322387732 269378746 553064549 89392612 256835614 194042431 317228250 527060879 657606461 367209144 889840360 470821215 688671536 639406852 502800379 217827311 637748068 540913505 835017590 335018791 829090774 581003461 317042924 633512267 216766449 808841636 629907548 835538156 494228562 32703341 962988781 441953458 839583859 844632406 869949375 96743428 321690423 360874845 729709190 872115306 79360938 231948582 677006772 10721777 886038321 994461152 43365466 846439132 97080375 616049535 925880961 614813768 557439638 490602635 295032191 66310020 606587721 814962941 431457224 523038075 282817763 936840333 125385330 669792006 84975671 109485645 805500262 306009552 952964529 541807980 836064983 758675363 372680281 501443098 121001774 9810312 599423191 659799866 724553384 262712977 190643013 91534973 830016765 38015249 45921767 860517099 482270574 918270246 476812163 446803163 744205612 918969159 412274492 241408401 754403230 511651528 802725314 912098750 905435770 589880554 264231509 681525449 794198471 409110975 759269357 692269431 979686001 825505661 455551386 672959753 711958552 108510783 527121981 969099195 60458096 359471247 761766124 779501284 354100067 682657038 485470375 863937746 575528758 645498021 871604529 25262965 466649279 364161712 137508037 405182090 224750396 85705238 560158155 9819443 752896312 954676063 316530683 614212368 113394653 152179953 35463300 104987864 373222640 391037425 866050558 67577343 827304764 628312853 877036475 24290720 232246513 315623971 407489313 347550114 119262964 850410103 265205319 203495487 280958968 834585649 591579169 895557999 288492022 741097458 219832409 875771245 234414983 253885666