4000
603332366 870535464 292805653 105908469 522480685 554613904 991408987 74141638 195726748 28625676 331990096 400052859 6616890 277497993 721069256 674916001 379517329 704662282 443785816 975517840 60646721 276301215 816889857 856800956 70186635 747451988 451315600 60673458 372937309 45467614 755094598 807960061 144515447 737305204 106344540 784435253 130002312 371413957 655318350 200440989 895914113 618427577 997572043 571219707 731447284 272528874 22186567 428938725 672673755 721054798 512425521 628625546 417715792 104728271 800921295 345558774 575325290 884171492 865791799 195012498 560928486 947007829 968356209 789213685 410532214 34596874 702303018 51098807 842182892 107695899 496896522 486622498 799681775 639349661 829327163 441971752 692433929 243333943 966391997 547563518 727128306 314382995 221324443 787232386 295915097 395361861 732093956 363419997 459259102 782010255 530677527 424478980 569119195 749956386 893900542 293169445 775516765 961567387 966493779 591526531 905138276 476525533 247237745 568129076 769537945 995280605 565688006 614222511 78109940 645681234 792901582 652983039 257436301 437304447 656140336 108726820 359098270 996306632 371667048 893038383 927919770 124146343 807976793 400065717 565619961 752362597 756915186 827144915 492217515 995834975 338545649 354112121 5836305 320462656 854035010 417832319 769223941 822042830 838786533 494651333 595901964 11132673 290359256 872689614 176410305 949724345 312030710 901910015 604958709 136618260 829846785 243106048 122015984 484423925 586161953 417259387 55547282 405590235 370648360 599704357 792240295 179299672 292926300 908865685 221302855 758792598 390259347 260032844 263678337 186653655 222206967 61616876 274764083 102293421 54183803 699481477 546023747 687656417 632292627 461241803 552348291 438037662 957862507 971747065 858178264 452101688 294624647 679795059 776295929 203111153 273419193 508723513 404999457 669171335 806329001 508385542 550737937 542938925 269968894 751903806 714847971 807826794 806475331 353945142 147305200 889688152 399617551 871435862 788352761 819183369 645352814 228396075 61638023 264106295 382819990 115461163 264753807 88846081 97201846 507380158 550315249 84825613 657618092 808463235 857724983 533092205 386399389 503917340 489180705 992601796 284992844 586662941 902563101 397949897 758936893 432732759 537413670 975065959 502152363 396411535 361372855 768398970 299214617 52119899 685352236 214202357 644234180 212669434 935665090 525509827 775952920 924487734 379559735 727303810 391828723 319507821 507579947 690811239 611955843 967560279 49871697 662096780 25252119 52142885 213572754 479857516 196813690 612196217 944498409 142815883 671100106 768739111 785490828 231232697 450090399 340967649 778112894 910359928 875099369 492750774 73848846 20475019 270561719 303222883 357236712 459253690 478955109 615892538 373028104 514084227 765072590 78638355 267289469 792237015 380465992 347247809 989859025 195869616 120399766 921702712 446370679 730804617 88048295 88078742 335692500 679450149 96863217 865431871 412669572 870112521 910144983 17818423 129053896 859818633 858105894 657853386 742577602 813262759 246428084 982837606 845237850 241010562 130416496 655381165 429793889 859411590 657111086 776972237 280301755 114887552 968205532 251211368 273151895 746177488 730378913 317128571 382695928 734996648 737744710 515375949 848674346 567582224 747923950 752622977 704341596 553340278 393454201 83494095 131243362 267746165 577598687 483097205 741165509 382510543 285262011 713129443 939611653 898311597 962603863 270373579 254772895 942397504 982788563 6264555 215626601 143746087 175974682 603931115 767344173 589462833 871169406 832074215 397712921 153915585 932345740 571181739 372102412 281494295 845455734 236981649 13672199 722303223 194210500 860627702 526757237 811630514 934890697 444686586 196110690 353916112 597014734 626309189 209891635 468417091 512114741 723734963 956944949 252333439 11771870 861592554 621313818 758183258 874674917 147400946 101364640 915483479 94307460 692465550 363782353 26842281 965377668 861219525 232616353 11112844 449941098 490426182 174774183 286332770 453311608 519662872 127355 529901589 275489786 713198591 126492385 560475653 519933181 483084892 752510032 759032830 331432612 266784862 549822082 953122397 806572608 785956790 517076442 997712535 201849006 42270241 365855802 84583136 62216049 333582493 228326032 3575965 612101082 297681001 803444798 820442909 940532048 490784265 284368406 631979354 772396287 734984854 173304894 964581388 339142408 924887704 619874315 544895442 181410266 77018913 98889459 362125848 126234977 439468325 677060162 634388377 350272958 806764110 592321532 4894631 832058170 204401500 126078107 25046723 646976202 424962471 914520535 511824233 909619208 749675097 134982385 168045095 500487701 148828982 656745667 681901510 121244273 903341594 548563083 37411594 175319355 815845589 160498490 589381358 793581914 332239688 820247448 182367629 543415088 721279748 100589179 152793697 313784054 649014910 519200698 3434469 209675621 769216661 381079581 977119390 398657851 472372675 23290841 727932420 768144389 144011159 319610475 517951436 766834944 255597466 672657837 208709407 259027544 917408029 697602558 795042647 799859854 711371575 19341041 448827 722835284 224990196 627870798 400448109 908483477 309532943 323017969 82914020 416544313 433287167 962280683 673051660 988054328 646549417 110778290 328901130 162832133 411783629 38936360 506616195 426383391 398365431 843821339 878582385 73460699 435125194 787530937 1178322 758243667 593851568 318314861 406556788 263906856 42806074 587021838 238025049 903523668 720039539 822246305 172052874 533921266 560058010 781042668 783125449 678000003 831900636 923906230 833902609 517864164 805853911 637371590 734300782 629488054 661649572 290454344 354999294 637097471 826207746 330052461 647795133 211224462 991100357 614989424 637124333 788042515 246528912 116753808 657218384 67024484 864331994 67272145 246471997 748814838 962515172 46332875 443377520 693633727 757388759 470084663 626630724 597858938 600563632 200870348 419580233 124517531 541665396 501995359 8632070 805890324 258881631 716789133 946835003 90895171 440985901 546798515 775711473 294809113 399291529 270780286 494115328 868699413 840426905 562033252 176076696 331838820 855824905 208656222 269117595 542420746 200469580 485488259 228823075 263433448 669298234 213672253 940258890 871458806 21197253 343014732 612592456 18495211 941707712 559347578 846158943 300128579 705706414 517769676 179947970 196390788 564534201 797329020 529210718 996051814 864327840 881681763 493902728 485089768 222340859 44908685 202766268 766166393 772983694 361642020 459607791 609226807 749850973 93797819 974676586 318494511 476036388 554458758 150368560 554346663 146633864 670267880 376536788 412869893 42116646 37081459 631757172 290784018 411423630 203669085 303959274 146567596 779495641 968398903 545787860 780891102 697281802 840762306 753889778 592233578 335457920 421512475 460319788 94159560 924823279 621342670 548533729 722256351 264469202 229086010 153977288 291406381 529558688 941071487 597036619 808594407 862590587 118812577 367302617 235751673 653596182 584247566 208037763 373130355 609007935 362700249 724001526 913015582 464181882 123343478 375716621 732478651 906537217 634034583 16808513 43601464 903123864 572251929 803427582 207663677 642938024 612365125 729235537 401708753 377093193 322268535 56784229 745940672 572736790 543159930 973489655 468465150 680487714 168479098 403509880 428782950 108889195 188298664 575202786 373381861 489191281 495460965 373442235 520423078 951133286 663722868 299186744 560023991 612015953 82284892 168619491 238413101 314712206 790789089 125231695 500280478 803387392 127128830 119636756 499482652 188422068 660837791 639674126 754434011 222776384 789430843 55479306 418796442 163819993 854484645 762247882 769322903 825548461 57324398 847570749 369418068 905473936 803897287 760400462 211570940 991132681 510014092 910483255 668611140 338950625 652782303 719740642 524473441 910422233 657793237 505233305 824922955 504982633 802559249 401648045 672679185 140374297 271593055 954427008 232478552 2291637 609917821 219382986 842502426 561149201 858477309 917372532 267730746 993448016 51325104 89906897 803432957 929301235 27039913 319520984 197547918 993915593 395006641 411422055 876140261 783072338 597160518 121195164 194063137 919733501 761163018 449553429 634526628 385387480 611813147 434511563 938165897 797533966 671049589 148987966 231156999 832235249 755600873 615778435 1799536 111950068 25102060 369659362 911728100 232593753 17553462 436490701 119749834 129048946 467057743 984363583 896390479 810674000 568753750 415262121 784389725 962542050 595512851 524242266 64313194 343843462 99976131 99797851 805651654 757912598 54864967 906371138 446858993 864337763 586320808 62672873 571667318 603161213 160903929 470427909 481780297 617064223 952982047 684476451 646670357 320923117 591496536 593785387 644388018 736508838 421556 136748873 649445362 300554418 479154713 9925612 775877040 955551564 40176091 286776088 76089621 963689285 682879203 399828767 591814547 611413279 986627847 887621713 748889685 325348343 654233077 234638029 352708950 354017769 546661983 659220328 827864406 722143470 293088688 204248552 935986546 884759420 622948857 237660001 805779749 978759836 927007432 699905166 491811789 908747418 760576648 644528102 903806566 456585821 808435553 932401995 50090826 179730341 276519382 15760651 674457049 214078998 823519738 582799227 989062667 997555017 399481892 355244783 96881662 760083263 690516735 897290902 882544515 919421124 539163735 527199351 743462991 595723827 235819780 980503077 689211471 538076289 392769413 193482204 191386421 635051126 190870049 90923617 265233157 506688223 809747674 229092709 755380538 336365498 91439695 548105797 14727458 475830025 894026060 167648669 408109761 389541571 442456912 911445509 150255552 489525648 490898370 149413475 326971341 17052490 559248873 152955003 129398502 391198390 552727658 903850835 553825597 315055182 31142301 588475494 782025466 517128137 979136990 231744910 74980409 584954579 648144084 81203054 592945320 984909524 648606227 65420282 266865728 871113508 834620238 934099692 461192117 18693614 940163586 520662337 665073870 154325000 905971068 888210790 301555835 128739909 364126983 525506930 614802036 822802078 16203274 205957032 541051084 267242870 555509459 139670510 648031977 62890320 990985147 417344696 506449186 227782393 500269872 450945998 230167856 910979162 702223144 137416593 498056101 250172299 221152193 126735494 383289167 282160803 174819150 634764400 212569712 47073564 421220229 920957580 916920582 992530255 379953320 78009864 428168720 202862063 977851786 790365525 936930505 155332302 318077718 751784301 22170713 655347355 557187148 753966630 963903261 331242896 279640586 131275311 902906206 225424482 347424773 758353020 860881392 122141946 985184662 926271106 26825183 103375413 785342620 607674635 693923639 141348772 453197738 862707306 80802663 435399496 232446026 187569320 454798439 620774316 749389287 317249483 338706135 137518270 448573058 174811043 130473096 35614933 831498458 731779749 924044637 554384753 935000726 605713063 28299621 769466800 729760427 986765817 890262959 178022588 11198884 623687525 465424674 680592242 490592362 135261871 932921494 841443965 350299079 385526782 240404386 840906281 949563286 133110641 867168859 936261284 552166897 633555776 409715417 303676327 346019978 715985109 708130263 502915187 225937394 634585430 431761163 514604575 822088488 145216234 271648330 443880317 575387220 759416656 64627421 541474676 977869172 390063616 239832777 9155020 924844379 259931879 978617310 265393719 484223407 910928386 249819281 338062996 119437841 212097969 247837197 568739982 123626040 619566346 160563486 557736089 823283402 309863652 893557254 908402140 959444031 302010746 352428723 640228724 751918277 482291101 322354053 435217436 845425658 851711700 912691556 814996977 645123603 436975924 183964218 9534730 997289211 92463910 102669050 849913092 755907065 179776779 737156874 550132817 615192844 129717638 491629369 154392397 530985142 390623385 641760066 45608377 339668883 413113868 292850175 496866220 28095728 638294946 617084307 340498959 901423758 549147924 388741632 769541299 276775398 914696401 551829880 656786862 543509083 906815764 878709384 876033881 583875583 528879164 203862263 918344207 652361256 969327933 789124807 243415857 496377552 530060048 65602234 756763316 653551793 875019151 670811373 64948007 831818049 26408932 477430854 73933401 357009130 100922430 963923604 273782317 268929731 93400360 184097643 786494369 417223660 570360997 366874484 476020678 10155734 569742811 357042603 425168000 849779149 840835186 244259196 52883984 923085113 937982234 189560484 872217332 647737656 780742154 948072986 494026661 970525660 513014953 1597331 434460345 643163919 611701888 409141046 630356627 287279966 756342718 440884636 862211755 727466176 564392782 934445905 333197172 791242484 326808857 744012555 446105122 675393905 381687922 372204168 57250775 413764724 834575105 471896348 76301166 7030568 62870803 139266887 416584489 573152054 52327464 627614826 754036770 525993073 329645082 973835479 695566067 71496636 264673316 652867138 768114231 196435796 187831876 752686685 119773401 523053487 746797603 591529461 181726383 948170892 596046482 479060167 622324356 808501780 361899523 623485559 966343310 158530986 208332939 408006721 23167513 635013843 82103400 52887113 758784768 933007597 770877129 945506080 192264820 82851002 843639617 71848143 19575795 638269878 594031282 62480090 430812880 700835977 950980615 512608111 498343807 801171253 648675386 253979087 786003275 10914724 282371691 193103369 378557185 108028495 907532398 182482722 508883802 474404622 770708053 590275565 174287341 633985519 996688405 831471910 61820719 389878834 734543035 555114945 249630531 343356714 235338598 34487909 680434420 827217776 64607466 746815278 189040051 592334580 71671088 470324717 409271945 631703253 267403666 264627337 444184909 852290340 375926556 248131029 726163067 768486177 50050091 170440168 909805807 164445750 550572382 699240203 388127763 567062305 511492159 187866993 66659844 334078690 398513485 461909116 308347271 259451806 43967238 725417779 442777999 257155660 599246169 833415884 234011369 741260111 101066759 854298160 189722018 560688365 636422461 14009189 490750396 435026340 193489879 530450583 245744359 100687115 365122551 830764665 28164734 807479827 670372641 845614208 577645521 428684716 516914015 210517378 955633812 217689179 222742874 670892941 531506013 290203530 490592403 128004391 649809605 265264577 55763623 118710116 346609708 750111706 62015287 579730575 249006102 25955672 326760235 802969281 268016018 823303143 890583275 988927017 533114477 642808632 49817873 247139171 64577742 560272213 983804819 172893089 286202965 495816238 550878800 682889987 389571238 648201115 14716370 121167986 518149763 458418825 35157493 291931414 655998836 886385579 670663904 364354144 56554460 227006434 445240979 533554210 335157506 728091103 811155551 341909597 924062868 170635680 543366269 721112124 424923839 826383566 173750504 372154134 235206461 525229163 302081808 406126305 260131230 785913024 723641525 946585239 561976471 319418428 779318611 850753171 915315429 230285772 121041593 764154701 722928335 919943638 500170021 388075133 154177984 819878111 923113013 761695312 361049600 176865925 596597278 767290386 397896115 483828312 368198437 498818566 505694020 626976798 997690109 96419980 103521247 835054535 269565393 962277322 841526073 935987387 214668503 735648939 795455318 51580626 280129998 749784170 442540611 978999250 504730359 15517828 894730966 373997278 592750176 273896940 937600289 706097318 505698062 588314489 6188957 616655788 794156025 212659883 307232466 57582987 280252929 571550891 992875065 650140524 143503468 400385047 101426733 532190224 848403599 103128414 882964470 484241729 518766191 317374820 767974322 41775487 126185026 995911592 637549741 887319808 931482983 938879416 288088749 625388485 596799098 614811966 64025328 160679507 9533990 110841544 188795765 403571030 996170251 82522991 360025989 734705639 760257403 855793169 450282650 365110424 138182347 25919432 874471676 259124379 410653377 230796603 929822222 989808958 614777182 281055708 568035847 395292280 589873306 209664906 170906142 922279625 123351164 1129225 772570573 276196181 145780756 886803771 778576700 424449849 694660015 957527939 345992998 721954968 96449266 544510878 352949264 975204138 552779617 914881970 698288684 887459630 688517251 494422649 413679809 639014885 897409868 56824182 516719592 200548907 291466436 125695082 738084671 600120839 448994100 854201019 973939183 535796390 438594517 896831013 393692287 457025415 691283853 736665420 14880193 396169925 218845016 483495240 464583530 550193630 577081094 953554983 952762988 398068185 621941776 954841705 801867920 6373493 741755425 861787088 424148567 563534717 856190720 588532379 876166765 862170284 326995044 640511871 518408310 690020166 96975864 761931048 892977614 925533205 472879742 501454690 713055671 91857632 202144719 185359514 460643741 911229028 5312459 534358679 701275692 792645222 244322628 281850700 670619227 634354950 272482989 815793543 890789649 68820837 825460664 683556593 941969006 224263294 126817667 208082698 143872384 520967451 189403998 439303716 219749773 500773916 813590472 974270205 978609520 18718975 25457053 385847167 707245619 114190156 106747044 171194442 291772271 725831560 332500886 866157745 572601804 281352632 178693499 367147369 788657982 332330565 826785292 190737299 187445817 106531680 386661494 592079326 633923153 504284238 427059558 836638097 473933110 422125818 37698701 351626324 935065838 562864914 72779460 76072971 538383881 925833765 574763037 442817661 274447455 116914592 985687273 757283731 717284802 919637633 685255614 66390102 586522828 351238665 108735900 361739113 911440658 259583984 425890068 867308845 88950401 961402302 592673791 835439006 541303516 322496639 901457300 598515132 781241549 863413443 383830081 451615192 793145952 320872392 85229695 139036485 401322295 150469699 761779491 442033353 7420186 651610977 814361893 46591430 271468376 979732717 978392295 770204210 857811872 43209943 296637984 978988997 949269920 268372097 516987900 787603331 363487672 506311756 347245582 259433469 719389688 89041826 818124675 444739452 371265398 57486704 605840687 844242060 360168245 437523041 388065007 678147435 377873666 778111832 769899903 284132929 686343922 228075391 841903512 737873351 7667685 389640645 331420418 117346115 854581341 915808827 153726140 56358578 472523769 207070134 803074227 410060168 907169467 209295853 166226887 291119091 562192914 871979978 393940745 525285553 584091953 972356380 758052464 744241678 275712682 773624233 16746542 985424967 551189821 177380153 966991572 799016918 973288848 550936428 539372265 283556974 870344524 1625393 575900161 768937437 882763821 255391045 665805750 923759033 49170776 443463089 929472164 182119067 584171835 936195808 910975806 453875688 436173167 206706448 940863458 700022622 401987829 972273076 883628241 980642618 33493677 933397542 105772335 450020053 823426354 485812716 587028822 148467534 135976674 56513635 417477979 148672201 38459503 385425111 148055523 291934532 252010769 253055114 31005863 819330870 637568574 374044307 138358287 791016392 335364622 594798494 777561813 34385118 90847826 365464721 234667928 160508113 819969529 927643530 2502981 257071372 806742246 30134429 574356450 71822333 506571130 433084379 692815728 87097629 689247713 353586950 946154362 875962155 517269560 590046006 403858024 801312370 107227020 330235457 668019534 667979253 142493562 857178283 88207266 911581818 428867283 477941268 500659617 626164656 181952159 270906642 344156869 433386364 206588837 598138107 295401853 714517471 10068299 980757236 183518901 528953932 579946732 722678276 612340433 868592275 116639033 60538951 119299321 611892455 625814412 670767403 210383465 549289953 474476009 864391969 531199389 737408687 134860052 708623700 973468563 50537919 925259442 916990915 388301603 570079959 56854581 875409314 901362121 262630295 322817441 478771445 801485709 126998956 584527793 666548090 688157504 906488461 329357488 840734991 444782824 408705328 913985674 821063527 599845001 476745139 138245570 584085547 521306122 636106543 60399310 161902245 171290438 383845154 959772966 510856050 992681964 749931890 78604973 794148315 766412961 165282333 417407205 543492947 581659086 601252548 934066916 165472700 230372403 810044593 321885904 645879969 180476901 302950564 996296967 426255412 962285745 144067697 438992717 45022172 849597970 858841006 327213427 906165795 144611119 669964196 524518081 566173115 620464198 597684399 305095189 895472745 783017786 416169483 869234775 205861527 784174599 344747360 959171080 570050182 31934541 778505898 670298555 161173918 81076857 112125946 948901254 461004165 212776804 41484538 763304358 450998828 890538477 901936786 979626578 625437722 509377418 848290333 461118759 199795477 889422285 250528183 467466895 500766305 17604395 368982688 393622291 581316572 17523599 189091093 244273370 409111033 760273621 979896438 730930816 932453038 139411487 861170957 815674152 874197457 440966173 24964594 594798047 109112346 798351232 601325287 9159721 575032006 637947396 130064487 479878452 382962584 660043146 647016574 618016457 347338067 203081790 934333344 873757103 772265605 435381158 668995275 105617584 814439579 596754965 129448435 284040224 903024870 768379236 195587610 776430883 634498739 340007 390489291 256244991 46245082 292368723 522607118 645044846 209754022 878101766 147889919 629612141 982014038 345128763 809836080 509021580 552047037 13445824 480394327 467969449 889367779 346183022 695223799 990445626 491742282 596704623 321222247 525531340 966214986 520387247 522728495 241693321 47735695 237204740 132782444 854676271 59347452 721805764 535655758 765414362 901885577 984262989 196570633 205584241 99955989 589111359 329394396 737463352 197406512 128067728 705847975 689480524 541968665 17765827 348512820 418719058 370603046 182815698 249100646 221239398 287415643 124638024 378847544 252646828 771512563 50317004 802294810 986296651 788457850 763176231 177327569 224074859 395183842 730175517 592392552 624710494 405636275 85477423 859356283 178630150 995216181 675409571 881773717 265304375 462688778 335639023 718863186 933648892 678475650 34212266 391806454 414722857 939252506 488424285 434729377 976943044 170074057 724071793 745414614 378622982 496606 585419359 426525538 619041752 777133310 922960056 254638273 576481963 20714908 305810429 877277716 746943093 747149858 280868434 46824754 705189627 560121828 113437838 974504204 950049160 737503071 840406373 265652599 432252267 36711219 834856051 43532765 401450658 850908740 672633175 911955474 378718827 347516378 331596469 642916962 930047774 303403447 464067810 809327732 240355247 189923742 689799273 458977101 928263882 921087662 830114184 547080141 788646670 856523000 775317847 553078440 893636417 772200755 446168043 439072753 724966383 922345142 902613416 982557788 545073066 433605953 819860891 799965237 825251464 476578038 725724995 668421214 960038417 400256263 776266819 119581849 327507744 668763843 548504292 514592619 461532543 616763704 79840067 621282150 600317510 111978578 718385502 5008159 499142305 305191080 601591451 998218236 207611514 248156656 899131695 150041867 288403268 934448895 645759313 497981621 169251023 307179548 984323514 548359786 714399706 333736039 436969813 383045241 92953846 894002355 404707626 738860548 750607994 130716834 786744863 179730823 962285075 993827434 112736879 176621427 143416470 152907431 381572398 864353544 54517163 575609762 608429237 159059844 689955413 81919630 318232560 102093378 566659265 323561148 694780965 73168633 88889706 508998048 815489437 350599176 674477218 794053062 785128958 245188685 553639934 894047616 895626756 567707140 189497128 836702905 243666616 77850301 461996441 757493965 389196544 354423036 619984986 44892093 988534015 941592201 784988332 769430125 453441660 279459114 966501447 909589558 438068806 888487071 20263017 713721563 568505081 57482245 596886817 583829662 739405546 757616326 492188534 950975102 129539410 966857046 226402821 418684842 780217140 464727294 621151068 357582536 77038835 605016432 504333363 745498203 866004446 627959868 219743474 865790693 833581482 438640076 319833256 522244127 532697303 871045905 686607656 684396060 530907129 114746505 602079400 383086803 738616118 125855602 765779875 941918490 636834313 674819103 718189668 817532056 108189194 560102061 124277757 72830679 72521287 204258425 41279657 668571326 336849333 201730161 411986272 904080391 39224051 712213231 369263195 623519033 789384172 377775804 298704675 962228086 917452168 234251671 681596213 219596871 121893096 371953468 395458336 27498562 506188011 88446063 948662698 650892682 693329979 783675713 42058019 552810498 289317102 781664050 143286226 349560738 398241655 224653328 533037994 240016620 549873123 810266216 456476467 36469817 99750919 119648585 875437848 535150452 249729729 933418471 706011002 204703416 448522783 452096070 531817760 308258472 680625056 276681060 196930590 679925736 433119264 938433827 795770439 32125045 168270689 427819316 586976519 79243407 106784110 53218329 281049077 319962279 753390278 56038524 874794449 697698338 106110624 836863255 854843349 827512359 719072403 568589663 204108970 49135370 554159572 422517879 646121740 378059072 334365879 254583299 202525630 415547407 262947998 382846956 429007328 585866367 498879944 800695342 319130970 931253582 663684652 142378983 552769380 715655782 328077375 334087676 258022397 371967656 307246922 558273195 86538512 167600496 925332353 533429307 922041781 989784726 545901455 485688183 111893651 461146039 588304910 233818448 271900926 668117142 236494726 150049079 928041209 759877347 618735986 690850293 623658285 545095776 841207657 413946898 485459736 696903747 595051252 595406383 420414840 432820402 157651762 807321659 605617887 113400984 468815482 243856028 822623926 216730792 545253169 759540513 121640499 419236467 430297432 760531393 27623780 856590810 449878935 108683004 672530200 552148340 947188366 789524596 167297760 371666000 582071606 893468751 670876953 826307838 681442391 963735481 381376168 835611738 362689995 535099976 768494435 516731422 938978916 306378751 267379915 583324553 813660161 560079185 613125868 754457883 208818983 33811017 156756761 847291938 759425742 11143772 46806052 739575045 620499813 536265964 798855668 167488507 106522270 32211707 83600468 862816866 519103025 488269546 385462415 364811419 6752622 554282112 271236935 454712413 253507587 366469163 452460544 955313171 322794639 434488344 198897672 942870518 126884617 128080674 47369541 537114386 350973043 133395360 494962595 779261550 573154473 598781997 98427274 918104535 488023107 573031032 439503887 727879191 202826047 398855546 456697875 852082361 612977965 100758274 281947864 393806195 333419577 233571540 508823945 963121028 138714998 153316479 899454989 403375309 35140726 484833891 942330237 224196145 484596621 663178154 365969884 405388257 52890003 549707766 477335985 500878939 808853109 578995063 892754355 300974429 187809480 413100061 338065105 993134937 499903378 118479872 597031026 581421834 128045076 579423670 764967294 126802393 801974622 694584859 695652483 352040132 739331148 748849301 796970042 156295562 996240258 401783154 201235441 361504560 228381691 168543788 631684048 230460656 92098890 497011054 722117811 208512971 248293211 273155410 57879417 404529831 321539782 229792784 887237866 246302506 338419498 729697112 95574674 199720394 943896647 523864690 748828924 526411050 172959919 838673406 542523117 785982699 880952195 610161240 978474862 273418282 541619672 713575711 651297108 58121283 937147381 934764591 696412954 514351728 338106478 378088224 377260639 364166333 863002330 643922272 402937387 78890651 383354962 740365303 284104607 532859536 869331978 951154990 283454335 98329018 608870766 866984908 489082527 771501742 341042132 394396280 664875986 401185352 671843984 783970019 818388977 155725594 178150753 393225255 321186384 616078362 485516750 281628885 683396449 448619920 289635821 603107681 379746898 121819887 659502589 839027008 674266998 588102301 284231749 968736526 214621999 863475892 708601233 471997855 377062910 94155628 671284735 581572001 612633042 680195769 960317633 744604280 869966499 942334414 721991905 578812352 360065677 693797496 772539651 113855198 257201514 980461692 254397336 547048186 114873690 409339531 631435300 58746076 229179457 606447357 676718116 960731621 749339939 403062473 987058186 473017823 627488248 673868227 633170281 144429053 466236055 257822346 415577805 102114807 550919809 34814671 454469343 199874820 938584671 13963552 548840303 804384096 945161372 346536299 496673834 326055427 379942824 200603253 868503702 907009798 584456155 905476068 899440783 85979756 476819711 521804660 585859958 38297905 537651875 253370622 920199088 843038138 418201651 741459408 536836375 110535408 603908509 790335644 733581881 332631651 732295285 916236655 652441738 271834516 863119662 753863048 203517403 714511787 249126909 740883081 269071787 797414016 883467293 874118931 903210937 85025583 317810261 467804667 540941009 336606004 832109753 698491968 550442580 641290151 344060121 431920866 389648619 735909103 736137443 104536382 977736914 452683582 728017323 850837555 124677728 629490087 777320507 596790939 956238227 598169721 653336424 926071494 69162602 69392965 56868540 948451150 553052238 682773255 598708430 445804595 854754355 65977027 126216623 59207943 65508095 363159220 371797816 821504140 356067177 383818649 31225672 921561965 312675268 802967995 714145720 633777611 507905704 975208344 167154794 545002422 347288897 488023561 223230611 74948665 352437069 528911697 958134628 355594619 909209625 712253070 955573003 515195873 476816259 678255449 835191520 845091611 938909448 921843205 888006139 780122045 245976360 704562232 690453884 66647352 453184785 312156303 25707805 345482704 499658071 126113797 533124696 839716765 497031333 359570070 551449538 537586956 721085183 689696272 710328507 351829698 63147108 522402413 980627989 35729366 66472776 813436497 790528397 67700461 328930681 994681860 793500711 58210183 756820982 962665113 95720228 646733714 256978573 532955936 588039476 627508738 773857288 754077363 672518913 52242156 742728719 703003765 849420991 856831955 777930586 214997754 891489565 615311162 275174514 362396847 749422323 763615956 898181777 172940623 597216750 483417959 836743749 890508646 712020450 814866843 179312603 339157698 775805050 671689392 76156459 556650739 672842145 693741498 603009286 34423460 449524548 832026137 217053821 962501440 985620014 792183529 691708941 536686505 343068164 548780157 424671165 121686629 363285175 648017765 320891409 761464139 981306262 727828466 800147015 76991978 125005818 372367176 447480834 972768595 363688262 355500940 610228832 688805879 580693424 26258328 975567162 441370864 339788753 877338945 248254531 850224364 201916335 712280603 279504851 200184418 348406291 28205645 24776492 371348970 332620980 664589 581820477 38514803 274537190 393259487 499190487 621675360 918349607 370826748 523771944 207616658 869666659 824460079 162216746 42145259 955515101 468788668 194497399 805759098 490056623 479739506 739842243 228839607 28031626 839996005 203056470 768799233 874861471 461598037 453246051 483592354 415113464 149066746 406376073 992400964 242745049 260818299 136642309 490065004 297763204 968347284 734036436 988807557 824423343 871336459 507008645 733612240 451372282 843394148 780228156 187991853 361039831 890237135 985120251 194995057 235183747 545092672 143725022 817548121 951527977 552753065 537399266 524777055 288359525 625461054 510506891 22022944 82932298 449481158 595386415 910717049 606841388 456072777 998090427 517576733 222981864 345133504 242517888 2287495 915165530 886542196 463096887 912556307 661704822 896492015 938777825 35456433 673422647 615082874 20734285 864643432 351822607 363569120 3595953 749982551 121098230 705067056 488855274 573211135 712643264 213182561 259056516 295032514 155389656 614736167 569256661 65558062 189322786 818571905 173289379 146595423 1752140 421444645 47601881 167379575 864761659 175515015 40886840 550533571 291649430 600706090 824057057 180161341 204421606 991910988 96531189 264696433 986713209 851771609 472575070 586149308 547784517 496607905 978698204 946328042 864110880 87474542 690524313 661127881 709479374 111889247 849947380 26572822 301960747 62944899 685707396 616177945 104636438 700850083 555855480 268571559 988525232 186877373 537492769 211016717 475896907 117684675 329190861 440013439 725083045 794852956 101151294 128043135 489392949 345007359 568071729 338370917 65128022 650396926 724459203 882238138 71570568 12700238 306770695 910483196 957714184 283817707 884400780 865324023 144651422 561702118 491557934 735076100 568097338 135029520 185471839 845763284 215767309 705643308 944409910 419805719 562448215 928652828 834908462 979584420 410760480 766417547 924030765 299987478 499843067 736754700 148675374 640058323 861303516 72807742 162072036 229161384 522270435 207528792 75382540 556239387 204361149 520886697 590514971 938049782 368700533 815466923 28446037 364739194 807952116 134832661 972171277 473122260 736271150 881995115 959393790 235396806 810617158 304684337 41038540 50972125 479102694 641536435 933587251 806028275 394269591 745232252 301017016 778080211 316368253 428190792 732453005 584080354 555111186 100148731 835577272 973581821 724322511 113802924 492896760 910850315 497533790 926487238 671776957 181662257 454746098 174922915 154541805 235480286 709826817 760535188 868217699 929986418 81196525 237996561 36265928 959462900 595135284 377674121 526050975 860183665 544340379 79859835 194258242 191411997 582917059 192256545 951211686 839695345 517781498 756247413 237398936 727647693 259228548 525506007 893954561 384672799 492819361 69576 164320378 3879413 210646561 627599087 59225206 732266413 688760746 907683181 170094222 397032030 914221841 967478028 389400059 486251834 647170290 173927744 50899053 607599539 994289203 991440607 959410662 169683003 562871684 684343334 232994814 271218789 997328395 194136771 795584699 501473194 633677281 412110500 911849918 936630384 350113028 923744952 692470956 461887312 108495087 107313872 619316925 579215013 728849751 105546143 968128377 145090286 319881524 720142942 925216377 452382490 731751427 584784477 695089621 449171991 446692555 284780363 171367980 953697376 366329073 933477202 451108423 870908767 368183145 957408356 164836136 748479853 813544765 619528366 351364964 658769904 715282459 544645418 978926849 208614636 919865355 932034466 714615977 570876880 232900909 732255447 140824328 739178977 734455343 826268266 493757505 997841638 627175399 558618351 347461029 356380376 134626105 248024837 898321532 688164198 39609440 412375442 342395308 991369302 205818611 147005167 383150214 904951232 251302057 372891836 237039886 948271493 425746582 446232815 29293325 129988478 68946842 664471961 86571690 215832760 917568594 126576745 964690870 931894888 826028145 287150047 791260957 894044721 413571498 849923362 964443219 234738501 56958025 297409149 52487676 293034527 826483647 711700223 238470409 535912034 948641747 581767328 125342781 768467995 190840249 194896626 717588956 955413816 633475956 390974078 507646168 673417674 745909487 398990108 609153031 479939941 466717377 852160285 459616360 542282931 226572689 403280786 997360468 692910539 457599768 872632163 994806521 477421708 380483370 878277493 379294948 820964597 986636317 390486792 297156449 828893366 948018303 151999836 88012992 652219037 637580349 302718132 695839895 95026291 839316376 80135044 173167790 145727253 668084475 511960718 903698159 705858287 196602724 610414828 509944939 399014818 454052161 639454284 722717002 531322835 952807369 799225073 474005533 631962292 742752992 32691809 340306497 572588547 888770343 28082723 763042816 75278615 210317146 734269523 407738046 228241178 422378810 732056167 462463607 956588418 179383994 388753973 493989928 455821955 725491566 66112158 464855800 349713852 207628152 630480159 766189233 924370454 459553557 891575880 356625584 376635491 101418850 65707152 54610725 685777779 46074430 93999881 274534689 825129316 636465665 57450781 770494597 403233534 24476138 426911929 804039568 245401604 882085088 1723772 574246802 384880637 905600481 570728827 521212206 446343635 877434597 422241712 153845265 647705838 514246899 378046280 217136549 383601628 370261557 216057532 830741406 572940529 520689581 508856614 977253047 174450398 446245859 762949561 579523770 429036499 349726862 474204347 873924050 524351755 230677794 522636657 447398707 688421075 980024538 815941092 276991248 504525324 845957410 352852300 497425961 569295082 977689791 220822888 538874489 977097555 816672056 888785259 183579401 674461558 216157365 978973445 522597332 152965417 148851941 259538425 890624151 586425328 871884091 76565112 564689702 291919536 734957641 709418614 614438166 609098893 684657323 972603632 919176960 836392002 869833690 235476647 881591731 884643676 775527530 532517057 209919760 92102934 94918576 585943358 951271463 336210869 942336894 135701872 566458989 125547248 789715311 529260827 854882492 41103793 446759239 101208463 183431795 238822795 488316005 549232170 349877574 519862782 744518418 727394009 28986151 396702843 577950164 525204800 187254472 435881180 146877656 553972634 235949729 983808032 439104287 818022835 805414582 727631873 301585872 504480804 682647249 143174162 883665821 83466916 691876790 849180102 349100769 578227311 323697145 282481575 883423796 415342785 987657033 24783375 404152827 653394626 953099044 880788673 766141081 82980790 841451691 645428730 590904522 136614721 470389165 74350148 443005496 168730286 664527897 366454939 993558882 402449696 811976336 871649113 567398645 170621228 575525968 568943324 614213518 692495932 469709304 818963819 119373845 90141596 569880448 38236401 894223721 891589072 56742475 912588285 645899967 144680981 128887181 130598077 703151789 893533469 159621255 736242136 335966721 104657440 263947688 813529109 174667064 706529064 38447956 239690579 746769095 782508893 497043676 454985231 202309083 20508470 396299448 942120886 565215549 788945093 218344182 651395152 631599027 667166397 519702732 597044303 402281749 841422326 980537218 491862776 168643523 984927014 75441434 712289912 777552783 34881151 790400747 674375164 686932334 729752951 337865495 606204476 406019363 805500420 788751653 93396767 749853034 196680929 62868984 962621593 572049057 871227693 342144986 179031887 417249593 844460532 828065616 82661944 161042340 61777974 816467556 103257708 535424251 338264288 801796019 824409450 80854998 558652860 621321248 285984346 568668596 375204177 813199609 571255092 916595130 73806556 668071886 496459459 875044346 21144112 904073114 600467180 885279199 965532939 908260447 988820429 193545104 928993428 200833768 222545125 465507279 460488364 371020920 369680020 702563093 152831663 552815726 728555246 624712416 306004099 751656787 32504660 82713189 144609729 395237004 594121459 600833872 748033621 836539589 175413582 334681970 413303359 352768165 229292902 360776134 730386761 655792046 660007229 338893519 156529845 229043656 533802843 54127285 263780277