7500 1000000000
816518019 323150040 646477075 133341954 748677905 773849920 489509502 403706512 85074275 493581278 621200690 604418626 698305501 933159541 2004333 81067073 205037890 10151270 131641612 885906761 314256886 495111535 514514890 994603620 47809688 627879145 220570323 694503532 737445980 807065213 592308975 5510315 166328937 138946965 832162300 516634633 211285435 612204147 843634970 707551683 239790867 596707920 364833727 677484563 17363808 135565587 141592552 636004735 505993273 684350826 527389372 599099015 916204057 750266471 845217596 484071232 510889445 369165531 702773339 766069838 277077628 660076374 326170913 817166734 4894404 28542452 203654572 43211112 659685579 473491226 700023016 563197496 51530010 512559828 307310977 526744945 463613730 328831679 91745882 635371836 231971845 229781015 493856090 322841985 849488131 860131268 933104962 185837529 387010004 506838481 714547435 869162452 262079450 49078173 247775798 124846302 319410147 731586827 908143355 995840333 206329425 99004018 334899631 111612095 660305616 547469471 409873360 515075870 831700523 7378630 108154683 297333438 542034610 425150526 732364119 443363088 624084565 816235553 217186519 782872101 15372411 511697056 611860163 571860545 540700191 47299051 812465035 109668478 455590919 586862305 184577196 236072051 568719472 226315929 95772789 492781751 378342462 22562651 522024704 606016823 249947739 118572533 747778117 807572169 254070346 944970261 928804422 284288341 782184522 586508690 203147913 734182234 793918616 568032609 300824579 953559105 612944466 992716475 929523555 538892890 298427124 166955425 565188833 322689762 430073156 29760556 526140456 301306533 887802114 513043166 903176381 183623153 438936293 755227512 207177012 819713381 43906239 806258520 848124421 981776566 302434498 787469875 220389055 934212764 932099414 68929659 509427524 266819202 328225800 492331672 347512758 318697131 718266046 964329073 703378639 348480639 739742877 772597002 456322014 350590983 768140186 975562312 846804063 111540340 863608481 104141519 435682101 501702618 697135707 595944460 618015622 200884218 829012128 869510223 3899187 315379772 889901689 949478671 629366002 839211707 471672146 563861515 506535547 30081451 180282038 38218321 338252612 24290280 6794579 545121632 45058527 456325714 87712888 296229997 69881204 502863410 825922358 337467278 85577942 384883298 423792995 378649047 28578128 23949513 297686150 585264735 771387362 788789105 208771562 649382893 718431402 922954566 623354325 1317184 101443166 174212205 325309395 820064248 856028662 145222718 244989483 358235684 705429094 655700192 360217715 621740649 587363977 307851904 241689803 578224921 283992621 181599477 632770587 913627355 14648915 32558012 476846590 283688664 57113811 426330259 823106965 385696965 73905022 712455374 34900868 633384359 900113626 213965895 37957571 623201459 350798290 815552986 850391835 883909098 787767603 170346610 846540217 948589703 252911162 330266236 104235700 952973601 940627604 411512488 978031652 247163463 950486996 143324461 398118713 780415483 886819783 394556985 519813589 651007993 414312942 411435217 61432816 880344913 140453148 473256332 232870005 891635671 159608929 456708546 344005270 847378013 355329126 683572022 144192413 94212321 293803683 61576859 42400287 959280282 851363842 606405681 631025338 435487378 83282530 831189843 736303061 355551141 795207370 842657224 295359010 656361942 402558138 572669353 199691075 865071436 306937502 886902250 613183112 162873068 576277340 2298758 107849175 485107860 515771148 271970635 842558117 762752240 659867847 752407103 946152736 301982461 373879704 599767214 133923183 799727896 479339664 223473617 694046993 527804866 56831478 581394530 619313139 483394458 286969893 690077244 545471255 840606794 244090924 251488186 152717993 635545694 882248216 759276395 344097646 747829051 169279670 838558783 885431744 739543867 136214693 817028908 722226867 161778135 327509714 386609736 390105002 434174880 93590377 613774975 468092485 102608670 551549145 490688629 66086424 971378914 557440594 706533846 8568624 391748689 866210404 344608492 146980676 927745150 245653303 340780881 534082938 489379637 76810337 504441790 656267474 291801109 724339815 455777537 619555635 507618261 547409363 255553037 632533264 894895015 999397358 696719147 750024119 844911801 774974235 31952463 651721688 995473104 563947654 850771178 323256623 280149297 376379530 884585381 751571502 356815947 550296184 710337147 934274438 912972010 910871705 527215402 225950544 118175580 481677603 264038221 732676657 75662949 283175481 890362184 681973926 545289918 24114149 815341464 207898447 781839915 259436339 968054172 240241979 528395812 365621436 126630051 663227466 541316859 932431527 197338803 704988940 422959981 293535672 400786554 188549265 56764296 527161983 759675255 284186148 935871998 494751698 304957272 435960489 985696485 648954363 289317956 403314206 694594055 949997839 641123780 198895847 683260510 266823246 558790999 709757702 946681200 253001208 639113116 741206434 618979478 169946412 216783744 534867744 109459576 343178109 992731278 116225200 690246434 328081470 299158864 684822233 74426529 565781996 708301309 89946533 826340423 477848025 91291133 721907868 856839425 221566503 776929295 502683617 571064423 654906572 915723499 168787778 701744218 729581186 657789230 523444375 863461193 979669685 41359061 788190422 78724022 277465853 112137779 996322073 640652670 944189497 913169917 717149256 600944951 125745476 472029827 733944675 642696114 857307641 295542895 322411423 343144443 588735994 658041168 107168937 336400880 508476747 981200534 636056333 429374251 16224967 504211617 942097627 448056138 56520930 424564138 354128202 542619216 920138697 662809294 237750212 954031233 500042412 325298702 361354070 909857036 775693703 798809878 730499081 794911169 758815286 859792719 41760908 987045621 297706747 863158169 581676225 180559310 97753194 944600838 493756101 576430348 582257368 659331381 22585223 439894691 97680745 232643131 347223995 104641827 647405441 775528561 10542510 198051044 665108150 325257363 526475690 584503599 183233547 857320109 726596966 870047627 934571736 270555498 445242583 166012200 349798932 478932186 299793883 698116985 765502190 137051112 435352898 674821279 693768461 101965129 672905998 880590668 658385734 235725179 934686376 572441072 257806804 891097403 941463463 522071664 720271649 992938803 738041213 145744109 863720454 118406994 991991014 37800641 334148551 356477779 417608783 784926069 953432695 294113016 877681197 388217976 581211498 927518905 286732538 961033168 425803613 498284042 195375778 781500279 94032065 234559806 880480730 372906979 498323873 686657232 359562137 765128615 301754268 294796502 732689572 465457465 467117438 957578642 824834996 730740942 420202619 296045352 685536837 411142754 357199623 135381097 960120318 164700628 48652629 144451277 291427000 533056813 253390185 423841152 686059308 358208257 483903196 795648915 861817406 329858286 410018348 614194003 913796832 610601025 60448701 575815351 358569636 878542521 955909744 420515570 901643490 83499363 375155167 571736873 563033730 939925567 221518439 851039317 351164833 308448715 338047097 125002504 672634246 363583019 306010444 190209897 353221917 393163186 59390066 302835904 628665308 706020605 784450394 912780691 941897065 980699235 957652195 110697321 675985725 807763841 225195987 427288087 85268490 776028320 784383372 254724733 364389150 149145505 992280354 400279543 885243697 693108550 275639751 243040055 760588501 496387289 817545311 581881834 532887487 264249668 75635131 535993410 485939829 7301918 537715027 76968493 46023415 704013790 292040388 719830468 896680108 982146996 151906129 34529977 639616680 555357480 552900054 135749805 824630230 132714443 100726335 332327731 698054504 125432676 865098847 702295068 789895244 367553786 349307860 131379895 904758000 974174900 803735597 22586856 363387371 467475122 347058801 821549535 271767511 262632637 119823814 536487626 682785108 282358556 237362756 879609923 295480614 253158677 930850533 988072793 945062010 384388867 651917464 861574970 604568390 370500113 972759668 690593402 155013838 446018960 745236746 272654594 33664066 307674107 353423571 881461912 212831620 285169540 474387400 41165318 715117064 461699162 756199441 701025002 508447701 499843194 749426133 599859738 832376488 196241199 130312240 978624689 925751095 547555880 903176003 71221395 399705652 881154916 132296312 60812710 48861084 939265910 51174224 173620765 874163284 471246165 184510431 961534592 533703015 682016365 721315706 866136024 985901144 698190884 639274911 967602776 319815134 272330509 650278276 30215118 218978000 801107943 392732096 687291319 420952789 448893811 232137505 629887475 691669900 285184827 527567792 176761374 701600342 609462114 362355438 637981173 755611667 740684253 616660178 715550281 69486929 787026314 817251423 137687789 515477526 931052104 487385810 399400285 209101255 95768002 913494187 738724462 913119712 71701625 919083198 922269193 465212461 350911715 393255720 792894446 128231521 108148740 258005703 806141561 783408195 562546937 819795143 507008101 569747781 661522124 717237425 303372229 965153258 977630137 278965919 83132895 429242220 796548380 543524313 184711148 226100369 112653622 215975599 902558364 97012749 938998186 255913595 432583340 99167482 495479488 203538470 701715011 375960109 753638231 153934019 878085284 531908453 50043993 216448823 687383835 173975852 163101886 763642076 577842877 822556924 915815070 154210481 126745336 557114270 763949723 652586772 108749417 511214948 647609486 619894792 104243447 304859083 244019184 743887099 735114186 434499653 188103658 765480861 610111674 619776229 321206842 557542369 200122786 80093953 568895132 124051100 591062819 266219165 866587945 488272246 780742738 179298572 60613647 587203911 969026576 357111695 86211626 76348401 664236600 398591418 405810006 678499712 108352848 634578859 721372088 380378799 424023018 338032471 142281124 107512708 487050141 911458560 635980334 711347222 836271515 17398467 842101840 619746671 466399983 854785869 523079861 414951052 823619670 834162606 756278304 80058753 877710775 339508293 26207356 327595193 757152063 701141723 644913280 13695579 160721437 327683533 995818494 619935177 691857623 537920608 842479817 204316482 808129863 779956793 979509313 12902823 851269174 743922045 371859035 666999444 435170450 814523923 840568131 997660753 582726880 315904902 178372845 587282138 681152722 795355981 817085133 620655923 789612254 366625148 293903777 950554029 382874661 536881681 306989558 66671429 987051964 715669726 245290181 452829337 170674473 869569550 636453429 58925191 793914858 49132373 937484932 225767524 616092206 333845432 643800832 770913750 676450471 236175862 345821487 863558735 641068919 341236626 85224974 729755686 106910791 926488190 138884948 302744439 487733605 678770075 210062279 253216367 16273557 244825775 327471974 936261908 850837896 702459044 563576738 82854487 473608462 98929333 312529531 531019015 692441379 603870699 440316649 502472313 879944254 721795683 193169454 673827226 386847674 521968127 511119972 196839047 33799534 863318812 929332467 43455869 920822436 883562918 705962371 436717887 532215460 218471383 204631216 491286490 278506269 563790811 969804672 103057690 530569170 124845059 372410048 449188037 214508413 510748189 645086278 574891437 476218717 379602778 207300964 197496158 954487860 978474911 363462491 486197225 62677438 477204044 118233795 882267373 428199765 890393266 267003526 878144632 797826799 442198997 362697257 830398142 387816151 805523519 633223537 285784480 413816963 27199329 875149534 562311335 541387422 907771347 841827272 903987212 266203569 225781269 658062579 698667373 485116224 786917269 985955001 132108951 180797255 834449250 964710288 598390811 794179191 36008245 527106944 910942298 929511923 132150116 857426975 759515130 895063274 267163618 27033120 308180323 284255201 293579353 614716986 167300279 781178756 279754804 24391891 398815537 863652189 38260695 240996940 924554923 155353651 51699951 978711523 847523129 473273341 363665379 787880265 431331059 363545473 953493609 409384129 250698705 624872846 791642422 139758065 803230126 241668562 769571533 106554185 519494255 356216153 656920589 815400509 277578403 86708310 462413568 533312493 794040160 272657839 47810433 6578634 107863439 631692887 565400264 34165151 217456051 302072948 731166752 54282938 977254375 745102684 381322573 342628856 914004162 884292800 39289277 347561395 361871898 922606666 576747276 34674250 534809914 876076277 865007211 452231697 472278897 779671756 951356456 250892526 99137951 444818597 405343669 727949334 330994948 23199366 206315316 421841993 680895524 976985632 914765189 625919343 298173190 570341524 555401279 246075565 88780051 857563189 878506745 555758864 693326378 266840769 358827356 899045526 641671496 706872255 948531940 42135143 328195027 402355457 579264563 142684705 831878019 667976009 673454098 384742481 680681198 693707528 748062213 714225661 788525230 733934914 575992457 315975005 902769805 476809452 614863275 807893788 56676919 164543177 606116368 795739740 445475207 3942175 245556157 616803787 549012252 732488461 362260251 359179644 635338867 940762669 89235482 126805924 799377284 32141450 672120742 185315365 931133579 50721343 57879608 491110072 344014308 718210221 782465417 348322229 192526351 393614168 127152993 605838210 301246420 770092639 747463830 619111040 114796182 729682670 176058921 573203021 646159170 770393518 760125818 152980703 15495536 541666958 771743676 675354603 286377714 981773659 622536350 857086450 742560503 934809216 893067563 673438644 864101503 78142743 861219283 52516014 687301774 231607755 529554379 38448015 575280596 415473837 292342932 630033780 1095892 947830499 439281324 231645327 519887489 334788735 227297570 580939037 264685236 374161997 248255522 459804481 595499607 178042396 397346876 665778087 685969828 426179487 978990913 812456892 579287815 750255669 350099050 179007018 687182094 123668209 159087257 420855535 364215165 620281666 1395895 206162201 855343999 993631300 709230140 40594464 435712758 560716450 631557580 933996768 611037939 431235365 825820671 294949937 770964289 722774494 922495545 264002340 321004316 600225260 627476408 838178013 981284095 153923563 792596653 589635592 421733275 981311225 665920897 805299193 579699171 963102310 257276772 537483332 887372791 653591027 736143029 714053875 693841111 87859855 814989326 946970462 112102683 578224235 329158875 4574404 734007792 477986376 872949522 415613920 64773732 474720585 149855756 961896384 361031373 299525913 949512955 487246773 448021722 330336299 358210312 732467299 430309940 44237341 690093322 144001016 549139920 432421430 974271204 281643386 801463764 718085134 675091579 691734840 272297507 93890125 419629138 889665122 570909063 152881547 584371141 954415029 632102266 142793047 673236191 41851214 716045969 498103123 537174944 709205628 827136558 819477889 967776992 544391816 529751390 127050590 423307585 778812264 734459279 581713996 267038957 701834236 6543814 79972912 927304839 923559852 714667936 947593686 764466472 144515984 36079710 804752803 599526727 639589608 802503085 722377450 481271040 887758706 798946209 434593266 791788120 847874432 602745793 661340318 877098399 556080052 540413755 471464383 466459630 57143387 45334072 664756467 333656016 19098724 496595530 168041783 942660093 193889282 989258769 388466753 235620551 921197983 997854547 415691388 377323452 19800288 20821388 748130242 110602909 691228155 331324689 405705122 589329682 98506150 362484131 318635908 598258017 482113106 981447357 214810156 982647415 873227901 551675739 242206730 909414188 418077269 933167884 557338476 204328444 978432446 875494716 309433597 996611675 267269359 308786925 799331371 778196287 711787566 94915314 73450968 685925951 641647352 435284405 170243106 11113053 228988775 263423920 663070853 83931942 479269201 533587870 153269298 31016763 594106371 138256432 121998796 294087233 135963 484663164 389364986 779411734 272036935 402709974 380510844 967930137 463301368 973903562 222776635 417924627 352425074 645256782 942841933 936929806 219693374 896890717 646820861 155037130 746700043 514523385 863271761 101088844 384152495 698362548 418510710 680157991 129952740 959057471 520116892 49108497 655422885 573253826 975048096 747657265 538418640 207138248 355545645 66167552 734863375 740173920 239782493 600776567 361289654 582167196 503821124 633841433 936968422 151778166 166587988 120666527 138076502 695551524 493164548 36227685 41686336 700974150 264706138 211756144 283180006 772014179 134112216 682847882 948661838 806074624 864095352 637466505 950318127 88459171 644386541 18742633 557637125 395088514 631340033 47058949 99466308 780469453 141439005 559482738 505653160 764660629 805231608 795063979 178147672 327476998 166179246 622743056 25527338 83908609 687264177 460988573 194869888 808796229 729854720 315480038 370683548 739791173 464547575 618938435 649563281 578593639 234744803 444740338 288414734 557376590 425103610 854806043 601709772 612464952 609185558 194351643 778357078 401207857 401700751 489862811 310435429 959204125 211605809 465955836 723843159 345732228 867698396 563875407 663718330 950529642 691089081 544096512 39025391 592911850 272448849 357211164 157124223 775201759 447270337 474215397 441775490 395387041 388166539 105488330 23407666 343956412 630760005 829433885 691455303 655777223 522146729 542163870 708826601 768962705 245945713 837356725 424944991 524142058 597166427 565477963 691861471 523076875 930987852 275252805 916159619 648033955 623827345 566137245 602591837 759943551 880491328 536001055 164568737 491013076 379263677 875984318 784850220 920528985 667239824 550070550 953478379 178745108 430729325 700010489 338280318 140356995 22659871 180830962 418104351 375475405 500636230 922041416 148806 467658191 217193931 829199159 450594735 105412704 866613247 940424192 67456686 362236495 787553050 869050152 561942215 645872550 467757856 912819252 772360287 208225856 831211165 59619263 50871781 665112273 794320682 479569238 718472170 389977346 449517576 715570496 530635691 378839839 308268588 393805399 185283241 522958852 828875169 23997780 282247662 647613348 118335535 51128266 274853809 443248656 293974028 681784343 642434503 254550602 816358011 679575646 247114762 614877905 760397967 836796188 667280885 152232650 264416782 495032681 94353234 576604621 842186864 788326922 846656072 755136519 9180349 962117404 840980116 836566328 238934449 100739753 828340370 116536807 249120227 242594091 84933121 118977777 114474917 289229254 786953568 101069778 368986975 983458231 979755898 696123496 635438885 294557929 955135891 652904143 405238769 695015846 921877037 853720938 983085186 224344426 908826743 453750019 926098896 948416723 240628307 418341130 772116266 710014645 91650819 985740282 618592750 500415051 101369967 240233945 106264293 69141640 28486933 723816670 807019320 552335499 331665037 114813996 47096595 874853168 579959480 33537213 62396867 882667098 733076977 498237903 165030239 802571462 74275940 824687637 776759 417648891 540767187 746205848 222569769 332930700 399789376 63734741 969891533 104720681 677666920 405662992 143317533 663348289 564091325 401835978 786068990 406969538 850134011 15733327 877073773 86364924 77952361 129034603 771488839 368776355 5620399 159867197 485064884 701699827 389433678 340185379 790990641 43086062 188589503 919798485 463760697 848398785 191039788 973068942 926681744 678334277 414435525 302407780 48344364 478464672 794947777 164146112 205831922 460053450 203013350 873087664 448377602 203918948 399050472 975477327 993670071 837075499 368838958 554751329 839658051 975345208 586505416 915173636 620675055 274252648 91810749 371835704 516350764 388879504 686310031 718497158 597161718 617839776 295658520 722767003 471695816 311003118 528983332 132287575 62359805 226976500 704511090 428847579 878957266 132077671 661211458 874463094 231542555 10557809 853880760 691310142 56652396 548677557 974780011 926446057 835244708 517221412 340894873 143654932 170309998 418827866 189160315 847321648 310607075 480829335 869291700 689981961 877215309 576847704 470811107 922020596 626609927 734781841 42027925 185088384 110930058 43108834 553030219 264445022 219845574 874598456 719357887 377968613 393759437 295662320 644811930 711284183 221767541 848587453 354607684 261741242 894837575 844375948 61122063 437479185 90672200 722058873 99545357 756836080 134560137 918260722 51735026 656595247 345436377 779914 122244887 688706635 877605531 790775003 412225202 174179610 753198506 230925208 77906609 461695939 743196021 696590478 263483547 190075766 47914050 648148462 899282880 756872390 341580379 683464348 273354505 196166417 574407910 337128347 977700996 788116194 518344738 428214460 366165293 394350844 163227456 727144048 126774623 659903350 980014043 929655999 403191767 399816448 478226198 307874130 790109024 569260099 169969745 389136042 56078113 387139943 763923847 624328819 497691519 951265096 294399731 297801648 739621693 677378637 914979229 863454686 182122747 435802301 766901954 8579059 165698706 459406439 445064967 697858090 924680241 174985572 108086966 708892222 694915197 576258866 527187518 845366208 554577860 143079547 221208862 484369371 62329213 725276588 607196305 50873440 516270198 478323771 994518802 656241972 648937825 683239764 542127440 465216830 192547602 165888386 200425736 668402070 566832281 741024077 337648820 873337142 247053726 565821017 524074969 764301589 956460281 448620535 456848663 713756569 291950378 282495599 891999389 902988636 293706427 920421646 566578080 672927171 684442495 664795066 358257977 860797500 89368140 281829303 685414167 5005766 446579991 948095523 574702590 136985685 888629948 755984322 573007890 918947128 710692619 959640886 851249843 492379439 807729055 343951757 477783396 444143367 102500845 324767787 188046004 537066413 55487902 833437176 268961956 981445029 406954952 510646103 182284701 868508006 567352991 963135798 202759646 310660908 678740879 540358768 274449632 620806374 605221329 59343739 182805626 355640002 141254272 905875168 534138486 629933454 7814541 654418427 251903484 393773037 757446592 662388787 913568085 266070512 244936017 229643047 246519242 332034125 54574487 716454262 997184427 622159166 174887896 499907627 141036139 667563768 967242559 93318852 708332777 354893254 432405995 362014685 606869450 699824066 192672548 156112510 18721793 371045936 271482024 474617712 893196407 616219428 946609297 898174888 695499198 783942773 997055693 969452062 585426639 113585589 310069909 270103470 168583833 411319349 887553959 952895147 425177024 974535878 576230411 523162725 63275336 245595129 135816033 763777404 131146403 24994823 648671674 511340483 384565484 502490013 811278882 21618366 835459964 586336116 261911346 944572356 763954640 948006287 450968259 832217807 64286600 452464145 691784381 10088932 562623116 576066488 871644941 223477017 308333385 939356666 710407349 827416392 39691545 135596218 811624445 752340815 477180609 407868327 354275783 53923840 397682964 938837810 758460076 282390452 197035817 336806707 546147832 656745717 251350327 129751352 642739689 71088492 893266697 971873728 581675367 219279956 561301940 241303812 455396725 948392044 865295544 976809826 529469274 271632827 680271722 200443582 168445348 884721513 593829003 880326410 354629634 270233168 812065589 628043504 594125123 628500786 546629738 456038051 665938416 277161315 51049244 134592047 455996053 423652321 85494180 35053277 369402849 209729374 720968708 172063565 974178230 822373611 564561477 553803051 559837023 180372735 552983185 283150512 109128695 262585706 816863645 424078562 192293853 707014374 257107385 676189933 246395057 722792389 610152068 459587564 195151356 302446312 64726056 736272854 10647324 88618237 458672020 583356693 730787348 456787432 576504708 48010158 5531211 308026343 714095876 825986038 135414922 362690043 439770836 29625214 160327304 988240288 275224836 95578530 580241681 364911800 214779944 332469566 196264658 295995270 834451001 426148737 390483907 290739413 643368712 662085081 3237169 127451193 546574943 643407118 231672423 920555117 321787830 873048427 712549368 895521755 982759311 861373974 305163692 748984635 755212399 936449409 674260229 288184915 579423609 400534265 995894381 111569116 101413544 984367964 761460989 422383493 687250600 952145128 362301164 593640721 623480914 294080558 671518354 162779547 365985219 611736101 594913816 51412986 341969687 845055322 868917183 900727103 979374279 547404869 456156873 639437915 51502855 918468062 780703823 960526810 776288960 102601422 809625275 150787046 97219279 299401631 52503338 413423422 982031065 609963799 964257843 226346248 658452946 210366685 364920155 250644657 444983035 130102336 77533457 958235766 720341824 783110023 612936853 292134399 170629170 766032003 554258076 186916235 72026112 8832196 711898456 706574976 573499916 43642944 328352172 672749825 377356657 123732186 695940359 878219363 373968545 953341371 181000293 921148085 993662687 180489573 405463524 498925455 782526687 551187908 595896011 398050766 618121485 717274482 892020174 482846368 240618224 479815944 515308222 969959103 508660572 145775760 728526609 574243253 4847615 711725807 457484730 722804739 649246097 491204676 60972867 158992745 429975089 725659033 171237886 444812333 230126574 531429446 891945810 516035338 927662647 827153336 777621114 594144743 154964668 247009300 226078545 938776545 234687685 658179565 753524537 377589587 778347987 761860970 810992090 758857767 737491995 242579573 827416783 291579385 332399258 567607618 607814396 709722718 529126622 12842232 53472228 770032924 397369963 285882022 275490530 886689625 381788751 793103629 846024155 964905361 483513114 287496611 663830832 699423357 132312328 241164829 370825718 620365061 804330552 207170027 588386274 51014210 93183732 980198497 97222190 110880782 763315909 369750763 118463333 324537150 726057369 879155372 823164551 932149025 684975893 993195588 728410480 615525369 311013549 183066697 769500529 630909601 295727043 349645541 477145644 94784641 213461374 777737785 31078076 685271825 893175218 371015021 948992753 121697516 699818238 388953176 62511800 406867085 385332725 815326153 112731546 148312232 862909812 450799216 919532123 631097895 643523091 826957932 875889858 909036991 419078327 892948338 869104505 272011567 874716227 378408342 813624330 178952302 549914810 147859209 272383632 399983185 648900262 899390550 485585741 977420134 350403939 306948789 590945004 165082618 678064331 936312955 250050331 478344843 736848781 822137120 290719174 90285865 78452083 944268668 685382207 592341589 33933218 637871219 416056583 479491589 167108204 92689611 923128380 964166341 924598482 939153438 844029598 428900599 962163097 804623595 805360959 950123579 314029063 859329478 338165191 709156073 590318650 871336880 832730977 412242363 145025318 606751617 184056902 768163720 310325289 811534465 206438884 526019149 891342359 766167466 480325506 249997593 818537625 967580787 683414931 441525012 281832770 438076556 172480712 657361367 770392897 445635172 716650331 832512462 837039567 877202125 461782923 879473687 524327927 583962255 262603385 664536543 189523652 480490741 413922635 333733269 273452318 967263620 750765811 609532916 418580453 761526706 223858652 493608211 473886486 555898376 486809439 37667662 736710568 750368117 43415006 191317230 912323306 164804619 224692720 829195896 961996807 596366672 348650678 620732815 322559916 967498306 132748108 831961222 41509824 717672171 56777052 441883270 919762770 166008220 446830284 769112 19393169 75687881 295335575 401756625 526013684 153507457 894110905 547320791 632649594 673649288 239121732 969460499 789354763 118742034 3020432 792735029 357687038 732614686 633166991 557183710 507873133 142269759 394362415 509615457 534978846 620624440 978346988 597557483 729643240 712194917 403942220 639804138 143282419 544105167 127864415 882004176 805703573 586797340 654641442 298587910 860116964 282889016 615270547 580761467 85692948 263818 605040808 381731481 589855052 452101148 516500373 194505933 959798922 700185764 908611941 128412921 637927693 873021885 545984833 752423510 169017540 299107465 224508019 194257486 309240659 369825334 797455377 606530438 977660760 298462846 691393788 442674072 426348753 692894396 421797566 799540141 987410214 786841971 183820056 546063906 657449874 638269525 220481568 738670735 834950757 117921507 259653852 866943598 451201512 431448750 919734326 148339408 142262214 332421568 961153297 123573588 340268256 619730857 676982663 627594558 815185754 544956711 362186315 812932655 759571919 553633905 522232878 56799879 41465252 182941216 510177213 35024212 349344378 131019451 160489223 142750197 233140413 687852253 78551932 970252111 348317018 232597509 562971120 895293099 936894093 108410362 281567423 670267435 669255128 435619545 603581451 259575015 35588879 606649276 586960929 876517008 564357641 747459066 542533441 647838353 182612820 312920029 363815813 597211026 276940834 66188264 685068273 59158555 581115409 707035317 220725916 455933371 484217576 127929321 408050400 870591189 54373627 907544747 7651680 362156180 306158326 255468137 306686498 927558896 315342654 180110736 578652100 503532406 426090471 96735692 651901892 432461342 608405129 319734813 589023727 725104509 822406020 724173777 208187839 37505268 173799282 163933251 920497793 675805893 167740934 434091369 891289023 672476112 285415979 958861271 358598423 474318070 997251014 365899322 38694071 961035526 187735311 420010586 942074914 522203426 762893877 707547487 484540581 284247685 58946812 221042996 730283946 758881886 639500705 883284498 757320926 538270782 655906623 879003053 15024120 212301622 982972286 694138255 144349508 449977970 473085954 479204317 201661947 813646994 162519733 855716621 727177036 814186303 106703247 698370204 57924501 430570461 417559515 177176950 20686582 62538569 990965484 786486568 717360572 739971407 46607414 275548011 850874476 998895626 280289429 61345541 255255238 817575095 314782792 263859624 765648421 63385525 459758183 307603439 459610929 928245119 660358013 810534407 352283346 707522841 532984847 227852907 963528912 723312550 925666253 627414215 911086089 238430999 776174420 666637566 86493262 317286910 772363422 277506119 545896922 480132736 92093447 628039282 548293743 503676521 814795772 630457673 30265359 107465818 192789009 743595860 977599005 11456816 227676524 770254361 36130987 394745320 98873269 333665761 415611457 981783793 995358182 796350895 827230469 920609318 717003853 723816491 131523557 819393301 574242524 481508436 815033869 33937747 805012709 724237066 601510725 562183354 846663639 74247751 283147294 953583876 139119532 632417278 169636064 62875088 150100722 969032608 152119311 71214983 123908232 166165790 322993953 222737058 127679705 441596049 685042665 947492081 399368544 954993614 67787455 976766601 569734183 421491839 318760096 486804588 443485498 986943555 532073380 903236255 194065030 524088218 365685793 753449562 688530611 877784435 942480493 40996772 966675894 350940353 315490954 706345090 851376669 278590265 999322107 406371294 84809604 912959479 916813379 470424658 161826828 555751784 778041122 385623867 994345398 563832478 894926729 317950206 355132752 796473821 601777392 140711001 406923351 679409457 468791383 167254741 505118599 511280444 661694552 849052674 538551310 181131747 71801814 926370585 259165228 832299297 812798248 969376441 921652659 527994847 360836085 506703476 231322007 306572851 494093260 363373355 94742788 519937460 973632340 369722710 266657509 410167758 808684699 645100930 176675270 980285066 221780993 206381124 190909515 49525114 252528329 385155476 519612085 855676639 510886022 495106786 336011741 826957858 505306083 176772802 325009559 492841613 258974717 694531536 742898272 270747410 979612148 4688961 13094144 551436232 202961869 552015 271779096 925224375 397417085 228722967 837043925 497614440 229430549 17985183 490450141 130002259 589229408 565975771 151621309 867340739 986429649 934016181 28533958 211763010 755194777 184284696 681891705 647141791 897204627 875183749 563203783 650203163 264642292 945723777 642531459 74271312 736704446 62985207 862886541 265232205 343431025 723818460 399719441 550332701 423565962 35984161 271616617 254273849 86915301 230569316 599514801 977184174 65597501 746865715 65794302 690307995 179864839 168608774 635274195 47635820 616310723 919101635 409872766 663332384 930035429 729727249 193469846 703565052 497961734 762441657 69593317 996477764 178480091 946011507 845904738 189673310 911639591 871387200 241579450 794532542 459053788 114063716 112915638 924375884 170690940 649824111 923203967 545208243 794924596 62810865 874070616 926806597 957490930 543853077 763242647 930039408 20402280 403157056 396869967 794823913 130369208 94180159 87338332 876330439 730394903 350867522 596726084 872070701 451368241 839520723 233029739 574399375 129562443 274098958 429781812 264027124 771347678 807797856 712689889 253700579 936219298 307768300 780080990 767158850 489320115 567609525 373153766 278047530 570605996 74789495 41068631 798912358 807287664 587395228 725130478 443360428 428115267 155193832 585572146 14672862 435675801 257355983 25266023 574406242 427127735 107661635 601510456 825121087 334586876 427098354 641758234 577089246 263108999 137151803 87569598 762059413 606883573 161890208 896372945 636377416 856783583 780286909 720530400 657335779 252008966 654053473 153383769 312048305 623383222 638091038 311800872 156471910 591205719 383145689 723487546 523070685 622914563 264978430 823686337 226143137 56932826 874312659 217251364 671454856 475508739 33784554 511729287 304415864 628117567 294638768 59571698 959426859 824301091 608064800 742575059 979352594 670342561 571715047 645779182 3767916 705215963 650116670 505792248 122113008 272427403 142211185 738396790 903680732 862478133 131215343 27840027 13533158 372996072 219329245 534825162 316627582 851838804 316790419 532689611 788665004 671206800 257963102 245100147 874609317 368489557 387470002 467352586 271149468 8318944 992101806 255293204 915638743 110221764 328106778 14387384 298216420 984615906 957170276 181728516 343062301 557007814 215904758 446109911 962688589 831355808 62173600 659177583 646370925 531881692 548085812 2965648 117959047 69185121 557975629 123752892 901321315 858820503 144162678 212104801 664740838 617635546 796120990 233743171 692339152 595803377 36182983 290046987 89651112 683913357 926590636 932293053 508431857 239052391 927288747 114674778 630634525 438260914 373874766 10236582 759076912 372663216 42042485 844802035 217124193 471476513 767388797 402359760 579194965 124941279 638339295 188824913 569778595 17819855 67021058 881147184 957451250 660458534 689444634 622348724 349666633 422891896 415024389 555394675 387148567 830265011 591030314 836103182 146874083 753604001 951018414 170187077 278306969 412984240 229867364 336840267 423006768 923108593 275776761 486180540 420761165 206217115 345317111 503917047 593774753 189642630 94550615 337686409 494722206 84358834 986961814 786024909 635390460 478990235 122219672 360701962 659050053 540266927 874521455 516934823 384799460 68101513 113523339 586403180 279030393 975882138 744452518 728386845 984540920 930588935 161404987 867904898 469797535 854390468 41783372 253632525 691265842 647905745 268182072 5002092 267843203 13523673 911518787 182065652 557975812 56636156 53802286 538323770 225161965 706358440 788118642 127079430 539302937 907104717 491189535 912569402 312287318 581341656 56436501 940211215 812594968 777603278 271678352 489241780 732213959 721409381 171414326 86113662 341714016 682747883 80754166 595413659 220701217 708198047 261436785 64217725 49654619 34941201 164944137 14050637 948295663 337911498 632046102 528738167 797764333 160308610 691123772 85734191 535675142 515892102 741702120 429122120 290157791 492345879 511446415 673537628 268225863 464531454 45547195 639575008 251272840 146765777 667461872 752857047 736215074 271023867 705318892 409179854 995692930 312097234 103422428 557289149 530349644 469898334 328914602 962310740 624934676 432014014 163018422 230594879 48799956 822031304 143105834 182109069 741119080 727986762 390299726 68486566 464294225 334060495 89113307 91816293 160996743 860012117 491735610 920699862 752444165 238708101 854349807 29728266 671083465 277169544 632543859 323194490 957667321 797743491 998299424 300453142 123601329 335806790 244387817 72282005 555022108 409972827 875087100 659851086 777321313 598007526 823145884 576746748 509171059 79599252 109319454 824897468 19083853 216245977 102203273 736973929 140844829 52483261 431638159 79503232 688663165 134049252 956132006 323531148 609401616 691113179 107221624 239657797 957646182 499230694 53210727 430269800 316234906 354624774 906750622 258875715 218966469 99821432 297036769 338712464 847240454 116068995 744597358 501976302 478138294 724303203 16244538 941607410 229538594 278844380 549393482 757970410 959637578 998287219 95950684 269391650 770387976 850528763 540474511 958912250 883619855 850924998 4727928 821601811 42400525 551815197 26806164 903855661 487614035 991941825 545003419 300161453 814919144 270629383 43176088 27910507 2514821 624547513 108661014 40546745 344581513 539601711 902405700 777467181 132608563 351925864 933753882 136046082 542349870 466975003 572797333 600920406 416471822 451734698 922408562 333469926 97051769 968818323 578947264 424701645 724456387 77289729 524844800 871692651 973032233 805178614 86036321 602080935 125180103 410434831 310802872 768512630 433444536 618480750 231244833 857147174 646823271 325767573 726802263 96996179 94069836 917059500 583517447 420908701 429255793 101354867 600460460 661907385 986833597 268587572 543484844 85462714 336191407 991949991 250484525 479353975 449723954 337348944 587042014 172872385 218147709 815815141 333685452 287309243 577443891 288952393 394127675 285623749 673779243 432358591 373326057 419911860 761292869 444770648 239953091 939144537 580274315 441028682 285133335 527952235 917097870 474838091 459430638 359867606 628499048 594136675 657824605 330926664 210276093 523361248 590471851 407822504 462623660 170700064 168348489 946323375 127385706 569110239 343473314 932393413 453764531 336210977 704114524 686589406 724023836 748714810 549411304 813478596 653610839 810894462 807186232 368542705 630690706 673334280 250295283 437482798 183868486 138341667 686291754 748794400 390573288 703279509 581769630 716095377 598199620 917785966 996626806 28111640 955662048 563476410 328920944 538935143 233850493 561971424 820250930 296055601 850004411 756827802 613275839 339488438 43297500 726054289 870564101 829907436 444545697 16086164 681295762 605517643 438228560 321070453 702138727 472626135 465036672 119250149 762260481 168669706 914093977 476996836 449518755 20860681 831373297 438452451 312807929 597190845 779140964 220116057 809768116 145889665 554116722 536675114 418868705 973683933 75079641 827571509 608847891 337084013 144558283 70782218 400432431 696382688 782434513 556721593 215158996 866347804 883827516 679385541 216101733 523475327 457372739 667523384 881649076 343716161 357601214 298031824 846128972 43156981 767091582 534608983 404089691 6334254 986255687 124439568 731125306 26152510 706387051 425838925 265327003 689146906 797272836 919812126 398688078 296587609 299556045 75295780 641185456 54730331 605517725 911024259 831903408 640968071 345917826 829245173 813564332 443890294 936303612 954946260 314964617 490185152 87238617 28268392 745018090 125245622 349534645 94509540 471621210 491972305 554990007 529144524 414100368 275780754 328038939 148321056 960757931 315464317 772986232 988245858 281823447 290830852 698586984 365989537 408894264 793310318 108552556 327742250 390337540 468419292 825666240 2634983 3009250 137063121 51566897 735001183 116649139 531753148 782696773 771876251 623751079 159266501 294330923 377445388 330266520 772911857 738185044 293035503 196202839 681543584 514592422 393579214 143719645 389945354 995852789 107408670 705386065 875969362 476712720 821749121 730030378 121283087 459260399 50723407 354399200 388157326 115966116 87071788 696476795 860248527 195522731 373355410 736484390 940190273 841200673 682700474 175805020 186400490 154766484 204555657 607592436 391216593 423580485 839259528 724901220 544190620 460625198 520848976 609446213 737886466 590581093 181681604 28091641 885910475 23796856 756743974 603192588 780428683 501482601 120656504 112514520 568744228 991994926 251839616 881524502 695108242 517001707 871157289 394890094 593168891 906918189 411671506 633670238 424127745 371843111 406515469 795941481 233817617 622667322 273200116 469387374 222575176 273212566 566823458 301672470 580201985 799148282 797878101 648675687 51653119 290016407 136693110 266137396 794227475 436324674 175447097 80815404 567622569 525892657 177714042 86390553 593605741 329206560 693135080 313915259 446148013 42055237 718070088 493366891 553087859 692231087 414871752 340972165 543997224 656822591 499356276 983222896 672083283 411062342 235565250 878450444 867347326 434797245 485511495 643326518 523881529 832904731 43422605 409741882 785597752 386273239 813871868 179756502 153329047 185459578 131960308 183268583 647775327 364094461 686129075 557790304 225590027 373334806 319906002 567307805 186040355 281445930 893729721 447409992 180373774 306376352 389267940 894837826 501480488 571808529 51457797 231235743 514070293 150666098 565070397 829746158 63051318 128503591 75957904 265082612 867489286 935235961 658104831 818700464 106144091 31104356 313534619 615587930 816756706 587793435 402110626 316407930 8788432 596187070 130570431 474820743 78777277 194742280 151210035 228221591 620706020 748430043 496966754 621424854 771985031 843818588 127719755 491210606 136092672 546548540 180485026 272812450 753446246 684310290 620433914 60479704 387068661 445557657 659390569 643435461 115856017 824328362 3499176 358037400 272947822 49989625 954526666 477849586 928491315 538113950 585183606 284021534 729719544 23882964 872709933 745597754 64892609 965326567 128957781 42890622 9866135 392815436 302118112 195515805 352824645 35026122 258446237 202699075 469055660 933060566 922827035 701745087 931133379 624044030 333349941 268368315 87790383 712702587 920229695 911352614 41208699 379144169 668572876 248942386 764611572 809563417 626112633 614570788 866638566 518576153 438516026 973484777 464362375 519707677 468315586 589601840 137642625 677793055 196048614 770844755 841468951 89204908 294010541 740185613 338483640 855729261 695538954 999218198 147960721 206850896 305718982 896116576 458252092 41509720 910025852 58678508 100257685 796763133 269007806 366035273 916260781 254797120 274845782 952103850 109323480 997223760 768475558 289318051 155830754 326922962 90626609 358150784 349172574 724528081 983917362 655398210 519052062 99699522 84036714 196694071 214467774 335295282 551854072 85559605 879417691 29003662 119178336 68323698 466459234 994684815 748069550 122995715 96970114 719008192 391315123 313475567 159090627 540116141 716990318 2390511 697067952 779055658 729734085 753676464 353808701 891767284 91463990 780740979 829765801 419855550 448925862 660190088 914639895 529781726 784065870 792771083 110361571 828064833 454118172 725917569 324348139 401578023 498494603 872120375 433518028 677100748 904766056 747241276 752190315 898749618 44860058 202457420 548047032 591814929 737891747 85455766 988985278 856282620 78036117 189628651 559396470 900148081 4354869 531398144 166409998 39091403 364984196 334176636 115804900 795296649 9491482 541849224 244701028 968250518 645911238 755728726 465363574 948745909 529187126 556974184 922068375 954883045 167582187 152667013 758742457 174531772 303582381 988382715 60311803 224354493 667599358 786902975 111665242 15412638 902150187 732018362 217400359 569393315 757459290 458966496 981457914 354838521 254621251 315093151 833768263 988066761 254459263 193527356 188433243 536075412 495056371 701555471 821513267 296179722 111275992 586290870 297987535 764063327 7269005 695067826 444590313 855340856 158663293 779015971 540962851 400341438 280263345 433104058 205665449 27713874 938707627 786819642 275243667 505263036 788623297 305613271 561136698 506455610 784803467 357519622 903832353 992590692 654296244 77328323 189185572 979375890 875155825 442913133 208523004 153666323 379181031 170684762 960173296 625565628 915950971 666306429 470949038 318395182 418207016 509208509 201848675 473369023 541161404 320810905 221393513 686697234 49120765 148267617 569457805 462531448 540527390 692210606 593905200 482365294 544856207 459389924 211309340 679814307 668148718 293668838 853206859 24989625 976150326 407639086 219612082 717307907 403761804 664158492 934231810 456718711 857253965 726704954 272044993 516670402 958314928 186562459 964324870 94460022 646962200 918188636 222612689 186731103 879143673 560245580 307236612 426736115 938269796 487068328 690379778 717798119 946404400 573143039 523240931 954076382 914789319 630605620 303343441 591759676 664074378 183084450 126735106 362243609 651936994 521204058 822383314 865372242 735392228 141212807 182616700 305916089 593039264 453234164 837259271 737758114 352329573 256943683 608501916 629595491 114595811 975107273 799486219 659983600 311801763 556085983 323196117 60857586 803470903 492142057 400966255 343942108 893256198 29563035 580798947 226051703 284433516 623832970 965144685 493230261 784197796 773045500 655053140 944793892 66080442 446615717 469318768 235640730 242687034 58500967 154091800 650746289 147099090 631151279 906441966 384117537 589872303 858874742 437757415 91055268 337664802 712290702 269799722 592738734 968085490 9181703 813821947 56822283 58877068 538875655 641488919 804834645 252833060 444558758 816148000 122854162 792887401 233670399 832448093 186172135 618859786 897648689 272600471 390936430 236861730 990488703 221514642 720343583 124352575 393143191 114751787 868706923 461261326 590977520 774891495 644246436 693596492 428901381 475149733 661902187 73579357 29400082 377677983 371303847 86501094 236128589 775279012 459968180 587506262 503994238 434737781 827829097 564043874 293970061 633944581 852663136 627026702 723711083 492564632 925867843 309419769 314605218 367651264 985417314 12243707 970959095 672925417 905723268 458883702 964366413 896668411 523567336 245891780 606370360 677409314 122607574 564432848 402662687 488612266 851446752 47483329 219497229 54350851 858950586 144330704 140030740 226446052 210922931 344248378 953547660 262947153 557109713 201709860 51425667 707723182 844918110 78521153 449485069 2273665 501810663 444905093 462905453 698503945 47568075 878025573 560662019 193084958 645717007 729600710 291534572 688557610 151309887 921879070 693877690 103566957 323145922 648771936 318790632 371103245 541438039 624525540 377886712 432186318 906682431 392721091 332612290 584935502 404378809 678327090 678441196 372208800 199978102 947009713 901853488 353073283 925478845 139892134 237938153 803418677 1963931 191554378 92327564 632813610 563598373 522837066 537743674 176812635 223404907 869991132 285401748 928949103 561634510 327599413 556034422 658276605 584323899 458904500 112272520 784399448 335602703 580702702 521049302 128606976 596823493 255092840 250723432 681046063 730034970 844125562 903175808 60893586 327745760 284730446 331876720 160253717 926772321 88878088 408239637 725037015 902065774 955220224 765254387 955363389 142529283 726751274 448880367 278762786 481617816 81610391 321356195 776849452 214710791 266002708 847833953 196089146 772988436 985225712 959239880 725252857 334363550 358590684 318026236 210884246 442232673 482208490 467976069 364264590 122081381 133981880 325199046 965399201 683704839 127222950 117417495 671032036 32714402 251577666 556377730 645491190 480923866 36880151 120313419 683352965 18105015 801911276 555882660 172251190 665342645 888086943 478558310 150577971 905041147 732135530 476840257 286234564 695918588 531802259 48008715 463186678 393498656 952261371 661037869 111145907 431264787 22366698 273479648 821010593 137198979 835268668 239177635 134112632 131077560 208365374 609163129 435739211 35192961 120472604 549398403 564557636 107357605 149202598 501055907 59541460 864713939 433757427 294575679 284682347 500193065 914939653 570624613 614308087 105540396 963391698 908578314 161617147 238262000 683882603 490332487 298708956 976122517 840695641 814344568 574281727 204011600 892262421 47976893 861110101 694233993 367425360 980205272 115610860 35408832 385424485 620052052 438012169 608593440 218916725 513117675 815698320 282383586 975223582 333628934 838239940 316072226 726409262 705400964 52278014 636626768 821355663 513084978 216618222 76452817 860769444 757376779 842172679 537731224 747804639 734551647 725872990 183329696 843495850 168195965 502058953 156539243 281511023 628989980 409587564 208635357 493241940 358671190 90335184 475172967 638778722 995576642 592204272 306436096 157535445 225631976 63602338 237339507 593270267 966502270 343975813 898701596 769834560 762922225 88860343 657493805 637928323 194610018 113359689 741687035 881675337 911498422 669450083 79284808 251300279 183175169 420598264 89324820 711943092 367396458 645346073 500089702 940483526 775226316 840418513 565015683 162092179 916422294 150681029 177485441 998056350 775736676 152468425 148315753 824498477 368778809 569189775 604341835 614166363 591945594 526879977 705419211 696260497 675798388 980712992 906376032 664514191 406004597 589872274 888092287 427719190 652442759 634055172 590115312 146167954 943927681 168800478 668517008 508102218 453139272 209476458 993349134 476773686 403411619 952771018 259197257 447156512 540249987 285627010 135275239 213526499 557032776 925482511 793650347 383865487 119267835 840300830 453646522 183182621 107427212 145160862 348387792 937440648 119737656 613005827 554125341 573331046 56094791 786378626 436099683 29557808 649901062 904623183 986114250 226033987 753317541 580225391 783179328 842459648 610697646 68482475 246250122 333537042 382279714 199405216 647666412 356564943 138895604 890721137 841868472 388235415 373424547 720446680 692834843 666387854 274760311 451533528 512317846 190211741 793789760 657606905 647755317 300782575 158594073 813463812 109933674 445212222 65668542 205760547 22551072 996551523 815191981 689692267 326964343 125682807 647669852 659851809 113629999 718820886 968987885 978890840 954422654 720218495 880572033 41113570 149948714 35761134 851902344 129307749 232202960 612504710 375119792 80622074 939708439 202336050 325206478 776171190 411101834 234514000 735178271 24782020 585384617 156880732 443409577 803119134 858959421 564299200 831411688 380206845 196580140 927701668 500894057 370452061 490249533 92332616 907816614 984818113 908553100 659443245 917111453 19492835 520738565 481476379 140124792 844330703 360979002 884314414 683041110 173548923 417294260 80086154 662978684 331813106 903641915 552615925 423366998 432616282 14748641 703120355 677504149 807787094 390238792 712555278 556419796 539559137 373540522 979700820 227274741 464135986 721429982 311280635 694460818 685320393 279801732 446027877 769257445 745703113 457589861 700538943 233132772 766444969 182679180 363518246 241886732 67059762 38172301 87088462 385872305 809336495 216002709 228160442 600338305 13992972 998555259 27265823 406573250 360474241 750598021 998712552 881499181 911243113 216815828 122673235 536782695 349614641 29007469 569058744 145147928 792488043 447586020 844678634 525726890 544426754 84392359 775745974 610805920 34185864 392363492 327347856 459160236 487937325 668943295 787462343 489839670 41754548 442482519 64750485 193194608 965411693 921056071 757393920 634537636 744073747 543118007 609246488 780762726 11777286 625866791 839773472 853707174 935336880 128758563 919625666 467599358 106089994 321756069 250447714 785090203 914917175 749909255 331082639 947899077 803114062 339684002 762171030 55244044 858213173 430780937 388464689 610849553 851412904 247385819 448303453 100508142 608882777 149183049 916872009 381816643 563267634 830539301 428812650 596924638 208308150 359497122 353172139 766006534 470370437 674608046 230451138 672782692 814335742 689712361 111708318 892519055 458969599 39190336 653656828 529224242 760199879 314512683 197471708 73797373 338576511 516052866 943695460 667774666 912516336 257298695 107025399 342768417 366595623 863004110 273600 756907550 700970876 159516722 965795724 186074448 912004269 772821237 837883402 626288412 210301802 858712868 314450604 827303295 250668765 394319247 327790865 745205522 891153734 645453519 142928837 134562420 595925948 836048136 168180609 251721366 182704503 572404150 725510209 203883216 97717120 552531726 825459716 364724749 641555191 995927939 317239072 749799719 502668801 931430244 811331135 833956942 75288396 930920098 72969722 492050337 619813440 755179696 5927952 176541919 66449347 900256899 559411267 660308535 696545193 120362681 809817807 203973179 5584567 182731221 389425287 520921843 896386898 694833832 134931470 973442761 811996365 836860336 234183731 441231691 573967195 431821149 635453501 325045479 523083663 969221453 573053563 5923652 650568647 266436476 533211019 955129550 997118431 42977151 873081262 54112313 685411498 965101924 254785806 717015740 896138859 555189010 564440687 679661385 304590620 786751950 203601813 351205079 885682522 570482138 556912947 307497946 812496880 838496824 609989771 11043028 181353100 485994151 93476869 442266053 571934495 707083058 399436862 255010322 27166976 247514693 556843076 379970159 773669627 955504258 237291363 577317099 616422243 910201877 53846287 915615669 106876094 241004186 104539671 398886390 917776622 630353089 765622159 240541927 553064679 527293490 70599887 835278540 540031115 221971447 375110878 849716081 692476496 748954236 153121884 810215721 673688912 387693374 377048802 877716869 89250941 524946194 168060040 461572526 960151794 316262672 715810688 318806628 586403684 608790554 449076703 739260819 423497911 649480972 933661564 891534735 610722733 928931714 65146353 573402093 953487289 916571456 354439871 244828157 287315186 907152450 19240846 122785511 429259555 847935329 147008145 238675297 569044991 247273887 719751944 50072330 221043826 663746063 970265055 904634214 605764882 219326052 713288308 811515511 85521332 707842068 404588406 65521396 217093147 322701352 628623848 505685032 71497676 664286115 24739397 966983018 292053245 52169868 582136254 800667957 806876843 531093402 680293791 469845475 809116107 766439548 496559311 719408139 456529816 975440578 652426102 623708427 456396139 602805433 561434036 723516777 325194912 489427305 635082230 723570329 365105689 663285523 959201991 781169363 992844566 993106061 712051381 476367438 469789393 31550502 862695021 782936606 173913135 122317920 471248549 275263261 664090178 520678212 271662953 14135772 454655721 207113056 148024467 739595556 677472147 442679391 523677529 658145063 71722528 536969027 666418433 532308296 869939265 695737007 87957716 32733279 665262203 604677802 763957200 892801773 24176415 55717419 454798673 421315832 722824645 643394577 629850332 259196416 367146223 752149989 635494796 615185162 683465115 71731993 996101845 443368704 79500970 572584120 251284293 330093448 187364458 260526373 344652861 925769224 170094661 623321263 348251859 764661913 726160020 260512639 632730043 595183794 879148828 390562325 363495923 352560680 677379938 966695035 487338643 865675854 782647806 372652955 32720047 739118195 974453175 298515251 434632173 636307381 176610646 210015801 926107052 707176572 426224278 895636969 544665665 195513242 598524983 639011180 151365724 324612349 291614001 254209062 490547849 559497743 903072518 947710675 414974379 391759664 1 814843323 420639162 571803740 581393522 402801899 568771415 579829484 647628067 326040092 95432614 565374989 156942524 314751403 745236241 358028742 757979656 936737568 612982369 358208172 304595437 38244963 423428754 772902900 407831466 736170587 338239006 724485725 786981278 709031944 401352855 130987238 1890754 195023632 685798466 812586789 425384329 106632985 241453348 413534176 816490595 916603371 982603714 818091637 528998305 176502068 423957671 471555106 228804253 736091897 136474506 825425320 625174075 490445046 449180173 751123973 693302393 193890322 889510383 198677126 444179891 620246242 672486809 243304685 157274247 556750049 965692887 881562686 956001751 148624716 307236516 834353900 830084509 26855197 668799241 899728823 821605281 855564440 60276902 123927348 265833784 876720846 105113449 461341672 33265577 58543923 127660622 968048777 837992608 452285799 519543661 65745092 479072550 3513336 427212793 462398232 552606185 921202826 553081135 168895597 633963682 330571443 118775299 162006976 740919276 538817854 65644639 350502625 222047818 737665726 239035004 598580508 735842848 691926506 343375088 170050008 965564234 361066161 987498645 592109985 948133063 844592879 944158651 10375362 726163428 549349015 556316257 319981886 276056459 396988132 387400835 222142645 51493775 111944227 384274559 805838085 834302979 368380638 339312985 774049331 945481435 805337202 482501079 460763021 627635795 550814608 563393245 38605895 258466339 244312203 968771878 273468796 806412531 906858894 790109697 391501812 731767926 479828253 881428629 747349795 966616138 636181881 210245993 325352001 714429528 842582397 308168008 109017219 749524717 552225319 732592674 715728618 867028400 398055774 604444651 280469847 729339291 554159971 13713443 659868745 852272279 651041125 918644225 939179205 306597044 488572723 13163835 612685570 924371980 689279861 488435476 302603279 520501828 96693801 838059516 270769117 58599901 711061998 456336958 534596524 718496862 89597068 851888367 816951223 672585145 294415518 41414094 551800864 463746617 841434092 782439641 45320455 100851122 983626835 743604358 196731708 87829834 669141184 859864473 196789264 68561885 77072548 965585476 202538257 863491008 838777379 620624632 509604456 603432485 97202860 378159707 817881638 570246338 976547303 977084841 583545550 274603516 493668952 186840188 438348272 972468325 656217489 83627972 894041794 204817240 545462242 938345106 565095451 445570510 706345772 262516099 616781468 790015200 317526228 868197063 872245993 416244185 426259155 31751885 758051861 946135031 736148457 790937485 522244124 460139455 700149489 828181105 312602761 388724730 438931280 376361697 698551608 772820047 998547079 716265834 533709694 37671145 711399306 582102839 616557926 426028570 120893307 453553557 571038341 792998458 140224112 57362320 19802905 453716743 192528937 690977127 41721976 873834971 222507204 502959733 705116059 811172939 730719067 931142825 757347755 17731437 870940119 425197779 842687309 819724307 109211812 115862303 31635648 749021014 729787036 554034071 49099163 334577337 358049155 694372223 743230838 881162136 608156330 755964766 421536425 842023298 679221590 841660724 623993523 979080333 432654304 324468518 608987021 517573698 129169597 270583064 59389222 660233300 207296398 250689520 357137727 20142827 9697699 79079354 858339419 645968606 275901116 835677250 608754308 437619377 935224758 289902643 496924902 668468746 504058226 321988954 324836716 958081303 428814683 611372641 880287123 154297096 540458264 297918428 281644568 813702452 773837797 750088976 628151416 498461289 779039463 949146254 65990708 550301395 38689543 16502714 601565464 135117330 450985987 849459063 175244696 536640246 589871774 625001330 988958037 661253338 594272760 529338376 794330266 306850296 264092373 95298261 883175218 206614757 672596954 554757129 764552180 789327380 223923530 311453503 197204070 359463868 699366385 320111603 153359286 472878053 687419457 759764601 280400858 750305919 953781755 216522080 921445960 424921231 789092471 143709263 707397252 919743376 182372051 522117544 185593646 233583056 437551389 971406002 887015346 781667245 625778552 159053174 434852679 288851321 430694337 556564170 690165380 103874357 744621881 338967913 247008454 241441710 625834622 228208241 600421171 476594556 964833111 315631976 395275071 949779045 843382788 751437862 332692299 825709647 481192368 389573473 461507943 456777731 308300755 615939128 599507122 955482068 503986698 469057525 803950390 836047100 135227084 658932619 143075367 461701445 270930468 353994209 709997698 916555021 139162422 974173671 138864568 761674682 45680293 664580528 874852730 901594240 141426123 481335336 152594258 685483361 868506751 864405642 87651419 692553782 976088768 337064791 774447852 2851704 610779821 729162547 763992431 983814571 123195053 416784733 592498767 980533095 130886062 2294729 786149647 738595844 162875787 309896924 111482488 617611489 443187591 118661315 873268715 546918225 684519158 70327921 469163476 599689507 792777211 622794291 947945279 564198349 658545772 478930417 507621508 461026356 378963666 702113539 903972126 137526555 752818060 41683885 55165594 326581797 79282195 759564345 656591019 184490888 922526295 686177200 266137690 528222289 884525641 51146804 115994714 367121229 85570418 874557181 289742970 714697371 470208 228035566 256375859 820613580 63136865 499390049 332942792 573145615 987304144 951273421 349886955 205156459 123370835 87061745 988066564 379491800 140272591 812388287 898398134 470937634 663357821 176917837 538204310 684208425 539466722 243346848 616226950 90117053 644629938 967677647 273200315 855274343 874692036 961314386 142987846 203798378 543816948 64336491 902250564 179065982 325918997 83375337 165326340 730882533 794951726 717156928 113888028 97999116 716006373 683027522 77639317 344377817 490761340 252170566 496226199 875422954 767134767 632495934 101693052 324869098 564157531 447143863 756500161 312479223 543625418 155370938 507335980 844908482 419111386 234555142 151642494 727040427 894889678 911006638 793164287 481068280 812062579 434286831 906347177 727704182 733702066 708771274 69145421 502973742 998718437 67107532 824518570 181648466 105415318 146615362 281464672 584965748 73902905 815147338 140663677 319069711 951077517 342144663 924450629 781650555 126234020 205669636 694226260 789954646 271451635 982615864 154363135 109991998 6771337 265088985 357999400 844102749 718171390 307436370 407711328 409990080 732298915 464182905 40683761 662860266 721510369 870666688 878862287 148159906 851227817 996335785 220695145 632547191 166226102 537968177 954104696 386086149 490117465 77920912 417539727 83304507 864719957 675996563 400128668 322087892 944057621 48178178 672353118 370776057 871072169 525437457 659652083 994779396 131850992 142591486 121381984 267099384 627212157 714813812 691015564 337020558 47959065 801929476 425617214 422055171 118582680 279041313 631337124 208326940 127163730 599208365 154984133 719424087 64653891 721403399 768258263 611073983 308488481 52007881 998292014 456626718 66638512 581819440 957281832 714301463 122880434 590432256 737354760 976104967 983454880 999802706 124247267 805990428 296567360 7002865 947907507 332436158 49274051 115707801 294772831 884586197 175683842 286566550 173361403 187968357 960268738 658822443 303746256 254909665 935691241 45294138 29920740 59933822 970534194 411628937 415268417 809179273 995677961 551727973 673342495 911915808 98844674 815546844 658149182 169378098 986785112 983566858 686747378 163283485 707836516 706891938 930809898 156787084 932823969 538525553 878745145 201682042 602990661 80308218 69154731 761987563 364115659 452346674 911495027 262740161 673711214 968370132 465556423 169243279 981375124 68877441 533949080 418464140 204073688 30260225 792791460 813206962 266729051 202537640 674873811 149675235 594610596 404177861 730946920 147833169 170747651 818264672 830272651 709416353 702361239 772299533 33592229 900544632 829024444 359526560 129711995 222681436 323518216 35079936 640796375 572493890 296906552 827739173 412802032 697552598 165619947 481361916 409672183 209294028 38724545 757259236 400302621 967220074 100690722 228174067 173487872 253983478 349592645 343673999 96950484 552634520 91442535 492293148 385619503 794648670 399960232 648976847 697474928 186301786 781225602 19291298 402063565 95093222 570720230 435239776 414726393 59424264 380972021 860155104 392712302 584121840 629163351 537378126 329730396 505130142 407253308 265318564 330415150 783174816 63116781 357563449 406771381 664616697 990841614 642967408 833648115 318736414 996801394 467425169 325230726 700960026 34730139 614845108 555457968 265955025 195784141 167380953 171195135 524231009 820071117 807694357 803892381 333432228 875534395 275521767 608467510 710403794 505874313 221116841 219136641 458974276 869234327 120927266 399832942 935775571 807919341 276918840 789428971 497839967 633329347 747904594 876560529 452269436 520150130 740560102 365782783 243265044 989193784 753959173 673605832 614133857 437590009 234391115 634708223 815014835 357446314 618536413 582255429 958041071 620802755 437354839 841390543 560861747 794440906 686317400 452018744 750361992 5983136 361744233 437518470 13365107 672347961 964810045 33609223 313558025 133140881 58071700 147886294 687766807 588596537 959643783 259083254 810526794 304062521 170739894 927934348 513162442 668764685 452645564 421839466 279562500 255325505 17531588 283018808 524309122 743145124 181417781 280701429 74486828 961489801 447331031 734091093 238137190 15640635 432987492 165748255 954196887 323608543 901785359 923254717 649555316 520307531 368288775 346316804 307690107 687783155 52429167 35033047 61801453 311243603 718715878 314969576 982152552 797829765 402380466 73239967 9303794 552180616 15733267 326317514 576608037 340727546 692075317 464794299 605443453 542781196 371518757 881706103 971433750 11422414 634691954 449452449 929283038 389279322 929105263 483655102 263303283 901185871 919110733 610706009 788960854 369459349 734665540 109949741 299301683 146074066 398634306 573794319 143388738 846407330 17226422 100589472 389819648 400622406 529255603 674264289 314815263 973969746 930668187 335028671 402854456 643663931 342957674 85455662 259045676 293932867 175872521 564551918 753234868 596400944 476148417 367958650 594762705 120647831 780039954 129387965 414271890 97493734 253958799 161869540 313610627 384809342 334301013 361256270 891944882 991954168 776314665 271045024 386276703 544968841 563269678 554166518 609950527 266431360 550807871 556762932 793183341 413272300 416140271 194912378 352718830 822996506 54163382 58931423 302515899 286916904 489381971 921922365 614376037 235209438 92970255 598675793 811317552 948818912 256736746 887797686 586089921 578551239 111665466 643793928 151549155 45754587 254684123 233044011 409851920 220928877 548546692 845804085 735821328 320040148 328904246 873522937 746229689 846937090 332146125 174408497 653216980 388350791 176127776 566384784 455003334 751635904 960102256 800433172 245006102 356303942 963076335 222676029 862886449 461036368 849149060 638087158 618675507 590845040 249105488 727136648 789478436 89294136 528876884 258698892 528237925 490335434 32694155 861772869 764204539 562279942 432849716 411810995 245119012 452145277 454291769 660916750 544211077 228311010 78617286 603535129 67610197 303890024 764404382 964937994 517971818 953949584 379817684 717244865 126109569 534111780 231578390 266708011 330197853 637063404 829652811 294930261 51467428 780070858 569814688 772249714 884878198 891858899 58750982 765486663 403041248 36199020 587298539 387774802 573779498 861370057 295985716 2268888 348924432 571652864 333687946 883960363 282910409 683125321 891616467 106607983 44317652 544208479 326958529 342493901 101115335 293801772 658412173 890301907 960709220 85622216 936152134 785590770 395961461 511663140 726076076 643357119 146695521 945232349 155618284 136611057 235786413 862039746 753436106 78451573 486894193 572721380 869981305 332802344 625588624 743322586 604642581 177849134 507988738 190461170 104469581 642817127 682248978 929703098 973360915 929737011 694467483 736379365 607284676 90879537 726455366 334320324 1759091 280356825 982207174 19433737 54580091 708384275 829426696 903668908 444756638 403820357 490929753 231725065 211563003 611470020 317607941 837392447 604775921 453097174 350046611 637591089 680040422 665031321 760294913 435111351 49382112 886909713 199992615 406070010 95510638 279789314 744864454 634447006 471259911 41298156 211962768 926273559 424324799 605149300 610467029 887386757 455613740 637074026 827086684 372518903 163837829 178679644 611107791 188660257 571594052 951697685 952444004 809267865 416693267 927762086 667598194 912494136 33038463 517664500 820072054 495085203 378274542 850299000 513377360 444508693 533554062 503309143 98707466 407671681 953215921 957939990 853154552 711342390 55565959 567236246 986755027 464947014 974365408 803469674 984075726 698641440 911925762 95679643 191625206 87694797 553984896 772454267 94902660 41262473 13831485 504823202 998473349 603390626 169483648 315187547 928800105 272687122 545753107 901043901 820318573 404856280 44688260 219400006 155145369 452682543 336626419 216052880 222431060 443548088 986884751 135135508 11446917 95321959 761663533 34725448 638804200 348129483 761817798 925059495 593675515 958648363 983538793 116841402 249184739 190391148 323431903 493717263 51820562 139171845 425770713 1782633 620977906 521561469 669722943 493734905 268054874 849531795 57752060 369852053 733136704 2926343 773465854 499118231 410581132 387805442 164428122 220457301 516425991 945709858 393911181 106285112 380811814 67124702 768495739 620315059 133689651 713573087 899431554 121948202 382855186 623540436 988505123 596575269 678481575 822407351 367626084 385376955 597732963 160666727 792363237 39847855 771759261 626449138 815194783 817720163 198003635 674733181 576133010 956128879 334608071 348218369 117893363 383924126 526025946 263671670 405856682 841765050 236800447 567273426 226325851 829452654 351991066 667493392 679061983 841721589 890037346 874085977 131472306 726660294 712153100 361231660 256176645 289080022 724599152 310851338 118543640 734134605 460708982 432151619 111321847 206585461 408165479 684333526 237376521 141048603 156550851 760585909 16793791 384129232 386217497 474689105 282729565 109211781 799207314 5481406 849264089 878124224 378487208 782501252 692975836 981819769 591159284 70315009 775623909 500901267 579135524 578446974 644629645 925756922 645127179 922067148 438627045 467829333 929757394 87298970 463450363 668709224 306202956 679959383 949641596 294885130 212050792 50597310 678325181 144057023 471414787 348899631 873555951 132715597 755990936 636513859 622295756 981965117 340011932 819999655 979592894 886600413 629503713 141602556 55862146 599547825 362185368 78605293 92455400 88091043 825639323 285979825 611344167 935888216 287385687 319150765 39774170 770284884 705708341 498368155 930399232 665610339 329413747 898389563 959613819 275386467 994026080 957220763 279436364 98810799 425100784 694286634 71382496 174016807 705812043 120805883 684091373 171873754 797822005 571674241 45175199 95881037 362224526 47707370 65262058 216168043 825108725 647825150 372751112 711223176 125090009 183064083 187802311 603701239 69510232 387464343 851008888 884487459 523982832 738607970 684426155 503546224 891025478 533075547 25167223 978787139 72972998 77463519 933016437 765159305 613571619 528078151 335290887 374508613 95798010 428402834 863193550 55856846 615223376 396863385 218307656 957126993 560548992 431402989 354037835 497729529 274030535 809332754 722514339 814482709 690810833 459700528 228280594 276940811 701337655 83015568 703154449 185597975 379693093 364960147 306429008 126406864 606419635 331577499 441829215 446406689 653329490 714885786 862241392 2647009 174642017 101644853 270794547 848421136 695712735 889922964 460780257 701015216 78563387 249181640 816732757 59495485 861672264 937491162 800318036 73482187 256371020 461821036 667101677 48453052 950757646 577197820 552743962 309179121 556684832 402990792 107813783 967879263 278404812 985639966 793862681 818413838 683255699 896830741 239078614 567844801 467303356 948934450 269198981 795036361 162787101 247694839 340762648 351316996 262013643 40250120 325471631 995914393 970905015 258934916 38170123 763824223 7570361 441105863 815494024 392053721 150514376 720259970 188970001 321635401 976058726 882910329 354820615 651061652 796444123 676884778 185102057 12277011 642976423 223458502 705969568 531760918 840516229 356736572 41145351 838367007 57239021 771213611 910841180 931025359 225142268 803750622 243894849 578683447 163978550 492967817 878911672 33522086 406566347 955402955 362730500 796601940 427889241 600773557 189897885 453562240 660279763 780255207 334900902 219070836 677712768 759616110 397589203 968794077 598728256 467770587 586193536 112189814 940624365 699993088 61292765 307841110 518736454 535596358 451708114 87110019 35642286 632418480 676302608 493017653 711595874 927856703 336972073 209858312 877018871 933621493 642108922 389022679 407362882 923232390 741410440 366493283 343656660 76246676 691356691 36288836 65548963 615651550 839767798 351926384 812866700 795219647 309922908 183489015 124870172 207388516 497764618 608427696 951524931 126869611 106650687 46793390 659719099 637268676 730440182 860248054 225329584 57388728 791699530 776172012 702165275 914074660 960927169 804859623 269811418 655460543 870516966 128426030 474019218 804105038 80186387 196931304 102143255 656455504 99210776 326803837 363122033 139677691 680760117 809265491 313317494 172114133 346683196 366760112 395057925 580605794 971083365 501359811 559798776 698768046 623193022 461744663 766655918 657567725 938600732 540097862 773177203 244746868 345138176 677272361 691434554 348214367 3577790 873545483 538165331 375161724 662611058 8657592 20649429 460269016 48408526 569288987 349114936 70449890 294859250 349323897 570038527 699590974 553913972 419240516 770018706 846949161 696055679 559284893 622312490 966711172 494765847 338377189 565598079 705083002 297567503 824254457 767294691 829259682 126424779 875170821 572362491
