90 86 191467562 813111295 41063789 322243782 435247875 669340643 582650385 186826107 371235756 112176260 857825786 263385179 522022123 441419644 987107203 315889067 686785031 59952596 389833373 418429496 149311152 71087947 922360407 80592087 211764869 918504685 727269456 556970181 104484513 267896940 920192561 987651819 617967293 514559799 929064168 116506036 864484925 957871410 985355819 971218497 697214280 850099416 389914269 557516685 546317701 904562546 771078160 127566989 142116141 86813315 497236775 659640562 205656090 82065656 675608629 614290662 16362585 257511455 542062181 948496358 449371906 225783378 937685380 695779004 367741977 765397176 472336941 308020606 308109382 892731651 170035161 255659033 27219017 628005687 88231878 80302102 356537778 771187988 123040588 280465696 993888738 75643638 340034421 962262240 753979494 747935938 71 281679509 320708442 580566498 74735876 598635513 704399055 860600912 668848617 771753087 21562214 140602889 515784848 750712841 111920174 758432699 326638925 294706177 772040376 862886719 983296095 992318718 790091368 163616792 311248 875872357 484878473 235492770 222145767 646202761 246565549 670136630 888915156 906328113 446998518 248507742 272758256 624390477 952285057 725823134 808924430 990451664 819896261 288179649 601520574 664477662 890248561 756394590 461759794 302657514 863678608 127554354 15543456 532925547 991706913 796512181 411490322 131463373 473010312 225618343 152794404 261582477 117042359 57676366 771009965 240461143 826181526 511992211 469822899 603144136 190094074 557878155 90 501131929 215738894 167176228 250299331 31459514 666759516 746102982 832354122 44303012 134612533 428101797 861488813 887349563 430792370 166032989 510273803 199188934 768628957 230663658 888254730 203937519 824939606 423842143 285685207 615443130 988988960 187977251 329667674 579416315 469116894 290661400 483876127 765944419 994536940 419781153 522534740 242366142 91596919 605619835 561583271 552935486 644937519 353955072 81969842 965894799 254087102 848764128 800048982 296608505 215635681 156556452 319213599 729616865 898694716 951462370 375999912 103656803 407916058 487345871 185990398 123217634 435239617 267675477 141402667 35264783 343165191 354219831 885107878 31215621 852535410 70856317 868736903 116930243 376515572 895882634 332448683 374412510 22971711 283788650 827741333 132424810 401503739 121010762 979075868 503096246 785604280 595302461 473797960 38079989 63751123 74 563075205 937749022 146502740 5463214 640769335 251378177 849432305 460568247 257403041 331392788 973771324 18310252 312787449 935750928 716361743 326875703 477968174 448068257 144665623 629155173 31008180 791115955 770766210 752088745 134138758 825558910 3904714 344004842 563513839 651807762 836354677 79402195 411057104 714035262 828885677 970444184 663422996 230391133 472825381 448054270 331389600 135666428 51165640 893985082 902590166 50663144 487328761 698559572 838821220 418974194 996498546 992963891 399220224 203020051 904522984 587599049 127057473 737723793 309021418 325079164 233919063 325081301 453829558 542813705 313459504 173670382 536057722 202347058 902801527 210073128 596809909 217932434 901068448 298522342 57 922375265 498293355 259699340 775605479 62066557 497584814 480285600 468996139 968204216 141295078 383585309 682658267 723284591 746387538 850788585 581700533 705568302 527210488 589529249 389459027 254508817 390642559 240568445 409388850 316564048 813057588 917952128 811657806 957813126 358256939 419701312 69789370 662167993 139450976 567257043 525987199 594291350 956457079 806097748 386118374 902963374 884095297 370333829 193092765 136166439 123093080 982558486 442907755 967278410 708890084 351380959 873918974 160598027 233300723 399208381 130705622 456224229 97 396463314 68663480 195154446 59799282 212003481 240266949 347859413 118536061 45286029 586569128 425041318 468016385 429948719 549493881 333525580 623950658 841875953 720775302 567328277 625886511 135217493 657662105 724563839 982755925 561675730 929173366 733660045 748740195 678442299 47812596 73058917 61288852 526726973 424238731 477659588 97738186 822113746 471775537 884681829 61102311 199152359 369366786 719898117 290407036 605078380 334787565 248911966 611198581 961350878 112791347 135362257 257235183 172705549 423805293 232645599 424196029 797056927 747811721 744598667 741184200 276572745 316640884 409896826 128096886 655599268 239599896 853077768 407234025 110443874 611998740 87137872 713930653 359019752 448959077 162423224 454096769 188444677 794811731 675647144 620689884 729585852 216077662 372667695 366474939 302159324 341870499 927470896 608783713 339877843 19947795 292851536 264169123 742461922 613281079 711037278 668002806 380970316 65 193452138 157348165 855775858 996069614 373792119 353463253 919810965 626969522 138718451 434570883 233497907 622150429 585821400 914312214 529377426 570062287 333497231 339020260 109307513 370293652 71333840 450401426 15834884 909398977 278400674 311044038 254062159 395424215 505585209 416067823 233502452 413853060 988896744 27307981 423789432 678816554 475009970 379399602 306051937 312399167 947678185 161103673 321700070 209045829 631937572 720861300 657320429 500524482 791763769 418652047 704529042 105595895 422224331 538476371 8128671 637591829 108623310 59525197 817578695 521720870 384879731 93672504 522072753 61689892 633937198 90 371460405 658456041 875926749 537957745 801973751 745620894 547754500 880037685 54913185 517459760 310520384 113247370 662465028 89652536 756395733 247561551 560347171 465650648 631089593 784327340 213040511 138373176 458001633 995343762 644708895 29003763 692650684 562700382 583408391 91837723 208213608 621523333 689848957 357154287 824905933 719686430 149215002 723164341 861415250 113718795 800352756 988266118 893383056 18975867 582362816 504368387 227010147 101946020 555724508 2662974 210453745 225947313 579290105 430541774 211244562 560320356 26807165 222320840 882839646 422182858 783135765 909398845 588225189 404214681 240796295 865760238 547970896 780030990 897097392 516807997 301656051 645227359 416059086 717635783 528019157 89798594 119529322 945969331 562668444 820708940 885374811 514595692 562192953 582516479 419650828 23671691 430547204 940959763 310952626 954749427 51 321948868 825852948 752012533 897705757 630553408 680674027 711979936 328024139 765522838 649561650 641000979 342318613 368961 404579730 376257549 96172813 632286241 431592621 18369889 969431118 58506806 210993809 298187503 815446782 915517517 212267935 204598534 191034035 719428065 950636610 215944187 189173138 396274054 62082699 77708437 279652634 940379060 604897428 375300748 714652494 909581588 939489864 526223277 611017489 683640589 258887508 56737841 89373468 69899013 359567692 697641700 89 981748193 198853672 849320439 546202705 668678750 736185735 6645857 228381310 323283302 766540519 590388906 156501987 491572471 736666011 565424282 272796066 870453244 113036745 964249311 348065066 402331691 279010675 844073617 129654686 996896235 147902245 170892514 441614344 520724774 360844059 118084870 354191657 149652825 385987182 467764323 542255580 74901318 899648131 658699150 986791472 736963999 648815208 798280649 950091088 17255472 899223809 424580554 510905673 226474465 362349795 658857710 248356737 504789174 227535437 306953915 183057682 808780275 989430461 891768752 274166511 805795611 159562869 362569315 515449392 614748147 763458149 937106257 275741683 941888653 9674900 342162366 426879401 593532314 484028772 994846886 957335881 133797099 455146936 356161921 81784539 358177049 716929557 18158236 505885443 32557421 825041998 142115898 491694682 831846907 85 162221401 502896509 108163843 981721618 863122504 107037004 367070356 918979922 853819281 424313568 902095883 835558610 636225013 100977524 585543663 495936698 724179237 404027038 254004787 504178465 163187954 105718004 767117771 63321095 16426628 752416198 640873328 196389716 913616937 237632158 341366244 508327089 990785139 172054474 473091570 388924174 880214221 32364213 15736502 546567234 587550030 270844215 795566154 261386100 3244443 877539527 804059570 33312405 894133711 482789846 257515935 700280752 174255583 785261805 917951862 623507890 687545603 586177209 229952008 538629330 279964782 640580124 555283297 161569346 11291495 943142448 749387477 209365583 838308400 195660776 839341904 720604360 834505134 505950887 903596178 151439433 717267379 26572498 959937822 719710329 733106226 346527824 853429783 39263328 755053778 82 48908926 386276372 855688048 293233042 878029894 758343654 365297683 578306346 717519321 919215139 563968551 912400235 201989007 634327961 610588295 946712185 273395899 314671303 549554063 241226253 8480377 596912810 691818207 938044117 564796240 344686024 812427300 910234628 14760872 193037159 89497422 333929030 291255100 658830085 670216878 944076444 737673553 138472534 660531480 34654668 697967094 189220161 111459085 106798676 702125044 960471171 459715175 669725632 521742573 855303033 221020801 41640333 29799921 593432882 29716198 69068430 971981923 805892795 288336384 295203197 183573921 78184275 822174216 206469579 650104310 672240924 267034597 625331398 199595295 35223266 705148764 398637461 120871380 911482643 266176846 874098783 763796212 76251977 233082153 797524205 708164227 363771096 78 251474076 762106408 26320046 203133900 35092566 918616953 8845110 137888898 340690829 319357706 973667639 298395198 267715940 43740227 789444946 847742465 207488842 94773562 507032793 173709915 969627599 267272776 52325900 756386639 260268704 352708651 362831321 292255661 252221606 491718061 403554933 855284732 28954584 901840407 925245371 173996179 654728431 481223652 30050660 368225340 297163102 506162646 152157978 67869366 887110631 67034198 970266207 234246457 849266648 759142568 47047972 186346865 917271391 301458939 233020435 629410064 268446805 569567123 594757277 955403365 278170553 564122892 252779156 468953126 677237383 941721481 148788565 431754736 345273088 112440953 52166584 327311201 727981782 497107253 35379562 413695698 708261889 128299031 62 292903329 344345744 191280015 969588266 115698061 504602062 668041064 992557316 152955161 54685836 386157403 451901974 592543489 947762870 548052105 269659806 235819503 122172789 883939761 637112919 199200013 715715150 520003119 666389572 495812910 274005345 361204744 272972440 45588072 552787076 675432841 358850383 66666997 351553766 870923907 458659608 711326357 416651418 696364562 399925362 338409919 393556361 733390536 402291999 174902800 568891629 338934196 877786434 386463350 200356509 602086947 589882698 257443913 744877375 167755824 624484200 31457285 474414943 487862200 102406808 471416929 733963787 68 392992681 641866704 145395675 757404596 779086404 674284676 385185913 617659481 102810474 382475210 329133800 638424195 247796941 386674391 330787210 786623402 923777781 202329177 762312715 83614935 859594041 936565310 725622065 633641313 495906269 851750348 453263943 292438991 222514267 716477338 849427384 377632249 614736614 845668756 124767464 308000216 22404384 930021459 235603009 715736305 624605061 518133890 903758308 112526087 641883639 401865356 711841776 317955115 782625284 416829890 625382520 950327654 591938173 322410726 742097902 215900845 810647947 842326797 321362567 243208628 848473009 417607963 926040138 716890839 902118692 168570781 172694289 49416473 50 871643761 494135152 16848675 367651352 330264017 408403285 387902420 663067991 6606757 970453197 404549092 598889651 538312880 964104368 513512489 647339255 475095174 615678628 253960164 94761541 134170872 834286738 488361345 345070309 419748994 541907091 957171951 45725301 612235720 523190753 822624993 945628917 852011716 359782339 776219220 689788996 488704068 508133949 248543440 472989271 742451034 429698293 994808078 808353749 317103393 989276958 452181699 160866450 715136592 291663084 80 600514974 145810523 622255631 265815841 633054254 899927473 219349845 295881330 59155534 415122926 261225856 756817926 800432139 826946178 441867393 120014126 832338564 427748142 514522684 260126857 491463676 832358993 827059370 931202640 848002628 557421675 642475786 958954610 962560587 829852062 130179888 759053725 68431396 334995918 750794330 536434713 237564283 844707197 511006436 850262936 118713964 568039341 287876874 476079350 417321786 682773297 735410856 916547799 955345382 115697421 854342554 49400670 508511714 774090841 26302560 225931164 430199712 113045219 284703480 648885272 732395433 233644019 83785600 525796134 363966617 24342102 342671025 276142370 198032911 827436203 983246602 145102171 17644357 208871345 561004373 819074500 337782645 356306342 629907297 626453490 77 407335013 732576641 258874972 361821548 654181427 792191173 844580742 970418046 562096585 880285288 320638765 509075162 882043469 241896515 377848493 373437113 610877222 287586958 372892198 110613868 800750697 248638546 357867832 925375661 530378590 417077839 940818735 153549749 792806984 571478286 100862109 659536457 358128772 671766221 668129336 722003137 515001683 378543809 323531998 338666675 750976763 634780000 51184083 304311877 932902886 686824857 452864013 61108716 197249215 736258729 131672133 540283995 336374509 368524077 298691322 193990179 571316108 316973568 842317701 795698009 228759258 340074163 908113332 871302120 631116507 23977176 562643242 83773360 792560879 753236485 790461274 897344460 74166738 907593431 693834226 997770305 580883491 54 526337358 688270047 361568317 240803413 496762918 370225170 999279335 958593713 55439937 803621609 905440788 358510649 850594741 394963458 739708250 281952060 981716425 55899179 881450396 329816410 751068806 139758872 945513402 233371213 167878228 588754462 282898465 559446435 875824307 820048831 414515378 135021228 853501170 886964928 917104857 193643520 497289838 500935411 602115658 417909169 446345105 31493718 334728455 715264654 574195634 590752632 861434049 555714267 839855935 167270103 878392451 612919982 727756931 814936107 99 312771637 520145659 756122231 260988154 86189886 73603729 655630074 847521558 272172478 908779810 898063934 509510399 533328752 828949382 397122897 442489044 263883377 216469683 16815927 148963003 361261530 792537166 641940822 379137079 642364764 977514149 277798484 635497887 318671290 413207998 11645766 684427411 542658203 280787540 459852839 254105401 883147543 736107561 254311451 72712613 870698508 766338213 982143567 821853311 823736933 855721668 779823237 651789791 768331703 392424580 551790725 565382058 211034428 102930616 883161881 376393452 119517866 933724245 478925310 703931553 880695300 361134199 703493483 428158060 530371631 5456556 787610741 776381859 406190054 897227383 462258043 905396483 26530784 701015474 736503207 451658420 979605571 861836739 174322998 683530838 178627551 779126307 356641445 436338535 55482608 618835902 254428868 698501663 12662669 863165535 856871628 146006511 430880548 983388127 124917505 349556345 952859621 152524719 110103363 86 708410860 588399876 714542188 834932097 715543585 687382421 179360973 951896596 515409700 782045950 345105117 888875388 717689429 481372351 741123752 176482456 958119118 310557003 954598228 468622514 537602232 802249109 789423774 59890229 318410966 250287019 424974968 811404021 880234807 584110367 742447010 88015748 20734792 776217285 762347143 765274349 110626685 682251055 688859846 370292321 192269154 373628065 60040926 77012699 736550299 93742720 478538213 205214775 186659655 289736146 317235474 538298875 853689758 572443500 713431577 644116957 978988492 495706956 822998467 779219634 251568793 641402651 516525713 269778371 438172498 180616058 779984951 358100592 67759554 883688323 291184346 800017151 636448417 278189164 49322339 157477313 518607776 514240620 430568120 550659877 831749034 430582463 758998173 440982804 820645791 7949464 78 878975543 719626368 984546232 252816687 778399252 610495489 265592512 207274457 452297730 891835545 243825975 482239473 306125246 336429618 35887795 925754843 419753547 944339527 905048572 907301466 703729479 487787038 988627430 543616608 779188232 716466811 836277921 933785051 56967828 908843669 822014409 28369238 448330043 974717607 438690441 172479724 136234902 25016220 143005409 234390241 438549608 568042387 622400443 777906252 144607451 525311859 740178930 573273332 734780156 727689452 499367534 83532846 888559729 693592298 592019801 342338616 398157349 455536215 946580093 264403011 618435526 841527235 691636734 944168617 901182719 466946555 943485932 901757749 406788838 8778056 953474789 282296735 239194260 797802525 831073085 530978359 377212278 450858755 89 722720455 631128320 861294731 214948785 90479789 351865413 301905071 135535866 457717455 781000658 557746202 958541297 892749081 150013956 33182560 664672884 935715849 884197571 961726208 719530186 451986124 280326978 662210755 341036918 322972168 175173255 923807963 910002195 724611391 193733665 993492998 259726888 385661541 486668709 159442410 514980601 415713197 986538611 796150035 189331867 850974486 637852965 300174936 433707490 936107409 523630646 511963876 522628599 134462046 483667483 361090028 252489978 611814786 994584211 990449507 99531232 172940928 507571254 377077177 763868950 909019655 799919190 337732127 972538829 829903521 813077063 481731153 822191674 340397374 983612194 790864378 149570696 52344850 97365619 366195381 150761392 504996256 399263574 954552064 46600063 436294982 256631135 41201947 19757012 653436911 196405095 7080548 840331112 794485070 59 443291035 756948097 495262528 180447942 571107602 144562907 780160930 534912427 420352352 797428446 737473483 252566858 879039438 992914677 461845714 939805998 776437267 123822384 911704507 734133143 521676168 519376389 516592716 576898849 443815195 259274475 185003404 984775156 977064781 504963077 550263404 223493622 448407797 18412381 784267810 959028125 393736003 23952112 659828799 958406762 410109079 965332621 511590762 652316749 634049835 157333026 515178156 941649706 131088100 746738813 196201221 664135056 684884444 947309373 281784650 266292993 918870448 382651449 703164126 60 155459573 226057269 505216873 607735609 917114001 164806942 848020512 497632651 923595108 679033713 167626771 268876866 330774603 194698113 872154052 966029575 504397692 286006859 427977839 463636222 363925386 261743401 160035847 744562155 991427534 605707213 206800889 827326870 17727180 228866842 91203534 533644204 196612240 27560155 429469696 764750745 137107557 137029478 818916481 344221867 312587505 995977935 582043231 332887479 74922565 118686242 170992243 518006316 828150073 260806424 344368359 592361176 344917645 34573555 714525859 148519634 497490936 320658149 88658652 358140249 57 630676580 109718019 58572180 304087101 643353121 649359855 694757300 936791792 518837936 528896022 134197455 669836390 127158285 797719361 956974511 110723615 386695602 477807372 406203699 538018806 359145525 291861761 279685430 873154558 690739263 582389801 700495089 542287414 668316522 352273534 653211903 1742270 319413056 963102026 3899208 417378304 27710446 767976539 610215605 327687480 144617957 335252146 802237334 68889661 439930116 695212602 879613812 517421928 311787923 289336640 195118795 370502975 883542148 707669453 588028491 434301233 771058744 94 517886909 586717388 764700941 752519790 473028286 572784831 623360820 391038684 423227069 922030283 233942203 337150438 208973982 673248857 420974836 736563974 52762780 155503350 751411994 736209400 940316429 405639556 924088858 56272730 860570339 169615078 728267582 90044298 914816463 53792501 680269015 88471044 748054254 234830977 886017722 311320440 610436030 881728364 966076232 407401987 613096111 139422702 790090550 714785609 117273597 225110375 14826259 971423671 202889691 64087264 979016627 960437665 530019761 693260017 976991204 661768575 681284297 343328885 674383144 215886339 651469443 375338595 703910989 384895557 746490184 110988561 960883783 545870523 227241342 129655525 181158489 426953248 716440387 370005777 183969240 686469014 189335873 877491822 995672989 311775199 912266496 948076767 230579212 451622578 92970734 879717583 338396428 638931726 168565259 159223474 175173945 780613120 444333693 591994780 59 210867919 607075892 765857587 474076380 306257595 828403691 79810414 556606620 35433366 643904050 822420094 742415874 784278416 334532060 782072760 703009762 507681391 507182973 858274910 742963054 305918150 617404514 882974076 9632430 460978354 715002382 160655345 806551611 408016266 880519491 382072795 317598954 805207461 232774204 170618696 969824752 874887497 772428878 966488685 893137677 233117902 795333548 539925485 147585403 259493964 528944677 157878799 778494439 855977218 235888417 392131984 258229599 318280867 652278282 290394958 602388386 196818651 98494128 984616318 97 25760711 190683706 988879600 788829211 694529429 651236645 17611656 693767269 3695985 530890303 574136834 939829095 769541983 885938163 135213827 754070825 528297861 473539098 32875689 44013123 300364089 565614118 39214866 159062772 690280287 288705606 500788830 544346587 244297270 749070675 739029031 991526067 276263348 356345690 379327316 666828987 922096621 208974846 966372111 833640013 693938238 159507932 909685766 940368103 289284712 74377136 981634856 302886938 550922040 546603409 146712288 222482738 88986581 976227486 769463593 39496782 775546125 99636236 91910 782096038 615959005 462799682 311716031 956567393 253476455 644808328 611509793 449664228 980462158 147357660 700077729 69979967 215163695 598066603 770855971 528635967 991064790 657382401 126277257 418451327 992249747 366961355 539002021 431257181 503150847 799653614 113029155 880768705 657488003 117589371 924264601 453144984 755849868 674582748 813732686 518421390 222597285 53 825551546 161122971 193874720 379739977 518731358 73481696 460379262 622556530 787016665 103458344 466865093 991713408 669951671 731568029 352778967 177535270 597415348 338019594 10885136 732646232 316830299 769192860 235854108 70099283 842118422 172429592 971435089 858402573 996224240 913488783 679617089 420478348 451705473 286779757 375398362 517367975 160936399 95819650 416333819 168166231 21556564 548503882 453158500 322370360 141051114 456119506 190220636 469732429 53416331 37567862 154312439 817016774 952335776 92 287924773 403588171 7654627 944809536 645212984 639887272 14519641 621487867 110048447 564708359 910701653 34475613 77947695 114299024 6833530 46389324 751942681 187234816 746220158 530975898 226756728 573342078 519327128 235950479 631257611 644536962 506744918 733075658 670048265 623527595 912990672 11723623 644743903 730755545 906469820 213137176 847057524 284809300 792051705 50621501 136143757 227605327 15625730 136562479 301372578 891351299 283063535 717197520 917026022 400170656 964798051 736050067 259972858 25899383 714098568 802591515 13431880 773480373 557537925 732241978 229423586 611195165 265727012 183780592 594279675 96994659 99949207 501078715 48900360 93954708 841205411 319492177 326608962 134979254 739722971 737670919 262999138 250961541 913168760 761055233 473121553 800737780 699021609 354629587 94109003 641479250 967144847 93877454 513706156 331897759 605027205 592031109 76 67853986 305708478 419917008 505766666 495302580 930418088 683180156 399799415 88061444 778145696 767374723 217443808 143280215 612150412 299967294 613782568 176616823 699322285 176900880 721995807 615511714 627746866 604266729 796162688 223011664 372581701 108012493 708480404 470924226 422574847 295689734 773593721 286440763 331646034 991099533 313598041 191395572 635243344 948627987 971131005 305138363 223409736 268107576 64697094 417065870 275862374 440330121 201311831 243653303 955640934 953834821 801683863 173966186 929677242 821792366 849033888 940036620 196096961 859574921 815388988 577878102 573151147 395315509 546628131 379319010 660370588 744741265 554983514 723690837 886905329 256425564 419079311 453630097 804571940 108554479 93190277 87 478202811 907495947 496749425 278263888 442447637 218571675 31364508 333723639 160375110 658728272 582641084 886362759 29385339 787168356 299996287 955909805 990341510 253645187 490018934 32801806 278927134 269851971 603703034 956410236 672852849 444804788 172479350 644135438 585366918 785020887 503690220 746547463 870041246 549517095 883740939 335661786 749523486 484845081 720646445 317096557 515244366 118731349 943340739 443012520 188864247 556760275 795678391 439896348 745743166 611512685 722413107 41053941 704043 695061992 752843914 855920121 305688639 49072117 134948073 999566721 720601162 556174230 802830938 108275271 246286823 171129931 968639838 516133457 586787303 854804075 752793793 458643154 186307064 184356799 536838369 958633935 120454753 635487272 152899431 964265438 493002719 8997423 272148301 576767579 198603131 501801203 118704417 70 14702833 921439189 660168989 699012320 823435644 31263705 397218828 584344471 561565836 569077007 361451569 396109002 963512963 833946978 480741367 67002143 445701064 160658455 772974227 517663098 116391459 93478208 392625767 556190439 983206177 388044872 246181574 752119957 606374545 655981751 665153868 584799260 685692268 690568404 918030513 399081317 943313378 675220178 195407595 404558205 916155357 188112236 838023821 607916103 525140826 605091849 557954917 317906120 442503990 558513251 316682150 761452913 344754167 925695748 295624592 372107715 232324398 876951426 568400163 257359613 800416926 144023856 657105924 124902768 244216173 642106015 135811252 701320705 114968643 330165262 77 562817437 855292468 930263339 808547399 45347926 973255412 425587416 506567010 112784559 689489200 887122083 603995729 410197393 482960851 701164420 756151769 537693064 114144580 802182494 410111127 271992160 748655378 329202402 330763228 52091776 699099306 360475225 791607646 696928158 193500969 493587220 917924419 804834971 441943742 148305576 390531312 957354925 203646689 51843690 935869877 348858179 742174618 801401440 133984957 923536694 395822286 435409967 974750119 733308485 149744659 67818599 159711817 184480870 224085633 666502386 927599005 244145422 257268046 579455438 996997736 19499416 239892969 999326792 324621209 137667870 841747900 983182284 937417486 22631093 207760651 127142965 126503977 574188362 614631747 697508706 431310201 186289686 82 583307125 450070693 428173363 702311382 499288099 980895464 235852275 848662487 42306803 290385016 548295349 545607921 220195679 847379561 509834924 193690971 228363939 482192883 989668783 378865956 406470736 515637654 524492139 489530570 628566276 815850321 837441765 807623711 445974032 836726440 581387726 130535172 84200553 571142574 79292804 935485079 674702651 310973459 245209326 361168676 284507331 263683589 407705715 883394206 640135831 402370754 616542368 652534360 226783119 9602602 963120252 931382565 262074698 259687340 363948583 493120642 788609256 484197238 397565332 446650894 900237737 775923546 453869637 226874571 867752762 804626237 713916612 545590463 785253287 47386137 151948153 353336453 73061957 75904099 20726754 243956981 946779344 707052998 40657445 205053104 818143845 674579155 77 659271623 193762778 319640264 250745307 789300534 929437515 588173797 102858859 462251792 571329553 821454340 277643763 961269871 372534215 349772630 977957397 51940145 115037322 450497853 505443926 157849276 309425294 351684641 309114124 641942266 891068943 66981212 580023679 601881671 395608174 208947933 112459737 442528622 405751109 362151883 638655459 984050602 267121602 495283290 366803757 597453177 423315999 518775404 262576726 446596514 154805744 471286524 229238564 950102801 644949331 589105976 692393030 184348497 57413852 75612456 749347120 824155205 301547726 722946023 901215032 143109694 993078680 334949773 834724582 106140536 568590210 73846778 536038898 647745482 861984921 133568786 867602388 232432367 199906340 208192028 687618193 987597829 65 903148140 239309293 897438783 19127646 800510254 557030029 381114755 133228205 365393657 127295336 936089226 111930560 4819269 415551495 439946910 703011088 52960380 824645112 437437755 599080664 477373671 145242977 654366309 172127489 235258721 426177011 282433104 293690325 22256199 902791760 586410971 837233314 78688863 304224826 280214218 208511928 674684064 873521367 729389036 790774900 739908213 987258694 692781650 974501304 359788453 310349818 348383435 831612841 680448139 231647320 711081693 770390484 452014974 687499010 716480132 214146385 459643013 185732592 67140410 896777426 234514976 898173069 550738114 111248091 577032734 84 87964879 27274594 680157109 480350443 509810018 386786478 16851613 22497019 349261146 535495224 549095431 937164007 160652006 28059363 294821296 75556121 540797945 371220508 67393108 881018751 41108658 301040665 991800295 669536235 162647675 854917027 194496914 847182390 399805431 53183846 620310258 657553396 7927398 644295104 21983542 106401167 685926981 368498288 663209251 405052068 888047366 631173515 293813048 488475643 821183555 288799047 4494304 167109276 312119913 603579528 454221307 713518672 282568300 673418966 409866246 566638601 822966618 921272447 634583036 551557706 315617010 241914740 531052386 384176630 596622710 935880227 91625118 730705802 410330174 402356481 604217600 4228731 6327659 131940486 642066038 7715985 960681646 621438762 418946370 285055121 15586342 939916021 839619952 283370516 68 422882865 674310645 843678928 898714443 380503771 788704528 709045656 382655619 433367104 465914960 952264442 325416177 609612246 418828046 514933404 650373189 325085915 413432691 73179396 400986577 47441447 347914078 951696939 169114781 68290136 632183631 327155326 961820081 304402150 863903509 618171779 746280576 552897061 814687599 335648520 712064912 588396688 631073203 937626892 481969132 506352929 220400963 74887046 575738861 514242767 512205901 383870411 534277244 746943634 337363367 237281526 196347116 509515730 732892435 175919123 965066050 624629385 318494434 655895373 579287352 195102069 725506964 631125673 782633167 147654858 675117512 579522440 396634881 69 814151592 810323560 436103263 191603159 681064894 972844882 874606190 699534042 443822307 818695716 27056720 141958091 443070577 206335467 386695698 426718494 822587169 190864079 138533687 673439964 452430617 211657688 367417965 197727053 482891670 130620633 359339045 951614664 443519943 826192276 209905034 375457139 949592135 933184920 614320768 763974870 42855076 700973980 313326366 859944558 468107747 379997741 374484413 41344015 574685576 149969127 541566309 614381244 532367325 239428817 757839694 486933842 223068661 666218185 751561375 589190009 559954676 422065565 269024809 48345460 563263537 642969662 786137481 575489261 403604302 439636159 869047207 999890287 942562608 75 476099301 158531288 402594494 39947121 804546031 989497117 807406117 949993864 255763031 990808455 249318053 583981686 342674157 495797920 335741204 336637362 71170993 834029669 170450408 844413276 769778314 264121019 906101260 462179021 29180258 167285424 103739104 921929970 444897607 577520567 91030539 578540046 226285218 400587013 919826053 245710838 912804770 927286419 172729242 84456461 227823947 222485478 576343626 719609097 879149265 371192157 34686303 374449897 607409679 427211274 137337004 430798131 68280273 73651985 295617602 261262633 632876262 203105584 382679494 505562633 149188162 211947925 822630526 788096952 697264657 81248960 137095641 322657744 179863570 900375823 967358864 444686279 973672221 281706131 744769010 71 520334736 126877705 231397534 110691106 115236854 578867951 597816975 598744575 640496607 476600001 315780824 863068505 897307271 460863992 513276678 571812112 114350724 39267695 179317386 688587168 256956485 227752903 375608339 444497210 795483780 193476995 671898245 605874304 311621000 295848610 937962920 958137891 657034877 223524724 726774092 762148283 277503760 75552818 614135369 292850088 402583316 808906596 86222213 811165579 561568047 871924207 779843598 42818399 450380923 31728962 536192752 50586485 110733689 781462334 684242728 888398598 603934331 288304377 33400794 735344800 726844187 57080582 27227261 723146200 224536699 776774893 817322392 950064658 130503061 510367192 509839239 55 302776913 212990048 78299139 485729957 314736551 816755362 926448049 143597108 67804039 287577681 959581050 598278686 849124321 477906320 18450421 315987638 437166491 926026477 894365859 543767559 389754618 676317218 108287770 909809004 286344173 310740745 468432995 263724445 750065121 879076408 404480078 159138857 679489079 561564662 872350242 734213128 146587804 154063185 22586247 948036204 184435678 383556888 364715297 408853653 695196735 964662254 952064037 408095291 857459375 257505286 330068061 734536918 977569697 664996642 978627604 51 353904712 714221880 502336124 737098981 402573750 897106454 538167731 834666958 189750194 15487075 792755359 151588336 926324887 419877459 745508219 819683926 306915276 221948368 765088104 798888946 30798989 345291206 462745424 379434821 568459395 380685263 365796221 200412912 7852444 751816847 958976619 339284548 114407736 420879115 80547735 783476131 82171816 184957934 566403671 276491052 24895161 747901357 618760814 2047306 87906701 658959644 178874588 21387638 508709360 923406913 70500622 50 555319079 281253417 476399489 937454778 538346757 90432431 861682063 686442943 787169725 244722286 55291418 392835804 623699020 415076455 304487823 379720701 90651911 722121055 717103139 399732114 440396772 422401684 549505316 319774228 301173702 73937697 153882621 151644746 889161035 998895445 567040050 110480805 532430910 734377240 78086645 90560875 328406113 710008816 26907166 396690935 101538625 314225465 31179330 68875874 97639935 376903838 783259092 134359143 62800465 794385476 69 938331154 211798843 654836665 594286320 532344602 14687840 841793957 492331885 91313415 444114819 394742045 357715331 998747473 334361865 305762145 652823563 893643770 649104667 257219795 355396832 951031382 98856172 664519765 536494820 646685323 863727327 802872517 470325484 709658228 925519975 145688620 243146408 984060921 567097859 552238087 391751331 440724741 670015410 333455528 658651674 16534845 676660539 331334245 192727886 96469929 913173324 609684319 622092632 20547418 126246845 163161604 390362748 712364919 666314859 699774597 920141340 610354357 839940399 34129982 795124924 30234822 685741287 688858015 176943850 472891227 487689604 605590421 434961814 719037013 82 876704657 132588307 964999854 181093749 482380487 745934749 282943055 972637120 104116127 422831519 795067565 885846683 586374008 494091532 518320374 461512118 497008107 652330646 155492730 563764733 490841854 857073727 65905375 712430327 241294402 628590255 41928120 39608857 187256312 742111161 874582060 32441879 791860352 510758740 268418799 504128009 188478135 121756751 767723993 118212895 323517865 901681797 846168635 498483548 265541780 100567463 91570673 604893180 839609068 710749554 172905607 745507009 563060414 784366303 575705625 566471061 479738978 286120744 4529507 942192990 513878494 270848655 562896933 647982120 345480704 187525498 829945950 139227755 293577636 184474493 656955992 43821963 407765233 374626774 261330029 76990386 6222454 873584398 354245013 535628029 472279782 104608968 59 13694427 931216162 391243294 781749629 256838435 29018289 350150876 474136938 719408136 216167159 574288986 636899582 744172370 206382980 363962917 726045268 902421689 805327043 592811726 564115960 784178608 509387036 44033801 496386997 798916781 166349389 675625864 213913828 22258808 178881710 752597407 954771534 252019190 623660385 744393439 257454150 84609447 594682882 891029664 597860507 803136685 422141548 626428029 728898645 29217998 601278828 457190852 362957479 5592 52349704 452363503 482769398 719558573 513157643 233556875 9936160 506297777 161251233 390038302 69 286612407 786233415 119525169 237371680 416352402 847503990 647235336 869295378 913208647 577023049 50575161 655049324 462109623 541614022 839589390 805119921 467028350 550350735 410522928 935810193 976181704 596336802 26190343 304480310 883230946 37534321 132685893 816982630 905182346 346595731 531343648 189050882 506319697 229810387 550574595 524056330 736695036 376411945 916576230 216507571 860668038 127644532 618157663 786491228 469113414 460293801 950133522 490021820 131737511 144655526 454052489 595092275 35911230 468127214 970141071 227911762 961574782 946322037 113006416 561857953 803201744 107357316 715498417 380124977 455706880 876439881 978490375 186588884 981797319 72 997084941 935166291 156189358 767635106 612117705 923070606 538611896 356832928 103414638 627246613 993471999 393252567 374836598 834584315 48128329 685284602 973960390 443580903 758345465 822231783 462886361 9457338 561213363 585340354 39350915 379167615 618358165 288565389 301615533 11631860 282020803 579932711 678085109 579573959 895057123 191107107 45274365 495894730 122087392 57577564 272146637 408238954 952446441 455466081 999336067 108956515 926449965 905096619 26140735 164567799 254361142 360448231 801959569 622112587 12104886 299428678 452795557 965969520 66599152 904917242 238634410 558678782 925860128 925730631 96850475 792184083 429045412 154134331 896743805 326334830 45915259 498753717 90 58201497 518323967 614286801 868764627 364850902 554692110 792451667 901582422 671619138 448248659 820844016 934656437 282247974 477777548 18536623 447125863 591014415 890951139 433539381 165924151 2915759 128657880 225557852 987076524 738218121 877192268 129169906 825752638 147687726 581326007 686536414 238337825 924690647 996725406 592913919 873418650 388800818 534225806 746828219 380316916 82826611 662389240 479785847 376653204 640683806 933990625 221085113 3768194 755307524 646766158 28511732 554701706 106237424 694622339 785618666 240901932 907001440 720739500 637046905 872978959 340137551 203935383 885201958 391809193 868921890 2603271 92743147 943956937 299032469 935863363 438213850 628231442 63813001 297148046 143036068 8271752 74764501 674998196 86528463 536375291 967302627 926182811 813161642 409633843 777618654 235400237 224750206 2201397 403535965 691185679 86 301907130 855819336 725357867 344065181 221790749 374998924 636600508 321916950 525750213 818612048 27851140 920330492 548816343 824538350 502233700 999512804 740531378 939972999 844029915 780249617 616064246 894212297 232731730 582889608 76831657 113308066 988964918 456214727 321674838 231309768 724134433 831060475 684399019 618135589 30094845 610816109 624775310 224987680 42960342 980719409 690291591 973345710 140916354 150427720 36674582 227119590 997491600 37158584 782854973 303642107 351278538 644168102 716988700 272531320 150957379 46067978 163314762 852064957 742468183 529264265 292997497 93254051 156382332 328394033 43224325 515404226 634049327 738118023 920709823 430168857 155852057 228173931 151198306 309334301 478670267 560331253 896423252 715408007 357775367 710215292 648263100 357878743 767910821 220867439 984828325 647222446 54 862195645 586668881 959267110 798469308 514223276 758045739 662527849 906351889 199346925 866500494 74155941 510451493 567913676 894896957 369437297 712297002 969677720 862791275 679524861 402625722 45709795 392459050 812855689 417317849 525952315 892013336 608207050 597902221 234536516 306432762 605414270 25230450 176042684 376438857 714197612 476975377 53852767 19882679 352888636 929053532 30542028 713967193 763296829 292803420 983819917 212031117 348558902 635039663 110110488 139421326 92407476 152057165 901698726 31046752 88 942779579 336890890 550767274 453181892 402612486 794359210 862772317 587487747 726597194 682211857 966754083 311831058 315841324 933553137 171642292 9319416 236749448 761813005 689307624 174500102 430253426 126745481 546056216 39717752 483102955 607200071 933430322 598108206 150285700 835795881 422529651 865812418 653890947 127392393 551838305 304240699 653847019 312742235 319533665 164549753 165381617 37333711 406026560 939116752 381899195 933103075 855824189 454050535 327813198 714129852 645102531 553659406 630773130 967474806 86123231 608880343 751797101 193439602 850293365 614812582 20332575 138183500 648117391 447393214 157553351 413572964 795186251 463895300 450362224 49392842 731627767 246810472 449546011 190933807 408190335 217909942 32364236 601780134 784694593 294835278 607816562 839806514 412218657 820802400 157858667 334132282 967992320 401940834 51 30120127 945470421 927342775 700886324 795283397 734606546 826569199 323358557 18353468 56876489 906237493 475447054 20092960 558941954 659040716 867999342 940666509 634487681 425875531 803646207 663169080 972553265 815291704 878966056 99388696 775807513 340321140 248174527 731798352 406308942 527574216 977611775 345243430 123902167 66822557 399210476 747248630 769268021 852661079 277816034 224628242 689289374 635120745 604208495 30587040 554782311 205734563 145442906 44414905 165818374 269520909 76 626222589 82127577 644487563 15719941 338681286 165300769 518876405 742471512 369576711 715651572 671994549 189268438 28063480 119438598 631778134 518794253 119905192 779666745 982083183 298622304 142175893 989945005 161184174 568753929 982233562 599763104 113940362 354193217 535793880 985609313 120527830 381158778 174343790 858128336 233012071 728969849 915742819 115935829 87661186 394428560 700198831 779828537 260257561 92635402 809125091 542156319 400358169 284232282 318850821 139697742 319281124 556536371 164131312 496441449 373805516 177949362 660247102 229348554 42216908 898743812 451566755 875370759 391558007 880708145 530794352 89898073 616041212 761442955 930687494 485294514 511318066 54438033 401235565 176463756 160604203 858299747 94 391305367 706155584 133001668 296511468 825293034 69748672 507958988 495871875 793015585 708583210 786641076 161132996 149471751 197271025 408798109 721201823 337697233 543506173 188348619 281205778 31569695 501425681 223840347 662089589 653277850 734636545 689304944 870997630 966592190 129861627 725406928 472457776 622496 751744713 114981137 616209732 444291534 292405521 638355289 485497452 923054504 957880418 39221228 497015484 545516511 394005145 49794306 596870460 763073052 126127520 785016714 576359298 203041147 474179515 780497122 658013371 923519588 750539219 872581408 400332900 31086912 65851093 983413825 593024361 822980643 262926745 946020623 596460877 305588808 668389145 379308910 115352732 687244121 626146478 797587244 23984422 84869989 206288272 525412339 115756310 438845285 147488050 576701980 479576648 500598662 208143219 333519032 492205963 809932435 88606024 414449257 1427786 868201818 774699126 95 332065978 20547605 543602059 682482106 461327316 776509459 407875037 795103403 847684286 571370413 376110451 123202112 521178694 659335348 304056821 938233788 581322799 967752253 531888837 134298071 839562306 190293671 484732284 183193837 356463861 268390734 251095164 289875038 707910143 309163875 931789598 653398395 697528256 745322155 738441202 576495554 458337096 638427198 604457921 942613624 48148932 751999824 352537797 961056308 974691742 371980795 246435267 870479233 535350953 282805333 70529565 831554573 853663854 770215756 62431241 705070819 286936825 737473806 233860485 753031143 791765267 664897365 748825019 191167613 712801492 655482666 410073811 803007478 387245715 958151736 6192491 571208559 190604921 92820111 76159978 272726437 489758894 126150409 20722235 438229672 156150620 281538670 502756353 844088801 66360686 514806082 662785575 92766839 36620504 625574897 16726047 577947678 653751406 101160539 41360706 82 258310346 62016359 582231909 686756611 649401682 413501708 796342012 153033620 688009684 127027677 448839715 672709354 304028581 967338400 573294716 802995546 86112560 472070184 460782266 90874953 896108540 662779199 271332855 102331279 933194355 805180332 101326287 974657521 397119143 822866631 983172580 138221284 985927782 798440447 406040101 954270159 175198098 399339137 620671778 618042836 650158327 613062317 795386794 52883308 230851602 626919008 492564955 72115444 549918307 950827246 420146256 338844009 581089060 947361088 742268876 889678164 844750529 141810901 664622872 551210958 124133113 140393819 105795392 937992278 936408431 427814347 767170618 365316533 591793373 637999268 701577170 163401065 556360795 199645168 324282690 778918054 509017633 781285117 626361081 818777700 633128095 626115175 92 768539804 915626252 861738069 839402624 284802931 324335986 424126143 134514086 51974397 188582699 912914157 757419687 917460940 951150940 768190594 740667657 531409721 272332878 246186159 965116971 885815509 79781011 417780168 847986109 747837948 466420245 466601446 798416761 261411243 57672649 30051516 938150820 137326960 390308891 119598563 569231153 625758090 840943018 237072122 90572057 318362447 995306828 81256962 859897438 244211953 812275352 393125508 683751906 586774795 134656554 396997213 415659178 315324210 449127677 965511849 268575651 858346732 467320089 642704581 356884598 240849383 291342026 122577704 53453945 993701653 955319176 195476371 644227491 943551073 769363657 267428813 543528910 883957764 585020426 726038264 355380952 669575130 643048123 222397162 922701755 225582693 415948705 514470366 490635289 847610586 610515389 848392058 594113853 495623441 634421525 627592592 698369682 92 819793651 401417963 311198536 624423983 706155536 814468049 366111939 223997480 174275743 427861305 718039503 897918153 324846447 53417729 522113546 589623462 351294287 386603959 459171704 432155323 890559581 878174070 604318648 828965189 854941792 217567425 679755685 185119781 585703072 528338245 630148035 371786350 567298748 481229804 761940632 329804625 532128467 459920522 711551716 137363419 747584238 852150697 839621930 399163235 277436902 869141765 612220005 389525050 316866992 973848620 203979044 140124574 812218653 678040520 218615025 740587303 142667679 46027043 176893960 964022146 702025540 767312268 653348510 790848430 11170417 832135645 467004903 827706119 123017679 199840154 992803056 502857300 95244132 758799204 757328065 770022526 895356370 322207345 788624331 563315850 409099336 441722600 459865049 146273156 583527538 982528285 554282276 211191790 844448661 222176933 161481534 420407850 67 119050394 780381581 43441740 769759461 187345007 44145505 123379783 413098587 209519396 742920809 316912081 897077689 75915490 749171693 491241788 240733191 905299562 109826370 34919519 766264959 226494740 470154247 179305072 512791465 495123101 120694341 931301295 407403377 568654680 426081021 276746351 916003265 135911715 289417790 58007525 530525559 125400764 312040973 328899638 561651408 243046666 379697913 714308573 795036057 439372860 443654195 591552874 722830500 372661781 600705512 121756427 786766112 37951733 164725631 153960965 599244486 349116232 256673208 5325948 420907489 597118817 303804402 861083548 567713315 265864904 198838522 589865872 75 844365715 711495721 964021882 176450378 808429361 626816781 876744668 241165984 560061980 794194783 178840185 603312102 435678909 832118172 580495757 56038314 324821379 239058644 891938661 125336887 786642071 915973814 29191384 124385905 165032957 984525847 47343382 6318599 881919526 621905251 54723045 572021480 789121927 651705896 649249257 940635706 406331008 506572246 569184064 801272470 531045676 299123299 282001957 829861417 737922 809159459 897739289 192345626 409796673 8409434 181963970 84086428 262237804 567211810 741599198 630893564 976259225 424535870 554421259 527292262 584080322 46497412 431888374 378346275 937772299 124165398 155416873 559305267 25982311 209794856 750601495 429304987 819163175 878979727 197670745 53 367281178 662999207 258699874 178746936 139798025 864359575 395283400 245873425 108720578 542931536 698640878 92405409 482581691 617595662 158515906 456762620 646566603 533081037 180777811 458228165 983144942 618556213 276072756 690816324 740906488 226073489 73722813 841354324 949887574 558021350 833371425 404533564 139016662 441028682 341785028 883228687 186673739 721688118 381393931 853607506 444529842 917198556 80752838 229735352 149802636 799296261 462622491 118807136 619152190 442854608 741785490 45406368 179735136 93 849161107 167035537 452948930 869923781 462939612 496713474 9578347 455070873 613907829 511339555 762784742 124085114 783537504 693557213 611591222 464349929 725138630 30898783 229496293 526916297 19436705 696707558 883777306 164573991 684324732 998982993 332288820 968057544 134917963 59895954 267594198 910293871 857548033 163569078 861578289 579083306 36316472 156995077 210339034 650083996 284231795 983389363 808918005 417794798 324442802 5793017 361551877 963443236 871469199 359298200 734140712 983184035 852862754 848627136 804191765 671117219 272450025 347179239 171087326 137097587 448358474 953278267 653233766 153581122 471600100 356660200 534235542 271866381 178077448 650056588 281746656 392779431 827233873 620488507 827956680 16654178 126794469 489333140 946183140 777848347 760428441 209952617 176697196 93134468 320324251 686912622 591132308 667996391 151713078 900303246 608119140 211849001 788267422 57 660256061 400561504 493735357 715747802 835903724 392239971 520315398 172354418 605128207 77258660 705153755 426384440 255790786 323138692 167807181 886284896 498774953 563955357 821840992 536545744 678683808 441208719 669010267 157125965 952416548 302878866 434534757 53144995 919875643 439420657 611436643 693055648 852083757 223750848 510107556 203574551 243042044 772552744 711376095 731690275 901283980 516687308 730595365 301836883 435038642 838430277 273161293 824800470 403978013 268655921 221176589 38648561 692015990 774566798 99108126 482452505 162184945 65 383636414 876088233 129592479 689372047 770078791 965693448 174745936 386074318 178994843 667858059 727734391 462884362 485657948 888152888 475347105 422169259 321062960 214533527 541158380 378440322 368142361 358821544 404250088 66166533 64654542 339451264 43485145 855830257 442041602 83280665 59599841 332089955 59432396 283361051 943963846 757009781 576672768 735630585 512372034 301592742 644348432 558163349 445432812 344481848 534069193 395886987 399190590 215670723 555521720 797274922 241742759 822965285 532353691 748197565 527592423 152503953 611388497 595048410 416328453 727542191 150126997 502948152 669437007 52640092 406267799 99 982458097 162914412 275777796 826605849 783939604 947335278 596790395 680656071 232704646 724114084 695484930 414977683 189547123 159289777 492644022 939255198 679769743 104651800 657997469 665761600 705417302 725662641 729735513 504443212 128660313 807109866 855793655 57909168 803680813 850490741 347992357 309456861 962447303 60101319 736450679 739550395 157549484 449540148 280962924 919445454 279292588 940532414 468492913 843757487 663509328 94095944 517917921 834542782 748142069 466040870 258820127 536893609 284358437 334738746 56030922 556341106 128245783 650782503 83130444 499698958 883442962 442801321 863509472 835770367 370106098 104333168 799846593 601187756 994214506 215983315 827391396 561747969 256598062 655161413 585806658 833915679 527784222 939176532 231396121 9204123 336082127 130338823 305910322 254595863 772314806 903803947 185086977 895525739 241328401 684543804 471639006 244345577 913103713 419450030 398400026 576654491 40006238 478003335 136850012 62 867633679 545944880 236400335 105574152 350865681 862924957 278558186 848331724 741847814 62543407 422652714 978527027 392729124 945074915 676819838 787112721 612005263 949808190 495029792 137783258 677868391 900797059 772926700 400713017 349398085 179765396 514887825 634978941 480735840 248968400 62914569 948829885 975724399 350037807 88058050 613151766 113606534 785985361 283733407 290791349 514809191 703396999 348569352 770371825 380543153 350845140 764950420 658267599 276848389 640818073 773348782 806798611 573246804 992779753 404658354 524625429 312454061 719188082 873130619 596468321 267282626 137036729 74 906527885 730102173 590252726 432954676 844078959 755264498 229473227 836561703 249534928 761224623 44808768 5267109 471206018 431472609 394434313 181491972 807516616 370276365 283767278 803730711 568907743 781134422 710474760 978883972 395989232 45879500 183876346 644821451 484195803 577025881 766520086 684653594 787949325 486417256 696946017 980440117 997304468 433781678 949461575 482365754 345388578 244057137 964907126 888511714 988270304 33697349 735302703 660528033 816806569 775804839 326135981 158437705 86130586 954322376 343003494 221849952 73432928 172249170 439902702 950190348 376581447 507920328 334747273 268341744 813797667 976722690 690140617 984722179 83814182 59568093 236674794 224471440 191605697 645249986 96 849247623 719564678 697662631 379577992 122632327 161492090 497086880 91202733 484902068 859396585 134840347 761931690 779430978 123778108 904363398 466957091 430273184 728550359 210170678 201029948 291621045 244511261 531631681 266108507 799854945 583923881 736986852 118311068 975470043 522451712 513635851 746088469 653892356 28958977 385252444 809901320 855496284 174269559 520253714 128151543 664717986 654118739 862405279 841229447 260067542 430175764 917909220 70345365 659704124 405583967 518107450 282086983 815216028 646812852 72869426 620352757 834638586 167237064 700525872 237427927 281302873 575753748 97382891 834643572 365546593 470821711 833095597 910690763 231394841 708685107 98801339 162247619 693405874 197829312 597086520 5623616 226090438 569406959 442994735 610015058 467288038 167571199 196816459 727933234 48684203 685342049 552284739 541290013 800096598 111717396 435428534 180512906 417742690 267232937 783373192 820789482 77 259814593 398131171 494092730 814670026 610377473 517749944 868867287 308362854 729606537 689161484 940836091 269417361 760570576 641277529 163374515 909311130 629017222 900921178 746874226 366978635 575173916 745784395 366451927 601501394 642501283 715735664 995975513 205981372 834155678 26861661 307099498 585613967 142956571 201724217 464297105 861481736 488756634 481482864 444006274 30003365 757087617 792288187 822557542 501953526 269559999 247592357 753847946 865805772 373649713 50952217 122217432 539722621 472517458 408568457 225792182 817973210 737048154 742606835 533204550 142632216 779171327 684635402 736620209 602742708 825372518 961450856 742604240 407457205 47954352 270510675 167546720 730345949 651697162 580922548 794688919 148333475 960411053 61 995540610 161766981 983797219 197898907 376540094 723136633 626831017 138750028 885674532 143782862 62411618 256104066 752467410 810881576 862245489 701189482 789926915 479416499 563904119 108657041 257022550 908124984 804857012 502137612 279517743 36250995 611966618 480980648 177508924 711021121 264117062 751648614 640097661 974254947 415266648 852226532 919154048 979433906 387287040 994579675 147095013 204231316 981042529 892690210 62987435 669456909 430529307 293615459 326729456 868092290 111428534 824936061 334540206 756784901 225839963 600738053 629872214 395420487 625543274 185515509 657468654 78 317603963 147207458 311260147 840267307 689569148 817559620 941352059 164244990 66657504 803122955 939469986 884978088 672990945 578163558 178856046 443150198 867747252 585074332 429105835 903498350 284729528 100252489 700821160 270995774 782566771 826415996 168515723 368854822 230540597 561575080 64929869 508210802 911519277 472215122 508622901 290649417 741397016 532676425 964287133 643706621 647473865 856667527 704870666 303579582 681887597 784849160 248805641 275988308 567293048 351085424 766323762 752786903 239035731 12672681 957850620 407863105 906614791 722268398 552211157 1540312 60743262 10913111 575221481 697987909 812380108 794454765 69740277 810792966 53061567 547255139 473006414 48541031 104435334 723673478 493870187 512285868 357255102 703476805 92 872677070 256189407 237671804 508857735 542227517 170549530 726331070 858967447 292013022 6985287 112000446 395059202 844336882 50943434 450273630 220206726 816568135 416821719 322023943 574308568 669864194 431087169 519989033 358721946 49017383 176043592 564091900 835434425 777750776 435378857 107968893 627471696 352964912 916238235 766338197 54420648 82469220 75204464 604498217 724071739 265004650 636821932 645798229 995174128 622808042 905693805 168220734 484894019 176031495 41469583 697658761 524694286 530548697 366477561 509726302 377719692 885808833 529762500 747256130 120081851 154025397 473100597 187485439 957076425 555653741 373319310 724696483 779695140 76597750 707379515 290111191 426863154 288233913 103201175 136638104 645996934 558439267 648361777 282805302 33051425 684780933 21569188 361232116 705194093 861425376 135519108 767376645 727592883 745258494 418121026 556378328 98644677 71 37215552 173705431 6360432 246543946 663498068 6389117 517996346 27189799 641291582 161123119 290998174 903175278 439252736 114316655 505633374 556798503 366215169 676409216 559773106 49819652 783671090 632876141 109703138 757474684 818083428 71775590 996733877 984731286 33903246 810097144 814602931 552683149 120798268 977254860 87233215 703600655 578157814 817780034 867570102 259159847 962911530 789253010 56738476 896660085 94659405 22605074 344959448 417693995 50032440 431235009 468780482 877099215 136084773 244800885 555812503 434439093 195847910 625582052 291770856 469560312 455378903 998735067 312289883 922343650 387184596 329263793 684677232 796314697 911072429 38384377 528806022 70 683054469 383273467 888337233 802365437 79117301 886971864 948739689 958801868 17556112 906949577 709817661 623612712 740829242 807370362 207180910 754424556 46941701 781976392 590665102 407480832 867813654 575121762 326183770 703730826 603810141 416295923 60659102 707225508 260716596 62306786 785498162 445252103 66365120 474569959 16655890 768395142 923452415 439060371 903972247 705878147 469645702 682073836 645944335 350346509 847615925 965228581 449222782 387467329 986985995 664677967 916547274 973337418 318884819 29961201 831426393 973077221 592300069 378663733 847173163 275705930 600349871 867414979 872214817 192485483 169151944 190481390 414148284 112559158 867404248 650204148 69 989168421 980899013 199062463 491106047 160366700 899378546 527737900 963263501 599838380 820688445 945077658 659807041 626154125 108686497 789607540 826018940 967224388 581728755 299141391 249913891 339955430 877614954 446746976 9992512 798527147 909104127 238424317 17814156 513262270 227628085 39514024 452098013 392810190 14161095 825886415 588970140 315622027 31806262 513896194 990525055 506120075 287439396 289125814 705546051 69824854 985928895 594856892 474946965 650357907 903303068 985829354 68915619 24836188 552874534 247644767 823409013 613490477 188576528 38752778 178409623 299021890 32854582 518548950 370006807 969550311 954129561 155150345 100526808 592211435 83 36824761 713759811 63280442 932696198 193128416 319657598 916813523 820218157 75889433 23181524 449857689 413323862 314666052 30356311 28523603 262176200 638701817 392402442 328270111 369768887 39842937 563569300 532585985 837740895 910527089 551552444 265141458 456143338 452114538 155657937 360695410 979452194 329613884 696041023 995265301 992414407 503291618 335253542 682977923 806773398 389396226 889532295 77283342 8795384 572013717 855955677 927272443 873074963 523486802 320071693 489124309 982855067 356638617 413601778 654653739 35454359 602957875 327631260 212512600 538448672 200344502 858939392 674725681 419439306 419283148 783057154 833667926 625175010 991955869 309310653 665774958 295069321 237372484 341984485 181236823 801524338 666837040 688736718 329946543 689835290 69147109 429051717 297039267 67 641316297 177317303 716280497 890433341 261353159 219436037 262368551 608174202 286706241 443943901 389514600 873583583 182900063 57792044 413619101 484896972 399540762 740662914 59173214 366671422 773391204 100838935 812407398 221261803 863515242 583723522 559370859 891533307 526702718 164779602 400990177 84574827 336633043 704547067 451647997 3484540 638826111 71428243 7798416 979980799 200645084 681177270 220431210 800599151 289235914 815728483 749698860 283003514 25084424 390425204 759227623 34843855 623575845 578673279 535461781 741005950 912308487 415338906 321281173 868602466 687341679 778434430 180998010 318658968 529401882 505039579 91280763 58 391945832 927301560 846454138 844060565 613108597 674300876 563172155 346497714 987173863 618352140 250749752 456230892 502823988 472418799 880632857 956503303 848177716 257769651 721140678 339230155 601759355 180088596 974857117 252809194 505762222 322166280 641332700 614886146 917259636 622640880 220872059 908680919 77376656 814803974 371416413 278845404 580181099 429571217 379771385 450220750 29652517 942847341 405779381 128174527 958033253 66099521 60039522 531744225 99206600 468761342 362568594 686657769 493990479 431772678 448163077 750677190 407821977 915015305 75 221977122 921767565 91741045 454482683 404535241 507541170 999130688 432880774 740011553 513162671 372938028 523895937 900207836 991345978 623550397 969757183 41377726 461158424 48469347 331165660 759435166 676792855 277863451 337130517 318446947 350347889 706450431 33891578 183989560 101765583 421735837 214151783 676939365 93376952 757739382 802031574 159620828 113213239 70866731 287808099 790064379 484831748 568556831 669064119 564145519 551243715 160586974 14365946 861774011 485926108 611836299 234809027 911172343 19264860 67180899 430004764 466534881 613103222 816032531 761038981 764145589 780422099 755639114 465548408 341237391 939649503 894999185 690081948 932977370 931499545 466235804 590667095 79850969 440394997 664212120 82 315757597 702213069 857178628 471776834 929488159 516459198 781785925 449780756 726014108 350000964 538861494 342212448 114456828 275452772 196745613 526591604 122983392 722882614 534283050 302473290 180447503 532758730 152616162 207004798 293497860 879658190 684308157 771876326 415651845 653365842 56595722 92302387 65751378 233250437 745952370 276452428 223653924 463349736 380560574 577411211 146801851 233917366 488594540 498141349 478058061 983052133 697750887 712691380 903878823 333657974 844193241 563173883 932744222 667280025 533100667 319015864 819371531 25960397 723793616 148754272 108493903 605773876 247068271 238431010 438648768 590189668 177973162 952454971 538927185 224217755 551092250 199272471 183819 564192075 231918009 70823555 768656254 913134786 506952909 434840847 368243778 899328456 76 439939512 400155458 285184125 430327390 341357397 686936134 202496126 982129580 314764801 252554513 982126845 129723686 879146902 223228234 7738554 6301694 744531419 371282502 906761602 314976006 235178741 993753393 906289968 656923927 494389688 772689564 182066972 445194570 756014155 651103092 467470133 532973632 904704146 182686908 146963392 920758523 245113059 719257521 352140880 933730186 983426815 339903341 463136057 850782125 500294732 340054888 676039188 21770271 610516655 778884790 683609912 471708216 140198565 829461035 490083376 88094370 716805146 992448479 972201757 504458370 986180888 48635138 718783706 750796724 34735949 321872797 336863491 977891830 336332462 188337319 242231956 51541192 644740720 282102227 57463203 380441272 51 252056854 75135724 308624877 779257739 49895744 476064544 575849546 952400533 160533446 34843264 290425968 424998735 29039282 242975733 365321085 129416718 966627497 68951226 301119581 228598048 158891251 92778648 503885361 519693823 492440316 207175987 598737648 146684156 183878447 617125150 407739414 289073924 13489835 611375507 340096530 392279381 971205536 23447246 434711997 461511090 958163831 571498544 694115048 714842791 584103410 246467193 272287514 600434845 31251460 273124957 602745155 93 711351261 434395040 979276235 800341312 74820293 617324326 665169908 51798766 428197135 605183029 26863759 546960745 115075849 464483955 458847171 222390329 676678215 367561184 333783541 339213510 199898414 2157429 97800719 187909415 682410821 638984353 798442115 269958508 624670133 475341838 671222467 501923082 971561711 522110466 91467297 601475560 543267409 854483366 333442198 282958500 934289693 187754907 27412311 663795517 210054409 329286409 240626258 280932163 611416956 985058207 156757524 135829352 860836176 366360311 799598829 176122887 701515583 679973638 434887616 431784621 224300824 745158779 372789328 498457838 398644570 499025951 443991614 376247619 400717924 208533458 737549567 591247520 890387594 361249178 562185000 87072644 990373886 736603660 547187442 718105717 663292068 982199065 772420273 528015336 415710880 42480166 942262010 610276725 446819471 681439343 129394188 979355931 551724748 67 402623662 487306605 56506059 52893834 748591918 347932372 859354483 788808923 843291968 880073240 537418113 719149842 776002167 300980396 291526486 790631018 93256261 758638019 320741175 489482529 109967027 592605865 773810658 512851127 838158621 907260193 609143879 362333149 186380554 759356281 101629814 814991894 138723041 701751968 30119466 437143350 62729015 812671469 320750220 317456543 310506359 772725518 203994869 574336712 599992573 57043801 125907212 507290374 125262059 65603612 703078459 539703942 207406067 912820471 345705697 34833767 344958700 288270875 170733835 715265965 7380440 638319117 740082492 244258381 767481878 816547763 644271164 78 586517082 779417306 30488732 382686889 31905670 31249232 522952686 258744742 591356782 879792695 636710523 223025370 590050405 82107882 1408085 390123983 650912019 711840242 756601469 98144234 269896145 999133441 586426515 257572652 605661876 216550541 492573645 342259861 937279675 32266913 318798797 709608150 505587585 62510499 517838320 368713598 218900929 917267870 240909505 416198735 451023054 73755068 986005438 17994845 544296601 298759349 397206262 3602405 382633025 836012540 29405665 842878377 320337977 543248831 646871288 207751601 939661848 313913134 123131672 283378205 868127330 937442196 927025926 813118147 106706926 279228478 891402128 321316909 691172645 180550388 378007110 332180608 930475726 112380878 966412353 921313935 492363148 649464105 52 311963501 330307735 314822711 516608728 526361000 836061026 943386825 31850948 495664548 390815190 809116409 977534905 376224472 821271833 361056398 195505844 355407890 261134026 635812240 885007979 262250693 778588492 522905826 834732525 996615688 591249184 889439621 464648796 899127043 282024518 659943418 600833852 288047711 459436039 395029728 633656538 429436222 416846696 547865602 375161478 805554716 92465784 125634874 855809127 860526678 617094797 90695851 91735015 996399024 13134020 370793309 378978400