84 87 944276561 916397521 894413561 203952390 624644457 119946782 835425600 411460220 209123122 688266562 235534728 440682689 216003093 796060958 214256302 626568833 419529870 449805235 550260568 125527298 557351395 352754787 959030802 299547705 57320944 204536459 76613610 756770416 115907269 282431291 543017529 174511576 46713006 875990312 243912597 381598405 851753861 103251713 34122461 499691991 767715469 483181696 676641961 200362319 174087478 789185876 313753605 947294724 462820206 890246321 269671339 554593289 62736132 457329951 244923109 531491519 976499773 896193826 662614899 880211051 294172218 471086084 715049691 337178757 759471346 361311762 813937217 361597144 113179905 55587400 605702934 673755687 443030695 51230147 203265873 39629021 106213602 271287991 444142087 27377962 173262902 163580651 652809367 258557194 441917318 545946007 928224490 69 102594100 192958927 32534584 903835606 879292343 37483062 614006797 186356062 758866448 367202750 89672110 66833091 880771375 825258783 881398961 246592798 796386161 851768695 680342232 334858196 408616049 285234067 666779140 933342391 539445164 913710883 94135988 837722395 105534870 645754292 340577790 63132638 502301001 698260146 104082216 953422815 97885544 164564251 210559983 229505534 52803976 710255345 585575846 793579685 601318859 163450427 269800532 383040156 72254002 896439160 698278773 569083107 471946717 893741635 367723537 475310283 229264266 64827654 266889881 770746171 3670942 759181330 394300842 299107852 348755765 685065861 206114396 857007883 136760098 92 862995504 544365523 298064846 65998575 473085974 216452620 301556577 477322855 681452933 428474817 427896866 471651148 921413861 219860145 208964047 139590770 43809536 116082054 605935630 577627045 52462693 928554683 705664280 661297952 41778510 458959956 139265355 843158771 524882725 879507251 660230481 718026094 732080942 142633679 943310559 781591128 474189830 757034627 110861817 315239663 131723410 5950791 319006882 204679530 217451456 264325599 432468630 570813438 659630806 339943293 473805282 342140064 718116919 31595003 108473751 476548672 872686956 124178560 228698796 524457136 747292670 900623363 372864363 279585456 851111580 690238784 996651336 49350171 596225691 458028846 864736946 374940043 964446270 215954046 840260427 447681456 705358686 207651919 443726933 912495016 229261015 523527319 323484667 990417824 592746311 225872468 687361881 684399421 993998475 334652212 706438215 220520759 74 965540418 418680044 727812197 367529572 350386761 441337209 908612526 338218765 487532841 117393840 505152805 342420115 489044573 253231201 397399986 507911017 944331954 467567891 278389983 722641640 6462004 541777764 955540724 852071420 181503193 717044046 583289033 244742972 85683007 781151923 277404245 467160060 27874106 629700267 458356730 564159447 390999822 374461473 464446460 742817315 128878589 759923482 605268269 658125378 335998505 388495412 710357617 41487549 902009506 797137333 587423232 300212303 205922289 771255665 584143989 581897759 923938444 497611516 367944322 379923750 303772294 723258428 76824037 129579715 877136811 956970975 276119843 241895978 140099855 987584310 198547387 675521221 806662062 958989328 9 101729783 387631902 379499339 172901749 434221038 846790457 553282713 527164057 555897486 34 179689841 473815500 326676938 568594085 456671346 488096374 656821387 569202289 496976687 436233932 716007662 950510438 519986443 968527192 770850235 218997059 616937441 320692538 21010305 361650179 752396722 677704778 16501204 599693222 295681124 805761616 100788253 342005663 372506632 118805096 838572069 23435151 55787496 561743778 44 973272684 290484634 650676394 836034877 677521247 515670427 41046282 47165386 743719989 65000449 110143419 946015714 243078652 624199592 948703110 350901487 598889751 588113803 732694094 664942390 553560580 831526357 415815108 253783180 831113241 757477058 817618683 21381185 262626369 339157758 429379984 286262183 921693866 662868049 963773195 760307743 169710197 143149547 855621322 840662377 384296356 636376791 886342671 986360432 47 324190762 662772021 32178560 884583842 70545201 291755758 370491222 908206588 331767238 719365738 573311062 572490319 826821195 369951496 890638108 306855657 150197530 305103611 997162072 176152726 521597588 695622746 628630904 206434977 155596160 918734055 464178899 265506745 534497221 293589760 893505869 583355360 608051062 271740 153228214 928569696 844417974 852085522 162278830 921747263 920061350 417231132 292755327 909941753 227617320 738629884 249609888 7 988930979 828649021 374339458 557263874 142869342 618785443 704416982 15 894845818 815884856 695692298 722803987 362454082 532426131 948856575 142540867 155612573 14769464 359807148 273020332 248817735 666773389 169644455 98 536453193 63411499 783979479 220936202 69192460 402783788 788232906 889703565 710377343 597040329 768951962 851695398 494018498 569571612 584635211 680443270 640894038 578356965 992083663 733481330 997323445 941463253 106736255 814512032 395881002 805617472 902746853 216605949 240991590 516793207 280620480 722708447 595910511 201111062 872354114 375374690 936350737 238500194 508983229 242127085 256133923 314210497 705234185 490769573 290141001 112775351 273954688 820602029 722562068 539091433 825546642 49122228 787122213 174421303 662051661 655655296 852534764 157012169 98688121 469068617 301649027 774803521 132056049 801330319 569933016 340569652 968686752 663413300 690078503 597848140 587545205 368149756 112963155 289843580 344862396 820335013 493811413 692849114 553468622 922123382 591049962 532834879 204254854 983509323 206961615 867853314 337934482 228693405 966105598 38034344 277263633 552974683 777261055 872308369 273383711 439995416 46136701 574643805 77 694368862 188343580 555486323 853140828 956328734 610181057 441970891 925702091 803333318 254689008 949969881 348809095 60214324 876876162 756958364 801285629 73282411 690671729 775672470 744636529 394044470 516570196 753067099 577572968 368655286 106092670 660228840 781325057 28575456 127773722 683989887 490850617 614681156 292143640 658093700 13890305 226162870 684194567 657765184 431171557 558328166 570867170 438582246 183972787 509898770 954735479 528541985 932300814 168571570 465843653 432248373 215097548 692988620 4031242 522195473 561935668 28946057 371616136 401884017 648462150 250090446 928043805 615424372 326115547 818591413 645698803 789986997 956680990 954937448 571675551 485812807 709583308 475169695 952383478 113060715 152073234 494781133 99 677565045 762344925 697370799 33002581 456482370 716312612 206159824 508851558 902664892 798164956 154021460 315524208 246956736 338262739 702359305 72220473 251492131 697342286 795082681 354216984 225478372 225654499 199890576 665057670 355158066 506160087 59681010 391045432 122598587 148100279 431153569 145493956 969110344 480105254 7668572 133502431 813067162 294081376 42400279 665921866 578593320 564956026 62830601 615510464 988625817 1587532 350205629 581413143 319071418 365400492 434843427 532595217 167122577 962454761 652316428 593573043 441281563 891537052 724472133 141589852 689201909 212826322 888676919 402894472 752687327 124426710 337675143 425426886 366191453 567916874 616160170 470530142 729499862 529278036 91453930 51001363 105420975 361842350 906559326 985075547 703380464 79824460 612009682 963111362 425994216 725408087 906117991 551264794 318108061 655606607 596403191 550714235 935996955 191429797 774171308 840401932 422624518 431433140 82544657 21 860561378 861803356 838242888 472423054 847901548 692766890 994324909 11085191 135290849 755752755 381368924 110025385 683843198 379043085 446536766 643115089 624291316 387786070 143586171 733122468 633640969 71 387902236 857197083 540701187 482070440 979370129 398624922 215809522 299995069 263458113 688441962 365868596 688358002 940317862 322231431 741077981 606906147 938179926 990771344 952806364 676096949 47001019 503850961 704841967 339366872 575675504 267872542 126129003 281827208 737701090 906030629 694147788 960567069 824677150 693648360 591484623 445199134 293817090 882902055 126008633 915475029 528807391 91548746 34013894 619323325 494719378 794028568 100615338 643378659 766660274 28271560 150075990 30036459 116520481 243334951 964540561 489081577 193815315 338141299 913474669 223879502 948794609 596666747 46380813 467205410 786018186 830796999 790439351 289464619 378822929 694561294 681459009 7 521314377 996393559 584879529 64243326 564256871 175041591 850801922 59 178006687 673797241 612156927 408973404 77960650 845233514 245345530 593310270 695523 64881056 589418106 810309357 822340509 797203944 939590226 793892585 277325932 341972056 769849397 157350713 825147955 676203026 246581657 312580470 877290775 664734284 817208311 76164141 705487474 727331688 260039966 330202410 373076265 133907814 134223188 727409266 956103704 770900882 758793161 544165360 277911922 641103123 833550989 26937568 643643562 809827469 708321387 871299522 871037451 49743879 431963592 261326629 938445090 941798589 984768608 16182722 534041461 789737313 846804807 8 713404637 957236846 62459562 992550209 200278228 794146019 431550962 491246206 86 272441890 134307039 443422347 600424377 458305519 738652643 764407757 299439335 860045130 484051988 542754650 755718372 31046597 474976107 626115157 133723404 783047137 43307533 272783075 27778058 32864193 9610788 994808338 608245548 664126073 338229682 827235265 816477386 477943322 649465083 400346719 424745931 586299731 974275644 998511650 919120443 873503782 827746792 878444294 203444986 365114162 638316806 542007631 668873747 888534931 872088631 826171099 222520350 18132853 936078126 349928359 274139336 42569090 775597474 997306227 450228738 704540953 64033233 661599504 323018161 829659770 378397600 129193616 739909807 489274907 710964680 571839227 998192391 810316168 807971224 224319864 976424122 722804773 339165752 302314574 418309685 666757284 482723270 194657794 638542177 680692981 960066631 747506963 280796483 528877247 176793856 82 288744101 978489175 821709931 568873240 88704703 657822844 924630281 464838 371660150 361232151 104247608 499091677 568448506 312973333 444719547 535588204 476188454 378447831 142160873 902942596 539822370 216617471 2958045 514925663 923537898 383410701 214654321 481099 815740084 624462443 459239349 97488166 930386114 308141014 663446220 450439323 496830078 6588138 541332908 946782320 110001647 674622740 845135947 19642084 658883380 722913110 163739096 3229958 549930626 20270062 775290156 484478594 807609938 435731231 295971839 705181555 463256100 354978911 65139559 360053936 640246845 145795398 549907567 171231572 958510065 251296206 634208656 982193740 27875091 933398273 344347268 379693949 503604563 516764495 455045543 547967057 492321237 68741054 872568894 82895886 598343973 207195566 3 16917643 976599065 338817798 72 660233043 723335199 372705136 518850985 332691007 647346793 424993281 972892825 456480295 827367593 657513865 982226697 336936099 970230571 169504183 208708366 176862297 663580973 940784772 622458084 341035645 423824988 449105607 589519465 25376918 774063252 701560130 995179535 239477244 1289796 130281621 341874997 531079412 124611568 968308424 739765107 653920307 683483703 403221045 599067240 587990084 745294045 267460745 170286233 974863163 625784885 687144040 451964729 858987553 164785075 594536916 276698511 433438088 544484748 895879579 748406107 310406639 299927153 276022983 932811451 130861935 207544269 817440097 493399617 159771920 451519338 923689132 345780210 922992160 960607811 94388530 862849508 91 505523664 390141503 777283657 500036505 410059070 521573887 127422864 608487895 102057933 641540283 431191293 514026511 496161488 351626256 577212786 759999081 463935273 141151663 28098145 922504618 683355112 541160675 344266222 769489595 191897802 502529700 188069820 868041757 355494222 496446084 976107882 363354510 239792304 875344933 241802089 609428101 983918986 640670520 723928725 862589199 315118307 77039531 747484455 318733245 266203520 235919816 38974737 566420703 873418851 280585398 476250981 251810886 572805885 438297226 166514730 171982609 147550406 765168747 310017419 442114704 42529061 321198777 461988707 779648160 742539623 200854076 148580934 958536334 870692182 716122425 794749994 321227481 801203386 53776261 119156586 467186498 555143023 308439646 40967163 562241965 829556299 574395263 821134120 242173557 510149684 228438046 925593633 581476917 362905716 217233579 460202782 47 165334857 933947045 220935513 667506893 507286627 662455895 652587560 243853862 152521505 647974348 835403816 11126028 570723041 426901273 928855805 432477329 671411517 46433311 298994575 394029091 270437626 387802934 456609853 383124193 619721260 66531574 839164797 34689208 177181332 614748571 474823476 198393336 336400539 775784088 754064323 819846434 803619297 691618378 174157375 560850684 985011578 905662420 68307221 386244519 783546960 925283397 283135016 97 56703008 530372820 715608656 914107068 315067272 594866303 234717954 726352053 175683579 543131975 587731056 955410892 153707357 979021889 162209637 536316002 385097041 507288834 154972224 690433189 474961883 334990428 498631296 748031401 731258355 633378442 470892249 688491267 16373567 266026693 972039235 701103553 217381769 62738290 426395039 637125354 358189481 706437723 753357073 582697483 197664913 976882914 792029039 418093681 755766394 927730438 395497879 399803662 209507924 609865253 252378712 644937547 395693567 258356769 840414022 985479974 356112344 615705615 221289659 121263201 55797906 742801534 77777252 903230550 435490457 191529873 173859122 240561412 34361102 893763135 211222856 505314410 707610288 800059067 325317148 893987299 80700909 178617934 348549098 907349804 226495270 739522031 80519198 241050577 377922398 981451522 423288280 470305582 921227000 638904559 424386197 341146927 328194907 647758922 929144809 279263832 243552295 22 326512899 12738526 871460653 899904351 703471043 296951795 687774050 678192965 548784338 552210857 640277507 514699203 71648766 725014460 605783974 342282951 940378260 195558121 329404238 731601322 989811530 865666960 36 407473993 382683901 288709588 817351832 460812578 918781265 694491383 650029479 91581016 970221134 34432556 125926854 922589277 136798072 607965725 535164903 426199049 917391771 54342625 802862060 93792787 451973873 638599970 576913804 856364855 563672540 881780334 639006116 421043806 676416989 636404462 557256775 843366157 79396358 657592898 733176179 24 100745032 517472941 878996711 199547613 671474011 353169209 392788727 912753962 751963879 245123294 701015991 493279690 255390119 430963753 67314558 749338240 24715898 416278929 394437540 666324285 268137831 806459187 51154337 125312952 58 607822858 398258313 822496366 31869648 600660717 84928998 295124906 351598012 320462457 825406643 549461028 248449839 424770889 125500222 706689002 59258536 417711443 820816203 25161590 313146377 657325575 831146692 928026308 72570974 339337228 69602099 29439672 359660987 689650079 341580477 657024124 910111297 754882721 894656871 852465888 830534371 380494392 19235315 859375537 822821194 216713794 737062835 4138317 168031200 42007466 135525391 57855350 225374547 968428181 357120053 932712748 440364590 344339361 529273728 188477238 437884450 978464016 570647181 24 573121679 526406595 928741450 838320193 202635582 126350923 485275117 343621940 959562821 686598208 984325834 687028677 145514587 923134126 70599058 59100078 301594399 211180322 26044318 850944070 676627425 858999038 522692037 635227011 52 232976077 455178266 191188416 262736605 693672086 764452374 774542468 743153913 579292731 356338729 457498414 92640602 848070397 742257615 190574391 965941948 760239333 816925555 471475631 379690717 249419734 650966241 748572248 115828117 154407192 557827965 76470668 795416625 109869758 560935356 295872681 655240389 970663857 825754694 400915071 903509573 315519853 746692719 865488938 714442938 272694479 854521605 141374126 487964257 740902498 933757081 562506373 101191493 271509366 497396749 946970008 644940441 19 733589386 675433867 688960458 306828591 796110511 417976811 107581263 771171058 664670159 766635796 89145085 776675799 432069462 899178790 349679426 581518083 51869178 825168039 630420157 28 839849063 828827215 734116882 978094917 438616033 458427186 981592151 457538011 281829139 179239245 84998977 740112385 454199562 625053795 217175217 854602949 789154637 699635862 826755843 571897783 749995734 998098631 119885927 772206895 901750000 864820473 725421998 543523487 97 764374480 498919989 56636196 649371185 877870836 817801955 793950379 95376845 503836261 375533750 293570936 297886599 961719610 953722176 820868758 351096983 207723821 796248938 156412968 112999 110518857 966001714 795703934 210026479 656278362 270619265 237837458 128500920 732831471 963600869 973724275 981535809 593871231 922861939 810193045 782400634 692625917 302012105 194483981 67092135 753254513 211493058 939820461 424741078 793685754 177017579 7732400 986762009 778114768 219954798 9450881 887133897 996138584 997693384 26477707 904248554 822089356 380062193 662676003 23597871 222183050 253717641 392050330 281704680 217775739 564013187 468054629 53210732 103424857 500367925 186016018 924482143 121907599 972377190 419519833 247244316 252475630 250156707 24559325 84998859 755489183 211916629 837814989 793819765 843666358 151423683 667270646 30730658 407370707 876508303 93160954 38635411 556554512 664758048 572275822 635138316 237633880 11 638286618 372306196 507566755 262580019 258884568 424864859 755185054 350047998 977101229 808622018 897126825 61 940710589 429721265 411351713 870438909 975148269 965097966 514872885 102666271 591538189 762656419 398011322 547348597 292020005 622063186 550378644 854769078 942742594 798690506 895582042 356142144 482690356 361596019 67242461 433886581 678823235 25770529 237971601 953225770 198036568 746791209 587302276 359107762 653400459 990942722 514945238 940737325 85495553 419595450 549961771 921339946 686725466 43291274 129000262 130513391 96459854 533300688 819173850 161828856 846408705 786729140 805817049 974537730 685651404 165707991 131672101 985686893 984874798 505360266 355999077 990640587 209629218 45 565916898 402934127 59573334 614335004 242512341 748903579 207451737 251497594 970273249 791086268 992873021 164554015 957242351 408715526 566068482 60302104 738487022 333894558 444379687 516175375 852889669 374934816 504921653 661761860 163785535 376297595 353919625 909680987 366854002 972155194 786299861 907412433 507067469 804791038 229655611 875990558 666069312 673803709 603136725 981256949 934552406 84882542 260695487 508635241 919675639 57 515024729 224994785 943713129 79118103 688164665 468544905 60501864 458029406 180915465 256911686 749961030 962911347 1240350 905439993 926164032 410947585 981560179 886087280 194932318 766735585 357024467 645787140 739872985 358799343 838026520 315277818 802953056 446193354 773824579 104220673 107941182 42360062 534436264 385569657 564237261 199923208 253481010 995778794 767274220 695510733 41719722 182186533 317193456 33221851 730496379 658327109 281054107 995903906 133762571 80734959 731205779 836809176 258057296 918155983 599350933 480938380 354931630 11 315389435 674424322 56984298 672645765 277099695 491879235 18333660 202149335 950965246 513287800 917487233 35 353520412 897331519 336743965 163049861 316700829 428829387 461024793 695604376 82391980 719017452 18319565 682261400 827174816 764662074 330601463 482787939 488510 434428902 574663790 811050675 96931289 487819821 307204066 546660513 746855807 319279813 715801575 506569223 821058142 923825752 923374784 206081542 736127005 527838240 911030519 100 459083853 336005617 925456632 318857345 412547872 862446028 857006217 481469076 962574895 196903165 99564491 157455000 531954325 333314572 974981320 249484749 776562360 776547516 974384076 474760876 285579664 659157945 301565969 898898823 665062431 876195690 240309242 877996287 938498496 988878076 694201398 8768115 75933965 416615168 812406859 873040012 506238206 365846594 734517910 618463061 251021679 91757587 120527800 698331973 35897718 828140486 383743127 587269913 657255749 306278321 987234579 216270506 451557299 276692744 107018996 597585096 748730563 773955408 168078782 83440335 2320255 957559978 289227457 623490459 263782831 591273076 685345955 824394843 230766188 914757545 572151820 965556041 980215683 220473702 524276876 800204343 563116662 253436272 395444028 67728856 715670309 907670155 830779517 850466168 668806229 529282197 997877854 475530300 604806075 859145794 784233649 243423256 647741118 722707394 809451969 735746837 923155542 914656225 512776981 733113233 3 84404623 631501401 499148466 10 92940527 369332583 822000765 888303718 761703490 336526470 823837434 935783858 672797410 770233440 93 792166320 818800507 278339757 737412206 464231328 974846684 973154220 834949453 106187184 434660610 880787117 123860006 174521590 544375868 658396873 803942765 568455760 42133742 175094950 200821529 372575367 667175496 878658033 520347123 150337104 186048988 15032618 14891815 180969754 836379105 688937536 439396935 885022789 20172459 788542933 770638932 120033489 110992687 754543469 861994927 57352665 265995417 305554050 198440324 353085325 901975656 425627571 116574916 785704803 850238985 476206219 158918354 211259424 603305747 657501407 880499958 17508996 579564088 960622884 418381347 378521016 748848782 869644329 358717428 97255223 747214635 181751686 236762499 578965834 947955771 811784546 816180779 343952833 445318636 636553159 27697026 692983595 203642978 966725842 855492253 256022999 905453059 947473075 626028447 772009381 411734600 796060185 430870766 193648540 53840388 907239560 44918154 387086313 63 618559044 592067829 329034942 452753938 337072985 985222177 662766764 819935425 243593576 465145957 422229910 64149977 721457897 760781996 449561118 606384601 784173914 113969663 982306934 649427706 732836248 561538085 76399922 247163956 373587587 666821267 229449587 72838667 562719141 845419473 992290855 936289630 175025774 658335929 720469624 438982949 284524177 401376387 206399449 427289828 945180923 219070540 234128421 825808564 23298943 575662504 340586267 283547775 890822813 57982834 566803802 546179810 473046701 378646265 859988615 510362514 103587344 862941346 977913761 203706347 942602461 492357331 944880854 43 569284761 237983709 595367513 587751412 667032342 934603146 651127753 916188848 948299992 972502133 213525713 586038217 30448241 199137014 339301805 64093317 560376560 76727657 982226755 97887542 482122955 156460299 272904422 911098746 413217055 678478778 463667109 901881830 766327533 85552239 976470083 211401608 777396418 136170754 901688584 104784604 646631088 962237639 423835814 312542572 913812464 520378951 992653050 95 75625154 826563175 928548345 553287012 610019360 619031512 589759251 895258048 104917179 282387212 259172910 79435790 289848305 541727649 363269397 954364976 727541488 666010173 781238499 248187945 386148835 790416589 484875074 15892513 193000757 999487774 104752312 630748261 413049179 321646857 20872042 737378839 440376301 181540726 478700901 917345302 607795562 109141929 812388444 394198175 405714071 310882059 396543992 503077804 249404624 213775763 990335162 786856015 569384191 791941849 919758762 250674008 137755515 263735660 888024288 424583681 384602270 327446423 47202400 233174128 672098567 809386984 815825707 127616553 879960504 161030401 665910738 792492425 300783253 511950944 45676125 899856353 176727157 329722155 480265532 868502067 588545739 51939354 294530962 371291023 71251357 134897121 197485640 203371993 784881152 569089197 231202507 747027733 719652633 832076544 12241303 165325272 90283641 761017232 644396610 43 201986128 804258504 110485653 302472927 139874932 867174036 351127925 971821114 425550323 744829241 424119480 664774531 629068008 406571510 405599479 101893076 267246192 375778958 118175021 594741458 888090078 156454454 122795580 104994179 453114145 760287746 702758626 89783412 668969829 19995696 946522610 76929306 220183164 272771648 621618171 327238053 979371089 708086638 409146686 534933647 288567927 894314844 994016285 40 221072482 251828454 326033048 43806127 472841934 948370838 784374630 906078495 796776635 466758680 171509091 81605679 330558817 952831317 811711259 188991258 215534230 319458799 697265636 631085003 847860353 252277174 911426333 330149597 91153432 996312723 914019746 584962789 392040129 320449230 694587891 37379198 330135181 506859535 156963463 938592806 953527009 353856337 846773354 886837892 58 427353021 881312146 586617712 101305147 358642484 493905744 339754763 534270460 138048617 462034237 854406995 312424232 762005833 451857850 634827105 114415887 167201597 950479133 464764139 252483278 254717441 142514005 865056769 857331014 359364226 87898017 378471274 282641142 781454297 492861867 93979887 69110994 836798439 842983628 15359444 566544025 994354837 363841487 509566025 487818894 257754865 767678018 532398753 981423452 985842656 317150609 694191435 681417641 410389668 960429917 300539109 197747644 811840301 253425923 545079603 374325950 430052660 129958435 5 520881369 186559292 124137942 118304534 895858425 100 791893990 761681866 190518286 286766174 26457571 266937530 929921119 201370072 657475228 131505852 439456882 439281058 303560039 199205459 753959274 696860567 22532496 950835995 39527402 138920060 429487490 699113793 238832973 830164461 909701762 211310432 418270922 336758160 815628860 848077478 582393170 214497457 763506653 434888646 197404298 382770519 777123603 575710875 260726120 905631929 422342687 573094471 471926799 374949827 675651092 505785371 852210133 938930102 186051572 327271376 710197106 538758295 524272065 46318781 790557921 321810785 570856883 9991493 738827997 167540255 901685358 653251917 929300711 471976772 720790577 768204159 267333364 763990011 639080783 121660101 555269430 649366674 401939447 10032008 698571523 52020401 17052104 225484101 256560676 106221039 151754071 525010927 871868109 111751958 490776956 638546121 745070216 452340663 514971063 969399674 452203616 36933586 362381565 994667383 555781022 951192111 17077017 183910153 36160945 94356418 40 491110315 796218611 985780521 23255629 853617570 909838542 590611637 370398541 778386396 166106520 441649429 16548192 943550068 832710403 584153744 515295759 995385648 657170942 497193659 907920129 740945366 780783484 324770201 108104090 606902959 521065698 538825984 860309141 438800265 861709501 130881620 776748436 848286520 257267015 704915540 909582729 768590056 128268375 616069281 95977065 28 515173573 72717981 576975794 881096027 161071568 440965169 656377739 128062139 774801176 943349725 45526427 725686383 605744653 6062835 322823795 53914120 909483009 796737542 234146857 396739233 519727211 875496343 436531137 804439419 378307007 240392358 581813233 127009699 86 113851923 79092124 469045046 770412698 535621911 734015029 988445090 287567510 254504603 990343524 581960104 755176398 830074737 661372522 461160790 168219776 224647661 17865330 551744493 274591556 2360925 538091588 802260223 308131822 793680258 400047683 77262065 529453620 35610673 872098093 338550025 777525262 143671880 400819874 31076027 210549558 976198850 716255364 562538261 481874938 909686968 385828893 989702954 940241568 292443605 202875126 194123546 337876241 832962940 624036940 394869272 284888309 887310833 402426844 318449399 785787386 742516664 338903688 11393198 921811782 452099963 899297297 393543905 168422341 8875870 509505034 412651899 874804892 217321243 5301998 427132589 628435021 613156278 318821129 761081549 376317244 793765748 512439995 700952183 631661859 377183209 821532661 618294479 901660522 668941863 274882924 17 25068690 128085311 156609723 254323190 753600152 884662163 241595135 9448856 652132429 757483187 717055808 341949762 649986436 532980690 509212580 868214692 31381989 58 616763431 601434376 475269740 259956240 796041566 890881000 743979764 986472077 397489403 815758537 581464355 371077651 361160807 572794726 412002660 483345015 990184751 446152996 367300904 865576101 327811728 693662088 104702598 75795533 448601730 612514383 717778431 854536255 41580576 358325020 700505576 647456860 914229601 456087392 120289832 479248118 12615530 512531156 464320199 856928213 734341418 867942201 451911320 507683412 82651074 71098081 44109838 512657969 106896853 370890252 807442943 616767638 604239072 457929149 797354376 683908604 286912074 968557410 93 530008153 494109085 400391927 979347115 486112316 248260910 887282653 674569521 705029458 45135037 770199027 857795768 663455721 883096719 729188932 550336754 4852200 689684551 670302420 497348285 89195596 928064296 425867399 833053131 364377128 334831643 256826411 571919122 560796652 208038500 940913874 496659104 775489347 948902953 587198668 218323892 92511632 321930154 856384606 891339753 349554214 734792773 706804763 10038999 436866365 141355451 71413395 965681899 221795172 326454166 166863846 937983587 114503189 111958018 501353190 716390505 129645094 732512801 729900485 603314519 331452231 815329779 194410035 644968828 202518828 748605745 103090453 700927477 515601377 868471704 359793037 723935289 510246756 751131368 91045461 149305785 170721683 940599529 565552095 564812137 823107169 484031442 188475042 411063803 978144706 548547312 293045509 684089963 151349880 62204745 676639116 101558832 686311892 31 707864584 607673400 952083987 217417071 888268751 885858803 54514936 706876305 288123145 715483771 176756830 521357621 214055470 825335645 522117394 318987157 295205891 208268947 663715025 332574903 182147251 614118641 131200838 896152778 640397419 853751072 938467837 318898542 924463512 197933145 310211878 56 285687806 542075213 260607453 939677720 631678 889416742 427430397 571741438 431554879 675734133 606406388 177543889 992872709 7318864 141541914 471783438 616681426 454302299 415546000 737892146 696841476 852414700 363356190 813250476 566511072 139671282 20079015 687341392 803372648 845509855 74223645 221443573 173637569 189300978 919592255 488549709 334639401 272607498 623523645 960907991 221874715 467477115 449995151 47067379 328383159 971011779 622536129 263271582 172456775 298113460 600653326 669819176 531848026 517333653 780212076 159070324 85 338364389 588314853 769246620 728665217 735250601 667509772 497375407 527702885 428270486 782864353 476989599 66588427 881428634 261580597 302173145 156460332 148127701 632527805 917650494 935433513 225596768 636909463 191232406 732379006 292001946 876088886 644732640 666198823 896517784 156764570 328021984 518106986 839323336 453481751 952567307 111857960 981738751 945275290 576729768 677370264 671904239 29221416 693766765 550877857 724019960 708041147 498200751 646282666 180407257 71995912 133971734 44215310 458088263 36287032 98047541 753397212 835281244 40255524 830528182 834791387 715984571 309794812 405835182 209908326 492425040 844146573 759269213 352241880 711180763 141528294 205936920 104131804 163255432 105036275 517112253 558427861 897420488 999109619 963190544 1314608 808801611 167210225 785038985 391295161 183712226 45 174549434 852335830 273982796 25298134 809576416 771303103 432641161 487725241 659502881 9265103 278165429 30181401 547886821 794560669 871345743 235943038 284901581 339299892 280165542 204668672 109353962 382876435 214563532 381046816 210902468 554511741 466178537 194536120 30984535 452106561 614820393 205699438 681933531 99283083 171864043 158027515 508145412 840961661 862872020 859532026 322408261 243960535 509975261 74787757 339988313 74 768080079 233221105 791180171 861958470 217003292 896507930 911661418 270528524 3501995 750590474 143549044 710018249 70322078 358453034 348844964 395501165 735933851 997476292 645093760 33108402 472302761 29663819 423955174 891699454 91187852 318258576 220585546 405362130 738392534 759249349 711633177 955902442 221780183 801285546 463739814 664619819 875800575 128104257 873723137 808903045 591440030 860500010 806829483 512584403 251893517 884041859 745374206 241236290 880967000 321942629 209806251 209517327 583526786 280052768 222442456 540537374 995087525 226682226 431459205 556931059 853016524 337227965 963343457 463802543 554597294 785397772 752235470 708165968 295028348 83211864 861829988 449534118 145777521 375277896 18 337382757 944433756 263619482 803534515 982343635 168330168 609496251 900648578 659729299 246129330 275349064 269493776 138271926 903821785 340544787 12047850 303833943 550485579 44 244482718 654577843 200138319 241480980 32660705 216997134 407082051 36810150 376325254 138685618 180076368 170459002 867803927 470002297 446805975 926899327 872546765 948238202 230407399 130071312 597628672 561914979 206455933 538146027 296190773 298914527 928727648 582130787 270791446 843287279 102096779 410949893 184369694 427931613 408869164 139355042 304025828 913107615 736879102 486376740 580393538 441328504 884432660 699489861 82 631248225 792334995 108636260 735172464 764176723 268891199 471266227 830656090 832651571 641499983 697224538 615257280 702368413 82456141 584258409 751944397 767316039 735661624 490018437 214602541 872890466 671069895 255455835 318109474 879754315 307659559 835088976 598845917 769718222 593981124 139001927 758452567 255784235 354687279 226422584 991521040 933741000 591175144 584521967 68655815 286219575 640484128 335023772 71166191 190921995 632204006 769166462 452094471 398105104 49771704 410900328 644503813 456501135 722112013 880228091 958359207 229402843 281541791 429972842 830840845 924918481 694211200 695883345 836217254 188629281 623265330 351332588 886195793 134527217 206440692 929498693 734606990 6943218 14461313 585853907 979017890 328497010 939727733 838672422 323846393 750269036 551832144 6 258423621 621165247 538079029 759482322 274564861 66957602 66 482769318 364508641 190970708 328318958 634768239 2768279 793398168 93632609 127370250 518164376 377670016 248216485 537692752 329678799 743651615 196196215 805466593 211636240 553511734 37206548 674921166 847008670 310167654 503063753 354097446 121943623 263163427 542834269 32113760 72567301 744400955 77041750 20654389 924388857 869524483 796812233 758597023 163265473 246013550 892033474 599016598 514312601 72576344 942722408 422321497 446284869 898528528 787482034 442794112 698782875 678136478 884950060 32537137 756259671 524021205 316703576 818970406 991898836 241953739 6005890 580756338 390002300 533947357 816073493 181550272 511047447 92 351928362 579009917 730699109 309516094 757792621 699728202 205545363 937211655 957500700 685184826 845545653 504773803 999622594 141281673 413850608 331068940 227481326 667319423 29009650 173723477 532211885 561360244 830765245 701863405 565046395 837641582 841071368 333312231 994753176 371927057 56560357 559713894 994685212 148240076 259664608 224986701 551396512 431588216 765253893 339457092 39560206 35030854 579534283 416895194 995232992 466573929 97633700 154424925 302506381 445567365 699165124 540471768 249982769 988401666 216295220 965061590 909405506 13850146 804843966 151834944 490846118 954768198 592740506 39332925 46221439 552703349 660443505 994266199 825216488 204946599 825821220 39882445 496476872 617322915 588999666 54199031 990183786 287138171 430518638 259854007 596513480 755665469 80927155 168072697 483738790 861016835 726232668 730685586 331829594 64701189 176897938 101163418 53 144620606 848933929 544678558 784213969 207903390 561532525 593670287 866624612 433927899 143484401 672619637 181875711 537626506 662910091 692093837 737505699 120457761 807823288 104856907 140492506 961406471 178289685 106974882 456426026 918179959 703826071 849486428 230520700 976291593 757034606 106486855 190119217 683720227 426834580 738301628 770698073 264873412 91696703 625794724 785370002 602749786 98939328 280224081 93549609 367113347 299747190 848390562 754145418 420321994 454543795 848516234 581893955 187452988 3 803757586 452893401 112529208 93 970761028 578885438 231699773 144266997 309068017 426416412 144750243 945175245 385935075 416995774 53972693 120582982 77200403 721248853 612259244 317346412 812278526 677294478 102604029 450049346 26202513 447701293 199330237 29464852 511833853 700431564 333562933 536790841 965766376 675334030 633661439 175722033 796855802 881510533 627558864 241619668 192178393 873721834 860280800 367081430 838320287 403100207 570613617 64376125 442426322 690989911 368877501 150112583 651406291 663621428 381708891 668839712 550336876 978813568 20264104 866668984 763041739 31584873 426968956 258189478 554425599 457725395 744062648 977546040 688778676 208781978 552422680 333969921 103595358 11989513 761604066 851821249 566369948 37687258 596505421 849175516 191134848 940265573 662062681 412557555 483027360 911272294 843695936 898979267 175834135 798631497 279917113 294665945 173257064 75412847 187725739 94302776 702049509 33 311200895 570421547 832822629 683153216 650511046 244503540 146621053 373739265 398151225 952265761 972291723 618964594 433588896 164987596 153562572 380336224 959496796 363567000 611360564 243703641 724690094 222288075 885174752 759976126 259432618 257598532 146155988 409054717 3157166 646845887 711803581 207107701 129235082 72 538949152 897924132 708012181 40533851 622614233 73809457 259070168 461015977 798134942 894179524 985796876 473254788 559491891 383046720 543623010 835280930 944169825 706912838 63438141 821240533 976312180 914272725 826703423 442924114 594028225 898429199 42570445 369922234 867514032 63991876 312509192 293211424 137638611 811699047 604695922 936991367 347886249 40728008 119988027 727350943 104662793 931800219 440821136 139908144 512730869 246670136 211138976 25250209 438117724 368806057 146234535 801492374 933227134 731742939 168434770 495746817 298990731 290504658 212019091 25783838 786869932 760417088 602893849 295668038 48397416 43808389 272411315 606546937 104625377 398003797 889325931 231419001 47 890693992 963762167 867233734 386718692 82698518 385601621 671684047 412915964 868717615 826548561 882952547 202500935 754764519 105474795 560884751 266127322 325075048 14578546 20881580 150388478 580319693 994679314 243331411 303060973 93413946 323292809 637863925 288865430 550807757 739369596 191941176 190532167 790688521 868084151 207766685 50900555 840678689 349109922 597788014 33868719 320056295 231792688 479796953 62626078 162604588 745193597 711470382 78 540838218 301850948 149443219 924934453 665987255 902226341 394352820 564330897 159007270 282930465 590617656 310493091 940163660 361926854 99644594 998122641 242875575 17299890 938001200 317247117 252745125 464018582 4606439 476213061 418147757 290026864 659426659 412457396 948203215 907518747 466368043 10162735 858076134 884238978 111585491 416185587 321194631 953428782 540285184 695858541 566849284 388281042 248582766 915146337 844162959 836863964 820706341 149718622 61797233 299998086 622324376 492951456 997172568 128148494 835431558 604614530 799656573 373239693 47962119 220582234 305476289 254577366 918662181 644702936 937919960 728672338 541791105 220333125 778551912 121594705 666002290 752136659 753264330 270494654 974902727 341053798 96385483 410832019 67 62802009 892236462 285771432 481505626 298697363 478580069 959451773 363968885 186591026 903427465 445272895 580254536 774314741 687987364 85907551 630469861 778985146 434766617 311299747 281352816 191430164 737913345 461917730 129855365 496349225 739602902 365773320 645119382 802908880 85768354 592536574 791893177 767581907 718797110 234858157 443903662 255036642 86472113 257775681 584754656 582574699 923299371 747387865 317005584 5781677 419985686 178456002 405296762 308470352 865061734 968335684 67882060 360351895 23042532 175565293 505663605 687048517 398487897 404454608 831313111 636552262 594097849 102390621 547956186 597180766 329056113 133614080 31 113252618 788553349 526682761 106599617 48287393 131562382 717368691 314238993 468570568 394759325 649997326 33777313 832795042 934051313 407904780 249288913 239893563 670851199 822920439 563470435 521757316 471069456 881365377 577230377 737346108 573736796 398361858 984283932 899610470 100521135 251054595 64 918061604 744319601 114641888 409072917 153227219 513540831 231814537 564862581 231259249 349023152 93426011 751980623 633049385 763196810 703507721 206503425 213469113 144608174 535430938 966363391 353283921 400724637 493399147 723595944 627507210 39813639 925640412 780492641 684566869 254410770 125472264 59884093 635070410 208207230 952999546 792387651 470453989 905646294 733568628 942172168 575323573 674357514 518942691 722623523 773098625 723194288 371584001 256398992 356630060 347511374 31285581 102460294 551755937 224482234 357651396 542575982 888284173 54755923 491749995 327161302 450842925 517114388 883834635 237116205 6 510970585 205188199 531142045 210293360 807671212 903808877 18 372712124 517732895 734405499 324568411 133666182 761542749 650517565 762797921 493185595 592772321 848761581 360684464 669716391 962456289 715692326 333558280 866684781 224114519 36 675444790 211069739 436732775 681155580 126265275 149826193 541744484 208164432 906845629 340995279 474352694 566344158 604235260 250832144 420510690 171151691 587159369 202637717 472125045 684825256 911304504 144508004 792878319 541781737 138166214 89117625 932707462 880671266 950620566 458528531 274879499 679003954 686716534 152566076 663586852 788601684 35 370131721 412228791 714015765 418744387 629338312 740721199 871215199 233955238 596129692 277221341 91396140 578129432 748337346 954645710 362905865 856949633 855793731 943302295 988051913 584944482 417928094 424405731 232843264 232164108 357095451 155254090 104925385 857109365 411328559 322595903 83557019 63144103 278530710 831541733 49765450 60 436052187 609386075 430491550 886621118 563182255 948379659 514069253 221723633 775703517 263446820 157125773 638013764 554583251 580127104 528651198 864937259 141626875 464485803 679886586 92834755 684280128 581458029 208414198 216947502 953097343 745373911 393581311 602621784 194138464 639809532 946470918 890952918 704395104 702223160 525701759 993302672 243924533 337675574 61281884 729473892 749880085 928892539 431908091 825745045 895362912 410717371 415303837 32678057 824990032 603746221 47054638 792193525 126059840 330716814 451744936 519947953 368798842 133221141 669304424 558100621