4000
108021783 982250924 545834700 838176489 820215967 513693304 390105282 848238707 105079792 333761754 705784636 274083688 586494541 304157807 99536031 698039882 173398362 231461702 755538664 44788134 575610972 671290651 414567314 182009678 559161623 319156721 818988289 308917285 874079194 86465570 286069351 276074492 10617612 284435115 536908706 412062351 161715861 30596762 624003379 214346041 74479468 426834711 543428842 683221357 331366167 143867639 76986001 189411725 743920121 25641712 800183368 22838104 760650765 297166648 153431728 897573325 597653143 141896496 368484672 8307767 393525893 838845174 669916527 474321214 704215894 513113144 67169877 981947880 514529314 928637366 624697619 216253363 767990435 607958469 396370549 984386555 423022400 543620829 760701491 382775314 742342912 546468428 368805021 772094751 537530834 667853441 182453058 994420577 586909937 853515080 267738304 469734818 606740891 441981987 162292274 145470514 637236832 514775979 244381204 926127550 102682689 343639634 646168013 819590027 763899227 756141986 481359756 808685682 586985775 956477314 866233304 735611969 179696487 294388145 286244432 756064023 746001199 549731685 231603441 702219018 699156334 582465723 363373595 707863553 487624097 348411642 97949909 958965557 838844751 430170121 140180818 15172482 116996339 751742196 427689104 30630827 622344579 457025422 521057784 560143244 290489416 313666541 791924474 532021432 307852425 561716674 325325695 692518237 632938622 51208560 568913605 79049656 642366300 603980308 169437483 640413604 942416397 954617778 793484392 610850041 567125039 771438801 96883919 311567071 512624851 961487866 798609508 573731952 483816600 517964949 990273127 804003461 853300223 345138543 641842792 74776061 827063120 703095990 6938895 828418702 558725375 144553471 314105557 564383251 353309711 944206261 471642597 225974754 403147893 458900563 310147520 361297289 988483186 178684813 958214546 896337826 872722093 245834924 516701877 852610876 188879056 923830410 401570718 823113248 894412785 991669274 912862967 101766888 759735688 163670178 307095897 249087056 581676751 756294559 619422081 502174416 382308981 805818316 32371186 834008495 25849290 306395747 415562481 509522232 388192189 99758893 312170097 499598818 975013370 283427049 701270417 858901564 110357779 739725898 151750374 830396132 865385430 335788585 818940537 94839737 209063428 234622433 695138971 376970873 503918041 283035320 479371051 510647633 681502751 246816941 677497477 470974908 353889387 207094877 832500818 451406094 19229290 834121902 306404813 167257981 363226402 976689029 824878137 185054408 216431498 946043379 282090074 817391350 366457707 563396921 707630340 8246435 58668183 622606170 441955032 880806246 666765356 608556651 814884812 373909254 196601969 513018316 684916915 730919701 841396630 312740463 587381075 834042335 328411597 239406838 352962254 811100181 450424895 356648734 847615989 344593223 920969768 4526827 588668093 734902972 90361575 589393313 615625037 210457161 754500994 228852847 146693552 808467471 841642498 465541673 925876728 921276105 269483743 472450520 659475054 214816474 994591606 318206447 152086232 950760192 763512794 347603644 571830369 108746931 18666503 958934023 511008578 740019376 847523411 30542250 342179005 368407852 394345894 453412679 472637834 370860436 892386555 503745832 836577266 918225700 304656940 762159499 79564163 819666947 54389582 295466360 61105332 658712837 116277462 956234040 300838293 147745157 145381022 689992701 309852420 468585454 245471215 600112857 49256935 400710314 491136662 85687095 162303100 399263146 182779600 392229143 866618008 299399152 52062735 247291297 996998068 624675777 855504067 299000682 518277220 671694295 211406511 776231986 672662781 592080594 587824967 560167929 207931048 353985942 204451520 189529033 947870941 994038001 172154440 821366982 322906450 392083454 886693644 583158406 573590767 260529333 925543022 266985241 861866553 409570446 894899787 619267222 894904559 4915559 75189920 142669815 6247220 644783801 622646162 185513700 303397849 815680196 431519043 456270896 989709795 898140173 457115553 158220335 465898883 151540194 786497336 237058616 82626138 32817129 391613627 786712096 443430683 591439952 813659547 323700043 508102727 100869673 911795848 443809130 348890001 842585187 339710056 703584147 175973768 688359869 353158223 830005074 467863103 597642171 837046875 782093100 760461763 503774877 788878013 893262069 740307493 593005672 8825004 90471597 695568828 19641554 761420177 217449221 234090437 955275668 8442086 65792426 612021963 225722328 774166852 151432457 547716814 823432463 195784616 105861205 572824215 173790653 658004823 774335571 589422239 537060025 638286632 780791450 638877146 237734599 743176220 392120211 725938226 26397437 699165435 507748874 280340967 515719173 383899401 40654201 809290966 241297159 807995431 383251909 193224349 960377869 486517603 735205370 64814499 310094274 240390752 599141402 726535976 660163440 414119213 739881720 886353660 417756632 855000053 570390096 421092362 119577411 533937875 928050292 848672791 929432198 948705741 587624206 811395310 173408898 831515537 398263447 701576044 400660770 384820608 659422218 676968099 136384272 385839614 153183428 314724809 203025737 882332777 85898376 840902335 422726560 861286213 415594587 426035003 840523181 318277428 649624521 607161838 332452938 619446869 34032732 190255380 308314772 300371124 512771553 342315490 541659965 933682733 296739933 156079540 194248729 88418925 543982127 158099503 897709001 799843241 950867720 358691304 270023804 31420881 293378164 587264328 260966087 544223644 417115604 151146087 875583046 167176800 272050430 806734186 922313792 335405549 348497096 461094837 50370451 21487144 445680661 225637403 257724405 396280396 185132147 615967084 524944800 53099843 693557149 156360192 373394430 92525583 732510327 545236413 677972589 539182643 92289509 337194187 990421362 364109728 932646016 490675336 720313652 789468521 721781679 448132751 732452186 424190200 90820909 477098426 660124167 173664403 461264101 39123905 139891675 254133937 761869665 669828577 658725620 198103020 37900230 646466647 894587947 270822955 562799567 879442313 525470844 677784199 291268184 222612602 526931299 865924532 453026510 699904350 829778774 278826567 90406274 623993543 858094382 35337699 267399718 991505820 545880056 501515535 623049039 715039655 527670708 317103114 874165269 986805930 268578617 381100821 493607877 769759606 358193655 460348752 866061808 459903787 75587498 167122677 164952970 238361702 997312520 364885846 609695515 792029669 200840787 247333512 841807521 877438597 199447076 106742996 361847928 636035655 891181434 790669799 244833636 561111223 96960063 609190751 552028669 48233577 578373938 840770929 509131784 400645631 798491624 635530707 787784897 365029147 868049746 478943050 448838377 352856813 907106470 185312178 672989832 532913870 518450591 566984439 133995115 6907302 66550846 287360398 323476620 66254060 86626308 851607190 626419775 370696193 400935218 271613257 755671531 468508278 545558442 208678690 862754722 16914666 935989271 2250780 153011725 790872227 238410946 84083778 767229905 757437745 900074574 968831750 682633096 15418845 693164045 502751711 713710858 788740556 58445459 638027653 252813724 536225544 77651333 492997121 624574653 650270738 986846809 809280778 608964623 635887953 817591223 225106387 778474996 722988642 881777887 922752868 692468237 360812244 892689766 53378341 585057878 560479183 609747074 789996351 670918540 137817327 851630262 555446238 387900921 94288457 340136633 321420785 633618925 769213369 116880665 691455151 146948371 650902020 481690263 285579297 382213598 616415063 853740711 87765531 566652814 198080952 334049381 369448884 222366067 862037384 569730189 977124181 639467292 874591902 405793938 990357045 951729204 29721670 737946107 568035983 941303655 948193930 365259034 263225278 273714757 383256826 468999805 281917369 955988815 692862529 796458714 440032817 904274674 664849431 521659951 418643088 177337211 10153734 381823524 815165662 529802940 89234387 746323395 400770597 725464053 638729746 452625024 167199760 878289055 305378295 701701918 233134123 848567965 585837661 805481025 761153924 934743690 131137519 702639311 360516603 664477480 84612924 664342065 942522148 967206666 8905690 627005094 704109642 533851147 373358984 76018220 360839549 516695610 7804131 825601136 794171219 771052298 447603879 188906718 323751721 278970013 488358169 875142154 574034327 412255711 36133436 688647516 907352300 223949121 855899212 518010342 409525639 279293708 176363860 747788811 564809123 217513462 419760307 491182138 36491707 404053217 825805030 637541469 672986365 938770035 99900344 862137071 876793619 77024557 223172821 130112378 8871536 779201637 269546012 794414292 326046810 555967024 767087576 184729663 222017033 330609014 436848300 74095584 834460169 486364279 501957980 861595000 453819302 444566910 5040113 893452156 807036618 935514371 267574573 613236697 929188479 983202479 899523071 552298969 147385231 459094344 666135782 372019311 592992548 521665880 190150710 808080605 237716216 724818164 793972175 272215504 180851241 418207382 573939801 385051906 402167669 765905530 196834598 438153410 724987488 341742823 949078652 181458121 130763756 681069236 125623674 201092293 558330438 378361508 915990400 635646657 951989821 387347494 440629687 256642175 186501479 188757822 905772822 967484675 535134193 447320203 371054811 330487962 467463203 541651885 820556010 282964569 256444638 956186948 272416807 219431933 769840976 750682566 576365812 347174382 369130848 930554275 769949615 510767893 547666676 839729924 978290552 603115595 565396548 137797071 517107874 370687822 592381527 15412866 19628247 273268392 653428882 463428419 639625552 326358188 296677808 262521505 456452323 526903520 429515316 488795999 179907850 4181428 272679964 856031926 717397689 369031658 231866330 268114694 199301886 917300241 880181109 113119113 550037043 860829540 41228211 961908234 442462813 58002950 464520526 659391964 19369880 180312730 320293580 50726152 181014134 206799303 508379561 868243079 521502558 98236583 232571838 473591672 657351157 59373644 397878325 27341671 482052364 310875730 943207241 229401968 520459976 523277032 564100580 282907696 788576381 618067938 583948448 767678446 11888740 349948148 427841294 427472928 840745894 701973175 466576780 383565314 175759356 397770846 598913106 620043070 719907170 63463207 986636297 397543672 341378057 617101654 572906189 888770200 356058837 135205603 666803645 50436542 172551930 166288855 185697472 753266353 250736662 952941023 86389521 319751238 190480268 791578541 833203017 184948183 679596583 53369384 185979951 903072167 75255131 172823956 977587112 910795859 528070776 620550699 451542209 673345019 702711347 70126545 989456090 216101870 425014940 557433594 115355845 905032741 924705733 62039644 780682774 487942325 989923536 915527296 125451223 941010817 156281095 192271553 221115052 425613107 55223988 296750191 204378059 826288742 534218398 351947825 882098250 942643467 707022430 557025238 9715780 536111222 91659807 252369377 569180734 40426941 185327037 704360593 500142966 518139467 146038979 782544770 929819505 138741475 929044832 407684540 167055499 795451035 693387307 452690443 517798464 933034164 285981396 349065286 401215214 299611842 171006380 684945644 205542019 758050230 677915008 854204610 188808878 337319368 308462404 616918995 103571189 263042232 442810671 80631663 101448648 484677690 641625188 258549419 401252143 895491482 598645996 346096657 455485910 112996504 230492502 917214099 887952792 58699400 257307437 921646928 187104036 623996354 501486963 566082840 483401878 978764694 125395610 816676148 860828519 895224490 608591006 303762119 997786468 303430599 252448934 744243258 805212011 769261412 827272360 879796133 68486627 57692516 17286486 866314173 383073164 117132686 394462061 178611445 666043872 431380753 491783763 57532021 950118135 438872938 629562933 917901232 778266395 920223973 10794415 822298682 129919812 504132778 124383755 285066197 204007228 350252084 914854336 32036089 420813654 565451357 688244376 22984211 342857586 272537552 830210165 317154827 344979082 610004262 412265268 258898613 848272000 620002819 744704391 298334577 153160191 759104753 597861594 931151266 160909827 143206078 810284919 182467678 709983902 988995146 746832344 230283441 222493636 415983822 978768477 393369939 147126021 747554191 492444493 221949474 774837994 926635276 251923845 361478665 931455045 73622289 90074803 241069155 536902958 301314898 894463248 16915138 778634296 905751162 490842549 325511373 658641511 591701640 239644239 380795687 210844186 141268491 328324756 688346834 33732765 634403957 732124084 970780476 40195120 359442917 49485788 585990309 996599027 257230009 247826266 685582473 560670361 908945235 251529695 41305273 300326871 868033480 657509068 565056580 99609442 865817514 774056166 245335481 634101244 47009484 154290611 179077419 301273181 196284412 340399705 755017201 98412940 74930246 361690086 897457639 720913867 915875558 89403806 278056607 525357878 6580351 160032477 954560214 471909269 957373215 37814687 394809782 487980769 89200481 449935962 64523788 380254268 991092963 225672273 878371920 585370134 42499924 451492529 614225667 667195302 914760656 227397432 181101198 167521970 773125579 507426954 88974843 866650903 869038336 673338975 296822631 983761412 77761805 849538320 167812495 587043543 873445430 329320864 887996212 612352411 219090377 634139988 964951200 42577978 125753764 475844584 118525278 566956623 74352635 552274185 561697534 455962819 749702412 622108304 117383856 185916085 386963951 805578550 363514827 285314753 219603790 983986851 88663057 908761239 251316192 671880685 385367369 473760555 664257834 848267624 383175301 943200639 170484959 795149559 665757861 737940664 468479579 221786366 781852880 612643882 78774711 450948447 827418483 961766163 545193392 762212537 770793298 423618369 221940254 924326838 39901985 597397187 334725490 64195120 780622231 124826922 293071142 955382877 17456109 46238986 483182533 976254428 384856070 731070479 117811110 551936471 479510258 105576862 833060398 61448261 839686666 126155651 789189178 53190900 789111264 740707988 113952905 109051637 192947421 676289151 433035417 525592518 510917946 22857841 276597297 723340787 931471060 533291704 971780782 873189257 562142813 26996844 146420601 32375481 231053920 293161222 981079346 523775143 733366164 119448347 186069612 51918995 106405664 911421355 373872760 242250161 428341819 155221176 602173845 869516690 192410547 18119461 264599116 727615668 530038242 812671623 385584442 317204667 80155245 64191383 641614343 222609063 205285271 672485431 113809064 823685275 940891030 620905922 629806311 393414536 368455935 542447480 586832374 921090348 312867125 8076674 686330230 774775215 523917049 499949258 791274607 963318518 464593227 417683174 114619343 680174181 540730225 205787837 554293151 237966589 941563685 665044519 810480313 763397279 583887544 492934967 656125537 642953725 75756150 433100218 327775124 391636373 428097451 752267468 757851963 496825800 380170053 745891669 633489633 690833844 255302792 968768301 600621260 512187319 445954235 977906721 944874304 927367921 739863779 349749804 411548969 107629891 422651476 141028416 953526151 255166952 501771500 888129221 165176595 102421961 4191123 552156402 498095409 115637904 400618928 747199015 741722294 129567908 142790294 151552544 567363406 557591500 418696570 50821838 288871881 980775095 81811498 693888250 49570205 734522724 966994601 165711336 901262537 492092474 656567848 33617798 866706036 74488795 501488243 693936540 695520719 340747964 643947485 956213489 33490568 797134642 597718576 601057701 144068717 362413373 44845848 176727067 906724153 828232076 503178696 318090139 551899977 450279871 330165521 370178384 467662277 822438549 316151720 387948304 98942914 224391503 329452309 471551401 906289684 723460289 553499611 792195579 868930017 155232601 209897990 551900389 789456275 850777204 696996879 503625066 492643042 249433820 451480548 852278907 167852931 153572767 884420237 67456326 860924340 603715470 432069470 506739895 962906952 104834294 912723277 664325014 136225740 221311242 427654978 44720454 678533339 27779289 80214744 424641926 643430854 215138881 16246114 268062544 998056576 996626992 716075123 787036920 823400640 813067619 670994668 371647847 14698768 580249985 480079944 949602287 75330964 833590501 565707776 468605458 533044355 565823549 652588155 490072201 159548587 805466641 227063370 548078246 831818654 842362441 152130284 450386824 479246995 601521351 295948167 750199522 112378834 575948568 594077526 129531944 406869890 382067560 567353258 99037576 99770409 320941130 835461329 719785243 63513754 966427740 313318459 512753057 165364318 78873188 60416813 899805180 76308258 529278359 302511848 633056887 531540160 645262063 597602529 455213007 631648112 937967549 656869472 214415800 574312729 372703617 825825602 842279409 352093005 444160584 145447004 746407081 194004422 371685664 220291966 54458157 517763208 161698427 64949435 357626127 624037540 56476525 302736171 986382677 379173337 414195907 350413263 473557534 901282616 836311555 601937550 518381262 487401588 113351473 580767358 976029760 190831052 565787164 404587169 788047169 118132312 395336452 226434118 402880511 492777487 496345145 853561752 439592908 688204005 596463288 817076150 394565893 827732584 105142431 203823873 51124119 688068252 565840534 452508798 697189823 448282739 906523548 529039565 324223878 820718089 54002982 446821304 995061679 693736805 741188809 106918283 232628752 429681237 874842760 972107870 895786349 554808849 513535291 986113095 936256349 645729840 316329292 939740423 817543815 472993736 883112878 964867137 207924208 828490360 844329814 512210096 962214763 631112659 91635819 407222694 339355429 831704708 35061164 435501667 661208689 819818100 784125208 705633653 839305132 873282199 821697202 259109511 454142072 90045810 491852809 221976824 953173520 228088250 101630155 339147964 166895771 866635333 752900588 313213265 609749271 99168996 256225316 929878964 978504013 480660702 295479681 627994211 881364711 492732191 974266015 422860098 193243257 958024715 458350616 164578780 540211358 152771290 243011371 776453024 642034931 733006969 484766237 174377241 810083554 864245481 531335312 29779222 153661778 351380626 656299447 204278093 982993814 261288670 762096412 464654848 212201853 565897973 784687150 927945027 868623454 948265464 438309213 677163136 879104470 144904775 457606984 776353420 315765733 350258799 82359263 415227222 386922747 861337233 815875021 433717788 387704014 558876048 263231693 495461533 229713632 849372048 323264854 923791933 303957033 169584259 516139959 681994485 299915276 869367668 697990610 804671262 257727076 739346636 718706689 601587597 901869923 214869035 228685629 346186489 920497088 33383804 79576996 881654433 656290523 626031011 687853666 521875118 552857656 905544832 190373839 258777249 929864369 932025819 3103756 186068842 882572346 158950467 861253855 704358456 830673139 888459942 826468659 783641967 672462646 401829002 438983998 193889789 273104764 833896266 579879576 430945069 893005405 339355982 330436225 530077945 780164820 474122299 601910583 621843735 515947758 416808838 634894836 571029148 321286117 576396560 581001905 873377605 839280881 509252029 188626953 561011593 341868224 156432857 40690008 632283269 741957689 222730741 972434872 161484925 531690620 316050495 235927330 904405285 404574932 761474633 676652846 836847674 230271768 13008626 438425317 638927933 870233099 292488762 755321820 649621888 289011024 998115212 498285479 803472324 174600139 962815566 38190242 669235411 942536885 566543530 345250682 347198088 501572024 338949947 697602806 558019646 292850453 135058653 131775024 433202232 248782642 243413160 186441507 994726264 242258292 402219889 895899788 83502275 738499146 826806510 851012541 666313371 527353935 41381674 324773976 628559232 466531353 501691716 30197535 427413656 715733531 979235769 505391588 626960695 978784080 250735028 560815784 809099308 994874455 102576925 281672678 905693127 106565814 586884805 825666890 185726886 615041246 870472704 846701229 469552637 21928950 247685881 697598600 545068542 768096901 435064480 358140164 956602910 647824065 20027149 46246526 792990483 209322064 85790723 613172042 704047494 405118201 254434114 305271831 525624999 670145629 32194130 445006461 533968093 264167582 709305227 31134875 13071112 505830825 869374220 820458625 830127207 323467208 358139325 959438125 482223099 673265272 657212280 782846239 136055863 620013817 233023287 553344607 808967331 878753259 784901738 869066755 82133912 629034163 833838704 926083851 794006605 432192735 831481278 495006772 636697328 9949096 737101793 201850723 491327631 66714658 435404002 216284041 451044706 97593072 101200025 19872639 106193809 939033993 213400756 520006302 82039424 205310277 616105187 704249066 533780109 607681568 718808325 971229359 969880196 464126067 196740017 621436020 314246191 348305941 732266891 909148838 84983193 523122833 545012056 72150015 858681831 546331886 57524024 780356005 491900680 816516513 304403103 393161607 285929754 583615498 433098008 994697937 45284739 593669869 569423103 85681499 666469754 868659551 568207476 279094331 486227849 670765609 975142268 307844082 797786487 684233549 791236616 246542669 671532290 662351767 111415621 979604370 706167869 699690341 316486144 897145503 809261152 690493098 506149554 830912615 292198358 602450833 767808874 356448008 404364234 45000469 208671030 410715210 109759322 444858051 612463498 892550913 702922155 246579715 683372155 938872026 236463705 138993223 905179958 356682780 299254875 577010905 849851125 793620907 251432485 332297108 892168851 574651583 690404609 523913995 587002087 354562618 626061699 227609232 544673758 382018496 400055120 283619596 949400138 312780019 158568172 986913787 366220528 28640143 757571912 98545624 468187290 843945788 36389051 909198654 480441840 561933914 197831352 167786956 319694694 808143744 101480978 273862595 459023798 101191301 235195094 896078 787191841 67523632 551409230 859363267 251511273 336863232 907869274 212048589 597214462 610508254 190363395 74032805 296615046 763559901 5658900 11132047 257332884 101565400 235873360 770092227 795782931 885728138 991297803 565429757 955435406 811659961 719707441 742610784 671398315 788851878 933774705 895511992 449650810 448803508 516832391 448147172 443756561 604203157 119741939 268736913 867272147 212237829 616952128 417832627 964761361 151437382 492622986 722305941 988351935 865086328 95184213 815611275 609839645 259905551 235794711 267674731 150762278 937911350 39500779 24600656 751058660 229838869 383874801 936763439 824299679 938183474 627685334 900989585 511920522 16044784 643324095 676004835 825262579 86201661 57086509 184373539 343753761 995574393 12040637 362554753 108268570 812527082 774625134 378569946 958519472 389131972 186168055 70965145 933915081 737525292 70872185 370240249 216417199 96746004 920046036 214118524 858891501 136464350 796964283 290799393 297403163 812314020 3190840 93684968 216939649 188078161 393847089 19810156 761989115 241995408 60048182 925037886 83882584 379396384 280784414 881880928 880890577 51212311 38342244 707365006 515470918 51528602 376099154 640836407 868292596 934652580 625958294 393092504 975708623 589731733 692745843 211989609 450987092 179169259 57029175 590075092 225563998 891206288 257208899 277902277 454980777 835811359 163719442 805469609 263673124 814760588 705466052 159511507 575376343 956404411 631697693 159709673 16932735 299300929 110690402 923388584 867235295 805796294 372644514 548420067 738638024 298673220 726289154 431861150 764169348 39772102 404207732 668496436 813947082 819562772 926910639 619232316 503196059 454287984 293188185 282915191 812322898 937820934 720294213 47979017 398768768 175876622 859791186 530690293 925494633 30232134 792521085 244203470 133496621 504126781 602111116 995164338 769671032 97566773 738432693 929729605 270464066 868451960 450285924 898510465 285093645 275121469 850156790 445627548 805551576 978735973 263029186 463872436 170075788 767353732 143244900 196388781 587427020 731826265 208471813 688099640 675167028 460758971 773057881 271143848 490734330 375641753 713544257 242412790 819814615 546124824 350355860 163876445 130140876 820628701 664190150 434784517 874677997 736129700 4656336 596012133 857610536 489288161 269401866 340279835 355840625 490807508 698141706 364383363 946518598 354408760 552846048 923179984 80169482 884163420 602167500 145850308 108294826 512488897 997894223 368830991 489709821 832167516 627735256 812891450 127431023 79963141 801600631 156562700 163540968 523553407 940799837 724432875 877026745 442165138 739856539 991553008 152184475 798664605 335592379 60886156 702599373 848040960 809462576 730286691 455610129 816694357 423948281 359544019 275677024 605007182 178863759 150071450 610919863 423636991 850828069 789026335 939612487 268089987 831263939 422341200 786633217 507839787 709644735 594071128 240546006 60060852 314015160 747539391 604066165 255115279 162027947 61520052 505775312 456415247 784108375 285229461 914022247 450719591 593373771 722512857 765840478 852193934 476443999 845575860 720551526 828077257 586907846 802163266 205200114 611465922 696954826 84244079 404173573 78918819 652362898 410862929 849762805 523567455 193953044 675160610 26812121 328616545 884198275 5073934 164567051 896232301 138247656 14512935 515745129 179786136 813118076 220540662 410941932 981913031 990195481 690544238 415875431 186159631 741287189 934434593 456116224 161452264 972195301 660879714 110956173 625167235 783453072 742872124 182805659 380800009 357965211 582225580 109012177 821363987 352523745 714636037 479550429 373545955 536721457 399656492 896149532 343021011 380941724 420476681 783039317 921696632 794635038 426802739 162106113 708830448 511789842 311843724 114666223 604041419 787057880 121122777 639330636 587403924 571665082 363998600 903041928 253626698 303880357 444286363 899047496 131707800 530503275 972954764 244576210 767555652 853031549 398423773 158571802 248680797 91748787 422645873 242917370 647485254 464609570 644750045 812404026 833731117 869953724 129872088 522393790 599039130 499017116 835385934 561609995 952798476 665477169 820535912 270763808 750967550 11519383 389134962 304385326 775621396 82231337 974312587 340825682 771657417 588448052 147203232 581246377 981356387 840454021 711735469 631593548 230034938 511597635 708437979 652494814 232823224 564832490 423072028 512926960 561629380 167655919 551759897 872951860 930061291 921188511 209801141 197334842 188627569 717942751 980805355 911106880 202364180 495167470 887657619 57275079 563413606 65239140 720193772 357749599 687285103 385198509 297746533 881499914 5065182 570272862 271751306 406227047 473192444 56860328 848734699 819052610 153749958 517513717 911779177 294037585 798212433 881139753 143790828 698777227 68309919 929132630 67704544 83466297 642566249 890403975 624655045 110861457 20099821 972974439 637515825 581024501 561425626 776813188 539989916 707972476 110583659 435924449 356244976 932777100 503851260 392369582 437684308 849021279 961424752 220573993 909766826 8682595 951973588 673199486 505255882 200573213 526417821 591226158 887642139 531511194 293283865 2613756 459420752 110418338 590662459 983256494 776403477 583777357 530257697 542555433 621040553 646052780 246615220 587624963 383438928 745716993 7253127 975379570 715922879 539429683 339050459 18496885 682195548 552228997 914179436 637970283 271533686 484617163 608903112 789435276 692262677 263234747 766470051 119542643 611066506 407815292 441342062 609670430 14745736 248916725 845838450 606112693 798772953 71163117 571838920 539146102 953088591 124545308 240017651 948784241 495618313 281554958 521139943 446764679 969654231 927491161 108978745 899444662 523966706 903930516 780991060 342371696 743288298 503033637 380672975 980578700 974036699 500131100 967320590 515824786 31309376 815398362 155328815 443976173 775892154 23609156 594396899 287192528 856794273 299063301 237743759 430697206 11523506 458271036 6002818 77990775 255884395 66035975 755397261 984579339 677874091 360895143 805553311 895683922 94512590 318471952 800397006 334919187 894873703 832252977 547964466 870073182 133791027 725364855 471497497 521059557 865792391 415248290 988190135 79786620 673713948 454056380 831514265 72872306 729600641 461531546 975915685 69098301 544493806 200528801 42053037 293233151 875218340 846173233 82476935 1034048 807766142 985307753 652231967 89743420 431415953 751960786 669858024 702962062 112665719 824373197 71122800 499214541 284059345 682705503 436703867 37853349 903219539 540968795 628351351 493618724 839835305 533428431 592973025 234236428 42158414 213171452 201979125 838781855 879177366 242175112 895243470 635939958 709352817 106523983 902093686 753347568 413604230 164698382 436076939 576335322 528776767 252655746 792941220 313405382 681417371 52252327 489281763 129648841 96343879 807947238 787186780 588289271 858779139 849343803 162793730 723149566 307624113 964960933 914600073 891476666 500661792 644253298 742140008 44974334 682427200 235957238 301577501 991528155 181273822 791517451 433443891 180627917 647292322 713920129 996915124 109561056 962570876 734749178 268132490 470708329 774182332 938826357 359880298 242072656 888476692 434402938 240997167 725505289 444663752 470064728 393930154 364291579 619353141 898153405 939079987 342256027 436329820 408165716 235334968 918930497 759707198 351441069 693850551 43154106 864555740 460438264 886121197 950079519 274352256 832160457 151908937 954452897 992915452 10345069 34889052 730499726 95597390 445478841 93470932 509799571 186937224 900527552 668658566 645556098 708589244 269702604 63163749 252300941 568688763 462277927 182961587 458482070 25996417 583033644 97568885 1629514 851910195 231769468 502383151 902084396 206425944 570450936 648644363 252866412 704134910 523392207 457853659 628590634 611373621 298872698 281384371 943557853 988534600 215230368 582694701 493073451 404980346 321011611 988457032 655545844 51227362 730343263 316710351 638826700 50361085 812216792 176170290 818215441 626261940 418320292 731749224 323722812 377838507 532099498 394342434 15189684 631655619 584531651 240532943 574361896 705973037 826433487 892456387 534579457 341408874 36387008 918923887 218088638 326956917 193479853 643533935 847109280 599154919 299726227 88004252 99561828 380759236 389420199 657497152 752997843 45842807 95537955 257698547 196146064 650005138 426013843 645111220 387816665 661224828 542976495 221608413 536674265 537382100 569794868 903917004 678217165 275095308 851080176 120403760 814909793 914183275 188226396 143199503 114939974 386207161 327917849 316456697 417545249 474859657 739000698 114579504 556084874 794411219 734805597 175295766 559838858 414762214 74294429 654608978 448172866 292673767 291990693 142967782 504449361 803390786 895172502 218450482 953788540 660024674 709149471 132075672 793618391 549510637 764744077 748810797 35457904 977269892 437300549 651710287 974856431 997701335 536759185 78358709 256766105 553587413 149360095 788545211 794546165 289388921 158544839 434841537 679127535 567468054 22052328 917625177 538635565 819859477 530344128 87405477 135582866 629278116 873219618 4846480 334707067 862512602 475203464 445575525 269712914 775856123 817863735 9594828 789779681 452086087 630676150 825490601 741467550 24599699 439630336 682864527 339421914 734843693 329407797 62112306 730820176 557424260 199855893 768319087 691214423 44363041 588370242 194923448 803650867 746825634 248767801 445487195 763063682 931978767 395216993 844416825 664809091 620071767 239711732 746731376 272559548 403106033 142083687 704026104 81499158 642513278 201904082 901643408 302548816 948197775 260152634 806334614 868393811 521746956 395103770 510007902 181376333 173818417 340672501 971250149 177994224 320550139 728665351 994636543 113032211 35373960 300068414 212295649 141529380 180849779 375782416 296199893 228534134 793822041 163773373 759579285 287842176 768816185 703829793 567813470 98148883 592273824 751523736 479419897 48456977 630119995 901386254 941274307 982351971 857882310 229964369 651123823 374249217 286189849 878405089 618060823 61195851 137815312 277552914 468100213 626233475 602049355 823091149 284263417 112055787 784265465 55777460 281735434 426877162 409835458 99433179 340914236 411344650 531275723 37290154 688739774 528437090 817017041 821705383 586313367 925076443 172533593 60754288 478458905 220849164 387233178 590468321 149231167 434901998 505137921 641351667 913309689 751151294 140908637 137189032 313934599 825935918 355391041 326821762 157329107 21115522 286295585 112357397 266202383 21565169 80258300 861861 250625180 971169791 126136779 118640312 423273536 93067140 857875959 112170457 516312277 840289191 255772671 783797587 53707911 517938594 374202903 17866675 376629489 185676246 418882376 597679929 289946588 154082630 119132844 188331181 709231251 227488957 142660405 929476378 741928127 77464560 623882848 871128723 406770845 274691391 621579067 313793730 840532876 271362591 913649377 624156971 351698927 561571633 692720167 21020077 208157701 576253318 238893943 638908734 84853736 518398114 7521323 497153971 969302854 398717310 801372755 876191426 167142030 411824988 636692797 821465273 892701876 980235817 510779415 195106121 344626322 310517541 992932340 826064340 259548754 212098842 383264008 449744347 801377455 119735223 9969386 159813512 921242810 648146892 412187983 545784715 648358227 900882288 882233331 835561401 994365515 104739990 494523230 754235518 133406029 455150463 461763741 726761333 978918265 233300369 662825492 308368595 750040059 930462590 405854590 705594225 895847706 947917089 903478475 435590389 447798262 483718295 722539110 909366005 655762687 366890666 50933546 382141768 303504378 575862197 910461588 376186872 593970001 236263011 172718718 526237011 538059915 399369983 465472486 584649033 595396406 623630746 83603347 282961256 275898683 455072697 827258067 918465389 87344332 975558531 901229472 439546753 984992442 905172363 989831643 864253664 940149660 419438905 693133611 903915682 969451427 387829081 869988701 982147088 929370508 221345539 341759834 781770721 177679173 234793224 898952041 242218598 158948703 879440849 215966738 11468014 534315657 68819863 851388123 58340813 321660191 997950834 88822644 621207021 288194797 702221425 306411710 573627452 335122605 751629790 564268322 475256531 341996857 68844599 694806673 101953398 779867260 465617189 61514072 446647112 125770628 721452948 516730150 716631525 639480698 6207472 214513772 166989744 957447213 995403694 98664178 670105140 990935791 421827393 418974043 420221859 279254548 604681649 551331744 60854634 399454987 943339653 277994800 598252374 371690861 768464659 588818372 894336149 408467949 581743001 450410506 182624311 393154065 432481789 770585367 533156435 64464955 106534902 238002558 229632393 179487044 669891612 965430113 669752343 802774090 791726413 80962356 155546129 860269834 413977269 445929385 34194548 994550893 118590707 194233056 745438553 619887821 762181347 608207453 481232603 664517184 449731261 490771208 711792160 272173049 688723327 879155174 231399446 684062824 515089104 899318271 312965303 742638571 476268280 836697451 12351270 526716936 155668897 31635814 344824180 336797861 797225376 24132629 731129157 806883679 15878449 255589718 365705073 86793608 117659601 567746070 346858078 559171525 722442984 288367728 890609658 668546261 25406086 833694858 269289357 291792917 888811730 968009903 125286502 846473995 560423063 175557296 703693497 704119450 652765955 4849248 297098341 860533460 390055436 888752298 52648412 66322400 347133579 413768891 540486624 897229682 184401223 929065794 793795219 523249008 828531632 777808877 861460093 299246759 962326585 711434021 716529119 325037582 917358945 82714205 405416662 554623488 890249164 119986781 523950999 867202219 474870164 83490434 929912919 563131413 648227226 586434427 189285800 117637430 65437359 214561497 936944645 995679078 606026509 351490573 649944678 310360195 286179467 727192569 554091054 476816134 37578857 597090920 700367151 895599693 991329034 302089184 402345810 485302885 473686404 301193593 95589275 183990265 726943706 819243222 911787574 508327385 471674884 81917094 378149042 604825697 570367270 263156097 667518251 841397312 777273633 975942776 475935580 977130907 360479841 550103966 476625814 149966315 427146481 80686423 565522568 845083671 744222835 110767292 644488032 153562988 568516344 333975759 387920326 499232256 857816828 777486592 617852478 635134770 338045106 609969136 645392473 703478910 296242966 322157489 997827648 382184025 257171096 832433829 969892550 959453554 769374922 9921723 707634670 233180390 478750255 343384590 831946775 504543426 425568386 562027654 278614412 799432201 578675505 804210135 399923646 395882547 68723864 298098408 57654842 726206489 985398728 673211179 585882092 150005787 798092223 43938830 600314046 786115502 140998837 459070536 108175307 458167222 858744219 292537665 585758273 958830684 235003761 184881664 573009669 350104197 326220877 647150273 948168575 100917765 733198393 327077464 276468069 609919009 525289034 651907849 784809364 111843569 790123780 749511422 958639983 759077734 262915037 453860917 411237798 256020901 442191396 192035908 417557559 459036639 786071965 971254977 222345791 393693082 841093798 935683735 334788869 797072880 404540209 72279120 654958599 845920133 419162771 967529508 601933807 28327771 206958372 741382396 499271020 200240503 61432239 567459780 98819920 197460366 834481675 36257664 225730548 71411035 776225471 589982410 570019654 821946409 606720580 956093148 735601620 45644584 471742711 187547081 874039509 503018853 954551779 619752640 830619481 663889686 422110697 454056163 259401888 550539640 170084857 628544366 854207276 870769097 829435125 650677341 614052177 88361483 929876852 628102843 392447007 318865797 989279006 624105425 345384922 628079974 940363282 456792639 573488462 343466796 704333664 345193121 860973951 869189014 318270941 870986450 153490884 80147908 338603120 851889699 749026905 234448662 811242368 830809924 763808293 805524553 804117961 569838684 266486406 74637910 367560246 877184596 498597852 280395262 694882723 254362173 611201129 542658384 795834356 371690741 872535173 948596250 920763533 154625548 7751831 347273373 672784614 706131415 873840283 419640490 543560659 430127430 534285631 324118759 531315536 697470512 286458172 270231145 543982015 686445287 96617434 355863283 199322655 809474730 75830156 353120284 727624512 704395001 482600413 879497109 398859058 700786704 205775189 642433942 519865092 929011543 99996812 857975991 90285273 87428928 573317663 315445433 329503377 242355779 393479676 530303072 484588139 607340913 521926339 115893603 331445892 802814932 504523638 116266041 491553268 290754394 949731832 640628909 693276718 871495234 659647544 527579103 917132637 746338435 353700485 978203118 262709877 58551985 22340079 411121818 231225482 748934769 655101123 208782849 518405110 197722798 993615122 729642112 840714931 285961010 833094353 286869999 562247338 514182780 73988118 939913190 807503919 918232852 405863701 308001944 76073869 653083457 90233370 392331120 825339849 784371785 933776666 252855783 64859501 738010886 195419666 545979348 266342838 502862701