12629 64358 48976309940773920
250999165 446035744 762737859 377804822 719108612 713367201 164436202 643186149 214257527 244586187 440085196 388270302 410034836 444156613 482179856 484105309 933259199 727212147 534331561 253158427 16106056 133276591 783930900 518803304 738883498 550781842 645370520 186395759 92996807 398245803 535758213 933024630 672526638 849312067 509441399 410787869 676776023 511107745 915192211 263189660 966425316 474110529 340589766 304317191 951225312 209114653 626781963 380571787 54991360 897683175 184885923 619457200 489781478 472629066 517493083 685381270 603271258 223692077 839844811 229205050 276157841 11634417 401044628 936964016 874934377 490057392 103469471 154385511 785131688 689341822 667289442 659645546 473997121 905366697 907553819 760027547 472843664 32023291 398980372 692707064 200082587 973028340 643592159 836001240 153580625 356743442 797637018 263529260 247175372 124838666 548422186 849707200 438610832 679124750 281184129 16003193 914632395 143910918 216873177 462597526 460566165 61272025 165103607 829318640 489721391 805276835 267528299 229745467 637510469 807317502 293201613 109961797 182728494 109960251 590050303 550343220 652673064 604845479 521783407 695702474 61760158 488530889 881663315 802319522 286077028 479849120 940149228 77198449 952566775 857360870 192776901 147507783 616255935 635812945 995977972 413827022 496861005 572406478 58848597 520767111 195836063 13008327 558322131 724964113 405538137 591058524 810017441 411915364 865490444 563966378 673016698 333866767 202148209 653876233 263882982 355858559 949658540 109902407 708274038 575917113 688511370 74810608 106078469 592225053 919214533 982478215 408225782 989021859 530940989 754875851 785027706 558537247 735749950 745256693 984157641 995732989 945489086 46084342 230739301 505339655 545474461 551508923 482867292 417580444 658565860 820348522 846146693 522313465 676526345 59366052 724989887 599278705 119155495 520594371 48663351 483783862 434538568 303768603 945974944 540604688 197658780 934821434 143019386 718708897 584794817 191975465 542452301 677355433 332588795 264191658 246939117 707259582 247591034 197234298 439555765 210446865 766382744 558439822 74006478 283568813 92191258 19118167 440719975 986977721 238676076 179245824 75692795 915917747 735661287 453191340 341665424 33478580 726401549 298651322 931214836 291079344 132000968 756208131 46905600 428294324 653219248 285013528 674122710 627558440 787263556 757859462 136292901 587645709 870137389 476423699 555819105 284403262 298311808 370080256 563074317 625406128 634345722 179087174 605230066 133943475 321347907 972317147 445040999 86749488 240127022 142253548 500268425 386454250 91492085 259684642 858112385 374109631 892305534 797862367 599044803 769066470 370790042 76159103 598525003 911377201 561271106 522585241 628908511 911042634 439656410 329018942 293217105 505278455 605522032 976400694 399859644 367488087 297122044 816777799 816980676 974917156 559169695 64257647 536272344 408935408 919055589 893795367 81623921 60633962 19405061 539766944 211823698 601132696 4635421 584712455 75814599 883920668 345099128 281768898 266227688 705693553 619096522 9584561 712939221 104559149 453677168 827379056 317700089 479789886 804244401 687604369 180708424 463230767 82830593 845977316 551432322 998115938 743190587 329823153 45637232 387909204 546076388 447086842 927341092 608066782 534784365 457610940 570729275 813629295 831162991 942791212 81273371 278851157 785829358 463491835 229447479 919350771 692451479 828646035 701143112 79509514 234654467 523195737 597207443 832913650 469733620 848574955 834240807 703011551 195576469 998843489 279336989 637857054 182254012 350090126 692879320 508621143 955931433 650423358 454686021 571103434 26220486 328574071 434131993 206133652 630856166 482809530 495952407 50724329 461132936 853432128 15713865 669788504 442489490 156436287 161756228 217648652 944610840 993106467 384176998 854279687 199842196 352385751 475145241 232179303 254485293 426999548 332252943 810081443 613447666 787748398 737203845 558644684 622440734 288752964 301647234 409334222 520326995 678731662 751836439 149505710 578875360 510068759 150005150 150476747 256939005 738947810 788792316 5796638 28299788 59843117 309535968 342771836 619220183 219840947 717661700 721550544 837827798 234140643 476452201 727576419 925581672 927727404 176099484 250405654 67662358 69899571 962923509 45791140 138161109 858671640 140570580 294240483 404461634 45092279 194556900 456270337 577979621 376432866 181641306 216731848 191396464 432027817 692152629 955977948 988896255 251937684 41053053 13149945 551080024 184155876 703871621 469494327 504152874 317243352 847799594 638119752 37156431 856299747 741524755 48906678 561670411 820677368 232697329 469495591 333658956 332550336 896738494 505222811 482109674 581479392 987596032 602888106 246422758 523165750 900944900 828539847 487183532 661922074 931186213 544928129 422264147 261536415 527372804 636834239 458469593 212852945 368801743 804322561 78823273 883686645 192107644 682699940 225440406 662808782 552922380 403974171 745527455 865910740 940757962 441813560 923014571 258031228 281444747 870258787 875770124 127970677 729830638 966029279 906420349 635962087 485688731 364081929 217372006 886867891 952930181 215228570 984766484 657759927 259824170 348566754 230865667 706825737 551485903 735458061 767443478 877725241 917270214 592742495 286834650 684170129 952628905 464268665 409980617 835191638 328627614 359900563 461112962 936200965 140851090 913674178 261460243 222497176 979279744 497073713 424778801 140270273 483949225 726708585 123050620 712126508 463807451 715317130 562364606 966380222 509105837 395549585 807845674 200097242 25632958 600457363 150921887 433738904 377578746 345341182 732594147 427730189 894987991 309036508 648942826 220682632 230570385 651858448 97646606 568865744 559605108 161965976 398027606 7156329 715243280 436927179 750646193 154798541 450428036 271038363 253052473 270464437 838665909 423301330 12579699 357338704 132236949 662916438 68724875 42445192 684399710 318310758 156854426 789331010 102365398 860598747 913567201 988461467 619552907 899904874 354419981 452489773 723763478 658399199 526204531 503828810 78602841 448245601 117061970 325325885 753614787 428187058 893081366 815598990 460614024 926709613 39150224 546803260 434288619 945163592 607155008 208874754 771853429 907727186 233405582 388813716 21330748 599783987 290529546 78205409 9383455 252382320 144296369 287992144 768815111 634086309 527152424 548504580 873131045 788025291 462801664 645132314 225119544 898335858 699668722 299076328 15088326 149544965 131462691 339205181 819195487 79841546 199969886 241114021 300990686 528794465 147091294 391934372 154304425 283624834 801848323 53979895 276491246 479055809 684191129 272349656 124657126 662567819 248383767 205842745 767746068 498769064 647555163 787574789 199558788 808701049 385025904 149365348 309558798 796394808 746627529 56600821 63618962 592295740 28624773 878647826 355786042 353445428 390573739 322336018 971872189 86410857 838050413 57323904 376037784 810250750 324995686 978999398 671291476 826447921 682716638 284775815 137095109 49932953 692254466 548240541 620015431 554925159 141234222 718448289 766946049 32202663 26339109 823979265 752212771 536769662 968857172 277900009 597161769 109109867 582632468 345781373 918121239 46275975 543560167 453573658 742691516 297741255 349660600 362972570 584880369 356087862 470387485 565782414 150158553 645527101 336535702 728390787 762202912 822021341 21353676 971931712 229168446 114261489 632101845 127799044 846138035 44958575 317962348 144094410 286306378 621269157 458524987 418676358 795639640 858444669 650907666 198490982 889824507 829180859 958403374 402382355 333753693 355120699 317288053 298616303 275421936 674271286 192503990 289613911 425524145 143762043 116151532 765669345 152403046 367719095 335540089 313862556 674790370 94558384 452502892 498582612 815692350 935744387 143607229 822148044 753596959 558107883 416202382 893966339 18708980 54891643 496505961 704103538 529669431 418742496 691190150 644779338 264993193 297167137 568610051 892660920 858879127 101919201 729048620 170176547 806455321 595592857 439726002 427949418 742862927 450629344 56713973 37955623 821199524 394766245 93919037 652916976 344704781 148042864 76347642 284875411 385944392 864260774 253561097 694457687 925394463 354022084 310711791 992435775 234579108 221173665 380348189 721800263 420468085 239298990 75065900 262692775 383474678 679540790 490679840 247206157 907147675 221204128 689148583 990176485 681433373 958647210 506811225 298696338 242363842 587820717 255517943 18241459 994680471 976959197 239094957 758408033 554839991 852352136 639898449 549314413 825898371 191196244 336816803 646659492 359948264 345527426 39613069 63304972 87431070 230683695 190789731 333720358 966138726 566881936 804920353 64312620 781164873 907117107 226199985 409105745 955275741 606500418 682009636 805274630 437566848 895613888 650761974 378344241 285245852 689800395 41618764 214485877 147526116 882693082 910095158 248223598 506789779 276761343 597597935 731117299 532592817 69185828 150161946 267553877 784933199 407753039 116186372 974110620 274803911 975921119 587293159 858643406 622097663 169618382 655656482 103026729 559423396 11713006 549865347 428978534 31810929 483846702 13262719 232202998 436177255 986544341 449568374 956642886 228468756 343835587 598508274 248269820 983432398 162579892 324518118 777824569 798289143 214132094 497718512 812924118 313620792 535937359 974976921 552860841 379186375 397256690 802270865 950651071 354349731 796826120 93263349 605139617 882422484 240601937 403335051 387198097 986939822 73105891 845859842 248748747 853295884 739164014 813799477 679305926 425065366 555263104 258637414 317335155 245419517 277124028 616060292 398105466 54545980 968322851 900311655 291232897 98833622 654038861 234108688 30310502 954175004 186087086 768012268 323858818 433476966 386997459 927124751 63383782 389496918 899810212 927252859 134988702 78524954 477230754 545186904 416572914 891961001 70533671 891456571 36447394 533030914 346668714 622157409 779174439 999544178 29458426 776378354 318215159 191109324 265554560 42414912 600392639 497014704 526481535 508860679 906837672 862708934 311911765 133453229 479000212 238640898 701787833 804621952 609046879 843849951 100575228 298052348 726204960 688810406 818038090 853671941 241039463 464912550 879445224 930943782 771803006 323415163 457111157 215246810 508261802 172838984 510512683 998182081 12492649 321882878 530615324 876473063 179349172 171688085 185419127 363480834 684377660 104080720 346779586 209175731 60284077 752384251 472113695 40609217 531557871 419064878 469858953 382732643 249708642 197855112 646104341 60769652 821889567 757980406 117919540 867019710 292989500 139148523 135522541 237301554 594987526 11025832 815622693 667015980 402860101 24619123 641441752 608449201 881369725 380222177 714562910 744064433 189842985 721425933 846820777 359609927 868127744 123777504 587406979 332939766 28652338 970110025 915975122 298575595 824787113 344945284 695582422 14713663 969645130 218029653 32764775 439104052 294840883 26299211 637349689 860871541 405188092 662799871 743661849 925934680 445149688 994832724 995514926 584806685 350099571 114427830 505203003 527658541 343465715 546430045 530306009 949048157 457362808 789521545 830268351 473863466 370002877 321659077 884972540 998032893 185132663 837981733 622284856 656048998 837382803 166772106 144772088 934310755 136130169 954102490 625311193 717379991 343745869 775767626 486196434 928021653 460082218 402374038 411969396 134440724 58581351 972974405 977397035 656646457 232182228 987321831 649980795 862418386 423554043 328411480 588986693 606606743 247426401 238996476 477763586 343208041 112997315 734100482 269126916 811152533 261845084 193019556 813248185 505659408 13927707 356759395 944334313 515819449 32566255 893149004 42110709 69750427 541120509 374096951 95259416 108064554 897968357 559395332 538477991 112968323 214502402 514664926 509988178 760252846 663757736 976488314 507167074 578504925 909581414 627447382 572097787 558209196 726574148 728096508 938476633 192961376 173416963 660815422 150376468 564574762 814174817 316159609 669354590 449001059 702987092 434853076 378216001 154196175 538708812 148281983 688208099 871822044 941343859 282125814 757408451 882699746 421216238 546691134 361057531 317190242 3445018 465993764 744395901 568715080 933125329 359376771 696785752 728460586 923271333 820250236 379145715 926633352 131474465 972380860 838598734 32610828 470201869 868448955 469986629 59664329 169611176 951714553 873774542 313706110 76960237 573791554 455072823 578904530 62970576 13151209 805095787 647412375 710461568 616142093 489276460 876259336 93912740 434578392 44582487 111970572 995082144 198870460 697239589 220729203 142784975 446059446 849231206 475033909 623852744 433892749 380687045 798163896 189169306 383361298 573444873 375852296 108080401 954851679 135108175 115521823 232137457 866152986 86242642 870915356 618802999 455418544 158879397 544376973 242182749 96109980 550082038 378357415 170099605 91534751 83297611 248055178 38364682 742776071 67343429 335653759 51587620 563505386 629742945 831268411 740441282 918165610 117362995 173050395 182580863 439769072 32911787 350326120 468918511 233941618 663426386 953474962 927149537 672869551 382628491 539604086 17152668 408059503 498075860 768190874 828862243 208304581 809687044 308507501 327551347 758082126 868756876 738565770 912084674 783172722 272542648 837871859 929086655 516800159 886565613 757585239 972396758 933605523 927342826 439931470 621228395 450126992 602296841 380605337 279786267 64219815 352185468 121754981 505978880 692015088 182443410 989869958 809827563 380096461 829184753 831956670 980268714 231994156 862431195 504660981 147553601 916920260 263823467 204120447 835517234 414587220 266329303 948187739 89052855 661774056 793856173 413308273 55729924 35396118 715272215 844283601 820322696 975919675 206782233 953265911 822733098 12218816 43991759 149466635 275743117 601067864 719417010 492848411 733682254 115268929 666492369 923561313 412804674 913532032 243516954 758059393 902192315 871732263 723996560 482781896 258797250 151658129 933568915 827602544 855521371 957966498 143626781 735972569 421858758 622521097 317488897 861947087 822401721 706252670 660535596 71530184 80185256 429578246 416409062 181563940 246576384 287609388 324246543 413812333 330373221 562046023 274116452 807389846 242310137 221880505 900082617 855653438 985718166 274072876 627967549 480784620 441923088 392566740 568266939 753578321 421703285 893408945 560393429 996954763 100538702 78614219 362518857 612703070 430027229 549780342 485691694 71639418 130557791 667450254 4960053 298651322 731811401 199442105 994478313 377504865 887083917 975996586 880213489 132366940 813423060 875757145 738978123 45694084 101091010 65175885 304245904 183791579 428603958 904206036 191490357 876786636 887820169 916406599 689579461 893720428 271492812 450158921 505836329 322452157 488204812 186653446 206932450 995196392 188265103 92826486 828193099 401934976 26716694 314058137 301228761 140580547 332763675 790022585 569835868 899359961 42161938 298619565 10410045 569983509 443497385 447598866 584972992 504516657 246821897 785585298 984396609 116415124 106200340 251536670 652671608 585945485 14246823 108715573 514695863 355228054 303666135 948488733 375934760 508209299 699442229 312385318 479468817 687564050 801680140 320188652 519315217 896177547 984805279 45086611 395622498 378319263 167868782 987879691 959065111 969640795 108852591 720425035 44120669 170451571 668350806 47783063 829960635 35094409 136384719 592711867 485346387 402203493 453731008 774127695 975218465 865952316 569646730 245741299 434851128 346153194 506572103 959097234 68308746 145328186 486042378 219228064 54118814 722073115 627891236 228443742 205377497 247323369 606850651 382894098 219869112 628626604 836355122 479456081 457520529 166283857 419789349 899351095 459903319 758583540 283056107 598589867 301171669 183426328 254225844 89226910 923574255 728687083 703403371 786002250 778665446 287345285 137247731 825369716 340988562 793712934 857519723 893390507 415355559 809966717 367334764 223124873 691162611 714027741 272431687 24870127 564309148 824828807 236031049 237016138 332969059 807155173 979891192 294245330 160320997 123654346 429632596 522468295 82940886 391893428 132648985 800052660 699558982 81941004 219007225 398244782 3627998 410919523 382611173 929324436 759276833 252680628 740939074 100753998 373568429 437612710 185176629 634675983 24200569 649187529 752307674 888939156 220437526 147798485 235200390 601417316 115397104 341699824 456147210 490190351 610859404 872277990 834690544 574558834 833697993 908810352 609244349 954170095 298029089 359866224 749070384 221499063 71377382 514301489 645954687 571102209 384989063 411791785 656938654 250179409 355677898 843623863 546214265 172766900 548155153 326835303 723598134 910908160 259606680 465803051 474313845 564569366 699541938 951434273 133507474 609237281 567728144 900136273 160366559 328664023 789490172 156438510 957329132 423895988 2042263 598444946 260830657 705898563 37591585 62502275 366539296 770478934 278869295 591608307 706236357 363832907 365983220 110228281 222764455 676719943 188305018 776495898 948071222 292865660 464851176 326489604 464943004 974753124 911191739 466314831 2460926 795064837 880543758 317278076 724077498 618196524 919673556 846425463 366585769 852723380 268765210 278804951 362044251 242745534 133728072 728378138 162163551 651777272 384558430 2248171 636799866 496493272 799561273 330016862 911618540 208389600 658019789 975516976 522875057 974928089 306183017 511993097 709759163 9338649 764355832 594265531 406575418 479431103 386400828 48859522 125854934 844023539 493031443 105000003 874547953 738296105 846448052 809730255 865349863 184121948 11643376 266568223 33614159 44186453 833991283 935338647 119736121 356430051 132587777 146982212 152939375 607715105 187568315 377817888 332899766 848416949 69325146 815984203 657193996 897360397 623590512 330294097 46047721 241868961 852446380 151675496 172971391 193745974 966130964 988484272 442647292 31242263 553760330 590975859 407272901 543324251 989805000 753105764 300743610 840995108 407952166 366990817 151832694 398923739 764088657 739732019 578263694 326451831 721418195 994234059 581756111 633463477 744489488 319488644 22549889 625981790 452283012 261530085 733752232 642987910 136850439 708541022 177282111 528608200 269797131 789331847 474578813 419705741 677839578 705389158 901960210 9144900 310081242 704187559 821699688 553984680 379195850 383724515 712267748 40343551 822797572 76690652 722116643 107058007 170093499 447941820 597535295 22060745 317152316 363558491 416903178 845403832 335962926 306780536 597331280 915223312 186609363 214311420 172310 471468169 94497351 402662716 567654111 721526754 865362621 646775093 959029219 568943400 431286983 797288912 801638487 858745071 282387341 905249309 252846762 346569621 298149393 710794137 672869059 174814339 948833395 951540586 906635590 170976109 255107369 558063519 379091150 195824527 167756356 338173042 885134641 859624687 281470127 141919111 500730561 531503008 222041969 702230828 903392647 267812602 291403495 247492505 886379656 746842852 458212877 568342575 218178306 364013325 913818548 637315771 571794860 601550892 137856458 63936177 913711099 107308869 685313687 611946610 683449177 61417700 718492156 783986824 695991406 366933089 755540147 125668071 654065753 562876187 710316436 154022444 792754677 113393599 295701195 668088031 981498134 394423169 787280164 734018738 114719691 340291935 635947330 260231105 220582300 311361379 169946337 30160849 847834826 434501599 610499609 974929811 212828563 485196976 168913563 177336800 790906221 428283516 327496947 493123835 383329351 327839222 281472454 507748820 910124493 856337687 706011923 697732929 426007715 960885860 543699828 731325765 293139366 67394092 494729051 962756683 879915824 845972937 747498583 269925481 108811859 186604764 266799694 644296351 564062234 527162002 399184066 773442071 103801549 881659107 209720335 181038436 848999723 705555919 207554728 193695685 873409455 918203041 210221662 929784929 710878157 605467950 479177627 624640905 184976179 183333652 375028897 753504251 244515594 59869949 56003789 974054939 792012085 21358555 287962584 364925241 52061583 674919979 491426065 544394447 741556014 852613428 96992934 45953474 661722020 231114823 564872922 691715998 541188666 267766782 414088013 681847260 205032756 173578622 64192570 302519070 917263634 878502839 900996529 722968175 647789514 358272160 977545443 858705540 510782481 328446077 864782164 940054783 49953937 92327195 889931304 317200296 158675761 939330320 892570456 493263796 868165714 727241981 635757819 817627904 470353422 713017549 808103040 537586005 428693881 417059573 458785776 896630691 222598626 725751220 811674414 906789703 859022352 566060626 335520056 570731335 453298566 168764514 87619429 93025682 258147777 143105793 182394022 624729666 340593526 911274006 281086151 506145499 113328599 504449938 856293292 264252811 678229964 582602415 27541142 858898538 165412156 548032307 268425054 155853497 276497475 911216299 372347318 158402084 466323579 88248242 459521645 565351426 104874549 898117929 159993513 91773585 25708478 357254526 920785196 33351228 383200413 785108967 821823888 128709335 144093393 549613478 693595021 914106590 149860884 798100292 254308400 379631291 259889436 398220247 723968803 413654527 289835735 418048574 525159402 944578214 153857964 708929633 336738081 8127061 847367870 612137075 288175552 36520861 638185258 552951858 274751065 12024119 884566853 236734499 156679254 935806279 882726880 611706584 857697597 909434010 227652998 332737067 747036653 129386986 578691514 637225602 956735968 952458006 928674364 25472523 195842665 555152492 367777346 365720062 39963125 533698018 601722304 160522720 204742988 512821846 306429090 695333052 362520782 965651666 732896271 272344169 904048567 720083915 846150565 564155081 942544733 21319263 521259713 363426053 71415407 912830357 404097974 417165011 790178869 352540062 596736274 747628978 433856980 210791192 596396766 790744619 456056713 833277510 458937820 49412367 730134506 248716891 391221961 759510205 617689386 729438894 416219546 687841882 72952404 265111045 153982656 775816984 670947980 82404300 567275110 937905010 260823635 886627676 568591791 126721131 836657346 121923895 814495226 877005012 743152331 864222279 276933664 182715525 346001020 50704676 726720946 813788577 932767293 133474125 466589757 581131732 75003407 362326123 735853703 451026326 446757068 141439891 785329105 522222950 145913708 997834370 475848468 72616721 268640316 846899936 172229190 177169642 764634150 339555711 616064404 880723217 293038061 605918619 597901991 607113903 59117935 311260698 178941921 453360949 726676195 645233355 296845727 912008098 333036570 169455528 658649462 751627708 366760384 863502869 18665335 19479891 747846810 817551904 761895788 759935363 67937992 108594113 128768026 289946096 180248833 756203545 175871104 33220105 657571291 692578484 844469524 655530567 771420930 153052361 200880906 831267692 461345405 780942966 984189326 780838855 200399854 558802438 319324934 615261804 898453456 947570477 918137427 688713854 94743225 962442311 54912014 110415975 591366295 506320798 351781837 848573724 964489205 88506019 105443165 621745499 41422132 462976306 337858566 717879021 421811156 697663184 202671052 371853286 543381418 897902062 926234795 837713378 871357993 528754469 17251288 454596424 701651867 281588856 606445316 905617544 311868519 90465431 159692697 502299486 610373194 731172376 99144700 23616526 536277919 909189822 739994315 907832999 956064409 828409012 694911007 467959363 869155974 502213584 735992009 635406403 195602699 964957906 786686357 179950484 274126700 410330788 521218187 39210990 386350530 8473497 864668715 335622417 884316740 962376879 983605934 600312328 434281089 99791055 510531914 74966119 117408418 965152266 40141164 324581775 548002474 309737179 636507644 782025191 926327735 161851753 249861790 526105122 707125056 312983747 772755181 858325629 92913238 622548004 148245952 96403966 160876261 525112366 319492199 847432120 748393202 523059760 377594861 713593348 371978204 869412706 591480405 418116039 9874332 347650086 969552862 312417713 619570182 588769606 278832704 658446713 262165000 96356666 150910958 974388515 594164968 133662049 514770259 860871228 506764168 879752004 39798295 111794458 435328419 243716056 306298970 107830814 458655502 378954938 391488501 642975987 442978042 471160178 263316413 720286158 855600430 588403378 936961729 628527789 573385550 712302998 76406153 121281690 96175129 146670820 34697047 438295783 157075620 860500043 611382119 959327346 150667682 565471141 236761648 112944352 966342301 601297974 440168097 404152290 231914811 143547884 828388711 919984244 33975931 356342943 403635236 345950235 972450807 986991952 921708214 70468644 962146082 925737323 595649143 106866922 221685897 782045702 804657529 236710670 7734036 617972002 250424776 684590270 763337027 968300775 231110314 250240752 922495602 145431785 150929375 297767077 758371351 687548263 786596578 766267433 171290369 548751496 823993383 15714383 57096856 120857502 812636765 761567158 353316385 772494436 658187692 209294344 124856313 232349250 900478709 496984376 196109527 750704517 511052566 759264961 414727436 631722665 235750949 819066091 569365443 269785489 105103538 563223047 472866371 236790986 890479367 510891951 330108202 994346190 972558441 661223945 838654385 72597820 933982294 39268099 371015404 813221410 321952710 245741973 230560009 341565237 855666795 37377284 447888525 709864725 333729267 111591451 421606300 355960460 96612162 620208241 393613616 776154573 198538171 471517095 110900318 158190518 481010294 380518057 261529494 234742032 263187848 760521962 910892513 180776396 184881984 278568874 382408227 911170629 166762341 373671729 170453080 615814786 734338683 818071058 35306712 203092338 749376253 238021227 687222676 358205999 321681569 725407009 842203480 26153790 698376601 861589286 511140617 828131787 22671822 790982325 127592166 633447663 122687013 343385234 458859465 894741739 895560123 841305420 842025061 207892588 902947114 726889595 994898567 18176967 814502340 947060228 508372054 362984507 217317588 311839570 473226644 841747764 964542690 553408156 563156700 957684611 29531373 743482916 546174180 645675176 564928944 369244020 670665658 114807307 532828895 996384416 514027529 980624444 740342377 237416840 504889938 345418296 617082293 994709268 870748725 356799652 334810854 326029432 147279783 538997009 507560473 312600175 562415163 459516216 838486180 405999746 295199324 904069181 567525975 128278080 68665998 664658926 21163707 637777541 893288114 380515843 749573207 373868725 121796416 117407581 670595048 740920319 145574028 977726792 5878693 24187548 921547779 889373883 390783619 691576078 944233837 420672916 479617900 573365604 266939946 366266334 62969992 388230770 663122039 254612236 516032630 671854875 145430696 847711549 41787281 657265545 839268973 803508856 583190317 111961712 118856207 815420911 91894488 626423888 928531889 915419965 355500443 916987058 691285137 912888233 388166457 237053800 722550854 907051363 254551405 962042318 998173185 544363204 50479917 533696013 692691918 157063567 732785643 176788052 594211793 312322612 749868239 636496415 67363723 735542025 793960448 605960562 71180565 504503185 523773402 256104989 4592225 853143479 913215543 475776247 358579326 572006161 642612136 707954979 693286098 226197535 181127355 439232336 162762847 857537930 521733940 785692915 777530112 184272231 972815701 870413709 117651115 88244340 979941144 20453864 776984750 211488087 871167857 927277403 875353331 9359332 570727822 973874435 879720766 132748885 650760216 341829386 112379499 650463889 951971442 71135714 584948658 142441319 55241206 945287048 556462053 428573650 936567101 598028995 221204142 37335092 551883605 663657059 143387091 627717532 954956042 555536004 239013492 971672834 934448671 680605642 132920393 235121800 89871508 564829861 369676005 402244792 531368415 294629004 615994616 652640714 809942068 307013443 924674950 659749596 469845952 358500375 694283570 608775482 622660583 993686302 326668152 905300373 30592139 131186297 246899180 999231821 866682694 153406867 528701309 757680042 293065899 634245728 605806006 21960988 955780491 355582113 228408313 774781568 919490092 466973469 977934532 503892571 221426577 245790439 265786605 502157854 99833527 274528924 182554855 4269922 913032659 383088547 610316285 913198891 784496022 93760365 787703188 931266855 681381995 348138164 635221098 771046126 211756981 15889597 625995739 905894721 775972627 29614232 840819992 808863052 215023518 592679004 761504879 483065317 408273191 591421037 550990472 173048012 993284475 373964472 276323236 389055467 483189664 255562739 279714014 872298134 687527703 493008607 573003115 329572553 105354522 899052423 253246939 908126830 649191900 496592512 312404823 849195670 17548750 463452713 525384931 737307325 195316950 996696042 841236123 509817352 692350359 968516470 216486647 452835463 580896941 232566282 823202824 750816885 542776815 245192110 26974907 63703925 40272302 399727216 220693523 435322324 429089778 620339630 358990448 461858764 921459137 568584010 973096652 869600444 494049370 278758645 882300409 412127346 321362035 386117478 243220454 430778979 278795136 885373858 694434521 176150255 270555373 745252916 836662964 765357727 240445792 412898419 337233971 639487337 664144890 216697792 824584745 440236008 659813268 694138055 132008648 961556645 867091460 39407291 774325975 797010259 829925719 847756955 258586363 707268620 352101142 396270706 173058289 464082583 172159363 104401040 112953551 315625891 483052762 373580499 475206216 914650122 933013139 293533155 227864550 628264977 997551260 19541615 645444176 14061220 838898848 621341298 253528451 272003740 503087428 88469618 522010651 87774202 362666854 730915517 189560969 383722795 795158879 514213547 938221659 616503363 230591552 873819617 186880377 302386756 455081238 846559114 353761123 976263254 976359463 81623453 155103862 669636878 499275315 277237276 95222566 423972777 325732278 291612240 96928579 40439119 306608674 329207824 207324982 723668562 500524327 398018296 547198274 627765614 577568749 978472372 811261637 458287881 133883478 57282356 948581750 692926065 71051326 895704055 248295078 258084642 734951612 728104258 982026881 703025151 939504992 581266023 282185036 214742678 820842357 29773313 824420518 296777823 138788158 940133684 533941448 473836027 229569850 856190703 862672839 368245366 119510881 328556843 800855246 20336262 351106662 689096234 469453671 37418443 858688244 814460859 421449905 572309007 751995123 798025330 960420008 444735110 362342083 387903730 440533857 501916428 607655037 194816804 128987212 143665003 880073527 882834815 305529203 431081108 626368062 525920832 407000759 719237603 826742874 678679216 919873304 667626589 54499087 934581859 78307307 919072754 100822488 989353589 285045283 807989437 988466540 487516364 642335626 744236097 704867067 379410267 145241094 941745323 530502512 925235546 627604695 553820692 88508077 483688592 306641877 835191230 249250003 195751564 752132275 858715476 481079162 466653157 464335424 511083564 989258994 992164222 823231907 984171141 797027210 128224198 498463644 30735563 443181255 33838065 38002120 265125584 818327721 519431490 245060571 790333714 824738539 11226179 790514404 973548538 628981826 247002633 998054030 764180248 223530907 594982770 69052507 799243370 685440350 664415336 192673001 42454931 70689967 142536988 693813551 948350245 945554089 244442957 685313470 113943514 506237859 679559553 501085185 614159316 726779501 679715912 110432127 733552098 794575249 869529982 550398230 794301116 724322452 560178568 356911679 746928195 592180532 155757715 846834766 606736580 449197737 4706265 73428401 12664884 727257829 939628253 107031854 947900786 137014742 812912299 650745127 544212873 396271265 109789979 357601495 731080941 190827238 196646413 819351443 261553851 111942656 151481004 184269323 885459451 781670979 443654829 276415368 826899679 897651774 949202318 171226413 423259651 168997369 886900697 429186873 780074924 840084533 832444000 190416961 250395403 671443376 906965888 128926327 487563129 350530144 203415136 866428135 442713530 985780405 879469617 214928054 87049532 115072217 689294189 220559972 655012695 656513521 199651097 174201096 834694283 432448858 229298693 684509592 848265671 542143470 58122760 229088288 238478238 71009087 553158470 974552327 456931217 455297240 70016364 59036751 540690762 52406145 627536624 929489620 630057436 139615353 365184083 82903433 147348742 380549307 874603360 163804864 984185455 860569660 6275692 185860960 514962664 658476328 633179541 708251694 792136623 887511850 863684613 512596231 640883112 669593762 502669103 84723745 197761699 329200622 762417678 184573775 659425947 617608356 848344682 535321404 811821811 278847187 653506580 909036716 12910520 331860039 359423014 439319488 231698147 578238404 816115269 129229616 399368598 774348872 827229153 614804880 946227548 477350475 196875633 183139469 148254059 751544063 374975418 497063471 257784803 572135313 319658246 913189399 303552781 462570088 198820463 705545407 835112606 360843363 135093523 131117759 592844531 197475357 705619806 789844483 204478549 534397226 556160069 341999383 31347764 926318425 720248455 43380318 187863661 158365169 218145260 857076564 238024838 784454389 453929095 464228305 752216302 29800546 883783670 428422982 580466240 142453614 711313054 568218111 317572734 230376904 596138737 234182753 406589015 507245276 554618537 421867563 957266019 666239758 236187660 290101174 545675875 871167227 491068712 558163255 501187204 763287229 89691925 225363449 396490394 298067750 183452984 680035750 45915495 117673729 178775164 212461437 895641043 139789909 914308248 934843802 244746290 431707043 848512845 630052402 163702659 457602853 70711207 709218517 712175789 22640143 415102777 585874861 158754755 655879120 362211171 994615483 141347134 705665871 478692493 37265183 913351495 315861551 78259563 649166414 835734764 895210509 934064184 755271003 705738087 279547326 797493245 768792112 917867355 273040532 922447817 721735379 426093080 881221528 876733943 802244260 396407509 989841102 395866477 862864795 832466419 507783286 290424025 314715020 173833278 537346118 221915124 778765156 637304364 216623795 553706176 613252202 340778781 816800807 964602059 926928257 815427227 636702281 923007596 643380322 633250713 814648634 260317699 123055844 237449654 813862612 438697274 32603702 544554105 945491947 190706247 991114785 293455507 464584589 723086633 742577224 725211426 659932739 470783721 298111849 672742634 862719824 466298073 103393434 556271515 620141550 176844757 858269326 134326544 758702230 325050758 170440912 218441868 748254262 71049627 771944709 876536316 435479930 530459408 177834540 176399673 540755973 954593129 996332510 497599301 707644342 764269045 249479055 468297611 244952038 603576589 174264781 850990880 676868774 674869587 980659070 216564742 161478659 241702646 528421156 534319718 201314628 161426666 411022362 429511123 777958951 590114866 264479189 252595339 86982697 642390296 565975845 732299958 601934269 651651696 820750195 436349351 322992017 241099483 474279939 46670104 253019598 244781567 329570609 978463344 325013846 859552209 632698293 594570750 756907782 949652429 729736672 105365564 788680435 613837369 419740895 792647950 938248111 271460200 126134773 14545666 318973826 958471923 24765378 510102672 455435698 757311231 416065920 721504601 980720574 143016827 449253441 966963562 629454492 413583200 547266100 12244087 702034432 136362481 162410464 504620834 276499350 358394 6712677 860126771 99522117 677187347 263558591 103816670 909460843 808951004 985604612 765831426 674483749 725112384 269246115 783342694 512659078 753198260 700675748 418733564 146666716 887522166 839509228 358198304 787672304 777246928 561936248 115640024 917048132 656450900 714398 10833682 532980820 685823263 709729873 432916458 977795543 240432408 50695516 882059747 166537214 647303727 909249187 202172971 121480881 842214560 388997735 313410521 892875990 279956271 691846016 702323504 37258635 649538156 82722978 176297179 167483241 132164078 928403866 966114609 442489793 864784281 767179408 724255088 904858080 146494170 404974405 31912706 169327180 381532647 793572435 688598205 880589830 103631105 882619506 152638492 718933959 721069491 351527343 685207177 422011205 950386194 848089779 289114261 302199917 38799356 191312388 552663355 947995304 439776347 866861373 201391394 966172696 735957601 590772822 924237274 20751065 615795403 134340320 768642843 483338818 85617440 586779975 209919499 629032995 979229937 275134992 895690870 845419527 418731288 187069210 576245781 855937137 490282746 421058271 603414986 916119584 626336199 886962097 15199456 480203084 838876598 257469695 132248140 767618280 567144780 939678863 377796592 91380704 172845203 386732995 113587157 18333274 310428260 411342550 889100654 321188086 725495200 228282910 839834841 9722384 519944304 716213577 655947806 988394234 638120330 811541153 122133104 509869380 97387885 454700106 163417961 305469430 163834273 548687745 636276303 806405842 928667129 724956 293994323 643545492 844709842 84778638 295639247 291919667 1024339 458597793 452920453 704509727 107608237 879488827 258080996 487935106 938207066 217760476 447624772 774183297 325739360 334368924 92035110 995759226 606368909 221277807 611882614 881508166 702532025 773645666 666772171 103707253 884399113 602524380 996496803 332149910 651142184 70814176 948055977 698468718 268750221 57910343 136062705 378996030 339638713 470478856 676571192 930155519 580239736 920060018 3536422 498024102 325927453 824258414 366214285 197654626 656589000 510101695 405682601 800249819 437013409 867853635 668714335 291230323 418612507 969636913 158680704 352920454 30355764 311809626 345438213 907612075 932678321 195416425 555096146 774418418 633820772 122606885 861900404 563487013 671525479 925489836 463687525 18938121 123142496 798797239 558463300 790694300 871377341 2941915 149701280 782498390 682488567 167876035 706142124 115316074 136423632 616271480 670305161 564397315 677600918 185973915 364162945 318064777 676802144 361970599 728774727 553022939 161878093 909885745 869652793 85351573 135534538 327814186 607436192 110624585 90090186 475040793 991141357 830532295 642032909 530124898 856064251 366800726 396451675 806547844 353655633 231208442 790739656 436151380 772514910 885654446 170322928 732046148 100876733 169509033 435643449 41078176 45341297 922330523 656200469 430411469 912792615 833418478 215806271 898113419 372440696 796907527 942289403 767757618 940611110 969261187 358655064 594721525 652731483 840905596 18577007 832395555 261040111 545425092 756208290 51404387 746216609 845612071 321424608 437784309 163226202 202579114 587663837 142943733 479952495 411819472 137139804 949370521 812801245 306442449 752811623 903477104 480762765 603306978 291643538 971209122 805578127 284826482 335805757 431413812 10198624 560417640 744505297 847920451 192935718 128070760 359039487 55116613 651259376 848403213 591483654 743620685 669864184 48322862 20983532 175661894 592794594 935880474 637636545 783130420 636298492 420737757 115245281 801151096 532618878 684064123 873755184 940209674 797924297 325432370 507565405 568273598 658511018 803502010 178406177 609814146 801883797 97761157 67971199 103733148 998308843 774586625 636880387 419511789 328239414 317901010 19842309 874130994 54346346 129621530 807065829 415066431 476477988 375624627 789998158 590745924 670961388 21812082 489788532 418260234 618955380 140599651 140254296 117398836 174389464 775056145 731586560 301545344 222600157 79502012 423130561 912026118 523358772 95196834 828895607 28743797 322450101 931110457 866093001 609791834 799196070 428325232 21895527 616384346 496848372 242461171 995820621 838682228 821140086 608760934 751483135 710700354 439996719 794315686 751726541 674522166 5877898 206297101 688951310 254765791 875833501 949593773 969622886 643408163 360734824 211948689 411287810 957914756 687574293 518306305 993449175 647066461 296187191 909655484 486143208 911074340 476380173 970108989 422351999 870932135 407383742 993236216 286284145 264946513 422805403 519542171 157402461 100985955 769706850 134695248 108741354 234633533 858735734 972250103 636308237 908733332 901892138 602099566 539349571 759549627 338914805 844508362 148101073 425128156 153038013 507861917 405231880 29291582 879540238 124394288 186132612 811707518 160621921 415741895 50516330 356380631 99754328 695590370 927596711 977954396 390353149 484046711 86118965 259061562 657656072 767234363 980240984 480130553 858525976 514559448 336629466 872119225 64816886 984072502 772473428 724163191 954513367 140342708 583057766 712399431 437656984 989156716 844198396 445903001 149448706 405139828 796409993 789778805 234333701 648982810 61075788 112936129 343243518 435027749 455781263 532654455 802666483 195879704 572910820 369571569 259129043 929678960 631556713 178608671 437869496 700428258 491620867 76481741 121408550 982787232 944973219 264192736 631965771 645799827 554883206 344329623 653401663 706290847 501059182 655175883 554981187 145514979 478470380 677254705 294944003 414646520 402413207 582698644 880528086 118044207 151358548 907647773 252465914 997982678 452781197 909351053 702348762 361113969 822765180 687453311 88810313 601831170 850498399 594489001 174872006 48046659 794872770 434136089 432473528 974076903 807154362 899065977 149098673 966878943 392647974 38350668 338011821 315480977 523725550 348934449 594077009 125442336 858506822 281844509 310292782 524434601 444537577 858247075 838861053 265613953 955971935 876057645 818213090 696683897 875053113 197672513 800834474 846372892 14358354 179089598 647772687 987657709 794289421 231583518 372918768 201081516 1509275 281024180 787020187 74379151 48097844 18486765 103229701 306064522 21801050 736508304 854795534 320626058 15117595 213363199 443568832 969772979 489981006 708317302 184201870 960850087 358957010 497345097 654304663 95559615 191611092 834627623 931650785 493549905 376831751 433548635 334326432 591817194 55485419 674793735 80852334 634320275 756225032 646892904 991045010 328895246 258793009 150971159 930053692 367780632 919232708 281059396 427890372 748246438 976594662 379169787 679174128 274559785 453316553 832334688 247608620 912127948 360166888 9651444 249684433 626046130 597447239 497677263 592044128 293111610 624829365 384731877 942782406 575015485 88867339 379064900 51013272 57903436 121168747 782824018 499180117 52270580 672900995 108165392 223505065 166500603 44799178 218375003 785026726 710140834 840542656 26337319 778157066 212703970 720263727 174435780 146839165 308529329 133976174 554113819 968751825 515235132 302169754 643170544 925491778 343442988 818651612 799383839 636003254 82157027 376368552 406535648 282030332 848580286 171140857 377625860 722860558 51170898 174663064 840617783 826047568 808734896 177566548 759957310 369311184 41154978 327753033 937178936 142966406 560367086 608088347 252448735 507648915 307899024 800544313 185084357 738148483 173323777 578497820 273852569 292862605 976167284 701255815 924372578 178804687 359957525 779337926 8902336 706909844 273496650 856789745 663842351 181135504 709119732 96194600 613612356 268661791 784736428 861681877 555745264 616283531 507675400 174185455 909982906 613613125 522910677 767662643 487512583 98374185 167487068 707197291 209125715 525263036 939896479 89446313 695364215 880506991 27670170 825229449 114556643 984249307 618824068 8050804 987119330 20020483 715559693 940605402 814308058 273969303 279249567 853497972 238249099 119103789 873027743 852089994 753726029 72960136 465016235 414751784 328392276 616186579 969007068 14127720 757346285 668220900 218569219 866237613 324518592 887686267 18968812 544360931 58099725 145388418 131422879 542677442 565399537 912812364 665175964 809814026 906068128 926237911 579038748 904547270 6183850 52894476 248114517 771339403 250103608 302236155 138911924 191687095 806261069 138058274 614811426 803127220 825330439 765354405 147540544 749070644 534340573 258655124 210908589 169469556 980994784 274566953 148728381 788679803 932707324 53794057 135372609 195066969 843576629 809946240 931920835 718907498 408904172 745458887 206458312 700999571 76021786 108341312 869274510 18508929 904295313 698575797 604146893 44329198 343045440 143231902 485561848 790223582 439361133 954010970 511038842 75324891 594091514 444388466 416647931 859554366 152930722 899523035 906790043 726653031 926763322 995966770 624430643 538345473 534924786 954477055 187782296 419668289 152033684 58512628 905937625 327756326 225656769 66141997 75707774 866780600 24455480 302871920 923874249 207763274 216012049 81465196 49646838 12650425 643691003 182311163 832668540 208463020 960200067 103749473 786958923 118248916 339842383 398215820 957570573 383572523 843074140 855882836 720618599 158743350 824972869 144864186 217699126 52916805 452909693 41502762 681989589 802512303 547947921 567080122 844670035 398215193 997901928 605307755 765974719 525269933 234235780 526663269 435454046 857661796 718100033 333813564 422380784 553305663 20440595 708664879 508079600 15938695 349829577 601564517 680657875 839938322 224639694 892474416 511395653 791950463 296308324 843229259 266794097 91823734 838643945 627341085 847441464 338687722 40042259 668743926 952737142 591148888 578730805 406588495 953087553 601293320 879049338 847398668 510473003 474446152 176861734 135503290 457828989 350205622 846502618 253582035 827839868 208587380 854926799 474728950 489935270 114740851 608605719 718467377 66115571 511195563 888400352 427443769 188441109 726623582 152157618 624619438 550316474 826600026 46115246 461772890 287019975 489932853 928516815 835665520 663549852 246676113 743316522 228256462 992097876 774405719 873633327 255322173 285175299 749900541 984464359 124592813 791604984 672459202 530465845 673028220 485747962 99250926 129184535 441699246 895391885 883053845 474620644 340501811 14800428 466660946 954546062 778295845 435046797 47623566 184490463 859986185 833708258 798611896 569148093 296947467 409249812 829029643 706405991 768316740 297815048 108884045 547708855 294322165 69807580 151369228 157616479 338761163 98268199 895863265 136404782 822721307 325878334 474819502 115665226 424270628 164521323 323973345 211649910 825028433 279947830 453990833 62954059 489359478 408578462 44884061 234486399 870012432 512916062 134075506 274883619 300605320 802936362 680816131 24667614 923085678 689302257 703451888 82702901 601282751 320541210 987118626 257402565 593098784 928410569 538128586 226121604 562270498 436384793 61182375 556349957 764288894 659261536 114923582 855581874 791304792 132820592 288817186 699180050 879433086 736802258 108086315 904097282 832872104 823868682 972488640 308915965 321223863 316109016 314108431 237104982 143829751 632681843 515357009 647340667 123474526 702972877 319708681 132353073 866091725 585611475 744955459 771662812 649383500 177958572 576014551 468478390 705122383 504047607 625318564 244160020 783081717 998837519 339223511 362249381 710963781 632859976 232532772 630184372 407058289 698035248 846753545 182945635 665608724 333067473 333584143 956374256 869783413 43361003 269551882 154501618 262623684 616286268 879833686 441211802 391406938 339154361 340827418 841708020 948944890 691376340 931919238 743377701 670839828 2017462 851242262 739934892 657614334 296519043 76815822 794097315 220935483 426097563 591073661 969150716 249612726 846104788 636259580 512336582 476596997 968973763 145335150 844798823 934159272 159839474 664337791 128952289 959728712 768421416 302036135 650444303 149930746 169898406 556906086 502807014 751886460 532577638 865115527 914502326 749248884 5580380 278987102 714209897 186069942 402825654 721518348 335539904 939135868 660057118 769543863 563885723 577559213 210217204 100748500 787668783 854358552 254279573 60150623 984368463 211921080 492671641 60821791 858359461 229097711 483395854 573630693 660351223 514976716 496681408 912320715 227631460 76321863 807680114 49006966 501317542 642990209 238740772 194685781 825376080 595422471 981678924 846956513 842443535 796369422 360529183 367866589 362516459 522634421 731026119 846579606 509187716 851178567 723591083 100635170 1243734 650447224 683946924 188804258 903654647 154791845 123010148 163736705 936823638 488351255 374366823 223281076 859992316 562556734 755990659 524555769 460459852 682603511 935938817 364758042 345636035 562348231 863940835 200938793 330889786 409051935 596813606 292410307 200167969 282539160 867848191 778554703 377711044 178272822 89436703 46447422 546489479 949677479 542004209 332249162 458880299 338542723 317719768 583792568 578234120 816252811 943950452 369911960 37380947 900354539 997922267 901893889 623779927 960104057 283772641 211893080 881498813 839143157 349795154 926012807 487329478 426653001 846303284 995659847 197318029 956139209 717070600 100410457 865054791 611239281 187837192 519346630 914717060 460593451 20557416 814207268 835202157 766639880 346186134 186125009 833424901 514397828 914842747 967146039 124704875 212541124 32819129 693379337 54764052 910697432 176372204 92783234 111214866 493977083 333726956 134229162 182908497 710474448 438213895 903327122 968200918 471734948 893096520 86160532 956684544 655939504 362434997 621881238 587751369 709165910 100341386 514661957 330145284 314939745 436744576 331120988 927895966 778111815 574328330 277793244 731416286 934551912 701397396 629666899 888716198 523091533 371403460 53893143 208564913 28933099 192186043 233808522 927566037 970542304 613524563 95954005 250184768 199556018 580665183 211665070 894047165 944921621 121198063 225490068 367813614 277471267 566552971 764261391 348952208 267923875 282414709 780278130 892305852 258058052 762202346 838757531 935386914 135379424 29785183 663888943 533996877 28213692 206557381 328977632 441638116 585061828 31360454 98616488 839026148 261747409 354480647 777373709 120918760 187117796 171375207 340101469 56325219 370776170 284684604 763903473 287697379 666442615 929654170 376954219 767222605 11450637 199403661 185854201 86660645 153110100 918734427 789119122 960191685 32010209 150005188 835183157 293930402 779150577 101785412 230803759 973907595 449278636 333496909 402911571 132860907 512651108 184408719 67754561 89869317 806092757 741306162 502970017 308161077 295979620 507647000 490783079 365638706 695025762 668521245 222160142 588907344 679898440 63118680 851412191 385063352 429175802 676130393 864497705 947067311 529164294 115217771 838706055 358842582 521446628 838102737 522930207 286446438 481965877 937368330 940721375 251602289 371858949 363829774 775240640 840779302 987753994 321049744 180478213 338025739 198568676 989906748 931453050 15003458 371920477 647081464 403023542 798883014 7066025 842728228 4110427 396029357 981256868 639580891 744433491 250576741 600025880 752866354 392113682 32338936 114653686 128610934 655663832 26230602 336006297 554820208 992932590 433892951 404546057 95640993 121952742 646616696 977027123 845949832 143875804 728137372 162467123 508124888 502451641 295115409 276187275 417056964 696345196 668915258 312992875 730767926 911646769 908914903 600983785 603919633 371172044 498953794 627802440 49711476 32844748 310846510 357769011 609897207 792634826 316372840 936306176 656195564 772991913 897726744 557512174 91156641 497075157 529592830 200601961 529993883 150096262 424014262 217438275 920374234 837301756 437119990 734502138 592813082 388422594 305588173 971163127 61813773 356276716 853663460 120461514 108612771 31280986 989920446 283231600 368261187 833504757 401532409 22122383 125614609 143266287 338294667 734486454 337203496 837255941 821494791 173114016 656717279 128299965 324649176 932537967 718005510 858073770 206133635 429859314 543030055 662921125 822166758 849063905 119005639 6375187 511724157 778475549 880809636 204565283 856818073 172922099 629465846 701115150 157590697 963802711 401156272 997347927 330482291 499701035 653565885 225441803 886636888 596821623 184636741 129302528 514859669 716464 623002855 393366039 539687806 909625075 288411134 888348027 455537860 307174472 937321695 242602464 319185326 622147297 725822486 217149127 371607392 919063898 359919534 700445879 455749656 575881720 932889192 750432899 945614957 975487980 80336640 224117384 182208657 142098575 437111660 937631213 255051662 990011045 286385694 346210274 63220874 190773660 159439679 742011107 712943108 165885643 88642036 732972533 78557974 647873717 684805531 833679845 392982707 684807750 544644364 818409613 798822120 519161362 503242201 1655825 490681372 869174682 509410192 909581339 101923921 944692872 416972533 22280484 468379746 252575215 128838474 36623788 584909637 53650830 979369354 799339390 624850761 41709836 640912295 214866159 974790998 779711802 983495632 936413214 446239281 929975638 350914991 400172083 164104119 9396292 31751076 212352673 776494622 188916692 55909389 468551781 625653561 549999617 980096128 706365766 93932466 529298478 627217677 43593493 151034960 144393832 258186622 206978284 687374641 797758120 296466071 243877489 422200078 258600464 958373208 801166097 926200955 943616555 849789496 235127623 232688933 684349999 139407977 602059220 331969300 899002427 645088537 432497926 119897576 767432859 546537644 366493171 681135134 967847169 225847300 970715580 48969802 613402059 127347131 516649165 233311324 789083970 287690597 672137241 51825885 641307862 883131089 383403103 742188592 576356452 383651142 280600937 210565075 315425650 325129928 166863178 64958365 439314543 164041041 323886493 508882687 798266357 894852634 253286090 667686981 57582601 391256274 286740290 535878100 557846359 742160098 108399296 643233131 922609784 866735793 351903111 580137316 96329517 451698396 97578408 165042161 654023074 95133562 698181691 107571297 257192366 840071520 263179938 468312666 450610703 503924056 4925387 627378462 194626481 600923498 742655340 639146696 330860261 398651925 663756615 114895758 467533995 706357139 493205605 710433022 186960874 133463322 421277277 569139010 802423988 932748312 918148235 687289438 22218629 545260916 599200603 621692270 189828227 299079889 921758077 653192683 198401724 716871116 681975088 387962085 460596076 397294907 282035065 402966599 469465398 421988461 911060842 352634391 133902696 394709614 986069854 671462325 930604858 846416193 269692472 730061081 856219917 589524262 845802665 601494038 686885805 722414548 476133481 209591708 601718160 873255357 834056059 164577519 387037206 949076814 259497323 932190963 379163337 375711789 375238288 667867489 83419804 194731131 699372876 170358288 329914670 381430290 636900681 523694127 811474950 240290758 287854779 658545542 921350101 40510117 560822178 35088314 56005049 539282745 318292742 764745608 109848182 937490626 466863675 824230407 536202172 465355901 337002013 322344936 118974310 256277730 170527826 394078391 954423990 84928735 396862092 883466776 74956188 190111520 565778886 669829388 599586798 879768904 788107652 139909420 742495407 889937719 181331221 679150570 507481417 518307395 956686034 343367125 106389204 826672768 337553758 452883923 243411791 610780666 914382565 50763877 596612836 829913080 130989663 436627176 96760613 119414841 420888779 70622417 362113107 202168375 510067318 992393454 867912851 505542760 792718388 198813353 989383993 317967225 278451363 289722693 943198719 813111187 655230316 454248736 36981835 80621465 959445635 352781042 528942702 739656805 7350116 527686922 990472930 721864719 82310230 468125333 759929225 660798248 888955817 473214168 709820146 113382904 380148473 216145523 30400405 46241734 883512938 914692253 924411155 505032206 511992299 856092780 233456505 408630729 394672246 862194700 778646139 869992618 344307531 856083460 17054395 307389021 862936378 17910903 11974401 156312009 128476120 3571294 656682369 813176908 185650373 33743568 314197786 456315651 468704494 149573691 700288147 186745345 547025351 436092842 394808286 817159572 282921102 259320319 682219351 832446341 580473741 277451575 907589380 594862678 132794198 554554795 493861331 261422723 509470726 853311307 632376032 287149508 313519748 809955042 301230766 324119623 663236544 831506263 537503851 150173687 481977334 956240103 554347310 747313081 601196523 209115246 983316794 784918188 240331308 112479901 735708986 918556518 207801427 5564738 553391493 920081723 764391491 480766085 863563097 482236791 309912937 859333158 110924320 576561312 916472315 320105666 942998192 329716151 11472442 294755085 17607812 750029173 697901489 971214615 468466438 917079952 52950645 320676745 289366215 50190837 776704612 733668582 476206274 644417037 630350440 783606476 450859422 893063162 788409267 604193586 364720875 859803096 37814019 6130090 994859617 565309182 881339869 416277150 65180966 154197308 7843794 867707540 791499014 855296029 779151294 814325099 164432826 371290660 44852486 11309468 804295716 410579984 738782935 554409852 152347535 704235033 844264812 486451831 878498544 112377650 571960134 52274260 448980009 51320903 65705587 548439669 464306499 127857022 461183433 828865813 68657585 501268855 273412649 85836425 352860561 680209038 252534206 321003138 224326891 508627989 921105725 46976839 862233841 435881372 986027813 681022205 302711104 803589163 730224382 996078304 163295003 401518468 504071835 508660873 353252020 178423139 495220570 583398695 833409637 724959935 68771680 338413256 103106032 963969288 648316639 847807887 622001604 204923753 21865809 718732028 572564537 297513477 983863995 424611113 995361488 960145723 162430701 649890825 448593269 833135331 967902911 462445226 470264255 49730960 98735443 700692081 60463660 323902413 293582167 71487586 424220519 215651682 497724993 415131222 164811652 710355087 320092563 263521348 37390144 206589261 325145110 794180987 452700995 281666193 853376288 468477411 409269087 838171530 890029008 409512770 101810640 498044128 389454414 177998450 497579643 913986037 819764494 118908077 635450417 222824997 213043211 547921603 662972907 717023751 541398541 873832544 537233932 842929323 375212005 459562825 556397476 706101467 2103214 685880989 910159274 135268956 183694860 115034645 813742142 882963244 380496237 952318789 612424174 903345347 349158732 837863643 875570416 402432852 940776299 159912413 133805154 522968330 700124438 584472813 766635918 781156173 369861732 442726790 945233706 98569725 50854775 765074749 768605329 299348147 141415352 847456002 714874125 840044548 998786846 904812638 717563151 863031487 947659109 673712309 638507378 497847596 172491097 585868419 415700669 483048524 367105546 782689952 835410015 482027293 714951703 603976062 787289075 16348629 135910629 622254183 95742076 311072036 757448167 882152641 612194215 926110068 842600917 898977611 75790093 184002602 126011382 710410079 580557679 487232740 807174488 633675824 882605050 469136570 432443924 780384267 550170499 645316478 652993165 965950871 440034762 696795902 358397615 538522391 507097272 106843711 770464562 239638436 771049378 879308481 529824469 134912629 539150981 400690111 30234021 522479640 352824138 994935149 344144437 213685176 26369793 87587386 559740645 435768407 267220263 610740237 218041118 120115730 485311714 518325642 645204114 794163042 728189505 527180620 713193086 398638679 207233406 741008682 207065832 944283613 94021693 739938675 587794402 270425848 114985676 8409651 463429319 858125321 841339747 407393902 889844603 28823048 139046243 506276706 909500845 816771017 753299608 902201287 637157399 189470009 932457593 778288911 957663161 522086048 836490084 137738920 85037347 516210655 283016164 544513334 231436201 456748465 456650733 466105820 839205038 543046891 42547740 482521458 784081628 389110717 948334841 802791885 233203048 526394096 966946358 818310907 364714320 174297383 192200174 61760134 650799262 804818464 976848361 239905454 309628324 387610610 175134420 376880049 268905022 125645903 498146187 26654469 94267669 61197760 452712529 303345305 789640409 958485229 636033556 678213657 283284868 189662164 796360619 683570729 143331739 21878543 172972313 777648551 157803373 148974865 748352201 49672938 989822547 187391334 307371217 426802439 464551920 836646904 568520753 549729544 544829809 797143110 609567763 76287797 822744780 689637548 811522314 257803853 562425346 292676511 643159125 999438027 309996126 732432112 202584858 772769315 603045301 914206982 78772653 587246083 145408421 717068838 257627848 368036757 358675672 831757228 480535250 769777849 765378624 839353169 326299931 204140365 272250458 295566949 768502555 526639718 961304173 818339603 9332664 283330454 994153418 335167905 955456126 454426662 711675147 4008879 746936038 652789850 82871125 198692213 503059346 115667122 418471831 686118151 485264780 535554853 397239243 592172434 672429452 429212773 233760818 512218782 267322161 22354207 728586906 627685707 344695364 242747194 324034457 378299798 580082170 582636309 52019664 883068307 454478384 459514059 531823402 325183153 961847983 123715439 639433244 854527739 48878183 55423058 254193381 664996947 493958837 727451194 943248077 353935799 791381151 822240426 507070311 442644606 524274708 236797215 600471504 250173337 510262574 449981007 571449839 295757012 729739121 339198313 981248949 105624084 847807243 194826073 583111260 490491544 512556564 896236034 715312042 460834361 981775821 868648836 604923692 555717291 553413602 177247093 677389181 724668604 203620778 916162090 588486526 132730258 302101347 677576685 141326237 769979375 710291832 82494021 836427536 756297582 234039228 460049715 924072216 58127812 129226414 964964977 65903169 497418753 975205557 988443827 614421918 141021647 702897507 944757479 58471439 478368943 617573044 608253814 439883644 683895104 798558797 480163714 638097944 294414458 713452223 378623016 535512480 642163436 361102531 169051069 705841820 719080963 786414716 455987475 874549147 47180100 644237498 194273970 890786424 254101391 997628467 421704737 420801945 720500316 494800586 731190044 496254763 932623614 555431626 535247068 611429481 740807140 19894825 925803861 196253397 561936341 741006279 902010993 922667387 382692145 206433454 188941655 633560626 589436213 956670289 756907944 490150107 715018036 150223 946989245 416027298 178301920 977352238 372127468 656808250 965324928 172848034 786449090 845186595 4771385 850998725 828447304 166515685 54848328 319185630 78688833 553986900 166229060 311469085 107468647 544393931 908108638 364830426 219261874 224511347 411827105 369654235 554423699 554486907 454417972 276136076 477108018 663219294 707987861 313443398 545174453 585676834 630766301 136466314 41076859 957804693 223780608 494019397 472641114 350018448 631956491 404413964 778153190 275169078 936256102 21606750 666291627 597079859 655005714 392440039 283362671 61575678 541762538 706796985 903505267 311112729 692408035 547286930 245151409 995307342 106468173 562293786 448321308 589744625 368902673 597736995 443568868 697467938 440295410 291647721 465978801 75123466 259186382 469318482 423943653 42454554 419688668 738980653 299596253 270954065 605213166 483085940 952566062 182261108 396996782 662050443 310733801 996228950 819857378 272964480 936776665 426312975 82865577 593883467 326162369 600981062 250455229 101398797 471950496 914069610 552467376 440166482 133699310 730150386 518137393 514198097 514961374 203467169 598998598 625894184 130507420 554017734 869496209 324900130 514058126 832607093 218244749 470163442 699070357 309357521 674572752 946568183 280155978 454306628 749941576 332296056 367612995 429568194 618972544 93528551 552439885 334368524 904158426 743336736 493412529 741214184 559356115 217076904 865647473 611542379 110731588 177373424 798208649 13723953 216131996 403514000 149669168 171107233 609700905 66524046 139759382 127490347 292591950 674230935 452879782 789549963 220534988 631257154 647107395 209428229 249229051 251197010 182733452 138113960 530731023 943310066 224215961 474632845 517477717 868476920 737605437 211762455 181319285 425669156 620536900 23844915 36120751 52801632 823929524 224258967 809922080 938955007 495837453 709347076 979641596 744819967 52777354 523038597 350186706 502222665 30741344 230192814 112604621 246014957 480897020 59058144 899599855 781017449 109484615 125368193 24620118 253194209 739245027 385088070 874905209 297238629 522958444 151082091 41020265 515003951 662233785 929821943 491982610 549451748 768005146 23492859 743429497 13767376 731317657 903532241 216906749 408334380 802987835 326311262 938083991 312336985 918100798 501374802 350134044 74976804 163195226 312482916 918919287 314138114 590201858 453120152 459624433 85921618 781993378 420731 215420523 552853920 130031071 190963554 705430944 698404830 414615772 228048561 4677990 947087274 749159537 615990544 429699819 221574796 507382644 823431861 718000121 71745846 209859313 570695582 625786932 139846852 950153587 859947733 162783832 912916988 913347643 105764268 964639613 573633677 905303685 872673536 822482005 681218129 864051400 726911608 682537066 521142412 910488052 753482181 389840738 381446956 308492979 465279457 890428989 909532681 339210922 965100626 214873747 717484068 719974327 483922533 744465879 255785193 888355122 605039221 300831896 672860526 436455725 688532771 773671357 590087604 355602870 223803549 889925574 135127522 573784082 153393113 426603024 238184335 941185537 403065816 203588110 380850423 441147134 867547877 234828946 277357634 784549246 438466005 549183236 957869250 125277229 311389511 800708263 977862194 864865590 280002275 10942936 37518329 494449018 864238236 501035344 726366823 581173205 526370800 398385503 342226421 378352733 177895204 876375345 420458631 408113060 702081674 13102090 559463594 801525235 765703612 528912523 238367959 912850063 804810464 760364012 957658800 620187894 2902500 899248961 509082688 129689632 503262656 540420280 872874813 610318784 935626681 303076055 741958215 105471873 384246937 289617343 792960552 792279627 695234042 949543021 436236563 204379005 877088634 658595830 82835942 677275186 299085830 436790983 285205866 413312638 551992081 586430957 915768719 351946928 193098715 541925960 474912435 811549327 23773356 849923031 91748569 816817311 441613847 921202417 334744820 371820891 473828922 450947976 341508635 422785146 794594810 69833830 286768852 109998635 736384073 292796016 49404491 612966490 978577250 17182696 524909977 676786155 378178568 186085284 552204031 527331836 40153292 262447706 550529834 856121637 815341894 890161622 572748910 952133304 312919897 609549375 292921357 465810434 977754737 463847255 634205551 454422410 739316421 780932025 374481257 35128399 859951767 465957403 259945848 348525324 543610224 123003020 281670916 973532021 196907367 897934772 972393120 973598585 481053785 698816536 747779398 359002239 625667887 748775252 986318748 269087403 307951389 748433249 526882611 288027672 660864222 136203215 854498244 276400668 569071099 867207945 563602035 503630473 382081027 130014101 535882510 360884968 332144082 109068115 172641101 979151293 76964556 901662395 850933265 444581832 924396576 49800225 714384550 263135552 35339271 619323634 260763138 204070679 328790275 787009270 420523014 109461562 906585890 878418830 203269306 304296656 864448827 866780404 165817234 632151928 569605678 899630463 816773805 15361677 991760934 878038750 159099410 425610083 879488983 529590618 790276338 772257160 525176257 696552726 962222315 904719366 93415277 866891088 891346241 454984349 56459948 102053279 928582181 77542667 558868701 584814388 651257328 541920837 177619494 718983195 467382885 758227389 810685623 585348729 618641396 154686620 273951244 236737485 692237043 243394822 312263209 384543792 694820581 176674139 238006493 489827735 633020853 272016753 798471425 624603405 409265401 14333405 558048696 708849659 862487345 523209001 63189935 953304930 589525766 226992412 62444635 652161821 857058957 185329143 134367039 654023970 141184132 956987828 995808037 438703295 562678673 886758215 977569122 867365854 943768968 738779102 63356692 202341443 87058595 542908963 639486565 662107338 994067145 429981046 752717767 40959148 57674953 457221941 960112951 685803704 294380445 981366773 530060668 786017947 508169642 987006151 343014758 808600091 948835324 972478070 628150033 718804565 363009932 363721926 838117665 544627972 665118843 497407412 248942598 688017339 345341782 727479482 628344631 52816679 312836690 360460297 833750648 477538895 854298254 389659086 656079637 364762582 397283157 430417263 554513190 416600885 595342171 877643469 1503947 438820867 625049597 77020034 884740975 987110191 338871939 553858082 91127559 700180033 702357856 701633915 528498514 125927070 398332269 741341654 912957208 964884163 524536627 866540597 629186924 175010695 93031456 783233429 661850859 112528731 553672142 86848043 706636028 186812298 316656449 63982760 139184911 775810427 613580327 985089911 514315744 802120684 585074199 536204795 630422196 644179510 573971412 831010772 943914648 574604685 932615306 364964376 357590439 244161599 144117517 87729819 366220354 936729842 214264606 607258921 641763927 119511015 414005415 964870857 734933660 488069179 362488571 324303609 579164114 749151011 373896217 575064310 674599428 409247533 959886824 590306035 744472007 383573891 726754170 97763166 531665274 793051432 253595722 940005920 636029061 315064890 225152384 145549787 853536923 4050224 10840873 45333804 275179257 963447324 358038401 764190184 334207398 332008424 425233451 213590112 939069107 218971034 324820340 781437087 142750586 844272529 692792213 981574056 906530273 927296711 616507888 80995514 605539734 651399182 497479248 473177741 303995217 492600661 423331371 475430036 437565463 706274019 859739105 849787963 626998386 318126232 955699707 13176361 305761212 430889264 408512110 385779068 228116307 121897857 662869976 91623697 404136931 145604025 27843775 938295482 875276449 80199843 278094551 573495432 415890060 837503200 513365562 625972224 983376812 725270576 159581359 809750375 253285461 577496233 784774373 652171513 844371554 675255291 414753206 46688299 672895611 835268788 940727143 551340782 254995793 971819895 16133348 386277612 373699295 977694789 924741382 59999947 266739113 242600886 239135694 760752487 269882365 499375166 823124905 642490137 762685238 97444202 122178731 104874228 135355638 689812770 783863766 371862020 574597225 526445799 9974354 175539855 856243590 842886931 456301236 745367381 728328271 101422621 84313657 665604818 287602701 178115540 231186441 906175096 955864726 534513825 26867830 815657464 141856649 450646215 460628540 102879863 20859279 755078052 832469952 369243098 632633241 969549039 943627347 262397949 451148326 265636345 647483758 373188085 633429115 828947694 366883829 645578067 250651626 889757715 416055670 655651169 492316942 170291463 529867625 963757668 898285835 822447108 197625967 442464474 356332240 846071580 18170772 176944315 948913238 262178174 488579982 801091258 114167775 856247472 274562045 22173059 998391609 75424212 558078635 148658940 223338747 489821413 660288715 595081093 420451269 970707448 480829500 623421754 439382401 594861694 724714181 123695917 63145638 229665918 435207000 265327790 181112177 681274845 786624848 966828677 549777195 845520279 419733428 476521012 618981224 733308164 204895860 316292407 225247556 174097174 686902185 824743493 717671077 200062871 265812694 629244558 149666686 57952877 806681643 866496764 39504135 380067032 386751934 728207732 9539847 488769712 812122834 564869652 468179212 872225705 774818578 196985972 661074863 781924496 94836179 210392807 433065427 387592332 1863511 97948088 553943525 156399200 268731399 706577007 882224410 485623717 871386038 937076492 969624757 710301202 173309154 379981128 776248640 687591606 366649844 700475352 2155984 217925433 455236732 213789099 401748291 208046368 65643639 34646825 41509250 792032520 137291147 862887795 18929345 731197416 566620231 908296615 221067964 938130513 246199142 587085851 748666362 952662447 57121546 105555359 22766859 952750982 910030850 669640381 741136843 661690039 404731142 498579706 556903070 968753851 617423351 582687764 370932148 9812708 308694306 917544771 424452676 165686688 989724795 797796986 63600082 665920951 725289188 300196260 25768298 715400586 468088165 716182505 864364772 338708052 95209587 684124904 113464864 443533162 633674027 302178812 467369545 286224252 78337173 197813626 207423764 689896403 141561571 407962095 504852991 441525651 464667825 112490339 458422164 528182008 183167044 921297050 946204325 142112410 326307021 754312271 600576911 679718059 93310373 772697208 917228921 345886773 538654608 904547207 72223124 543719518 575098364 630457765 475087962 637179813 344121920 932189175 128231632 423514916 46880991 507282907 767286725 428548557 612485316 643198505 79670547 621036975 175554694 986663539 989872347 540836145 153105315 892172871 969262795 377585235 218027974 809539177 334667609 740973553 84367874 778912796 899818246 395458817 569940502 576915544 83324829 91089361 124991400 325878034 473015155 519013196 913940876 989836409 601667750 971524148 236245245 331916852 481214560 214155878 438096608 581146278 861602835 680822811 633165061 481079340 49427133 582795555 122425191 256440412 287683619 1285161 137870185 140754246 634890262 757556212 164665624 297847476 530069427 249510049 191734381 43858794 693083804 462024427 66116234 332228200 427446850 213868901 810365690 912327205 645780252 59004349 882138355 807676371 299689454 754348536 159190164 823198368 416517381 212891066 666059817 115715312 58062199 325926781 822294884 946959269 510818918 734582230 479343267 413109593 905409083 328002229 445270575 943386016 561189868 699841699 73507704 811456073 562807864 634499587 831420507 510679195 34859751 100943955 513687646 365065370 168977420 515628906 103740400 31405633 411353413 815428281 38024107 686539462 105663223 225265804 123301268 878006747 960321428 685440840 193395799 530379497 187308246 699094188 536385677 471948884 900726019 529084178 27751415 182731964 102538280 471233196 114406593 464410680 804915040 781534921 617212098 228138906 148440077 802799887 920685752 704993711 41148187 955439296 195158927 343179390 98532929 26529783 760317848 495341702 93589312 464905449 279652307 391327234 526136612 607927591 213436711 745751590 180720000 14451416 629771174 667058272 719555508 145283073 837316556 749121433 665692712 42448830 21873599 434541940 222794128 485504392 314787469 623932811 548999719 415082094 719095154 285564599 794368757 652873310 5676305 248731206 630650635 72550747 178183864 804502340 364734148 234293445 483133855 86803893 828121348 216478870 717446182 978176982 776806522 478496417 89510684 637726561 51305695 608256467 710521588 259223751 802050101 266844532 902274831 359121525 217069066 455392356 456111351 530458130 55500981 112473696 785364895 438774204 210248853 612945212 969862822 693662032 463302999 944052263 182483858 688390561 932689198 212653804 814575895 605799358 332697114 153181485 83288144 113806382 353282340 419920808 672029186 861223988 78380445 259246452 293880797 819849997 632887396 102479170 603685308 893798190 577668895 732032157 355883745 504094600 39221118 811342124 121989948 80299206 871302780 442234349 988255395 480200843 959620511 909013113 913665049 141355191 791025718 48276037 411124488 816003232 850840727 563938780 587794056 340114011 529442152 941360679 397253784 844535794 830363860 774220199 530906977 591318188 278983635 847513015 143989880 957557834 740164453 320739788 898142235 381815877 716053973 401453750 684231280 405506835 701136375 348762078 701368522 732739938 195287659 594553480 288055014 67599193 456364762 310898960 484690471 699524571 80379702 714412078 966478047 973178308 619290364 902027828 509124488 60668204 631375474 322888268 150359556 476339361 513241067 531853756 202395874 35886190 760734975 203369763 832843930 117034969 548232662 681079739 21387981 611707486 437731420 890318999 155779976 706500854 395833227 236341732 222186111 674077013 619884198 372280361 301814355 389481253 515668089 74490248 533930447 989355853 260237980 524479741 152017188 39784750 16916143 150223259 565484850 972406753 934236573 957651412 944584896 455787900 142094043 139439279 380641216 240913484 197757351 32581905 460822670 999032858 669939787 286497527 605000495 634232168 589651289 697700023 19692692 733157043 995964142 886388292 145984982 435667888 245063152 85783145 743313785 928413840 368036690 701492234 133562027 352271677 173515085 175722344 793734787 58111133 918150310 953994075 341429572 971402188 151660013 360586391 289446809 726412131 325142713 729889002 403737048 322157237 960146670 576435321 377718594 568786190 207718904 253853960 870117182 748977396 890603023 539461425 512062627 243293544 182036339 33267625 821356268 521623843 760841136 816018560 954975619 918800859 685254872 475808351 556603641 345485181 218864845 537272777 257967177 83545458 964425846 488596572 263638554 730281436 738037510 940347919 665412603 423112919 902542138 686323315 327282599 993850298 418055321 668270580 823140929 378305109 364592308 692431639 843486614 418072115 248179301 970603963 16759135 220149207 299969297 93076058 994598014 103355392 779888104 226907462 909119037 135719142 24440609 438987758 725905300 748358012 358115648 157024280 196658786 994268334 186570322 886051110 912212656 150323874 499936557 281591124 482198515 923289081 1401010 725800181 589907529 970339084 399367437 461884858 801177528 230622513 719004913 699959789 818895731 191684597 725448925 239741871 670085399 156014688 432177243 770163264 571437031 211277878 468306750 116494133 938992149 879102770 500844257 265390017 694690810 179848267 599881068 892133358 204777307 340215537 708070160 793279971 994743460 466887759 108538183 524020509 219166766 780260488 893979671 353173431 315150202 73556475 64979790 183349156 485154932 891652224 526201284 144667121 319933107 674100394 128987806 297337862 651957429 560430341 202508422 649420003 106925861 993795414 315661558 666245733 603539991 517201888 942830444 608102528 486982216 203155099 357294260 736714371 233000544 270753917 573261348 161497689 872877105 489478323 815384280 914986948 970873846 474838501 426709244 963608994 630053783 808994167 37501696 48270122 524748258 748329668 772439266 397404973 450645968 571300963 590266218 521296727 769542087 934515556 369164135 152342892 514257620 696602769 779483892 14328461 240489966 34925487 154614967 514907763 346809656 830511804 353058078 740006064 664931645 373740848 243380642 526688243 28030516 943979326 990742533 904092482 781050683 884334353 991584149 37705534 589676956 316064273 759265897 416072548 435496973 991341086 589193376 722084169 635821545 211388113 741825959 285444571 555176570 566526655 27339633 214896292 350813233 697641143 626166718 328438536 51218921 678069505 534238550 890196355 52709929 815773854 318092109 193056493 336197216 859727500 207268414 298171320 672236585 675320065 362302866 633233198 334316166 824915117 394156216 973678261 226881831 542947322 759628396 44732684 834900898 376329293 427861490 149884813 434166457 469769028 233473625 440143211 233774489 28277239 136507834 961583859 419150615 923461688 336540791 835870412 412621555 9564629 946780286 751664952 184690454 670415315 594565254 38898003 755937493 883372978 837884239 845460560 927479853 507335341 576727267 810533569 789246215 753178360 145307609 919010765 599713907 967705858 649488526 314656889 608197102 226921139 475046507 570403554 756547230 876478636 703856932 523481983 958464658 983656843 896175093 543135329 630983684 480449830 992566501 241651827 90939544 231703501 760471556 722941628 860008604 519646602 906984622 539854745 76851272 418440033 336495815 366147590 206954237 217030802 60228606 339920596 338467975 538077652 417237772 829292017 528760413 21473434 307806964 664254885 855909597 926555215 179042882 713881041 619468434 920952731 845769806 832615727 927663472 270505885 742821496 252888215 246595092 111907632 125936491 945933877 283787526 686508584 311275611 170620117 70403576 21016724 499562056 814605594 262391557 629002747 358689595 189782720 483365877 566055584 185225606 791261663 774774133 478628032 285671686 985042984 762807905 329954769 99827298 184028711 191720188 917122499 571636810 466405505 497277492 777912384 163607226 578417461 996908256 277349356 412975158 646751965 814858499 554233255 628549902 921530859 724323592 522679240 333244057 758165486 312548101 480221537 910106235 750267596 259655162 325507455 530110944 739518983 890513169 143001193 801276096 134714875 760058077 502691550 425735963 213764891 268265117 669410649 611427900 342567736 836385655 1483086 387584504 774086332 442503615 256732268 780725229 641305577 345864751 911951834 394330309 912681500 62299438 656320891 87475570 836090125 658016268 746991916 646776945 210316814 802049601 740880387 988794121 490752330 387529395 454409615 83666571 495908101 170862318 237040412 462362001 246130399 673598059 427990766 547186496 912647443 275163596 78523778 131985544 31190961 843592731 355141330 579063648 634378730 946002448 705861519 765651980 836931906 13220170 284536422 163230297 423991005 125727634 304473918 25743581 329427636 817568797 253522550 365139001 308654302 266974408 441955881 806185048 549079242 500300123 801267563 777962415 419263105 105253065 893719946 233444989 590917606 600371820 139376975 465634826 899315703 755202378 981716029 90340329 351295499 735239508 330892238 237588791 221997331 925898916 668577467 287523803 298261211 106088636 204133426 699064262 126892871 50337227 447907103 135511090 159097240 487043048 97318757 875140325 622462375 51483223 342410020 221176685 15697702 645564609 749403634 493314658 692675300 432382077 703853092 888407720 1574407 647265228 365623300 465404076 210221904 30591254 947240729 255566756 532930140 862251567 479998308 708638418 683333344 791593878 901337759 646002879 408846314 88633266 549963134 946823297 508774180 399848469 799407855 756184823 143625234 759856827 852104539 189544969 589055312 102481225 533000676 924783594 229637078 85997648 768983975 866131544 36825142 517514377 550067961 766071768 45098458 723682327 184468652 693722364 421886024 983749578 686662472 994573214 376953439 377117784 245163092 496079908 629908377 937868196 830095244 997858492 156344137 101822969 452951594 642631839 421973980 31702861 520341023 72337231 435035674 868487808 761782104 603461594 866248291 607595676 204886779 130294294 312301043 634830868 841311401 893778405 463745568 192897031 198147004 921742960 210092953 575451003 961710215 800738670 412060582 13033124 784435099 756884571 134525804 938016796 581862142 315825603 927358248 127776810 622495091 321192054 350047600 532447741 766194614 967956691 314708599 916956912 489488318 861062655 822981448 224341445 750304764 457823020 430987015 594735596 677521560 296457941 730588213 310713019 863398073 632794622 290343915 222952628 516969915 511564150 673807643 757109956 372894839 403342614 469468627 36525952 651903616 664247040 144812667 720621671 174113122 691150050 563781396 957639973 41629667 488375603 776268920 499573451 122152772 162685042 890431391 847071002 686751359 513455724 172392150 178588599 981542791 83600244 528261383 373698933 712160909 402764714 97921781 392792464 366334263 523254839 536217726 34052334 263702504 694852237 784985049 277445470 98510076 837118376 124377815 805741274 27576330 908925265 128145956 549749958 283651874 558994775 819076741 487202608 152256015 797718742 20458521 839377936 521124244 545167730 81204122 9734279 573574320 716721306 474975131 634522145 693007835 545402567 459002825 567327765 581696584 871583420 681682987 561182337 308782883 437841093 335471203 494503856 850974930 117408762 764488428 444381525 792203318 121281914 876446300 828456911 696154600 68325810 867025569 882647909 323791742 156106646 148137029 415117705 502866629 247944676 297062828 521942551 716459782 111879270 978000467 816081556 744357443 324339501 105560080 667663729 368151672 590935512 26600534 905183558 829817564 928526029 221453679 721214489 488291103 695024252 903091138 125805207 386337964 338488481 105077004 756244311 928678886 929723776 637014952 770957340 943918956 709033769 861491657 643409681 15624534 874323635 106537149 176084492 914569335 910695298 814980649 746257869 775165851 663176322 763738961 923852605 701411528 75494251 917199438 974691506 965899902 115489789 265926999 996874535 525160697 486078787 161619451 823548806 70740331 845427410 876688483 123545567 82224452 417103880 831462546 770499248 521352044 478629711 158349734 702992925 936892293 818095961 773275926 448601910 864813355 990901859 980541427 877078325 496468277 239749492 343275561 79744703 386445043 123529628 869163965 531146016 778766703 300019511 348350990 346651025 33588398 563816234 385639189 427399283 722094318 398907938 785179814 664441491 948996583 192789465 794770863 241986662 88559116 911344210 259220342 549261643 184056265 680932634 778816733 26556622 20039364 537752199 857724831 120345568 591025437 548061434 148256657 511581730 176462511 58206238 350055908 945453337 883674703 348825640 612438111 482582904 864854794 995238167 926962854 916790875 812379496 540216306 25696120 199651976 207742125 663720975 447415274 502097326 921936404 900226120 387814063 180827047 880553492 240725573 753024849 476425655 984329629 393379766 250091894 73020364 561303385 612241304 993246749 893065661 766707437 746598253 346316000 174873229 589886007 291826822 402326322 660277672 177638543 94586170 872997280 172489762 643934216 203413037 941567250 124121084 589802157 258378124 728406536 324653408 486192070 269678669 409613278 336268770 203751698 785351026 470963210 662795711 591040013 355906372 933943131 951904031 638443817 502425241 377854777 309967699 668150038 248225296 872219369 535186969 979622395 796419409 303772872 651081941 605934780 457574479 480581005 507768280 669626932 754928775 574464905 121598875 611960442 978342464 768690151 432045057 1723933 774367691 289960942 755551642 332355434 939680963 927443516 619444444 880108450 431469387 579259402 408252778 223510598 484610388 688839788 166181199 60983373 659117014 846379920 603477569 918118762 343292435 799876603 904138976 567428936 532079321 855145425 51314678 979905743 75647934 781396492 495783862 285048158 298798692 308076481 968808702 802105360 425042356 908914016 845390487 39796985 143853860 66179058 736136817 174743656 621344755 392365659 733609706 669127205 26863721 430360727 318491141 850723505 172656922 274284798 587887797 416537738 590228513 29204353 836867089 802154342 393532007 5066476 46808223 843786612 905917147 396004388 772574091 192092832 686761400 870350184 951647726 179220430 135104452 135700370 136149513 316646428 995807117 16997717 552692873 876818466 924758700 763926654 456460738 195118898 285491459 716166452 813454070 984385690 313438720 637884217 385654669 2964702 808729562 369147688 238258268 930752768 981765328 396958135 951775968 482544058 480657007 732743924 141069441 554170561 88302282 188248458 596308946 754583553 208115137 358934010 874341836 992584933 345271356 6886372 609562392 685602189 607111535 908414781 424834372 517883927 735056918 569335192 399549962 354644952 757721527 274842464 111010446 291461794 493856740 934382873 470821534 601425918 457600888 733212836 450502642 280265329 230940631 104198265 591141739 924657848 767226416 296655084 110696533 155099917 166532284 82672490 107241894 805994081 957535230 104661947 221191998 61852578 534184450 850049343 526498087 104466164 828228511 477699635 644103893 954302713 173659575 712923371 377796197 799373835 647429748 498810647 111364063 26284926 175111818 23496960 402711156 183204577 592292474 620280521 48956354 597676347 486170570 494920624 20553485 389729359 986235471 323733324 744925318 768622042 41661797 696341198 262680197 28553426 326059314 358773314 12492496 540326054 41839081 718946764 550090708 911370882 496983810 517942509 215183336 408983689 851427973 486874046 543663759 231822619 270468670 689684017 129705908 8620047 399585543 910429525 260985581 987834871 475258371 449512592 180792506 984693600 676043742 779045092 952795588 705153041 53938192 727447596 930865184 628354632 393616409 172383325 95211148 514215938 152375492 717564616 29810094 879031858 709632357 688726868 134676826 887424007 340055325 603186118 234797002 264468008 241347602 476869882 120574181 520920568 851173561 658636840 887356282 262427860 121101582 513543714 319750275 770167121 582699992 771334802 644983397 261895809 200561127 336698686 918110252 949654828 585832791 700570438 500218065 255093529 31773389 609978978 450954869 916644420 805684406 965562405 598471589 319338023 368674956 459904318 390243478 719393011 240606738 28269748 679127655 161461973 122222741 673592615 778049123 965429555 344599595 196930068 892616510 932739566 360105205 859025679 129461845 727174816 348971614 231926023 830239472 191351261 776910427 155181447 906867073 396513395 855559850 85288945 866177252 294072491 839193109 352474307 611044255 843916167 918992302 667256019 868931361 957966340 718072850 477445780 641336580 525221975 301835944 106520913 515626060 766610226 165052129 929263727 317338791 866136829 636441463 772596908 561320364 111925535 432321967 440319332 206621214 190699828 94547609 425808840 852114217 279042645 104234572 579636774 785374625 877285974 145633580 590309158 140670279 331649793 856440102 700550409 706722309 204147549 464922864 513576170 536685358 270476011 307764555 119080958 862163649 827566308 540327491 551785173 491331749 722768254 971736171 274521240 906852332 288407846 135706658 409967691 608662033 940991429 581224146 369303050 440884796 534653437 689963053 83194957 890491002 46463595 403165553 935449381 281766663 234066660 129373347 688399742 800803717 572360633 445256661 281377373 156486212 945090293 89762401 281411618 623096698 438174107 404107308 601441732 736554634 599623402 334508774 676415001 795635519 808138651 182105415 597094669 114447119 331949343 605664337 780822247 976098394 279441635 219953298 830185353 886849961 708629389 600232800 916586415 375566065 1654333 135665180 976276012 59066064 357414351 794203506 925921074 824452556 154569750 716850325 827394952 234165145 497913120 764141701 818582483 66453073 965828726 76206410 254481360 617704379 371116122 57104695 67757461 358093446 308868872 22871594 838035669 281471884 116521975 602540232 753611290 811144466 790891287 28607427 396879371 148609028 318956563 476882197 779448485 72431419 834232718 121298244 503544452 6557368 298929255 301115550 671897625 574399207 831468278 949992060 24962802 349522399 370942030 684964992 268467959 754591903 542949243 495494104 346023336 787367504 729832131 419759738 717828450 392368007 749384423 307300968 678589081 913694593 722945120 54369515 964690717 169741670 241490084 114867674 588579671 116279688 850590048 108474066 344783754 835068579 622923196 969313916 956996884 997896988 658455452 11995595 516580780 170409540 861106396 622923581 396099235 837024660 472865937 623242776 493159973 546904048 873938508 678031276 1785975 594873574 709965143 18638996 216678712 843038190 734859255 195260406 346106017 768004008 353180330 738656448 361335495 396614435 812195688 579456235 310227669 268564242 850631908 17068218 895485013 252880662 961652682 640947193 301226086 481874169 797332992 833665855 802649860 886646766 233166310 577489198 728745028 989451220 824740760 162472368 559945110 40986738 354633256 165695801 951929604 862762682 490578662 590415369 638158959 22081031 495978650 933870441 515029207 373966688 993958086 664381674 389617041 447196341 932600038 859139499 148347792 172576799 308096433 857612690 712008350 743867169 245643863 679937679 58659489 851820011 350735810 488843230 708524249 547220627 265894359 523332931 627735838 10176604 988462260 135128653 444232483 58592496 60014065 216439189 108425655 769328039 711251425 646771710 49096705 194128064 526340303 339084276 197013697 30924965 785155651 807176879 847020948 674567465 67615805 147411823 520461358 503377610 744513654 621840574 336887198 650879985 490193827 16473523 585450895 798336046 142863027 342017835 991715203 980109694 500006414 580378384 701099544 610807175 49202390 446172564 776273477 28946648 957706791 733360756 293543067 13901867 547500631 672902710 596990597 613118373 210486840 695254893 803881866 38747666 999777875 841761778 881655432 956693035 669826093 900630570 77387512 553924049 8910212 580939844 166297646 725806929 271808400 909119353 464768664 16050335 716258372 669806924 692006140 907114653 228295563 987046090 256912828 679934547 93581965 299737033 331460626 201836598 252800233 295246378 956618582 680580451 303710715 916578584 933726261 722204386 363149845 169951815 742454265 825038053 550133191 157498680 386684357 6540296 424247576 892970609 306244056 115225232 604386508 808215751 828885191 437818286 146505630 221823639 884295876 130221243 462219653 133746949 51312859 856817275 184670448 703103813 663051825 816515676 385883659 921076688 365765958 567754165 132382202 221780395 385367857 211289353 213235739 813236134 213754088 462669123 945922886 424303512 357752439 718693114 877900557 344197541 26508869 185626028 171818750 436799354 706411092 2235140 604399070 699201421 512166784 41092117 408636653 40554591 668662460 834777758 586234662 763630523 114885722 724901445 570245757 52747254 732241729 915094494 993112865 824384815 435033654 835024036 502961849 691469454 764962582 822477180 791764393 686874502 664555543 960439862 610875980 397815060 761292044 18241741 256606776 729061119 734086304 670551204 578446719 513184024 442520471 795442120 11373034 921056889 378604562 197206066 887520318 290534600 715446985 817101060 942167928 779636594 630995536 787911113 922823698 720783090 616813140 669497782 253681981 711099401 522728669 624802541 852308007 747644165 44945804 532652983 537617716 405771516 144493787 171147719 873103687 689188111 346585442 912384379 882393848 466519465 736861453 548811548 4259804 619478464 639952488 214812698 172131777 334287376 136081878 341975634 387244017 65579108 40489683 290371914 961401964 263313615 715472695 878200177 52644144 628890348 168450163 388248417 177736562 840879907 303077075 817103135 447358692 264737253 546534076 302054231 284950255 678673132 284780525 584432290 691947511 742356094 193620671 521774273 108262556 556165801 454572903 8675808 278721781 994549382 24372016 664750550 523930068 225431415 997314500 300658017 876791302 767890026 871810146 718646636 586588562 411411733 428475686 310329931 185798903 71795514 813104709 706232059 517753968 639988194 806583631 985247844 366800177 87332003 833266798 548749976 317387944 256841948 369780643 858203155 575107518 408050421 816330254 480331002 72096790 517308834 462178084 170114654 357719883 158549278 949729272 125033848 489480755 178549362 166050420 303710956 811744799 457452717 335082142 540975112 666611226 752570922 305684438 867699715 213780520 52729295 818988564 975657792 127801478 719068746 626331948 618625163 248434414 384605524 344071179 186560600 846254545 403694832 676321272 731009032 345808284 460728490 52081622 164906277 180266998 243523289 341067102 39200930 303508222 436281823 906673767 844365342 16120974 95680357 78498848 328321311 942310780 249750434 682251858 410768985 471547606 676604051 100300448 521073895 673749283 865442625 626170824 577612686 105645478 544081664 862963936 560986110 104373660 395204267 461513371 559610898 916901754 975944683 98941060 167646476 472033841 226878575 981301824 741613276 664313964 477323571 188119758 831017304 847087567 303224251 505546695 45457282 208664631 376469334 212815519 275438791 695385853 580249693 228639204 335922748 424076853 931700083 52614268 962799585 283493865 32160964 662145257 310612959 737946464 37138759 267870342 196407243 754151003 486245374 438302920 545494499 631166036 707486515 13650047 377159245 76222398 916030907 444632852 719490652 730921802 774725172 689442763 207577037 686668574 83099207 971606272 394692099 826539549 318104040 736441195 343888208 21186851 113917075 825152349 632471598 170346056 107347599 313252867 441663615 146120730 522810924 315459744 181603538 499530469 842334982 386800596 260820895 739438060 880530241 329456345 155103879 639708334 848575180 707378369 710528918 930668068 999464096 299341243 383581315 318912511 787222528 762236494 348642284 939006956 851324857 144324762 926828701 703586513 211495264 623565211 887676615 908082703 828726936 786381927 61539658 926252223 149741643 217977708 894265581 243925751 374756334 455069109 818387362 288832260 410628799 572803108 820346309 250324655 335335176 836509367 283235675 389524602 263477083 333901764 50646357 104092386 40334293 191419198 799670476 113699228 581890909 237529072 978741316 590926041 697748195 122547902 562320619 136302724 513707171 124973033 114638296 187341184 210134370 241224265 248942926 350256876 316384173 687521426 963848696 560721248 923621150 494036113 703092780 590759471 983472024 662971502 850916650 728220837 172874888 144085994 660581980 54090056 728876580 73570719 283581589 378052377 701109933 699238469 138116436 444505297 649732526 403659240 197673984 231695910 683650876 782488372 823429931 791886085 705945909 15634092 879059920 967951063 319367811 494108140 385478806 539487678 411231832 643692780 707734284 421878742 983134065 702602557 734803693 288479350 685043029 997076811 226365276 470411631 427970453 205164443 736465446 656346185 858367243 26142220 218549508 57291658 94244637 163228440 321509592 595989488 945093368 910158097 667655404 885031859 254509783 507736934 422477880 442252230 457033531 7937501 55284891 371098901 868402226 74733528 834003486 607510470 563450514 859507602 870029878 194236026 135952700 161580385 420175617 26058634 140479579 831929075 54980741 366705740 863650980 529942162 167173109 233598541 243992214 993597538 977294573 889966229 559382969 387738016 903679155 145341672 179703264 875460066 745988982 901492994 904095336 395853403 232832912 618552792 583631737 472328981 350757062 32429787 808328513 462210614 358345092 396425525 230776126 36247870 733078562 178948875 454506354 469442629 786264100 647086779 806684590 117804351 958484851 904853533 814600906 480071481 848690087 474148292 502059496 296213402 200911166 340607036 713143222 509903717 932678371 697641291 9065898 433184883 485261994 998717745 434344773 955560635 274486608 747484137 6465875 562606988 397374333 419552360 315156263 669549775 519767811 317446107 213512161 322675783 249789469 287979242 135694761 151546066 143758515 180879609 748470514 806698919 553734034 83083619 334214586 856000407 534384566 278149823 218303686 52447821 24712578 248358429 139396328 214353296 275068420 685455943 888735803 20746366 798067251 676691714 164962658 27228880 862402610 504243788 424696014 76739611 581045388 893995933 680451575 186817802 911531895 244066600 672520351 167147686 491204116 659179801 325134357 928130448 511729578 318170325 272225901 79289155 386840815 962460223 7905225 646836564 15407937 84775151 939192213 751694004 356633063 916983162 159584196 902162154 621235538 640937647 870737942 497747290 75312736 870359254 921127252 789357186 485269909 21684464 322605199 133070650 409842273 439504892 123200614 517664753 549260895 668199981 544290878 726072308 796337297 368073782 799595401 418908328 448445607 511561344 704473346 300068557 27805751 740477552 534448621 845633979 236300291 638030756 127961433 284668069 828058936 487998772 717685599 597822426 505410731 996810483 633240674 534788609 798942748 206927532 834119758 635020634 17414004 555775847 49245146 158134529 174923272 28740771 290070984 679836204 844728277 186908571 986911266 20517738 426124483 415457924 941550460 436572643 670538725 943569354 97717814 781074588 124822197 816563544 507984825 10546610 197102681 671995854 778231223 114439579 891634914 78773194 473392492 25367658 584913546 809511202 511988961 422596874 648947955 167905318 236936229 273700991 973022828 72528096 623687316 398704426 200342317 371981396 190766098 861378563 148835991 621306306 742865486 581357534 805195382 409182689 101045249 191299753 636028481 324647460 211892782 288767146 486500438 704750070 961411425 826134978 983654208 816993279 287794930 651530414 797625587 453814110 456218689 295414850 662852620 381862638 995598329 663837358 53092627 742325379 265390927 817682619 106640826 200517676 327914305 11641100 658785308 149228400 732622808 116198239 522547713 89486483 731087720 734023115 489629206 853576144 69193677 457451522 527778103 501233821 21794222 602475150 791170471 733679340 889344444 153551381 329719380 659636838 814563824 813116566 915913749 637069743 806830802 936966826 803291373 430646183 239790766 705185478 205354311 588208805 156389598 926334582 259434297 586095547 835448581 108152737 16073667 395704823 995061328 930526153 646786063 270349213 63546549 456745801 884360368 405567855 459088949 690005143 38769381 247849447 919007771 371061633 944881620 893964921 914185787 610815090 133763025 691612372 701245494 172107179 271334806 466751519 798103219 724841612 204554122 281214525 988797093 798176970 741558525 508439307 703184009 501799352 87873383 149712287 660041638 354745728 878191534 630346120 47747404 965109865 800505182 885282322 737845783 910567952 136511984 393864065 130071340 847633072 268287493 305321042 556287352 281457756 849737898 612991103 656441078 897956929 258770068 211870905 814628839 206019047 378669411 609017262 413713944 369614446 911006944 274185538 719396385 520052179 144697920 614764503 313235619 882946602 854924128 86947207 554611079 524732131 253416968 242318182 48349507 241177606 543867691 37036738 341755925 43884921 465986595 343249508 607598919 830813750 591882742 731447759 413951596 823925655 911891093 780197501 21095583 235045516 925290010 191790375 626862536 443343585 695796231 928776443 589752792 898954363 926626955 401245925 951926793 609803929 245342141 819093705 402311712 871645460 618583265 437702340 813119405 765672353 372641696 946525296 582330696 411320075 635395921 250069534 582544339 567675003 600533045 628096539 50685372 638144178 14337716 617836013 359910457 641541451 893622946 270923669 435208331 628735996 411113598 827760845 125272894 714005459 556335791 580514377 638451045 612032634 382620359 984890103 416388575 157180276 861075138 595341632 62399638 136500064 286239301 228255815 664570301 956619059 452315617 436841766 354773263 890489215 836797006 218630198 125941012 360943025 404967346 523759685 270876253 330677580 243860186 474003423 356011205 802784048 452462205 815584903 999440048 424292567 847049854 806632956 289437260 252856212 259824424 937869175 724102868 724006868 216275569 593787113 181474761 522139742 257107769 55847999 245238841 191714196 618206858 530347167 971720699 91036850 134340311 387634602 653369582 635057420 921875775 289946298 888793663 740428625 69334728 214303779 785680289 272885452 474646438 601903219 419434132 67500703 435859059 9460147 786552736 41540359 75337078 169457829 799122841 755921565 437507038 642831877 377659610 351375761 470005510 76183499 728044172 236823279 868444080 473709157 659177438 777707483 600030028 663833598 435399499 332590806 730105136 207629244 867860441 685091576 998690782 884402427 921740886 447808309 858392131 238669460 686013595 139036571 988066548 328490010 670081739 19537552 295518064 432157465 433298578 539784725 887996771 398750808 464221287 396341511 83531742 122813717 478787276 631554138 106517666 839971405 576620938 774829662 922267476 537365491 451895032 234093052 473951431 629847093 58212147 331304440 611067447 716953788 183375716 142754350 808854154 513350634 10207999 399398102 502708111 516328475 57372416 349963713 807202112 81648358 489158957 215804827 531198209 896544347 949391705 773281065 876706528 540831301 472262812 157098634 220578005 362099559 392098461 948857976 230099969 769603776 136840394 99016069 703356912 666658505 463687580 21050208 818062296 385516723 89543126 748824591 559826394 751206314 618546628 966895413 894164542 827111959 847957630 371474251 987060920 452541143 55686948 234898663 52887975 439000711 443583521 279493114 53177682 443315385 333117545 701638923 161240875 952386877 146283708 814893695 675627790 951524187 403849955 836629970 545122944 82396949 761519344 436117725 484084209 183856231 892086400 106030352 133056508 764202120 714296825 474434742 902007972 82212648 726734798 954179125 172798615 342927794 387641272 409595213 577130604 492138121 257134588 826278998 772650470 467473996 622439081 151027076 103145776 306125587 648114392 329508900 341312544 661377969 492198892 274478558 839193974 610897650 233250002 948506098 439244315 278867164 523594559 363938429 792713829 131579887 261512950 508970419 927021903 437102183 826219777 515751204 650708931 875406710 891327221 601293561 932272593 253989516 753973808 609811765 235101175 670341777 152601884 764402934 713016920 802142503 141584491 987980211 412038151 390122474 21891674 355107453 297296443 49072561 707741680 433610559 652080026 897165772 728448062 821861376 81538928 485055301 795697054 25989662 790957814 817880097 811934453 742466963 453232269 147639966 51774194 653067825 886015746 776960116 269906255 923068135 264721610 182999062 281733645 451452155 43324228 315587056 35239097 989572431 659038204 454187432 741715883 969161630 905651683 750298462 772478787 71419325 86072986 466869997 455093549 555650268 172273574 676470058 246785947 37250756 904010170 324984098 382241423 542693657 633891314 65469789 780432656 713143959 58570004 718974751 560539249 392740439 273441486 962745763 988079503 869629192 179712253 394913632 593959953 973463607 709905634 352889158 826502056 814385034 461752940 7172095 147458382 256922622 857161586 217695536 44620937 393336110 809443575 845821623 964779174 286969997 233834599 952924140 708326912 631496360 256428246 231538914 472018744 112633446 372500037 474738084 966475388 157744201 884263646 685416826 343281346 432026541 515856949 231650852 783688971 419128326 859373191 366286107 218598818 964892195 116075003 311704788 11132764 474625391 278086117 303625726 238090968 366801708 229216768 11889344 930765246 526636984 543394225 828974590 799861761 704821193 295397705 666714771 462301983 74843058 531469121 316392598 846690141 767859358 364401532 898292887 920056077 166068689 447743114 53300960 47654345 857042412 592715489 944202421 625429943 955967016 851822116 461255574 52532932 950695831 76423262 679924858 563416043 201198183 514745157 731050260 43111021 401086752 135548281 944612623 895767832 7800291 444961219 100055379 915421059 371101611 754613849 401965375 302626125 264973197 755374614 367310318 597152098 959725049 841331652 84248437 361837880 452520952 728365907 128639520 595089931 87488109 957656864 756533178 693179431 942582614 487737649 761543875 460121628 849944330 562249334 9892281 858374153 949897083 90298375 116019282 686230739 787469683 765312617 791802558 533703532 334630360 895464651 6645479 129098766 523306217 426562627 342539185 766784383 748200320 755414291 156652604 239379533 717418063 293978600 125510943 511544337 274495269 403994902 821527980 778732205 46560296 302963167 138737457 956695952 293828891 434985387 737799730 91700974 306567319 673513295 149408690 491592970 340381010 337606728 475502697 539835757 361504093 367412734 197371404 186833965 99771231 234728707 341093001 225301801 476564445 257051219 184182090 730586442 691496052 505806484 967995503 529099201 874659098 568701269 837151766 471499085 411295074 757313104 141891989 965121396 585318326 26352809 840720059 705412550 856332445 108739630 14436628 669011230 181412852 482421399 119407908 411474146 383267894 421936325 360140200 773198400 983372726 839043076 716178138 495852913 404439522 972988234 715627435 446917368 691836031 850034295 863534345 670265569 686813937 444997013 93465368 454373380 246001009 203122712 79746682 80816449 400218199 715288093 761661321 193557698 37252431 325729707 946698649 808269630 574128805 274192886 239713337 536251698 812348539 342597273 960246896 243991080 500222991 330507993 199704577 295333361 688648440 445591271 433108137 953883628 179338855 756635419 899466078 70393407 853326952 356965691 796662159 563683098 715127072 39420340 834860136 845599737 986171918 715065053 740772365 675886304 572351308 617425977 312703707 31385502 574422732 686136755 753966252 19740428 179318173 109379297 801395217 432905293 675572005 878816322 290136471 838121486 869014118 875465346 15128325 268055492 498232635 526240179 405448346 713149170 186389401 188200084 764792400 514853474 155967696 639254987 634920733 166304617 57362122 228815148 867147823 627438885 836484936 651653873 373042733 307268032 817676586 852573441 546955386 342122412 834901925 75081259 381095539 735374054 138235787 404406121 523814061 913051700 466367113 939653920 769827898 82313833 665859170 255096924 129447394 112888222 250457654 536366614 843865964 871872632 903792575 320776815 215353044 58093414 368747152 485668852 869890452 62670306 165917526 103952089 939178973 117597613 766458137 984604736 790018524 725455380 431418489 784758641 166460152 902624559 699321074 462445857 605965583 640843550 327418394 357359277 336778174 294013260 776666336 598549341 941625240 557173166 426899661 178047907 856757099 288856578 634697028 212476507 563802496 582898962 753582274 426915851 712503514 161585648 418669600 288561186 544021619 791779642 702984654 336814650 845451907 848400981 786634520 662971735 511598523 645508786 458187618 340218151 743415939 583694605 772930925 83245889 109726274 88425643 728365201 8873576 891661972 750151833 329595907 932672967 442727571 873967346 697771534 251945525 156552208 231298071 596245339 493003632 386168536 755520501 80964139 271436131 261260273 317871429 186218393 253680993 872126684 77031621 105608410 800017257 653357266 155861121 892435582 543540066 775496201 332351758 712206766 742311006 376699118 488658123 982584685 291350488 472886122 244423968 90144218 789876471 112047135 24528320 48466282 279067083 485413290 374032360 435286575 88829581 405838304 651970975 901880085 462393568 828804882 943349494 606758177 920904468 651878731 254715207 518721202 262817631 89787278 363289208 521641154 979519268 672353050 632169526 703603748 593809454 582129832 109917500 603911365 72045555 912838569 311252619 713588460 833179859 853559178 886718641 980442747 962600279 975020273 366778628 732297773 407819636 948544767 894758630 653849816 880846792 854069389 10516736 848533674 932770009 589299569 570479240 459412078 990447195 55803320 341550717 139144902 212814952 254047979 334699751 861185903 424947399 25912652 868382234 121617026 675048999 445752087 852444657 658702767 383852898 166609347 734809876 938822017 559641276 126649664 295408180 578220190 552202532 122827065 295492940 909490950 612532592 329698385 737211615 663201617 341603234 90222439 71693630 987401715 156483622 109479123 200929729 317688442 951258899 937001384 407461386 962229451 653054312 573606642 843575623 103201898 714503758 951385335 201846127 944365489 610643033 656204920 241044609 34317077 661656777 246661614 270948298 738514533 758075075 551769807 711753501 204253708 255427226 452818120 750723610 183531597 170849034 561555714 78215529 870904452 392786552 994493279 162551806 763001960 365113909 887655867 215672916 93394253 894579130 616828205 690515380 179500380 859285995 562652485 230164333 413915866 459981398 129138509 159775771 312951144 804345970 654183818 515047137 176683839 515637986 973832826 578102960 63419505 781011634 529703446 956559744 469337645 550552726 88880910 132412820 357230585 160170543 964254225 901634232 547444471 407166279 965137156 223284100 241941794 571670801 71263304 411268247 275742352 339417452 396262390 508323294 520582319 452039711 955233059 243408332 255808905 249541148 820491550 959398050 904845570 459161278 664971439 582386086 251922966 17514764 412385624 791835757 337166366 578572022 410589845 88066066 499146249 562775700 208340765 761812606 47336357 40591724 877761056 925975456 686700757 137738667 303824008 999508148 151684313 17971560 724274746 721036670 267498379 71924709 186874196 669326221 882826910 333169359 46776174 190868858 103120095 295466363 632756443 802568232 191538038 974304297 831728103 625651715 209244963 163366723 280728087 766749251 865295746 397415068 776014702 16258600 436296265 151456434 954233252 250458173 923197575 609692141 60140910 235581334 867694565 296947168 206929851 637465876 344370662 268065925 169683699 182253213 376168744 45455747 186410040 813453414 347148449 965983081 350894246 704837675 300316900 972537073 760252052 185255539 909690716 338575424 642046673 521133518 210864526 919924770 976615402 290055704 177392728 318654800 283004768 16874421 896563510 57999275 173345524 327256788 474940793 932796800 544570333 880477871 302271888 790788803 68457486 54682823 455454273 922080342 450807667 149530153 504654829 325388609 541385009 719665837 704982993 913420280 825436907 727270963 237574465 626836379 265862137 830595046 913504494 725128495 650177200 966538619 501152287 702406887 163944863 808459888 772595192 816243551 965376205 588748623 597179575 972582108 891815166 572922090 317490931 39441039 115598573 570563486 498974942 786050513 18417809 14396562 437971330 396616550 447813209 467604214 582107653 307129532 129212530 667818822 153839846 887462186 173168637 695708807 166019903 576475443 669048923 902128518 189975043 626538434 420229219 436965918 813952831 606137710 526802344 715670640 964289882 808994741 354513333 499929641 938917974 975757889 461774674 252644801 143568142 865313832 482032574 687584696 565410424 827941669 867343348 723065306 918992611 777021666 883570152 204998778 814120247 253194288 152417737 680389047 402279481 675040331 121910078 906042555 328800709 383124504 750872747 367073528 631444500 605193063 161016427 434353515 571468022 63376435 643077140 19777499 89617174 459842014 402058168 614518809 514301243 431086712 664326432 850424639 41607554 305044471 337005329 427871475 946438823 986095486 656836744 493368483 181024571 555621015 698947583 480466119 568134892 379853434 246377128 365451811 946407874 281062214 153167278 615876356 169351517 158494533 507112313 546384000 348701754 316780074 318559976 179285433 193352941 309148243 535921814 375496984 717286758 297870344 541934615 119027603 41675822 795566780 124250937 480958441 547605928 349457993 831014214 807673314 99027794 11289142 618250814 714193297 390631683 494372594 973599775 161976467 270981164 670347543 475636254 452734288 557696793 56904362 860561389 576223287 577274415 863600727 416659701 610526979 770528557 440263350 181510555 390311418 40491117 866291083 101453436 94094121 263729185 138075391 60768178 999225771 376225688 472910570 346654222 732868321 248316024 465170954 730515037 82441145 372231683 413407050 171242662 668311530 934973524 569200382 376497000 686421811 903539617 614213667 643908318 281896609 821861752 30170017 510682684 120430023 344845827 708807562 337797360 310864901 516228422 886123098 133595620 556155331 746061405 317728822 830953656 186981300 339481793 643545647 779173642 700621846 109520770 797047166 669265839 9271790 158882443 99356871 425308665 182286926 563700194 473675096 248858864 327356305 698322663 282465896 446452379 775349403 564142994 393584218 909301558 600930331 783603126 550310393 662655099 205914569 222020163 632620476 721615067 315636650 262114429 42850561 332146371 325697865 425291591 151606099 425552346 930843902 855961693 910327717 252955711 606223656 648106387 237206421 199785933 126393204 769847321 737599148 73674071 220614677 414466999 299568027 649363950 80692491 997246482 23123325 32261144 439431007 192998887 19318554 615057688 395389538 661011021 32292383 64770091 106658547 395188213 485325416 699881414 354634423 292086379 275242807 600252635 895878497 846943571 180705916 355202578 121425897 726951342 621003277 639726866 945719254 135932181 163183340 670062007 863743606 881245434 369727110 119348059 727310882 114586092 133429744 435188751 635558269 837880016 667209002 820981728 145444531 979639850 579529309 77504020 539958460 202272596 556387102 413408364 37626520 22133700 735437738 68298338 662141073 526571592 467694122 762402922 418978174 983296074 921577966 623608114 652397052 547708173 88425139 928179427 974866869 241354991 662479839 80875615 641972890 320360616 650914753 631785091 976195626 295060615 301539540 600541540 789954219 381724601 376407290 984421779 708485229 130146179 74192066 507297115 802724620 728868485 982812324 860937727 831855788 773536246 795580481 164971262 89708349 571036908 991655845 338992465 497514422 300887955 923609735 425967785 85036891 747574898 181924741 849292979 643060984 930447276 304785258 108969557 259716133 219985466 931319914 879833840 264418946 543300915 229111138 733158301 287994 623622917 890458394 53935218 74585857 999469755 592652676 269751740 266720216 33170743 704999676 581600068 603768261 296798838 835528583 627432844 395245405 509876433 136272406 230651153 120768188 764144696 944523202 693277064 903216841 477058422 747819791 775678754 176090229 515885426 220402475 507507658 678070266 354097769 300636973 792041571 576082461 279487287 290976600 375542284 220393837 389436557 290799191 529600861 585634692 782415929 86629504 199873449 368049219 496642659 125415187 116449340 835570455 350419659 746177914 449348509 570315320 574490638 290569352 933173962 649961446 13365984 214768060 641271936 394868140 989274961 862783101 363060337 732488095 297395722 414642524 700488845 21064606 589040014 728404311 260526652 132350097 900092795 184450322 232598944 751739307 327531464 476908573 164011734 174620585 905484295 863480883 256902451 254738450 759785634 752578678 484473992 134022262 829377567 754219702 130648671 640007602 531045469 548864169 952081213 259511592 840513493 252792625 52093920 455447561 727222492 409070491 917325441 826421900 615041245 483770076 251201553 402395445 653989794 164342996 335461756 298939921 815260298 585288588 450087658 224160758 41581521 712135801 927875323 910338501 141742028 235768760 820222984 358679466 543309356 183899986 723659111 189136472 890829624 201737335 428008101 882323534 238740757 25583300 143686859 696498966 63852287 378348415 120145819 609875074 799889551 651145431 106535121 475868656 975048436 271503654 553812324 156786565 147900988 461220913 359410372 594687347 575298186 107169892 549548571 275907380 332942686 780521495 705906574 787725518 654747346 588276430 401897339 461110286 21027545 994921074 690407866 415499727 713834112 952028314 73602782 461183794 863652143 406618055 232665971 865741541 763777510 579921569 844447039 710181982 930073730 432926525 473700994 880422687 614269175 117100631 985522488 302952433 821964437 759527578 87873107 624964650 634728260 202161621 776134915 12753641 198090954 214638660 898099696 953584726 281952769 224635343 234267259 484093157 825369123 7116611 942803971 90626705 334032896 267538844 647535899 117563427 824375620 310152509 105515734 478987882 248934836 413062452 233191422 362410881 930146927 958664312 123152469 168447502 999125294 978026284 653186524 376267391 553638277 452458459 427003402 509870156 180785698 599177403 216871186 517531962 145537547 251747564 851410720 595805844 956520930 176592312 597439898 45504625 936950050 687055314 798783584 97810163 992929632 331853977 360422669 353741187 646566796 755339092 428835382 789421592 140646703 415695476 446467239 614232687 597407149 802481879 920252075 63038801 90594690 604354817 574765379 619359186 499705734 78472290 372749163 797970573 933103659 94546069 93142874 523670251 405344955 929404060 819154879 907550299 528475804 556150823 828155142 419239320 212831373 995632844 486515859 277605864 4079592 162013517 741045252 416719449 23210464 56637655 103901809 613150980 84018882 994892351 666700717 779547724 256905525 475901252 179952003 646086685 446911868 653585362 867858171 416491311 106440368 653215035 76661140 822428737 798929416 540035453 997680777 291078496 700278290 346524288 899134479 7157024 823049721 856349527 471497362 977993695 131173055 93176700 492303357 343964422 651075713 995179029 114021104 252265545 321044408 549827379 113662473 780067556 375277684 40174352 97966878 609388253 993951648 217904974 749984895 810267719 519266371 320968764 110226998 351122042 980261051 117268498 335121736 291266909 838295553 289488945 27939058 736009375 254077161 540142181 335444462 565945079 227961184 587686949 161796014 494050665 999888302 17490383 75201949 767365249 562783668 904273902 333048931 549050263 418065965 954327158 917985055 208148490 89579502 978391555 442851500 423359623 913057575 454413599 212696286 367573570 667225249 368070011 110360004 778112057 211298559 763522867 470231781 771840630 243825151 137370636 604757637 38445387 969903544 164217015 360406239 950174357 660488667 584338957 207492457 847188218 113818356 548918866 949937685 95651117 768487848 299636 621335692 270966055 3673590 926890826 120284019 744406893 656494200 610552023 570498983 334451278 915707297 140172678 386764162 189140772 347139837 896039277 92014101 629036432 814054006 827517836 623522414 417867967 188295563 821671181 966551761 598835369 602754712 954861699 428195840 451044686 615186450 90972460 583473781 557995513 508724682 468173361 810026404 431526015 888878119 4771299 345946428 540342910 577758574 17411325 995328612 9427616 490065659 275369446 411151616 705798103 191433351 451570157 639872234 776693920 140148066 594865805 862587195 399998530 919412151 963562665 277421953 531991566 51146700 978425806 812199176 715902622 399943489 801899381 912480788 223167255 60328014 804969023 399862050 474494057 297397511 630038329 449606700 773837451 630342297 798933272 601095139 209340353 375748236 242832252 999702773 375068632 172107776 667165742 666880326 832204134 871590642 594483811 423092536 272545036 589225334 502111736 510308069 659910325 327410939 569105077 804419425 282427606 524433804 253846925 531627514 654950830 879858955 947781082 34860922 658830469 363479670 229300898 840387937 866361582 759767844 751263190 183072557 138730502 109708294 590166415 391653267 166420404 938350824 564261714 122374084 36328425 727922607 903425355 470148779 919686111 65364377 130841490 126405164 248276316 221314 5613930 318137444 309092845 813603867 713499263 28731629 234127405 978295091 155125285 759436312 619162365 405171440 715973790 35489330 379876043 169103892 777906770 756761794 140997325 731929146 773492501 151624134 42085445 202709271 824599910 42182907 831232444 787651515 461378476 730357524 230689864 366770640 270977913 810040063 524972744 522477783 190530761 100344102 788329252 868631919 100101953 35395241 388880271 233887888 507180402 952689317 898727879 880581321 112492052 544511858 214920273 433769863 128125261 790399454 129729983 789220431 968675818 817341045 717203947 196796929 421825186 937492154 474526523 15107605 544883544 676931180 6624221 340701662 561320535 807668420 585724169 597114315 609811349 55799731 909864004 432032931 608418802 647409446 475929241 354830534 736841336 565222979 292343263 430217072 905056666 445315755 854710776 799908855 468611190 340466616 909539853 586515210 244842005 487460286 890436052 307251697 552873128 990140235 327763148 809399249 325639370 219358312 308578686 204638439 764651714 778977751 666685115 283083722 48774079 160389717 961241314 990503083 962742044 379247575 400150808 155666581 751820187 778593998 684528783 208499375 156700332 697088357 114855362 619390839 947392933 527614143 975223733 129751046 933702408 302467131 971451702 989417808 744334786 772535474 73137184 415518562 336657511 429381045 678871189 429537444 473455737 600852177 866039873 108438807 389376928 722240716 416323996 56296854 758786801 668996839 50239269 371633430 12698153 820631579 507803305 138792935 733431025 61016670 381237883 543076594 188646937 210495965 737375419 291370746 222553822 658339905 202211474 298364893 548511782 969706988 227236209 583523282 381162432 301154106 266938455 690036395 836299686 929266626 207208714 312030482 784633660 791043477 105723226 398649805 690615440 782649979 335013475 598181115 260740506 61416250 270833097 174936918 942069115 225909968 662576379 142104432 630044095 197413302 67403378 301971704 16670620 690855197 245803760 704175092 28411699 763429426 721804996 727123974 464907468 667019099 11273474 983967145 432961563 291590008 753649357 611333491 157189503 926260005 610372239 389966162 479980863 940771316 944436541 333897681 216504013 382927285 662759317 435487570 38022660 306722736 492232032 230677330 149951084 79871975 159536818 264219050 65605746