999 1000 974031829402851670
894969298 893134388 116689148 345975631 479285588 230718239 255961678 10769075 314207855 619962665 778032648 931457852 205452832 68063732 792894320 811372668 894495623 199469840 421810190 369577237 125851686 920413250 585921005 288307452 804751392 888586176 908752346 370278842 991302267 870613106 70377892 503730342 397151070 121813554 738177626 17677611 51769939 715302924 589325968 675382536 906977413 259758718 933805209 412165771 723244803 648193465 506763981 974076116 788862715 303399901 714631109 359607320 316899839 713815872 639614106 516506587 131040835 503712424 115704105 203602228 862786780 97106828 184517201 655436556 396059650 58233942 340007474 298792543 901354318 800186019 119647343 918044792 97187836 870957440 497487469 287403321 586517290 7978927 362337681 170008400 158724631 236565984 859436421 808590979 757608036 125881080 53009524 508181989 224704085 111049292 617582409 793068061 635542289 968659430 87617011 721956262 914047709 31359679 827550116 68160265 987111269 220040451 539898636 664433444 827837939 49606735 280852642 922375526 881342389 302091254 788563163 13077520 550183930 702338871 276213360 781208693 381731957 473536904 416030876 526194490 92849016 118649550 351119195 426555030 708909626 44902818 188828076 544327826 556098833 514772877 226016208 933498698 417056184 102170443 155443592 947411242 844983690 834298124 672653402 162060594 4222404 817934510 174690763 769072946 372362182 257324548 598216614 715291149 522398034 28499729 443279923 176297466 861691595 746931277 421082752 946309310 539143031 309347038 191725724 945110002 993558461 629342432 654833622 771829059 335497064 845275549 787883266 90714284 504079329 778144213 173956787 747961533 841036408 367366135 798615937 535297239 739534491 565932645 757850181 986650990 544574492 398159796 267784792 982986309 970539375 906028777 813259735 451797172 817156073 280614844 518748641 288124389 324206082 212203736 489635030 204854034 263722387 351517720 972706457 960632777 1789976 310928588 702872783 549440551 8222447 983384561 249230110 297157920 527368087 580860028 312879470 817911477 340945905 59565455 683257899 142547515 579879042 97587394 541461632 557571226 574308014 687593563 857104028 819641995 683954942 714496917 681244145 523155161 914362203 305626845 520787311 121146528 234233168 461956111 993016781 6763921 631382603 601611965 176467392 518550571 142821339 757056104 946211394 314341891 409780723 593511108 402513099 215579645 301134629 793244152 858004891 433952911 390961896 619013339 420726766 393752068 607610322 554702648 481304645 75025591 289009118 778689546 417235619 312856403 61863079 278622144 69755597 151755034 622549418 27915386 505233545 605570586 919718536 279587913 194707423 22186872 61930817 925127538 450152795 800275369 780791417 618519211 755735624 720290484 637018038 277612892 84545781 710433905 8525215 508472287 614468852 696316108 14797374 519991233 638011733 25649666 551484223 43614206 965411567 554228449 616885806 143479623 693360791 624865036 265642684 361891391 933080423 132872501 407634683 655812537 834883320 571810145 254117789 294937852 4732839 11037991 859521080 651935743 196527827 323022320 793722756 341935020 233536796 881808184 106453402 250841632 209131174 870885067 943222838 90810089 355862867 756541192 819483894 576774982 990658828 466284833 669219225 276511850 793497593 231816025 730515521 316557753 429775043 892426564 895260080 797628681 56934104 342445577 212786574 584978146 897018023 467787427 561321121 522788542 779422175 835806747 467613970 153541449 196169140 160016335 8324782 774893729 703068442 218453422 190403874 711505558 621621511 502557817 237559358 972356331 836810933 282912771 897320499 479406995 956047325 38156658 10539988 795428596 977464572 870491003 967198424 138281511 245265809 434084009 788335126 46211893 423864412 619479445 64515526 811561819 286570401 795982639 291579334 634121030 844286818 246031091 762476499 412736855 273988008 873131317 492862411 491465696 646380731 797135189 615247345 558608229 28954980 213766667 338908456 750689500 696130354 79858076 553303862 705702380 994087089 786607137 586779907 130960177 225047988 672453063 605608151 321517174 934101899 638891273 106433182 916045561 75922253 799634168 514119207 791777194 365735439 170138483 352996192 635907947 346173739 549233006 509125787 987529041 261876346 688415023 419019980 913099489 903416473 654608011 124770761 150254163 993967911 71246125 461758088 921827538 555318533 157277392 485734755 317630650 525004948 301824895 536606807 154048472 930830330 412208091 448590655 32407469 720973661 663562068 636964893 489171371 471854885 512303214 34135890 462945653 990939198 845928190 561647585 484946723 201124947 789385322 875675567 449132923 67828756 339771884 642502085 829836345 767722864 459247311 430413964 912189511 284787163 475921072 802930191 401929733 638404745 834792382 783548476 392051074 654123184 76005625 949906211 123660992 771425738 750526582 987088693 699909619 781709776 879581081 574922117 611995074 771875199 881793368 627494410 730456964 941865110 41518207 903658971 507893124 223383574 116968422 227078513 449077053 278748288 211493052 73106663 596744094 684423194 27800767 474328125 190483271 409521450 278860929 399240592 894841034 167380536 147575204 128010083 568403178 255293008 13890334 413227226 109242590 924811581 102483318 643001849 426200718 704154063 825780996 88938472 625076949 627740693 293626420 296369457 947617213 428665251 483916739 304071168 124443845 652646861 106702080 261221986 911103262 564601833 301108236 538347142 9599465 321056145 565763610 904362238 19723386 355101406 145234863 718736638 181750936 238366893 681162978 315623580 552001210 679075550 902243740 433527566 371291722 268607631 58939353 592632558 90135526 705923685 648528357 698108025 98428825 902709954 164042400 721754571 126445862 775078415 90940858 902157604 807519805 512761588 303522806 942399269 667161795 632661658 4970347 513305875 275225870 768893168 392399805 876454675 757730342 449560290 197022824 747649132 737203205 855802019 34203893 999176135 754608599 528962532 798089539 16212850 730324026 475804186 173016511 397728664 512908159 324035259 12138411 281130634 570053095 203182465 914462042 922705145 153266150 676109989 964788850 80098872 351450210 820950308 114822696 480941182 380050676 727678205 619769223 222030626 42925093 97031537 240148393 308534493 738069938 884170049 20560379 593332747 978745033 770994931 816954493 189161 717582409 822742285 851017727 168040920 448143621 764453464 182541925 786305944 665062913 395312670 189356260 213714829 385218227 776683627 343218242 820315133 21984067 899104335 635871513 978665552 664239818 614279193 323562003 102286158 822774678 770709917 402918447 857890660 158623588 205579375 362081018 420685022 132175268 949337637 366965975 614423598 214981561 418556569 559623479 8289827 403680566 673093156 636537057 704620082 970066977 715683300 949376043 262436017 980201778 406134262 416886078 372892950 409968149 184871867 943181909 932960827 724596643 280814103 629021182 492935837 565051949 318857645 372589911 227367576 857683377 385932068 625171025 85855404 280174114 70755172 201579504 168862651 112308643 629950425 383808649 606530376 478133964 554325167 255566850 8038328 394125539 344050451 642250262 174696596 217377828 163514232 336411790 873559237 487231993 359091151 83527047 952722646 489728322 41940429 575938994 476868406 532472462 348869416 961052815 982828658 438665311 297633242 234326193 661067134 819013994 131635292 49162748 959390701 565033172 567034348 828459498 689019956 965239413 820103879 157620673 399027691 562624792 161975406 215376605 62144011 231212217 1749989 625794284 251386160 434049733 298130927 760739373 840935383 116397661 987796819 510118320 9212577 713389714 792238361 286545304 289019022 287192234 133635789 848845659 520982851 994895449 112615099 724116480 350912836 715640329 981720112 360428639 972417593 422576402 470436799 125219172 830682925 187683329 222070649 185893964 264320713 65991381 925864755 258278119 232483229 754213693 488604356 917275604 222123608 370606811 337124931 636784839 542899210 347498371 659757132 427638981 739750504 379273596 585094716 868899941 787016200 482358717 321321072 740174865 53132960 739412529 62958218 513931843 257991499 655840755 835729835 111187912 840375491 114198418 747836089 662111743 984129959 616114510 581501082 978841371 854821046 201172824 594105463 272918108 279216402 761443349 361807354 355218010 268947070 629707867 55767439 752123194 347090336 933285810 417915558 437761781 509701695 825585812 782537199 773911448 903506821 563445422 20039068 332627326 374166589 849342748 198284194 253169559 959560981 612973744 671135223 855244197 301120221 880483370 548297429 538114681 262213830 36378752 580203765 939177017 848396452 598788376 670322133 451051165 772619564 624248329 229050354 790993197 117618230 302573149 460987150 829490052 142017275 166881874 95437418 399107984 946825303 327341971 279966988 157965263 283656456 532537731 241555450 769451410 755473388 497331058 93971581 852469565 840299079 935447269 987944543 206701189 745652218 190371794 551894572 555321520 22761420 749408481 340308852 365797592 592472997 729939884 19710727 337956904 564878541 571824383 878567223 794198044 565752369 827853592 800897049 862505157 475629726 843470823 146551236 575577858 935487235 709945167 270176911 694544584 324971187 67576162 660939095 904925531 185583520 516083369 609833910 227276178 979515553 372115545 373933644 795121686 287787436 1672351 655035130 949050274 191293468 941203157 165853986 550703940 373082859 520295881 922823144 667040410 261181176 70096380 456378995 656696854 700229443 465195488 225842220 538197818 737979691 447068697 150187772 306570460 227892918 216214973 208725906 559109475 145704137 60893843 704809883 415084295 673539947 725396823 127072263 705363476 852272646 753974772 246049099