2086 354936391 272736372 66842172 45478928 962898882 572305956 802667390 699843855 858749377 137422399 562630437 283232828 437184640 635226402 680048393 904461276 66466690 83977601 974385909 912948029 92706638 508383109 286783539 298293763 579855717 431724121 966638288 185729335 313212265 481670909 544611637 674723462 463628963 703640693 470049825 723923191 195808944 359984321 603954704 711384307 74407819 282682215 612042058 273561470 831231622 256398545 948759577 781916661 301601394 561708310 3777695 786389611 784976317 746111442 429835305 432973832 140180923 223206359 112415898 15232502 274264768 221193368 353328593 763980779 267249582 441208294 433043711 62633143 382052218 210742319 75730177 821037776 853924846 774306883 816945593 398437020 446413991 773331673 214030704 553582335 352871815 573729785 233949322 123402944 518189479 868786753 702622318 999069222 833968882 489793421 811302189 334436689 986555169 232865122 217269417 767477544 360821867 333806391 485637789 440478272 313014321 733919655 746200789 155604199 606594476 665823895 385334915 816498741 305902241 234565648 717195163 13424617 386043566 93180798 166844472 199641488 399880053 859585391 641976338 925000825 751393729 670943841 880689156 141004807 805960507 10173633 5641929 505846607 380674634 84906399 307222543 546152514 275228101 850692522 791169774 132137003 122148976 449669267 55069504 867872819 932033723 922811673 801665592 222613267 242311767 848891393 54219871 260930541 959082677 432051905 76352432 401157893 364335249 886262587 225224707 851001559 837392078 827790316 523631752 485338578 251515107 546515940 937470788 590220725 2799824 609860368 472327367 709711536 447034189 457052780 631895213 479896536 688523520 966865228 651522787 973812991 58618736 429425282 976577086 589128517 113694786 231196490 471853702 703966510 267624711 55106367 97762796 943600493 532303026 505901835 157083043 595549744 446094420 196019671 992217215 613771429 991815450 823782057 178735198 864691347 545181902 938100586 774527447 662339817 249204530 845169459 437317825 109926206 180453255 816558017 556718622 126960189 543622431 381249437 650565925 698265319 414885506 237095495 660872515 794489847 570517705 731563275 33534690 995341038 370144993 171966078 430299114 234120395 867880054 300138377 882090979 922671705 100966301 382667510 31094471 522314660 355512521 84329404 411827854 109870032 548536451 487586377 183628389 244245477 80152955 509373184 625849005 862085193 663132375 942988081 296278188 373989273 65368972 658909250 354246637 281135498 983616037 106352602 328092277 477564079 276628459 37557999 327661021 917460393 264871898 741258234 527478573 830928708 437687250 497555876 271310545 334070864 914498263 569922335 759891845 611938751 451413604 282887442 602266157 522089245 546103374 496738241 612197728 203811966 827634337 84717475 789566071 199305985 662201295 726572116 679174073 909289217 801014989 723472054 464441724 587451800 332565734 574106089 305663697 616818954 388810868 246825782 382819133 650833686 273136846 208615616 915849365 796490236 532685264 957942414 666455194 44666471 227702380 929866580 712426886 949415625 275179939 592322865 444979947 80292891 960880330 32142801 488128643 946253880 844267468 245115594 938702886 74065899 42485868 688797161 609303548 61337564 412408690 117922651 458009021 887733254 909812841 757668030 174471576 585415091 731793875 825931356 768774572 638489437 269753660 977667416 76476999 418850330 21521303 517527001 568810214 919879843 696927158 121889086 695256033 239001476 213333167 274328324 985216339 770657757 4058347 323321452 746518121 456185342 198240306 210290710 553044515 57171705 791128723 885943102 731372097 441809980 672386272 411259409 593685209 721030358 63082479 31062813 942522933 499480688 847905753 716351321 339042722 442095935 959979001 282550614 522070766 993722018 906609418 850317089 857637048 482260134 19269852 563128835 378660876 921702479 567414838 634259904 618061575 572611359 340548955 656052475 494861130 25137706 960925073 381421678 634048756 899618005 376706030 418019672 219396215 467365575 609797022 872102634 994418794 171714769 640749767 418935006 109758084 66216780 643546288 602969911 215256977 422685479 158405737 244191193 297987392 563115353 467337298 816424360 472974977 762610933 158928919 173519459 496065417 181333530 687327845 20512598 563201907 712758578 521596721 839050665 214240051 810283461 712080423 299792051 582812726 946430112 540128149 674303552 34072716 900253166 856479953 764370980 189421429 391644237 751625545 865446839 823106705 333929579 832278002 298982228 61712172 221065220 278920610 662060983 412476665 884144203 944630646 892457815 436714424 350839348 565969699 420056759 857175334 712855712 43414186 846162817 734841841 836958897 828982706 121262459 936737005 153939233 580051592 963759544 963433989 386124893 1328796 349405328 763196549 611384025 797270278 185850433 915863942 483413022 557596354 786678119 345378604 477086301 506645734 8777913 864406168 550650447 945685117 968243475 211257888 740135143 671119947 893139219 865183770 941220920 488048863 795321770 29427206 384324349 263126847 319088930 536474599 577156143 2135230 945234809 288037467 103894433 955174215 860644807 39749405 226472008 120902831 94476571 351310691 392134597 710330071 132648200 122065094 324034270 88893114 528128828 84601948 82440728 216581739 66750928 615521959 621701978 661726272 278570571 886903523 523962815 821972271 106305904 960800373 680687206 840731109 94730929 941336701 107640465 448844396 828738270 615717148 128940602 266268801 869102584 505351430 182182440 190367670 186100250 741429428 706111805 598343711 181283034 85807181 308461979 86265864 404253828 752186386 143348017 910134682 943722172 972418460 915286331 238860223 380339438 652499533 515372388 820492224 740137943 499392265 176163432 633138167 662120694 214522516 720555635 670650376 134889899 407120665 521315399 954679153 1486371 691634449 526281572 574042289 561281607 86439866 462545012 481902465 310323653 189677047 560371479 142000063 972562575 972465227 81653027 81509052 148375874 949118156 70950161 843703492 453793537 384071633 394322211 115519678 519590006 245268461 930230054 627796047 563242234 938075589 20724320 830515311 436473364 94215588 226245261 267984101 431188020 575098810 310264057 728809530 719073970 99267983 758473869 100973033 643635493 802811206 510882715 808968873 269778878 268732581 874840365 135925972 997896201 757630201 949285106 735576810 867075151 441814726 445794604 547986163 689074542 224510846 273759918 824960646 832130568 127316861 599753112 716623052 388557593 845237513 388902094 180330730 577782936 475454123 727691375 155544875 615103252 879129197 872781852 66814523 248355550 831428446 172933266 519309391 349223721 121065355 701547054 930178795 449248287 770073345 654376746 739649782 723122770 746326565 688374157 164236840 646118402 835322435 116769819 356603751 281173961 806438263 624481250 683731713 735572802 605699813 628936509 316845410 632152403 209268142 615334970 164558066 732763248 724233831 818273916 281537906 613173844 239677869 318187356 434934475 23570078 288092941 33627120 78215025 717486755 981401995 693945262 460027481 302582589 617605279 706797619 828740572 60156490 826341323 712330986 7347696 151340796 332854810 496074001 772780600 24996133 286864851 326371649 881346807 601514270 76414594 794343919 610062411 254942492 741876187 634711030 226242597 649512659 251204546 906788894 263765176 553518807 141149805 114017112 511600153 129338333 490977784 623557707 793485932 783745789 128168767 413245970 609491900 186082907 785541952 963581297 255328263 485245567 430599970 504636816 894801019 197730691 260287609 351878091 23697356 220818683 729521863 528659915 680257236 849134624 308634975 21597302 710271971 714473444 747750275 59525582 212258553 254796577 631443752 486646001 525158454 591099472 406978637 401122864 389570727 37517969 167351787 980949787 814800358 590559051 756465585 963091993 585318443 104633938 684848423 716148636 132451828 47028585 996569350 587180538 869584535 334664697 45474351 689058953 730995560 527582983 316888932 377443343 423781430 627928721 209548626 51662233 889204580 817701502 158129930 806138290 917580086 220746343 318535132 305405798 470713478 388133997 425176288 277290703 257904511 906491995 719775544 410912017 988178934 849240712 741952881 776036042 737772726 497169213 535844194 323702786 161015171 149920733 861844576 700674981 400922724 723695550 871131688 803899830 214110520 709397912 733857976 333422399 393380987 598949236 909843553 466529895 837997695 245319601 620974109 227200014 495067974 640650486 687253894 588601982 205014537 571953850 245374834 477977360 335952115 339525207 20109580 979431723 745324116 115182024 787518806 144644394 713143522 174564326 338425526 587076683 718105885 272969108 122695914 830539432 569578205 452454478 282210970 93817242 330148090 602125848 805568449 906210274 541878446 126651544 445740775 469795581 333244621 133818855 506076353 244273272 176444444 556158704 691097901 757689179 185932117 703275202 965191570 233472383 897186372 37043895 563662616 197709018 882597215 615915003 579143526 214985710 184556777 843793054 880667138 878963991 152522181 300527196 720922731 237571866 571607664 472183078 632160949 8024048 787478058 554404566 753898545 913434259 325888606 474661319 650153951 435953737 681139159 837790708 926707255 851979627 676650827 340435193 434220325 959569477 576091398 136940302 175237827 139374514 521185728 607136304 695277471 353437475 569933224 478195901 496969617 201309175 262203297 929122220 120126278 490088188 117029259 241278548 729503734 400402757 493176484 945141098 272765555 342860569 364387547 711353070 224362530 266053138 696264234 926393144 821643029 81578270 519186476 487507374 76710897 411117226 476989844 18972784 951532403 180262187 776759028 981807523 690170992 706359885 246053536 793555718 809241325 829581756 863379826 253790387 486897862 735252794 457403506 406562786 346963022 45178117 54302049 696576240 288444205 294777327 662671273 472036655 421703169 648872204 943924728 788057462 284350438 445658610 198980693 901226158 692302464 831128897 974900268 185139560 431589676 594155507 224290778 280335702 208685238 69571170 837403254 922816880 522950237 991640871 951332738 663443406 174416533 26751705 195734554 724491563 807229792 222460255 495322370 415042907 243427617 505616526 562824100 634900435 365512782 628449145 200893817 341076139 314999000 616708659 649597887 813293270 831831894 546374934 753812479 84131401 464879819 334551099 335319443 431260680 704722151 453354705 931226282 730509664 40835770 31610638 13743923 14919311 576350758 950992145 359992484 787948948 347503907 852441794 983468847 290039879 812637410 952012831 614336271 797034188 149811624 342377859 799282758 837794693 823043945 356313748 976740837 500430157 765641571 48477948 997635544 389547671 635239316 267945121 714486112 744876663 364048953 391431900 435927971 186572436 776284564 741519487 12246724 960048599 258330646 913232772 275715029 540055103 769001427 823245278 916244369 11269297 172063883 684890454 112057382 415756747 387158935 215950753 756443184 768039218 77561982 376086431 83609454 137747856 667925126 282895854 128331463 454458032 382804983 832643752 420958814 347927646 357585854 92552578 219062431 490187770 121962515 405430304 914304659 293176337 172909492 141154165 506757341 32980989 217178258 246551856 685584506 374393552 122025123 856192121 3530250 283445581 325614378 315484019 233418247 477713871 693701136 554159656 645109157 643317487 560659355 622271218 220446615 241974247 362827375 575811737 699774954 805804974 584887650 563567390 437770467 797076223 898846603 350439775 211912153 971169043 896991587 659003936 600239975 179380964 471455375 375650475 22816627 961569693 571615341 774184995 291028791 506153054 780212337 986109570 187135732 843000866 117974036 92187408 534913239 921018361 674050670 234674821 392565388 876905354 615722764 17153668 534801299 798492423 667190961 110938751 396647474 115777183 700153440 292116564 918068531 835945273 886259566 387785944 86799540 371774218 357710100 795853951 83892805 880760100 588456996 462159753 998372848 438157798 781557065 351741370 416050849 525121776 961717427 741348345 27654284 935710928 744804696 451984612 41534795 28121810 173828180 299455965 753738274 167985865 420504758 360407328 240840805 313115214 416984962 925247460 573243546 211263242 100761563 653605019 564075935 754032409 123521801 130573297 905099116 836578083 168303941 260619824 385205254 789902838 189969090 408096898 666170531 516664487 47607058 275848900 996478734 236511630 318532143 275596331 821376501 879882643 983005432 393176517 906960035 282442789 337109602 974206420 416370211 598009544 831024552 29153190 723935618 429292332 289359398 710365353 502068445 8960723 567972418 987016531 886256643 810801291 992628603 372366294 969218364 50186065 135576587 778209901 311694510 189923368 387283540 578324555 268335709 440845693 348097171 20529144 444713717 134194769 821413517 794149649 539124887 391776826 409978779 971882061 225876597 354830416 18821802 446030881 100548895 599035526 223764624 240227557 867905364 311427674 246867828 555572615 625847842 500390703 373551484 228542445 619592708 210660304 909456796 258261310 219927383 666365053 169488719 176690153 580211589 857382007 405813294 516733712 151625213 340431810 420371586 655371585 520960553 804906965 120998518 717052753 56603253 916046609 693313993 39489947 840678605 282560058 73833718 498283159 62248985 65527598 988587055 259590524 953665272 436521569 614739069 461172047 674267100 370629921 417730452 164206377 634010485 755531569 861189538 889060311 703570304 38087069 531605404 437616611 842665783 4931336 273504821 974510823 474255673 624228563 173962966 20767146 811659526 718277160 618405337 388245920 996780730 689846547 810973588 965529056 438950561 898034441 820905901 646524610 716291086 774224259 733409757 700399470 338739437 642247212 149089925 186138463 37098758 21370052 304914681 609798023 503321016 97755019 980905565 54859718 4483475 695715341 635356792 427597412 63217187 105430762 423393549 322898887 781547847 322089841 689298941 122631749 576607133 702369796 179777383 409822014 60310039 356299882 799445251 389797991 77505989 94232880 860073229 601140477 817410230 103148530 553458715 778082606 66546301 817998628 480044762 246323025 807975158 856981543 760356350 755244902 20382558 575017755 349267956 656451809 91160010 10573956 454155312 22997034 879683175 834978090 787305805 593626055 363190205 187395943 130899383 525280741 480242095 663888244 907735733 43698376 61316437 775193069 245923338 740061938 790308277 737089098 468183910 239215294 232175512 468497592 184346018 506190946 527669540 367793196 320472890 193447737 793759809 714145158 296267531 811739573 421471279 990188251 116885258 401421789 494955521 231460222 661512512 908640921 622411984 590300708 795729465 333336462 109851217 208523818 136905862 545261341 146937775 659173034 398189436 823042675 558839318 516128470 348942787 801989883 623488661 267801192 757898367 473774535 312479412 15248562 810338346 952190088 270716949 146988011 293511059 248914737 669714911 336215326 378149717 532654167 563816978 342840453 915114929 173797639 118456749 109262262 385943173 785293924 175385097 52510329 722975643 965973393 354213250 855864048 270324503 449349658 408569163 998253330 471052366 157350612 291223842 217729992 585883223 152051513 699905203 177439347 293931277 437431441 560132476 94756982 974970940 672533572 530004648 211702585 810715992 113905097 991603136 64551406 736528493 880022264 14470863 214904539 878729877 129322293 215470455 186096075 101648623 726394188 919478465 226195115 131487472 167645512 923846524 666533040 693354389 675532791 373700479 214019472 390715585 53140200 606424814 953077488 734670717 435070950 196293687 583348919 561519817 395052146 666359379 377035503 722332048 382898134 984437725 873920992 736541950 445850991 724790510 807422741 608592875 256907036 52204938 24338950 324208270 292455405 166722922 257988503 905529209 158521738 358319030 685086481 897959784 915509684 259112757 898821947 205176306 349736918 489413200 703597021 265781059 941444882 557418264 289093586 4243404 676488235 100104560 396886429 651260297 529702703 258695077 428870627 827529145 307502988 334069291 125215282 227003921 548500997 737490192 762824043 201031156 637887445 751157269 885098573 255311558 155120669 768270001 882256078 373006660 173130832 583370361 221733296 882092575 595805154 338476824 232690969 522213205 819211272 958081344 103945368 921327357 302930272 722834159 710128834 554080225 714006007 524339124 145232852 254380930 799116388 164016011 672265715 154645627 948263852 373439523 101136969 890633040 108492456 108541808 834639001 191328839 82205751 399366450 415447601 154783007 398863732 261788629 84018726 439437881 128107791 408547651 794842910 951687142 59272869 768012514 279787388 269640100 789156886 409894368 369289519 733689483 177895798 229663877 94776300 390599990 441228320 65966924 649213765 840331513 381361027 16304850 713243437 853926108 609576863 290254912 538584105 892596511 985250281 773183294 10702900 104616728 301891644 385344019 785750294 638194713 607914582 23463004 84105211 621485155 686729975 67574704 507054451 294705202 734296248 776891044 728543288 744823061 653226621 948631378 107114966 532918155 29641033 664594799 610629506 2659272 412832023 788949823 270809079 671532799 847410173 944559067 916376186 106631269 524080204 458030597 927258755 788456875 681148605 402429513 85462809 414398897 192464208 632293579 454065775 579913759 324630962 708483249 851415624 345341274 750199212 440557682 182084286 470990366 353039812 262632979 943791200 143886428 730951856 772284122 920414527 760169950 100554173 288971483 635173863 318567255 478898034 318254912 932430217 359248067 233784877 903495419 305675857 694685790 599637500 744966249 392289307 133116400 407630360 832181356 495845414 951568235 681236707 747999569 124129576 812184461 763951038 826409566 881442120 997209061 136617363 564233679 55874080 629237447 205789820 720413673 360411206 999766507 371735927 365762620 773447351 317966869 620983672 359910648 71593267 310050933 599801710 581837899 475529609 788431106 968920083 850494801 549839109 51888064 965965850 202119760 343629027 959986712 609986015 334784378 990566969 502504823 436538843 490342044 425676205 117917339 817580559 168408909 191455752 571055392 113522813 881646458 84634587 809505903 218989402 797784835 904686601 383351893 723852471 371672187 323178356 680520721 311289957 224437179 735903931 847494032 762130013 143439803 3564299 44614817 78329302 61616926 143440856 434211224 453441491 285174576 122231882 45170425 688705934 281440603 144609775 351913347 43559265 168566869 348903584 263024419 725752455 176718396 522140711 521587039 189365339 260812374 506259853 408030450 944298598 302477000 57636291 803535660 806564066 400189958 573760591 260365539 36136704 430828546 789606494 487070660 35154498 499864015 114839886 697019262 864777177 467820788 865632428 177557260 228921496 558296292 429489122 495609142 144273619 636959465 399823537 934186215 788299007 277868706 183673067 440453756 860948110 698910141 619202911 210745906 217588626 564094954 278813460 567761644 992113630 411436174 43261454 794033235 183229962 290494523 336626258 148923879 125613106 896372766 547327626 871456588 169996869 128715056 148295575 348709923 485793007 334711055 876590731 734114052 714723562 767029301 552992255 248213333 633007010 569555814 631580795 238698281 201191022 219720434 557924956 743472797 806392291 288903544 589627356 233182474 407604350 94844802 936871862 967126824 32955816 588130508 891827497 305762308 454197271 841504551 361499793 769826594 736506926 601024346 97911800 40131501 631865260 674510096 994905308 926941950 6806005 951853734 862574642 314042263 462654344 465240884 10798153 225125920 252528274 438897108 334927507 363664083 12854758 671979190 72428498 698790634 969693094 484322983 159297933 742473234 933879553 885284335 547585209 359948074 541335751 754169618 199868713 643592780 378734957 464458368 993677260 757287242 716568397 134787267 747304705 607091428 338374427 470398419 763390186 630952206 628343016 824291662 798722758 558220563 175167300 278854975 636966660 338464511 395993085 351242379 871536702 184673561 421560448 727703763 228391709 455172538 759981221 574131403 810756052 182060410 433048672 755777762 91747692 123489512 974207360 693559595 769724191 949505989 123217496 575335315 180626903 248531275 904651647 20375431 162844922 472808325 512439583 937232374 782512296 488787407 590009435 184798006 590924879 883363342 821740585 661292345 411902160 257318973 85679922 104012096 196653757 960546062 313007516 910291172 433046654 324293374 598065608 168110873 118019700 31951431 44561197 731640005 242885082 421863352 714592871 151918534 674532385 223136726 66585422 301793751 215984770 730139338 818003142 435172744 132956941 10887726 113302551 804961523 496935463 128948369 302531366 172776305 343016902 825075794 666961405 915798152 539347347 612714416 908719693 185822687 906526710 5933274 119086705 106043434 308563556 698450830 568130951 259660876 208623646 846011629 698022820 992499163 365591818 941253387 582992246 36021219 445068658 208974621 207834341 825937383 353448456 793117485 59006660 359801002 815577225 27753267 268531974 206444749 320872176 981898939 63099514 970997984 309455923 7018358 850266275 178578869 879519762 386284440 619850282 889398959 566640002 429254346 372599067 468427215 735873023 530385877 613684548 857630365 916715501 130240392 321657076 110600264 61745937 537567267 383379344 82682042 676541078 412237870 800829501 739469024 718880470 751422505 997442943 221375727 302637472 766793244 765968072 136208780 62918393 777482952 580388594 991647031 458965318 150194901 972654188 2474622 130980376 190790757 155252844 603298442 471959871 853992312 139341681 384789810 230797274 439857510 486869496 362516345 977816775 844663895 606247826 160183722 254911703 933611672 274196236 415777154 135471854 960357386 582703095 488861989 549698036 234723566 895688910 30408990 977687054 592806200 932664578 364811940 400506720 227506742 797409336 530250830 916419705 892932700 118232571 957053674 861525173 536139038 611623427 558407191 351375335 770502232 682798161 728909963 907594018 399710758 274514761 741132719 129553046 984925022 4578883 377330041 984594959 560170847 2475903 311912447 803419653 797943038 6933292 114570954 901805183 850331627 96047827 648106930 282323284 141437458 966878696 886695688 306281134 520582561 886284093 491362644 32403247 635464810 824571699 822339298 922555167 885920308 375568235 61617259 834393094 309730430 878762531 930920135 513746544 324463044 856460202 885704556 716043574 439679265 849187566 432378778 828106438 638075960 507476377 583777581 876945049 185636278 518450355 850994611 879749278 207290475 616449472 379856647 743386959 623179554 868135220 823924818 543386368 156601789 624183684 81075064 706852059 84076587 138470004 205283900 377230396 489714230 575194733 753304946 830049679 939452206 627541108 132624105 482268487 910915040 437898131 806222324 376948178 199854121 88981880 908878026 674244322 302640269 836311824 474986418 923713014 715857403 662664168 546525774 960588723 531736765 32394471 155486998 532629733 689978769 408912772 136423291 297023347 886743747 647729865 144793795 413756493 722841132 995775842 796105720 476927845 655195861 248612808 557991647 35711958 622996238 297762667 293489720 121300371 547450100 423038445 719855413 254960017 116489706 387361457 792086979 212096920 325656806 197504131 326919846 287990697 532821136 838767566 330928602 536035784 106748396 779573222 557436142 269075892 14551936 23576102 291022009 101048667 587636874 977401287 680211405 42680658 806720527 519513402 351924492 663959877 209640320 985514937 492992197 181307174 527870470 983696502 951487088 896165555 967570085 345014768 723836923 175998812 423166231 338898579 828715688 874994608 666206978 830904749 530653743 355176266 465970380 411371936 227692496 70314456 820814213 429145283 523623480 272002127 544032218 782623369 318624438 212054710 306187389 389267897 397450312 167785132 862115378 996411047 969146156 566010325 644030374 337357944 565420318 917468989 414684260 850855323 642239007 57781984 229578868 154326633 931192820 471749146 805119742 109233879 6509845 230016313 654264791 334270210 259971265 412959347 131818576 119639067 608840272 89347294 109546789 164957650 179466309 799588898 717138861 826921031 683519476 762191204 239759753 62034548 399318626 297612634 410403885 841241595 155802912 916596018 748019319 465885067 575760197 296623939 487583030 316985268 237847317 973882194 306570985 794178817 662683491 805679362 696783877 120163806 513675190 256989383 43840443 966491532 984639694 642866642 442048489 204181658 780660768 920478129 577645028 435154444 294844648 509016760 428662224 65667962 38877230 69791561 969077414 141569352 680520240 195804036 221400290 48695537 600455360 758029245 157059837 239993095 705369805 192893456 125727964 499116258 63796265 409188154 387151046 335013472 25554677 817392290 995965295 629984180 688548593 285512389 938005249 954081048 278030 787526473 227656529 915557838 369142794 944977240 698979289 282826513 113346313 682303685 659426440 912851755 628599054 104975046 742481510 922141318 79996435 384693116 152356418 4116607 42032886 997306562 234505022 670265591 867417890 853812736 223400511 890322090 912292839 950273245 467719285 446309923 568347500 918152705 119451617 943242050 788582830 792668190 987819056 923577383 304404505 623629628 132653177 812480170 5658334 821230003 835590305 156547207 167065055 676128637 213092023 195955471 102682530 566628410 8499266 831736830 121358651 803731905 893029021 137439192 191734159 154076277 27344164 359150187 778002368 526616042 864726907 742850480 837417799 493855457 658834866 176736941 913261908 236102707 403132691 304526454 657624946 168421973 562113519 114187411 618170584 962417167 394217825 957964818 377566641 560193291 521550442 724195281 642630366 919174329 956253960 172291030 175191754 848676495 691705140 684107921 64842556 869507564 41015347 897024649 182344649 965226223 215357997 56119450 303937862 279819962 143470525 356246214 253209647 783152227 54449226 508771758 538087992 964419769 869997170 412531758 346173591 200590567 419407791 163155382 641400522 762513698 600038860 575795428 536538422 518404045 91769139 359234767 727196599 446911968 638481614 188756033 36906483 2054773 532149757 868564001 480652965 774279148 760145278 467836095 667301899 476435275 78709576 719318826 316483987 531083790 745306768 389221389 153579463 677102210 542057908 973032047 940788304 97379642 245065742 883215067 519834362 186037630 550221317 291322446 696881542 903297882 525695336 343452277 551470509 113539106 195533220 911853959 498029265 780876502 885471852 275928389 24069766 69868388 804551272 671892774 974098451 671088847 704704838 934902858 520644368 677737480 53747150 499394721 508515464 638288715 753233474 426789317 128428526 334873778 663150576 627181499 136741202 118665219 770281676 888415124 485738549 448220552 13789661 437431473 103856691 911402615 748437248 788524663 16993995 635579460 458918411 595830074 516889812 46542926 596266359 607417405 152919344 533563374 182618914 328120179 375451022 716724163 849445299 503244214 433343508 571028543 717183968 795098411 295425867 193604474 976559360 391860236 762417908 936830783 272896418 668682951 118749355 545051512 665809638 810547423 372277281 958987856 307295830 609502271 147099663 415950226 603451833 35014526 28238638 25139821 956526450 409215486 428517108 926331961 243960977 197582965 641098725 767105487 593481241 125756868 965572190 243551163 85973040 657857360 113694699 361731570 597975639 929085130 913791996 115509535 170210441 979893017 339527731 136555156 993449049 579952880 546715264 701177845 764562003 488839654 676086173 290887236 118399360 376153556 952290149 286728126 552584080 990524979 535135340 578828968 82200347 430186200 943211240 92559081 863952826 904776311 945891102 833666976 920022107 273410453 631564514 779016359 874858892 242482553 34560458 480459479 255804795 407339341 424294393 312204608 255881833 415516156 952619186 811172230 661020900 935590965 177415871 320195443 744073015 795270519 576732951 641592527 282783378 292530257 760675823 513652125 197108548 412270569 726032945 803785720 114831298 659567643 808234700 38357258 128681767 106074540 555397668 888763617 448664037 898893916 384519177 885961031 184661892 29590201 950062369 981375161 846623397 845415031 283838795 523074040 720352480 593907677 613648457 545331065 774471046 725026323 696245629 784334595 336443517 266480427 703379054 800667700 987380716 805215296 646858826 94331655 860609948 609715696 311899132 26914054 642927519 203276951 988635290 283083887 211423600 368836146 832266201 621101110 584868213 122668048 584292859 399905883 301606619 336593682 297475413 938520843 452905928 291217828 794732360 940952980 609245694 329904027 87930046 798454650 641057474 255529457 604732345 745835908 495347497 279046482 542190899 50445831 998935642 187240698 419574508 545444045 266207367 86995772 177385217 220268792 153733325 9658677 342842157 847297298 306777494 414805521 609101034 803433862 389472449 435708089 131822493 117731558 695124145 794835544 888766332 324937873 538085259 554881393 471647569 79163346 435898712 986923761 733572605 752145328 776898597 729950074 373134173 135935501 681679975 757402030 387549634 95679098 726695717 296361723 749351447 456675051 28309211 790053762 67267118 81968077 481754680 798915003 401300067 113853000 163805429 548321842 332592002 61164545 770186749 120871170 503768988 733733468 131608959 294715951 333213964 817743050 616551057 809994270 197800043 617098760 769875005 34883039 639760946 182188534 573393497 619785057 69668822 776166917 955747613 609677563 971887873 926057039 123026246 313519776 408665793 411030266 133796477 890426776 117982474 391821940 478736789 214522510 932186079 942946403 485591792 763244962 28081576 114274290 950550571 786434585 962811864 913134325 957495652 774591442 256998822 257754649 266206462 899951671 676299970 678004973 239093268 64753325 488006410 198085943 940930598 982757148 292366910 400299177 724883484 902291425 931116601 718005014 512806898 23612366 293980320 185937177 445927218 242297700 982877203 414551625 325270518 556433398 388390867 771137653 937300714 974409868 380654438 367043654 205391388 758371004 557538661 856011614 55593971 56078289 692950447 622826802 948451544 221747804 666266928 428375155 797404594 690399812 683006209 534689994 644881864 548910850 844127869 147419960 44234985 498354933 317585241 747894649 453857305 889051581 112335339 667792218 683072197 307043271 608214640 168733112 167033803 900181873 922529867 370784011 579163526 863288244 520482420 161200014 602458910 743928258 64972284 731367236 832466607 883782410 484008829 408177771 595734946 422553536 760472355 826764617 416929704 557917850 674182259 979110049 666197999 941114459 567666596 724088491 370688108 226353303 457674081 222947680 250806685 373096360 793080699 192868828 62050488 425276474 141613294 500421363 508110658 783247766 707563549 943844039 943502795 522924485 426528828 45780984 937746610 753363208 592431185 321382435 135892284 620556793 386564165 896306517 110001395 679653247 503278584 197140147 994975488 287209048 192866547 416470168 767985054 425143800 268024493 155481184 596052765 551031352 497359066 818557222 334740218 754432015 519732688 305151158 817064698 450016402 168048495 597826253 856662298 397297046 913704699 107003084 798252306 793486547 626910417 845431413 932843494 55987861 72834202 816359135 449332481 887892235 781357487 677530396 150343045 147669120 195803223 422985397 909913881 584189288 916378226 448452086 454521252 751666408 963377879 750145338 653988661 417451085 299250660 501334693 651704739 232596203 453977567 520101919 729807814 619796912 118613501 774237188 59232736 449251649 714039426 800083854 162111466 387226644 97877434 393230549 260352734 791499234 188673054 915186599 606703893 350637137 263863416 636637790 268400282 816717269 441455731 41014325 684384280 35457938 611020449 641064852 657430040 697887747 380998411 134737369 911153196 655795278 519997053 962348075 882501899 514511264 713710028 277157338 194655228 314273046 492568818 828894873 312468055 828431044 551755747 830186058 976792556 331954294 846892012 157403408 157893294 176113653 709010741 602026223 510623706 578790005 485462414 554951950 298561331 622636338 615733552 706619309 413361010 264977611 849287571 808962743 629444005 948243901 921473549 10995106 235085746 303314517 622551029 566770375 215821934 930198285 155053404 860083192 944193192 523327055 503969323 530491568 895734712 66309052 172604922 446917118 502545177 538572085 703768984 721136253 618735056 356347373 71015508 156082630 749157148 279208395 942099337 632912133 5122318 338382083 552221827 656855840 601956706 789605509 427971761 639442433 613542535 792571206 160065917 498099057 499473846 961859883 48604883 293575796 319388358 661958554 39696624 843708686 884143316 349155996 738943452 51918819 22118818 357288370 813266787 835908872 303358032 313470443 52154558 425915515 858220038 73262113 6986625 890809711 264212523 128380163 790376282 38888178 170071498 266675471 993669651 11401242 660831653 460898306 912122240 571802220 772074142 497118045 813194744 841863959 671406343 561972690 266758369 388653539 438051986 29162789 721505662 68041095 2808777 792550559 972141143 917967151 74103608 842389130 464390639 441290901 291116484 136699294 352499202 900370190 180695670 528080265 485836386 639329909 128539484 802288109 275424224 259687889 177910865 538598151 442735540 757550627 576736851 245035606 433376941 184753390 931451584 846786953 130908272 587991794 740769908 160388737 697428754 605146451 617572512 234027664 719298842 695210437 943359207 605917669 320384962 187060116 874751237 285206153 762357569 632538336 360330342 682249592 724853197 367375189 123703357 839370031 116824842 68680992 603915039 593901182 639396296 651664166 399576772 682445229 548302323 93694249 319014818 735324440 255339220 506780897 941862578 533228344 399892491 882749402 901706856 651579981 764032550 28258666 304015285 293019149 90790929 961725253 957954087 291065951 218929766 445082837 112121690 255058750 884163795 681003953 24522570 875183120 54722685 749260085 863210521 704361237 752453960 178018759 758410455 974700376 553496731 759991474 761490478 367698891 680146242 357386247 705099795 651253474 905563987 788907691 635595381 577458590 866890853 614852299 595893749 598938948 88856591 389308511 70982033 78968786 444335822 599301410 6418168 508814604 718433671 276387989 50549704 539071689 459521831 569634916 121928064 346774376 934490653 426704690 179050651 280346588 601683680 508507521 493727251 625326594 769144828 171069083 943814312 607260527 443118920 873868955 155630847 697633415 537049663 330873701 783601327 828115480 304018239 690677281 158411608 748331724 269681098 780557635 932709720 655397507 791402000 773201185 370808041 840595404 520665262 574631529 65481831 393711489 251770373 881890767 86559065 883207267 40647479 771374745 800620456 475112362 910131857 221521581 401522293 149445097 639675301 347298972 468944559 248931745 17225869 213592465 702271500 627035055 773347472 726817474 715412442 610164160 377183496 510493785 31623161 406298439 935026560 181982321 459019977 856578544 401261230 142638217 835758053 998381549 512978594 939075489 796854603 793617488 865037438 478624172 805062972 247627790 275171337 506791149 854472144 900275454 119466517 570167389 885541090 147263667 964030361 25946204 844415838 776381885 610500279 130532927 365991000 247171550 28922836 334714843 512401374 21161272 654797801 202235354 975684107 471325412 532807987 734112732 118453336 878337455 504603206 311519904 464152851 499579434 617316667 511041947 529257770 198966500 336013312 502470034 671378953 984283930 788597207 858337114 977380789 287490372 840897832 372250283 84723584 930238902 150375437 824806820 654329056 355584520 478866025 655575271 515434636 323242442 769736719 684175892 710865898 547359151 300655775 572220618 392331125 778266690 356931102 219484192 919019424 93003344 701651087 548629082 391221482 189504795 548816825 538344213 495627467 893252116 633235890 39260035 239004325 730193273 619228166 894562634 407457345 997475709 88877493 91078707 657200527 779895761 306330885 710416679 941792268 429856406 921393639 154196150 956248123 534098657 912190539 263344230 817403733 679663513 426470250 261523245 65264645 489802689 185307580 789341876 851767713 449177123 484224423 199366976 428413458 919206044 226903470 553026261 797350849 629976333 67418300 398519845 826532983 155106384 339593437 911035805 913452834 118255511 703263354 534688684 436155455 727692038 654293058 614911041 336373955 125034208 686501742 766406346 940602565 233368221 592457638 892855377 500555309 84665556 581703102 807525120 35452540 474161452 934127369 829076190 286578044 632489929 238994816 357933137 849837610 488110692 397180465 226597133 818060932 689050042 427635230 519067886 967800161 590428243 25566011 479401099 904107862 951156977 434549367 569746034 437709085 799598015 446628561 345006855 900960735 395377471 330449713 553665886 63526665 631507828 894640272 706808832 517348832 287574815 664007432 449248033 72001630 953535973 255630344 267303440 81762736 958386168 269806156 961141817 364553853 366722425 426940111 340858401 258790505 156175891 47507611 644055776 337976397 5914234 777611473 682381614 266575711 954194413 83580336 580572046 904828766 110975420 889091126 338375595 59114423 48594861 768780415 692277037 114234626 353436557 605479415 20446227 21711599 231695758 215721162 156549085 2886123 288087032 326822081 869151442 344441715 69666031 637005756 118483268 285820132 396718543 742290619 491066573 681904001 686991327 725558633 516277769 189998285 52811776 986252740 295663926 747198621 264051206 717943434 979897562 72931190 703740413 507734212 123345962 306634236 782929577 952694620 339464806 249170838 506539357 370705466 889050538 913973169 707673673 529471006 701828608 841938169 68069457 981379468 527869214 719018309 191699808 743235302 99092693 50400969 600360027 749359029 254827520 863267246 156028594 942589414 957706502 831999758 117407928 368962165 893226013 931917889 68102122 296193224 747569235 167106106 451916822 327315063 170394539 763365763 360704423 737283560 836555027 758056141 937514248 351435978 702385131 885592379 916022544 837878582 343619615 247514345 555883130 80614299 303070046 782216069 638186772 922218768 977112782 976759020 795331245 883807704 493652004 851334765 706948092 60687675 222008061 584378651 659841505 340545444 63888213 397562484 298243632 907693429 131475110 992852586 126401318 721963737 513370098 155776210 34041550 882557515 36689450 695865268 35016309 807485408 66610453 671239676 896119124 629350716 952731983 879331480 613341814 724263434 874008624 289258132 356225104 839696314 839424780 914701684 656453970 215153170 528302018 745025547 574948963 988492768 388262019 133057980 360271677 150244466 684355222 3140612 642862953 157735034 268077887 925073432 627648388 209977470 444938442 806349643 887695868 835245236 415390711 702661934 648825181 522215380 703970993 308262376 991263861 575552612 933092888 539106226 117339622 98415037 262053795 221651582 512795836 770989418 578689712 766030091 536380353 119492903 606789957 56013816 633023553 551031947 293703700 951302100 797216790 409492854 782491964 131980905 256202253 871190756 158753392 591067200 689411024 321100494 488718127 94194540 367427611 142635242 504667923 849976664 673030589 809130887 733607287 892157388 390055688 973640336 451544881 282166454 519634044 909261078 161176254 437682075 379989515 434197714 45404561 839675766 721217760 166802343 995424838 228703429 725670458 378487263 257652814 720459134 669275380 145278575 541319910 396161552 5220838 423756100 385729724 227415215 635907622 638900336 84161171 971411189 889841926 800270082 298641766 640873913 865739603 937417195 266801984 1407798 829874929 32506812 868532445 491009817 929349593 63090763 230380882 388593961 806258939 561777294 982267675 592624090 64665575 339985236 208969071 465608878 670200592 252883923 600528545 816829192 765587563 900570649 626038300 368390878 713112588 994159811 953176481 935933866 100736037 90945098 588041048 289645629 327307389 265165359 78875648 645301811 783419607 999762155 876461232 672034936 349619220 348250981 288819486 126582673 125612020 983431634 743520118 157297833 465762534 547347903 882436567 902019979 308351269 547398899 227937434 640683463 200189042 36715257 98990044 303860091 505089466 344837834 206902014 104241601 379577596 814379198 495895681 557582107 474851534 831076908 652234433 998513838 250231629 651508748 397938935 939069963 897270267 457516006 49186544 822290840 881321313 641861881 58553615 928258585 325951987 21824846 529937257 864717632 4725664 869129095 301060363 361733646 136393620 316681009 252616112 911405673 92120352 493855263 812180724 874814372 214864573 238576998 557953275 556206182 822990595 353988198 42388765 904340930 275121515 749436927 282551097 814955878 394031273 637625545 274216679 977396934 253715250 397740592 959751839 420333919 985626433 636102909 443253346 944114794 96806516 540388372 81744446 890223346 545752738 75461304 851831244 274154651 508627474 996203307 31095584 667976072 886793898 644761371 497211325 220558643 202233585 595291785 433915189 305884754 911215197 697549109 506260166 313046337 298994223 773734333 624178275 922549440 339988642 337854249 519699489 943295896 79220128 435754031 169986946 722724899 269917368 323980828 718882233 712113060 106703514 629964934 761342543 200994982 693743890 888565270 598083157 706445933 555770206 344238165 882047746 938311005 457024659 935902169 873665747 180294035 23061105 553830003 329914960 103762855 479249099 374552505 788158844 502914154 789406982 259939792 880165162 30696685 743235319 561153102 309953846 662347954 361576152 657747988 163385178 744302899 577175683 618930642 470282586 759791770 891739357 723340284 482836527 863280636 498215513 543699646 127014014 374907121 16115496 596594993 862201160 630125248 32937973 783513243 11738678 243505098 941607580 804571628 198291796 681543468 310589864 121898524 407502022 656250697 219688965 296443077 796296360 567284256 727147430 39233844 642464843 842979306 331751659 681216691 782141335 456908719 748121516 728097947 769111139 171685649 420908101 399699972 938578959 309021191 108611327 245884260 40195572 133940559 898046481 715869582 189608002 854883605 974657539 48842406 819207450 20969387 916183365 606814233 666086056 720212739 360670994 698930376 790201130 132667280 608900120 266025946 82901909 517672132 975440915 409753398 677475101 454961119 10833156 174422654 195079725 127385223 132907435 337320258 121491781 800946643 303141435 321081955 364649191 477434033 694751195 561406642 6683426 130996671 579922968 483359345 30284369 859980828 939656922 231630636 991864197 649161334 460448150 512549150 810596223 983511812 196644162 132195006 883510737 813517709 574078528 167873800 903007679 733018382 675976840 273808809 710677892 455542623 965855053 306518276 869297823 553575266 192970073 713606048 667530484 495672472 470419866 98347854 70165212 809905047 657034663 996484799 258775421 670899102 675450415 203244403 147540809 376890116 392843972 570669275 286902620 557121273 905886789 45122591 732373456 782027050 527293010 638227781 700566366 567456744 953988402 944811466 716057314 969362744 733784595 193995154 524955854 311299699 536361012 149528709 392181087 354620552 657327502 378400723 929190827 626801571 265591174 400229277 110064177 805674299 724259783 455775462 160874269 639626732 40231926 767010610 483567426 479550140 313488990 425856551 804683782 514592184 140918239 330100802 237414795 651042923 132412102 991319599 675191005 802410044 308867413 798063501 842972236 2121411 913386187 153640631 847863080 829790817 584732624 549961337 866553249 797203127 41831191 84218146 925001286 801153819 775389628 628408763 103758643 919437014 982422633 268849653 808883087 738305195 56791017 2854715 864995863 102835637 280272784 186637492 137802514 508668677 438290454 368904539 821198182 130875698 80176735 389389802 600963409 396190651 933309179 843592414 24182527 848720862 873418079 338993162 933528236 521361611 593972441 647553764 577523653 957938353 54355724 547858739 400891220 428115193 79996371 242040608 446620115 926507212 502222375 916299430 769184373 227792452 928365139 263324420 906115087 186682913 540844946 34751606 731595874 208486458 900608826 904586385 140965110 643716569 402531159 261787746 712104712 661526520 435975067 649134183 165074686 109786142 826888220 933296029 79408575 761999052 568586017 734910621 251691956 605505557 510633352 96842407 222658783 283078166 786503237 155871595 712682341 438381969 848155094 85134648 455341987 453338065 509233808 621538607 362792517 444355188 711639150 189450196 804971527 481019292 225095944 808058107 91766969 762611592 327464196 534160419 511300521 314113570 204877819 334708210 838185139 52401441 554322854 773567577 517781650 765844349 613727828 723290981 696938460 478558096 358110762 44760512 840111117 927960531 164049205 658082295 696314078 340208419 738070769 310764251 925701480 22724904 181534010 421150943 775063828 786859534 707144711 598000150 444691215 110291578 261447032 554467260 581523997 106778939 578710695 182426346 41364065 679370725 550047133 407117643 637547819 839673962 40038234 750524264 804241278 429976544 304494720 968012313 906577312 686746074 942432431 863879613 585246329 718919794 49224169 974530959 976002097 977642819 304867118 171086648 317236621 20288294 371064608 357421927 329261016 582700058 28191866 968099437 673580528 926478554 650388885 921634668 527428759 830129611 684208680 133011829 454772590 591242333 570509763 921863256 831771397 441384267 38560875 305221460 140761693 649793304 931034323 998396463 867847742 739571840 953867196 372067577 424146313 762735005 450717324 565987107 105910064 316959681 961120116 32618569 947119782 861309888 771401026 203889535 38877486 968364421 157594437 226727337 67439039 183904897 429808905 312840493 51422440 427930249 216187737 611496876 704327602 478622598 220601398 971427113 187853569 345992315 919464738 346815891 163463226 147124456 255859876 872080720 857545669 858991924 594456288 262695137 20872649 901881268 756165783 421257335 47893491 412560070 697192357 628153528 641919257 93974206 7063263 466639132 308845375 558097072 707526319 102682098 705597511 516132310 876792118 257397334 791562926 343378582 389011060 795201377 635155567 847511230 638448380 304130663 77801875 541975895 444667239 638761822 885109191 259361133 359260538 676226936 696545051 55838959 411092828 259887208 683637467 972538559 978484671 663040310 684114125 437116177 572524111 397057015 241582931 393864980 167094652 619215878 338319313 208812 664902744 106429931 824019218 155413578 201870087 970006416 631182793 532427750 771734126 390716657 778839531 6636119 142957644 686064345 535728496 359878777 257142688 288450163 42794725 372443746 765243548 568702382 282129296 388556208 614485954 540489680 623317303 87273308 130132310 467312397 754137545 662765318 849889209 898461862 256684013 898830085 911819138 250683551 783921613 978267014 771183844 798440434 61359092 178424584 600040980 456746131 34577332 174186182 76738567 701331798 276542680 667883186 184963925 376805407 223346962 423686124 397499239 397423245 898171033 149477174 304227964 192507391 20696731 798985507 242852414 893969155 265287678 702190346 420055820 895684031 819632566 488579576 459490520 972855382 622570341 880686912 322471065 870648422 138378357 617313113 91385774 829461070 792945436 265459641 499489321 403056858 384314682 934844450 691457994 149673608 545721142 433878480 484298608 375459692 297224213 219757750 904984462 401148442 178764593 381070163 135474574 383791162 943238554 761231881 907595426 69844906 997497434 800799870 635324907 299512994 263196884 502860585 936633109 239460366 177711267 505519833 54238237 292649028 180055411 279169268 50165557 225964776 509425607 35232191 45956426 145951885 883423826 68906052 33236315 776863439 94688406 13520333 907231044 172175636 998967560 851663567 80738810 109553087 964593821 518860155 194592995 603254777 331690892 505515700 917235872 956338342 318594058 845248529 446550420 314895874 645669644 524837188 339830751 772739717 982045804 48394453 537332956 87399909 141738171 370606493 449980091 41131284 945838566 639407201 649279181 647482544 246925000 525493678 181932711 409579483 356867733 159304476 973205652 80993039 582132676 327595700 933923262 877484329 330339252 639203898 478295455 244320979 580453534 800975137 281067517 668572903 11158358 997908618 800809088 56659538 472658475 483136275 313489236 475800808 298631322 676014179 249647286 887133076 397972193 848013040 507141986 217134408 303491763 82908638 639923564 514526468 335690516 36916920 28778067 727810488 748376441 9003201 560448513 31519013 837454700 374766130 594395313 548589420 20995862 329737687 882306345 449890968 176433782 337397470 383798394 36783608 57786362 288915514 92365924 460454965 526544010 940855256 784215623 430712940 774821970 485112454 529015690 101753473 972506531 914943500 895312136 433939770 744829448 165550771 481418053 630351202 988084141 946105110 284754220 640600702 646303408 105850418 516975888 530709568 547923726 174162219 369468968 319028884 122905119 341083792 95330107 879894607 450923313 620054772 471590855 807973790 889391428 823166164 205161933 447220298 956996636 424948927 180688239 387763213 664232524 166248662 411957731 528120892 820060292 786979843 813114557 429332129 929191282 733900755 984702943 655580049 646414995 78066005 934153543 30122764 914826660 72790739 292062605 170411458 38281065 981925878 110951771 480638844 494938413 950100348 128708634 690138414 239603367 321880653 454414607 75531212 111972298 374430631 718134107 527754462 621098381 565820899 785541328 300081752 888350424 399634971 175677567 157821466 997446672 517159932 502885019 621792759 890080600 243279920 448578643 49800712 438201731 940016392 840194514 843365757 206200347 418930290 312291534 903573669 865300214 894154459 644209857 750760804 463429590 587006110 240490763 928179830 655552524 937215606 140661310 854420096 909520366 936901701 835884842 391724889 83937278 966073684 682743682 908361166 206743172 459924898 519974525 567278422 546839914 379328160 475545193 443052920 226808576 927268340 840508374 364556639 426453881 927825853 34534912 334069638 602611669 158326192 46986385 617744245 772097328 385716162 837297500 895496902 26981896 94312999 203688912 52847318 396825462 367017029 973481265 420428155 867203490 309165538 302185395 839661885 960941864 721746181 342418505 754273196 526453415 401791122 468923238 908887917 370478345 67067199 218474758 796022131 388966157 753879128 666776669 953346117 577766869 189206569 64039097 885733661 351077725 692263912 541824215 158777438 560395735 54534675 158704970 826995898 74777744 888658264 604161538 493656492 264981708 293043902 357027103 632572123 567698897 619009203 558432509 349351044 206702071 993228839 171733252 300888390 390305525 680701308 122565821 631606487 724555368 943538838 901830724 761084161 55219005 332877715 554857583 286928826 523774379 926957323 737450392 780307389 901312521 739581990 99451820 127099203 223191556 565198174 500852338 918593818 785219074 338271011 620031975 128843563 35989846 675138015 883187353 351387714 945415057 378866529 990017239 164113187 419414626 562263352 141442868 11781532 299278536 855503781 672698331 643654129 380744571 556937579 944032957 22447685 155583506 117566540 444979771 68213152 770327495 157535066 781081308 248922532 909342682 684209785 736436761 853966231 680486129 892979212 787175409 872651959 866841426 272684549 33392116 445831111 215897547 291536838 860223134 581667866 939237136 174511735 330111114 636201481 663278045 156536727 859914017 957036905 255314177 686757012 146751900 428619784 643243385 373874447 419769675 946903779 983712337 822627473 789375203 905733257 700609922 481363090 547495231 961573248 48550505 203671217 746902974 322011956 48229445 425776819 730056524 823428503 828514772 184238745 323936478 166115225 412642939 918556452 973939660 939770325 202300129 978873906 32489606 851679051 194923833 697670506 281755071 703965646 949076995 851424592 929982264 618704548 393160472 686863179 104574785 150167387 849515241 774305052 584760004 920710850 996092977 871652786 325354139 145097905 139647664 580571158 961200459 522887877 257715090 673965243 696745035 330661098 517877167 927455460 778392694 516146660 896469720 896131943 450254922 755015332 842281383 88775545 538309815 584226209 534104580 847205417 336470497 134289991 405427722 508971234 709843613 583259773 746909355 916117282 99352985 180502152 143962437 895457772 44511836 367176052 824889045 213626009 889496229 470736213 481680168 995821915 665110644 461875190 167793841 678400193 387952469 832971529 434854793 831291167 514524798 637622421 757557293 167220069 648850832 915801985 473588526 112302279 871923871 476623217 766007837 765568289 399193843 290701542 328779329 655616258 330404095 218629383 999195410 15001995 315739355 273658701 438229129 732124462 827562072 469976966 564096911 949399986 703317792 182766907 768203983 277902101 159043926 938660509 709792547 920063649 12857137 521206394 783254340 270705353 997915495 556423004 47671107 857033630 809930030 842614861 469550198 901822251 691671981 35269902 108199134 382092760 9807268 784785547 113356353 882999584 995310693 376553748 511374070 777687938 59759579 590397340 547354004 38733271 371369156 395656880 501003133 103359081 314015725 412757139 113003028 777656069 914777770 520740450 406605661 925822923 53311027 543461574 691469409 437023840 973140750 38548819 203120616 921979527 476159934 962197577 99298435 609816661 527399603 266958701 501615949 947777606 78052690 598963339 439227357 360572510 464472571 334279651 449507456 1352532 838990235 484252996 479451859 326132665 273993323 157202794 903946485 766029992 672085311 709031562 793730033 752765964 711012799 422796597 576501492 210824631 889284012 326949346 126033453 441793876 928703601 966081744 689061649 917143367 278399205 291230218 209420841 327730067 407676188 896381417 964263940 373572459 376244326 99163568 741487761 916108649 195288839 990101482 551104282 788814835 289009372 239709791 553373996 469918625 771939059 58528645 401564293 771690957 192940077 778181019 800843558 822122155 649668461 210412565 267055835 690242675 765325513 283509908 982754548 886767164 420377969 455291084 52628853 944409839 985890982 138279015 38553628 621884180 712681934 883174255 296999495 946291681 926116011 194782818 900296663 227690948 628616308 214808458 371408000 512149957 827748216 919078019 276885772 540575377 839931948 921396269 266196124 764983371 492160014 949150861 92025788 753694884 567231664 274545463 331145821 294634220 337037840 650499461 13914005 467846917 319775471 262952437 717574013 712849467 176191666 905791355 467603712 946355305 42666375 324338901 19895 522353977 845526483 851152429 853988150 969433995 115763890 666040446 264082051 78864614 11134055 195859522 939973483 825204241 212541074 557788182 183305825 382365879 887120214 169899612 765751242 367802048 225092994 247792141 868306253 824809178 638734773 717076010 510345796 827927665 182171294 769778436 931158001 181775834 624807917 267815008 205848822 341180012 20601717 681069746 233752545 296166417 719822928 974399621 439040390 32464297 316181575 859496271 462947439 609730625 872099364 67143185 556860330 607328017 953431311 42480398 194312450 244293818 191506003 620123502 722580321 929709366 595768022 348503567 472849156 295293959 558093906 798421982 978878369 433704317 666956570 841958583 947880485 865792939 126348799 769282454 828620672 280216027 352430376 204920853 278875124 582634034 679585452 143291415 397031886 126978768 648129846 347031835 33937772 251886800 655672211 854904009 285099957 348273360 168187977 46076091 518922346 716245355 151431370 728250070 917105206 583107623 286875471 724293365 929708435 991027942 927596131 34094976 765261445 163705724 374753153 840923684 635480324 578414202 171087961 992860156 764958050 796781054 720105352 754275560 279616892 351584131 628112154 288439344 317784230 638573901 33598011 271601238 781777398 238107414 428852944 255530675 853422589 580483540 620690628 940447211 363973566 133555371 231740267 516552967 89403809 53668594 567975295 896375181 432569155 266848397 893205966 739655968 911173774 874593581 38169131 872033908 73193840 881427248 340083009 251620424 703192060 779694277 250204650 289149593 325466369 37564043 221127012 447917052 489143076 72285113 780905686 468307943 807097106 193600784 432487178 587217175 574058765 275322909 360062942 503986594 399287925 517079451 661378688 686601929 590778978 662087369 726746456 491738177 978279573 962766118 534249557 488746865 528981853 311605890 287125236 526627553 208684318 554830106 207930251 278951820 912113990 727514307 592689563 728239670 237895842 149913955 725461054 402320533 552999773 972808424 489700288 24851441 104374229 343502300 623432690 236652459 785276954 276567519 642135249 563178120 293586983 401229453 932442504 222336146 836443104 4792248 837599190 183669785 961717793 844725859 665733052 275759985 279301269 62429643 99050271 696633130 302400624 520856873 945568226 266884027 858919894 975019881 653077710 712418208 540572864 773690656 697817556 103159695 106266501 567877671 609125515 56393937 939152374 155483856 880352175 994514362 160351741 487145119 126228680 590132496 115025673 152699958 978269545 914258981 617354529 888452254 595293340 95296150 626745559 512966868 396014887 658471800 830427786 780234928 883754521 730432272 413870572 511087883 36015001 901811396 320420861 251335594 741007244 143201309 828101209 834096118 425469974 720775627 653977623 918573322 677262794 398995100 476845223 682567914 893265088 191892188 933199503 562028347 136745303 553322337 10804245 274571709 743994137 208958431 403445155 56873605 669263261 543695268 206278427 76106565 368334202 794954622 626118642 382233021 321459552 14126879 967497089 965105858 130091469 731893220 101846273 208830212 549310992 628076451 180988139 946567294 765046596 575490833 899255417 348005778 208921026 782924943 671742836 471818388 673282028 479269116 381091933 297320336 834680547 831896497 441987191 946729277 262098183 800640536 286186304 180378721 170527613 813578755 590294588 673679343 18519652 778331788 215198306 167658068 460867229 549943970 272512935 632387279 952122211 44336105 589460389 699443177 807667339 218142915 386931625 951655157 136445660 914946947 887932733 498309978 453297237 598962711 856502979 370936180 962929574 132968475 613276242 636920869 862461452 434103719 642306429 610998676 200093848 791249082 431113568 448364756 321470522 752696102 616713866 481758294 959595313 240284915 183577127 374893862 914840486 521044431 741784675 215408844 496072085 997769112 626907067 472974259 949330400 223660286 332972612 446367270 161312486 798510902 455465131 390998601 771816110 197193982 504825420 873555866 344946962 442378903 326328961 556286974 912606190 923291433 370811720 442687891 919181198 848576180 246282836 678985902 397728997 976219613 124487514 998862012 842808563 937012796 14008137 978807001 118988636 843752409 952740317 720286963 412852098 815192777 206503315 490055557 683551711 146041533 894086836 532223976 444998497 233333054 209202698 450793864 384214307 171631876 378474106 232977711 976738656 397351010 608305760 820522943 27531090 396563276 339917968 980980081 123890491 59438840 859424744 702231208 310062002 323965158 110911625 909232581 331296223 539246248 138010259 356763687 647702402 578071278 666484522 972280074 934191979 42945998 74890376 875209789 497664938 755530355 42602981 761772474 751659177 691985682 823246228 296870426 800468828 366579636 893908960 198983619 649849289 275423253 397060275 131562568 376237827 752612282 997666316 493050961 240107081 672579201 509854880 83613427 563759704 957393640 341462573 210068691 360005374 491239219 302232724 181216554 157723848 922228291 273720536 846673467 455976094 672809718 663872731 957334720 136741214 87442863 322114245 520358816 772891411 406387100 101650029 580809372 4139618 259066593 402442033 550941309 856501963 437840966 177667499 431768506 117215078 47752826 542768647 109928570 982360347 587507572 582094452 693258647 774678309 30652296 775282311 150504457 959640306 763523772 783525484 233188904 758371114 745136054 899903628 875479166 43405614 966027824 99630354 463692808 104008790 694412489 532319537 780081501 951895000 616824995 965856785 942898872 552263535 619195132 5240394 311235939 418757271 5906785 308953137 965702900 397515848 259161222 93222019 890216764 403988313 723507652 63418477 447631363 260760899 538400075 50554082 544675457 293883213 643749239 456687474 992536228 876862550 759053515 312087695 139344095 678632639 793661189 884162708 43889471 113180833 994174512 951822724 453381045 249157620 13332501 165722026 746969091 152503974 312167060 77760207 290537593 150921670 391173874 856559151 910011509 469001475 608321240 834589076 15540897 817478081 415904466 773248980 66144291 136802237 31708193 693400598 336521882 461556749 807795884 641983231 980768317 258757060 852167516 278856542 281041809 383133239 709673137 552680644 686434852 799841099 3354997 949352124 539399462 607808044 502834841 938349606 47179849 966545463 893176375 928406358 701965468 139963053 287153002 771353653 269915559 9357294 915611775 472731753 492161063 361977058 698288505 142383170 443413827 641882852 702115738 436383113 347410027 259488137 501542829 437682201 285093573 553280417 563654998 442032091 142471235 690560828 12052461 955277689 285576874 134342044 570423247 516226302 104700229 640475064 661033996 193303051 334174257 897006771 420747468 233880643 821032103 433949845 926986482 953720568 349914682 937904104 653594551 309376419 609141055 776739961 54857381 704699615 392648235 469446736 207558107 669775952 294824059 597124696 991210152 360953659 779814843 791493385 536559050 651272919 766147485 525119503 51111182 616122478 19247256 180971334 176774534 413311565 245906759 472329800 123683643 412405263 507850081 791339955 774406570 443521255 897344535 967584549 408631239 795923382 393328588 314090300 518103751 338318018 349667460 770294730 777532897 582567129 25909327 511602038 214798870 531516691 879227598 528553647 883377664 895661046 767127953 484746235 266405096 284328284 672445195 535863021 507693828 845752161 148516468 631700068 375639299 533529201 705957897 150203343 467341576 703296280 699854157 994019483 266634972 455409404 518982772 88360187 209565953 75359862 690960716 496071657 866002835 181513491 867999250 528885525 164751486 352134302 396889579 156466766 893769189 407551744 896238968 210969172 118360785 85570000 486970501 486672776 505936845 792159500 57249661 25349974 21839018 296769093 647628434 908033194 508354836 410095039 509579377 389475353 434718858 979710515 176953590 460212374 420437694 828905680 596976559 813522714 155745241 710651680 648016270 549273720 746588409 20755358 610277190 308313739 491203112 81893619 288268677 262123609 766554431 804636223 284678078 727987787 889978752 785807571 829646392 583704707 731152729 630048665 422038178 196004102 310739083 369963620 907709251 108614258 859647244 437349553 878142059 876589221 624991458 652431332 114685093 590883038 319684236 165103414 285245 286473862 54878507 670227936 797764793 282560521 383123138 102975722 252827928 68704926 466068136 265079933 487428613 485933044 913929417 96486935 277830525 34737689 32095015 531192047 592630685 139843700 290245978 398261076 336345909 451468051 622851711 35770580 605448158 392666846 808239151 989012960 688803445 78764133 129244511 144835357 141217475 13524605 519370707 632200986 961673384 654109172 743452744 842614087 707430771 936523876 992584888 296435283 502629385 882745956 544833362 142689809 842021466 940021613 363192822 233072243 331127411 602142744 439929785 391995091 245500551 811531046 944981023 731871870 589409109 979076881 610254266 186629074 522750609 528852381 578864258 416788402 92074870 266702220 792022948 129508858 955733062 987001052 853007132 152196129 190191007 637754986 779230952 353376190 454522849 262899503 249323997 179768346 859934191 570212321 386880183 560589497 235445220 198280504 3565696 763002961 198636575 561911347 90326725 738542604 433399730 833461431 775269621 51416178 579878443 127052635 302301555 607635488 972497015 667637111 924508613 781995913 2962958 73226497 525598030 304867552 159548230 675706411 88177454 371625089 432662779 939349308 89744388 783303572 511278058 793792655 431485183 205856735 772565303 521864752 993142026 983254634 995878544 630239799 240316519 236389567 977420782 504304807 407717576 996345276 394546490 961155649 29318606 25695089 919734147 576202918 204596753 338700570 587703054 628485714 275861282 737049640 381722016 930646341 967480167 572996567 229703941 915406871 187802204 282634963 204007156 734355482 114882658 300541352 187631180 731918372 963070739 794890136 707255136 216169942 460354098 741336135 382315868 709841593 568558885 926948669 227142453 437180483 523449128 38149927 651956021 345073742 185744873 447214458 604872670 103989264 882196074 443593898 6702221 19142354 706221848 434196445 419464887 762204813 36981517 404722692 323938229 496611120 823363836 434651310 795996383 419440872 864794726 399477279 815631240 222798380 129300512 608495811 245999726 685356955 751437414 779353997 333063138 535450269 526419633 889959321 653566462 207325741 326236750 104529554 41164632 96251538 198932405 409048879 887916020 342168557 53156537 212866540 502461971 132417588 793415758 786411757 114340383 301630073 112814118 178103353 42043390 313599311 986622152 150268295 523976191 817086750 465612015 884293972 616109004 283619794 845145518 530820751 733597877 477173511 949375451 659462174 991764419 198174288 855224002 780184675 608729665 603722141 287298876 7706228 989799938 795289878 342200588 885224862 988187428 541420235 796547424 102790056 157339513 746650885 373014776 208255214 38307190 619986889 813010504 669982308 219616905 846528733 699304605 307940900 68648134 29108154 584688891 760161110 236147013 983601095 859988811 922954285 685258217 605775925 529415333 761820156 700033851 760634027 452380846 628228926 361703854 514831175 441150868 146219652 714895328 608731987 661727983 643096165 593229999 495128329 693118889 846656102 617804237 44117165 915532907 604956305 74261300 831652000 509920287 306811638 151149897 148932175 469194177 979729892 646661022 846403146 84373053 50967583 302228921 746756176 836596251 588703674 912394365 944441218 855477607 425614694 665118073 810579290 779670133 712478044 866696192 638918360 810672142 496182645 264494326 484499403 426546794 581392134 79594014 790159392 961227850 962627140 336623641 676085437 448957438 350807095 149691713 857679418 402933224 708377198 422743074 595383675 593282388 669780585 274545344 743569330 651319873 273587824 95455423 206089532 250282290 835259679 348302557 190008276 782962349 492585186 620752376 659807196 904203658 681487695 104613897 837619401 12908839 596603151 517119427 39997252 584967984 186018036 801186576 840220891 229307546 174893354 517108015 994374798 932719234 985955583 988187865 575976767 45895626 123314306 709967452 321693620 645903895 354016621 84937206 671680834 411669202 615653526 371693154 805083344 238315342 358895834 886321179 838600898 955002408 58089174 267017364 829776074 854211381 961247135 75883824 540325394 665442666 236060205 381493494 6140602 200404973 833198703 82296923 934799362 746300994 228407881 713858991 41550865 629130109 707759174 154235014 592773542 64208214 25094201 785529603 693734420 103242769 595920491 322498467 320310120 118509519 973801244 887278605 22385072 814157938 615036088 108315457 588107348 509343510 409384317 639938693 463622239 260478707 716206224 294476692 646427864 737793887 297617803 621762959 581345675 234113246 915204126 222261578 186851171 556921982 154868783 556974445 753829298 709295982 767786839 902511087 155266881 398217319 885362439 865606148 373594483 615856963 440116726 86257599 489038702 788731426 66790228 345282707 905562876 790607843 226615035 748228682 916630043 263257013 16793677 64922013 205067349 532643986 510863134 35742876 719616161 828590664 628196078 349756302 220599347 351703615 346464566 450383250 822002361 45992356 892104770 93297407 700412927 677571980 364119310 637779432 762159810 336570537 55522177 990223987 644692605 378171935 416801619 146548993 651699951 769669136 39021089 489416515 201386711 6404940 158315188 508625882 418374328 143594939 400666276 750944223 664667894 427005021 652677919 553886644 957259204 576170384 879133291 531448351 293325686 885116565 111764126 940706960 383897517 766953503 916342089 572455829 358080810 85506727 467941282 457357562 61523979 375034807 445229882 510516962 445742408 68301743 831806838 51652433 992056896 841451481 419006000 446917523 507326103 663771155 578324764 791891930 541081998 905489653 88602880 816786904 559539823 71180861 892738077 203360886 145910378 874735000 538668065 191321954 130381946 458806399 959919470 896967117 760284596 973460773 610385539 142352845 557039861 76901396 741016332 233107657 631708696 823063759 244598795 31174236 445515337 316229093 92080503 920648391 877768009 426267732 175440408 152774714 967054133 644856452 933587470 811618904 107183753 373705690 836374516 987937018 149137800 723618025 170599684 534549937 288959665 16153113 890264535 214833220 30224834 39964987 201410816 241394531 762633068 490725876 267364831 133214353 831902852 312769586 196455491 435467359 404204168 39593413 712329160 839467446 633223684 332221334 163681617 37137976 883413702 591638499 238170149 224928791 104266903 71302577 678195891 612848987 645220333 157827904 810961856 384318409 772926312 263893739 683013721 898185923 86940960 83423300 242188107 667136799 892123106 193568549 994671447 569382737 144724966 340555684 976168491 65355918 484232286 263499603 998110046 873239787 227247262 264932753 946922263 269391915 882856305 728021653 162477905 781175828 70807859 827442068 702463971 534339080 97337243 523658316 732021571 170232300 186037616 734042133 583489682 292408080 405123573 318872738 461413752 31735831 844791579 3100519 667705869 204260635 832915153 922579464 406190176 467017512 830356936 655789621 861532929 717213485 144133864 176328578 100476711 283099415 834928198 275555772 707686346 843336184 921704665 226732830 299231016 553293224 342636397 573165624 676093138 349403412 359138460 229325090 310163381 104981664 265770545 874385108 122521203 152882422 507157400 885779613 54829103 162889611 133096853 526752818 694033408 640443032 245703125 721454660 178625248 234234989 558124060 370398302 624350408 83498090 987889718 580328937 600200260 272577919 59399251 173941514 99996629 79642627 305717382 519154655 885289688 969125699 518044853 957079706 496579225 630282869 368147513 533482334 256728453 792976303 333343836 341907568 224532184 100613947 288561493 173155697 485795112 340136999 61895521 352559184 353568016 921632079 64396347 843159707 932840410 534569825 373740037 44059983 309453465 947753530 258291791 106638642 527497213 826695966 736302688 250558523 276866877 463798954 50855553 413700960 116117909 768436989 867869301 770753028 675689735 649398323 812955254 215650664 259968816 468019023 662742397 29461228 285978305 607000410 72504243 977668802 777138662 456035665 818652915 590337845 389608773 970566991 554235132 169689533 66016031 572532612 527910391 359174453 763054980 938888408 198488284 457170321 154684741 539350093 427948487 476197733 334331768 686676730 340295647 542891206 692420876 567630109 337953061 366432979 210584200 225499009 81154085 620687484 2981472 511673666 29898836 919747412 772947514 494615203 910718902 122913693 643108566 292665707 843013159 457052136 133480919 211222337 168014491 935622667 734302432 842156454 173344420 941807113 44439881 227647973 118939746 525744265 645832710 80100141 539772616 939862281 256352454 797151214 178603193 196756041 776613752 945868087 150454720 659817995 752767081 103349609 993822446 780305940 18456862 773994720 316328057 548036812 924260423 924895258 99115315 486995505 442012476 77147878 395874522 402854843 630814662 31913668 701256141 635515287 788844459 231538621 653298172 928201357 541049865 483076758 125298557 97717017 851850815 780983364 452427017 584552092 611321439 385607206 385528494 184656204 708986227 247671789 774558753 270175295 64351274 761499694 326004412 355893707 754292219 144134934 739389591 586716716 275245848 824484390 848502932 579854079 700068913 364368637 371584868 120524446 558126496 25723416 983420934 26399273 180508035 103913380 895251281 160602432 262118536 81843299 718199397 138785630 805032954 640276197 563741893 482350438 728940862 430049450 817989786 542960425 949102474 854211342 793188733 797947702 245898061 74411075 639240812 80321879 951845165 824714718 332211950 627255340 957495045 811901908 206292610 494696019 833567732 758090946 622008884 829172290 59067303 534123762 48364041 197682449 262334841 319124073 797633424 405959860 774485609 911617741 423411734 626133666 784294322 850593166 32829574 293130211 965893890 116531421 95244228 571476390 946537027 311063083 59293852 870348113 2034120 116695822 505596827 810083589 183001071 818218836 983406025 82559686 106852798 68291921 354104650 451242008 742476233 814391689 289663005 78801535 46987710 470876639 875865238 761423309 793326125 266822563 583256171 674729411 957191225 777339224 980407712 321983190 723622143 560927296 761481248 426229957 804551007 470736856 587615932 491779914 801625096 961175656 910416384 71693425 179410968 30716609 509723527 591881062 171718042 235479318 153556953 95825225 653818831 925551229 560532090 608853218 71050942 624568955 418219891 111791458 939168250 54482239 712710307 232911718 802622665 211311066 340541516 129251527 352517538 866647927 585595604 344841272 72531643 838470853 6688897 108913380 622516383 364256379 94213784 253798532 386444889 602297445 912424641 420055765 534053893 118639730 875399399 601855311 404535546 514771318 221470742 176051738 398087604 839296432 687155776 27152170 956217753 697239556 312044996 164186424 873240429 169484588 851233692 540733506 616531196 285997042 596102155 439519098 274388698 419322140 780568391 720208146 72805354 750262323 221706393 926471706 324110026 793156387 614077015 368802723 484928766 148568614 65113679 444804982 860767770 989420673 120977491 543853726 812350770 719674033 839040742 93332207 663887593 465996206 211627786 387480370 20742689 555334445 944700596 668507660 662646455 349225461 379835674 378376305 72028930 411949387 223051568 336575500 312498962 306418915 485451143 672488047 988400983 439199740 125358575 671947511 7847748 361232373 517089669 199189303 889395079 816870937 401997676 489541085 306711959 950618212 421606293 27979616 677908177 23274550 32606613 511029705 51384255 723827824 933142696 465323420 444588248 997450172 11335094 412773023 115340735 387196525 263886488 598004133 772711639 385283543 224455398 338325847 72284927 931963317 343097144 55653654 714258022 361834032 230419599 961081167 685821167 427620210 801505769 526890865 598575937 519995890 737417435 978659411 566491677 888280679 738803500 541410183 212975251 916773105 811637953 974701250 447692318 986493127 35117080 428100265 988848753 642974406 787099443 763916814 682428604 921365901 813796397 551906697 155820658 829910550 830116012 328115970 902567636 831817360 1856505 789503949 16452318 760250277 542189107 208763678 318177287 397728652 441624010 947585500 617127299 900316976 621804977 883165754 907754582 544123299 566823765 652075192 348451917 525600914 352171455 590280921 413149078 972453377 830580317 290679630 47564654 89427412 483251786 997046238 710598064 974881676 837988130 750779249 118372889 662496710 801665600 70094675 901701906 465813287 416323779 538200771 778074516 393719524 336276376 809870644 607700058 605889981 82329883 317094598 438170610 643877893 301113752 222963411 355094539 913882942 76783831 910275980 705296396 268695743 925370314 349608763 975996191 628776297 995508221 611044892 651204652 196075737 268494772 834191272 618761725 850737851 678324060 168545991 853965931 710396759 164053146 944197737 653791205 464347984 94751053 759066794 242903012 70999011 388113679 568789326 741809086 61222796 120199375 626370909 93916030 160792094 650514398 717902485 137601767 691800127 368112780 201647718 762442169 761058376 74416826 3312946 501701670 738212593 458054875 486792852 178587040 466996161 420648564 113976745 521203401 814033610 365734593 854158569 930904991 686235073 508606076 280275180 262297726 847855571 587020708 505849969 207195229 152017110 787810328 736262799 77575375 370946921 786542482 990908743 608442828 159641711 153586788 120504554 244904332 905585546 476958447 772300540 772662527 476811471 517729561 672883436 777639782 38052915 413103429 631347405 782544192 315850996 807492949 993603147 107316219 932323144 975987465 781870148 718054709 98619752 244550226 575393870 875262732 585915802 590245511 830232197 203527998 216655589 886996253 936218527 735732082 407599540 584864624 287611239 347723440 58624510 19428504 282578444 776412791 885036185 645668203 156916650 329344747 609256972 572320620 507243225 314783973 202518390 565845691 47208461 149551245 289872720 149706036 156739040 541703161 687348173 769476277 943131107 368691003 970834960 325668356 863783882 193023306 539538506 277326615 323637600 487229644 491740152 560634217 284468119 620197694 688675916 362388530 397206900 181075514 962997262 503174209 620020759 504537934 740129790 57096763 956378164 787986449 236421105 409792814 993529724 604936294 620733681 633648472 995957752 994063193 655092875 908963442 642757663 949890354 78045243 779718187 925595468 827246865 154352922 497550770 219790995 563893188 92114721 848661879 16187600 446156139 929475465 42308386 261476257 444836577 510344279 813097368 434485112 587390811 682419965 14419649 119718121 326207188 239878964 835361293 958990413 191260129 20827550 274298246 601578209 122445214 303368370 11796378 951626041 430330983 797733110 776584598 337036929 156687734 263226860 526578343 196085768 980393496 421392081 88383399 545041753 12381976 832603714 388792462 349550191 904329661 557595636 851060392 844450752 132429127 358103057 177331239 346681157 722116021 469251905 873681063 102183086 500156595 716012172 551460996 652533978 382259034 903781939 585633255 237860983 575658406 97281106 391398424 417218192 109730615 13549757 456752959 448641944 165083480 262566338 254773639 395050126 746842762 508561155 532299044 549697130 933328463 693562332 844421896 901704999 715003403 849006438 374715793 356686957 688754445 247932012 773158614 573742879 684066420 129926559 546988948 235546936 24524477 108119044 535660819 477359695 917064733 220380323 247083459 292683108 464115968 572547222 358955501 921012999 767998323 172028835 578454331 186025205 775616405 812491051 111007211 353844047 63239356 557085759 570125232 949937289 410738289 662067479 867637966 934210630 480101588 900434074 770638703 114301938 132825651 643125306 263155277 341611405 214375041 396848722 678296209 415162363 271332922 18907236 490201720 531676960 524416509 754534045 996525035 259377925 824335926 58734181 701252901 785177997 364391970 119880938 940099234 298350824 141169045 527316063 646531499 371215538 794785945 447655492 955899168 437058006 789091686 897404751 663083978 937302293 49162060 75318768 553606203 837825723 760570302 672973056 812469723 911341239 49155665 410215910 470027366 502917769 496628608 890557379 866347564 601269149 110092259 939212641 437417756 611639183 747651694 997273337 635008492 897962166 832517123 623804836 824251513 335939907 708282085 149957095 349847143 355759920 974260379 626005086 914460678 53563254 21554975 551303327 343719060 265390066 568844711 297769167 821148196 451961820 702059467 702386979 99662467 744939982 178067447 477735 415987647 386498138 564989831 533671908 391463020 834278345 42097126 201980090 647029193 299789025 349072971 525334254 669754299 466700154 427939118 384118680 372339821 678145469 45804480 514726593 804924125 65130050 835140883 503131122 400190031 487743210 725405415 677020401 74849467 342086440 34285928 662489111 229235363 717394619 268191719 785466559 399403422 674343603 394003642 294362540 434362353 323108742 41275247 334446230 983523506 63631107 322824025 654955376 491597221 803216374 655347275 334176350 260660269 427988169 182167958 248414678 975810595 155397871 80403002 164558040 632411532 266653948 283550488 742113966 129223766 898807921 966643214 629386638 20337739 494457514 692730872 356825228 930107473 328942948 663017200 430059068 957046235 612662100 517310275 914110207 88821765 421861566 520031619 949383011 150936384 869781537 835176740 743269218 563795679 482368587 936464046 434189663 884507319 258711815 614347906 75564170 616549048 100235153 243813912 615013146 517399535 607971858 43553131 248096212 735370410 342423812 200886539 662795949 957178645 174427480 56970402 828687 831009767 846180829 883135546 682168274 357240614 695439225 293158031 349659017 287155729 964822683 823535222 522712290 98905821 302682799 335477773 406735664 237286221 870777924 452219793 750066434 229516378 234860210 102675458 3837022 997445507 3250007 969509954 965272112 626773773 480961763 205945322 57733125 611536717 655688932 149949524 114655055 912663491 667404553 916456176 419995832 881918522 405803779 191557100 84322205 417949939 594863282 6277305 258460915 177564504 233619285 548737166 138816525 914302434 163052777 969638615 706770036 287745079 21304265 289038190 694382800 765357788 117222811 657958490 990160040 855408729 594600038 817186821 720514235 517823684 506012959 712997890 1784753 596146730 538007388 600341434 292843786 835779661 217732602 455045234 410965131 473677631 180811740 661689974 107450382 474894986 611279817 253629687 325506219 808797515 788455459 529337463 901674209 966662176 884158924 877626560 884916323 945033849 39654867 395972996 9898608 791084793 441543514 317576604 315674133 597583415 864919082 450809306 950490701 9085270 213595651 904093820 463517524 782730877 355466329 361711758 901140685 874669344 206525163 521810634 139230715 49392445 128746067 405834345 967853527 610397238 483361306 588797721 42182973 649574633 134246792 914895795 207003155 638338885 863538603 933372837 747733117 402644354 8515640 825709896 858685717 77685547 994747844 317947770 833521385 779316861 772373567 254539653 573376105 71780013 388504778 666210322 640516258 574097090 681467100 496862950 439498839 555105095 499032866 925204443 436704973 771005035 850111561 520274905 57065589 670794688 90817905 530774670 933836988 472241743 648055464 16446324 637659626 240581634 856382408 292474761 259176552 670047890 877788149 79002590 267261909 65080074 64856432 162292605 24854140 662394256 538189159 346294156 171944670 265516333 398012564 184139938 11522330 559408096 782131463 186927706 245540684 434736059 874498756 831763829 736016283 676473078 442703609 152505511 354339888 202709660 398704858 620802022 884158289 687195741 959184402 552338828 48016688 201421169 228593966 551866319 730742006 549622597 5213776 758354790 611271180 44409252 287026899 372686301 419019240 370267204 297001994 548417809 288197021 178111955 808619266 425796938 231594428 558830012 246064541 857664425 310179000 247944932 434310829 124693919 625560835 196971661 148273162 408796364 931896975 749692548 332184693 333505069 820915216 236004053 852682334 936831599 716941580 641485744 877621013 695422203 786782263 59318835 106527190 610919042 413352435 321507966 630993343 783188445 264624586 884186158 192211722 1093489 210337489 565572316 12655336 568582254 24613239 600671823 123786666 296340549 836171528 931338535 83241605 624795536 159321520 280983693 866520633 90579102 14227833 116790313 618870331 58859596 929041484 547395209 967338992 79637523 269157695 881673260 306401004 679472954 74018843 603326560 535551896 206234880 195165238 904905036 363834051 859291991 470630000 368362194 820831626 319080004 331304823 564561547 179849534 841359150 936534577 815592159 171293097 124057186 732635415 369413794 490531840 713346581 850320275 508208532 276299573 226614773 378999452 775565088 580296375 572799250 993721920 336058262 802863019 80140789 810474914 455985848 321167463 890291193 255392947 906928935 979929721 295188095 897208965 202231258 180324469 314056454 852739950 870287633 589188120 840682474 37591239 807429792 313435667 779593134 745682431 653570734 661666953 160348606 707538811 590304898 274158637 685706344 824963118 794691868 104015989 773439904 506893651 327637376 320841151 420827443 63966827 836087222 729692716 406867142 788848165 56513552 613307563 780111205 650903775 480796256 337456583 43687589 636187830 688832440 635543256 144503979 889448934 699775992 150162540 901190139 230307837 707494537 264225273 917906044 819343531 424307592 891113670 95504713 163008504 169772935 697437240 943922193 463153608 606525092 759542857 977287661 295130042 910485251 855966609 86224624 887757727 715362730 889321116 154075299 443113166 710038025 257363386 344549569 157864907 678908594 520749316 938949147 685036355 889495209 955952124 242781015 752800937 15944552 669203793 929882659 932030040 680520522 28782311 215643099 182040237 496055375 864443843 796339557 982399448 729026672 781875791 32008468 683038408 292510045 266594618 553667930 259890052 147250373 392082066 181342661 331668142 666737118 660650596 359836083 1843692 168954643 236942194 972346500 294204161 999735228 469398895 911592299 569917844 562417763 948689913 163857298 545054500 525818640 106162763 847616274 557266286 917176565 783058336 80276923 794023388 826286982 2318769 671663115 527969882 876309273 541646526 701798091 984806807 200491142 807310697 23139725 966181694 162552921 446272761 333478477 83177440 984294380 457352402 861987326 126856542 604900793 471072735 774333640 691899610 439317468 974130033 294372842 101626609 506056644 771928045 868405138 369238756 527738990 808780133 975168286 192625958 8908948 221949347 949898814 795120239 307197361 554061708 295013984 717413506 91624004 870749807 169229469 204973232 539304705 132070346 393472231 137707019 971573828 816838704 7045095 143109421 431710625 862682385 141435239 484057680 659560422 494946619 443398003 740614266 193635722 79892807 56776826 903554530 893049561 871159160 326239902 247606812 168492975 51993904 930506719 775354801 651641907 619681024 137432394 524989639 368737554 555203371 780579333 562593465 724909134 855524740 118909309 14259264 238241605 106431189 346365231 628318078 435623499 210142075 82735036 213231756 824286907 222775725 723821296 540616182 28378397 873729967 401297020 132838279 361252167 495653946 22931597 716042316 612502833 631978294 444967692 603182636 429199345 528948744 220410054 844840523 727860640 405262106 160909088 330865856 246216410 751470944 428906494 679066353 981894149 93519925 374130785 976740550 172155837 461540156 842700451 695422457 9279194 126208671 358793675 575592122 530357645 440122096 420784307 899058376 898844397 113337040 394438533 143088108 655735075 291072795 486339695 875424240 943749260 493382332 617897259 858170864 936176877 590543003 78476840 631778318 158319335 163038103 644305808 954642298 96415042 59777916 416794084 302323897 839132909 990055363 179824669 106185995 735901532 506995923 725739808 696435212 107219575 88829040 300915726 338701291 222305494 362925052 359966409 114620540 36106831 892372421 173728101 466404662 888223545 544024601 441765320 281455807 211020587 338134295 346874640 542500560 946997981 347571492 258595213 145653812 788333915 427931983 976854018 103227841 713241032 825160975 98412721 876659821 168871651 552337073 461293670 861051862 774650369 123209219 233239282 350641895 892046364 688314001 707933241 447252838 437135543 206150444 658793248 669737916 547063051 305206103 94570317 147684585 655489019 222053740 684132535 723289268 564528001 693932587 605702847 637600448 26192278 773881911 210429827 687507582 853907686 87651736 803125780 727813361 778812953 312119162 425652794 433416831 337944391 897201550 647242222 901711475 445606441 610686685 48483666 749598627 534987482 858491371 28264317 860343476 276075813 772501682 534844202 336453840 122781452 56989204 197368558 378889886 676439089 993657320 286261251 470150482 868264775 491184502 490687239 389253306 216163065 64411736 838068600 186962774 119218382 598499585 742654459 739064553 539004690 399778770 412708322 637805183 541449358 785751123 875703667 238477115 477154994 247987367 971022344 630205603 817183588 546411312 504306502 798713447 201277517 318639093 204626485 958319440 595246482 493985431 694972539 994921892 483205717 601680849 987209442 47877241 349880898 897715188 123338480 72530509 719699966 519899823 91029327 113685808 206514197 494307061 594696961 404985578 634296246 814175026 63504429 533745522 544586858 117043967 687071910 427461737 763165651 501486358 229742638 871745667 641236460 892596094 414762804 713942521 597279029 92325238 207996300 278096547 375910823 696351571 970401718 422454947 689292645 878400210 356528407 838130968 424259936 794506722 455125488 502512431 957417482 707603821 633214742 680917422 274865878 888359371 817995582 866868921 478245146 661439303 221057164 356990465 237784272 319600864 501750146 175926732 121052504 594713896 830841825 728377370 504367399 473262246 764473033 952576955 280163976 126258335 739138018 778019941 785087532 412241158 416568885 490325966 183620539 86628295 391859047 217878364 536721953 454733195 923281966 236112413 761577255 134251009 622345373 173736401 199581976 732088372 106926992 273733175 152698833 919041696 372703662 14853786 131252625 974391083 925401353 835190071 760001979 725544201 871497833 965092232 28349770 728552774 670332153 45035154 876127451 533746407 321655914 157057347 207299975 874049090 57371441 491828838 807024030 864942058 319684300 888321280 511117504 725097953 750610824 399645373 994947284 679418727 31592774 132079266 198248057 377345853 366022269 266295019 647403726 940149171 249398017 98961008 138237613 751099058 258871509 788995387 814051415 26321518 384690256 390657198 18844798 411581716 494424119 753689299 831393809 707198851 189220277 153891929 408510380 677968430 693807250 610070313 297214347 392729138 255581349 358252171 418351533 618478507 653044801 888132146 4333055 431878854 675733211 73209612 346448125 600008009 969730291 448053677 809712728 726176994 113673011 637411263 723893168 211001450 602076706 184718961 872169082 602510706 762127771 318449968 524670839 174976455 650643596 654785200 935445514 673172066 135952803 889967865 578423660 327778127 527613142 888792008 295019025 514473057 750520985 639165159 698504653 991293727 3300244 333914343 840098922 506218440 708420521 508656285 644107276 623433343 107321734 673296585 625656028 825689732 99218770 614125268 345301881 705436949 958306190 786827082 809776577 313702546 508259941 15137148 146276298 127125690 665541521 464634738 232866394 748203014 853787165 478758206 147447587 311677497 342482625 746105506 35758939 759564932 737814326 913783623 994201686 856800240 794956811 223225852 755033406 560211756 323805899 230813911 136048698 792232738 703614961 330291620 454446989 104922380 66676516 363720856 446784549 71732491 138106278 611995047 318863481 323461221 979292724 136303926 53854568 363222521 478663512 960496862 431402835 82378585 371910245 144288390 327825098 514862520 534789942 494273350 839305527 540033955 588837252 128621616 628918410 917049461 771450328 522210182 732186759 849574302 903517293 10673242 952097365 637328707 911416822 704581294 553066970 711402969 439521509 809166894 355562280 498696188 70919431 871716257 487430005 430443307 693361131 755781737 778588075 495407227 54809253 843568439 561409985 80752208 364868673 824141571 6655169 94081826 294247358 826182285 936857119 565859362 936977306 650358640 276825641 914350192 434415996 61693191 268604645 47108230 625401262 795187138 595126283 333228521 470030520 136476000 565525649 571951103 209653067 146227581 884402211 908034837 738853081 350389844 964680534 220058881 138317319 126297781 332237816 424889698 681645965 956092979 249172376 409733210 816537160 15691729 920814878 70286921 179298748 286053383 331552414 806761159 653504060 234941988 129269841 466404052 506432419 144559895 782464966 973979827 212924615 368473219 162682030 934257159 810051839 41064631 519405333 972247610 702793923 447955703 652693098 508251597 456714583 297223706 139392134 513091681 580213733 136527570 258453095 522759121 1227538 667963704 883795742 626592172 271939222 126375010 301593980 170130791 886435355 344570599 424464062 732550192 15537947 2870994 878784284 244782750 772393765 925278740 222474843 644121018 30042933 146849742 957316862 409990855 789961249 458503165 609868534 526144705 535602455 28058189 670321962 399827650 762236530 249421931 411635109 596732247 704561120 67818337 597704924 876132791 517502023 984977268 484661701 495351115 776254032 880316174 905305731 817115718 949121475 742679343 209615838 402460423 982744100 224300383 419644025 970272855 680560058 517816345 10066340 190151961 859325835 168258164 383325839 595191541 356362718 104201092 630752488 121659183 605814121 820249754 930534128 196465458 430861203 366367972 836327076 854719006 605827732 827251696 531664822 541288161 184469045 389747264 252816136 977336569 466582735 614329725 674944834 235026746 651250494 138571372 512299065 623087413 366143143 814508013 320682673 728729640 876513192 705762337 386426035 397801117 452698290 397370403 191669367 119157323 602506033 829917066 204740197 346197798 344819147 195944693 246692622 864105357 357635761 909195064 741566747 255125953 141294364 375486394 438247354 598063162 112251722 741785476 717594023 119738480 249733807 92126853 960416816 846747166 1333807 824611573 167045014 989897398 673313381 961664963 323245893 642734408 395422758 892412005 939512776 908361101 268750075 413238149 731736157 664829136 396298798 286536760 185570408 938895416 75140770 75273907 954551418 575848645 786775746 654545048 859214142 179467309 622132545 44789412 336378526 842931273 972596040 235131051 939521997 324444019 121486017 716492221 557784277 986629730 233776808 663530315 789894375 647206202 76480460 689471510 225285836 602392499 994370029 409725400 294910530 960517030 668007702 896652948 288273536 116923722 202222474 911664281 281002773 126932867 611051375 988555930 560187771 41548377 665352579 299963593 725423305 82774602 552502434 133374770 719990210 472856121 190320417 999227981 802406879 648856647 572384189 894828277 746827655 889830663 229983067 465067853 488265392 62146628 778400259 858271826 192744971 247439970 86139222 814691874 22458150 682452156 535595696 894213977 660366078 516058676 353011140 675617565 824909806 659656115 734710608 928853606 603562512 543290285 519371455 934354689 140471523 863708572 730826916 549895261 749799828 754065509 211324407 102607342 641817576 30807488 656223628 752103930 272262011 431466329 796231967 513035536 485978447 199681699 519102969 947251779 699493406 871441723 15384191 761070004 735604371 722682659 257207890 500177932 638776790 335163393 983704664 706878074 167387826 358613808 304366327 118142560 498983748 957275725 188286974 211274561 917832076 793871675 468622863 95046750 950393971 943189573 698172009 645854823 5895572 390200074 158500877 981337597 647863861 6410304 567891664 308236108 125864847 947423656 297192015 576632250 833747733 112181362 42856282 837869322 465462474 540546539 95370159 741871547 7963392 953222533 721763118 218619898 720256805 396450274 191605304 748301162 68877791 751004597 99440212 517579646 133317289 533524500 23640814 683558752 314206502 511717228 302686445 559307913 469224761 333365659 568298134 966196648 174520051 902610212 482054393 101429442 149818612 647357076 118964913 811148797 52122382 649036298 907572748 54886834 90028460 959611994 165348937 51343169 963741031 658798240 553964633 553796408 450675976 313728093 64555909 210440421 166234869 711507045 654453126 929629937 601390848 939209543 627977916 265851544 266601618 19116974 48271845 535835610 271658799 863504180 478099999 12054831 704246190 862615776 87878889 357520239 318960304 373092472 126211889 24087070 323819654 956931308 604861753 258919234 115057596 708071197 61810652 753933878 560799838 573657407 612159332 523775853 796375041 834902226 149347142 839670569 315153231 77301989 243452652 415510654 780519102 108973439 269106079 871196966 47558494 614819196 812688905 271125314 525832893 756180963 796805568 935817125 530732420 575601776 414269368 442517638 589507196 217109816 755212950 543113033 877457583 351810144 966964102 490012921 98968462 710330629 555721588 249835437 850269196 376644651 380512258 172898177 695933557 780203125 33824714 528960740 891602859 872788303 152846153 585794484 529249498 718185171 142076001 688292290 490920437 881255200 460345740 997284465 18221519 481228053 325104179 494790414 735925530 670886844 235750138 135461602 662801794 732592860 117181007 677302389 868829598 289614873 231468599 59945686 295106166 839450818 265511014 16755496 995268477 720727802 414334017 210598556 585974549 96454550 73943784 927919600 645545446 560952012 856547123 744844170 703921850 734241219 284573466 215292712 632614448 109606859 482951942 224209475 56349926 777085896 880810452 895944387 762769070 35260586 577233415 463934645 975983008 232208104 47250616 88469286 845337405 593499561 430675226 335333780 326676827 728997560 257652650 728053718 535969038 809307574 974448815 839700958 407388653 964873155 822926236 727651043 815847949 380346963 645733457 670752286 140305960 123601251 447219380 143704362 720998075 319082140 177477855 864404339 351933046 881658764 55887037 797522295 6427161 126455102 663823409 947896053 490526220 282620707 146872941 373278690 658315462 317932250 447955975 599710388 810001921 571157618 969739416 312704262 158448566 737883143 146582665 963256499 742937864 446799905 422256895 619161822 707626276 766728242 569882194 95905289 880255470 706976779 683843889 342767379 558719860 564123624 78878164 704070145 541258692 601706392 179637057 951033840 603234415 322070960 439431880 543560160 183534542 189545263 119172384 144307533 707687519 5387228 894594692 859328882 758574893 355471846 537167311 407776244 252857737 571546857 806654946 763023264 871738281 586853754 948293804 355712774 487644316 835240573 832538118 637014986 131058150 758843410 852881014 640769476 336550814 622762448 797543920 71354554 317451951 443256471 754638215 305651727 930203051 866506849 112982210 325202767 725412051 245758058 317593032 827444640 230614629 280627576 690770799 563169341 541296386 347189342 693882682 280375743 7962717 107912113 614862429 658062381 241684377 79749538 863104520 60875372 152367564 747791551 483186883 463423436 612343738 505612182 182884208 276161446 719703763 899219893 667632396 347853536 644475645 56212452 870886842 215935738 226560898 500508847 296718101 186421850 331461515 937284087 206220014 298927106 943365826 484777865 512157973 802046743 837466050 746479463 105938477 825521652 457743182 230402484 190204082 188809353 996705441 388299514 157546403 829373610 162157895 330294635 167886382 907115840 486023821 826914619 564453172 455526578 346930807 604586947 73106784 368726006 341352226 606282610 585834620 436630011 280647604 775056111 519934150 189293557 983132784 61788661 251871305 779855694 330297718 701226381 528651928 787386304 337564215 909905956 703364484 218811522 742034310 336753046 674159184 649331024 607248945 150507586 354918407 258138567 280440168 860682991 125710104 920517662 747402909 268647434 310051158 100266181 674345085 439248234 565682502 94788797 638696617 228095087 912406454 972325676 969415570 5139269 964611221 891797140 393406113 337064230 34641201 180559067 228021218 566568751 422068569 507366332 612488206 753532369 531595854 823903568 740126346 799033326 604778588 391623215 830160273 888851767 360485150 985446909 300009533 698597389 202892182 758707507 987364375 320436018 653607936 104799837 471994136 260074911 56713970 389914117 698014906 48690022 622713022 612965178 168101489 46397082 821077815 381767185 879303964 703526094 84527491 193747135 294395396 733870633 614294480 909929590 672796626 739146230 963803333 512741130 663665912 188951702 101652176 836753839 628825983 553554256 176152552 79706145 392215032 915479520 386762317 805925910 511642704 965044360 894387580 693963144 106954939 508879682 615603231 764011278 901992914 314163571 457808157 267589479 939136374 467321004 697397363 379166342 347086484 690922670 63586962 970593593 355139157 180046718 591279281 651448833 924392239 150499375 852848618 379837180 633829197 962993817 816296814 949513544 921336038 591774271 454221013 138988991 976804191 345830048 993488408 738331669 798510443 235976031 352522899 805246243 513944722 658021169 451449750 568858222 14307166 299085261 544412940 737126271 588078137 277483542 509981751 813394001 525712897 347518394 689281302 242669876 311736392 506706712 171261087 238873971 600224931 945542303 135178656 695343180 991308226 205594949 110475391 612318576 343550031 232436808 93550638 140507989 366092750 121748238 891884232 116294209 811689591 746508127 183663015 272003009 902234506 201787926 719486754 475678298 34178045 662854346 932255674 217509374 813925982 665974751 89325812 306186030 302613065 968791495 888727314 355743831 550117867 911080360 871251318 284335527 749232369 93207578 74229124 380117950 551310740 601860744 881395450 408618859 450120308 342887219 947749744 174607394 940326560 497552507 415319194 677744027 850867874 23443571 897981692 998569851 633877378 343161284 910010735 606908068 674285946 82155833 815057915 838272031 185103522 371435530 264960620 201447608 959300662 717660317 777320878 943896528 529529656 680540615 140282073 398599850 334648189 865706201 240178861 883880563 628891642 266496482 58094042 791652930 290971009 265554273 301064708 415721772 40533030 160194068 443166249 931714465 330359673 7637416 497223540 799636099 440355109 585413734 817870646 422929727 709489141 439067510 421072547 224059595 920549745 773565569 621148488 206358657 339221660 674443601 162679313 47704856 528284089 151949171 274956254 263094532 263517964 317447669 312371294 282657725 751485453 201434383 373136452 901831524 33820780 35231 186819582 260222740 124435911 883673384 1321824 323938491 376118796 553126241 414095423 830061431 480441432 430289189 90936856 623044286 688277796 449436265 918864002 130793794 309246998 597170610 636038244 522988791 178427305 415402605 809362290 337872672 457676861 27693850 744352894 65599726 12798511 374118819 957691459 433723839 822449883 217359504 805581339 492881395 453321776 731674503 689489872 799796142 21847080 524735753 458294131 735350404 132638403 925547386 20558657 203209725 638497855 457588021 31980165 519304058 510373045 465592138 739576017 443469898 9642388 936445743 973803712 110010418 543469381 692280400 350918248 376411050 608427225 370664609 235122786 386668156 29296901 900830985 771200076 29695339 792527714 174629031 31613855 633110136 468827277 110008463 327149485 160242410 786283299 245299871 662209361 17546003 674215040 572294054 965333672 505923165 461964200 43895671 114718711 717002769 771490541 810916406 395466920 576246238 846330718 736382404 671261282 857538069 813487206 91018256 712659079 219896907 66840104 808905710 303232695 995273338 239320463 671623353 335821546 848446410 868137561 641061836 939848077 522030509 990510792 63012497 315366070 425217820 4034738 433550904 811668970 233656641 88530546 784183894 391475097 518689971 135418585 593732531 221316243 705317078 358521009 884973651 977676476 894562806 590725959 575088278 404851540 507805475 647680866 347017303 526935867 532336043 974287908 44772665 58418150 765319560 10207061 968503470 504998714 562940599 715298916 954468500 342499411 381836833 444088137 674568267 786783823 659716511 815651929 913611816 527413628 231399953 327047309 16966258 800684629 823821586 737569693 371319008 821192201 462331334 699115827 390009773 293717307 766039127 762322320 2847831 308908448 333149107 696483037 233534476 70073239 688324748 618220339 72088559 313725890 535379248 340578122 365982272 536172030 701180358 445995692 474948124 225224985 32525069 399320875 510309300 218483312 456159534 685347422 312053193 10168938 707239629 849148381 749127138 327455046 618637318 134688018 519176942 701525143 775874317 137244909 816427461 119778224 816477127 338557522 25981562 959988885 738440469 515523935 282213454 961263333 567691768 752937634 663577672 123723226 904806464 805482541 887894139 454174628 478877927 696598872 876994935 174882882 715044416 433236224 638646009 98748271 886198130 124030978 90421063 27926147 519298040 870918498 143531221 108175217 221345283 3989855 280097080 713584581 737721431 450294312 724159188 347488495 8011038 367589910 715325235 128447287 423390437 699614473 631790454 417720228 682327378 355587317 53793771 531095527 566782981 128833516 867151168 920592695 881263333 22547118 896581834 550876850 743203100 989535060 257256423 98424259 984122285 282773522 82361425 271840671 992089997 881558893 467597753 656481492 814362630 578582132 971485363 990246627 707859064 736566800 815896334 704090177 846590997 562480931 697465829 809010499 705299999 803568242 67545273 361768007 818409285 342328515 479058240 578885135 927936890 433667507 531882921 264992117 818358061 650308622 574653461 655616121 597224661 687940234 783242445 944997859 887512452 735123527 671895123 15167502 322771711 978059737 223004240 903379503 526716124 663419281 79938113 163220360 359510167 279072447 718545258 626970696 35736740 770257630 66501102 681821105 288806506 496351843 655470121 205724752 970315689 230086729 688124181 500230173 70939994 484410959 437428289 318833806 69751054 284924544 261757423 396258685 517202723 276791851 334724757 719814979 866013843 23392942 857633271 412561861 983976023 346174709 355158376 62630499 603405293 180428354 675324758 860282282 416799526 993531217 990353451 445806856 762337452 789364341 939981051 133564048 826367813 244234960 744788380 381238387 639512368 750571463 78801256 327589225 862391977 890910586 829129001 189814268 784230430 760957513 987696208 877484440 389723744 314828729 108599758 463820432 668979075 359522956 688043168 438471097 130135671 254448701 582052517 175609101 128379420 988061978 183940150 256928873 795227183 141278285 176333401 877713880 98635565 161022963 114155198 974120385 611828729 10562500 239004092 406337294 633050157 399024168 906557728 330159878 901157887 773206065 747651222 377194051 997966363 394106238 2145592 855069406 270713660 277369231 195117491 219350564 956783229 665548207 157185748 350179178 985379470 804619607 123757296 257998862 969306881 978782960 601595007 479438179 962467536 436370952 490033672 187164765 785430666 887751891 816255069 471945626 999182089 426855042 796240964 388969369 274495595 541713883 826918193 963582812 294916942 481839166 478581563 867074963 383912135 742400005 211438290 332444062 876333710 177010733 676233445 443221668 157446435 507229356 51761221 979926672 521629319 40134573 23069280 140718697 478794283 130451581 421193858 810702212 182734299 232914988 708527122 3169009 44139533 413940865 651030314 329266260 499953963 93533082 143171613 412621499 704497791 878228801 388484755 291170598 125588540 788859811 77616519 198266566 445380307 840578885 738801038 4536890 493070439 842406807 749156698 607738977 684262333 838367296 184536342 965790136 309276293 968424802 869297889 143233524 733056486 344362620 905484885 243457911 535326138 787328346 537638899 776548304 907191554 159651327 243141929 297267292 965778834 567255852 963231508 674865173 689086990 351923724 322356017 344325906 867342475 510185725 168804157 954493937 744741622 500731114 480485022 627754741 439979265 729134931 686902298 289730928 906157411 512802874 895133605 281557902 645667326 505108513 661757883 29308882 33839432 60156898 723412592 691758176 348534863 109871435 150824126 86175042 90058411 454011551 406566901 269976299 3894533 927974072 139641375 984125483 974922671 875662385 703294778 103854178 346783201 417502970 841523093 605219518 510341520 473681452 626713923 191624690 526722355 972284265 148338267 293829004 579468612 174234036 500561052 199379616 436805631 872427746 161397679 503422650 40308149 509554097 665564599 986760758 557325226 448354001 941719734 687699680 195638862 874792297 164827647 491315685 215694469 710205860 203807864 341135278 202550404 791708043 973689593 60209847 892489254 81498572 581353293 838561669 472902526 379095037 340891568 191589377 355738871 465620662 573092394 237849880 382299831 756133794 494642483 663612893 615198141 895738685 778349027 352354559 285566543 426028221 757272532 840238067 337058300 724096559 426169406 13850816 376301195 348369273 242489286 386532799 788166484 225606825 15957388 746648223 364171962 763401724 614639293 440106331 281089681 650166465 89002284 435274945 678132368 804434526 168794494 944600056 665609085 128228024 675060157 755597148 993588415 61782915 170011079 223699087 469031132 373294249 288346388 317931408 630976629 893067818 121919774 345450350 521704680 449723130 14700332 67405958 227061904 554229748 721964048 355402601 908976235 430435702 760411457 996096747 580601611 819659429 210312575 626351869 525412414 317991723 499079591 790349863 610551222 49515628 440897621 730077896 343634929 267017430 269370148 63150619 472497191 827796948 539380261 396909715 755986128 528287098 390355940 730023389 675262582 64358511 876015588 681262665 891122853 715931181 925074899 790777830 892038295 512775466 115758452 921343452 21971022 730877412 83545952 395777379 938685921 252320610 435031652 891313817 293340282 325146363 368415685 417316040 776568763 233448784 746091156 404995152 802337483 972942851 153709652 533507314 240440105 730270797 930860589 765190748 924283355 230703239 89441169 9629483 691527397 882497039 83496451 780782078 316893890 105514251 401604413 254828318 211413497 918151739 54169649 703523145 689303725 962071299 351194742 502929945 853026648 542357915 190090324 483822433 465622684 603713390 740806220 801918549 465441162 793862930 155045822 313620216 626551730 58751537 629262099 602825273 669636183 969742672 695173230 759872190 141102907 160042693 220832502 551881088 498851905 869719871 440471874 830714988 912951238 496909858 448944431 97709940 830949775 498789748 401876343 920833342 954964193 851285010 454392769 219972893 382795457 904277881 556935439 898429980 490191721 314203897 661152080 550523566 579170376 203675189 612272308 258187148 530542601 905754859 444515194 194352587 288882801 510096726 445107929 726690378 691116889 18092253 513059632 196616469 630999312 29856038 396430868 755582839 735946188 32786036 318547365 465793431 348398745 690192847 200005158 941620124 519930113 429082378 759132797 158735641 630039885 721056304 828206063 251432678 986810072 877845180 458926630 193769864 128518370 610964219 958925833 518850124 881666246 967480191 110702663 881854248 359318592 220622653 103421076 932961490 571117755 290780630 197844222 116300323 266845740 577351234 454407967 289047315 483087320 462072128 728512408 511354870 667155728 4916882 888141084 245314394 404653704 728975020 738644612 60131165 939921434 907035215 664159726 305125446 163306151 148539710 342325059 959383491 208620563 828795502 574956137 771833949 312889331 53407407 602926274 923147290 978909494 369277345 910250459 485494414 245916514 156942279 274142155 271019057 488199082 110700690 821374782 362427224 346171366 531834909 439959516 362884289 654691189 382385991 189692914 121313909 285961671 177103803 167003258 799126404 215080370 392045276 568048567 97582860 214418682 504435833 287599036 970588590 775863847 666298496 521115098 503254080 376294142 223586670 119436123 201890325 354555520 283550350 703449815 708683686 350957500 555634611 894173116 886581792 647944434 352755825 880640745 851781528 365353825 272949988 787186336 511746390 873097729 743746566 872247104 401633890 264726752 548576856 625572693 427555847 311341258 150203148 337453961 348567747 549436258 656505974 640101343 118275927 42449583 67727777 321614979 51831071 457300819 399336502 295825179 905711358 716858390 201149666 456680851 536374308 858591479 249129338 996395103 674074748 689036966 577361261 401882392 36488991 462428727 471488762 692828980 210385624 153835570 121506338 142017755 744263339 921482875 885867290 288771443 439064243 25143997 412287661 898349244 578704160 698364414 642590411 834956741 67346141 481042871 83982534 167918905 556075243 550187103 292896174 814652501 696734810 69707248 214416990 314843568 259350036 33536190 91325718 243082910 400007776 166797879 640423382 575142221 570195857 279948176 308728988 15691563 539435523 541403185 287007872 498442968 127197806 664431587 125359311 560374378 666838194 816618658 148826773 461547018 888204280 962597148 851052801 836034857 763903453 510546528 441261715 9869106 646041354 986826128 422996271 548277164 778909340 325411026 409314363 545672321 80222353 756338148 905568933 876936124 835851436 494930168 481495127 111083668 384765400 599980644 616877080 868719242 823982925 456735760 715993691 950920736 907078769 638375365 380543305 804386149 600525580 765575721 943279859 388767318 367611559 622962556 252846515 826725236 949530299 370502135 819036025 474568002 101750004 105297947 810002906 205056030 796036770 952029705 32199924 89669469 567642198 364478033 158834424 229139622 163598806 897523209 844042184 206481618 380798182 31091302 722253987 442018157 919968443 764720400 523593422 648797982 520217297 463145241 669476700 968206109 752651399 212245295 368380947 162559866 552194597 196045271 857110793 325590585 817184298 709878021 698804758 433925710 747191 598625291 387096344 337199656 509224094 41095283 805038983 94403246 23268030 847191511 991781828 787080735 625224135 585119876 630595895 683462387 572116122 249129920 73645349 941686807 322605298 914498948 35567337 761303209 737680092 908475905 651762685 314458406 527459097 423285194 332933325 321602564 156056370 604120064 782055234 194857276 505479261 813005158 667020487 218437684 70531781 576336244 778972666 788215993 2468128 850079079 251092826 668820397 843710633 48322828 346616406 921048750 549342463 55800009 824133572 14178725 696294486 242407584 455457419 242822542 363413202 258643995 101811906 494761597 358181671 342166896 529996985 978650172 750958646 930133394 303472058 979385305 737493104 810557628 655976799 431871727 267951348 868204355 644809059 372078177 157558844 521255796 965026192 381851245 959024677 735057545 117162801 550121224 505317206 161771291 146555997 735339621 169233385 640829288 474992694 944035196 626670374 191178571 676876278 576956460 537986948 107733868 288455731 33885831 737488434 238177174 414880687 694265333 864423283 795275942 17342969 158026289 890973777 184608181 716146690 956408588 792187651 329756529 327635463 626293926 11043662 740278627 569248680 7424588 519849572 311573875 612529240 155130423 8599657 677095284 97067403 697488158 701795538 855364244 463933970 610314928 187726843 684573795 849441247 293003961 862198923 425095645 76659423 393253121 897048077 136441821 601809999 75524967 313664067 178966724 739790473 840759887 902270523 474266888 249542451 19484074 766571176 692299747 686681671 432090213 19193019 620115702 122123514 500500761 962568618 916074110 57770597 34203976 413972395 68807141 800965829 98693810 506207294 226023751 355268184 726662621 584874806 136739978 279191763 565493260 106169260 178701444 603910107 179648593 565611664 196318175 563642883 317805773 895058824 101439654 114955336 41605263 909512082 801242698 719742648 165852702 944993114 36213612 528575500 750111789 597730142 303910393 138105032 890611514 817034237 711947786 333362638 829417454 635238749 347952785 789662195 819645503 327260816 879632116 356474146 880535848 691342428 594570035 50456772 143563691 948447615 35266645 471500444 671497325 828970583 323556213 832008165 754282051 510805134 91336712 439145976 339364947 205214091 901890424 206877090 256194393 541507753 138712638 259120802 727306853 220627153 521189055 760912672 394602080 600059573 174050799 304027246 864888003 41716991 50226978 929474493 328712345 619112781 690819127 327019613 459667970 888313614 887833504 554475058 136067064 538672286 766967283 945339027 630258607 395762645 394422499 547559215 732535806 52419277 818734999 269978225 348644483 778173358 390199274 767700686 383928601 349714822 343635082 342547446 146008887 937779270 548242449 59028186 679696883 13378756 935582985 515602559 444272691 571631699 352133908 21211943 502914289 618585392 174952906 86793153 275479458 420482706 656382751 499173793 602990359 432596917 45371740 462134229 996727021 561818641 838110178 614700447 232207482 91985765 506389727 755628466 224231326 828297274 492802941 870047496 139313692 215880243 56946381 368280915 69827307 349904708 590859949 25770524 952462732 493441193 591858332 920104425 293554777 950007993 645602322 523270444 808375627 517827433 396233665 901012014 513854054 589006860 867741967 738520909 37464210 352871700 881163497 209348671 438813620 648760907 198717862 950405744 543704461 982109992 410557791 325803746 589811193 214546070 592615706 649351045 679835551 592964388 448291410 928936401 562513103 691054443 278998523 611439587 435613004 738477307 507573470 87526921 329984575 836197569 232203612 696510276 660945301 270396618 207644299 812990929 764355281 925277282 700640854 335765825 556465828 870266981 998049504 402779310 495023064 600370585 796577647 721936323 993444378 567379901 373793636 911374364 747714652 746297027 120691464 420578778 619015270 58103320 219919151 511382377 855653718 596790877 883675051 561351036 569258147 516668542 113537868 381149985 20155096 778839764 905013252 280949681 337669061 827129770 368805365 938402603 398163395 229532429 801601471 488176241 604214239 517507477 308246164 349073942 800955758 260067574 540488278 399459979 323286099 244907130 499587235 939646400 10055796 409430113 680901170 331668165 114359930 499670139 979865600 719141733 600654942 545223509 861809297 107207296 505330492 60665646 73291436 75009257 924448833 581816177 531951267 551134021 430358634 223094522 11340059 92976219 360917978 709846229 157724360 386544820 928359482 772337321 669421012 224302392 229353883 842969998 252694379 658808473 969995312 821412007 721330435 528017648 821195724 109647875 693567900 894722360 538281807 726976076 931592541 130578000 866136211 548275071 910492519 642912701 50685777 600763707 504975742 527397512 201828504 773525100 878606651 875842963 994821042 347691440 344732851 903177008 374681337 419881181 934163245 661133063 125922980 289748430 199585121 539171682 895062908 819196203 212580391 404383972 641048929 229810785 788541485 177909914 1949446 7230752 690978245 505004394 9954045 445572046 915314428 199840652 785982121 637817780 496352368 140144845 138945222 592757126 442003969 317650591 642412233 14316860 402002809 590516019 411489769 566526916 634318413 824808734 162404680 465028813 922143312 623354101 539850631 739462335 320835649 148975985 382943610 218557641 242236169 719368449 384470767 147753376 382816116 387559624 697002038 606817075 608938322 856472868 984708291 416420926 99651358 496539111 823859032 377313951 672695435 93148115 507311912 302068780 539709201 896737175 755097809 154864985 818065801 960654967 522831846 596297857 454986118 101933846 101605261 699665620 386302078 729451494 123021405 97568858 68907378 901648017 872286941 103159329 195253885 565653443 801228911 638936069 422913982 764318117 981263474 902997809 14269159 598688892 216723445 356354097 350827082 546236361 856018200 429655687 519459651 966641558 393417916 39684441 603357020 884165187 135825884 478251955 221455344 337704752 477975522 857442305 684199097 357587117 582688318 928690731 622498515 782857601 613123408 486854825 344157757 76078116 337159365 463164309 735498677 451970881 776674428 552913679 717463277 470425650 516441849 800489368 301766087 229360291 148891348 926689104 758937420 537083987 861668585 771603551 887812931 874147749 206396465 593695285 714544167 567832012 681311801 254471470 90593523 895087127 319445121 692373907 684766164 811702811 524984518 34362720 774496862 116548835 617555500 161214118 761426273 577725680 580760954 227212743 521702982 933461559 923734030 925763606 20856587 855539174 822764955 822859412 621334224 311201594 65445729 574037778 424684124 708816270 896324936 488530660 840208363 788868610 487120019 529566496 904718534 916546106 448894030 450254390 340987186 878873097 524946039 608191928 986174877 143541564 221326070 65166505 469397344 216987404 545456020 994027424 475406566 533481637 438230159 24699519 930774529 589835679 150972551 53260956 733564489 583487170 676771970 617725838 488588486 247309595 612067861 329698133 40835007 356117569 806486749 836727565 350671820 1329911 691559937 663444112 366916099 432612702 304465175 839224556 557541419 9446359 900070510 995344554 230994511 643179278 4007300 253385651 761672047 113535359 422410377 626126225 387057559 429717866 148841325 500855714 677656957 422258129 757035607 599819266 215804820 680588967 282943848 158142180 460035027 42558790 450857981 875180843 640481784 392494291 371430834 588864885 902915048 379267874 508613707 777146046 882546625 736419681 609270462 324205467 465170229 717795635 348159096 817666909 147800851 991423132 359567708 496310445 866254687 209981277 933668145 292450701 411692186 14935952 881080147 62640108 824827686 347772312 897873963 552698743 440375917 404841351 168767269 819090898 188992279 149804969 671995569 789598636 64462193 723438370 274694475 864573081 746663615 416094531 564017682 930109483 797752267 518062790 296539786 600677735 876254696 628935537 426861996 844852283 277035142 874192482 46854384 128720482 983256927 423288113 993119551 494015669 384386664 265856311 40691483 690291060 259229829 431780159 533308448 475030674 676605641 977778256 203021812 980251005 574868937 246460970 109217895 708412094 77138822 790054198 849670436 632475778 111803685 320945358 323458327 892689771 219016103 305001826 954504545 265369093 454884659 618584894 440472091 447591444 833094201 678397203 54558882 215633638 723755897 393178162 176424646 207664805 844544179 560823095 437598570 841901762 372848816 222362078 814982416 409544246 328813492 615711468 772927294 416199710 132611759 279264973 689718371 124408820 270641231 943403142 908408070 184931964 226748960 840865745 87530522 20103398 683967368 307425208 775424449 745996052 946293830 677756905 616820876 328572663 683428724 59983690 494868519 446278532 912355267 42714137 287274282 985523468 117647780 734971353 394219096 70697120 228369330 851489368 660034931 968808199 744895471 219618045 159506182 565811455 716886582 675544073 985406664 322929702 716885666 468546407 766166499 35383755 939308710 557544768 398827882 172932892 556249560 833217241 377024402 110566733 950770684 124228466 466468325 761887287 967203846 242296629 929237421 461826049 272484488 102989390 601724537 188553673 60208332 489993159 219734734 751393384 24763121 66899954 425335546 278971422 418852181 426900354 617325056 268282733 807830023 624953558 508376365 523517607 121042564 876753355 763025584 537212661 299788855 765070572 924029309 367412886 15781997 612887601 22943970 106008684 700697716 399059633 413489081 392870818 854971314 541090372 736209477 551236477 550288587 829373445 213598331 518493272 311952197 894099697 44582984 988919415 316319581 932544348 167228338 863161676 995334086 504672973 286291997 521953400 864276946 515119210 352634287 843973852 184579327 966219376 105433808 665952874 106331448 619031503 282820289 598382682 570483762 185520753 500409610 351583819 136442538 232086909 157068989 215882058 773280062 429942482 16032173 811462006 325462657 247895228 617952326 401260715 145589606 233333109 859683291 653525561 710023390 467055854 302238762 877321310 378630752 916127314 458646147 31391577 410856531 764858762 424382052 993621212 978623950 40602682 816907458 460954901 875565713 822317006 639464474 732931970 875705515 348078947 893027592 387704973 100660477 429359669 656782843 165317228 276403966 928231357 67340580 676929869 887264951 128635839 438726182 361347275 380749400 537235515 142329530 986834238 321480954 729697610 354511524 909643215 990561610 505199037 987237146 524229071 493858097 431401925 763386586 328143844 173923873 217255502 653219016 653817299 893071371 533799709 684895785 502872805 810757787 798830213 895202792 997089553 109877842 702900985 844287411 609598512 970916853 263207104 654015847 446413360 524940309 221101112 485359569 472770629 371898209 804999585 609628958 749591198 525265488 926086665 703284565 448146196 849337021 613735593 148828359 365248605 822437177 441015642 736166542 387055434 338670206 324701935 569649097 911819180 49562043 326671886 114031289 247239241 861850974 551122532 541252912 703873389 346478457 225064070 453813455 525569661 992419273 880413686 943215172 552715745 693675979 799698856 963496172 312305597 23549626 904036071 567516273 783708854 103960888 677558583 104752648 282854747 661523124 118245823 509338485 74207457 550936457 272903754 250667823 764933675 868206320 62320020 427073436 866231414 523014760 81382794 181740361 787480293 397284364 809519056 491883444 996003364 416822463 126689303 819967100 734738661 48638138 809110448 20373309 761901905 146305826 337922855 639678371 342677745 431554357 153486334 54041075 140216152 730942846 669056561 76890118 457878927 246717939 237174850 664956915 774273515 461739440 253024856 16487730 931418674 407682874 456535643 821974764 716377743 59432393 889672010 721824703 317503371 648070306 249939698 45283915 320727669 993819863 557114184 397696306 709265127 715009598 931384868 372979108 309867146 801039246 799247143 969803258 449129329 617405888 102399778 264115817 123221438 244929993 153857177 392390044 972674289 111714552 487953838 639800540 118205681 507562645 314506250 162487075 211693223 314384186 724033222 461289655 922604306 876943795 999017487 725512536 185186001 195204464 19256107 760770181 201189332 818649605 794484932 933398353 600976752 573001062 165942442 211282376 379028176 829799051 675302368 576220908 338022151 723574220 241312289 496093473 567038538 744521361 132226545 722757220 280606185 882357425 914930094 289138427 262045291 427157671 884819095 34759275 990590157 164272030 289491591 733047343 464336817 795698655 637747505 285968070 489638565 435326656 104962151 720052739 648678903 774545682 687248498 843815126 332351098 287896863 188500447 262741657 132935489 308694492 488563996 34458702 230339491 936617634 98165861 349858633 462391875 702969263 861992276 935844198 878905745 443305025 641599238 502225419 617436637 954688102 511727340 182188460 878105595 695708851 6285448 819486411 944042657 91614620 594975465 720002550 313960839 561126552 592382322 944246920 381439525 99477093 93578224 253785522 768112822 971360619 275038386 680498571 843190128 38233933 781859175 139951171 840768329 829906167 125274550 517987566 445326614 961683979 726704169 820528830 489205605 999079952 866576497 831886488 780995894 221597219 530700319 574750078 604994042 919639555 685912517 918515483 255757285 666116048 897421350 789414902 387379236 498608741 679773511 922996795 121551517 551977564 611744621 730812688 886218872 22944172 593695329 240012645 870587781 74262959 364638802 489435754 34725686 458606726 29451718 801978931 388013569 125037186 441649965 33645793 451044030 398573388 331204814 209434254 678989372 602259416 459084589 42747233 287620743 282772877 959015530 165721 490773039 629235261 355440909 43697432 165418312 262893149 967416816 984387887 516291438 101465238 905121347 636573632 880743457 705076198 660046469 602437371 828063189 472856712 589828525 932240490 238402566 543734317 688874150 74112201 287583639 844110406 573554066 22938181 94439511 447178045 930121448 694122546 218018435 635001840 337481551 805486617 114588329 243365871 128617909 968234423 69138334 165789595 518889708 797110145 702443004 868768463 85283827 265071633 767698599 211919992 561187032 564154769 331403473 241585045 631151775 393768708 42391684 5812779 926422835 730709218 180509790 354755813 532699092 710104543 867391058 925918257 573519827 489814981 315295740 898438097 977454577 642852979 927035496 434025310 321636714 723515330 339189416 158152152 316354879 159350244 739676670 451415220 35198941 972171674 292577627 375369275 275121420 166713732 364145606 83666118 79203330 610266027 564315168 576390046 418297702 328644635 758553299 656027893 736400346 522411417 540510346 996903115 893363650 229792203 866889477 882476759 244054887 630042648 259908020 57401514 794417838 563864161 537462092 452828371 756263558 66267706 106615814 158966993 373059814 11583268 583801235 674242255 84147830 306520252 504656282 829436078 429445040 690294823 118122303 809580667 997355651 863124176 962276534 54981756 268793409 72360444 397410120 290978737 796896192 958117109 470819286 570993605 850890970 840837657 44267219 195078691 122817780 203536346 716795459 758658814 992614887 431096102 621465730 666459618 257144097 845492795 599987477 164632622 358612555 665391665 258314905 633108384 332238198 158334280 561461811 886182806 806698745 361715671 663448137 437117521 628116229 439777458 717994022 466692035 627018444 380787222 698367720 692397020 815321733 312298337 274704195 972773769 876259118 907004600 232473904 295853608 63010979 394199099 861974965 680455922 976289026 530885857 879711001 540831374 929714791 77084787 750169628 879147193 224588228 779941007 97213642 5652494 117424029 843873721 706219512 329677950 583671771 86734807 902270770 10212257 27930479 491229204 631562868 586939056 970811722 475101669 945964440 537987827 123822256 949448509 7062739 734531820 951963439 171969809 821321596 898017479 437561561 478028704 77733588 465024371 65453673 739441550 796135316 864798048 835722022 61838201 923888371 411189146 915238627 521174901 773629811 867569168 650338776 594722645 938068135 368583678 679276578 103282340 605319586 544445195 82703500 384025985 94696982 662464340 726936619 654204243 707646887 548912135 112245507 445480796 169625927 546552433 586576678 623243297 107531904 761959007 865870264 478499575 310702333 369465655 75737012 484249421 981600439 618663273 292318571 738039481 458400200 346317592 690025807 794111486 980286660 378747419 896644204 741251947 147533310 556546855 255275924 337592522 888254311 955103259 747223081 500482091 78291576 869397462 55324651 765462714 860329566 412608269 854309705 676771049 481749511 104972345 642491669 392243988 467411420 10661508 372068147 925580986 395391358 814652427 759867539 613671361 345582266 979516953 206550847 443237434 144908632 43878324 453207597 713673232 276916215 411149660 833636490 548962963 68764348 6205371 21470610 657372645 74104524 807203919 37587665 537289666 269086960 568937500 34811794 531470250 545923981 586184081 705751009 464097959 709332406 86568091 545090241 466121868 414005197 150049596 855631660 149170011 740981882 365779585 202831107 948337865 925919264 974239446 599289062 108500202 923137170 150958576 644039854 509864013 640020560 488671945 38499666 956730304 49255389 202051743 480573776 196120557 439800463 949366053 359283664 817062094 531138172 921013973 221487494 261881711 825277047 493841890 146412890 274603568 353940011 673209381 297524962 898869789 980045620 194178646 155721687 174864533 827093112 211202823 292346920 587938056 203772827 982281461 183554518 922782722 289450012 247917685 986661686 863364455 972865869 843106207 686531570 735085867 893336669 346843202 624202128 489768263 439365332 665421385 223737441 633276624 438250226 719728457 170178801 64243993 327797750 320833808 655426227 411917523 237389085 988464161 162133512 754452189 474826268 138780791 862517730 613341257 944372640 396499090 298108805 910874487 307583319 937878810 621867271 277165350 205146619 467419494 351484496 193908290 515253538 821146070 550322268 232693250 432484942 296527027 950931776 9045115 439876467 128821793 47568585 531926391 751818646 848250267 803583008 14871751 84103529 190622394 321373553 248611822 72292233 420541896 229121316 339968217 536751310 898843202 8989385 129673650 320492214 196509406 175612493 868048783 601968674 56277904 40067650 892853020 249803369 204901021 961034355 445057386 285103258 616195892 605446766 775658850 725470909 508787020 399341433 999513020 263819063 952901722 19282405 917362872 960452414 152576594 88334911 624927917 38423293 404096211 546361692 71451078 970384804 622232066 613542260 649949280 941379036 966044459 162420089 384960028 908348370 911424382 87842570 360553360 939484607 878912030 716178832 248409120 396700483 138319139 406243142 469462041 968858025 569097640 854519075 666061607 501909239 985732482 394493126 500196425 792574991 31816363 208296076 296128680 469047784 434934271 516888557 768244593 388789473 159243576 484444288 351495209 581987774 82117206 958209906 471690052 99245827 285569085 493598188 671966862 675245826 760109867 579883050 735598978 173077068 332168441 440544079 218025600 373254664 395425318 608573115 7218021 889159385 288548938 351426897 411922523 64617056 267061623 366157731 130500282 557784978 235785954 631462308 231874219 465913956 476583278 645274382 286419495 285627697 452991828 512890540 228863309 509763820 431254715 991048647 906086202 310908563 912730144 45715600 28111407 721202185 291059978 416061306 501853962 985125397 501567817 953911988 430667342 175968961 553186932 157829580 231731953 907169972 290392153 608834916 882955499 429894814 927650223 557045926 136569158 391263906 735112404 246886932 832107997 168228677 496001685 542840847 831260459 633082809 806358431 4505049 532610547 162358933 852904008 948488252 890883412 815264250 278045326 2152449 883009403 999896946 454705349 480874541 99414009 970833311 78090900 816315345 436848539 574907354 629374220 389958381 622632153 627349525 385510180 57732920 581152389 712949057 923618194 839798108 311249984 56979184 482598935 534834560 499353991 631512930 522044681 974250799 281710414 924572032 913847524 242956889 920895680 264246340 841127094 169799607 328738976 672117997 925174972 748728246 557161915 168044216 174067594 384611227 635856469 510653323 120083454 726135866 947891743 48652241 380092535 350283479 970578341 77964994 105161802 922938533 620898548 66058453 617878780 382883009 456880473 189216665 311363117 872904337 20674490 565264207 816679108 210455155 240408508 901247318 991933042 212272851 408517584 135752009 260929552 240846863 151377756 646842220 365764638 607457651 474496904 450784705 984736865 394707981 722332707 839627858 238256481 131098478 384212281 801066990 60722667 850904411 858554860 225234774 891992530 967160022 741555425 805417307 83977376 436434012 511790460 477917189 785022316 793690758 961554818 350458942 135227313 304791674 624824222 698976583 718511511 317123249 428355651 503863698 335206787 354153550 909208982 321605427 21965084 946072945 116636407 126695595 817881797 105803499 226020748 473105737 931030807 794653676 380187098 218487058 53788703 758990526 30971825 338677351 874580627 968507013 990337062 589279347 414889561 511753314 52087172 447349767 6396455 449812113 534629470 43447052 965472594 869408913 813485485 184979273 155398558 83917401 226991561 391206649 648448797 132408604 590638845 298262262 602247343 633706009 304175271 890289896 57604700 232506556 943214909 152900525 667599873 611914810 191325283 280439802 934694461 407164161 656543172 843792694 248736433 491501435 241932953 540667554 750571562 99628664 722193334 166660931 694393562 986687740 685853068 906944904 891152881 520887992 827534979 995174560 215789627 17537649 163329577 80498883 674610236 144782272 901414842 583543061 854189838 907844967 709778788 745276099 792441484 102630986 712720583 197377701 145789478 858797908 630354370 497094252 944763984 130211613 806378100 729105889 777668475 913192166 701209147 545463868 295761314 860942715 753661085 648161279 676542050 770201807 844659887 113989663 818753939 141056065 633013908 480315389 644258573 893206889 857496832 910897044 567328751 337681975 488216778 595553147 650279954 379026730 74858546 36247124 317796455 423535902 313883916 674551023 228459462 888426585 42856953 842871270 375341243 418172965 352699999 231531618 715464820 918061998 328009823 490701881 391091445 327962391 901051559 949904510 114680074 356120350 970256353 743089956 486410930 556756074 459932976 575699966 133151071 194705972 80920496 244008524 83252904 695008756 655029135 672135738 113631311 906100431 447001548 266214896 174927458 120136783 103981431 211891770 739496918 496260243 423606648 667682528 448617157 96894330 309512177 898308071 288152127 716883961 24389334 344873593 517019331 573229819 486144258 591083153 792446193 937739218 93167544 792283850 563452344 189328303 250039898 473681126 694798571 113539761 794274304 389534074 597491234 567639473 694173294 196643284 153080668 905081794 797307954 738356789 320992341 576028826 303286231 225714737 521261232 31637209 782272947 41371582 859877716 493757821 480461747 726683139 386218547 711972317 277086799 68224754 583807721 530630490 795730334 114875151 538082997 732587481 407077078 64309835 775801559 393744735 968816091 143720167 475505524 641413870 947172904 75362188 807809945 282442501 602487462 995351016 22173840 950780870 471525050 111751997 803471694 302553297 833953943 632395294 82688808 617914878 126264276 3968834 252261355 990402797 653388352 541878099 964224458 615590240 468761858 708766195 780037500 203434898 625585220 652891797 790852378 571280563 136739337 486353044 603404472 27539907 563846875 685567527 186508551 73090923 640895805 953728114 345977302 356643940 679704299 933008117 411196559 164990124 267216958 101438794 385847552 599331281 965998403 76063277 400609656 728309880 537459708 946675228 58381004 789909354 493037595 580272556 146913911 439137887 836515933 399129259 747763273 544640880 468318143 9942441 353821092 302866999 378825875 505480728 912415014 486319695 985999824 723580804 898217618 992625627 952580512 207853354 96894120 995021226 948255628 341361218 443229005 526828421 991589864 862071116 519079625 108570644 584620369 195746303 660663754 852714109 414993769 899990950 938203615 551343788 960166602 294236636 279634860 292692541 632555494 971369463 367259575 480367107 812564791 458153448 982577137 563723352 839593285 491235942 51387986 887221322 330505986 411747708 194100628 448922278 504487 122988010 425546758 752829985 484012168 775910318 308540096 504991876 519842207 307878491 703986200 446340997 144808728 53757170 694281290 340360200 736084627 827966875 95567330 586233562 894310922 359255327 884114854 985661031 919314265 195624247 223692739 258493676 762890449 913449671 366592201 478528086 50962315 55757324 640477747 74878655 706003380 628446437 393105926 616584490 340158455 994642247 984457241 891814542 420751314 126369291 712423200 340898652 457603671 291845711 250410426 38476269 765319606 277648860 114972559 281453456 169087487 989023294 728430080 3858517 205670392 616942955 144909126 174023579 173875942 364149906 549913707 74715935 585468559 955665970 13903203 319940658 394796988 694965429 970151420 231921622 642967407 248639985 481807426 910859975 922316637 871046660 690218485 126683035 433840269 798579985 86768610 622908969 451976512 580253611 616098209 507013279 259847317 372642487 646846905 882852261 896015412 348353121 553868415 41060209 825874660 899199629 356281496 730843668 750311385 686174891 966613232 303062117 245279245 423229919 780717822 173970735 524532864 434301864 777314114 832868794 535775784 169073436 281696121 673706843 858236338 924782872 7191787 971573730 256359230 587568492 168127508 727425204 533877118 328642414 889218452 563751747 337179918 814568945 112705384 103667789 809211772 120505132 641682860 654060471 144865974 624904274 16746153 734256156 973532159 456621123 393434107 781933929 320908663 920161658 105584168 548949631 146970993 379807305 198095975 681795469 87223644 943659881 535892333 713950984 858083231 148965963 341293403 307361102 854542819 33678754 616722369 48330001 822477098 610659772 231958541 452520510 370270634 798060090 919144396 76131602 142062759 998001119 142088280 232993761 856340409 730599773 208326893 29727344 800794865 307954232 588937660 913913213 703636317 50558965 322678923 753130255 235913835 998697889 383121914 566804742 415465724 572206321 881526822 651324297 269511591 369500877 470409644 431550245 588431200 79362860 668580787 771639060 259273364 857582336 296956060 128913759 86353232 672785694 67987857 472994735 310413411 557944221 653655710 569186403 388791737 944854493 285399345 145888960 839505915 821182408 700295967 820365897 763146311 789342569 965233105 42935987 59899803 538320441 474394597 162601552 610721405 466229615 55205153 592467159 262200162 618077896 846570390 809509532 567715539 14343836 106046761 740552657 682393697 778820457 301243616 923244917 903418252 165489733 448328796 745445207 63242064 799170801 495076430 647134358 437931875 669952348 228909790 44356501 701270763 620651973 631404245 447677309 821994779 44049893 678112960 280087638 946251513 952278041 375262751 535771690 779228780 248679087 277821632 422829122 957518539 810208074 423217456 532170468 478280362 555049727 939086770 736892315 399873777 205347253 176075148 819137942 511740947 617121572 438795053 672166472 67883728 205783130 151953505 115962546 269574397 74692731 500985466 378839892 645395687 835696213 362712408 278306836 890261832 722945054 490570862 588417212 273557886 882196942 788348635 662048750 277963157 506161660 351244114 561485932 314632779 112172422 428268759 121477441 863406414 997294539 232717253 558795542 185508361 690267796 896110664 756762867 950318065 552915831 962428933 997048371 273591868 320864841 32706538 376187135 726530735 155184159 423633145 930132267 871618658 172382678 631807302 203260681 167817190 81820131 44461766 996590375 238029685 123707698 944026200 212244441 25868169 861175973 58087036 145513239 799922914 405804638 378371342 122592757 448743285 388124473 617827995 147298382 171387918 68217311 134822713 526802993 292145679 221974624 86995176 185003852 713373772 657406528 79107641 760363823 890969717 212073252 654995974 273198037 560287031 242056457 237711912 790617374 727296978 210839444 276408182 923717797 201398550 165735186 687624279 915476928 478603993 16689946 788202206 354312912 284459664 929114057 131116216 697122819 117029454 262624969 577305743 656365374 793730791 592799052 31920534 493422115 601611907 655365618 589529604 680329295 457925409 689644930 124655670 252279873 366299886 117729216 496686977 123553441 38400588 339575327 168322920 915886586 562617859 853888639 349635834 341710039 739546387 700075549 865023299 511685892 34595954 369121403 913509385 806332802 14630726 216338684 515143554 949826416 892181524 781232887 682330670 338594176 379391027 297084974 813624457 653964900 507255609 90827484 243806896 205889195 560981844 623730701 73647914 252544074 202634555 670582040 534468808 941747518 448516056 888490560 628545445 613290495 665484363 790496732 705583747 457793341 702371328 859587210 749918733 242616602 768371460 91498130 756890844 374722545 410225954 814138128 944546628 975517122 62585893 719980368 173115980 133899279 399397176 118921396 976944273 78074927 820665297 98413982 885980903 825896799 582765532 153747488 422856062 798118857 281269336 528401549 883000843 345909982 161021402 973770588 696021045 157649333 160566384 647818748 411030801 96631633 120642255 900994809 679848777 409056058 308062189 943656802 779296663 712973938 825737188 965205550 225360981 791349332 827561346 680199213 64311108 712001729 988815350 881406813 328787928 856390797 505301683 989526189 397856138 913561112 89515713 181423722 390789023 135819339 382530253 333893426 209139694 651527653 774771108 827005705 383408844 776480564 430252913 260537406 578910571 281621482 150288245 373253385 711259100 270165058 176941065 635695834 833075209 109650254 702673383 752379664 852243498 255976014 503293433 694506498 721223352 646566528 703634360 967843320 153751483 424609974 798558613 990171703 315074014 187960334 628093811 969229141 479070490 112689717 581125812 164445077 160835281 551849517 617879905 133095585 819461730 422214515 621486990 279545418 263329692 751823856 751470048 852513302 669563103 48014439 474844821 299680123 902925807 425560632 356554214 205921530 876953224 315424388 307570727 539781447 720692947 592693950 102432452 435522798 505129805 13545947 925495292 997443941 638810438 748004180 281712451 826743012 312976126 559943332 387122608 655919821 932160140 992826476 393656621 233290321 490101279 134618785 821049842 26335801 416725243 487815380 29770872 174746436 635198633 91763580 870544974 921474152 578761374 345727841 115896399 977458336 359747112 547215467 359796789 957175126 578048854 96970525 259166226 555347512 655064334 769539938 313254064 952700345 299657610 912210252 664980684 183454680 108754264 613120546 146704033 836299135 258053939 130525705 807067963 883738119 735200918 197133662 366560998 104809791 202088837 515257698 997999032 173785601 614728342 187374924 920417844 595213059 219496163 898566310 187241800 813703496 838824513 52953138 404035847 189791892 488695536 294085792 741149381 893122847 537342203 917586416 769940346 65866220 836535434 855579121 783094987 242472224 297611191 314387277 304216007 428790022 864900848 408486278 57234212 536964750 849609371 823601264 597088972 890792741 752082582 288997221 350525488 918407023 393589948 575108538 948688205 881644701 656104708 224414707 256653868 523192900 652852040 946195309 480475764 220926320 279461704 764871076 849585618 268679040 147211893 300439314 568012304 259885428 121633331 452866482 32162210 744264981 483393801 622148765 417330368 663968736 110659970 869878051 930652900 293338895 191683148 428876169 725828377 108261987 794542906 655203977 153246255 361871425 748149521 873993975 119365378 813017624 277641567 265186693 372731155 847879047 144550777 766423910 465907603 287398133 810819213 918921192 731713380 761094634 677400290 472875825 101646779 518098489 375456095 544032854 896066581 126747459 434762943 875064878 873399721 343251030 177749291 45091356 694110589 33464386 956202398 80649918 473177553 832746730 480947254 404183934 835392203 550570267 737635077 60148407 551314758 576229456 546773677 907204777 416719405 336201864 494454510 167748281 955261526 816113787 164969547 1841306 4418082 273523314 206002915 874087254 381158502 170137479 478623057 540200877 263677107 341031902 743376812 836186965 488864816 677581747 903906466 612481456 417610548 360892238 193487489 615990390 539947655 93564210 259541245 509175876 216544539 578411914 338874348 532794689 756513392 762493585 402614346 925270779 890356618 339370730 852210359 316030120 639129658 338624234 836709562 541778916 982180398 885626580 840344422 163093704 190385383 517321676 11068933 743841133 962151424 498484929 156155799 901618732 536832622 320066099 979580162 254504449 278669067 823413436 775251571 321222081 815426491 745420553 386885008 931509272 761675820 425707802 920926185 434076871 2429202 289095933 498060201 327859686 270479488 572489422 722967467 541087158 397104650 133704413 399291309 93507731 956122281 811213168 458383698 132424499 343293043 824731881 875301483 975723389 803986819 292733838 470392273 210461784 292859442 126102943 47648169 739693508 298337883 48103498 120629940 800620187 276841975 896504226 657392988 171076003 127468425 793713561 398768642 14718012 420292893 649652524 421477870 475263804 626369699 128301436 395686792 657724012 578123643 992739990 409370357 830656571 777741219 239973693 941802188 933386987 633829822 355441010 546409134 873714618 114093578 86801770 925498939 223699477 947658783 93321654 225078988 694018973 759117351 665026089 674187361 743532421 178445444 751856670 762369108 148315120 197166491 724022382 179049639 307176994 706919929 15639371 763077837 995901679 567659117 514311660 891830760 8463242 855077363 185474597 120395790 244495662 627598184 486074985 955480192 681349820 225204807 4320958 385505046 720004423 878448351 587106584 33994482 498942038 126002180 158574277 978957271 720250613 864300944 297480718 208903251 162148368 659294375 7651883 697733327 417291896 739109923 231329323 45867556 737607687 610071341 698458908 928348992 796484931 712502931 29708957 733325932 169345344 857833806 781069618 371718688 797131927 242831325 202165502 298815513 586759620 42547294 982560860 821926544 211308913 862468479 721725363 582289526 482964513 447443482 895485362 564575379 303980079 836444529 390982932 294068088 105967897 202488139 13792770 729336150 229098225 778915705 740052549 339264698 768479231 630795156 280652561 972026848 768674878 271958451 140635519 535802301 289106188 377217183 799791072 944343697 998143238 575614920 348567411 777835550 709396293 804086501 145810580 432426879 91711995 750883040 998745427 58922229 696800035 360418032 670344734 647352226 918064396 452811294 679223061 283744424 331510605 676601840 643968517 261437406 920890846 346293020 258454017 722571321 461089827 674392073 491694117 86651141 57017299 511900663 74342068 596804983 258914479 380028128 965281241 995637629 957933959 601169255 202528564 942863872 197914878 71228421 861814696 102152672 106662233 678687758 770735993 861673199 680342114 338225292 28451832 846197036 933301243 545486336 359955231 880395972 144862130 604520989 190922989 307930016 934838675 242959954 129945582 359218844 405610486 67893194 653621464 798389799 371767893 573911597 220948066 329582129 789143789 866464541 224365201 708921621 499822088 886347617 722000042 90584869 578501991 87405262 394883248 329707416 185848593 265457691 5651118 739609051 834982939 327875424 689333448 742351550 103303827 130359030 408520179 255893427 890961597 659189699 603541275 209731565 126462170 871382997 7009933 352806944 620852368 863458829 70396749 496341071 220356657 155024154 406875984 732354683 348678686 228714501 71451702 735009768 379305075 53542114 17005106 363161023 770069842 827810709 605086368 254318423 228358766 484417450 826082521 103409367 84316559 124237579 226673229 124002473 592770405 547649657 424817382 22362486 785000920 541014094 287601879 889210794 220002849 23874801 56387127 809691595 357708896 263842273 946440167 123573749 179013087 480342301 995578761 243477507 785680351 994413021 356928705 133516838 381006398 512106104 20321544 251553998 865527095 774954356 998323514 704103175 574954790 398114960 96396565 975455194 667573334 321612050 431973449 579002944 660059984 847599779 405564832 555983232 342031564 140990229 517026440 808671577 832532048 242762366 498592024 630559436 826310388 776544501 619700651 172953472 406394917 345544951 801477521 953533364 115383671 693303067 146109024 837811406 720057221 250872949 360038525 794215195 375673355 96045945 526550580 448540149 768504827 324987136 758638964 642056349 634445897 142397164 670955652 486828196 732678095 644412558 557676726 230722578 709722285 862077913 690919803 983904131 58708559 991643566 733607123 749037038 971714734 240221983 854453028 454870977 362483897 338239897 730873172 999743472 806469154 522090 979054660 56611008 441577938 101798216 551231965 904553041 153974425 639279651 52146806 24714858 946479091 107665016 816961250 798395584 603730530 554275203 840436225 995684465 680463551 52938838 964214343 519532826 562680036 43877939 434403866 259559596 661963513 273708748 564305398 882660172 114421668 573132671 369614242 281991837 464245945 358280017 957651909 747488256 229114203 125286799 26302467 453802556 181454151 648965162 718843210 511902377 94917633 388089322 88931616 190941224 12354291 752571881 72683345 869923450 594803116 474423432 278998986 78923441 319261698 19931105 938981184 206580620 103114429 231589720 34665255 244882922 423401384 664546747 195938457 26210191 464321049 112162729 124720731 219638529 457459257 479043667 515267821 805679619 296973418 810603439 959649245 339882058 135522772 615312275 82970286 4534474 893636224 170187436 680483831 809720523 225695006 808115308 315414054 558792106 984051120 964607686 175781031 687083051 919129519 241672862 885536985 705849944 434343186 794668965 351523037 289557065 952703287 652415062 245761707 947179598 337365229 859738690 304980374 633384164 995219869 573593392 622110574 156117159 594151311 825254248 439470492 353222731 402829412 618553303 423353520 723337252 450850541 468769923 954783090 441734343 928968755 461289526 929315214 161369016 846958162 517572951 903559413 203470337 560429529 167947239 414860267 391503125 712996273 444413263 322498370 672184706 687401485 765328735 192649255 553271624 161507671 837912932 113429051 304950878 415967793 587094474 697096211 981783167 837207846 547723614 286863973 422300276 577647510 468712104 698239601 768442434 955257370 687688048 440380599 479440429 386610215 247533730 881310708 549667174 861204103 936625550 366222261 842554039 231736476 426385641 420468158 448251213 324410962 681482943 985691242 776829345 569663467 381984540 122167467 221965921 40079606 597181432 588419748 165942814 749664673 850030858 669269870 10708435 957282655 601397754 743368546 246083483 130976628 100626554 201620775 769946892 348705841 425213448 890923471 481408363 3063618 726307778 430536801 398442117 393025024 114464564 844688470 260165003 382819996 177898706 374849769 557644107 174303959 596828493 687861715 7369599 110419630 782381043 701153511 208360278 665791485 143133207 952955489 310566378 371909236 199373996 736836587 634425296 671852375 443596965 165620264 536932271 158084195 257159278 497932322 70822480 518222010 169931479 922099613 370659263 350752764 217942950 255942779 34596601 840225420 283021810 73338614 27675474 15651683 918240457 840836489 773343483 924280573 677970568 105732712 941215642 280919139 959562613 219381032 542751538 188300482 795701247 604732186 540666293 616150242 348019485 662015829 869179764 694873813 124276118 477490921 539377205 93301008 307812407 955992679 182380510 254949894 742471373 614006204 700592643 507270768 232380273 327406134 83772720 543115623 910466079 427836491 214536211 286118538 838272046 615640240 351075943 26367339 970425932 532282246 118184953 289514268 516968792 640419040 396803088 244762618 603602557 332328361 134900538 568103736 446170988 222988602 515882981 512144389 445649742 270107688 160566823 212189486 165122769 137928140 958637437 965250337 781714913 129132115 884033745 481448435 990321165 217131278 802847926 151808858 867421798 502948993 890414599 633917074 487737006 658971100 989412173 931075538 865056595 492652002 177805366 280407111 814748447 945599689 660074760 629010764 773984937 656695470 108566442 900051769 890151633 648420828 543632761 159739277 84104466 693389384 604558722 555622869 687696003 393462681 880554066 204590951 891566575 42582897 743010457 842812938 182521747 976953805 112207724 506229757 253977752 457998336 618619006 829606283 427727927 741084886 410468319 60999612 441827368 331363679 605942806 873147010 752882729 657214079 337758385 724115647 228592437 119957505 301442699 908591903 328263553 613695968 978519788 413720155 627127386 391751480 261597372 141170848 723007466 229012562 639023812 817711706 102329140 336349361 601298458 338835882 592184894 522963058 32934157 420729030 621532568 956943304 754728656 171055195 881549949 957125483 930297840 212181034 842698665 97091702 752552396 259964816 883538691 310967630 244062948 818735058 13223008 761976310 223932862 889066578 815832900 819410072 113101375 404540780 828073365 385020775 28741767 843153826 529416476 516809276 777899952 685265689 727840866 978272849 300649234 987158600 875643696 292415825 836625143 649680019 998177500 27957662 774701910 669596164 470632722 872384429 706685975 455629670 808591803 949865211 794855944 160785399 649558556 25589279 115114531 767372508 562651699 76413731 980622988 620401904 373769382 686255207 29931671 992235949 46452168 208333682 300401926 239163248 646127600 301877210 244302874 90635736 736695821 825859478 110538242 964817849 992945889 823491546 398269694 390746973 786742842 418209701 713965072 387802641 847883319 1660993 879624925 241511117 21428794 891871961 599424054 863356919 902820763 785261097 757635907 862552624 982080823 394359563 132330072 948969765 358541658 427964899 336665846 705425641 746537387 96234138 12165531 996574882 390465021 181679106 646010804 201810839 257697835 112301186 370111166 817701752 911603822 880997704 754390056 673029588 79146679 8045821 631350902 230732173 781854516 46187845 219971418 863024184 933981351 683671167 610412340 836921296 387623209 199912557 917228400 313117671 516362221 458272462 554984949 722191402 699224200 174766458 351850219 14343363 380400763 478199130 251659513 77341657 235160172 546495301 722597986 882911691 301418643 645894509 445235439 592791045 311706947 254909647 482649217 774869065 265186624 513720626 361647647 246783275 45636964 29886388 449853211 316765234 240063719 496695395 906689533 54596172 97121740 797894209 340576611 160972489 822368538 984967453 392677534 684813115 521101503 979257409 939079206 245631657 643614379 317094304 968365567 711944313 900331926 14382371 28849967 451735933 365178434 382890569 532606386 401195975 624514799 979007310 329207961 562740544 149593941 676342718 979448671 722484296 31881077 103448761 660717938 751397344 640854406 743413893 518236689 553026662 259092092 176900975 214128915 292604138 618627440 634969356 755894917 299642551 768669670 411779963 953911451 355446763 466308903 269211329 814916262 110487483 760755910 424480322 587940837 954454581 61640124 729026813 437885409 795099567 680686360 675144856 375026306 303714667 835036928 851350716 303765498 379991154 295131836 865887305 585597557 876194742 937644136 436648828 919618701 915445327 548748501 298930759 737958607 130814951 493666260 298638424 829524968 188321300 507969855 265292357 392668449 889330894 579521498 150420901 744354438 419037441 96089497 11014099 794143898 562608019 343069837 631075521 520654524 266542572 971303631 941912704 407998552 189356717 272480900 412801885 442796146 133089514 345719821 161923250 129970267 628968537 595324859 984531836 626951960 488673000 646471321 707228314 371588907 637767647 173502667 834759323 141528578 370014351 910956295 445840754 879391707 132463531 111329251 487272093 132996007 762631661 66789852 598759216 257744736 473379764 406918423 133078117 809105447 353282145 728768007 158446280 473437304 18684839 372262603 711579518 837068458 980378552 158398113 406249905 22680882 262090708 47273249 915221691 67772465 675343367 564063869 751886389 718064647 996748841 618262945 531143250 262612502 960071712 867009991 408202797 213757115 228685757 834945474 541240717 966820640 639524436 522211235 110266186 438607332 735484635 997093015 590855852 47911876 737722213 560383763 759681675 765755944 612387900 578861988 202632301 21277000 171721463 706538255 699683671 44961423 540760447 918430773 984569137 653504877 213203048 499428968 568191068 157903899 104805605 678778387 404344252 177254104 212136458 657810869 405961859 17610020 967292367 140191023 483642237 552524709 888046966 132939977 46813355 68624360 816997249 195148096 600060661 452901573 528849376 692863164 944575209 259175135 318100475 164099197 507760235 662749006 184384206 149383279 569187092 827985625 426873357 468973229 885006499 964873774 584975374 602968924 331974372 551242314 808051226 185169255 610055272 586035360 55829075 957026974 291673148 407357943 969920631 772460277 886688132 316750544 573902966 816588406 302721522 370069832 356453969 322866785 501570720 877432718 630924882 448448628 49280982 948851484 3439847 200911034 863962339 946892909 524770505 157186446 177648479 819399566 786995262 631276007 329701278 742894503 104349262 698204830 566007612 167856325 111633316 715050776 939453346 491860166 978344382 370936803 140042998 503567720 636512887 456907238 266108632 327572778 68722273 527151885 622850456 669427473 294888437 48468339 692236575 127389027 588710036 480003702 956045127 822004728 306247565 170907448 581802451 504040630 689513571 37205443 177557398 92109946 200849515 32816107 772291472 878163229 185239504 860537307 643100393 136311058 165851709 729666730 436996337 940283682 570738620 311248517 385428873 388657042 849494758 979914098 214979644 190457019 70448596 75515719 620303032 828711947 742347301 229036538 86399308 973049101 991544776 521970845 481879130 573428689 453869790 753506256 620814191 587775020 188917366 92552433 424131004 290573160 525220777 207145766 331611175 491557279 874079275 944965529 418661028 565953266 105016648 777122603 123579132 699946708 4159595 318600395 453950621 811741986 103997506 374194578 971418631 552676700 625877965 286908327 141038360 678810851 539624748 413408260 433500960 45309909 687448691 879079105 212693004 735771668 387268096 407447260 599325059 70199986 801663059 448763852 863882432 697330065 199064460 992655031 162810218 34666402 620262979 811072409 464617351 873726732 455131097 376448150 679213415 883202487 459871882 105908994 941359298 921581872 604009652 93386741 375109624 551790600 357472389 602153224 406567331 584225648 635592180 519527806 508417035 70868221 631560213 972522654 64737823 372043836 121505296 687748192 864194587 87507124 706553299 972543525 596315317 77581153 623392725 665835779 589667682 919916936 452989774 676850417 99163209 893365510 536754467 545340308 220105272 43108458 662042327 965205956 364687360 699467119 129982070 572283705 49177748 600077260 464701433 700625305 512742170 593651433 552528331 720908368 673728334 373315379 749133804 619354875 49206657 366596280 978395231 389336417 3545418 753027785 358359132 799220748 846358669 602803903 830631374 456150887 646512286 565792343 43191220 522833361 813880306 918316208 738102156 129886294 256328033 690605777 945097873 599661754 340918815 767587039 555327925 56130288 490575502 940770956 375727276 568780183 77527658 976920094 126331795 92740080 502422201 802469970 476948728 988963633 329310170 59563433 53787980 117288030 293914949 414337625 258182283 39259227 726180564 321148230 726429204 53599523 593843551 180958570 148254744 931034351 695324773 569627580 912448671 164916349 133113724 617874576 57807042 561001624 517693823 337084137 469841259 22179053 491783992 894907157 179010928 534629539 905654557 854908724 812733027 259981955 982310581 415989688 262441717 914354196 403855191 494739493 659117510 112433401 946507967 511528199 610106213 22346398 428120522 779068272 766852767 616072258 169662634 583906212 995750533 603413819 662738074 791489750 529176001 714541154 342893915 478210019 188165643 500719997 786597755 491737368 247052178 460906300 221752985 415846494 929812448 877161597 635905270 299778997 841773229 587022752 319593448 443112644 738080799 305707739 231894452 691233962 861346338 990442859 480555571 258438822 311677998 643558117 12365566 159237245 893167697 399265537 91123387 624332806 372339913 46372849 678602696 446887767 345670017 132029581 443551658 736198732 502574333 263567993 452579280 231272390 949578754 666825698 280448306 14723059 9131810 862070620 523263515 34984988 392668695 734997478 888636277 35937597 457136792 710698700 462508798 614473946 638046466 995661079 953932764 67600260 244387225 590744498 945525567 313646182 21790285 626009098 816728906 492727461 405214907 525752737 343410686 710229470 559056203 561795543 645636150 506933495 679153834 809017314 306579525 770298759 141538169 697617407 440387746 549286493 832681324 822450442 627576258 514997503 400658575 911742652 334904415 458754526 881463614 621807932 7751352 41994136 633141660 987590694 645206740 111617485 558064247 608144288 176549781 614447245 268760953 152344081 3242270 447560042 618767924 175370167 34114775 570139111 883954804 54761590 29263568 582990860 137089610 794395557 961712064 493366596 242019046 332095222 912300683 884382716 606831023 92213468 900298790 907642578 905551622 972854195 342364614 149508822 150552123 821680894 497741033 931103623 666627888 917397227 469601669 568570038 839039591 477923026 334844303 211816289 244389735 63286389 975438893 498310332 94897973 568649069 387338222 436235631 185115705 267986509 601964025 616315133 818690918 665849246 834438092 565284087 170690943 487689807 10619153 807994818 783553887 6369112 204197239 455220800 666064338 425402945 796390099 415388336 482992283 226504731 811374840 943878150 556561543 270487542 872996336 959454863 668382366 133361855 665676584 859274469 748849531 841546351 51254531 138816900 949240262 642510836 2090092 816364134 892465251 705769261 564405811 342787955 302831893 144726810 830219715 750292448 313244877 678894999 696796910 554885027 202659595 27267869 888732192 214171502 673851808 698109265 248958143 41089737 502386787 842449514 889152837 248070520 220825996 923470489 113976200 459506873 763306118 523238271 676371941 755371007 998929805 42116653 652560896 864522033 296500159 728238648 731853515 318301488 746588864 335186965 613580768 767460819 307717723 833795723 652891825 926254115 419868785 95169043 308593658 901095368 197814294 343649878 683595808 963676074 736822890 218767823 817711538 877694427 249923079 895774737 523907662 622020721 241637598 254683208 680541372 261071219 852475790 436046876 529120948 285856444 488670603 180419950 182709153 981939824 564007336 82351905 903854590 786901853 914906739 141939608 885983842 461685214 784814930 32752145 602126569 533055690 377895746 743821167 209590297 584854149 690617529 338303177 863377964 386546102 3160217 424307591 718475172 857709212 75856606 615262425 731038174 208341290 29077257 160605758 375438609 798671427 459436433 267508939 105909209 278180425 790472144 637758214 77618515 448004978 234881245 312734662 778192300 93194046 789306322 164973061 588983693 519575100 141224242 941931088 664260650 61727374 827714905 897998427 138075647 891655504 603514014 725401948 368647852 467707236 877360630 831845232 376445600 579512487 955326874 255648911 842978440 982007045 78049582 461947414 876868199 638305035 820530204 259562020 90439734 480149118 515711928 983830478 649411406 851974451 279336836 879615872 644038898 257702480 242547215 699628695 148020607 790193314 747367491 898660951 513981358 122047966 170753958 865258100 820639812 858459711 285094240 661886630 657268860 617564871 998998901 932383053 957424738 43571381 500411379 555329139 736510993 347353181 841008887 897966384 693921880 261232704 62224157 208607450 257311859 182373108 624432172 921754797 851008011 781026821 313539428 172302534 522711603 575847666 334989846 114540894 102684892 641580157 103319230 592495346 768388945 526919724 451974443 104227902 488789798 784684785 531753331 32463339 972618576 377822819 25682196 152367247 734657659 148303708 48399313 151637792 355444970 461942443 917733505 69832308 217616905 864257892 693860378 774552145 934271592 771004565 229791600 507689380 785730220 296610245 646403281 618043459 129316593 381289224 611050976 35142029 688298660 938427914 69242853 540823731 172262735 242499851 746946412 832450689 315583719 154275346 623940243 705576274 879022848 585178443 545966947 927814583 483173545 152331257 595317848 266292339 760993390 368448039 255297743 489258968 886991202 386027028 174810423 327243080 364331321 943016049 295328272 8359968 571038273 112634950 923529834 818983828 111041091 94004078 478132730 108372 120209323 965019261 469870228 120786376 154136630 234833472 406034535 196901969 626820289 237603099 246499613 712186806 684277168 370791047 67843050 261245506 182643458 580239844 981280566 255763735 878188990 986721151 872843163 532535488 147331623 794799734 260731626 672266818 214813737 932215274 220177033 88402117 783715818 730832162 325011185 48781049 462015512 976126612 968139635 562713619 814481329 970679247 455289916 930177485 338143 895070486 830404280 700430063 79198160 233033427 214559720 888596443 561122290 105386062 877689724 294703150 788898397 102036618 811316537 960407957 686421683 145508053 374806813 481230364 860523983 640953558 354855170 615919119 275577653 674180881 936130330 697528653 808627222 595514101 921020249 520222870 309442944 214587777 840718065 381874872 932183607 404333695 468004016 460777424 996982968 359630123 833357189 737768741 902262500 919672810 577935274 299421931 663586812 969782605 17095418 186710583 6368720 819589858 970919823 947389357 848028310 790074289 880690052 122833478 434656653 873524109 523757412 161307812 122505180 141852509 565814243 209307942 911856945 679371171 195072452 387508291 374335631 963909903 240298099 728019066 885356810 940698121 510659114 591758665 101898343 103793014 773868218 543668905 446373978 395786767 878856236 939287346 813627414 379490245 669237201 291727707 645733386 804915080 18644774 489996033 819095023 447273038 260022432 305549552 182421218 502359705 83886896 477382306 380382242 90274979 359380346 820706585 360728553 265824667 146039093 670030846 269178673 49761706 123689176 136643866 993650202 680331740 932106732 125404712 280994414 712024966 456430323 145729158 997239088 189002460 752892892 450167266 255744002 281274258 419900250 983233804 55359851 86873460 393130417 634914308 568524686 360493987 280662535 678966631 899441944 405629595 60531463 269078384 859442166 723686705 619076697 778271259 657603754 925628623 256710764 999290841 302783682 894186078 511950690 719767251 784115431 89271342 388021494 977759704 72608547 873748586 518326765 34793984 595469634 963819661 248658222 33098815 430975221 690717304 569513558 827258788 496524252 456590255 681546668 424292148 185710391 877667176 240294305 518616381 701423140 783722525 486577369 118234772 689343882 342313085 153931936 28883246 430856629 893920840 822023515 596725205 671781694 186900516 634223013 938769363 969991469 560205102 160511696 824364992 54604421 503451945 507518722 353157164 639756902 426443603 733921345 963189884 579107681 513700295 452189299 304897395 637654807 13634218 565475862 143276063 45192856 328876511 464772096 670780272 500594308 823931794 553134937 353947698 451233635 716501573 946014200 730956790 729179360 315723812 973281663 253805275 804460629 455058308 904031122 687900040 359841267 911655369 118013508 362238855 754154169 696650737 605080389 417592961 214368415 521202883 302917213 681888723 240040526 792800083 742421508 283297205 761690209 255567332 567345011 506335471 52031588 125558563 868039198 280388093 899093192 998056439 433307327 684863879 393599565 487258 64470915 457170211 935056418 513143532 322183916 767768732 171170223 506081911 603892653 333297358 828559844 224524832 772760204 370697629 269855357 630790007 57820387 388451268 326870754 440718343 51684055 638744862 16061441 594788683 223766378 470087145 691590998 776480696 497115708 206584867 13004924 287087167 419678829 676970796 630926490 575631388 284519693 895399463 392592874 94484498 556088301 166084096 253437992 960600041 951188021 307203910 216929178 551141360 129822032 161077451 194850448 537100604 436277332 133167490 733083929 205287862 59892097 393036672 324627649 910147453 90030514 64850884 726125283 658956459 939263194 823432907 772837235 444431866 550440511 729570051 634797884 485327080 428727051 742232837 998889036 968749335 928032288 137192962 463235655 29805135 436040793 674992985 247537218 512851639 773766438 743631258 645218149 939909192 976321086 119902225 668087770 826632678 85437607 378710961 733312552 108192624 290900302 174709645 990045425 411189982 626508585 165152570 978405576 929803693 829147097 536786090 799675628 260094880 165475483 209670065 454271688 250519003 746957406 185360535 521139524 748739787 941833770 35631481 908915815 71361478 246390559 601008651 493057646 505274090 265077537 62621392 355851628 905870148 275921692 63008463 307228258 914991197 18987630 203705529 139868875 167102313 232808713 759961547 815338598 573143298 137644059 4826475 381551174 559399172 601944747 439157218 574662998 768544261 66676340 462038722 669092625 109652061 524324568 162606347 90164876 702727929 484563543 653552567 654232712 991877065 664080753 313457700 428059885 733361978 489548960 303030519 793862784 329956348 313908339 380318655 569778699 879170896 614892170 875520003 863681625 531075885 487768332 845301924 307969443 647577770 479566355 180209251 777966334 155059482 13893436 373461864 952814606 399215390 888669771 72666667 756209308 790877084 409184418 122489449 864656714 752088686 75834105 411886851 992832672 933146600 821413624 512250206 345850715 983457218 427321530 622540104 394411231 408024261 342575298 772210554 231562138 593054194 929709208 914223403 378132062 713100385 730813023 571107116 242323573 674185672 5731818 279197010 732965328 27735164 285408701 305840574 618143078 745117990 872944031 324755106 214031753 751734754 858493718 539334725 374379523 280571068 294368404 746321919 655086576 989835524 944040819 223770373 131869412 534656517 730091497 453487217 258562622 474341802 797871545 281925476 178367262 871930575 248747987 139150644 50473096 316193430 681844502 838419619 490352427 295135651 537748004 449878225 988486856 30900951 899246542 52852141 742605549 947636449 292207695 784411590 311530158 423222320 811672442 403656418 663380246 297151005 67688444 501813198 802916219 290922445 412463200 482477242 168262941 458468037 90248648 177476962 613563743 154546398 645319984 79055339 378852794 441130874 598264660 12077265 946845837 922359120 170619998 691178392 350327362 828038562 338856566 837776043 478181804 376420763 949154508 433660387 932110851 549457987 947523414 995952062 320546593 143172100 486374814 451174397 840358108 996388647 24765529 762690408 682491448 950162931 83404159 794014891 357433934 270328068 43746762 202542980 898383772 282755163 644146695 897027892 68285821 806361977 334922495 48661823 991507726 879768758 729139210 767206698 392256616 993696924 339796414 60192269 134666161 459767886 643694538 290768657 323285355 959647017 697746586 86348603 424480380 972091496 556773650 198126467 49110504 563488607 51712174 879819508 34191971 825181845 719536288 642698516 835689648 985328065 741340281 78215625 695099916 785683468 566471981 275342022 849888690 709329364 660778911 224836691 338254168 359869495 555410110 733754586 164926856 738959220 151448765 77282644 230132057 827542264 292014084 805523183 764153050 442620337 296820694 624185984 630663961 101656919 529348469 968084937 712464437 717962304 562726255 403343443 815010461 906430630 408816861 165432334 907484048 913386890 712209112 192645674 749353812 90898049 729892531 984011802 928440873 963747451 268912743 748786737 980188840 520386165 312354620 732600004 670531240 840117588 301695794 109102837 770330588 950089619 230520889 132448514 242897071 85192293 415820929 38761860 910381455 547504296 548001802 560292192 506120073 508611283 910193978 35329049 21650207 950014090 448918642 214956769 182201496 8755941 935265225 694013980 263273842 473455951 146790042 346811358 224034850 801123476 976280659 734108425 740109935 906267486 729349795 852510885 412437533 474510879 841947693 155603036 222686399 621024159 418876385 682859645 761936447 394224969 538000628 754652464 763614559 810686911 89560436 969991812 189420293 28896580 615123672 915316160 913255823 441189332 5703538 99008026 652607769 838357212 839248420 91609413 531312482 433868913 828811682 467619819 447921667 16053681 489402822 35804060 684482064 100437659 770344540 519780625 947497420 426306292 614952631 421570096 5003583 442337455 136271517 291483598 553313924 408381953 430362022 694491708 752426957 624856183 43406611 880109817 976210372 458522812 256067053 31557255 180914402 693283199 17143218 509886908 633478580 602151311 418581008 846592853 565212243 512896441 364221393 856211619 506677596 71151112 775684716 605503776 122776156 552291573 397759002 201356613 445041492 765260981 366119577 123539402 326067938 665143530 766773356 162731670 752840251 757172761 968561796 12926180 528776848 233050465 425668875 600843962 75680679 31204944 568496111 414674849 637044093 842402495 649846801 354029802 164814062 317446049 429899416 881369880 642641964 597182460 858352076 232708494 234475521 125377311 892879548 912367044 602119029 27881245 967964450 870652806 852400272 31724898 724205634 585911511 84239235 619403287 701410221 619307877 78984860 561461888 713244153 14293210 291107798 252702701 8749794 588513015 11944302 132739364 949020945 352539151 87205901 154612393 49236746 374627776 502754771 661767946 966719952 365902594 52215705 937244602 561999585 220253219 457359337 992597067 304134680 482674761 498831250 815206150 867671139 121548119 935055943 34816177 575351074 948518858 461129320 352787141 99671436 860987983 272370311 342894986 28211005 597111559 144828657 729808634 583934 937795207 17662341 297705325 38081442 109784309 659538628 429962507 349375524 973575530 927999423 745508214 470610874 481751628 28014444 14840765 952277742 813871254 578920809 478542376 860491951 328937900 7311648 124575254 656043564 847795764 752354356 898223296 772892918 368066177 113288446 151637584 536381795 873170350 686517876 748566348 462318033 560598088 167538559 759373827 139377609 966428156 570282011 380189317 509806385 28023796 898756169 498361910 968374858 114099611 662053965 85025792 513513068 864316152 418398388 758382496 367706957 988409131 984662177 938179068 301186341 421435410 695070348 54728210 78232154 854957043 679724519 30620866 452382330 182111626 57912211 326995057 54333902 952900107 420407822 58677537 571784026 353843936 803147590 701453479 240472260 487139130 497868945 790062552 157823909 688543297 465883221 644988037 513069482 642886744 616741545 388754758 488497852 868619712 700918251 425167768 568291382 624060979 3364314 442251454 114697199 216994534 376280440 737569489 86245561 642133170 439940385 868825592 62881 932242333 73828316 692395362 392235948 53000550 773500428 783906161 487774244 364772144 185060479 656639681 414310008 843852636 104012649 286632536 322426273 704686348 16003787 74749282 820623574 517870266 471938297 854800228 35093515 932501663 453430193 916211795 264823342 859544495 837958961 872561362 665820981 74210178 172856061 71896765 344786095 988520746 938824019 503459436 468477875 478529246 527345195 574208681 155015551 799268683 572211610 704383854 269156286 465535041 340031689 245043474 548541254 208918698 473410305 768001212 778759732 851830633 620539149 894695006 204923240 636028368 65238783 168580943 238035855 471276082 694817098 271219458 257196480 659140963 106402605 985713170 385302299 700076883 213761132 332911830 468807397 172798580 511820768 964353572 955022198 935080537 807860742 382087112 839925548 784700356 701045682 418925721 850445343 997072889 256030316 844276232 968219419 178315696 338610032 891193247 147699132 156820659 711319561 12607488 268171000 339039073 636759238 541807884 362992381 583713777 649414758 931442192 382508127 259445896 500981655 841581935 292784265 454072031 670016866 53027644 467800246 707360074 861836003 176843589 971934534 159090022 123670798 181226866 849103707 134187018 768843934 980756345 552556685 58102065 349985187 380869720 360217358 397018968 254594482 618910333 441216718 309452931 411065644 307984465 183582236 308009319 551405695 477746141 807546525 561082745 207066086 628798738 889828 933658148 270175804 137630535 272909238 853822212 634938416 108699749 941924216 953808591 660369539 491193663 705940478 327113163 960069012 455432398 57870475 956371882 109123393 122846032 932845869 568725275 367123008 387665032 17960485 783701153 963104603 326544625 354601582 192454159 897675067 514196760 715197404 336289253 191299938 900751643 218572953 11792161 328851692 163901109 536161035 537442694 780112806 336081027 788736837 426454827 707669049 151089256 31119371 570009599 623367124 540580030 559972577 812148786 818354287 531724415 498740398 402537178 674157211 644228828 460929588 175709135 424972214 942854471 122091942 836817066 946973733 187243167 577497953 516174673 783649033 293360663 411567131 743673968 800858567 476614631 792966170 911162483 989790008 662075540 452140686 929902546 155451041 246929239 35232759 492071758 658827941 306464183 151907230 767205774 91875383 799008646 225613211 653139550 446366567 52900145 667519348 257354502 614517609 622861048 491786790 619790366 681425508 286436457 833642388 810045420 324285496 313691238 645675961 230768585 992151036 812504771 975214438 690516630 980049382 566099920 633170063 824758306 821732940 886686858 481548474 89633768 839703841 190719425 311165237 930339094 398279871 621031168 289701807 139506463 948434827 136523845 91183663 547516295 97529579 350205885 128612262 371087649 584242293 69063963 93333450 6592063 446016911 33573069 868633159 160575661 585179243 411868873 250750149 890310402 244255414 659354087 611741737 731208672 661785159 378219495 114270558 461472892 754171015 796541056 11216481 703792974 913343414 884511188 495132054 364728516 961367335 904426287 585059087 760455443 514066202 984983458 158082047 670974736 994911168 666257349 185813442 973209550 213718046 984109960 354263340 581592923 760104651 93288376 13585267 174477070 483645785 234811468 181428011 271790651 809296940 600130475 146627203 108723719 377752814 776714299 959998707 407193803 623297231 274880266 707561579 790361183 153196242 932284700 783034893 899459331 695839914 140939309 43557168 367398448 132581233 741334511 59053848 910197023 42220338 909132673 508540394 64053647 138944991 467956633 254195228 710788468 769150557 626135043 744297624 660719389 502450234 625396925 533384477 721799163 764358745 714408352 666744329 935928484 777266614 572125698 125474658 569639975 677537344 760272198 754542462 685483661 302611219 568753056 129657767 263037132 670339655 973841930 755514343 146173356 475489546 125685218 379111579 144722987 843878077 98214871 160146405 231167123 12025548 617334219 279439230 986151883 108778545 419751841 149431211 774504943 650719079 531023547 967155954 452667622 650525571 84398727 480661288 537312208 927889350 654896219 182720736 946537816 69046125 736090955 781442367 775450694 873226541 638869235 218227226 529945848 320921499 587077060 712112620 354480868 378996294 62394824 560528678 829341594 70728525 758092030 477447380 254533927 181694388 150746621 441790059 138821905 413338999 685374764 176646467 946535527 557912864 113734456 625224628 303527261 31183236 497236469 253605270 930417520 640207727 365943755 563152011 971919889 593886884 64100645 441997992 705468811 311739369 637878933 102151852 863874366 744610837 426080188 493638725 387535590 312568546 216349873 159736742 52158778 253484679 97926444 621679173 383215556 82613676 338041401 483749581 219989565 206595184 495212916 404562401 461600083 611125655 431730797 379094274 505550008 460590061 813036384 437444873 593467166 89160130 130746086 879178077 498498378 888625450 782704167 234983162 131111858 419933711 464575381 686200703 26983279 820721192 852763369 972665396 964514586 494728737 790122783 293533206 848686644 422377749 932834769 31499298 649282091 879563581 122530882 829998505 232935079 969093633 418128407 592201211 736353654 74265305 447795549 673540460 883604524 439916728 481313521 183507250 487111839 941525730 982350081 635146919 84736214 832921929 53960336 273517094 502377537 821245360 136590531 506059650 858905604 582361403 41200179 599125470 435407391 453317952 920964278 268358256 628175191 399582169 422437581 582198221 410566228 25614689 163101920 42736280 759067630 298048035 786626444 260724222 115148526 660443350 950653056 876503426 461096831 438238570 422327519 522064201 654643292 517024510 581008812 321548679 350993347 471332207 176338871 601135923 409012212 781106418 905171581 931383603 463748712 796887280 329803491 412962039 367299062 960683746 809014425 294670536 526325807 478527239 723080163 302277365 183353214 913928462 957276886 662241179 902780892 432574465 328194975 130816705 382457106 433358968 411545829 584821231 190294409 468218548 601961918 152242428 913320634 524927389 878336745 186117224 628266458 158500674 23859027 394350621 771830604 571675234 716872943 18145219 708861668 719926192 244145994 908833348 831688964 367328470 470825524 660799320 790756239 97128511 521509401 739969872 545772132 520734659 387190650 848810075 222082331 755655253 421886187 519164002 284749522 702807576 326187847 163371702 510311689 697518684 956889503 935025910 451068413 210612060 238987332 733721678 915974623 276003658 32232698 109027269 188966167 121437372 930963027 829671348 301538988 343463407 846562408 215158911 352374004 840834750 690455408 337674912 964362283 669812649 966148287 585069286 558205957 174300539 593200966 500931126 527735955 632342559 735661312 709445820 674593164 252157237 386704124 320953347 209350445 866590454 75923626 459112327 834640084 609877652 364550549 75143390 974138653 484672092 73359168 126586343 308207926 66795637 740564943 915123924 289107102 769290496 144683797 877452123 178497691 373806581 788329525 740231295 471587995 575195807 591118269 635790325 684400502 587254911 519454133 249482164 650052531 980128724 393548706 402989235 491613653 628321936 112857239 593661615 926884622 431617008 662884622 374573858 889403741 673151125 402873093 86397063 604509403 169454841 593739076 612878398 448454617 547249612 206301076 199983522 825270300 616608235 142147870 474937417 507723254 389262622 747080837 375347884 195272776 299247848 699420327 295495867 250692787 509074039 921900186 226917649 355889413 638552560 176664521 682095919 419315544 716841688 678445365 730933881 681400343 60792635 855225810 256564344 656825562 962553490 817004984 156783591 143230480 540786266 288459721 30248728 541049553 186878092 779310448 640902272 246471419 486457358 194507566 570348090 293262360 76693034 293794142 531794280 503147794 253877220 411317827 764509987 941786858 540801775 151596253 885624489 802149644 455088229 250080476 290809287 567773598 184727997 910008900 636982624 268400365 964641237 563246055 637012351 543566199 19854800 723790315 790159381 814796706 587199311 269987519 120862745 890519664 390432916 489648788 639038368 615505927 357801278 445214889 164552082 680385020 725783583 695280104 463252967 163580274 491237079 712524140 247268912 678106402 979714071 32951682 84808977 948370373 496297507 813985739 339889591 70598543 163162291 851864999 904800603 261813638 565931277 891280192 59702120 613775806 553134016 540173481 329171362 335058110 845345009 987524028 658889278 714854034 40022776 93465813 354514844 234455866 218045641 553759873 412682962 642352276 110675689 255879902 812492657 2598449 386111507 456940191 895522031 223298716 907658772 128026216 924888526 540992864 745091084 775411355 837413758 751741203 765153705 785950257 965891512 968098133 81773770 499239156 793791397 350495618 262523791 271394995 834489239 374545329 314402324 930157314 468740795 741342755 882200381 933159399 783012614 559169899 557178369 803163425 174495748 123969171 230225264 39352647 244398994 674794645 798766336 358373356 849055028 597453019 424361447 927262084 328127168 929235967 170098811 13253870 6814825 975393023 321508113 447468858 83940698 303671884 721228356 397799075 369021406 196436603 325112644 305624752 243096232 296784684 17711343 219877720 796963381 953504721 302409851 211310417 192441301 629318058 998104630 528881690 511785060 984419493 58418639 445677370 738602686 222723069 284549650 38574499 834022664 563865296 151204475 995608160 442609767 256604461 335677377 433222702 486398452 643067634 93607143 56650032 898197475 391559405 602321599 323847478 265103408 477418896 833392033 917760001 765954517 455678855 219417379 289290966 473817130 360737002 680234197 467252966 428293677 745837246 359745724 53271327 677789861 327189475 884464525 410217995 939598598 984698125 323835583 168521872 896539903 629888889 15722654 11261197 696706759 367662359 989237232 476537960 159531801 42279610 540521275 267104226 639223888 827115166 322387393 622682112 835860095 864647225 17146472 186079515 83098776 781522593 208443027 489180698 941366640 243216970 580995006 8044377 445221849 712948836 867001121 351794312 463332918 946285395 968683439 793911752 683633736 336417810 282608890 700454387 801091268 82903333 54891164 591592414 730050715 741879518 396604864 806454621 935369362 87129636 751159732 550934597 927876312 406919774 992634042 808997422 62328184 592206546 284682129 968322314 156977056 790284973 142175956 995105310 132233779 613557844 827746229 667279858 671204027 126597351 749229982 857380443 661705989 892201207 453754970 64534300 47653826 258074160 380014386 199552409 832904587 846042084 340756253 862409707 199661471 757284941 232778291 555994527 550964829 210344482 247013325 471772608 553135389 602802107 405679607 58429379 349893142 238635401 863569086 922155284 593183063 349552794 323778486 855081369 726903201 779156635 734454713 446427668 207316917 875587018 185046466 403542169 334386646 399906141 739991516 927805221 179774471 908722929 723299604 826256429 106990635 411557742 372316750 767362267 990423796 554165534 44637724 317440786 261364320 745418780 362029096 174713746 445772679 417761252 350867978 612648514 789461356 132308523 162803727 949161806 492892742 356948750 806813945 475247647 335864805 994023658 339772985 866647492 171868410 496441341 282869780 758882377 873153309 903254431 964202277 374742087 699308110 450712993 612545173 78516352 567820453 496786737 483991704 685199053 498551382 411691154 635836356 559877691 847837229 851835401 290114431 763783786 291538272 560552148 173542166 930350154 412208225 304482802 556138796 493520703 327182689 416881086 380322356 895086812 352311835 666191408 12171767 20818392 641583951 614143380 854990105 238942481 585812918 223363643 723343272 989665134 571503099 423372058 684110236 141124382 56804646 430778531 118429021 347308170 876527458 573276548 256893754 274094270 727130172 93778504 4754731 593593464 63112033 550021642 870991400 405520784 28009369 170904317 868181281 364911595 997450074 483486532 874911603 277725455 535482109 870576360 672468915 424779684 833415216 934309744 955648639 782718326 333985043 693667308 259069332 434096838 821567947 622798952 9177749 720674340 116700647 963477622 839740533 246734749 585716485 823492910 928356004 838928643 347945275 757337908 189135122 934501258 637737088 536471418 747840553 441404656 695507191 317500082 583746322 951949323 862189801 194384119 867020145 491431309 159125814 824788521 853518949 35949579 389866597 659509616 265518518 290222686 429697521 128744488 514361849 866864481 560034967 711778717 721653938 151447740 81776689 163493080 826245681 973243247 222141710 533870126 132381882 606107341 987012957 700924954 881699105 938039668 21876966 346851726 568847098 541681186 695050423 169627584 849839302 72905928 609067484 489953361 995808309 51614303 814795417 790070015 988912954 433651699 641948213 74950541 720895869 728426093 417306127 961093033 336880328 885703370 86017075 660735593 431585904 78859979 67430296 28215221 483760481 162965209 306849802 319489721 266073225 254242862 688257575 40709953 819396087 726577455 893379761 453465838 250947203 976832807 70925672 914584610 639261034 356479347 542652164 229357241 853776246 534825865 985847439 511251819 292332712 185240398 192828666 205708848 357067631 192924995 869684368 685751663 343435136 530895772 617473855 319368817 844004923 356302780 996114779 472630723 503871183 444006772 801415319 350247760 894993958 153136072 524036645 770851571 67950147 458691198 212035030 892449308 900995267 798869908 454528221 786852620 343808243 323643055 804493708 558978774 358215853 190068816 331679006 735988677 412123052 240034823 753084584 149090640 418767978 429923177 333939191 576015359 938142995 726955130 384577843 827986415 131032518 747983481 157125098 381536108 406841094 608913625 773182153 382808348 259320216 399047126 881958372 677824467 645018600 93095545 396581179 24425726 380382292 727620546 67983174 467724219 240128917 873834014 822556731 323977024 621011763 601839008 1646315 17652615 197833182 374569785 945916946 14022657 836750274 392104303 494252616 616955168 497689377 950656028 650462014 931097213 380708304 130445443 142910946 216730727 39702186 117899250 4610844 26679075 419732316 449097459 920466047 92511843 658398702 861563477 405671786 152050455 479450694 173186760 483055991 650736579 906786052 962142935 924219324 104381839 333264589 888552709 776455826 106597453 747060043 340081138 715205714 444519879 193943054 900711092 120187141 504951459 167472515 278315450 199851158 881390097 884848593 579059178 656307831 281540082 208057089 455511122 627747453 386040099 614149876 682150797 976287781 959101777 220982703 108028917 76606723 126261525 67478938 485045912 414253938 215811312 19659707 449434113 857554287 516263051 121255154 518485012 243332435 924043992 849548682 685108276 596527768 96335327 297559297 231566642 154137496 389033673 615810011 257767000 93616842 920258320 31775149 868730373 575021120 708382791 826278380 974395996 622095903 355272665 309430208 404529724 590835653 812463987 784943452 332822992 931665855 310059419 632316670 866274940 549391996 28004271 831908160 703832875 578877165 745729498 860532558 836480654 501729289 318942264 853956612 122243856 559271552 725086600 250199571 721705386 684634013 874147298 48322614 186876895 997234754 630533169 606427632 604547204 293502479 678295954 280863645 16530893 609405806 332384170 210037403 811094143 652237399 900440371 417682547 267455695 562784948 461488051 164126127 900833197 208440991 501971123 52120734 231741233 987347452 455632360 789701944 368086708 106738964 339594698 105306656 488927700 56078530 217830937 303317427 930219087 705194429 862286942 919138766 201191674 952814185 276434324 706503760 328652678 461669354 310709881 636279772 291589851 175873566 568697596 900764951 403783921 416431191 641291414 817531327 50528507 580521444 15319597 463879513 364613626 132695639 293766671 183305868 545762078 658190833 199173258 510008547 289753669 58262299 682127334 57000685 573634825 96485320 181253194 186658859 430888485 545230539 938671519 524331016 44913029 752589634 137464643 215931875 462139961 781737858 400145884 460078526 237943109 881261834 67805619 837900085 985245791 470724495 567597065 58421287 528483879 355111930 616943354 456114433 823154801 476778102 406473639 134136453 493862023 78447533 261887466 98108410 639044402 646499175 349422664 523334770 859686978 408675328 394717048 832145798 766906421 545499658 946484338 310660662 4808697 101378399 791204190 771897817 338511970 71967220 844141746 489463360 348147268 971632256 63774196 570721882 448648304 543859145 892620914 595086725 444000351 191478747 935634154 218492810 499058872 396298280 616741717 757552322 911854537 721775257 680838608 816587416 789554935 427963716 787516204 122462532 902615695 22138749 836196469 633761439 264905740 317815114 573926926 643181588 805026355 619269127 317941319 762600802 666049664 918506371 672380568 508748543 353496333 506766472 914769513 215113970 214454537 458077393 781253164 593516522 586046576 98224210 764072247 708380877 339194797 193502396 408022651 197551912 906818931 529245951 16040163 330308350 750107535 709328168 323716244 508968090 566426248 438170186 628837989 790237064 98030269 774000368 821599576 360642780 344739715 525717176 376688770 436445876 818574435 467967633 318268843 421572017 302056746 709183996 376789703 861644734 970786398 191601675 865846892 200871785 203337979 801829909 293772048 525912280 779462540 904903871 208388820 353311809 581337325 410129977 226337543 308975375 896645175 805702356 372373448 788934733 796099226 327973140 926039716 190570366 677258985 831666883 510366844 629697632 417906056 702682198 672027757 901282954 718759007 93955806 593411629 8295145 690257480 409504828 23780154 828960562 777568929 606382260 431181285 155006523 851970848 739679143 224482723 93050473 155990968 705213176 860956207 650443053 907114094 431891693 255105386 796697983 61859642 902010848 151549555 637910508 297390801 678915035 553554579 233104005 147644554 458849342 792727902 982460333 139908701 179469200 654933253 615457825 454470778 686935639 864195243 537069210 455213112 685213711 198246264 73139613 855344864 745146157 874727716 133984468 483385659 754381708 951891438 436136097 246771818 444038562 871578712 452385589 624997044 377221197 7486775 817853025 701896120 266851922 541370895 917715081 689222377 840604816 706804706 391418732 971241342 716452981 304811477 197623896 749331564 325638968 221815165 869172095 15331544 199839905 928594845 58249785 458884014 569104775 201707042 476050351 598910833 557217613 102004531 187624208 556867682 996784979 635243376 819206316 639020030 523107412 960408113 353192826 493241134 43635398 798145512 191000689 913264069 350343507 653449583 943888396 893817428 315999355 456118458 591086639 779871531 193347376 676945597 186962537 512421440 486962263 97782372 112824075 805799079 179943504 420058831 928322311 843673397 443225272 857400092 540214332 567051012 313855470 339114186 409106173 208592303 583434720 214853078 506402099 934694572 209716696 576847501 420963773 979371287 373819894 585212753 53506738 153459619 195044091 719897972 855039861 143100650 901672232 85374010 397111949 653677636 993960854 941849910 531522159 539976927 799871698 154986845 601997567 391697405 179070769 968967356 634108774 240185135 92557144 319629899 275422553 962107516 432698767 732537574 873908234 992816356 280906729 86029055 650487194 744420671 346250819 711963798 700015379 644314226 102676808 319789621 695885049 448675510 417660251 299076988 557166032 304737251 916440175 300819465 134631342 600773317 598252216 289566663 248321447 622143083 35197948 294541780 419807058 599946302 746095065 849053562 586053335 532879348 27491886 234230459 837723156 393331683 921684643 10590298 620400873 436866811 835914930 130546750 70950244 502628948 933245422 507469572 505376209 618158120 320812785 306834595 553745878 469815819 205708614 233992763 312457864 388000147 994738643 125845393 682853977 305576412 141988225 58067592 393771984 436072065 335545966 493326830 763760394 38847384 397134826 866259865 984248644 256040075 319799705 28907061 880083741 45582487 441450 438889152 141407654 94007066 2013559 629545686 27525603 683665537 855211612 407634647 381535209 895756067 75849126 490872167 420912642 463475787 398603154 435053977 606515986 542333851 33561196 513286594 682808812 966180880 543392269 189778022 590258965 767956611 85013144 615520798 193585157 302263492 920590955 193000452 307300394 747462040 244955402 950237216 288316003 854008292 293828866 142724713 789431410 486250747 915731739 991676039 566038715 702764623 797490074 266073721 381573937 567642483 581661075 498193183 942247466 577831468 509419826 372501013 926854927 18819015 613627607 609711495 661390335 768691579 327987245 395468650 924927938 292714159 792490231 652728687 805347609 361534636 255708754 226536020 872976666 241496174 879318908 587030964 678035239 828376808 578621803 757518971 991760771 768474381 121051517 285971724 129002767 334122852 813343174 276698329 176501120 506033884 352591812 134381350 105229069 158636551 592867846 377050199 374954488 647371345 520575013 953721554 596606789 197808744 590630579 311783543 926021181 747117591 634324839 273433231 873784767 600374455 80413345 674954806 260151360 95559833 444749895 506793243 506168764 257434446 660234476 782382695 879877869 335900821 376686167 793617704 943257940 210667133 636100995 405683656 667090533 906845241 921184935 64776999 674277736 617521055 533898332 382435468 100914207 814375772 185706402 619525810 705106077 874122093 886158662 202219042 761418194 810926928 106523601 744493889 833442801 47740026 176544050 565414258 857041993 646157435 580885889 82623836 903850960 482916486 853633418 53051050 747064304 200260828 501041270 467106231 268331042 46735742 906790992 82762815 202913855 975027651 636238732 511567177 53130890 914504982 987777270 142508698 624719474 853138461 932682822 150594191 959858041 437213270 844333229 930914336 253756377 479585162 427216256 292338789 847110717 865647899 66200864 911028227 112655489 579008733 973006585 697415408 229211186 273205509 59209876 351505237 868750264 786827158 214083354 848515741 847634058 537978002 546907452 222205100 343160102 352670080 622312875 195033168 148008186 739924459 942590190 661800279 185902820 446812413 535972148 733529589 490241219 856371365 717356360 126981713 597832570 848798129 907024624 480328714 756172633 255792129 866327302 712772369 773487941 134512947 737545299 179339625 480696802 551043458 337199031 529236271 832808440 719380633 357677223 433689545 622753968 757388345 128917238 45883929 629550362 830499383 431946053 146516490 394976792 694154365 255553403 227737939 149501381 496524848 235339604 987084191 804785288 206275933 988725823 781797895 318573713 506289406 144684981 829187806 200814787 690831055 36481412 135017638 816344636 198548505 63605810 967855965 294376645 278591541 778143275 342829807 963466069 351176838 797714846 8983602 149462974 385033385 12289369 642297141 537782519 486298669 172528654 975833286 661303363 145487618 182068438 986757946 966581758 714132151 283827884 735449297 618176089 38213353 333188892 427984114 661529020 234602912 144858881 671715719 652842668 422879631 149816298 384013968 600690623 299548924 498516282 702282147 842227464 844026635 99591331 418821075 233281288 35257723 212730535 684142437 225965609 335157063 191869633 3484428 541334039 609123495 506678325 323750450 62913514 736773525 838377223 784404338 836443084 206232336 850391989 939515288 183420837 595925564 559165301 926165586 989260862 775961794 596010230 920861799 975523468 721153760 447855666 977459975 488680878 549622706 48112311 112311650 20178416 327701409 974668740 903648229 368949955 583776531 373164216 137310177 313005829 390077761 251383951 342488023 561072182 478157882 818236875 785785124 250565173 416675621 134441585 613676772 309521766 774221274 107959825 726605759 904587207 354156911 173403032 548970012 986692059 78991065 384908291 64658170 447669862 904658520 607852444 508373850 597012737 191590328 184394857 194011889 503695155 80247923 631578013 419130566 205276448 229092215 783949886 655976493 606320674 793311625 313594821 971289372 361685920 38357540 566387604 725480220 464437390 181542817 418897774 114085002 529451862 385620055 334622315 802624703 619742297 337531501 557235668 540162286 153028599 985625561 198282603 637148838 555102321 146571409 610242391 206746544 516962695 943701224 989816055 148408525 336320181 632743032 712052381 512258346 450224751 114851450 149781789 678636164 185800541 139643890 89165234 938780938 604845291 224417413 332768462 531529816 430165961 966721212 246605231 103533483 137843830 188866690 608337468 701231381 259988749 878944814 591472106 90782878 996104601 406671968 558717702 91007715 293539639 25226399 994716587 87118905 995903988 129721727 550724841 310314539 824899289 345614964 936226875 141665522 558624881 748518524 754182526 915095271 974035821 600165321 122862945 24742191 273102544 24121874 889931547 332414539 749685150 48929870 430593123 636264008 5183855 370799143 392029182 839986636 264121619 360480286 295643486 386258391 45554949 406782182 884453085 649716373 667223444 564748612 679366414 704162238 793215119 981967452 275658817 627977720 826084503 578034769 455293530 609176163 556866991 563750760 311050272 19849281 228290953 175200764 408488146 258605978 482403032 595302236 311921485 102947480 927125533 828945811 236638483 151280858 643196838 628410543 756845710 772464622 598626386 341735700 652642460 454058131 361220853 216697904 165458496 777728318 289797400 142388469 494062308 628696645 967503864 145078789 209154660 785943931 469072589 660224222 367686468 316645307 77377934 697024736 345233445 826019887 559765574 279583089 545467218 740461314 518668929 977466681 620562287 163029633 129099781 549403700 286802442 137589537 706580223 434180399 304914777 441678719 183671855 958541780 272521485 788485762 585510775 715995137 809690900 99729992 245693145 450220603 110502197 437262704 344993702 753929493 992868352 178972306 72845122 471736211 608459344 844701211 242316516 34399267 233474737 148381812 824655172 49208081 44331985 900493889 574232888 536546261 250249010 493446022 299820382 181755058 886998273 993031570 320401676 655551058 458797118 820911196 656006816 984633681 609836714 980877202 930720423 758646607 100947525 537693546 139573814 388928783 102024786 363619434 524043325 619784683 449400034 562269289 494077858 355109080 20374825 21354286 492180183 392181100 298095227 888978191 358875225 983174906 594901556 670085109 803297905 646357706 344502852 361762198 934870743 686618402 194886492 547842134 67261336 401039304 610713818 229592869 114501635 136983252 245464954 294546868 455093039 291171891 61699906 764365816 142647468 114303882 17334615 216417774 157883979 8961730 627629475 481705170 553899530 24975256 999974541 687310072 517453855 484075669 578554227 424680348 383478482 472492687 923340303 947353055 22220307 964377305 254375145 159369162 200288736 132471817 545149594 594505598 222543294 344340989 173450775 448872370 966634210 452932039 18230985 461611491 807498847 607284045 479719110 88097922 816825495 305945543 924113213 633878978 508870249 959400200 875415397 526382633 517736378 749993997 894211885 938059242 337496546 671285837 854843748 173690676 162881589 483069342 368851630 941324009 262097032 448381130 512672933 256676040 79524820 821382233 209528537 248396163 943028643 371322518 541765922 783798404 870423823 833009460 969321180 716906860 431706418 700609685 345944105 788905794 400666531 835489733 51450770 756973529 367512246 149568634 48936646 503669975 772991987 440791049 839592635 665243139 505696250 723478127 683814151 605194758 918433307 999261677 952187471 82378639 870998778 477762850 269116854 749064862 552379225 987604760 767269785 211009839 631017351 983858667 660097386 324824567 349850875 487628028 587453442 966045457 34347677 719311257 478149922 990776952 119097210 698235529 132783982 607945513 935072743 757550925 677968694 228054777 752129648 936290983 60852465 229818829 791625449 883496647 771763456 197604119 573178988 479062275 842414220 622430199 201333191 905166361 732954307 275412186 733310546 327476889 55847650 965772727 94149638 44094445 106877390 376711817 782914562 992905753 746587524 412161781 165237487 735130483 402785772 984319356 554666628 936624328 839409921 631180865 845249618 48256151 360144429 245589323 369314159 288404401 688945439 691639511 218148552 837466542 159211561 257484853 972349818 280481922 120869683 833009115 108264683 467348509 242514574 23490440 508287296 272583136 433303957 116564391 295768743 202742166 215001101 982176343 576073230 408216663 786969870 952185451 660906411 494693445 496451382 240156239 889262327 684271416 908640569 445784003 702640566 868027551 783735886 482846208 799818493 433740106 660722354 467037329 164112941 157725799 943925363 531194926 584705719 119864427 445232137 731855860 250588161 401503138 558851781 250683663 362312666 923586212 224439352 237711251 645727209 532379845 392789941 227599993 84531204 167628187 4058495 307629923 197620264 732401378 395267788 840147304 410678899 505739809 998157448 300336132 217387655 604356067 342898078 343921320 885042546 163564498 168969258 820472131 670426289 489396195 334604003 210555584 606308209 419889715 499490348 493792189 387346449 558044111 910665220 685409946 817403713 185675204 225361692 917205284 647933379 822553791 742937804 74036436 776809433 309587278 215414190 749492149 282578331 604851120 146412852 702517153 136923241 822404900 459297057 639525101 221886585 621803033 167850955 225147181 613186107 201314394 679477923 233117684 748054859 558426150 656861429 814511422 389678690 221012668 590788195 485140471 505260580 264307475 261037944 439922398 342577342 635225265 95254025 659855431 118578219 676623250 269631483 614783552 867503628 165259109 238635743 656406176 196411183 99673897 649231501 342316520 910494344 462735297 835761728 884283173 974182242 537833389 610909515 737204787 592163897 61173456 195500570 456283024 987545560 934740674 134296526 17020991 634915774 30400522 623591879 874449498 776141482 71160364 616509943 229806827 353455813 330799260 441731758 918388616 822759093 267381200 943684397 205563229 22656780 615100031 50442385 795806342 276722003 932026992 609491441 376157345 523586648 842215832 578103376 639691195 96172892 785103932 937786662 717108137 805676184 491034593 509804028 52924971 292931701 480718648 40575897 267166562 488256638 626156158 994668264 764957732 756154304 662277464 163327462 920327646 954144422 644107126 420376196 653659812 635967954 637204967 459320572 58634197 983886461 246531168 593928959 286236748 910785802 925836374 808550043 112215856 130075496 448767150 839213417 303582905 202887183 279055430 625973108 814503677 724761875 773885494 902782152 378105402 900431682 917367526 993517744 420612958 868561306 753615070 301892963 165731886 514595872 804396677 225004033 201871803 211396590 75388077 392608552 502362301 269310173 214121079 413741950 996100535 559248375 893695452 301592499 786947622 249837029 816186883 350426815 553250872 876756710 462253822 256083807 743636983 260165041 233987712 420488804 893873149 316260141 371560881 530623439 119847653 475000286 61942609 920881996 425514385 272827020 112554774 70816187 715091023 421708486 463731801 593829149 128861605 10640068 739105561 180511353 773649084 961853101 626466095 695803890 957770792 434355842 533843572 786627361 54375237 575431609 153216232 899902195 531255444 604876268 925327733 554089226 24323107 784728917 804706089 851741307 296220358 473658593 872269536 658707204 638493126 290053419 7074244 793074625 183244094 517088629 915204344 667809196 553097445 965150121 128080691 647732330 755269421 772642771 928945773 16470334 814350561 789815574 931495463 143820311 49151892 379527513 434309028 522399163 919733329 734245092 865261642 684483038 42390836 504068125 894170281 88815397 312806961 257026032 710381716 875772205 54057706 693973498 210627636 75092085 459273817 495643208 455947212 645964201 508761668 707750363 514168669 606415994 474743141 589325772 233262640 749487662 617225835 343721618 165707566 309592582 816061516 326030305 41233598 877058522 534151725 862844443 296645466 868581224 555933214 970312915 128124760 731839945 981444509 758089005 65941078 73722009 220842205 503112601 130127013 205939562 774634482 926498278 374418559 695004901 458935802 111393693 465284787 879772830 400241525 951010681 951245952 863245982 637912278 583750327 859298992 768705929 304257492 166271554 678893241 170837415 443702051 105579808 223447432 303654409 732783502 461367871 432279231 976390843 838301032 497624404 531527899 948163213 985161452 512196571 5570273 598133147 915196236 183420135 108567993 772144262 828076934 991519234 284625578 146256543 795557719 500539303 637454357 892196019 653100786 792253344 301209272 557643977 229064725 551773188 625275200 817330871 299023621 773795771 841454823 835122303 933969807 481627552 55865680 35467110 825381577 393684786 799077518 676778145 691543618 674093249 362738814 397697563 895631510 79462512 983563404 858439941 95698439 990047562 804008131 681309662 476117421 529008728 893382429 409928180 119897278 164724712 696799115 972401115 78497580 503495810 7176509 463343719 190053372 25804061 731840542 294244651 189736624 770398298 925648962 873858447 757664000 561009496 87012154 450355098 601990576 913167727 898383392 295373555 602143956 259026285 126331772 891364369 176809959 871423102 938072917 540585257 989159466 746144648 436562414 944880408 11675183 554637035 182910765 646481509 873399213 38831588 275239112 711211011 260553252 442029900 221700621 802905424 528915220 887689674 682154339 434071640 192853126 476069808 27685697 535996488 113110582 747700902 272138982 898850583 777380660 233382658 247329063 479307102 896233333 707231370 901978217 982162243 281398359 513605490 679986283 883192938 979501560 802988216 894655616 393035655 990879750 634238876 34984097 412931000 962298081 968216607 293127250 158265494 294613689 203895670 503297765 821938443 736712728 395653029 435835323 823879472 916333497 909360368 364794963 345469397 131835319 967902839 589585729 70951049 871182346 376047408 752759299 942869435 441950643 284118518 495996218 430999506 35537607 600305906 788038184 571926454 506770334 917997852 98638822 276600995 238012986 967394546 123321622 483397317 468167361 198289864 998138654 550354100 268553910 726157564 632345924 38740461 679359634 611154201 294690713 177957061 243182480 356750743 707516674 370150691 284904016 95123107 885299650 11529082 108089178 85592964 303252084 370397550 960047873 54994862 915723026 839755744 223413439 804139721 978682477 523181149 822168146 902429801 756929287 191989532 956609655 237498604 69657816 792532379 430816042 735275571 871686995 247104906 713820427 211330792 353888510 996831833 600308845 198173954 852889902 708426364 824891055 625853324 151762220 137955988 109258502 628564213 606016185 272829666 653717729 522920875 353853964 997050778 125575155 1477319 78415400 300722216 488838576 670985410 977719411 636235091 154708115 595156952 983466883 467574885 581047235 547440538 693536717 801020986 399631188 779010579 663243565 94644642 520178761 353176676 931599524 715948808 856665397 379851832 239526703 910900004 568961570 745753279 220443618 871519452 213626289 153083368 211143797 286727386 353186036 295316086 514187818 686893299 423619321 663906817 902125227 47002811 56545019 883964199 742671994 494544424 751142811 876110831 307002010 668339382 242397266 158781711 695225278 940109689 804306448 428724963 210049895 353222745 927843661 462621334 530084351 602986682 910348599 131409991 283105144 284043396 946483954 535444631 406335000 316015725 200287537 934349265 735559473 726578134 400202620 898049000 991784824 514716343 138856859 280728363 497997291 335651385 365192692 391317377 456407831 378542219 692612071 473415907 210528748 557739068 506050643 701249590 600087578 297494173 917015684 799841225 204901173 202340823 863435430 61634333 306997261 926964894 773913085 363880096 801988582 533418336 8884022 171106019 115280068 916520899 430194497 588741506 709734539 814422132 251017200 581023870 166004464 962377894 907474749 434198993 664457849 993167067 691795187 462924135 841705603 877375110 952238050 259337775 634293427 999119832 401921569 879824575 64089688 188628450 566959720 457443531 659289305 144083467 73866643 405484231 835153899 913713564 578624515 403760695 566815119 894196291 337427934 372780074 975418315 387588486 683605138 521367404 619520464 199703606 897346428 20988530 666150541 480521490 357634820 533628156 349663179 514637602 975249179 254159684 513231933 921667983 284086534 699138825 574191416 527807120 87693557 891794689 617240138 23283340 877353340 808616459 996133917 923863831 706431487 405321184 990351306 708271966 451171307 773030855 946081655 626519391 641597211 652033391 251543066 702067011 757996635 150744165 459307548 651980590 955342763 295531272 641215421 567009313 134697597 446819340 676220118 403025541 166266628 641762431 383099297 788513794 381251828 444894609 568434015 921033598 185547447 414661700 58243985 927529442 576441641 904579984 71477165 197118084 818445849 577113305 667831903 704824938 610145634 650016298 827231436 258201644 290965249 870168670 260120187 648564892 712765162 615757942 283804230 651318809 185869532 53958752 306974823 766428676 48065497 658058917 311616510 263562603 977001996 952381965 35251314 206790887 163839046 254736152 20412095 778731751 708714448 57606415 826547844 131021277 849754622 411101211 341581393 344454084 52912134 980871837 276497191 233189948 92901366 639644271 405719578 155197041 853989269 837379654 748831604 994505194 827829160 575551128 772220004 59275143 105197023 281593275 170154933 858761211 50485783 416849630 84859733 707388055 474487686 766029817 394706032 968322175 755323596 302368147 287546173 534683799 725945144 422503722 990140569 264462568 826836459 496091241 359380708 600133884 20834836 891855476 688506179 540531276 548216911 959177994 442713597 660401219 274553105 647402151 557318405 716902934 67517675 67291888 61810012 997669297 738926763 706844425 171623581 784998899 425152021 255987498 67520082 458965297 337467929 241487415 909098496 748540636 413705928 999033727 274658012 72727454 410171575 249491562 431268810 376611118 870436780 520672366 987756593 543987465 153264261 600705939 653668473 91176112 778437995 854901380 344061109 809274544 541759033 972513835 821416836 19966626 580902874 259086868 565031981 104634639 272071815 95732097 799818630 825684532 885537582 872600321 712072001 133009537 655790876 532002937 198808223 454974736 988642735 628495085 257735400 822670769 797728077 997564408 341871614 394272838 788371321 753671800 700426976 552185324 213117904 54144436 204472863 505510077 469987746 383803727 170371927 492165509 361408650 537439108 774021922 689621572 420838329 916112683 265518077 249803680 22786543 293724010 373199050 116587535 766003249 476259798 993983053 136374113 206122479 919211273 245645698 331399263 415338225 237491227 196654820 405095585 622750931 423222251 63289726 291702202 404604332 230770395 778258507 734765003 209718802 63866930 803123436 760253971 420611063 216894366 870142654 200398428 297344435 56977716 466797836 174150545 778891156 415652514 448361571 546797739 879169434 761832654 994219794 993992417 801056586 175732524 91639242 241146418 756870805 862454661 470890305 920406857 176871109 208645581 94796482 296108521 882374737 867378985 332502173 271992168 292440058 491714228 912699335 118705803 73334019 931851342 653525646 99385957 925085387 554440976 562560897 883970402 7208100 7225795 813365906 897098705 455291327 668388226 988754299 253902138 414901519 676434264 440047375 20705877 469062382 928973997 469693154 664176640 74511705 77633720 652565834 840946612 776751852 448197219 84835102 66300909 554557364 358832289 1016569 631471333 41826235 154715870 760481986 717888409 374107592 713954069 424885222 629490413 891894679 357520520 240748354 980863293 166478994 607485201 167493304 119198286 323663925 828915833 245505935 731290549 638728488 436333578 207624126 472385695 569132192 719859108 138244805 884518606 57469794 568983053 876908064 816044789 97914136 702291001 733310369 412355550 370555939 837176991 468347297 288488703 479308638 544675319 633095309 842902412 931067217 620068374 217719302 161437564 808267855 223229831 251734156 993113344 503252821 266102135 425320645 283481327 956118688 760563019 223796755 541448717 681469817 603070037 37444105 710305308 602088466 635624919 926430528 635021110 896003982 133319641 919430748 77712518 920331645 352878327 74030879 670024980 52890601 455045878 708893571 142046388 892765763 783392887 490496286 110281072 388044043 789013366 942310931 909366335 963112058 752591847 932038001 521150029 947916893 114573612 518211957 331894036 944529933 730587772 817616442 708098134 821955490 909617579 22977026 247622862 575870441 46882458 703975242 527309935 467561611 657293380 291264150 695062245 144893831 697004670 441543259 686483224 90422029 964106614 555563978 238985935 285855186 305229300 899983528 412310268 642575811 969741592 32773563 416350443 637273356 554105446 194680486 624892910 233632335 68067326 857849624 678803433 879139741 916601820 842690007 819354291 911394618 472557715 428219557 387942614 229013244 183320636 743115749 218005749 66399159 721372250 610221170 949810271 536081947 974783545 279763126 150042857 689616833 197634968 949672848 126796017 683995943 471099059 655320453 766397061 249458936 46094722 360046172 79414547 334436018 425996254 197783136 620703732 991067781 582930846 989099557 777455038 460596573 736747236 246640544 96776760 113395540 313804744 663099850 168993879 877148861 74349717 198244282 877912619 216593726 427923444 446355045 491744032 555247319 817573976 414755095 745228070 431112997 346448592 15318728 232636153 588282450 239991139 87222028 825199121 177009448 297156832 462783038 181614562 232550271 961057839 356849725 185649452 882048293 119016863 432978264 920660844 588226286 780185982 471952088 127052861 480072695 818363748 434615242 297016413 231345278 666587655 234160574 425912429 716590545 423023419 988388676 922744981 852289663 199374104 13147857 453517241 671177061 334712287 946854032 353048756 921023147 73604523 781462000 572091762 938022647 384550040 946380701 117463053 98251319 989595256 832759894 760264275 225463655 231588603 429463990 55141881 564214497 250317066 744879842 274300056 413903373 767192841 782304284 785117936 118758078 812978381 808715990 255713670 343740009 891754927 732793412 459892770 632205516 895458079 660030125 401615279 722231486 246440549 205469918 794332594 327183429 418243716 438248884 641194069 604166354 909842115 821610563 930874523 620728289 27828564 293470043 749123162 939123716 508625477 843271276 775447975 489408562 37438696 960106006 239232187 889705916 405364653 272320314 42066393 626231528 940651871 533677252 241793654 995237711 342085075 384660672 221523634 27216064 511038620 221029903 395054438 316422598 115991560 771864960 130933408 120959487 849761380 514300890 558199680 362130847 338104877 714318397 906749695 178117350 761322892 812896237 175999496 225469392 689675811 768848223 693740976 65050988 670500533 854010722 254214445 630623063 407734010 73396894 979850430 550414917 335218933 385789501 540953501 691751278 774049238 659136174 393611850 871684988 944830209 14529361 916593540 580636774 651580782 214997158 985955342 431360291 281134680 626357720 163066963 426273402 469848400 758479290 255521547 895933148 672684721 438638610 499385235 745130814 99658772 24992704 926977579 886317760 471937726 442136964 113396819 701032926 770381026 292031809 482630298 422296383 786188265 172872492 762632295 887910300 974511488 74351378 210237722 514132213 321161572 576650942 830732821 720699168 456608222 963577713 4499537 18919865 453361046 549698108 74765163 891086309 354578240 340384199 22150706 304690558 381317110 51986495 463638511 575410352 221862041 932026577 994896512 902990199 888394583 923704365 440315742 551016478 60516713 651107010 584916884 834823443 102768637 154154415 152547982 240672034 67929991 203862146 504660553 80677580 87047220 226957425 872763885 221311790 317132891 713986509 958705600 967149448 681928605 447189579 493988563 759181717 632913295 592854309 226388826 425581975 727036996 14249756 65291583 623794864 966336702 420969451 360530419 582423507 269782241 351654041 239175734 560952041 127020193 658350980 691816767 312796634 258222268 92995207 384034590 558789975 699194834 690199637 49242283 963331339 189396589 210730922 774913382 244120980 317651543 608801124 777222394 585826266 982086410 684344674 783381807 916624322 742202731 120297745 919900750 13014162 914610179 114402818 414334631 304701697 516215730 76434862 180359445 420077564 318560725 137216908 485863807 677190789 597851664 691493699 259212687 622923976 717333884 944062555 777499645 334998790 599806512 807610052 300711190 514968899 656331143 35377940 648804310 780991707 126868719 91930933 932559756 35228610 96756292 805113738 299044340 709480400 114295066 34000839 6969311 522481064 164544321 237076789 730981139 872163661 600645390 278080207 835765127 989289215 675276451 137187127 688089333 945182434 205843434 586353216 891582331 684044097 671281758 213501441 562945763 432012919 466484922 831351223 338590882 153456007 88781903 365330404 751012718 109514656 422551848 746517296 994906023 950476616 711056838 426100434 234071655 405733851 322718746 935777335 805338702 214304769 333784424 90063594 48615775 426247091 763704412 568526651 127359283 945604567 160779555 209160575 905235412 543452649 57559295 627542488 360152372 528147499 207275704 312042406 213357371 552388450 657942674 852295873 326468999 630868903 162659218 591154906 846184332 886029497 804435561 403837594 855921653 697737080 79896650 448728198 433105750 647913838 837665162 603339385 535244045 352627067 171918719 310987826 181016664 430042158 807324233 219013552 67314215 600108627 763685112 745247595 728986342 43158696 398885644 897888340 686305677 714598938 23488273 120096509 518658960 246271162 499108625 748141787 68672719 913386997 783608284 583774091 153091341 731259206 145214080 808214681 742498057 923856542 541343712 671352551 935944133 738546125 175766527 409947304 772912617 480685028 607681610 190129425 583324791 282530452 718182058 450363807 287264796 98066248 253031342 547572416 685731956 492342920 433867414 336135908 871309387 933962007 865852331 875110681 699049383 590964894 47393374 541337266 454931096 157805735 117362101 668579282 683974202 38110721 120840422 575831584 929626615 134905098 694183178 853419642 945979108 895398071 550897852 615661942 281885331 413565054 904267834 978006523 850727841 475168351 17479494 699293076 375802652 815746902 803145464 632798667 797076980 11216487 49653589 804313981 196804432 328930977 726033471 114205820 314394523 159427244 725378803 239045011 941366227 257289208 281288402 702103898 377038997 931491070 960154476 438791118 274082992 263068414 203233801 691023653 405748113 878422935 645933439 989120625 197819609 257918303 615634355 926076418 597757467 772938493 113870328 126109206 847282958 168044950 783875938 571547129 928468135 563647802 208182840 52359156 726911430 556679539 369219531 87823584 588246209 397603461 321695156 387899190 753621172 611314079 361755837 360089110 764907450 675213315 459103408 346517758 667404757 973828425 678493219 603168590 630741626 119906665 815166996 140166803 931735396 775738934 462977633 68539784 334185967 176724298 745805793 572487499 53145806 322054964 263769453 740061586 420069738 772039963 308295498 690695147 635190820 144247702 572099278 421257783 954631387 962844940 451696417 652257842 710449584 341041182 47976770 378200840 83684244 215618657 350828035 330345064 345059706 877477225 580889127 764731883 887202266 326499939 736455806 417054389 135199336 789046846 411728570 537716569 956835606 805946851 18408955 815185541 240226612 217558494 900989366 30402200 906767895 197107396 54146831 471572602 163696662 297949087 360361867 735169121 984800837 769461546 587253239 582312534 252658850 826502465 612958953 553286124 713533827 186828752 572399513 90172196 660458924 588388925 274850693 186913918 544537266 816521282 279766393 24000760 136211144 187337842 771791250 411873768 359352363 980237261 716654086 122614793 499819302 254493180 962584954 914092672 758459819 966536230 298895358 462543220 561216790 755535199 385528145 635295325 401139321 311099286 962243204 312117648 186683845 311663483 123032165 34951316 230968477 574259261 910548296 888746088 151660787 824876580 449214507 947622027 990466005 439793358 794896011 836535289 293971979 901321576 141642878