5-02.in

7162
720138949 946059768 96074492 336145045 235721460 94768933 106744290 635779104 291980438 553907939 121941086 573717308 39604338 30211843 550646189 24139084 443725313 595974924 427424820 754448441 562273008 825680002 336148682 940991234 367088462 608211309 523427455 473447621 435207749 127081342 663619019 57348616 920868476 831019133 837562238 516359393 634155415 593565739 37254352 386551449 153686651 640487039 920510175 219440296 545403125 170418624 624973650 368383857 346845012 835372441 285305905 9983896 299272137 547575935 779701420 329201433 320355138 168953177 287106719 702377293 492456509 583680966 890675352 399799106 777413535 276853470 787617598 454184472 175124974 193457519 370319127 31906413 166878129 617388040 62878400 888350284 585031928 662585167 865548269 87770799 563167352 73628804 713912677 18160719 787742693 631167202 996712508 959960910 935629228 687987973 976276059 93390462 504879913 769415751 975584940 404205103 802933490 294581187 511748089 705573839 230696204 726042703 878187195 391694950 995406942 863362634 375632829 300921362 379275153 706249487 141269970 538687132 838803229 877550808 841262721 608013828 330732353 116287703 783328509 828400375 118159479 919428081 154681335 76067369 630747357 166930830 917014270 333118527 959827855 735016771 582033272 461300979 333078397 445448037 2345131 39196851 728008741 644330057 616640868 233345075 45672304 137053280 935279333 807812209 815305735 753952206 565532705 629008260 381440738 115541645 732627787 502796061 577291952 139390269 193899517 680082267 731896176 208870882 688493946 563351086 336361951 446194132 759639768 923935404 594311146 35408994 70485924 910147523 703702199 958695816 933068708 736362767 815371534 365256448 772512796 243234290 634420889 897443530 445094457 987910858 868965506 236239788 66187797 689624315 551021224 853494159 753679146 100535301 797800604 398412063 746798319 103774368 682280144 668680394 823193320 961390511 350000182 395335773 193040373 406631055 650184546 478661771 333408456 413937630 903345573 151901476 304098547 753090647 138597202 503536441 388564707 454998556 729751476 466583716 850097585 879021258 784690116 351722716 697267763 817503666 639562785 897598383 489373967 618811886 960891283 383958779 408487295 906391059 827243657 841022221 73666246 319386869 872034102 166276361 292962885 966559547 723838675 904144484 121829270 535345808 859052942 381373550 380106040 777635864 136037856 800077277 565288738 632222346 873159484 651605957 541212341 971116027 299506649 875798005 404400240 929751114 94847767 896015459 708613807 230520678 412513780 229227189 439052719 923220687 322973796 197085932 398864435 779490117 847152427 241209918 609214257 920771110 351236477 458374855 502738235 531083445 510712690 379995081 2096740 219602892 433796775 44515654 503203833 24718581 893943318 718439907 188945092 724020157 415584069 633215285 972793145 963005003 230735439 886870149 407666938 755035740 855657408 56892803 960827120 230568403 660918504 112116213 265057916 991076108 693396032 513452861 764207933 753229424 13647584 311454724 898529298 582946197 433839894 197998488 725808627 883216616 288105395 496570403 269093810 974225391 854976302 218891372 526134061 705137818 586565531 24652606 670756501 210971939 766307643 172865572 966600613 821912244 399712798 560046284 833993853 300345657 443924436 682010378 341702011 795182416 634180578 499004599 37100815 823164390 473256565 453593220 715125619 947501294 967310693 327549412 328267252 670648622 126258939 181572240 892015043 325065948 157500832 669709643 631685676 401376400 972303456 589015048 859909829 549169052 880785602 792145594 797317687 983258497 766781870 383686619 29536745 35069164 944294552 519611395 318934125 136485857 637716456 631665829 931823881 415796677 220650145 820300016 417698650 322370850 877243369 477322974 557783185 837859074 445667016 763097905 373435773 331823555 150881654 161893354 448709972 944391101 122456513 41610837 177447036 511101788 64861512 422225283 185490593 912725517 436604999 994316899 925637239 460791622 310070679 200479546 821818310 373290218 6304112 339336692 226103592 252226119 242646529 614922788 176288913 92149172 230444147 473988465 593139669 223327607 662224596 689936278 593553653 193183876 599944788 796078958 987602332 77707717 942497241 520284725 697165774 187627302 467661219 247393601 950536416 966651160 643994675 750175604 895753705 35726994 649819676 212138495 139450704 382530512 816710007 634600626 604127218 619851020 782922271 200333200 197600362 684028541 469165851 397916888 243026703 370960739 159841597 863654984 990681109 601746865 726706077 991770140 463472564 645794159 359492574 981413454 223034898 576117907 148366309 23394377 15760234 422595945 120393035 623708815 370194252 641325689 280329453 672279697 496957265 431526391 774214612 206145754 992860859 761941735 95362035 868381962 547432319 3514830 605177234 956185352 691445396 814972932 522731034 613260922 620857 701131237 891695839 436456950 557414340 607447436 424250349 977297730 875553771 998793722 628405398 344865762 182533038 803590312 922193178 296887339 953550659 487686983 280736540 888526551 307898115 488470214 693886583 265738763 307516583 390570697 971360546 668995346 704283713 380663982 962517435 353519282 742179658 719297804 491061080 53746370 389778181 758792087 15108445 51178453 143075282 976481447 89065246 917968142 12106697 751400352 422638526 622728768 874790432 254761045 845089512 75858053 41151569 860938548 992169720 405917481 861207923 521036702 485529263 794204053 124802550 409296088 951965774 546908990 581490873 463920315 14048470 944437819 112785154 985643837 550257369 553696798 370452798 840368482 18736871 17375717 283651906 49460427 830500662 347757895 871120308 880140608 39935040 233492043 891301907 327792989 94186329 734258250 246410278 675366575 20828736 414818085 812535628 836068032 835578599 11392930 482108502 675369447 691702406 189499497 531993951 880841493 761100470 655731054 47002975 776990062 2025313 338099946 51498164 760001448 293699374 717730759 310337891 289488684 787023906 974741253 487752096 310017569 848328724 930371506 551981997 859279515 571791292 47322912 665653605 778444903 992537348 576802555 156460382 866558674 162050076 371834565 734465153 625195540 174090765 941563968 482713617 965632672 924509033 623784262 89145311 767196565 342188049 455496031 640447907 532940494 250641476 79397614 177269170 517960372 288396907 186440473 581744702 720844264 721727551 636340925 891532853 928940696 942715373 970089133 810603016 402508704 531070356 617424408 583055200 877018937 42734753 393040366 434324188 819824576 232227374 638255749 373183206 789407896 564647219 347176274 460497352 273928913 108890748 905946772 92149525 944219281 486906391 62409584 53153212 615105081 600528617 361384419 935944836 592551367 818006475 333361683 988932973 665036705 946380853 146383122 35469953 575658059 87878620 386547078 632727392 249260294 463250406 976660542 516853976 558368530 843555988 844350905 885802520 595303267 331759051 410440127 920878452 858169342 893264296 381944710 376495555 608248494 728843466 745637147 357898629 604771712 949401233 371897770 294335133 970064051 228440213 188145448 15776525 193841059 73281516 359298480 951162432 710011546 385311362 702007149 328203246 856903267 440629764 403417743 719142059 511486410 33546333 828632264 949570179 920229025 515942013 148637761 683515317 266793402 638954383 749707349 818605483 372943123 233336505 981987525 194307412 545577771 371935407 535809239 734855441 492669167 165026855 760305576 777258814 895968435 710110804 658568586 616081499 856726846 280178550 227384614 962290290 152625909 100410157 464602201 157833143 607426502 10937523 476072425 488592694 539241554 519746045 34805442 899362605 157610195 430038655 680399718 830894613 753579225 713414089 193892818 395292175 325135544 688146785 657721835 734056683 246184271 164918587 617258843 91357317 437546069 365492361 727982279 217537544 907140912 509644960 630260275 734941550 183233528 707632907 120242001 953390338 246528348 506118875 290454681 840293654 509956506 864264846 21172112 191292494 661254168 555738545 384927941 865987747 867872128 79264833 702436465 283544779 73023365 2732705 319260882 715387856 783593879 190358991 113039856 84056787 122561665 965668315 95942427 236439656 408773569 211382920 911219568 963308906 784107324 553882044 602865095 295461122 913512164 287522290 830168603 60657294 105203232 138397448 547352744 549502908 104478725 858579437 571937356 20644105 361443725 913146152 833544104 642209316 811688844 793353212 877940935 621916128 928264800 948690760 954767584 847259749 323055479 850126707 644318427 45649315 667057832 797978420 748848994 514374763 863681035 313833182 641297172 445136564 665997696 776927235 985873333 404919355 657026671 690689869 568904183 156205299 795532899 749358458 902249519 806072048 630752983 103973818 174671328 609233879 890361757 794026199 168397052 297742966 808705564 317071418 982862807 223362046 2820403 927439539 809086765 756235342 150290024 237572357 852328449 18531675 76127088 1204383 556112348 129457526 913795013 905807546 120728911 323178526 150343889 273141999 464013177 482744642 27186339 897468916 320942417 892975889 493212461 630902842 119948111 776484753 928212171 298133248 763377499 602419243 202195573 260365277 341511205 411145088 578522875 378021748 310984308 526371564 308616282 814742789 551359146 888021518 432963925 958352759 405416700 360530442 870284278 139833959 406008338 357635650 352904281 292799110 905427105 653360604 559373108 371683814 27902015 136268729 577308868 185875801 164628228 661101210 738085978 357037054 692404431 747164493 794164257 828732809 835100130 428761929 429200658 280350470 782638925 462245445 317316705 60330040 722785464 502801828 310073199 356355874 550771988 501195252 46947567 233937391 920046673 536871912 508171403 323260685 410494725 701882486 51663729 170211555 853349888 997353499 846514375 632838084 217537385 693706734 656120852 983032077 694505161 551647975 573266699 822842477 781310603 19886636 524328926 972335967 776196012 933324149 907566782 387679597 333202175 83355331 402532323 267881065 188025386 872967641 719987520 742482553 669914121 290043980 57717589 629134177 50458016 984011231 780954735 626346526 573909828 637211761 721710267 55550255 826140744 622420594 414048653 475414388 336153434 432223762 500723378 743009238 848103982 129393025 525190015 718518309 636720095 404263104 370358407 607856931 614312085 441129830 241360855 438831865 439510920 592367761 818873329 720786498 609003316 421776308 566988632 747563141 602823349 561442917 703612977 239770325 307131202 942216537 369107350 75655937 894287143 70223719 28427579 823337863 937026533 634625538 934976357 10737493 37424020 232697162 252406271 276885521 178605643 574395457 335606694 998132708 594561762 405144294 495679623 938162396 378846931 531148839 319121475 896207515 535128839 499098159 953382747 318507040 550470701 965373652 198777236 845798748 382720707 345353924 940490832 786628446 67765156 170076547 502833334 469999853 216467714 40941729 340558434 536028929 902782435 332954055 439912831 613355560 734769608 16856982 66648885 597802439 313707993 590340247 963382252 304575260 423488318 391268697 973714955 827760063 148357894 297376851 490352781 334391744 178429157 160254897 906985305 741521656 61858137 190298794 994745271 692551335 27971956 513979296 862638038 142796362 742411488 73743116 690666130 420504495 505883873 94963489 118297480 933429181 333640038 341521702 372788179 466626414 804532130 740070815 250731444 962986873 205766626 825266562 779850059 189123109 135114994 62189076 815095053 79888957 665300542 653068030 136889572 397981319 559967092 259422756 800969859 898130156 339416295 339749225 945464899 238379759 130078298 776276045 349282220 47130150 275099204 290882365 756085755 404725593 743613329 943529660 19729088 837585447 650885852 160983773 647078228 761266179 705682595 739761775 309715109 493848958 918759890 749250462 418056920 897464038 432395058 424578300 386082602 74219257 452614127 312669015 136247254 47989332 571456759 340945940 373385075 986565233 824283884 558030294 149023212 56888514 442391957 815858265 179080109 527287246 558180960 954861996 322040178 582529978 725625449 304427609 60719610 869989133 784972517 663807004 480102817 80476011 197729906 325866243 747173804 248277230 63371805 237767904 949922789 676085252 788687049 305120797 391272920 147594867 537294936 704502381 299764506 449151959 792911767 629407894 997911375 86922533 796587680 336199354 278212533 685635897 648185177 457374700 202840505 955331445 330211271 128515652 524031057 135692911 825052668 911879489 334835731 358778278 710290782 691793617 460371706 429563395 629325473 17984160 327600463 206051527 38956253 620295569 263970107 608539772 127460749 506345214 245976063 902589799 747103005 883432823 208577441 500855371 534899005 284443264 709662749 120813474 37469209 324538676 352687720 253877676 789941324 794102273 819407118 948358202 903289721 49521857 258079569 558385313 603253138 750189634 170488392 618140781 617486981 480740105 334584684 6569570 64722297 456764592 693050426 344108666 811433177 186624438 894368255 250894413 768023037 792400655 41708939 890447163 134867614 42415420 276023883 112304691 318369849 56572334 843053627 187068272 924593397 290860700 905500303 93282483 58159017 48832494 497666596 158175905 476954087 270110268 90357998 680515897 642930112 984334598 43547050 620831000 106982394 446231499 337634284 760938381 849421012 154527249 690641132 608545547 743408629 265496908 601027639 468896069 975579657 612175409 875770571 215105081 719191759 8532650 914693355 784588717 724480028 751614059 722605143 212717161 495335791 781076994 973361681 486831536 105196774 13819440 626466007 643572495 634729153 294369178 869208398 229013423 504779180 223293653 22774055 857821955 459713655 464552140 504530086 387924479 464785887 751102580 106575615 508413760 281990832 821581420 765717275 179083533 793111066 548561155 456046139 816735639 2751243 539321524 508454415 980166441 429815774 791586554 836532087 890072636 507701976 997387450 994486212 251120875 282798921 325484064 118103505 152354520 83138480 805573414 37614876 273509595 700117068 767717670 181581760 710622327 764278775 758718940 467634420 172215970 118206082 964088036 708318806 920667009 198582674 400288620 585693903 631411949 494497919 443511572 12012654 465455168 211714400 207339850 925448050 467561855 93500460 854242247 418103353 272017028 647880765 24152000 806110255 242018651 601655355 183884256 529903718 882707940 779191009 256338041 810588085 73992976 926758301 749338105 189757037 949093270 115309187 585472744 811280931 118258306 500487320 910625871 24347533 1513346 261085600 582952082 457393401 774813426 922893785 198154433 407778267 941224962 22030064 454894447 99000825 132341003 965391323 74003465 968647008 158540293 497039103 440937903 578147986 399281215 839181682 798140688 726498941 879461830 661229093 400256411 46070501 341112806 865175536 226109464 646478824 414854326 174370585 364947398 586199538 759734133 898517394 898789449 885277631 363037353 992643340 764842530 313582950 492169097 187365244 617306720 437646685 466125968 811620025 233758384 435666685 623696582 992287032 212966717 19791278 424746162 948483420 536152656 560922428 42047364 509778047 493157319 382368769 135900194 280152769 470464845 491991982 771976615 236335180 304867549 112755776 752115741 642268529 89547283 333955880 109832694 32727456 889154038 396984151 301237003 177279372 867650987 374069997 815413242 715031716 94646973 242853072 768359021 405154897 370866098 312462134 476953393 223584408 212791535 26621345 995621025 422838357 633250778 511722619 856613873 783884121 727379120 670871003 617323388 203747264 771760497 202217794 153439320 419840953 468306635 913902153 318264889 825450818 426403586 397037380 604574971 599239097 347163921 338641501 138743802 938763476 842197235 593857784 596079972 864758539 626640367 371545189 630992369 774116687 41887689 554258241 329241390 218551486 613602246 880242412 219519953 612870224 346826028 251759455 968424730 981141843 984757078 319458684 574146840 626796874 165539816 936899996 255488561 415784643 648133593 344504859 143546249 848607073 875122346 825231505 655364517 460119463 91136926 767018699 47255718 688337100 972346515 239819127 469752692 982821432 754161621 917221742 726950342 185584684 511267423 644916268 645663663 36338326 504212764 771119693 193453529 151214233 691994150 457727910 211767716 800600032 143709372 557561976 791766116 463785021 987105346 708599297 338491233 850382423 479480436 48376887 263596990 24169426 292130293 85120219 569697075 983683307 389299201 395606358 450563187 773951314 305611841 560785214 85720055 567399165 763747084 839197950 425593357 310086208 602118723 869979305 944800485 893167572 165331921 366608837 734897423 392686695 984214788 3315372 365811779 183889328 298733164 441415480 57697025 898356863 634003410 644809462 254666523 186451230 690033291 943998909 538106852 221253855 456745108 955586688 811720550 922654729 121973776 90166769 687007656 176366461 791152823 819503990 387962860 471645088 688170411 380129161 412400343 187233455 68727136 981820320 544121487 617500192 958701716 100324727 392513519 462493286 871599396 791741109 274972806 792058726 292827518 922611061 46571352 72438708 365591310 320792216 889512017 715814849 32962047 946331739 940982354 437954372 635801641 431957070 537440309 242623613 424877331 125882113 739834963 325048576 36190843 464023629 566052838 361660882 446914561 219685747 803503021 683299403 403630970 166374170 422333965 882185471 972321518 437853447 604008674 670645441 115128375 632623587 782026773 541817594 640803055 340658991 722678679 338043417 758538035 153850816 77087926 646129303 320551786 709290104 343421972 925367922 392009965 493785885 843915578 42808010 54007499 783392501 941672765 856428459 482188642 873328461 806400381 416141419 647238757 257612646 429654007 975941422 311516773 993926472 855157104 771129762 516638912 787319514 806831627 478636477 879746928 354547157 654249872 513705223 801534703 24338819 696755909 850482567 452171681 375717471 477871023 798307956 324776297 324731362 123254098 509222092 335449260 194242945 540101390 433798919 149994211 432603293 590993092 527475492 595208361 343604054 940767711 876968687 145558112 262984405 950547258 614465297 34224020 712444041 614495934 270445467 969671396 694874152 457580898 971094189 151620317 70084170 112223631 690929709 905136729 528661632 783472997 14519400 769024370 662208107 522838299 613100922 126259413 527334756 600710902 793862931 45378661 336631701 473164091 905013007 909419592 823404921 825642460 548564010 521977059 659974668 105362238 444513738 956321826 45196007 648908834 722014959 244304681 808733865 41698262 466093340 317207039 849991865 139151196 820020413 674175292 441829189 771872884 801886578 147595418 525024208 824881099 694936855 253152462 695443905 927977832 796274351 166664084 993306234 123918425 753642697 620293523 930824358 859430895 659186782 567640358 966794802 555899992 66091612 586848347 777913428 411302684 352603993 324076768 897900944 767529535 226439352 76723757 309805280 608195354 792993342 724039521 728517298 581277426 164051175 977975524 917046542 863047242 205935938 652957559 550743470 850908310 750728255 340538550 914249278 713820956 699163623 419477495 542175298 225527838 983457506 400954125 916788178 8437989 958134847 297836070 123278682 430432816 866343811 790639676 573797112 270831427 413810981 510066702 719759038 912021112 970199980 863031747 28021444 843011087 430941275 28413144 651825821 745031786 984342328 946800843 183703735 895205695 95469297 128071950 192158985 429972462 230708532 346163152 384728068 871231914 242234697 449114459 16627127 919772120 951236656 877252501 731747340 489314783 814482317 678593223 674717425 157903726 803410764 640743851 34202480 340014228 815750125 958318714 127125510 54656468 163110383 41500953 264899108 957787403 659668105 171070052 32824677 71149509 248434312 716532063 929147747 332442243 706197547 952217800 483789785 268301508 749477747 736976047 193580131 455964485 450833837 443706073 901664412 718986155 703677425 992205225 360017478 574072320 329620862 385023890 360042912 193529072 377990039 318057224 503558024 69358556 184523042 765122803 755530101 796169027 667791990 957842970 996819023 11345504 947728636 445366761 209452313 720784062 747436373 689940815 335725110 998730498 954924175 450735145 338587741 437846200 665876323 932287429 156865037 705075455 199186254 707254318 825275017 465259140 189263201 671719525 449772072 332500721 388712880 844056106 332459498 764846976 299717459 530287385 414980972 797209762 673577803 88665478 688004434 432407151 729808843 19827297 905191149 978287261 271890670 1202525 416830665 36399314 557432302 782513626 754881860 215109692 363923181 531001622 554657496 686405883 453176186 463821244 954905141 56034031 367895679 427684689 351683724 729968336 886777887 125467267 655415674 254327978 252864827 442904908 52589506 989597514 419714361 876366158 58556681 544225892 121313126 807892934 725599063 982706844 800941734 221790360 529354871 942608444 392926647 776974961 139069632 198406162 778366231 481068028 291157540 994852853 308061773 439687129 513241075 321157805 613630761 823347360 525997140 128191636 687110767 446876310 468124549 38597711 329683322 306896931 529185844 236871090 789527493 334561935 584744013 220059196 923141152 120580725 457004378 249390656 879959893 193697893 66285027 628422245 264654264 163949912 647732648 768039605 933143089 445753909 832647526 207741025 59540978 354271667 871312002 225888491 666847138 78018365 667055847 757859439 942931035 146131074 288613580 16913397 252897590 703032438 36798525 440041711 615872778 803031391 757346195 917128967 462802892 715370274 275861809 360374997 718677400 458676390 506767096 696636977 406300713 489785709 990667337 718478785 536982166 32720897 675100767 835671413 495526250 534051191 28452431 884092352 423605489 399610203 847086063 273908171 201530757 841429895 624598644 929996820 9834132 426053429 510055220 710232863 887366177 492362937 876351914 653876713 906398557 117113455 559260726 594445625 51969307 592451951 81803877 235607566 236275842 842205329 750329051 215906425 327874983 416227973 645933103 809656440 817412572 646730170 272929172 197062154 598697494 146520313 505112899 619872589 848804181 289211470 671881027 985002465 358150455 4510080 614653645 693806195 102169048 627419115 464883187 368063604 617466210 801566016 925915752 907941756 669325690 69207905 156741302 302248788 568890970 592810549 444472777 190139845 236201545 280093322 74735720 421510772 945627341 564167108 820511241 95469287 68096413 744868251 454620240 187865058 509021474 343722685 921304885 974456162 586201151 987382309 531512518 125451099 817702003 62455762 236840569 84980386 280377185 960950244 141820771 125290127 428096802 492141801 670988561 920272576 610301191 336249818 605792281 245688082 150111304 435368421 520825834 846985107 684711252 576159575 571517547 348965655 524909563 904330034 485388861 272195964 409580761 32458102 577773797 935073441 476936602 594390839 115070812 755842100 783364186 897000987 378176822 871556650 314317569 730014784 223995660 441430024 471548739 814120040 928460537 254712639 629270248 583715368 467479250 565178909 124767127 764599999 208032084 762847185 901040968 166277559 570111854 777411451 148412320 358112744 610800251 450796095 389710661 799372748 682189129 754029042 448281792 149461478 168519563 313350423 283406342 689586671 559917418 839816689 313722906 706404780 712791713 985461945 206398828 644315251 574044219 199658849 258164457 287301480 332385983 703987306 693605739 880595654 934013434 227273059 864127646 998112934 124858651 574382293 824461640 627311894 592630676 185843289 797909559 361928118 71715668 959746335 28771993 694598852 690649323 789792791 714980454 838684334 235610721 882283020 856260115 901608047 426542405 257269544 81872492 134588476 286402696 295872276 467111296 464553837 728681012 134082566 943298486 25672967 834174486 487923910 956878211 146973416 408037938 761829536 82827647 492696412 38474572 569374084 797312603 119687322 78781325 364934781 129250067 498157333 359646788 593410870 389322341 499618143 787255139 147487005 215577858 548455316 405418929 160932576 414380547 575951434 932708386 211423293 985528706 72768573 55043622 146858963 25505333 899755210 763607240 154584217 801963805 447225028 839962733 13791185 829840004 625495449 934046628 67195501 872589179 830924864 648885910 967325048 433456208 652692440 31133751 482470083 718259190 459561984 418450816 231647904 18289797 848571640 866287248 77207004 60236870 189392011 200688473 324346191 677877268 766448043 285886904 431026219 522948613 69010675 459274982 596204414 919280566 224769669 810950120 231582264 589170100 677510770 632922037 823620612 709791671 992737574 930378987 807702675 679896103 462712103 529234612 798159344 119444040 37789879 856824291 262605124 462589091 1308446 86978446 347685918 302435745 845040322 840113608 304015787 931426964 148483749 52155514 156433095 630576675 462688691 171023487 602101384 146155197 42937296 494139428 162503892 60370711 740011821 892716997 890476832 38171887 834110464 739434664 831245060 501520871 297442681 125417196 409555726 327540803 581975583 795407255 269399455 244157969 834365070 539646247 15027875 419873051 923354379 929207074 292347366 233414446 851167837 259993702 167705066 515201582 386748560 938327013 960794683 507379753 1097501 307591768 758935725 122380471 882360153 894292125 702344246 569642359 893598010 715552331 885585409 796986899 936305876 249785939 170741562 808234623 196028051 111908562 162433778 823643959 271208681 372846889 9560819 186467945 539468135 720981519 521055738 328742870 914822731 520515940 333987694 836166555 933039902 496360642 282188980 988831366 822903518 210604214 350570171 570674574 178892179 20578262 160939723 94734619 710652869 298459547 574724330 636909891 356982133 824259897 374045403 54949132 822590719 926623903 630380359 449564515 235247352 797801782 358471644 355550757 300927560 23161081 698737367 124401523 438668882 413108338 241452781 17418095 98299866 785985717 342312082 559662896 877178579 524254948 612167168 23493600 694906398 104866525 389634961 622046517 181123049 712820323 381823401 749121135 549143684 280197023 299858774 547216043 807155074 635393967 287330304 186834445 645774749 760984627 662404540 775706639 418010982 792461515 525150311 252901976 934471544 616317365 897719399 282089546 365818857 380175918 50334249 672458943 758549741 822516057 869586068 449037072 532788736 4953468 56363527 720721857 499468173 514456374 454333721 772571898 325446504 145094660 368262687 229755910 595494596 610783775 747051892 644754640 982666662 143293049 806402532 559166705 332952501 491878870 787441854 161754513 589596148 558864762 873304135 229705384 29209116 383004360 527175568 725832873 289182151 197992142 67763667 925029036 390900905 13896564 107504450 202754296 437170632 102203406 825739755 256445307 967031222 455562066 290587294 107400399 265926422 756297577 321080102 682738317 479709895 760449119 960594829 993070133 566516324 815513497 476307923 720774272 700262259 546672479 327351454 187315482 314045892 795143790 801838626 768434792 81858105 772214871 119582459 486310512 318451820 742149345 113369610 728991514 59540468 813592227 452418272 179209349 874272951 175483498 755190340 53862981 561670747 178455950 578422119 534820999 510613314 946815162 472721966 945450465 184650790 60960027 576683022 639665724 719369457 739750706 984080357 642649991 128217666 789948534 317061571 596567329 520805755 613167635 648762588 72690097 860032225 962522696 411003912 468552469 480895034 945661203 168268247 860078415 241340566 108546944 937616853 449560310 189169763 490847417 829105355 253515424 156244766 338084633 858090530 442656395 21112661 182136656 903087388 963516252 665655350 584971424 469293761 434112913 925112082 25500911 531382625 163908026 204741889 24967008 682724942 85800410 815015893 51341366 426097860 347018168 239894879 839631526 610512148 286089267 451768719 448193990 282863629 100649577 358425859 929365892 153746685 184764793 277084463 414954582 878354363 167520728 236934069 146141108 102803967 193891450 34808140 389484627 721859398 637987457 612937384 33211710 592898705 533104019 92401183 666302309 219836246 290428594 841903523 906787419 913449043 472342343 484882089 378809589 544471052 699347303 246257471 484733850 584394968 180371991 595359619 127138606 181590895 383607629 955110904 717204658 785797308 174710761 686655172 66041533 408627074 353339921 357597104 763574679 866397742 62109466 765736558 66522739 248972226 500187217 718229350 944023794 646758317 128243784 462754180 635066520 763193608 258936887 38486026 867074881 704972123 750353548 878699910 883783481 222653888 735088373 79561936 181983480 634182132 349339156 188579920 880676145 899970352 721189111 108012118 4108175 70805225 145292490 906570657 766044874 886475358 237398413 49643199 153921973 155555793 546028198 827183688 789968048 32826130 630529605 556176647 302344697 257768135 703624739 261203548 411461212 685720733 179006230 467913315 601167186 595894821 805761381 191291308 494829436 873343343 940002632 260319738 394929640 271404785 672101032 714955404 437471546 341610594 968336427 924246624 59842415 939625393 557626930 838499342 530403494 309525639 541639565 61611956 605982014 447793368 110119010 888318960 635243764 542246019 940506257 65827044 663664540 744996640 260293743 167662871 623075378 974959180 454363030 638284003 93046799 698931251 144458734 918128410 63773513 532904988 152785636 999120113 495955199 736254187 499973431 579971085 39108901 574756572 225614849 504001289 329174505 402386623 349796204 828635653 917263791 291065319 898574177 52283184 156307845 52290662 789029493 157338225 252437502 834360864 101211058 338870728 388760161 22711654 73655006 474758641 116958823 699760968 349360449 453986021 35101757 639933253 336412168 258176829 479646081 802729948 196644281 169154055 271728180 20225479 983582927 635843444 262361212 541687646 848654986 270568384 482314554 526059302 193298800 144949107 697345000 755946029 720279393 559454459 866086448 367272279 253136080 3565826 597149089 551964091 747840370 40126894 684403961 767621628 428176183 405159915 210707946 479145653 801571677 796580308 195542983 343377463 643374660 249413980 101051744 765102566 191971966 193667383 143559711 823803482 323209067 742606167 784340388 289428140 316848233 72605821 141063283 887630389 25169783 615031677 997317107 404909355 406748055 837803726 201568118 189239434 797017063 325589298 553570898 431751719 729468858 437649524 413536522 823727004 937303679 838766594 370135261 529443144 90388294 508152519 373012150 937661264 535176879 859747408 32445471 766803457 315868239 93866002 59615693 380398534 914645549 884946939 557947142 277756065 824064146 978064982 944508068 850935223 175418324 212578514 739705194 817086873 621839347 930095348 263559377 763418633 578399149 681988848 626498824 544464984 373634066 493513841 980707247 795470884 814798446 822515355 163294667 241325179 753175546 902139642 103292682 635399380 578493809 950308465 666896399 381553398 823878679 154110697 240422912 481300553 854490672 71056824 198780187 952111626 532878625 365059973 221511591 734329227 598854853 543198653 965484168 131645724 579522821 283258428 598018891 399690990 858154042 353380853 902381809 266401657 732288568 773484394 257868348 904030977 442547704 658428917 427608378 737001189 964931998 677793037 305920730 743756655 362868548 336703253 488790777 887345487 876619770 946330626 206887387 688850795 1729692 222912636 374978769 475267727 281484751 793153952 831078432 876511385 742346117 122494142 678962264 480041044 921816401 924360525 166242564 557761554 150376232 174944082 471970644 134167073 230575517 70183567 927812197 749597193 811372195 545426205 127735873 829710026 263431261 585916183 64079192 763367685 822362904 119656722 36909578 616495588 77255604 315960319 816251513 519438 435719683 971782509 728167003 424967774 216882524 926806712 455843681 308916452 713311613 723377288 536537734 88241259 527091155 704239856 612705777 225188648 32477661 877959138 771322947 612086545 34662245 267492071 317681402 332729970 958470338 524183389 268915025 490291228 983904055 325757834 419236308 616783784 742477545 862518230 874438887 529926050 906377501 452414125 304864528 963170540 632143401 780939656 713189252 440439474 976943929 961494829 958563920 15081090 751739390 119189179 161888221 734537865 988387220 464198475 139001530 58857362 131359456 508578160 209644974 968455206 249762818 577155292 413902734 744483181 880867906 405739003 117794192 551737774 423681195 308573374 93335148 984596397 5367996 703529571 378961870 407139667 920409188 786283407 149120585 255150334 365146870 229912855 999161489 434933009 352480855 178990770 89111840 45917609 401085029 735500925 583382739 967543778 519686149 166767305 460174701 172999596 846994403 762309712 284912362 944856665 905176868 227460414 406313425 896255295 667060772 184452983 652210828 406890555 786830166 58920701 639958322 164013819 524235845 902683767 325396500 701574568 561049125 649838111 2752073 552558236 138173058 807689690 497797 790640620 943604315 97631000 721030698 11718919 83465063 20125154 251279382 595771330 195743690 818174054 892508611 237194423 795651433 492214003 986688951 392427105 885922855 656594917 538967863 308301052 586307507 489101558 137701227 771439974 271764529 91779403 26876428 744656048 682636182 820764260 87996688 907331996 730740744 744885241 172256399 506597477 674026653 171572843 71824346 251691185 842362395 715081663 997058878 55720047 54395239 215611493 618947399 249780658 339960213 381153758 919375050 738094686 844715498 472066883 396045646 540560683 741241001 116982011 71290797 504562403 601439637 672587884 708228215 538562907 236462964 870003968 554106945 92284395 730773583 922041910 718669457 442306238 364981969 235580594 747283456 849177647 995926483 470284605 31700690 123956553 686886055 673853778 194436433 965049429 260663324 848205921 590291541 543077454 716643233 677947633 441533204 981798097 622131192 230745303 488362022 448179805 863237788 380410867 765767877 448922083 238880390 775203952 339609790 231647142 752161061 697121754 288667523 632210325 550790557 197908507 714924832 84851820 810254787 658093971 834228033 605773226 582308887 932307177 846929423 293067968 57321494 736645329 612435228 380329681 902014625 759997031 811529611 69343648 229367620 812447160 409325510 112857680 96013442 928206323 810002530 773562957 154947380 380889843 511072841 941043167 905193559 827021958 317073492 522255358 932663306 395583997 661734830 955133444 188023931 322904288 272482774 909429358 383115531 985582811 485122629 233132240 524331768 479264995 505267674 103469720 639529424 6613639 567425501 152277411 866039264 690580108 191085302 673843772 740714037 309777982 314783751 159248164 552532417 792587468 128909137 427868326 185766642 257927246 539041105 996726504 215231135 422977503 414807255 390394642 108909191 520786242 780133860 502131937 326592464 581541391 600737494 461830943 265638744 198827312 978590971 722322232 740211765 170798162 447191373 713650735 226165216 57217353 945226675 4844906 256379258 259345626 357619788 285408663 269416166 222600426 647827142 179523783 364076739 926831326 992399236 648149763 543217135 456975179 881148977 607157385 501435023 273966735 573335039 477508672 178841535 773359485 274355616 782800386 171688350 595987019 603206277 872509081 472694471 26771066 968591548 39885532 502876207 799094799 277774586 933257891 370784152 227530597 758431247 816915127 840072329 997123314 110854505 132738586 967080371 639500322 918485765 309241683 358116261 392896195 292957264 428986098 215373691 327168398 142280184 268640933 79417699 723175387 609224714 244639578 678085197 609288120 826419962 952727063 697724121 205367289 290865202 819718334 28031554 69712476 699261200 159794187 722301342 126740266 49961495 974376928 198982808 379245884 912650596 69918026 738413445 886312043 356385287 831756596 73531106 450496155 783047210 70033821 537211277 608138199 777662899 794836094 929002297 385867191 647757846 928195307 71015904 122309643 24753414 776544181 858618906 103382684 675407883 49529067 927446854 455731248 658167353 616454938 350657211 678930025 896335533 62015251 789917231 442250251 243099517 696542070 713913033 557355919 994518006 604809423 470666636 548856156 430933332 441624358 604026232 279123309 142740172 286838603 931365829 764530874 113782213 755877551 177431944 220132299 179221633 154148085 303771770 108273234 821637143 363302112 44163017 576498084 909114012 717446289 641907545 848009282 290657504 988092012 541894227 351964687 535830421 912355381 502367716 559705219 830804827 183000699 541103264 189832617 975268960 760961796 756325509 818701516 494046057 860041087 680817539 836565247 281201125 966833412 3674152 913548046 768118038 243608753 306801197 478440093 883423536 855768289 277252575 700272583 608584045 474316629 511678472 71902388 948877761 536601428 976661100 603320069 502401006 690681757 973178122 991735629 883294153 661060953 298700907 503852533 558036965 812489138 377208444 627371197 447464994 389695173 277288809 567609431 422819861 612893139 831794296 969573810 304931473 436404209 142173905 334485545 680380343 130779679 609794711 302394687 961182184 870630732 989129044 426685201 507761564 894715131 595787469 893998244 433963455 565458843 4195359 975436747 324251997 932900472 823948146 806041836 528142523 581123163 870928120 507204984 550336481 825287032 843186081 820547243 676564118 806780872 331196874 635881758 902805216 476434629 664388718 333796990 290742337 322234696 372756573 902626317 747341576 157493552 747186759 457027396 77221175 367226897 719683887 748274362 770201369 608255160 698272473 829799383 118990182 12677797 829298639 881741973 513204135 200442744 682359058 239386844 997733799 863048107 802867396 780929332 364863055 614102567 674630061 353482925 407125676 916328034 81041982 491688773 531818278 691663218 315965117 400192534 248757016 70382075 392546815 833427606 732740072 269508103 598114886 338991142 704456024 922142957 165088277 929803498 470018578 534986542 406805231 367396517 456770431 332901725 558141423 784402099 679149526 237227021 945097925 846930287 581102958 299389551 350443939 107502883 889446932 89235126 757181676 985559603 808747094 388598060 481861801 791879900 375835666 612922629 789202485 209910253 811519954 277903546 631540440 888471892 852699651 244372684 514031868 968364689 76691094 640443660 302767442 278682582 85504614 744257550 166871604 896100135 999718259 592205467 787144740 560480585 33142796 422513878 946521559 851877967 740122134 78316207 126941138 471146724 129605653 155925520 574901432 643260503 22057204 31102409 612311323 831134961 397069137 848454211 690514061 584471919 807375327 792304200 272807320 287456801 737198337 697036017 125507107 212160710 883260832 111685397 481248149 419126506 421538005 667351278 276156183 879510388 133813302 786923006 472868642 415889276 358365127 248957800 769251730 750402089 670656323 93567850 439756065 430372406 372101140 462036671 930918892 81095795 814891392 913434911 490255152 250926818 333415032 622350657 846458421 781723402 151895626 247870590 30193406 424070766 346993267 790564062 63538151 586184112 865657535 287831271 54638887 971974532 961744702 873174791 43996478 649580935 968430132 235953948 758420773 105521039 338983126 740814915 84100846 545236905 101622019 299919353 843826631 608154366 144431134 897789651 130433513 958493804 265987748 621253065 47598480 567294264 991736601 339036637 580917068 349786580 40053188 388752176 57709098 584507745 71537749 994459809 395992825 935738935 258452298 85987070 850865212 645188985 412399697 537033739 292482290 743445443 209300291 829410892 816536124 186175732 747716077 420547630 48047074 717264728 955826111 708094605 480735789 891587507 952931624 348792908 39853131 58060105 314285122 136535804 936461180 41427820 707411493 66334889 14061737 446414639 57537628 235185655 373001424 733752313 25367970 276796323 499222196 317088277 960385031 457247520 497341721 544285965 441192211 690534803 196695429 77955029 568028956 512855994 117625194 245222796 610704312 793685819 39310569 505058748 201438389 279023775 415682655 122010964 828682021 127062354 225288930 946866065 543605790 527045525 976451237 970053301 379723424 41417139 326606230 935032919 609571037 370207412 433708022 440430769 67069777 356072832 452840644 525422522 433681651 382203225 353875618 560655924 973646727 102034351 935173267 361266948 158462623 74841310 741218893 618148304 122019426 720681374 133114665 560528317 506816341 42872480 377266847 973806514 706240022 13220226 691211130 637445559 5976810 487514335 705025588 845636739 797829030 534085036 870444045 923456572 689132530 744111681 637693606 412872881 574295803 950854848 118120279 378506712 405598101 988647832 134348560 32385440 669483667 848551722 204463167 423741053 529986111 693607431 145959820 666908815 939425773 518579110 422524357 192382879 825563637 734188812 341678328 506250789 933888102 882792096 476769242 928844981 856525497 579962916 698638253 26614132 356653635 302597532 574425365 459475948 820257331 350326563 760830414 28000920 159507408 16080661 14958613 788677547 706302548 11971128 582829971 665335854 97315705 253086651 30866304 21371773 125765918 568841269 293660233 544466909 5376978 813166914 924275404 711960764 891120030 591615230 732100169 121525714 912106863 739572573 832604276 665139575 143404955 976086960 958053108 167520397 848965465 791932207 233469741 581388150 928097997 951755432 961775646 82887467 332155826 721212304 387374896 697156214 808244430 516130164 854259484 558669814 45126668 355421635 779220807 136358158 34161557 835248319 312418875 594929637 204889578 103950073 502910850 243852708 186363165 168893859 269774990 336605731 102906002 92147343 431289897 134797519 850334401 585699965 817165409 687479173 289676652 785592632 630911738 801826361 251717578 892674126 55292185 795292989 227107175 510720499 832066913 424101096 836849130 647327870 257580031 620261049 767890913 637297633 167339355 827781251 81881154 517084226 92009227 46469477 635312129 695217701 895990252 290937810 920082636 964094568 637120592 559780180 140362479 481843493 638192091 9503712 271307982 184086207 369673042 619455050 161474690 872280633 180200867 672434320 120310547 18830915 936500112 190309045 571170579 60040985 587720667 87283873 506623004 467939371 780838249 590998286 842435273 447396236 586439832 429966349 244198669 169601246 936326254 916245457 413978711 181064797 7630308 37344136 176909292 851076640 488266781 551362832 817412124 163260126 315047886 977922179 506259807 213925165 928259707 324943367 14428760 14876160 595378172 199477249 320870748 153312093 202970734 383728604 427162592 888823590 743976743 826661476 657670618 629889185 943957344 876802180 51931970 639163539 509518791 119752954 843645427 724272105 471415581 35404274 135858915 749603255 988459701 16113508 686005983 933989400 448423191 215232303 438713912 399891145 904503728 747922612 268572057 314089285 740367551 63814068 869261763 363665015 389132262 265143132 987217865 805033606 102372085 836852273 46943981 415631584 826618851 814049820 971928273 989165434 959281769 785528478 838803797 880160455 379619489 242430020 549830473 265655553 68087228 991941643 240309628 925438947 181637792 692090775 420048816 458456189 621031641 808857304 476155540 716578141 480886296 745029375 485612706 892985313 829470646 657689823 49696830 18112945 781935088 998604431 784983185 647346788 126891949 971286605 530480505 765205273 830127875 9544709 116754412 419608291 793992806 263112051 422995265 805537059 655876552 573013285 537431639 530202880 937929917 51806723 36299333 771022601 978334740 725462365 136252955 120460760 476943047 501879565 594316733 19001344 920861015 970433885 982730737 312990351 519151132 767647566 10770910 890921304 447119043 804070751 486772163 871057343 527616021 754460105 960258457 48495457 856084626 524912583 732328228 197577050 911162345 294380868 147302259 37462252 607962251 899216631 898016421 277100426 777606034 752566612 1849467 497698003 124717314 149804619 767502831 448796893 452367746 525159521 838718633 511422498 369471422 500210818 65679966 692421290 402894806 941875749 871501426 894115926 101194929 520496628 83621500 955387476 463088237 282440687 357223284 164888629 771673847 96797887 441694254 516195232 631334772 768163324 405334195 876929306 535788296 790514864 304828602 785246393 36260272 467392261 567676792 239402915 412792492 451858603 179380581 779414151 870210504 855573391 201670688 726710710 271011884 373517230 5757418 424693496 371059961 541559790 425226092 52714532 111185866 7442871 49292134 302504346 3167700 572339018 235083820 843191789 405265985 153000524 649571049 545710713 346534842 78299081 169248976 14543102 140420962 201976675 371427408 484102638 264164170 362934404 218410732 832961490 434091946 446299486 162389886 171475168 44727738 679439868 946801478 574752151 94227519 538199970 991773636 64136495 957093219 824688226 382389950 999751900 592244877 801333235 79866036 710415684 416998871 788455547 667985233 29050396 392797884 682709951 711629188 313387386 372926294 766575646 109822986 189772665 24670886 226444565 296527641 562538851 750456768 84083804 552008393 4142571 999101206 49656139 854990999 463160309 751967044 514175328 432260328 681927466 521056206 690289833 692162437 554875379 521622341 282115285 520102402 351280042 984211700 329819191 306502536 362231083 865540799 414606862 694853913 79363527 119319317 851558770 591396229 155992870 802345576 339620877 176045520 124777890 95947307 486168899 683825811 334082939 432349402 368353879 976564348 589800970 135653034 620227602 59737028 700559374 566525076 628177790 921834948 202351950 914890284 852496311 553439155 524326474 755078147 248560718 153055768 883504445 242309494 164664596 110111303 53413389 859630292 513642675 466856816 721532510 768969094 70953583 691665984 653628852 615813533 177962101 923826970 123307180 775025647 607375912 884669729 405629073 285680325 871751981 615120646 604639955 229358174 897323817 413335363 300638528 103507468 495274866 700779233 212558593 947704741 25746768 557493128 538844016 502307460 164134855 989479971 73663412 971519583 18654375 481740910 302244533 194489146 689379861 560369973 726177720 245566738 889361195 356604351 633016883 535095192 953432287 148071043 55126970 603629387 134537723 17482321 748816760 351520207 88118133 672832584 86927579 734400673 976103883 245494848 260163305 855640846 231559811 502335169 611751901 46534364 136308228 886319322 702830848 51508741 924258744 257122700 138604871 634610135 737143726 880966366 493806277 980062802 44019808 801152433 819200306 421283061 465133170 895173081 366888129 818090328 188737333 92835140 41427677 811084756 128490153 983889839 392669915 743291992 105310116 641997172 383812102 778904368 225676220 936998535 991938659 388644145 856730888 913915693 575516391 165016954 528379012 660145487 865946476 976842744 677838576 903582716 85627969 348498408 927977062 28237868 308983684 303433235 226311046 934110900 694201296 360482132 155863552 342999029 843394503 164114472 255033375 271201098 254669315 820819027 579880311 44204003 359800382 457110863 654973814 308250440 473449501 516506137 751477673 626930527 844199247 170811274 937670558 44688455 224356317 305519304 56643708 701259580 212068082 770444618 985359634 677644273 835724474 65559350 808897177 956165131 430837844 33195896 184706577 197536773 954120374 733810056 835423225 797353561 753611225 656556723 123308209 364505538 386162863 244666613 1557226 896404032 411690884 884068393 511482906 479452966 388618446 814307577 491749148 18227047 774373969 813901286 800744230 365225439 957762727 916786154 711118461 722462186 375808591 584307920 74367557 511033740 143685579 854239885 480081945 643981006 471814957 584264171 472639669 784044177 96857231 522746782 480322514 158476803 149987400 746358186 322141170 808252040 960531945 340218921 226312939 780786623 137469504 750933810 391694422 54371464 867714016 925151562 233894283 377937732 666910408 997675090 638547505 86875607 781962530 211042849 893177648 30923347 808587237 243799565 37816234 528003890 31821861 119326555 660931301 287621827 951409869 690380783 766828834 849315363 504603690 133692707 975696864 684961899 700774889 29270644 839376241 470378101 834347155 405324987 883773157 579202713 65357034 81147606 240488367 778232193 794288169 430054184 63821155 847842094 897961841 766188576 15992261 85330684 365863484 736259047 300060596 493946128 686413003 176769213 483200094 265163716 437456275 860136647 113577320 879522825 101300579 961243893 369251913 138511044 607273158 205970752 505959814 893821897 810967175 25849372 73870576 672517905 547990348 484667862 791716915 759831277 338707864 439231732 793469562 249071351 865880174 824866683 961640409 843656809 47178383 595929670 156925188 85564680 172994369 87945872 447917618 62253202 661367905 54929914 836847887 246054987 546302923 983345745 966345668 388086510 255442816 57329843 140653545 355210414 182159500 428383815 604566454 123076290 86329353 737801632 847851505 602932692 219449911 196185911 630988921 381807713 307019451 426180134 64350626 290189337 601742593 187908652 359763479 118532613 476269157 9891159 746934690 279351765 292501982 711778957 235507763 914722555 339142603 827269577 521662623 779416782 431113042 308400402 78889922 228396597 217360101 384414292 398030582 389671981 322764937 923782307 1883654 123356296 693556504 179391069 144462361 433972368 917444487 281295119 191499333 456775827 622535326 529604954 429823846 117303540 893569777 664889933 708739232 356846240 555217127 772883607 789688217 740607770 991838892 539005880 863908616 574324174 281145215 864256943 691376105 26931921 269407593 556100368 336809682 203802144 324983054 827340611 160281245 614306449 833119910 323928155 483299049 42110158 761095343 630096351 56095601 960574362 595293024 107567728 555934480 258693435 674484467 139359593 82405644 355698341 269168630 356284361 879475911 623601993 245705470 364479073 994086535 902058632 441264569 528244746 561898756 535904053 64388256 809593216 356582759 777040404 132721045 715723192 410061593 921243910 554556055 137537658 128546862 835406217 377124728 76439805 988262683 367720904 241464855 56432717 654270426 655761476 666252515 418921571 222572178 920814490 576176259 105070401 438171904 211372759 775355095 365796028 367565720 950499973 970442499 870890249 721220027 113382746 895078928 476283454 733130736 257140428 191429791 463745516 645541594 571061731 411162607 848938733 850315790 232990026 218858421 614507596 133210824 730793005 799138377 134722424 55761644 692190990 98131362 396467151 198172550 279546040 810253190 507667340 674204122 654505119 666756991 877918271 489411914 186976222 605989676 591661119 388315888 763484863 223561315 406027418 103624062 309559350 679386419 160822364 746931662 835045315 85183375 346042681 37683058 56796860 713976797 101788609 454392281 434996098 482200231 858194682 318313767 188104704 790487029 307734775 783048020 702389307 107770413 257811130 325386325 144672183 375449816 623522228 520734769 36171197 351739808 457382630 793484780 76586168 404236421 483512234 756327466 23122868 95992117 646405946 119193747 506823889 563920955 320815142 971971224 92886071 339827297 711659623 481834908 729759313 446603837 515660241 376194278 332504818 91652169 24041894 866408885 664372806 372956223 548696576 730709949 615962094 326794996 908728028 713528297 601292241 374526118 28172629 997356905 212349072 792711894 58070963 1867987 552225548 647133454 401317346 217317701 965857823 15900795 58118863 778511142 563982477 164293746 213725435 54367981 619164426 702117062 377284259 756369486 949477149 446844518 444293281 62353344 931982388 174350927 169224365 23901559 891567215 14356378 860689675 371423022 338710570 815864427 835553091 29331055 914729712 434438892 748988863 363529584 590945823 897203718 148636197 168474984 22009158 154120283 725492973 356654271 877422031 902695301 410700920 483328649 547428547 403973789 555779793 53462484 667246953 966251019 195668310 835164443 156839408 238802901 467948189 107636952 897071336 441340976 834863482 233325705 394917015 263821410 757814657 382815426 18402177 13136493 470416540 423023616 618665070 212561380 401847628 158255226 643402596 211268172 145370579 836112901 326724219 637803106 156630646 941824350 416860732 688336531 462812245 530003457 702497291 400876477 422328074 438886554 579753104 763361581 161857062 775775700 594052982 172013445 980115033 288932012 708234198 5709806 712892423 769543368 357360351 780077795 14298998 553526294 85282233 466622549 2693613 780159450 957685990 24223204 925233626 206662117 201598431 927489234 563411716 268385014 252573979 272163566 348048370 779852191 637692456 48254799 36759203 126152988 266411369 939301440 638901854 80120613 258210376 333441323 623254834 312245711 946453748 992938309 918427692 70914546 580734114 316964746 678389581 55862949 83231750 263752346 488059134 879337256 29747618 602696324 45140314 297563841 784869641 267441260 66056021 310880365 548026164 851065308 265792194 594665028 663751371 557694527 66471200 373509470 687145622 721327488 296981876 254093737 727930266 704702102 990529952 25469491 86828167 598104814 844923404 727119153 266635959 855978989 457686408 353254437 833107083 388951368 365232583 799833825 344602333 688859356 763010727 341922398 861636826 470202699 96289706 876903887 685057220 641625149 860878763 537806914 54318128 177464309 690298287 354190144 235904989 537107794 686223078 484172235 337812775 691885456 53157238 217273684 40561925 974475795 557257915 772720398 54785509 609999747 755389942 457748932 32662583 185785289 296725403 691768717 356815805 217135582 936421706 319384234 955187051 686863686 642812270 863865098 446665506 828598354 217192417 432060813 111707916 793824621 905844265 668249553 389496813 277617879 984183562 378652282 885566316 930125345 377028198 302272123 339494825 624706325 478309553 756591560 8399991 647342355 352253819 702163109 140987441 569370975 2405705 389894475 441083251 513754443 295915950 179665131 93724955 120594210 379218898 928055492 749699735 484900309 21683403 590212425 906103271 219706362 405659688 612989594 733998413 6241323 557011400 884787777 448404022 775985724 914154668 609350183 276807911 807436149 762503199 19956186 290094388 268973348 705996428 923999759 628099097 421982674 901814732 382643099 194183600 165261555 617185146 384302841 435509135 653689104 489493380 887116360 157903702 300111891 407109774 284679708 525465411 299818494 456883071 304181889 522997596 872013748 216770929 318465198 969987819 248028645 827162461 690548076 918828175 272705123 457835384 488087679 490319462 981651095 854680914 254550641 557260750 832309742 489335508 928951679 77121313 784810281 758030546 388739519 403217825 301483538 263607671 131273878 415120641 801913487 353251924 251666050 365324963 24902012 3144791 602422091 83839718 281454970 83700762 150035984 67343006 850678510 77630644 63898628 271134842 917921361 914916001 174879258 116738127 163670466 691583162 868733935 298444354 329158362 447946368 386190806 180593378 586036791 498279307 100503131 85747513 999501706 746898313 209303902 350488815 71537542 34669931 427807031 422676609 274738789 562716988 175045418 484438347 672247673 805719250 329399966 309340007 714100539 966760089 46795178 968600005 790438688 888048436 249560913 497014377 900840482 561986643 814141655 532974935 452871328 459768729 488202027 399750730 306524335 164817529 618239911 251645171 725494759 425199890 808467408 51090488 803025777 280099328 701260143 601565643 237447666 966923941 473027861 965066510 796890531 356478973 454116077 413145046 379177889 709660327 944898852 254862293 46929057 156566854 835327185 445407851 425656816 359779624 876909770 395535057 953479426 819573109 143267680 962995840 379967582 634073889 873073883 448201044 368491518 624610779 581088023 616743385 738979650 816575830 532614367 257987392 679302731 721356378 201760299 349849265 832755329 353059555 576181916 737739827 323032323 351470950 12204232 78951757 320600857 857347264 38008308 836966259 130898278 443490318 571474485 739823769 698552218 628627802 883384417 523442861 814459229 557301880 561681420 500085918 908537030 870011236 121042750 362809011 801105428 438727436 852145738 514774695 740572146 442638221 479327339 883876619 259781193 461768776 827497368 290974710 652860963 456397907 575115248 556943213 594080426 203442418 812587332 910051303 513001009 434111087 593813024 351126744 628852567 618638761 469861641 277522599 886949786 74254682 253784254 951572281 903477708 635576775 963541182 169992609 741165386 91156233 851681446 902273577 223338204 950007324 256662613 682038096 14099715 391457092 858947175 686191839 215421747 586298254 359791164 661898361 813250746 589941834 819548616 799177873 832249459 718051555 870853971 169934653 512927877 768097467 711119910 19173428 851215025 355736931 202241387 57295719 255971152 241347164 844063063 373336737 592283141 916850946 201931244 635248998 339679278 529150304 254903004 87711015 265477739 12265427 216469545 578834754 975383398 869897629 663281675 326903696 890536834 797011626 49739209 332626068 543493277 948807358 997342217 621328271 830543047 583907102 16456471 206526597 96023859 739576695 718136962 411176292 293598992 945443787 127991828 63864395 799302642 172178869 353510522 502841982 172261419 171163486 616198805 724954338 539661146 265585376 826470722 903729476 107281486 438314390 924405449 6509151 800838694 753644411 928840503 805449758 779902049 352635560 860592275 967916473 152786721 23231715 837677466 129470944 925664799 160638831 797407023 938549081 242097358 467865292 156666113 650209743 788408989 459191241 766646655 260789444 375032714 931808933 99834005 389599608 759277213 673161174 875381246 282204505 498629437 963932442 102904318 111386735 776079120 933267287 920868207 890382699 340080355 443916635 942740222 679804598 834021719 458070446 796515669 404249590 547486745 690939679 467940126 692252202 857903763 33237683 941119534 781375955 109646041 641533846 73451998 102551616 147340988 496682226 866995558 611235292 838906182 502560675 538497770 616246375 719248540 206207883 46618579 806312218 112443950 32805797 933331984 262614406 463337780 617579774 581663910 214752434 23085529 270890450 999785369 755727615 767600332 68988120 24605002 498068410 425602591 56728440 913503869 607097675 280504725 509595160 948497584 785475695 489876801 26984610 100493316 32617888 326486630 299978400 73352141 408257552 843263027 536370488 13879980 904355662 767692254 492682894 741172984 47136495 463405989 785554941 306110970 721704234 335798141 591459996 42160930 774361445 937334741 891289895 775368317 223239713 600372665 810512922 814467166 351941090 816782102 689146599 115883573 969801766 376428095 48976823 618330514 649898922 534519573 684702552 462104311 242060821 633178058 408588749 113188733 979906627 10380478 238505845 309018949 330303436 244548345 885058258 179006098 556609446 848889007 530506098 195647786 455757554 945270609 361143575 506788882 994894028 843879042 872141580 15882618 47303996 725967634 967222423 651133188 709997008 489360469 195374841 775298087 15137689 230462293 395124171 143214977 378901212 721088966 258774993 532962117 771343182 452925467 527346595 32637640 180716234 517648016 949574665 48834206 298959741 38931160 612555035 54489804 761214837 950072934 764732556 435853160 507196863 495621601 570906741 485905491 425547943 103325009 899277966 730477798 183223295 527611063 314228437 195698176 619890479 327948143 48948333 587249936 112881227 331734693 859347790 702791416 554657927 13046346 20055014 427370832 736466529 518064408 931912043 899456643 562572900 835260645 639450397 762231888 254112722 358227510 575133966 352337067 653440612 685639254 778761548 278722591 742344362 192165751 545615494 268727756 86080296 378217093 583328476 907972468 292271808 809405166 345856817 966069797 624893858 977890136 899939359 628668190 424964095 662407027 34230435 851077606 482763637 113231150 930758358 580030549 244271989 704636812 872827182 776893295 276285954 577874764 386849689 27377590 847010504 172927780 744751636 976930495 565083880 248260412 958840597 454865288 2634163 273592257 67941643 115155649 142008627 78191092 756379468 859787129 393804954 575416638 692223951 37506461 110167008 843647372 160181668 447271954 407634962 18356806 46011105 565043262 254057444 52758174 563456642 509181985 798233217 930297146 643528016 443734718 234063453 946779616 910680719 911859060 837659217 308898952 785237074 996647314 996062556 724263407 271022142 329065723 169928901 665886863 289066725 774472295 286357825 795123648 230256664 187511311 311500051 874932747 6486945 297571421 64181668 940426538 568736465 948021916 620079866 695826495 548439569 570020906 715633457 600166891 189257456 345865659 963034168 71250739 655558648 851360442 907154479 630983249 821586993 350040751 997866240 975570348 464098360 16831433 524836656 367115011 880432111 70041183 989392925 513895220 31746169 600217802 782551065 774636208 798123610 928018540 39212553 866030822 99513997 69701468 535925 394314230 89429324 983259049 280197587 654177864 312877787 782790672 212378479 465675746 343312518 105092517 533921495 895421449 261360705 496505972 343846042 725217949 821871009 900649903 193075841 319877190 463901045 130054519 476163116 201738818 340919859 650711969 464606027 952247383 708727010 64418361 931424135 981052541 459620984 460601346 762135610 35161277 329592946 581409555 50480858 608678868 676813762 555529888 789737496 174780003 127973065 805103543 636311431 985520575 273684898 330924554 401586418 644168669 292301147 839929238 464510564 902005938 912360202 69197043 697802275 56989728 262861400 645641690 750740028 929908463 700332354 615311927 778868923 337157934 897332781 724437254 921049214 554343746 139052775 479764670 309863024 963663726 585038556 761160247 394227099 748287868 959561877 606741700 686487186 607677808 272512306 421221918 771817226 108583692 539430021 814203220 376965847 323027167 927741968 221751338 831970792 10894991 507208278 51721489 913783835 331705190 665038054 687807907 429240379 938638246 197883049 680708527 387673580 629534608 51803489 996753126 769379238 528881524 638738511 587347473 686570973 62123649 195612223 511315736 180814396 305651373 646380329 470281415 766675442 62923687 612642718 306725670 191639907 214738964 687938463 574411549 673569938 644429035 664209486 141206074 633266645 702459965 35500080 620666176 958504293 727212550 36541946 352492206 173600244 38142175 547064188 663737071 992135202 193374858 115215717 673513375 343591981 765803849 371765283 440114137 759622402 911709945 334879175 462408402 170323200 142323184 37490675 572808434 240720428 773697961 749034036 661580226 980865285 77429598 794797857 170163210 359245973 950223948 627947564 666698395 273399494 361528352 778091493 232404910 692903446 479600389 776716811 21007773 221698296 402333177 275985229 674882635 158728998 717921336 750453759 405706199 728081996 278198390 995702034 847509456 479599286 45469071 169540576 577184316 323364777 755757976 804313193 120246789 82537441 118938282 61917 241404036 570103058 32713728 871518547 582117701 801880686 68091039 556872771 476023888 813542518 502326316 773065863 120650729 541767996 655766499 23903954 291092402 402640048 369345354 713220816 557747263 832961802 91236086 757516896 435119191 239618763 477367081 709761661 78725531 751848260 994012035 745651821 950456867 903326894 780900406 771638865 834339819 562459080 748413249 101568496 776461756 722896390 344493044 376802000 318340387 673395200 897462319 651876700 851827380 217234117 976657206 344708831 899813936 727654844 953628367 759699732 298306413 537550142 548338551 449853279 273460511 789693835 477414642 342566853 591408184 853009625 685012615 534301305 620875556 218120704 364553193 849271701 686606747 682545444 914740465 122151170 983119873 995667561 695387327 540054639 205291051 914319849 618560332 691326778 327899607 485248667 431067069 173363205 28187005 997778137 69980914 493715134 250917296 481541618 510820385 755286391 52685912 698212297 514057233 796571111 876957812 226388975 223099109 345033570 257799316 250041203 979099764 148499903 76702101 233705292 82844263 205489657 596853447 225427856 296270330 961130355 735906010 877902953 81647042 63694036 491581767 580895406 155230496 565228818 400460322 229604384 642735785 362757275 541355672 704355813 512748142 365732965 707981635 353625706 378973191 109257711 598862664 204822505 659614343 530763714 328819034 195067442 587812034 966248793 687560206 237429890 878598484 366991606 982570225 652432362 497286621 877747521 620408867 784647048 752229818 229364409 175926693 433001259 444804593 806991238 603686086 395107971 545267223 471997132 43743633 687169934 470192842 50892719 711447588 238757223 230276487 102652615 400639269 561474406 893046687 315231190 632845904 907761362 761829112 678388304 555186159 756303636 807278500 989232511 202069255 40253350 761209154 439515064 79176698 488623818 673069684 295489557 729177880 201729684 840439797 677895207 549403401 573100110 170990100 630528929 63296344 163475217 428170056 299061384 565891235 288806031 502131639 309126334 154823088 329557980 388213309 389597096 985486827 251887198 419745827 982344658 885548517 531858310 131655640 759817835 815365772 277975210 526109715 911675144 661509550 270555748 714750394 215944206 27469078 714016467 762868805 214875392 640504416 758253981 263808749 999444580 933228169 955295344 928049686 677152394 773942625 173521864 953543713 982440122 727528596 842490274 15952846 861851546 674904339 258082484 531373059 732406027 637953015 959932722 148362346 745453836 102191808 306419445 476681923 554043471 198957301 576353428 740608565 413181203 503891230 817581624 556976921 202554818 286731133 627200957 299361531 272389356 378898389 52629747 403842149 512451340 325326225 964959692 735372093 99058148 769400883 278770741 730304455 640332225 51732048 802607153 17932168 148191434 373258109 524238489 406187325 89493233 291748305 470217966 653986983 317578441 216137699 227791233 323439412 779957838 725306976 758021888 189483422 901929539 569244232 853762660 916974186 961114558 439786576 654697863 631648071 342944036 442245267 699204930 752745746 220769607 619060826 619741822 198316664 388099626 618150030 665061464 758916975 928769700 480234428 424528469 58156881 197732157 606339808 583584185 217556111 730659602 452309945 18275851 932346675 233645659 167730297 927309447 789174215 957202808 336941906 156198917 302427432 404180870 270934249 262173835 10095581 620704321 557252766 537995583 589102859 877816884 675493809 533178532 597710737 617753620 227871043 230477989 657800478 886251862 304760336 453672341 317756999 937171119 62678566 352148914 742980810 630312169 638764281 771272779 59189716 415341813 609052205 242129540 983824384 772774273 937340846 926754736 717869689 668124651 850074210 50117324 678440888 673117498 188831810 663581246 630757119 67605949 428021246 657425950 651158393 212899686 132174177 781864776 614556632 825805873 979925910 304984062 404946029 690889696 250022311 690249999 125948520 391714848 394243915 739670824 583562485 221212763 681079924 774091282 900707617 356483483 19158175 330541056 432343784 804872775 185498451 151906906 237092913 628564308 408818602 959550420 269404165 698464968 84750452 778292035 164352351 433817163 632845792 186141569 234446629 135031153 503497041 717622976 353529674 400258936 158210330 527419117 535817247 858075606 290103862 396366735 696811752 743936408 716617731 170327108 23867603 506882291 201420354 219677138 47691955 331307991 464539003 404815195 694985806 459109745 836618846 100179525 59579556 937418689 712902839 330325409 833494720 395318547 120090480 89994052 965024060 933670931 846842401 903078774 676500995 490946786 547004945 34000996 40985661 714859753 401965181 205237503 980090066 908078847 893893370 736808809 558218065 786396817 470056781 867934303 529219943 977249248 774957326 942814323 423495054 29092281 902177799 929233846 504492507 912576887 247466104 529095384 624218576 303755148 924317977 356561053 749763652 444360610 698785056 756294938 226400681 494308326 785486387 644960753 297845063 799680122 143817865 743181441 799380211 154069516 48713074 167969891 462612321 956071980 681913959 852804881 370051961 527563336 84890697 12410895 914643123 823343244 945436098 867584222 785438738 258916580 299297708 866515439 128544207 724119955 618994855 358095109 770704918 463486306 618703940 303543171 261877948 716647697 100482882 138300509 258104233 288200421 218284254 350626885 736030286 378019934 895100976 814882014 242732157 642028643 911631706 461986015 418065355 416910294 305408576 915038480 200637767 645286734 468700340 21285304 282653561 494235459 53184825 522121980 400543422 143031764 28089681 218064185 84237416 740603739 420507943 449424588 682719524 557711635 804532287 623451100 302934593 168133457 684738662 45332518 562557877 590886262 739118136 443550249 378714438 172036176 422613980 690451544 24541673 582888549 917378356 786271558 282301200 230527529 12622357 589380659 321873928 107545554 524829216 670578538 884254749 549224042 690215203 492436538 993424561 320090351 837215094 609234767 213100216 957621308 967377405 493763932 575176307 620229815 324960748 982708614 659106845 547427154 406643873 401474214 176558701 976666595 961815862 459911488 346000909 466189013 966946057 208750673 460670639 291117429 420746020 462534696 393683776 447841707 613009493 920929798 534177220 669171885 725483711 121820573 377712945 341003331 543573622 725720476 477874043 148293137 922429651 208512568 322040778 863835742 677716180 820984892 204563567 854087709 315280232 224786639 593525421 715572168 780903993 235081370 841161648 784525345 852950664 649773584 771517922 11500818 719152231 76398133 567045337 505405066 107125752 690990143 667096477 633163120 942261318 173584043 487783753 980955448 666727235 429694342 485501247 820779089 7054234 13379430 179817631 711906952 285791526 923590235 500212003 577613280 546704403 122656728 260746390 357293328 180761303 750500525 651537276 491304035 184516102 20450923 510934870 801066910 539908129 185507078 93647315 144803548 681569280 727871965 425295260 204646515 235068637 590921941 248161817 967051560 661387470 674889776 866556078 443867687 999125340 78179094 454764979 294684840 452928495 4511019 989066612 865622307 567756455 467123725 354108445 887341744 571587801 25438603 343896602 885736278 878423386 655463310 314332062 4586148