10000 2431
496303232 861644 218374484 715307305 51592951 998053718 279191005 440184133 974116558 786416736 675861294 359310837 19727827 53902744 366506015 450026685 658283717 135624027 447599570 567120378 494218512 286675070 350641334 340060134 86018187 846464489 663307925 991118382 750222290 389736749 536882383 173956441 107551702 710663407 735219560 382439854 17504579 228616626 420038950 897213943 83529912 646386452 676960721 66143968 897667230 458318569 342058372 228950224 909919395 776684735 198030927 903362867 418840554 323488974 401759915 982032356 746163735 885310071 535947548 746788499 860531292 314606215 185394629 821615503 562383333 893629775 614982324 411274749 262811303 720255674 374690544 21369557 193615547 257099837 48828579 513868423 163302539 558246738 785811175 215572027 141986182 431602642 866640347 361484013 678486221 208460943 97169275 744193450 71399676 827950355 163176241 170899123 426214355 805658653 341850670 811502100 568904372 116109555 966730794 231092594 44152041 30194636 256072593 234132101 89769927 619237137 257172512 192356230 951178485 91464349 938819204 558188556 498604564 47263297 950558999 836405808 445735506 392797650 80057253 963926583 444577298 814346327 306584975 201680583 952029381 452375799 747320706 824561257 291579072 912147760 44786300 467245011 411509794 748262716 730790717 470698259 661198250 522011763 839189455 515738629 287970078 387060061 894654527 557672373 830157851 378642696 169966877 667409934 653707319 305814633 164631301 487449860 250229807 989503691 790398526 669254517 152709225 936918926 580419848 485084238 957373943 827363429 408378931 328125210 802315205 964952167 429721144 367775471 821949774 413338582 810098559 722876758 292096017 852305485 703206585 130552111 169910396 693993084 177061300 464522708 517569350 287293027 741477432 960363870 517790655 92387295 491939797 907221284 833849869 633750767 249771971 233523935 419003564 57783167 679703280 608654231 88301068 291989659 363822212 156525297 490524994 32123746 828219823 727619756 371963774 419035537 271098541 615460867 70708758 426038224 529282434 996870328 800426975 403136517 773508362 299675382 238360476 959269362 752321860 647709937 214993903 581159865 377064387 982722675 901988948 740624695 485108459 783874582 135344317 217065127 718394799 593876336 913159770 965768108 151209107 899909831 971311874 611082041 113899464 627358199 672468248 507971003 945176284 327344748 386239607 918407656 375147875 446108802 972034590 663941337 399820817 247452128 198419821 282403388 490050852 592772329 530577806 255264252 987692094 763224627 883429568 404639489 920973440 161808574 76714224 4949556 604164789 171402469 44360551 578905178 471628051 750149998 537674082 386965496 87621329 234475619 508248491 595263832 882053756 448616556 561588645 433859149 94642076 90281599 859935902 899548603 125016535 480553312 259291956 983789202 621210377 492079862 341292438 914577135 569332557 686189071 619159979 609158431 173327745 792612514 719342871 10558237 344326781 643741512 511014053 372982243 450796763 445745350 227832609 319541087 508457028 647080089 982500594 512215228 997740191 98985047 342545235 455165374 461728316 946762660 993953640 325970060 124906815 151003096 419793320 775258448 824785055 16660123 928705702 867483281 292562934 97831995 891937652 42096139 477766073 384852201 445814104 299605683 742937206 147775313 466838731 165495936 974197582 974501693 139943210 641667673 182558801 410412245 947656213 129815423 528282099 281617329 990403685 634140878 579763185 232995073 274499571 416924226 266010595 571158583 57238701 543112165 547578240 31152445 616545036 412466049 363327252 909885136 824787156 301119029 828483864 27352586 693782760 999282328 783069340 960258557 654917570 743029168 861906939 295750162 329384912 250047632 704961756 259307130 985330870 721236221 762081123 911656053 100115478 497025642 308942577 540836619 120684665 85706492 546026856 147166503 653441282 956073568 792489016 190113758 757210245 717400992 165133802 475273980 600545686 961729069 35985106 411374446 224771400 436600952 949458950 415588388 463104130 493345327 537758872 322592971 991709172 352462548 217754866 562374130 768270933 192799874 487066534 182759442 877563279 971625629 82708945 340822303 128964000 184202794 341304603 984695001 740991731 543393786 333119776 22213493 715673286 717887364 887938431 485753513 657901794 896584437 287605960 998007929 398753623 922859065 574760827 31658349 419139520 406969446 757688698 118144479 138141889 244039282 424560095 842741075 224854199 689726171 23002105 97062150 194907460 938895456 762583591 309885641 90217463 4186392 272212653 739217443 678295355 433631973 786564679 128586692 475588325 928202869 797628920 805303756 653943732 131258778 623936333 641494052 967118052 797170394 939025970 744594790 730474891 803060435 661250902 255199363 936935894 460655637 966224488 242310753 548183592 866002620 413775598 350271978 629477561 556795702 748134207 991418729 782299528 651560184 215032323 238331538 708608580 916510572 998048701 35756429 587024249 848600223 608092175 783652383 379187080 578510399 997321452 133181949 689594173 535765728 521013353 495180527 234811063 213662353 474198813 136328603 303928326 690807340 987459832 208179742 316275956 420750527 709888449 335913636 241077192 656308672 669669307 213726686 83186587 275506909 302589341 16417009 838964009 129844847 298569735 997824678 90606446 395283257 925699907 707769709 426423083 26494409 236017256 562053470 951491357 779992059 867001052 357719342 219628503 318604275 333391824 639163785 112535321 824378147 372827319 510091915 267462030 509235666 934230118 518662309 571770172 900673118 293742300 725125912 879910158 462338712 17807799 289684782 348552181 323799831 10266026 396281758 899144081 601036079 107582222 388064855 226447200 587687477 241952319 497437427 489775752 705286146 555973820 92460433 908439045 877295569 938866900 568737305 486596 538872819 849587478 228108702 701051522 802867413 118521866 966404825 839482302 837437067 247152769 33127943 780326626 671990878 838372140 971767883 332791689 514908959 335035630 227256128 661388058 285281487 847381504 358463864 206301588 65743589 883941561 498540439 580692448 104691082 638892244 599741571 503465678 376744807 427896352 530713152 581956265 670238248 88921382 699148693 593577786 153538705 33634621 766061437 901725497 833201217 187094555 643287072 341009572 363854977 126120057 146211670 742657807 460679857 213429962 878936140 896482680 194208578 376774169 531254126 564682137 846087476 813494300 995247932 411000727 45036077 730844218 611764428 792332841 335587057 773366511 703787826 527534844 441407130 508896583 174473870 244442910 151029565 938944413 507479953 266115481 779835318 394724128 711970446 923557790 777165338 991621392 925094771 578351212 196740184 222511636 813707638 864214777 955444243 847476986 483751235 812770753 60991936 433445931 564359860 840693908 393533523 359804645 997125665 426951941 956628553 577088773 314058802 628029384 749249662 553481317 327778229 571596292 578619331 548799267 514368088 381891118 899655731 336535633 854761262 529151716 204877621 572431656 775447163 709581671 410387778 468746292 109595076 652965315 69014059 57515377 246422283 605413520 82173389 976919893 619972096 894184634 667402167 265943468 95963874 212038035 261588257 956994142 887656519 508234304 536895666 890300485 91114762 767771089 904948716 756170518 50210993 822369992 276387683 192668709 739713988 971902176 124386892 433360494 608886717 320335745 945237992 527332736 317344128 217530224 489373331 948851762 889045868 270497572 616762184 843629150 837723231 10740702 499125526 78141385 908448449 708051180 152023717 797237195 224974321 422796319 946787707 226851772 706865560 656254603 274059363 518853128 687474250 390368545 407355711 394637243 349648233 470817045 137834403 941217716 662399231 254516511 493142282 56236556 866449978 266621698 299067275 495440008 597704144 419427782 469712217 298543306 845650691 106336840 340186030 192871085 900078366 685260654 803940422 763585811 497163309 680913392 774357110 811727124 492650049 602611333 556997596 3563138 467065441 701122961 83818109 83952501 830835404 250865389 965305039 503947989 36714312 613329698 587789906 57616950 919623304 939590988 910901802 491377954 33393088 187807191 617088471 926059977 58233621 779170417 758072174 733191787 277719507 955735335 335334794 318195818 189310820 641220545 71349922 214692313 683598922 408182218 255057483 13535403 375297455 63257073 751475069 39718962 893577437 603799980 285626493 165391272 685577895 747939027 198391613 985524748 271325825 910695954 795817920 297835206 840668683 251190737 262614960 62673159 337872118 912492855 464154474 661562154 917245697 739772522 947817995 927325292 55051674 204875328 205739081 199174546 389512728 271804272 534647017 519853679 383318182 878835610 541584651 382587651 980909923 385945203 276886760 658241884 698024358 730086676 440067710 139639804 798366369 499730467 146980934 797409651 949239758 908374353 981565721 627734386 282043212 214067935 100907578 454160448 871875207 156279880 424130737 574101622 608561281 475039181 898910005 382112047 502698227 586212486 21638347 410019765 667707520 338812214 674844734 815778584 584805739 930803082 461421700 322225707 146844247 443397102 139624662 111275560 344379245 810046269 777804012 618702212 756650056 241294090 30650685 149586075 566776597 773715518 933944917 800907076 260160947 179090738 496237628 557534375 222640005 264251761 688689476 505832678 408222833 647419135 175118163 727571414 22642264 674925845 734440113 975438661 619243361 420089760 763991369 889117954 487019347 335147135 811620046 48588078 850267352 686831647 922722803 63274647 83143135 480173874 846317147 559895093 571129854 235513312 863020364 327372931 45717561 584956866 811622127 327044184 595003897 230555166 263666498 666764175 209464488 186450353 693330021 18965240 420772261 925569035 801012084 392273481 806705171 310494916 473799714 520176174 677863403 31892520 188123981 938181039 542103644 12732422 625179338 891530447 54406278 553742603 887398071 135559222 113910561 108041747 294366820 111961404 938411418 446299239 193779584 65249043 848339709 171409654 907441920 355653439 262095910 257181926 843623872 829078983 531074062 816391431 420498789 894803527 968418920 424349472 202305096 484118994 391757509 255406572 439348387 529957638 969510050 598151522 838955617 207590952 75870964 998343329 585533969 91571031 363819275 718022228 2337655 275358079 627596198 100199756 715881342 854821627 642351651 839760028 425556298 368355067 756976878 92282689 786214705 216037125 504339590 357846810 402458321 175444340 367926484 310415750 304174046 61638699 172806005 820381628 440619553 81119121 855286486 736232230 727766448 577858562 809962158 85913791 642433635 317029088 590428645 823541564 431931857 338626639 485743083 585198481 559648104 56960729 248010787 548257303 592083608 25622737 419919821 325078448 718772679 666753257 552900448 410656902 250971411 136695887 404705195 814433931 167424235 718324056 487219601 790089317 304785374 944647932 794609598 244959792 104331157 440665169 799195590 461618837 164453320 848860573 893987783 494692965 530120735 470329198 741231919 497315711 691842790 434917441 479146174 307580463 194882074 789076866 610448954 841743356 258813266 349110588 176094263 819739627 440968990 97985019 689253789 675478465 191580924 1005925 531897196 955765126 638774509 657900892 83561300 73023432 788992350 807999393 719206873 987032790 509723305 681080448 423188936 390077616 334936149 895021263 903001365 383621755 690967262 560085661 635897228 983670729 715257380 953770767 809029633 626358936 23363382 494543286 817822619 192164583 754780053 164777861 574457966 159089662 961962061 568132750 162249772 87783334 251212989 785206677 855778696 600084359 54293017 571889615 8419486 524160022 322500009 373931906 645324220 584324703 608040611 204116585 985202798 789651438 8767325 373574731 328670609 996056415 146704184 856968122 89499786 151648929 195171921 56352436 53495556 963940427 829532546 925974460 580417615 903719048 757300835 381696212 88210277 745119876 181521339 325837163 3174141 688302410 656013494 59779066 394173249 529866373 654130069 160002495 375187162 590187592 891236310 8625899 735623842 371296685 631307311 301055569 136586461 462812372 454562668 604070771 504977380 869051477 393749378 942053380 87447305 130941426 480246122 49906947 892274607 395123413 330686443 895140468 441857839 995709004 422375746 941568901 990121473 383877126 729115500 64304040 671431456 483601820 304029457 396920989 28819162 901738384 585591958 262964192 458034037 122599643 949782445 819320451 489713616 301327758 345625801 739870103 140207341 9065577 611297905 763405095 982943370 555035950 14928182 272030561 399256546 722023542 318111122 595691565 975798378 543482212 741580305 251288486 283853428 659542363 471671780 150212512 973189162 753769212 164479325 221493228 246829903 11937566 646378298 236077060 26614775 270379581 12120410 887237866 294165190 695824600 90273805 212874166 91058485 366256502 185297274 469104512 36080014 197019437 198259199 731498282 822768794 327812286 805701325 366795347 818043542 581233978 176353137 266418987 974064130 879528423 156864935 510422276 720135946 412273233 694805817 261049062 404029856 692394691 204396580 536638778 925391972 755837036 667173422 328808988 226441801 61224343 111244228 461980012 305512598 740650382 53292129 154799485 526960971 130445463 269645120 596958234 302205607 907303267 498261696 576650986 469025608 54940799 848749939 261301774 665604565 648621335 979220114 825819402 647560768 307850068 31554229 109132252 781347956 789255547 559514927 948360445 476293508 943299033 268893092 312189671 394240819 228812221 579357269 111171270 47340693 824147841 824245585 138004307 919163166 666428501 620916469 959255630 91994737 291471960 257330600 402854674 781317423 394444573 344511809 286680607 676288888 927466838 876095182 785470344 884581082 613094391 601578364 23843890 414141846 370717702 799057516 759244732 378334723 202598177 238135481 462006137 554188059 729771524 591526130 361231710 404738217 719348767 313209375 719014257 702827016 928063905 675377698 880136 444009172 363936148 344546233 778504772 135668010 47488254 342946278 203386696 329894473 286227603 347757265 755388130 158395886 114252995 135828604 456064900 989992691 432174854 498879289 696947507 117495720 544219568 428106802 104475423 182939451 295372291 898307915 113708798 814334346 964393506 191112488 590120792 192448911 22638372 85009407 57981417 4173591 256493413 459834918 89900749 181182253 715448111 455014219 463856094 386797724 519541448 927235392 255381838 913325305 252410673 576892845 857389598 460877369 522152757 418959173 384025932 824848567 398091499 991796251 31668919 423478384 246903077 397730082 48007055 407768749 391511531 412991378 584751908 822973550 222681164 714489745 401260559 149893018 90085241 318990577 66673861 291095472 220453743 977156814 670438635 829189297 604536524 36699409 851749717 403744570 199509251 688866242 390909492 744760403 535164363 304510383 237262803 569258688 618809610 423158006 29377950 625482131 463444660 275163942 763267157 559249025 452186650 857596209 763684375 100875247 358853782 839186867 531921390 657232645 66750345 829345435 396546151 28074650 350224671 404150378 98926753 976122365 880757004 464270588 156363145 14640270 501499454 905119702 848429756 886697112 386152127 238770612 509627580 559561052 301596758 869387992 854317277 304533435 795706332 852287351 161928132 72027826 740252139 388146217 299325500 449449817 540440841 994398166 740749540 679478380 517323221 292795670 525413362 52469951 312362515 165494916 118678884 969111707 676971438 683896510 981184212 813884081 170280498 740514614 672817875 408443143 82592355 555635702 899962544 246682552 353344488 772470169 440786784 110516028 660129843 56688195 479300557 172821586 367704054 927586211 751299108 887480762 671707412 919498349 123718560 460800461 804968588 266131427 985342043 37977210 907478798 191238587 168349943 427975936 768900127 917292911 97129925 281935224 766553211 571855878 441133439 929014406 213399825 959610656 192664387 661563894 781371945 630458176 598082327 466005744 116210982 790873078 259884954 985554351 664176618 996220651 19071929 342850867 93688646 93864254 394701962 492381473 849870764 251516999 105255609 128076595 842611980 116793191 956602115 799644748 45423741 764774316 819131855 676048238 821993173 888285247 116237271 725947421 679106142 918190932 528236093 697500268 772731519 265880868 532209173 30775351 899357198 25028478 488661889 255466810 108250718 845455315 676648631 396505866 40332819 361409093 23222483 113144344 292847783 733413094 225442139 767849387 92647119 619067017 670262217 2948044 608699463 981152468 759520393 85578283 703739672 766697139 923040871 722725888 822348643 344187374 258120605 709298322 729585748 42820075 387330201 564048213 732674061 747346931 469627874 958618441 667895717 481032233 250333405 286077168 973386198 569727830 240226192 617853235 145283563 535694029 807476206 659581166 328788987 864363065 413444487 905298974 327876643 272685048 288368534 93686016 981928015 926381488 971718709 861199649 282355740 832349833 323573486 69641691 475790948 750185890 535521351 816312807 66261989 380044316 432888192 844801814 645046994 622726289 666817545 325906521 938916557 341091383 773515445 369607661 749194647 759709908 870757949 366348876 528219744 681072950 190923919 602815618 590180845 47828186 240108408 799669728 447870782 763552151 77910340 456191169 312948433 958589804 129762181 963334884 763189673 422023562 681943088 819152914 845828460 311799054 641752871 345150623 861888495 290530671 591533581 943502566 963370560 410234836 510303804 818744996 251620162 563180638 148705208 76934714 759114018 907953735 958614038 252266286 549667230 131150538 685258861 618560670 720490320 564688458 32144914 488849944 929804589 343457538 580651068 300389226 914503207 850678789 106320430 7033995 639544656 461986293 994527169 936570356 978022181 567992267 774292643 201563562 723016558 361849309 24502750 35043546 165542392 82546286 772161468 570747042 567952601 724150336 624349348 730439742 379414612 953665242 569532400 380742176 636439039 415638627 190535917 204232760 891948336 991501821 596672758 661075425 898167596 534954204 518787762 709887301 50622353 599580257 445575619 366660079 920585421 140670215 348951792 133024609 231208973 780173254 367774625 707769773 941637093 439539332 466282939 841183658 362727717 247717236 70251253 263052432 880780036 170796539 216925938 941786825 364094569 312343348 863881431 33401440 720966399 142294850 265123412 775656169 909948107 844355183 803951747 47612650 338240273 380477265 783998800 161819623 136760385 33657686 278877336 986779437 684617109 242365201 215426945 347522455 955307723 60603859 312486405 223390317 286720028 51202195 853453626 134909711 840009384 298000706 524080160 563572095 359193086 653552786 450473225 491906686 871879867 868087548 588403527 563206415 309218934 316649253 417602693 931167873 298436244 657654543 469087166 976425424 810524610 908021709 348516030 859565586 823826053 592859567 775797284 695860153 622772011 118792011 335496398 574828643 224892830 7600307 272829393 728434979 642644787 569766934 967274741 562349675 230089085 328056602 136681173 72346618 917542011 48613006 433445105 764086879 361993022 447690219 452748040 342551466 617864000 179891123 274652703 229833251 132957764 635877757 377955586 79460481 318769829 981331580 785887375 966092672 318415097 435695520 418401924 359032647 515190402 163578384 897622683 149902802 309604547 389242203 4065619 37347273 740414335 883067378 152094916 269580686 747411196 911558274 41919271 252739549 210981038 525570971 689651525 758316347 853589873 228401521 411142547 719513080 796668369 719775702 882435162 892119577 403904231 653425529 860284129 286796924 670383352 639077979 638477462 129442790 631682135 142460959 203896591 625425693 597548262 179291143 782930608 68864459 926941983 541398606 736181557 332285060 772762614 651131208 787667768 1282064 877032202 763259310 2355898 983028536 276319915 536932377 307956978 909780172 206524722 547845389 12610312 788364170 399937693 915076901 487415002 85814129 481425730 855669546 50275856 338443963 461799458 673825385 354085670 233645498 735383715 701811628 268533939 131306666 403471025 325486210 964714212 427005346 182841578 275030940 124164936 635218100 755845274 904569540 16119541 158331235 282057429 604839284 842293863 508173258 445977449 377072669 231735602 651781071 984014269 666546691 838101988 861702449 365433352 294400310 978498125 616101306 967821035 929049649 167324081 578324394 858885349 202923924 111645850 193996343 388146615 274503772 233748133 95786977 362650222 533779102 278671527 174889561 48225211 463072201 888234774 183846850 636556676 154673139 327760731 758001406 165753635 291764999 469999614 920258882 514623486 94167220 751078817 204714573 53408829 146017974 220322070 236210395 909663553 128789981 287920709 811961406 9073719 825327168 507930606 155163045 775333624 534720953 692089188 311180689 79669710 702442567 231130244 554765756 877167783 757688480 595771745 406080216 321223932 967837588 359138979 866300913 907339043 180478621 511638395 459588693 515216828 16966110 912777473 545940234 486234585 267472190 654760725 352016069 932394547 307822757 334590808 54884936 154889311 449393271 640941775 529198875 127209369 270024791 18105879 828896430 228280048 968213964 619789741 853283885 661090717 798874547 664831551 366041975 348956644 421090619 207412754 773116113 995905679 9480057 987759083 712098433 924800401 166678793 304264670 65369289 485252294 566941267 655538047 323368230 262134422 294149472 85156782 127687236 734780155 496398765 44954191 420623087 747056989 873979671 148730667 751176765 411624148 683551983 433931176 88571311 244806565 364538523 436788534 402329300 253528697 565127969 593966638 559979387 630543626 299654071 410013420 427860481 460602398 369907025 228128186 847808535 42212178 738676140 328732035 188036732 580925356 465230 673780057 528214845 72416758 45009196 913888802 416364875 598704325 103168899 993162644 809998454 443595747 42535997 476856298 973855077 41235050 634179780 932929214 923022404 968550163 812260211 599815462 614637096 853044150 81474763 892333773 580113908 176193196 846581587 509503650 873692025 605526170 437241365 975716467 187643074 59910439 74396258 179775029 444916415 655988803 670241326 126467865 690220032 93427836 240388315 964924490 831143354 749640338 559141016 400447678 22003507 116400741 867189584 136856074 424965779 775162991 283684387 236175004 595035257 79261205 80907511 910540723 675137860 610505309 898910038 190896373 935146350 832154687 896506159 313565929 517102588 801105114 403163915 457684191 601244575 500563564 152928073 746044985 420595770 800860257 224917732 113509598 383306806 366369883 7015048 784471250 658138660 433033040 654596976 291309632 308913690 975629075 409068551 47729592 317549275 323023691 905082720 42756828 402162816 687307406 726662645 465972995 45010496 699969418 885205712 347153119 832512937 273715973 996403074 131925422 855596907 816355342 411186069 817309042 586069801 876647534 389773135 408019757 843969730 149732394 414306956 889387263 245678396 724210807 132284130 969676509 246425594 772441503 18822730 544159761 904413777 473653233 679006983 427876125 542574350 292986522 318088235 739910791 732475707 658862455 942092540 897361939 140704527 700647057 540196111 411441645 212261394 666290368 482263907 634687216 479122510 595661470 244886657 38855718 321954726 901488282 5404580 941139398 937086693 790704610 906014385 777540563 647000847 19228164 459588217 722808750 153860947 717294688 999762934 287483268 424015940 346246742 638474953 648078792 842635541 345140091 322046043 481692591 123533698 908247301 207200124 128910525 294891510 183352522 628990392 385834372 4468884 307706876 667366749 316765907 516172514 842618301 287649509 472642297 960079928 510491963 999746375 82838774 787952723 988088381 566920538 613638187 845420407 837006612 979391637 47391925 443400368 404340978 214716425 239432274 421541193 746068093 161812281 231756432 806077703 929721766 409084787 209994447 698820901 94503223 58541881 183895849 189343632 818670127 797135933 787245799 454169171 519265092 312677714 24179560 119958686 256740697 88806897 637964975 435214225 108254126 574729680 750021403 55437041 980585890 687823585 11001446 913335079 420913309 952961616 703079992 23261400 274809737 463580338 990912878 830311316 584400751 4916717 399982581 218698218 561613596 787574848 49740303 207875224 173111782 462698709 563808019 964183720 955738772 327174071 912811252 45389001 981986404 964021198 190412334 637685728 774886147 971756572 825777364 861994498 868412450 342591854 867574806 131207387 116831566 362589877 178340521 26309431 677085180 277043563 200247096 12378343 462225559 795873136 294999967 201389325 85981353 827850339 801253701 252073503 842220754 596612717 621512903 433022587 229837977 690006629 924819361 412127654 138363424 1397949 188037610 84571417 214846446 291672931 701398975 645389356 249425090 115690148 48945494 458623348 521842422 913656731 983001001 76079873 421014148 106719964 996998698 376133121 739597325 657351456 176679338 69441325 525384325 209626658 181960333 338648966 147832777 978799057 601673953 874067216 639096140 483796130 100921816 310059617 344811245 169351020 483112754 452841288 808302796 540793375 202334521 785931718 389335443 358952623 580634187 334428133 162045662 326259238 49148562 124887869 448889370 802232328 418037935 363646619 610029854 66033150 733859186 974555473 515062107 482877636 613881161 895157236 34257555 11217034 703766400 373393199 585996346 131389502 41720604 147849366 623735010 39177812 116338648 575388030 111854703 105525391 231326789 816775964 997954751 761471256 784861415 504780703 727560335 729426701 512084471 314531494 620081044 31314571 23966843 385588048 776538583 842595358 109864386 719849974 568445158 197109323 76635461 882732462 511509790 311790258 523940882 583195206 35788037 983918598 705881478 337717254 794873213 918050562 505018576 715832405 625573775 308976960 696412926 751937068 245521163 178978532 704991565 117366869 701656356 140281970 468302305 921347783 342095356 383589082 571550348 66062565 852016796 438348791 706205037 491381763 959250622 401681329 474140892 488256028 6593847 447029211 577084059 822007201 832890526 848955302 545914231 183754162 212665495 903476915 718589259 754149438 902369984 968240132 83480826 426508868 603550200 192807683 718262218 876417351 321483073 722835452 782841785 562638837 308771716 140909442 954408117 324749512 896738762 334281252 418607005 977318419 416300968 533011278 473658383 42054786 970268348 408598444 263698023 129539310 654322968 634240547 471603590 121040340 604872210 861070954 234062974 859669745 456394304 778625185 520306707 758563437 4623014 840788126 77658438 194211696 838980358 256031867 256474279 902125469 701888001 677888452 89262332 53117292 828513832 940447292 760373628 558885700 764184676 934824742 547844911 872215290 920197435 393980748 384741788 687329191 249405335 833568831 733687545 409469268 803992810 217826526 995109431 278061091 998837056 340967680 755802599 213060904 817825979 237998487 272626969 289875906 797349229 452661019 788512811 427835315 832755818 68322452 80562833 867039554 189276505 549307891 973556487 211526269 774153822 969298626 489684931 611218540 396496909 226025593 619952882 506185035 169814036 89181740 805145909 429215693 305496738 673327878 449016037 970454521 874179249 274253895 179248276 438860022 680057079 108686264 984823898 43712278 649068 728491886 744552320 676474154 258999146 932373095 17150736 935119102 842785751 317372913 772844643 741340348 59436635 241143018 507273110 110358643 177738 118482287 784914905 564210579 225199835 911994837 862054701 902186712 714903432 986625871 379791589 627637574 346731410 534926985 762159728 435399779 131394846 897538896 653740183 168206068 207085443 604111686 543471578 190287876 160686592 142993130 250602285 15193889 331024364 429007306 274727962 221918077 815782789 118562638 734555701 130971427 442948338 330432811 823344784 379646538 601440294 420359026 623364727 111144416 765746204 36092599 54504589 573497695 804225948 388390963 440635064 87394827 494819306 92249933 112657249 162210200 174731057 99559045 309231571 962953236 489205938 541131650 3490013 896995633 609049870 933195089 889736043 508487843 18010986 692166787 353781671 206163434 100996780 506365215 615842121 656444420 827892008 84082843 10925882 155718530 317546697 96583471 568398107 602110135 313704757 98206277 890989830 453163485 44477318 629056052 58492723 657619366 133898117 885858887 582012874 42642127 417628191 13092183 916216853 812147925 426459120 8659886 673539087 201103019 677324147 285393561 374596818 633426552 984509030 204171212 254387101 606079171 443482408 970425299 668060350 374690542 628398089 403791639 84868242 253342683 647619239 346555308 510146846 245421901 819284458 197170999 190390514 221325852 565617524 718520977 432191099 486898748 429550538 325316374 941562677 942996746 401268885 19888626 402031239 628427401 978956250 113413833 807121371 715947406 233508799 203237335 317324485 216894633 647625833 557353542 324918580 993629189 541986152 650210453 582885564 267659433 340084232 432844341 867781134 304124445 352044697 493231767 48118528 235702445 271128195 272538937 2514007 461738568 769512291 742432516 84974291 710199720 626789105 956447654 563429028 987865327 167369980 568399509 730758293 697457230 201582826 899232409 602132470 188601919 190178813 456187206 729978162 390086918 694128201 614325500 890680947 474441298 525435812 257447775 816572082 113191696 501452457 202796671 147410522 404416182 384591476 479586070 279940093 261248441 444257167 739241277 118315227 498540249 698218711 538531502 665629391 583443820 181624756 17702298 607981943 753100551 997088504 570360524 45224377 916705729 13259861 240100881 488838373 175849080 644118449 641350665 174705306 467999745 509422732 408612511 573195929 171625612 403574457 797840709 709826489 407860250 618004202 640234883 956652494 214742210 769716644 477647847 628786618 810892278 479993714 701626091 399590640 95227909 71288984 92468259 221172433 500201017 106173208 499497975 735550752 801750180 793199747 923751056 185469576 93269690 228602646 551077930 373113805 494220787 833714608 216246171 978025990 216000083 267925286 584618284 268869611 259289793 518859554 67519788 393715032 476721993 653145810 642847999 491207946 209592886 406858594 955079757 898709863 31141195 574370824 541065782 861662097 587921022 603054632 592764626 734929170 923032656 872577368 151388950 81224294 337936553 220014599 579431952 155968941 21596744 496020799 125089472 611776868 673233233 518286109 872108740 641766366 212113645 287359012 478747585 933610454 807323852 1768312 623328376 530277856 738935521 231540483 730178728 188536318 919356579 903115470 200375548 177039526 613608878 873760470 741128313 132942596 931321285 929537627 181067339 633213698 689489075 514817856 284465605 175653948 271301675 490881838 887519369 593774814 944242673 700162260 257185756 230728477 715482230 518438124 794982069 853235070 185278971 666714250 81444099 587578579 101761849 915018056 470026547 696891858 953507503 778356576 898408700 918010207 490532439 559930599 898982120 168729011 399629465 80641287 843753803 920683078 618016702 654866402 299803134 974560319 55274500 448509147 937267466 619056936 38869112 754551740 629266429 68641517 113656003 330836011 473722869 564759665 673891986 819354926 770573367 509654203 307034932 275219116 685997491 358772250 224213298 455921540 628648910 985268920 355707705 452137523 681253187 185051127 957651326 612365680 491077164 518099775 833397330 169257158 365177044 77341885 671742539 306140981 809920378 96692448 485066549 128692267 177785698 769569124 167927425 874887257 931078477 683610618 272891600 173571559 955848800 616376076 304651967 232252356 991708495 819329706 945343727 634862065 694728015 974724078 761959096 644049916 987210369 232861403 512053723 953012512 574706393 647406488 718834683 512868742 878704618 927000335 363477390 316238386 503000862 492767543 388748206 143595615 251169233 12360878 104233200 760516178 566853120 232423817 674098323 433206213 474334767 635226273 448191702 796503624 530195471 821207898 722469043 888499992 51343514 999255579 870012843 896403591 323589681 456488049 618602678 694196378 355622518 423573593 303164424 208146151 793631152 485683298 74191669 459061977 206656215 115205591 660287875 933832525 801127833 661014305 681328043 112359855 621291125 523232378 112899356 313944692 839560175 459884535 255431891 22117153 453504173 666919408 237392290 964598891 741575990 836375608 702234068 640325800 129230020 220203732 696783549 441188987 129894396 871639919 398697815 361930749 827818222 64480841 696542999 781393674 899451307 189992881 554134877 686654882 762906974 623704459 909547813 594511327 179731315 956016288 632473492 847133589 75112753 55795778 722083547 896979188 466862206 766778876 741752546 994657393 853791626 139497837 490699119 464646644 137303561 846620374 87428191 979587259 462659351 929593260 983355294 504214119 945849702 100294549 886909022 870024403 195362251 226971423 228462743 182624175 164749294 225796046 325117311 448219095 964658144 475238379 261268824 352923478 74215987 810381371 667360137 967347546 448236876 238258766 948202757 201594054 995572333 647687995 767394915 336721982 409486473 338070109 879525729 169999365 530415880 845559758 971269081 24627288 540748542 304812563 545739201 963726741 230734461 482345861 4770715 900933613 581762398 620263399 66947423 702478985 825396503 477479322 944414580 351692673 627990422 772913864 712510606 587982814 19762739 517926299 138665409 780772142 205256310 889162376 455304863 825426706 624439943 131701927 534894235 359978626 561737564 677828893 821657439 104958120 46968610 391661362 984147177 955876075 761743755 264533142 304378322 559616438 526004776 661640568 546071161 393735094 373714507 488749064 388067503 247038458 481851696 200120896 195693175 583446948 997572362 433917879 949504790 979090900 118266584 51091079 909102905 878150943 789011888 324307607 72996531 821528381 619334480 45678248 652191264 267575810 338112831 307279198 481073805 679827778 747954699 522885503 992659277 452188617 593983245 619075405 722498802 74741280 234023850 740361870 654841344 128904386 18312088 199583754 9494617 137886884 135433398 694949657 664260448 24256832 584922187 406170210 55631443 447569993 928443859 951623766 829305699 1585803 907882334 258168472 412874294 36082136 919996645 808076848 211089697 693917639 780151119 458352794 795138072 890889898 833239543 575297235 970369521 703963567 35318024 652826726 109425002 456190117 10385978 989565165 1169268 894411120 689111817 831978696 943092136 323261662 682999126 101893450 637503759 816288629 835181915 720836183 881985566 472552220 319183283 67182424 870706769 994664850 368554310 694176895 287087978 356203256 747999777 442686464 975237061 286973193 529097140 827702852 578766934 156062139 937903496 607545573 504095787 210858957 961052613 842738201 242005072 730268958 989431258 73626729 458201589 990520180 357870395 705012374 672585290 194484918 77289877 121939644 475064795 28964340 462262897 35856059 966544211 747971652 468064628 888715633 350677113 866539767 627906933 342181828 764818550 642000388 568948778 270843826 689257456 620923882 33512020 61833955 545948038 877309512 31153406 190749817 565354458 571337260 200512893 250459341 169501480 507764874 579172108 344349464 171560343 886714291 868146475 54163568 585972239 482605906 936962916 252292044 986967179 158067388 735292744 679173276 151442312 409719387 601538844 479570138 929631714 320784616 544357065 262974416 921709351 617161681 38157451 450727627 924379298 125207642 228876605 522227804 445679941 590100492 422554335 767660372 303234375 259847554 250000105 813431355 958983031 672946660 789763341 212215995 794908318 699110483 408818387 222874837 574719504 964089741 30039649 436958704 638880350 33467712 454596428 412481566 975136574 289675416 873260196 46707296 897941768 151637265 606066652 614972380 846084327 840515703 801034877 406236729 655293524 402794043 828807546 243577842 813412084 803175195 997556231 499058551 744927072 75509159 580886333 946209648 265171414 82747948 694146567 136144434 77509465 43783432 797341116 639211563 642679383 451891365 556064931 439734478 513374317 83552037 61674071 546654649 468803217 735807709 144368018 752451162 874948407 483195947 742061134 902108090 331030276 911777678 799975199 585646889 333288893 299583186 264672581 415662748 806455841 272427505 789431815 714297288 399821640 399965540 723558605 517681218 586606003 800115013 144710958 139114034 612738359 33608617 725655143 811538511 899702985 375660138 966217844 904110019 172504409 464159366 850654136 826350207 653936951 344841372 389490881 208608939 583931105 539521780 709650886 556334448 46764871 125252908 122035102 777897548 566670907 972442376 52894183 2339751 832183660 220089616 674311851 904255950 733506007 919347968 97171477 976871906 874868409 814453983 924785736 958344449 506700904 982759657 827800874 485335454 194045802 528214647 868030076 307525083 4277306 727922777 203890179 299217032 991816448 509847853 477944745 914477233 85524788 869768336 125828751 948299086 44430094 68796600 123625476 794880448 141691039 514505724 358997960 789401903 409528437 735623765 593009703 676499832 731668142 954339284 121734997 686220843 753372159 347325755 67824341 844463094 185786529 916430244 998832662 792838676 135577828 795826068 289326815 122988547 141178866 145074883 911947856 721760474 773891832 581773574 565421486 815555887 475861864 232080061 602939670 273989666 313920368 593238116 808171358 946814297 31815486 511048478 146686451 691837402 193342172 625905693 363751759 636310399 768022832 481943113 603397064 735449 314717939 380941152 908594139 411863486 74781043 886188310 448323792 658838161 796412190 1135617 304179278 770513457 864277540 714822106 957655146 673933488 15759521 312939908 751455018 620696697 95020274 915073080 244022185 314094654 96785844 508305265 649504205 622620582 952388497 519421803 98790164 1029722 631413778 757672382 626142895 325916160 589789295 148106396 175311672 375145418 351340701 851318213 714776366 512682182 298155389 158487699 555702786 903321444 843399998 893172920 522231653 445873909 253144101 437572384 914234119 142317292 351241858 258010518 691706967 8570313 728433166 609945622 27915449 53040999 555399721 571165963 803226791 484120221 443961307 521380238 221008692 949275450 794698839 744685487 830348193 924684516 632145336 753079724 655995859 169399593 652624478 815673309 314606000 298253617 441193964 919818095 896784177 624440988 196695895 90707063 328544101 797826256 185475577 586741551 709771419 4524702 232323888 122709890 215389550 720381242 556530641 393263603 384995222 418986740 761763942 175298868 683045209 275521373 908422621 33945675 150406173 35127335 793331539 634643278 795576896 662698747 748443750 127679746 685971850 705214086 189755310 456539716 647034218 16592080 221892239 663114469 138641645 745832543 551603024 861804143 191462681 413636072 960795598 274204946 318586578 276711506 994697707 995941496 733220835 732603370 852758993 625277555 425151976 857186093 993376600 892191687 707955906 890813054 967084250 367120119 972403152 502766710 282406211 132884176 957544316 51425574 393357651 111720123 573419969 439323483 188612573 607933059 180172574 990007738 647689745 219507203 630581940 843895587 188693733 370132628 128218568 953546555 522978816 126426481 389351714 460720181 798004459 812606809 428440616 472017962 419510791 886887183 42016396 135015551 161837132 987240085 283607883 660857386 933678669 657716883 882228231 879952314 702323472 200981939 665786580 180083297 199487404 227529680 145863650 637351245 489093121 9918999 92544357 89044481 9708367 705342222 635266736 800474410 143188003 606094023 891676527 894617014 260640236 349225319 973118858 578001341 324033360 853123769 14917425 305891962 285969197 408107081 203757769 208701259 629167255 643507611 489219114 9619697 126769007 695085105 858081117 4823163 176741237 558662741 771732388 695329127 989318813 428030515 244262629 604047929 337188224 839064705 828180938 886963032 527759864 359951862 134250143 708848744 901118549 552643127 798139081 924562987 404931681 986243442 307374891 20535937 60703332 52760270 470784522 655041686 471034549 406448057 989169716 923590909 909856309 788936221 674279579 134795825 413159432 582326528 365391945 154413507 812120282 39531964 213990236 614147265 392558230 456506042 428777577 202004599 954187876 241268970 353204337 292680958 594888660 976640146 93901896 164883938 598368108 293638128 503780436 87820571 946737517 769950548 753250186 929003254 289762562 835414190 451254785 17625505 290810829 641191703 884006632 20226946 684875598 469185915 28799247 897563287 988697570 372060807 836967462 552812689 732762974 861264323 969229884 359127679 874823500 769127215 150647071 934345520 141557751 667567432 413516356 780133092 833222763 579377877 169442897 840466305 259535987 272944802 389933659 186163890 286322976 203383645 43820353 704093666 491382126 473241207 257057843 832969236 114987538 866803546 604901689 800777552 426204867 807912674 248043605 877278266 493048067 813288523 47882364 429017356 340320981 837345918 357370719 749544472 107368821 459605879 581940515 682041798 777435110 571329728 198408309 379272850 970192977 638003000 66204840 466307964 118040206 499231157 834187584 318911458 86038869 466377725 433414731 868555921 420648374 695749939 466153575 290969328 483980386 536606461 639452646 507231447 939945125 85676159 882499605 89563725 551101838 209652078 298250285 646872254 828872739 513726398 789190628 535535010 790077597 766007390 654634428 880980462 764675336 992493501 539077161 105308113 432521015 713333436 173522431 953527146 328221798 887416290 354768376 429624449 646418054 710260087 915667245 574625189 936283131 116118515 287034078 231680724 270311335 223108085 752864912 558829730 558754661 528362164 722194094 782296783 504927889 513324318 744262408 394471912 397884587 125054387 759459827 377053033 681535041 481408006 212056004 853131934 15773685 382628484 666972775 553199050 245212858 289836334 665432414 250889535 145986660 184889150 783109234 633362960 779414303 932064832 262411336 914380791 363927776 140661961 153153377 973169972 656107730 908092659 55343533 755186235 168465329 221878234 551985040 257744637 817052342 600380115 997874933 178807644 821426946 543302658 624940406 999041431 99705818 422423659 540203088 639083529 905276567 910283440 90116191 468715400 749767600 652231815 214321939 653730754 23078714 995940598 727181756 408090937 436647002 605099755 463346808 998334494 828803021 336496501 397407583 419964998 634968865 226700856 342522586 213950624 445233485 387834695 379484820 374317901 607038745 694115190 55588789 447875671 32654008 843063491 543320664 928983231 889792999 116411316 356519147 193380116 269566235 553240567 445230692 721434264 652966352 753735993 412645025 380173103 435864307 444606592 135079998 54998366 761456803 685954834 244602016 462681509 393446486 580498579 395715911 801316435 627477571 561563363 40590983 719425555 671748356 164746765 617727317 253056942 186842308 914606496 304325173 168634939 514215145 217963812 698342757 532766119 67178536 153267966 925026950 82561770 28489535 218025934 930009009 169685329 228763558 995503749 744713363 837929934 247100771 105516996 612618798 776792243 95436986 762547502 563132853 829005674 227725895 484196167 599462672 733993262 101043590 129974350 280683940 836616821 477004629 834973118 937797067 284950308 201767521 708566636 147246520 220339568 6256225 724828363 301759243 712673082 108507635 669858577 420164800 412581263 608237524 978330138 675644075 901503943 965620133 767954381 834763191 987090338 757121574 915753198 583644649 616727015 958285008 152029553 323456233 187532669 111071603 850823706 823723825 536419394 232626931 143458671 144272169 584533689 907853480 672577148 981963900 707852157 635441556 483489416 513695042 184725261 196823816 409048453 130859388 219165838 542734624 31000649 764423549 536859333 497713414 142957778 502211577 283198937 756089879 100899960 997610474 373311157 186221479 313835230 125758456 452514613 432452451 10542916 729956275 813862283 513599013 764502968 709060262 843072775 516112936 325782132 606733653 600120617 676086585 337653040 311322688 851876270 942470516 708891162 250795189 941316313 313814894 959709690 379153287 529204250 829949606 530717406 647605740 990933668 731879511 950668085 556448723 125561471 784227349 297627131 855373855 796754859 544004869 31757203 166747607 316850086 140078919 733218541 287722240 82947431 852316368 680560692 949960469 865603727 748512768 472334419 762108909 366214802 328728826 740946006 544628439 994885803 562374704 446504698 864834860 852186845 176907479 966837677 930956510 406391113 32294763 54733526 653845404 515564874 934714953 400094813 663850186 465429732 79278546 19312929 528856182 707395441 594884638 782565980 92471276 13165187 424895345 894481915 917061666 568710162 630933855 190977359 912210577 815089444 423997080 1644776 886301997 574674181 326173318 293891561 87520316 173926846 296963869 201274180 403056984 790327683 13583921 166884733 344335 742405381 777459722 598761927 362539948 50533401 947956726 176651757 726817657 108436428 166541920 356315211 631230233 319957675 871790868 588169946 917704618 347562216 210004301 339807060 566977443 41863197 942792693 668848519 457177110 148067110 6987480 831323566 277668723 752202886 236943279 382185830 607353420 342329786 415145391 926198383 131492023 966987974 421907577 441496003 655576074 764470353 306163538 955634677 820171684 639016557 740183102 744291676 103636023 105532923 878856474 385822749 743336874 53098672 906041345 545355739 487628389 663580192 343565093 163907960 826694365 617374708 951291476 450241831 535683258 81367038 489745735 444676028 485438907 107053161 132849372 679613288 941263319 17195319 225661567 664793784 116496967 384147662 43149006 697530017 955053804 668361605 882239087 840408058 597971899 482752545 853866153 447647236 888147251 482552418 115166377 968237298 949206846 461638585 21844645 510132893 743340201 660925328 999750831 940774872 96430799 236863296 644571272 468539250 957469045 31857067 878642897 797708416 893403600 87808995 386443090 762923345 852878836 480873813 248663164 77017981 434040141 825739882 538949132 45030398 92302011 412012866 583975509 815369341 347546332 624655306 423316476 405083991 376875031 757111762 547408383 637619470 478441892 733710199 250777329 124642309 92061714 290160644 413467662 833194403 330808991 98878318 494852391 955069287 365550266 128980163 694992867 246085679 882315008 863834075 526332894 141582619 901583626 116077726 482552597 78348773 602439379 410622566 316062829 562159772 922345561 877715522 724734837 539532775 937105669 409661772 351216590 573125208 424055635 501463390 926109322 383460978 216861081 204936928 182064498 408657272 558758930 301063030 635380643 825647343 77600081 978195851 223588277 665572779 220232516 118810126 496133105 75288958 328385331 176339690 5170516 396699819 670598652 969650936 659708298 200611665 163535231 226446318 817467184 825318294 755326098 302345461 726556566 671227212 403191432 386476042 475611380 953707820 94392394 617055938 940319816 192975202 899894145 753431403 695133510 347926439 346278284 483750751 507261804 501909039 223742703 864731461 695744287 991832366 785735361 759747850 821419013 980702324 815721769 566147452 823763539 507729730 123505592 439169889 809112391 822023866 754703907 468478062 577788038 912125614 300391291 245354585 243197056 999188828 366490289 61279724 258627555 206508386 128958936 861518643 549252087 386576611 647870413 806125238 346082039 62227806 600092526 216924840 989787072 316412264 301121943 799757744 593634713 301635188 715103038 711753993 675193863 631803205 280439118 564637761 192088196 828186465 664035527 507598492 748967393 558794836 248041304 993987890 812996741 397158042 660180429 103246343 762317086 159618740 618207442 689506399 976944969 500494330 404033595 208552232 797883010 926831790 384402205 523183744 887566226 997349269 597295050 612319882 768711671 427329056 702365999 581896201 59917528 93905984 180453144 376786587 579262249 939269519 34437740 619351037 946504116 426944233 501591522 663226913 587531672 754443229 438458934 117784876 550306541 260085401 631031398 103760164 272631136 678900677 932356839 189709913 139711886 617615937 322063602 723280164 353886363 564616109 961031798 32144287 403663524 454083679 773988599 562656564 91104218 610210846 444047181 706596995 103096046 718792608 975862153 137275669 155737450 319914603 15291927 720639375 35436763 380161900 318486999 119466768 339152642 119443603 182145804 271214503 986308686 582965156 675405569 20037463 107681096 435799409 480889177 124100009 801181516 409809003 939710220 883494507 154331751 150653885 2861075 466486353 494965084 852868235 755674143 925849154 285369569 466774427 441798241 727312365 312901325 210222531 58974960 170568307 539948272 296213610 134946669 222280139 686908386 166870590 842585859 405331445 707057408 530079282 873879426 493715691 564754180 500011292 239664982 189175790 937837272 540273885 689991197 759317097 960619582 253351247 134077403 632096105 291616525 222023118 633288640 801730742 741433484 179168219 679418462 375126697 841458375 722087374 887922074 571529138 857339679 174782100 489621687 705215885 247599367 838699834 88384203 963427858 357078771 73372934 786703422 795987265 606285661 623463295 123854844 472634013 8241664 326763358 723007805 216022290 243934896 955495141 927246774 224228784 668313690 930986230 949906044 975719150 404371752 468881392 800346341 916812963 12980535 21435313 218846403 740493453 971527626 929897308 107966133 278881459 404920444 353191286 960942790 870810706 433379910 699617373 256300807 298452473 385525844 376138496 477673644 148546948 147638075 626184547 824483173 797294461 342991165 106528758 324225945 295985142 61905451 339995987 619530493 6965561 32697336 228587264 807167814 516920267 659603692 509454340 720387080 483573867 353478815 161911507 183709617 660272638 782150843 410519148 497317554 70702973 655528894 353263804 136219555 832393898 677588326 914227361 329523008 300780595 35589590 214743404 260622553 727567688 900160173 930305343 561311806 818515041 732841189 354083721 489364670 322519566 68312060 187035027 930341675 225535142 341826905 287886777 880344772 492040469 262106347 548676589 311654580 459897211 617443666 492135265 912224589 250478938 403327565 995723792 827799619 312678635 520457502 341811284 647655166 144625612 558516703 546451082 409826985 64361700 206166194 564088202 311812568 675885461 845440280 849280131 875658099 897247242 31412110 517138690 398315749 244605738 791909997 151901763 824795525 750401904 705592937 625247569 644651397 493691183 650351412 446146539 990906446 472747589 506007142 56586490 77744532 728947062 330031910 941873686 671419948 192369920 200137395 442153718 836528459 807746198 897916941 297267722 595500539 24309610 854488544 4895003 372969029 898790343 548493313 366441793 198575927 874019271 406108507 585664227 702596416 512716759 797190949 286693581 595221969 460112403 162970648 302847381 391320237 684317500 327960574 978218967 223793217 23619185 177455389 395311033 606385269 122076023 574930206 680287850 71055702 763935117 258523567 484238046 118282720 205741801 257348595 108079228 75469206 337242955 602482409 110424445 553696191 332555872 3469847 870768349 746261771 322393541 864149600 10914827 343463070 471585622 813029244 886603140 283843268 489268667 703176517 339464972 698970447 680229405 108281215 949190905 235563187 736728618 122947953 829700116 647708256 704870634 153407704 700074068 983795775 342998864 547162146 918056539 393041601 533275048 693920689 477602128 585855003 896529205 557873429 815836378 959552540 912888076 481031351 500752046 528558703 703126210 684127977 577875171 695791338 403419489 16138517 791183276 239445422 169372580 824647006 933177891 907540054 505954646 583569223 139045160 463864866 870652220 728609600 930672164 175811309 152369895 179267263 381350670 142150881 317756878 31346174 31656487 872331119 873096417 663880182 98917385 325853744 768411201 799630762 384311980 620162357 363480907 444667975 238785676 66610216 33924244 338577556 70562717 78897125 747044642 841414607 99527911 227106044 166283793 462120539 198380276 600714209 49747751 358616933 404475972 983198547 386806541 866259361 925196708 661502297 256935029 406577907 780615596 678343896 552710508 117112055 142485456 327760515 976544723 461161762 569884646 519432276 217311929 568577942 825409726 971221387 442518083 509763194 562301561 703925077 335835115 297406507 964505708 962836522 5807487 615693130 527366575 438686370 295060871 571172343 596299244 892548818 133200311 362195324 310525611 762397791 802057668 661380033 607383548 471592913 284661452 524715662 560010577 515307304 942510712 34709251 221360023 365890931 252556270 298276259 762521745 359444571 231189348 542225577 989030781 214796613 148685293 70733703 912946787 520251782 734187998 992540042 964743685 487643690 815148407 870068968 26449657 331534599 394815995 476117944 146524733 671615890 779798128 402045247 88254381 814425405 968376812 721453659 227941345 577664732 201221588 873105365 310255823 106749474 771800150 142739492 634539946 365144151 599602241 18531065 811089721 787272225 241889631 180287274 344800549 441663253 884579554 557298966 186424044 96628786 318720180 546919247 910463851 411781305 734779308 191627546 859362998 839975773 721182328 669018222 570300170 778492342 358720429 827843278 663000062 630245555 291343218 606093524 348644339 858397250 691967 947791578 450088510 280451861 512278589 384540040 767898610 941878528 115446992 422218758 724495029 148465209 454560268 273503671 455126289 156387014 318433542 729717572 479766831 49555247 17707558 237945782 726069294 635049575 562350520 556059397 997695142 680778396 425623781 443337588 300996464 8858478 297136888 801907085 60748383 529285348 789092085 631072309 794343772 856144878 262725088 647597380 358224218 331754862 847307642 181640464 344054888 432693746 97910184 239090994 491502735 172613653 252836536 36259082 292123600 236281683 998398172 848190249 532115490 210067383 507597136 833373336 808778032 924272801 750366897 735625281 370532901 133508899 720856906 530713910 632097618 540167553 273227580 244003188 526395135 265754372 857904946 820684800 34403320 918082069 38567600 70782934 458505639 655272164 151940801 194604860 567565180 519155580 336399745 777257836 3594813 61947116 704882597 159032317 434527645 614374671 103656638 58494769 182326905 477454943 637936857 836361566 896304797 107331600 851280174 973446613 706326710 323320974 688936803 363314475 724062284 317196290 864678579 247007822 836191000 404054006 97113638 851579665 159058185 644187065 45791253 626192471 717109240 50727122 218040958 888186043 127409441 160623921 144070385 152418761 108797522 459158936 270568032 81773299 970484960 182806877 697442612 206755093 495848556 962582080 431769115 231147105 818870948 844990704 481737999 354735650 841378999 926084639 95957518 740509884 575384895 271013968 810144551 431536898 124776368 641378425 274547752 723431163 563235831 424942199 353853453 455843351 422294132 660832771 752157019 968858894 199105116 511567971 484737404 682928083 579113476 653179182 350830899 88735990 568580911 754894402 746216092 432149465 351019993 956069334 258039408 143079147 934775798 351825449 739893970 803672099 258000096 753950419 583411122 615245230 75995162 425809813 137348370 470106379 827691235 508221085 332989765 536091835 267339478 732489787 629457688 764309968 781516198 69603756 926922827 857370305 761506751 477177040 17366915 647811078 256931399 419219139 832103255 148143494 871533391 771211596 991516097 131260249 167691166 242777330 36551128 613746082 727850731 230595786 544205122 126495426 861263160 672127042 654372212 145518125 756209372 537976794 886728161 310051810 764461151 369408821 681863433 243379787 937910073 396333700 91684469 854531923 537969759 81263000 52343244 607346953 792700378 310582632 715404273 696612139 542681999 882567707 501977117 251250464 162665858 84345412 111603848 67375010 621498203 512174331 834667658 953649469 82259943 766983938 7398437 919448201 988860290 246160782 615576348 702921039 531482735 769035692 612964605 646119315 649028736 710118362 187106742 915055158 532018751 458220709 219942581 340000410 565584866 929478821 567234428 881327170 936676373 20378103 619349210 935366964 67816110 602568778 45610480 233814621 867640419 208981638 506081819 660508196 485850757 637305826 177011593 311512033 660257297 991266316 143376828 330760893 679058348 550179095 723744086 537444603 621121763 552387445 423413776 852164722 722623540 465600503 108203901 852175537 256207194 122423148 191024084 201627925 707210532 940541790 19109193 76884201 629924324 729399750 704392966 238679468 884932512 764933286 357434581 89732338 984696437 153588415 738736611 497767389 893218355 750604246 333988623 574760505 30523222 244133006 44571978 414238118 819962415 142945918 622770360 671797938 1409420 325671344 556555472 206211375 157460299 916876730 623644049 267170148 684843230 516642155 50577696 251209212 502667200 610441037 356631062 622284640 227582106 532799976 926426826 519489198 640703012 275694695 892342532 22840862 494116518 43223340 522585323 993394052 883470131 103118808 871814340 421926784 187107094 288084544 150111062 679073533 382634009 53306550 200487135 658221448 3646197 554310028 346508937 695011016 220149401 452467345 649520762 108047800 162383969 456987424 812742085 51218745 196762115 378905380 295359103 725862734 768690516 63786718 684811973 4338474 113548664 51337112 585697182 132107477 620729250 961906337 812106197 555977437 609473378 221394309 684486677 60049488 736255551 48740823 273638889 443985245 720072554 450409173 659475029 617954956 656793444 230601307 773824098 547621133 252056132 40347252 749535410 647852054 751113530 585247292 308651229 361538099 578716367 755883979 384083822 733918213 661769160 787882910 344338235 438261582 761910389 600891499 257507526 914396155 457756942 647792830 73938040 266994532 288848331 563577640 161428520 360262458 37716617 136656493 491319026 911956833 515676098 152579576 478194494 35029091 581967504 477874089 749397058 626845755 286697845 412807458 772277443 467415825 96213289 212618324 132508370 248509240 760630202 262096138 420627983 111453638 586731071 497482475 800761655 629345140 836036667 152152402 703587088 53216594 725562963 952896623 290332501 853146766 998241870 238339618 505861697 727663873 107521782 764987453 656722591 349292497 632730878 123258797 134590905 239688067 674983216 820654770 327169161 669683795 833780984 797354295 584074268 320635638 826442994 340473127 495654224 461406386 478483250 810140780 875924703 570127676 369762585 119211755 305160516 402581818 372968035 392328621 662899871 300783286 790555628 907149684 960838686 58400645 801528393 637029228 868893787 699470363 116798745 521583050 141207633 507450067 339588104 727367220 232247493 536893185 656572573 524825200 545604140 142062491 157260913 804714699 435196221 886178694 247668630 354017214 154489537 724258975 110189542 719179519 182363606 557179291 464518318 566776324 301781778 938309493 215803931 768593933 342733469 26722953 324744105 586308712 612502408 217405464 716890035 59355783 931539258 477675685 286634377 49020401 126779786 889980703 277593867 746914448 597419556 892884475 524013448 694735586 314956735 273912028 354815127 232220508 384748778 362669336 852795488 699443602 682246678 775752738 56607322 482017362 719554971 454205994 671683860 173779561 183991340 125045986 986590640 354575385 955582571 827615652 395192584 85259016 77918425 595341207 844056155 959358086 36334353 698723999 425960816 372362003 129900033 956795352 100720121 875770370 371253775 601533631 32166019 175575427 230171710 228498386 247982126 607878192 267305958 454570456 833941357 431048580 48415063 42612670 979685024 218870921 353739233 438749329 809653848 517531450 814682112 132571376 314428782 717792993 649346092 888226031 361461313 116712224 931306771 554342011 16548068 661326973 199507896 257026812 175895822 15317177 763690501 569701297 561237831 135282235 152250691 968806307 628962267 655062721 835591178 377850422 948651202 244229931 305940239 704266905 963625939 35939219 477278540 218962500 365132917 759161145 801184352 908139381 809012829 704776447 383445747 864458529 391001856 80441440 352197832 772045357 742062262 585303641 406259953 798670939 200129738 119654144 189484075 341076987 189931578 992369373 76493342 564320515 396720343 390515001 248597886 802181585 461439088 490428050 413584592 624297676 767497737 575164823 815026843 685249008 764036106 372079352 760670749 998490079 186400890 9336115 703364034 683168106 931724016 467331075 90544403 589604155 870101352 679739714 272338645 710328228 505046933 421441827 196044045 853772844 896551473 109104351 902948366 291155861 193634261 866944006 150250669 445413338 9630802 948674535 409542338 221475044 863587186 818400410 581576048 882087744 30935877 244514886 418712566 198420140 767224156 20422180 112952228 222924450 996519255 111961393 551504917 237809812 699381143 819222783 322732801 311907318 283902696 653647571 210468915 417251397 677380602 468127765 403556076 880145204 934634869 481116018 700537372 258868759 822841402 109950040 746504596 538171344 614088585 724349832 112573108 300699971 741396031 395675194 141702212 677793152 903523752 469866410 189287523 883567868 818362649 930346188 449589336 512736293 238939087 873753493 663903448 186972112 556307307 88133004 828259005 970922456 589790607 452273111 759549747 524777304 668072178 434791850 880013431 973347425 645238845 601771874 527107337 399242054 522943581 962360662 162547893 917974639 764712630 205942917 966047690 720357704 456490987 450215090 258102242 547849014 691480805 87490276 320428299 445185889 762994980 411225089 186294459 530247455 725481876 919175396 223069933 51547550 713757982 319176778 159698812 713263688 196353209 95668386 439038100 148486796 340453488 978236825 660529176 448567053 488535684 937017212 837723724 139403264 892261589 71302874 11000906 93081680 232993588 848281517 117793360 345916956 209369204 980905012 854576979 411296051 852498875 946306969 901329467 418803239 233360792 201655892 864166321 177460930 533853421 19184159 326701028 354286486 829760562 624494707 48563397 262953929 918695975 152526829 27046908 237734380 12973627 831553140 445198676 179089746 995255275 868725964 138192421 39421862 98451715 211544797 30096055 732688958 976424021 534225714 190023099 310939755 468416314 605629774 234558418 197510508 970350737 159943503 583474517 84716508 599085226 391291654 726845512 646170435 598631304 9460799 162926139 967276421 279000409 682468138 48231477 180305932 788807615 410528758 945762326 942316469 175968286 103407886 593081926 221582642 257306365 83052846 15498295 163413610 758293636 539580255 827711513 292330808 448472154 514713733 987250488 82541228 757729570 466271040 771686977 154060294 7329163 426669220 679571508 837937756 165697562 94653090 295172324 685502351 465380609 535018914 617289901 191373725 898925254 637764612 604751895 360482783 524820875 192117778 386342960 23651693 426837753 807970817 889269610 863983872 737526954 750946539 61266418 212841275 835220895 454228184 64949635 642020682 517269112 275902865 339651814 309117845 284766885 87024503 720139538 682183785 807566270 35600274 576475179 776612374 620350531 663024112 819273956 389896310 286441459 352170405 695112824 987483430 397405149 26722488 867628221 763106368 130292160 662811080 301156999 809221149 529580077 54344618 542892491 521606613 757730758 981007579 170681390 773839145 319611262 698128781 725187914 749058174 249675643 591150044 29513667 612515876 640275854 260926954 488006479 627176313 886615554 237071538 928287264 130904448 625715697 834778944 851845366 761683898 358503128 618814610 65003388 260979828 830882875 62293917 896267871 424409559 510618901 913935533 940832368 957790282 15956488 246996335 555670904 236817894 331917489 930493581 607682959 585817801 720411816 332324597 456665143 133712797 576489256 823804389 576848955 207578554 985826133 716258890 540385223 876539533 520608293 492317022 967327184 8650095 317931846 704485100 780950667 909652716 660390049 110957433 333289919 593950133 798184732 507315559 891421455 60272441 573972779 331870331 598355107 297195260 154237987 691037823 615850282 517838891 559782854 830043370 384836111 931267029 293821735 128449620 279349978 687431438 561268245 715546398 953369466 252710764 208213522 668593193 716242781 63018675 472588648 9264207 398992440 25487371 831214442 806250360 280278207 463309851 314672010 903635531 299525468 186787372 240500224 52674266 999199827 765781899 790816347 989223835 122039757 492935257 93411422 288532461 553588947 92245701 409228365 812492871 578647210 11051056 71619774 980042024 474777381 107888946 642841844 526588151 278194580 995378840 652217035 852797810 23730381 489713304 653070611 520450156 428235522 901866047 458584811 483624462 232292948 917119862 415667379 170127325 500089733 812280306 777662818 895656894 856064699 370779724 905644757 217092769 828777403 887515257 474835171 964998422 376016369 631016497 708422697 254678765 696387465 525242493 664552457 495706405 804383407 911341196 4562936 258940875 686639540 638719953 959063006 242459779 905856255 264026850 697641984 497963179 529000403 916184801 589681521 428239217 957391861 355521096 966775538 511638040 272867659 952683554 118763904 766859366 898498184 152080185 566488484 981101769 32812857 161165846 354104547 134342788 498351852 187178661 616607358 991076398 324407706 261718922 990563469 555649998 711149988 780220057 839397743 701339142 220019027 886791724 309138695 181113513 640620340 540548984 50743106 925788126 723932707 225702454 506873382 909400291 543979502 928979841 546363801 958021265 485072346 101318865 189560585 537971682 190685049 288143993 755274250 340415071 180982443 512287963 917596439 435282258 560036640 218425778 216670252 845655387 534170489 481457847 993116667 8950929 907626624 707137113 244707194 863122500 4479949 185049853 123403754 58773651 590280754 668619 597494410 520553275 289593812 935275747 806405969 458848973 872038384 185072775 383482234 191579012 209725346 63642009 230201842 907816050 94061574 160627672 926203176 462406283 533840450 282647087 397194873 580566579 429692716 605382058 1085337 359778565 86262238 150560791 375988138 854172693 637839604 932273343 163940223 29343981 249789347 988764340 904021134 787449302 106268421 8038908 663959762 461510257 679218758 536415696 26236646 231254945 528190503 562861597 582777415 903291933 156048564 390002304 856013332 356053529 557791034 837388706 360280532 835813761 103873140 305388444 972924302 843222319 173508862 542450307 510193650 769483586 312747959 488612827 55857296 110524203 22494192 879644037 873069859 439144746 664914742 643187201 581919603 1852492 665434914 276683470 488881776 861281269 909866683 615967275 828997689 848246825 799634847 576339775 713961777 448424164 213148772 970696381 547558726 716456673 675566783 387921643 421269472 777830106 566861287 988849635 924486620 853077379 40807566 325619393 83109505 993361510 873234721 984041346 639632525 211469685 976531344 731604405 96547991 146089083 168067497 109324297 307916120 719576782 505711885 157425567 763918433 378294193 182361181 517370992 267202811 7701670 33563015 513012078 895177481 747645100 908257236 542930371 932396770 849476676 708258147 765457400 370491834 641510734 486626377 203262242 913179452 147375409 736228038 63914657 167580057 343685603 705835272 559335996 606149431 845961089 918028865 532340835 739621438 738979591 911377054 416436172 423479641 577888546 815727485 792048150 808235704 602113548 151809008 858513736 728048686 978402330 524139643 815010841 318760088 404641116 139555684 796066917 909223469 348168528 892610996 718404149 891159460 319748463 38654273 602729066 419663323 293454477 523953561 73896830 497737387 740639925 128222447 160686737 274268147 980796426 116086972 658570903 394549003 162191672 984635786 768267445 609643476 831417985 28268825 881945259 991715197 86918674 233959170 268457412 502568695 705992687 101197065 597373283 828936831 695908327 43988822 767886154 272370652 996854698 270814064 826677731 960708395 442115168 466989494 302443154 606944844 200809754 639449289 506889440 738637135 972904679 581748754 590509666 975689775 130855598 202464499 984758007 798566069 675234336 216297525 16676399 412287425 345209500 8872478 188960889 680944106 255083396 160856007 278699052 984717072 633494197 383958170 136039328 639012424 694263442 592407502 999959273 713697762 536040532 549775045 221625828 471029372 515261558 575189508 496262915 679521126 595302843 252767991 866228568 636131979 396681953 598422905 764302388 741913556 330807986 665272470 743932209 249313442 222044895 572798415 634233668 582273476 447686663 52730144 294532307 199659185 828600985 239635744 561010418 45083439 947930452 626579199 893922810 447143195 164077483 535128369 984465300 212493153 491257380 47976224 709121711 878055396 100577188 608070389 4488398 400327303 898965571 901753741 241813204 137195799 686871925 512945131 648839671 539809054 34753356 35669748 254482305 142741230 36540704 220062876 748230606 533497477 314529848 324552986 803948874 500984390 880481530 889081053 36741628 387647248 800380121 449835868 915686913 249730257 758392171 220503904 639222246 660655805 330658113 970604050 604610493 377225197 658595275 68770637 750885980 615462960 745128833 644533062 317200454 866803601 582194308 675657467 826693997 983461220 648453799 151541634 301904511 557992365 144143831 926524417 818036578 314779583 127206229 221940150 246223202 507700036 36067299 571593683 476563149 453046777 855254060 545494644 234933074 402435767 213906143 664703568 995131130 983288735 3260481 763812776 861500883 794314655 15170373 51948645 128391573 894539717 743263974 287674111 46899274 166147533 787711525 562087134 616630065 976954649 375531638 565996399 228818069 119408872 303736802 915824130 289928488 857755566 262759512 520344056 386604331 51790496 846003250 573656397 391094673 349091524 844843127 224365493 607260324 156837972 823645800 371625498 311859243 723384902 607499087 889653166 585419135 199078322 402873688 696203013 875264579 893518096 196637563 92486775 325803061 606996118 981992559 736042884 749735780 929729005 891462180 568768214 465439692 382240531 550710012 67845712 433895459 338828557 186711386 592760048 288184990 469881926 480502628 821388509 991917171 266102498 318732022 235553530 130668653 34532892 564830157 614182988 55428994 895156200 811138119 159969088 695354901 516688604 42153873 949898487 314460257 988652687 753012651 160620253 15546443 640280276 397063116 194848736 401917425 882912329 697778787 982992125 711266725 694817146 750869308 794351169 693424513 768261304 359774808 565215232 90461835 501584308 52352314 636979396 268011464 19588591 141240823 835555216 663902117 417290973 36046451 63090271 932560995 219362880 222849473 823183752 601362636 234254112 945875457 131257390 706685524 652279701 132334232 207782579 77662599 40038888 729032438 204547065 929081018 962635224 462207748 368556967 395578285 519133220 114516048 379615889 903281229 96970817 990532497 608020816 219072474 715439815 948737378 2680103 261526595 764224555 475913865 725476461 167768483 90757847 541557842 312593356 415699861 881824754 181486433 310632306 320279100 586540387 487255020 860143435 70648447 945543980 616402579 516557549 227856926 8204257 548721863 838863986 191411175 780405028 798424739 115457055 510028009 196849341 662458289 584385244 541200801 108085484 587410607 382032750 792409893 934731359 974924687 384523542 86269131 322812398 857946485 723468487 625874727 59415563 295883655 810406838 593167270 937323279 49033606 203046985 40961796 10887629 60854566 697690622 189083547 652613809 464582869 366744041 882307382 744526184 184958080 410792399 796289997 345929124 73097095 680148673 764398400 779486355 933233731 855718176 99356854 79872674 662025200 569808995 379583011 89629560 585073574 380289693 521844086 390806689 404329578 716792271 588358449 263877051 930843937 902325514 683358996 985908154 937031267 484242777 284954665 125295250 30369519 452595874 402920578 393587312 312972492 76027844 441476596 724597822 103963600 899298465 387457448 366872138 127021290 504964132 820542804 817567976 863518314 851921893 282595606 959664978 645243009 582959004 715766060 589101982 582204640 974966901 579424248 110777295 718180887 482159848 126495831 697853684 971691495 652100463 65210974 456620921 566789369 215270662 673666936 587372035 839367682 769154838 836019859 403930251 362828151 401515073 789366686 703389669 401358458 889240883 821446762 760835637 486320025 876609860 106775158 377217230 894454722 556140570 917645121 91206487 729917025 841610312 456024554 697592491 657577640 488186307 620942836 495859065 122951723 649279202 23942128 695764046 424829860 267415312 452653245 273501560 512227111 225140396 453821057 234369867 880411930 22858744 407811584 756589063 874753039 540583764 378514734 918875597 470275613 733929008 626866304 577506574 585066947 765042658 628581338 626967415 778749816 828423243 52248860 702346186 892754708 367366055 699537106 31805966 475647856 795144012 871498206 314254358 144021923 862238833 654239573 278235273 787918501 845465326 308304774 356917657 682933626 541275278 136519365 872809269 871150924 231313785 612731690 638908849 333767101 37782118 941423079 675891260 910897555 775808703 933936903 41275013 988785141 146894047 729554873 862186619 232261139 263437862 155846437 66014248 390972983 545606213 629804667 185154665 933737208 859956794 403972127 521186575 269446445 234866100 19969516 27687906 64976487 142183354 647410553 695065170 769942269 323084470 182388828 606872109 694565346 572169406 916073870 238762569 153496833 284366552 216713839 129041328 853850886 921853017 862545969 924479594 635286215 157559881 244551288 234025147 911413647 591291105 363623016 973205415 944975308 955818567 383220329 100198751 987379242 104809408 474840477 780451006 633187705 253215911 690621113 532994705 879794244 436166106 968012107 47507908 171035041 111642698 803306814 729921388 670935196 136865815 417952466 301540018 74227696 457486633 373450881 252540656 992557443 878547504 986659971 224674679 577786372 619157190 899659726 573156882 324793802 171428019 591120024 360011427 477685797 20205652 64386629 452578309 805986732 190308560 804805981 82542114 539639985 978801162 815960981 515526933 692678103 770815618 254703541 565193976 182374657 939731274 986086907 447035481 835362728 440179599 994847585 601921435 165351151 27900521 332595548 218145586 381703713 566826864 756266143 210920301 418403653 482876298 608297983 80616396 88737795 721905042 745602113 405330440 128336703 112159920 868332991 822495270 276199068 69477393 136196541 871063449 358116658 733792956 694297874 225109023 329122603 83946801 123439152 344139798 329218558 354497597 345790760 938327537 229964589 318828065 102957762 48927963 397586687 392093060 583155804 278097598 546983604 969401675 255782437 282080229 723258534 374289114 373610112 819017890 540112585 159917519 603997382 811480635 336354994 459778496 498835058 768546426 663081326 414467657 56310951 641069042 893577690 143972603 68081289 572099502 998806526 196585357 463542938 253322614 381294597 961827417 612970719 919997459 509383917 240466119 42079286 555099132 442993157 96026024 252226655 660321455 192030949 687730288 243311120 87116625 745454904 152758371 478494450 158295370 517860337 327032774 979527535 435754626 474674060 517196094 819685514 855133876 328368305 770261262 694638539 337783001 23410616 668881116 783658797 275142316 908922332 534586281 23797405 176971730 768451746 665394235 564071809 104233938 804537800 616262700 212608102 895678714 34020998 362233699 322763397 17608467 498761420 564376716 242970849 674505690 345279935 21173056 458944856 555270127 615271018 538439853 429952546 460081006 390530912 764400304 51129561 829021960 881958828 102545230 703919263 244932613 328138892 671478684 931861257 90824069 864049863 173615337 657582714 79709379 788902155 474773593 146010043 443743349 829498217 731388185 852081202 662232744 297714140 887330942 277765288 187795719 70926806 865704283 834592078 197120353 909805690 886230576 259166924 205533990 150581445 474493810 87443991 581113500 884306273 611258867 496351151 202055744 774238952 515639066 652080229 989547742 215279960 327348755 883033027 567201754 60105258 201109728 286797898 506154268 854728034 759469152 570885927 400225748 870652259 479263392 167738671 351449093 720857644 466874540 817357925 359947376 682044806 154817488 240513048 549658719 886858932 15932886 789815386 442884912 526326090 132519485 313105111 9186754 460840962 979407207 933337067 485279451 352666650 509989453 196655431 787226279 617652573 609432805 849641132 144919337 579621197 588516554 722426918 757641454 542914625 949351534 164666556 444460989 992064376 209391414 798582237 357734230 382538858 506368809 350014278 976660090 267275085 487666220 321051199 883165266 866630341 401992420 287949174 393142338 99437925 937659609 372975871 478552190 844556336 768078526 286762086 541827292 468675824 116319067 452268442 779004931 47029739 177511615 894946060 609955775 701267194 365523837 647413303 991679890 267278611 525892711 823197978 350410227 603949806 543214344 255168753 865417221 547808452 204314705 666470970 1788761 180355982 512651514 191763687 120890358 550363663 497191500 296679177 630530679 50891988 274287955 2492849 694598008 219916381 394561901 935217410 405495694 390154508 753978596 60576832 141195493 378518855 134189087 524048464 585307058 563607013 667865302 845772292 625723845 175971769 592345737 775749649 985534092 46110517 773227923 204881751 35212713 132015015 506688621 507275653 217430655 161510756 126675302 618890802 364801237 44918909 331057397 957199005 29982801 822969466 621677013 822074649 983284783 373035867 24272324 923354637 708072514 59760583 635493402 423227713 177222302 425295153 243595853 245226416 863725764 966743899 86960710 213913460 940374052 184847227 835818671 514340410 145605202 16226009 419926469 84904626 244430709 492421343 265005855 35130100 941335817 317200955 461186493 894600250 960363844 211195375 926007313 320499714 868392198 357724736 498645500 305655364 867646541 996441457 449041171 499805104 458061367 293799882 42207704 674757776 7369897 447976548 170144978 71983085 23266727 101314272 899246512 174332292 660343156 186502305 901900201 335653140 454516170 398751780 952579592 513812473 294602206 613523595 884666261 697321261 495191971 703641715 2082941 23886708 944156251 122099353 106273861 989806362 12923204 347835395 549917591 608176115 544360881 972299109 717648934 841452602 183709444 89697819 612073598 523617515 178813324 507200464 847499229 286857771 812569251 286784016 84262284 457202118 268224793 568816593 8175619 55725371 789350257 179106904 820540055 133269257 703780579 985151212 236041779 596911470 511092281 531197847 547826808 808375977 874354278 39978992 740754145 505691242 114576147 416867888 978807515 164401077 696857609 55769851 370713756 871895029 994073877 810375949 740292563 531004797 36661154 600900301 434589881 322176072 850896643 646642616 65141715 277176635 204149761 704438504 788301022 566438951 665730224 933545709 960960154 425708196 676355795 826761615 140264879 907179063 844421909 75675546 119317902 537079775 559587705 304429762 594308008 89187853 214625459 460216027 648030837 287819790 630294111 205026454 800449669 364207160 35114389 690738219 258053171 627960063 464510456 581588788 786391990 677561069 402736997 32102973 73833631 708466549 33347352 966914277 579715392 840581409 411627048 382093851 601943348 256945877 45843357 571981940 569156117 606946357 758933180 714788970 810366055 506918516 55131930 643834121 38501225 846050396 169380407 933680785 336608301 10747547 787248682 632226276 117593107 768913016 275713467 325693023 881148332 65977231 989409841 620530012 136550729 18368071 646128388 343097866 995386460 647035627 628569912 788768818 85371613 530153311 732962201 270919069 159165146 306767299 739393151 594300097 525341505 785297049 154306101 863524400 53708889 885729670 98542832 16157056 154807723 33862578 843494358 324958839 325750100 407391166 715535566 706493316 443713519 52056066 800613037 264226360 215587376 363802887 334505740 934430993 616686337 223221198 620145503 834641168 741480926 982693462 407121076 230862292 202979139 624062947 455952287 875252336 740186600 466660800 858570836 210259469 320305117 347700379 431696629 88014370 193454093 593527616 325251029 292901462 518600954 583712735 836987288 34808933 147207183 86305318 880271069 537537845 768908684 74666687 274172207 351944286 348573208 646352948 321013453 212608315 803505129 665449986 267440820 232201431 323195555 127238839 569102539 59097965 585125202 605785607 727019992 410252078 571180866 627708988 232302386 1846467 627554603 355489344 380707721 166333499 532007032 624520029 42303762 290789607 444935269 619585049 604830179 384883503 850272651 717190259 742262522 24030740 371884634 501342915 149443608 775160115 939198752 35174333 113355421 596969647 799521651 861425161 172499026 83220559 141874582 649154445 592271965 262437217 310640840 721954444 247545065 998810295 234709887 487354525 576473309 189574969 937287352 938050516 773669049 833651160 508028660 775693101 30605547 407169400 940304645 320788828 906109258 459621669 75401330 975961447 612571918 794408146 489222020 449242950 902614655 308901537 951120125 446861508 332177299 352016237 802176976 622736851 709763096 999379927 492601011 343261854 843541771 274074056 382573908 437108516 334207655 390884436 427819468 67192038 819598112 83366378 55008032 309240782 403832670 413765885 397653880 918068840 357427424 298434902 260940731 974038801 415749305 187025768 366991036 570582526 190886792 478829354 693811575 977517912 898038266 738356877 199748164 262923560 422222000 851709267 129134686 584328814 758734071 643442533 163485497 575018107 379968957 72408987 751383475 905523796 33860420 651380896 369187126 53176574 675460953 456691111 462352869 674633895 530488853 874452172 985039775 888751795 402401741 183346642 457701768 51898463 597899797 502717703 14721326 906042715 270945173 729410545 932476244 394099449 577552545 477763534 371707134 685957817 84654447 170561777 399646237 838119868 93827916 685387092 375182795 789020929 615701491 45907827 12053515 529668793 548683650 726930204 18552205 649728561 386181293 519826299 968242819 690622948 421136597 254266075 101963755 29633355 581889286 513841692 566075117 148250914 150632047 20101826 532925465 98922011 811559724 75458944 631929359 304696713 153618322 947536137 575582779 926594211 536152856 898088940 750581802 446701802 369649664 789064254 839916946 742608093 12768 718051819 184849773 319970842 178761346 351827741 304871292 160432966 964390167 428902184 702019709 674067021 405914939 294948818 365101048 766687815 139974381 677613736 909570513 922844450 484829488 184765075 14715891 679661666 567443575 498050040 411595398 476845110 687322124 963055535 33804165 637681657 850368957 88339177 896707977 575663189 96585829 320366692 687330197 984792189 868682724 284775530 396173987 512967859 512846031 116332889 362105313 472635411 684527249 825496683 669649052 872546340 422309451 925781737 956869315 450247820 160042377 180350900 260837918 970263829 520365380 890694981 577403366 655521452 794093697 537999457 355643150 165069917 8120601 75150193 363569250 643052614 953446639 700869625 783308437 496712576 589062873 324415644 103903443 661492374 133380509 74173989 467490633 301517930 156295119 884634851 888761359 743690253 710720513 193802634 773607653 644812924 559830234 662684715 526184818 604731538 262599355 769391808 475648287 10306577 849407742 86364023 454528544 450846776 575381834 320519556 883482222 509353324 911142530 130472776 130154516 744857807 568591491 190820547 290948238 336987786 157819927 230120028 531967965 332874761 939473598 97392496 600346269 732924021 244449220 26568270 849619 348594404 78054964 141130190 224828986 268085312 558606605 46319508 611807291 692371893 100897938 385301273 119001881 373980016 635570783 626509239 140857976 542384941 670329308 697073808 663931871 181054092 500043911 380386392 957160804 490141934 893288297 143854959 346472003 852610131 693793872 971573454 955738779 844036446 401706416 673394049 64867981 165579813 79645336 904581511 731295847 594330517 824318989 267473398 751837781 693617262 111550311 325679696 104135197 125348398 232476741 438082347 497036277 354494851 654291360 950362297 967770001 28024879 664791588 76004562 406629314 374221477 148947711 596324070 9185365 722656952 187543721 8021924 530382181 304916399 770442850 192765380 672633906 299288386 112156556 83962323 956493751 420161664 100046303 53808004 866326537 63716262 108930669 170713260 557785147 984686307 923641069 561784729 868314079 232281883 292877530 401184394 290382514 170221721 525159565 997168448 720425658 819864970 473100736 414121218 697860988 431354391 641797436 786096529 910064886 127252970 557013291 436665536 863499003 340338679 664792900 841154422 603313683 688151113 601561609 830869886 590994980 598149948 53083250 888297813 321372737 677555792 961229797 832908969 332660146 939324719 116804514 991181091 270419629 266540090 581198278 305217664 690908512 592332468 320968110 33126236 631904795 431216874 66423914 53680331 430456875 434861486 987081582 771813675 993667240 914778305 409557169 635727296 520650911 337299124 420420440 327950100 870614801 736830279 793404355 712593626 847626983 433200988 322344272 901169440 556370647 925523910 418027674 253979366 335871551 977957753 441446889 485277865 709660800 669305178 940273323 994210495 725660434 150147396 884945622 786510043 598707718 13610804 895343557 663804620 595987832 658850351 12301670 560934118 291214010 426931391 69702513 728964460 852933197 515974196 30995836 984492714 11470662 994122754 840207943 778550802 315415742 412851633 443935376 227565735 67794501 930555900 546768590 411928026 769458405 759731316 44802618 454039311 561419887 75956116 477227430 464557521 157284435 306250881 228790069 142399215 400401601 147029761 501317684 110616650 222381654 752588830 332093800 535885138 126055727 182598217 122187510 748691302 298480168 357857614 638885856 281575440 644350982 494326863 792713811 515082386 9821360 277512133 774816521 85243770 372332515 451824545 163376263 70088397 50572917 677554792 715632420 510831459 170796574 334076355 129138446 757082814 340632884 460225937 541338460 444752208 666401411 470094026 746184021 105540432 331239890 421323425 22466108 391681508 857419798 101484301 408003043 949190344 427174308 417639426 747123505 496662140 898914979 429007425 577913577 378941612 527717950 971184743 942146648 975981707 470982985 131475912 602098340 236368732 643697619 734672678 28699241 801350299 260380596 770242940 187880923 596228502 230123871 925493168 122299119 665648286 770093600 767698459 103398198 227810830 220215486 436170858 459307689 140314395 113268113 839158237 438661020 969748860 387322841 6432575 130694171 870253777 971347183 852216577 144004835 956785100 233808546 163265559 521733820 996059122 834773591 69414200 457680810 854592908 469136551 853792639 418333025 967975882 247926853 376634114 553409437 934360921 202031412 699735246 84173521 177075827 814049033 960570294 673916133 228643836 780973771 54281736 108559841 521972755 26727001 635914824 135142339 190807965 853460925 956234218 53243199 427534627 178880146 402035032 476590076 599105988 869401140 497170017 307070432 519095782 473545962 543856383 390600086 179254853 454974908 631893667 123690801 186283847 159671426 546173764 1033321 22794402 881645644 200920457 714246212 224682600 603949179 262392323 761955442 755275729 561657155 525201610 704382028 554383117 625844746 953287029 28875567 556240474 476635078 288514897 354064894 553545814 514093232 706737596 523935418 212222640 406426794 474484902 422194510 65906946 308444636 679492006 31716594 645994506 25953712 792308853 79806975 569774638 801797186 171468878 967935511 108695843 412271187 855457746 489159862 692943392 96098647 810119598 614232757 830171701 991204564 94251512 900689166 447418676 722647936 666270573 812900828 626215074 432373249 182440302 13040837 208464859 964771501 967884452 918010359 659284696 406777684 168296742 75733950 817478803 282214487 378713266 148364721 824658676 598027034 411697523 430949827 22349142 452036118 340328881 356639844 369288505 7323265 295237324 148800778 245938226 314483602 319626292 32678864 342286577 818510156 689319667 139419701 723163591 49740368 980683347 154410042 59585634 786047259 631005357 114141560 752926209 307735747 291774425 517318021 31213106 399093717 626060437 892514184 922289022 985284619 942360400 996886117 723217719 276883092 21559946 231634717 675513821 554800127 951706165 336535760 351268114 958228256 76413464 121147300 618615123 737229121 926728156 275334860 864871812 376601181 138495337 231790599 869312833 490914650 963744947 870744904 490518679 665782355 575415511 566824948 268431789 285298599 526725468 820493051 689767008 197265440 606173940 5832467 344056961 41800300 545266009 271759007 100512542 229905915 546162020 480116048 376037714 790781579 997508727 591306294 185703281 877365371 513469522 872500364 355821735 838574714 797851240 997459197 586005641 633649453 933920756 122328589 698843177 524835930 359496877 731805391 373300796 898804107 865709977 536358631 759610217 568031009 901247307 557770432 62289040 540009281 908264651 200290839 343380987 962223622 167679941 886023921 28860414 420020568 164631706 964406399 814168276 386835472 216073279 457845816 77241145 616588243 959775159 445372035 691224706 232515711 710932418 250854808 405096538 75912413 75201215 977100206 728596072 334408714 733231250 777556826 778096617 836260724 632298175 637442927 274739906 113516461 66345409 707463378 201337044 561966375 559779720 905929160 523838625 506688322 359766441 777855901 160393684 508368611 292003177 260500469 893614051 678214602 695693780 43388197 316653000 52830036 255922294 550673609 99810762 632683737 569031573 509266093 222808712 692394233 709112106 423594538 393286611 459077357 65256885 407854809 541978485 511482964 891131882 601483820 106297373 117100122 823426349 370277846 693949314 605954309 892865510 158902441 393091391 51057111 983481461 977837255 215755274 694121720 101243380 815891524 947468933 643159270 180797522 574039018 246569573 451037020 107101006 365992871 562814142 119670448 555883364 47346492 462890177 950331601 739836751 961340682 103597223 276612270 601629299 332085316 199756372 205033696 488880724 177004788 333970126 52919219 383155304 453790854 776473737 612168569 968729765 953435721 675806053 571392518 483828319 891669691 549209469 97827904 968181939 425675842 318835113 314806628 613891917 66858831 163637489 147109948 587448152 29823403 712034543 576014636 971802180 467513668 564801348 546975011 26375176 504626394 175568673 104781240 839902472 936789063 670931596 399718959 438931507 87060640 203775865 582688182 412599551 691476848 925660966 614548158 4947919 580608549 219461593 172824257 526661360 945415831 581852822 939855241 253656110 423009140 62932895 591435073 329847594 925144735 41789106 559279390 255416557 245048542 757334191 952627288 791229547 315198929 450219928 476191253 955756628 160366428 246324100 415953547 532751007 867416937 355057304 136258117 479125811 603270250 933415227 270613275 282679654 587554373 728596439 958283557 634094331 620556332 505174251 697558895 887777764 750205435 199719027 285075668 585514823 509948089 79767873 229972799 575393051 723691391 293406001 855484124 708636116 58786995 200350666 106777755 27732491 925068935 251641946 949543107 926439963 294066950 368556934 992626937 136539752 477166086 889289485 555580383 397740184 856830441 337802667 691010727 506753260 932596114 800775657 915368392 706145698 546623549 309218477 696770000 663407214 600874438 847023059 111760433 169483578 663730748 835123954 520319442 936019997 611101037 591579586 886257727 275182120 530791982 650477520 875967170 831543991 406226832 44419506 228788099 486448505 707834617 387294687 465057074 187735538 19287240 580661750 410803763 135725418 362402769 167808795 613990612 392829594 454766938 876765630 696412450 166205044 431600461 985360866 967722903 112417197 154136285 459976476 133932386 833016255 257033849 506513071 212772266 751222116 453040160 317078712 180386227 77452194 260754898 576959738 785075902 757226066 942238552 370853237 684831264 801924132 617904948 809917145 932157474 498753534 120404652 809869829 699819221 334557388 599291549 804782665 29052557 548359670 215990608 173646889 243390076 450230182 546113154 623249505 585962051 346220889 887637170 183006921 398967516 293355584 574362267 910785746 961741291 178183212 702436272 174202004 326029276 514672218 6785063 282899154 923090353 201004791 916909179 484497245 839457050 801365175 448756208 147256044 194552799 637105539 59192073 316566290 531901096 947757274 759988192 412957047 750536816 967689139 750123089 678679746 786804178 513906245 293376657 624865157 605311848 102768594 452234563 496082840 280240427 362212677 361407503 541156207 136575305 243867237 168186248 182465955 796341072 637615714 268789075 452416317 898069684 548992876 325176598 424235380 13973145 396075766 584273216 763133701 9725567 226265884 394206943 597460063 559967344 744085649 678333858 79261 894342238 785655112 385816881 823231095 131657074 238361382 377460320 716522323 760557837 720547328 443585843 617273620 388364790 582749107 369131273 289932745 538043535 850852387 65440240 598555207 130847030 798753991 185058399 592516250 684088606 950654035 856156782 266757911 758830836 340601809 867928841 206817046 751456370 44083182 201340867 988217342 611927138 686394384 997243930 1773315 194917710 142806807 316863668 602342466 780572701 524855921 522154866 156378229 661039145 131925376 814634055 3732344 282425941 253444042 133246291 439876920 51772028 304519264 942413764 711865983 218622390 763668414 763781736 26000519 277799336 877663495 471419883 495516834 272935735 840155479 846124643 659191945 104400922 282256581 644452592 247388668 441856943 965938345 167389791 369833440 382429464 323518290 528254028 908018700 542024619 374001658 545221661 10427688 946679518 938752423 421469312 118449242 286893053 510894972 350592760 466085924 407701576 350734107 406429877 894059565 274904165 120765685 931963147 669113925 248092700 717926171 58680154 49873301 430828261 264873909 765785744 551165044 179656998 187366607 223574995 261129470 240171430 206243378 594284359 482960766 292046145 400497947 282864294 702306577 500160274 359509068 819095993 41164095 546420065 931044189 473382302 467420251 56046343 210268009 442398054 989401754 658001742 223415449 223827721 255947514 309828705 682436551 739669057 727713480 4891512 500959383 231002936 590997487 18575513 295393345 512407590 939933375 553919998 333559381 88953481 172459588 579081124 611791645 312094814 532147864 609780519 360309191 467442212 835010214 534240413 692819726 766092212 878652483 620588013 633576283 229890208 275840038 785717528 564212767 874751410 383056491 548389495 922406144 478073289 171820581 521705961 967060276 938157819 48778606 882190052 778613056 753984477 365994237 981564682 237774939 240244410 931512159 890555319 935918652 488424495 601297979 283257975 992188008 386705117 699356239 144768028 457813191 194080603 840393509 920223840 441432676 326424055 583383329 144095016 785395769 520162727 42998057 420714761 961157948 498016733 884834547 844459216 563212541 876331450 394131038 85832733 552003341 539581889 908566204 66189842 879459507 203910762 941707341 45553783 47823916 650072998 157664275 982329721 917309573 93586189 200019666 102386990 18613547 393321735 532014542 646546971 419439116 865794838 276274055 52329155 219474010 856838414 403535708 238611849 866415901 741435898 430178529 299247358 843030535 353715445 49554947 491263275 212127551 584759951 16841722 514352009 596053065 736483799 140192116 931000496 816902671 688461821 791859224 130603155 780021337 703901667 259127656 339843521 623022758 628482729 179466100 10476614 999037619 676991260 743145527 973008377 750909013 601188124 584783483 67406901 78479754 929187807 515093589 991571560 252063706 558420084 205779940 79586965 320078071 223103204 908723345 44207783 464828949 46609922 318546568 640060232 917971039 237417232 670564146 873889016 560216557 971669507 139588039 684821639 925362306 436992704 647513892 119336447 140661484 713193123 198889858 104453021 745310314 307874162 191682029 366078338 23321385 721030404 396267758 839095185 215606666 423987672 839994742 810476405 349230399 881676978 202219674 610041530 133761316 883043943 179232932 358778945 653280940 503037186 827819066 124465296 658694741 692707461 963498259 125551160 677932692 881682340 108881549 121259129 569156209 59536127 93845974 351823102 380924784 7063290 277695658 681845513 964657366 159609358 951806344 208008703 355305834 435423458 901789214 950484388 197228696 972593863 447666303 929114173 373011686 318174270 834240569 365313708 700999831 220005166 992804065 355817714 235034368 851648879 910651187 489528707 350211592 337568136 686323802 621813501 825458493 240216829 726207969 370517637 403491369 574437963 717287477 367674501 503839013 687528368 557693992 5391080 97842264 736307484 938660408 654889042 152475250 372013302 760727748 855601246 611885344 990119698 597509466 827055704 583655722 345272627 845130273 898547313 45498416 174729270 230724842 890942583 991146280 111947687 612974779 739745880 783828556 811843690 396788506 557377899 195930430 106792868 573777421 147835730 47590648 445982369 850368326 943671343 964447264 75674659 856324188 539264118 156141539 139624014 248822634 465555603 476577677 672463026 134420523 331287307 156397132 468581919 815525628 423161228 272817740 953328907 336809081 833812864 925374056 897438735 787466089 86212400 253750058 571748557 23084507 313756776 656026015 528822248 862413711 903706318 138224478 403190219 499598661 952563684 459154824 859182333 506554789 276754 122123988 951151506 356136930 257553078 87635779 623198239 319376316 606621961 814332238 474107990 278260548 116056719 364991848 640465746 676514452 413008066 665403315 629264872 343804735 648091078 46234254 775626723 377404822 449473309 767068841 896450802 145391629 318406084 417843427