1230
985351847 269542513 310933866 391471039 574607930 60945569 595773078 933499327 154743446 254922747 592670587 26258907 718722736 567270275 288477832 478463043 339094455 239912808 574058830 765936027 209135260 84959790 916595667 844190247 624281460 467797539 323007132 546702711 225747636 481247342 749103581 900098335 519098776 413814804 623589002 806466691 573861439 406624625 791889503 21839845 595920349 752197626 18510573 800727731 385351631 703368275 2094047 794073901 961133389 926676652 500307443 407326707 149680688 709004528 410620737 724129541 561391962 308551559 896719248 164877175 8433849 858230340 45768033 890216108 148141582 456658664 981592454 3736140 973174736 37817441 972991320 280338207 636119973 576985115 918436031 211830902 49166235 571326668 902430727 134611270 868177624 974344009 515267373 378311287 730116752 817085059 375537406 433044576 273185332 131626025 397725820 957388216 649843159 490399514 299120727 615956462 36086401 977958984 606090271 357882684 857864920 472501035 218238343 104828144 194128163 523052296 193079761 62638154 154114149 291922412 302467225 220084640 230210528 646582196 229614483 338410210 934589072 49531821 890927805 364870379 462995 838537745 319807844 217148842 926578384 147454002 872642578 102305618 607663290 100909510 479071976 535197280 689503015 312320207 305737284 646372888 913631140 721558922 434667603 447698112 947885299 626427188 385329926 945018508 569659732 255276655 560664444 790811171 138214076 873700275 172974475 739442758 333433300 531557187 298976291 549889380 807850126 922971462 96912889 213029965 484091717 551838938 377029302 896552611 335852618 102764215 155625689 602442249 274738821 37947535 592554609 723858271 430285335 996069212 652234041 872189270 17387942 116213824 980367967 943513277 934106854 740230347 634769710 350219108 433674945 433677217 889171130 520101132 251742776 102425828 304503797 639868672 568390334 924693477 471090570 772517125 708655888 509032900 16000960 102105744 763535640 132571290 602741929 584414496 145206730 215632859 442833990 47919586 607645546 242224346 289850213 495994252 259351671 923076625 195867254 676515712 705406625 912995815 797036603 723657178 609370747 253002666 979634853 219133842 40769803 904267635 292012809 168058702 118934195 262965131 150814990 241394957 251099286 290356310 567000906 83092876 123483919 130540600 187405710 775697433 483752284 346514088 886901845 963394453 709347535 674924137 551034248 123345423 277864837 529818483 578655798 514585758 903406636 302852929 359818816 65539168 802279682 353693998 563762077 374144165 733273806 219700069 976853800 838671645 305566005 22934515 907575696 610736916 670504107 258965131 164772194 838935391 17040858 882156851 605272587 447972858 341507685 162461716 393794941 280154535 215198505 850115687 421185967 991554713 69502179 774572777 151751664 76012501 296083860 797409025 743028126 545158573 226363275 504597245 7287073 800460090 167414272 901543914 577894092 776826526 669877643 796872217 364063240 469670456 479234279 715204152 66909110 326726998 773120798 771056986 546188840 16329242 83167640 123390568 89858496 233335779 784919648 750729921 63786185 425475258 491449697 854841658 865344156 426259606 246011518 99236090 275685262 125060346 805178781 137221816 996293762 592476831 74706426 619371970 961488467 914315306 203903888 248783876 144110118 824756360 505975876 361576338 39983219 529813812 441796408 684063471 513249329 550408241 773096173 187284561 822324982 671197376 957130443 146140648 174546665 861936241 18346829 402539845 114563079 926079751 159365526 132305935 121730768 20911503 867310181 107956191 349290944 417267848 309432171 850754605 217955225 466136324 832175367 183135389 114587987 786900134 706173518 46855236 63805459 123835788 100961595 165999142 379896078 733357741 183307958 331283908 849646873 624204971 675136764 703868009 143149445 871743710 366568521 586277765 76243338 980470157 700030907 98388384 414745845 610573277 765516938 45516054 16355342 819508898 863535174 184030545 236805781 875277791 434474473 196138116 131069565 479940426 369582319 850621741 184269412 829608690 401757413 448049774 784818179 112971213 658931217 792412502 153906757 102558724 7624111 584041147 89688362 701247615 717225849 372699728 157733519 531752580 672907723 484648945 138897711 227275559 215410527 697548861 56063575 112633659 716652127 779740377 290453601 175883441 474987947 917507873 279261021 149417001 160053483 11505590 907510936 234550367 471565 18700587 626205462 946995413 697508005 624847886 152683414 958815222 112960752 463578549 114475802 249517336 502168521 689348748 479417605 622722681 822558378 284948556 4918313 101166904 609026258 293123470 325378100 938325996 760218326 483202298 801238508 564991490 317624589 1778709 952293681 948491096 900175163 90236644 224928573 156772387 786018741 54738157 568933009 39325743 843476425 247160532 462957096 542587050 510042455 879087013 382226473 867820932 775765510 261633786 122628789 984021005 928305503 127140759 568364256 446801591 534397724 942100853 361280988 197900668 936368547 954400221 472610340 905922145 931114036 186118223 75734012 601666451 648997033 140186370 78248399 247940302 290161825 479027155 898300470 481914836 227557361 316515237 880341526 273627624 569514017 360478377 797955224 665790479 359793685 568600821 644584538 697059778 727914901 454563303 719434316 10482746 364834295 551369080 638764749 903127320 886111583 388009380 857929457 383296104 347716395 820741256 176118664 432653859 631605317 676227832 820970869 418291144 945334997 728358095 808935308 873686813 919858171 852591679 800330901 550436946 712223727 526205809 206924266 566621422 302616008 824455302 181907346 482388414 761970264 757294197 555686959 528044702 158599641 521884989 611126868 533407606 902359762 474293649 409058878 456479076 208029833 191540934 979388770 754237416 247804572 971461133 149814327 984577999 9421949 461350405 62572666 580675218 165852431 894263049 605643943 599873736 712963347 402886068 545092891 764608334 985155717 119992680 208261060 179564166 655522729 683409240 195150931 314926716 997647947 21897329 74056955 277397112 216120353 1808085 124079482 438613412 860194324 903280218 817351806 494191741 204056054 821166959 740824492 92345918 74644081 747298500 932895664 659631693 574209930 777192646 89479429 433937734 169255088 851573190 7134395 108934994 678476750 169813276 323575334 744254886 102053209 849874673 733397417 308511327 422780568 645868838 239852018 548388650 485031637 91254352 440323735 986272461 51275992 281204780 471850764 351679884 575983576 688973955 137295612 652523567 45693485 447082368 337490849 154154032 501122443 368642212 719876452 658851649 876444490 612593795 936275306 400117534 875625092 625937098 165301497 434035696 203544270 671958381 227099853 153128350 142793379 205440032 538017786 227669632 954877689 35405869 918992732 771701377 936639667 536462009 260693709 920141730 951784122 878529746 761083096 621593975 572536328 858063745 681679036 696409214 982868607 672306306 750497520 512793168 35689360 246776066 433872391 134936569 453232653 6867330 903818852 738550025 881621746 184418250 99888307 777865198 357003037 7409665 295954952 445297532 941504422 898349524 477050123 83132573 8860744 625520683 475823502 794749995 256486949 238744308 95315350 707436178 734071967 940953520 29974934 974894886 718434594 971903220 297690656 275112230 897619888 281215582 774907921 270430224 589026689 811012706 320798948 718545287 912741740 109510902 225680498 321224246 205780959 528070134 959396400 652408617 131433811 959852806 103259497 889563816 831757930 441718742 283887769 196383062 327626051 976718048 872565029 642390607 162030000 848204830 524312682 13730402 955296842 600202047 133958741 203439924 889765632 816144541 385198679 913602057 185841736 105237192 370933535 299404166 971095369 222074911 416231004 869881301 231109343 94396627 460504687 895774155 84078958 820567422 79891214 105850656 907946398 285081846 412704772 849086255 136005222 727592060 57766985 718452623 286114959 66561100 554729102 340750675 581405777 67431809 832427937 410786493 91063022 122521764 559937524 471789387 533191917 330517512 913551004 75684414 315080092 770763046 184786519 679184457 488928312 991719332 701944213 594321608 577205735 791003452 39459073 782693392 494212179 239702749 999246140 281762477 784414461 998437358 378312717 563894689 563524423 452898591 688103986 69737236 164806527 287506096 109827413 925190785 888366323 320241843 711441710 275975201 294839354 980970719 958196728 615180407 520088648 2059818 257047228 382489002 295730152 993877469 922861334 974377613 306293862 7221776 474787252 914039276 75685863 1692430 943572364 300935043 483406677 294670619 493946867 161196648 195509018 306123339 595571031 230367911 120985275 241659854 21977224 45151439 152681417 256377842 922735231 244877986 398478522 703931614 970356044 590688515 852242958 286012880 179378550 680021743 230282789 458781172 536032653 852716849 888299792 842781060 920374587 438870396 769700891 402249259 105893425 325036389 555543517 444034716 151306723 4800241 214097888 294287625 901915444 420577556 299409064 824296303 471634995 446433402 584174685 924326042 470127717 188805528 37919075 123797473 226564763 589112471 814166192 298022093 904464476 303178515 475631401 305408987 34244117 550119284 751822443 840078625 416633938 43485891 690808080 888099397 925257871 102972450 368374965 868119174 196936061 130252030 745653816 795383763 385403252 46794594 627457829 68478619 634904961 873342982 485032864 470796286 483746611 358006676 219201250 21980748 270101806 544956140 313315896 15217521 694245074 201845284 580631423 316966981 792288892 293968404 726087778 943979787 68854938 157637676 385282063 329001549 696696462 351415612 512517498 355558854 896595170 784183007 8974179 959210574 860796152 325921637 593046553 20147892 581419044 583517264 567037535 954040703 426332562 907064041 911976744 314504045 97550563 253097681 202404885 901360325 383905183 257267716 286005147 860769360 16345942 158581195 229637388 651538021 446902691 375647998 918267254 140363035 209551336 81318621 287156519 96761711 65151882 98461815 230453900 335765781 291880508 9536464 358689090 575043327 480805447 27553135 48499760 465670919 924467601 388279926 985220734 17531764 410467164 223173231 115038959 562600080 639312365 212196049 855771460 63777159 855727367 434921788 283630356 246811016 944103009 820776159 61123851 47172093 866206299 822888842 708085757 232562871 100129281 771778035 444204300 251559586 764435899 460063683 268337353 252420463 837387343 108605458 231074728 854083850 676933948 84946402 246797198 61445452 84878295 621373162 545642515 216139879 30244193 571358364 334797667 282224362 379365889 993413574 886778480 858820436 28784472 273275733 148205192 476823709 750423364 613617024 655258224 848947426 691329265 124915416 434818542 377218686 272984427 564415225 928262465 168813396 600747426 944419934 767853018 910041392 82002491 629494530 208040548 621071368 23434678 210681086 963371242 140265430 13468971 965745536 79336073 71681309 649902787 459387338 555649408 179523443 399525155 645282364 772914350 802872010 572692176 196664295 513940638 578667953 925366205 362794273 71871307 702927718 22560731 833261377 51576993 502064359 136192756 871976156 562081528 79998057 781423594 521122209 568327535 193860710 958877833 384403985 52414023 674919996 509832163 917968322 910993855 575110895 425947074 753881377 557290815 237770740 193214814 208126083 30247534 153979960 696718475 790796528 28711897 78745222 521861347 49956086 681735600 735728222 694172698 570192701 203793648 572832456 4161664 344885431 940627520 662201629 531906001 993734730 980365994 617448993 360169022 312005322 31322109 523560947 164837536 35210100 3484472 836707560 787417417 537309941 854797165 92521523 435381878 815448518 36900308 514376106 82496116 392705995 928094414 863687580 789570501 53424180 959347490 744020990 15110637 984205480 565778240 832367141 571874249 536305737 320891612 600962333 494470815 439268172 402123601 349830035 88622038 309868105 198967688 603612773 648008658 735836389 139999483 525247972 
227343742 945903154 346387405 490432664 507204140 730001362 22772992 286513228 248622731 74782762 80591556 291554732 681016245 98069974 441874480 316496518 762340551 59513070 131011667 568492336 106002044 938921618 598378153 926645562 371290626 497798923 7813513 466609674 79213607 322492692 121238286 83318523 409708281 225386605 836520240 4538771 13613465 713179270 969976789 31544571 297581286 679913788 212212773 198282271 27035124 644744165 785787568 327255595 995616780 952583299 507859898 160030850 200599758 87103138 82091846 600202053 164402202 439319710 509145677 566758837 9961374 392820674 629461518 972679547 557054958 682634490 640179148 306187526 737875055 734370783 578851761 297885335 281677712 650580236 735091670 764024306 250159429 513489298 425317024 995227039 862335646 919684079 76580492 277126258 381370421 554911863 599999049 404939857 181976268 205880956 29255376 479060463 285170110 168683715 432682164 359441117 357725851 543287284 224920371 267710439 859187974 141860692 244727904 144040304 57078410 344853776 640990369 261545621 269730275 673564579 391675794 189474935 503137657 924870439 860582196 399884814 616083475 647397649 475923667 571478573 616189267 264014791 932642298 985554440 771325833 572543454 216763864 841117948 296362587 871012850 45094456 856498157 44816828 328747928 244445313 70193660 869503701 204778032 268915163 639863066 790287087 613726259 997547224 705123653 571766440 487573100 595855677 375721805 160248809 25525544 934737313 615324720 258536024 319021242 896383248 727824608 769895266 299458391 187485287 356087722 774141562 116765411 202637806 244337320 645098031 903097928 212120469 920904471 193594944 461295287 812000653 849037263 506547192 232052282 233116101 135684433 226895401 961637829 380364532 938535767 440410115 681883356 618558802 194303436 656947227 745514814 13565454 652072878 525480928 972293481 83980476 446217114 148672774 127226821 985874008 162966368 925144272 320865106 185467763 932156383 435411563 485956602 276546622 81666750 847745752 599098628 125677305 735033222 101652632 81335938 658994867 740061473 519942223 34948275 873704391 304202796 665032105 585460964 945917646 20159484 592664721 139748661 482395601 318475069 509322211 549690989 928160436 921988852 961890844 129512163 346414567 966985594 57399474 899833236 113372652 627963475 538092969 883789384 99481412 116796447 951458233 725208945 932025449 177984019 127266980 125005481 27789224 101246863 31499779 963695225 30066407 409761818 531638945 532470756 157988135 838855593 665012929 880303191 267079445 739683850 351934831 917188975 580441967 511321722 944234123 106010344 364283354 221400228 676686129 210502411 438322446 212914359 589594864 163642721 731795968 140692141 101026015 916544949 317446330 886253271 57073832 112883242 679071428 442932095 672672256 841506838 399408283 325553971 919590286 156817695 440044405 990200985 425796890 38739816 635437434 443727949 508495484 823968645 704420877 281101266 49714941 578324496 387225689 428780611 298988385 151227209 325096165 447619031 585663278 119287985 360639393 928679636 572789776 4884308 990293272 399231216 541916071 971759842 579835626 895627061 642370525 847014244 262883948 205371811 951568474 850368394 940348795 973241663 672448353 121845623 187212475 726217568 957037198 531289167 127518469 608704773 34963705 753214033 841429788 940459513 776721568 116098775 95894310 31516200 311742966 211024064 832395509 604565918 44199491 799654280 492365224 243790840 23429691 992931 378982362 549845758 729464450 159358050 321812437 60123827 814689669 402830623 916310589 148798691 384321626 589152560 302430349 426968332 38169731 330127964 116518043 7503898 162640125 311850344 582445805 276601880 424519145 416905766 641808985 827175124 363767514 715486493 343026511 907837146 519058864 681908575 747028344 190807939 288924079 455136066 742007612 862369549 816927846 169132981 91151052 209430345 196077077 799573609 514174454 347413828 934915229 342817313 677729761 313896556 408624691 74664063 863863803 644480536 693792344 451906995 522658222 727304907 193512649 474760265 932598070 878698512 972034876 237506539 336456034 583537222 365755890 691964725 597852126 70770064 21710995 131129623 744891221 948039053 611185309 452784102 530997187 147869452 825260413 820450005 28383897 672612962 288509371 336398364 969140042 389829439 352302399 645117544 36575875 88440925 260143970 997899224 145875554 165733164 716107200 980275873 304995515 369403205 749869661 658286475 27085948 159096872 114254248 28243506 235843004 747219323 201864502 812212454 633509321 948681543 670738783 288250240 134871943 580663275 407687198 94974187 311267119 158165659 57082607 597627899 196537717 555498309 356545006 18005116 464378929 799589186 72932392 89116514 795606804 798451506 51680851 986882063 650047115 177730694 544528752 793738420 567734131 708338744 34400149 796724196 271770455 346652827 251805237 861906776 908977980 949378300 146344541 134419709 694175411 262143137 428916701 622921851 718784530 656341042 799172492 559590784 496972708 12877060 351963524 757869600 42398265 28023296 904153014 653193319 417691978 87458865 237119621 53181737 387923761 348616737 741584024 278154349 436935550 625166735 239047656 808704313 19308609 278735216 267902314 77845412 457188109 709068190 477123924 864031131 214455189 219578646 923788116 476509770 716702335 82206179 86994917 620765039 156180274 558813609 161901868 97659385 240259854 544759652 686645036 602352722 962050198 961303094 43653442 400020312 460988330 458519642 675754026 576943071 832618929 49534346 194841112 687097629 271268902 14904406 580089619 611332828 312191583 181846052 862676557 733714099 627491985 235312870 898440741 567572801 194794612 387937226 91208690 888256856 969597748 94876946 708775669 239212029 173662460 888843683 222834652 371355430 536437364 437149369 961330072 425985737 420734439 536837601 558371765 209455210 324910406 738457268 485151191 280362448 445217533 364894650 282630673 658928451 7612982 454109496 540840983 118055731 548355078 825042347 51134529 68625772 570994674 406074122 709819001 368390408 932816398 679102060 469190521 299301266 50161244 365688902 387828703 578874511 214662028 439289169 133372496 677204966 983092884 460081260 136937303 127468156 990246250 559857445 70022504 195248174 467469342 645821847 218882354 16905120 917106252 800244558 475866593 134643063 940681455 967601022 13019188 802845949 890764744 556043980 124136090 440442385 856804396 790955662 878871013 428982205 181068210 336240513 969936885 748641626 164919559 343093294 69072406 288439806 961266002 688804205 546346986 148484769 646054770 496806616 467204203 434587479 409520814 735390109 909026666 802332360 636133946 172255844 193469593 192053322 45679136 699966900 426873616 511470368 96997641 27169702 854995568 338661205 318092878 355694083 848278727 37576648 488145900 311461160 793434187 914870416 379859677 197915922 450531565 284882882 456122387 665712089 337906332 446255657 385098600 617715998 5714477 911916197 956600823 825585813 433988072 338936821 211047226 437091560 892545561 880272934 524749633 433505623 406668925 557484532 796170143 948990397 41067185 463810991 279009572 85065628 325084285 517658004 175315235 722929989 996508657 523372712 136445756 311289141 534560067 885122400 196203781 341689710 570212121 976876127 466228604 281591847 458429066 525249134 634872182 611718669 998896325 412227521 614573846 345088077 31401344 378368110 758837187 123217035 787609426 460824863 642122395 89011139 530828611 56859399 647169916 283669861 528592557 228542359 964254038 188046508 855401804 804268728 65005266 454988315 817600813 358875724 950407166 275971519 742659938 886341063 525798277 762258485 372078851 519905101 905863657 697961125 492543990 588548110 773126555 966047112 919731048 680612142 779165130 348265392 212453966 281842699 841173690 299242809 90804646 752612506 429288709 856982863 655475274 294354616 938078642 949138937 157345444 177609168 454050155 927746735 117858235 421351906 291143835 561112086 497975140 372638618 856686457 641569215 842329900 169274933 51413384 729542661 850382826 974526954 926607692 834334468 307312785 328322489 231497426 685833186 217266801 546843514 845355201 831289877 667108889 288049543 28090616 486208761 570147033 36673202 48677707 536545683 78200721 120139961 231203827 220022085 897809903 592723302 406663022 376488770 92875043 137281351 835894622 193605162 885978302 288625027 162093681 127510358 321199380 345455723 183430166 348720679 109138908 643160364 186771733 165671792 536035628 497088094 793341777 301839650 632946048 84893358 243379537 248588830 402849452 207311946 862508879 361381776 450085986 75191303 858352916 416280787 697862546 94040014 588611019 47759537 212594007 195089247 592717737 750763623 247686161 7817499 975294516 41018443 550494584 152277988 925225767 112738660 383862622 661536921 392064290 600174535 318367258 784729000 52500895 240824715 751328298 843736163 810279786 736084010 94641888 190912252 277179929 618936526 445277893 155966897 988954985 986687032 442377255 519481459 518780721 514477791 537816678 543146190 450327024 179931232 168488245 789325945 272860509 552864146 158958741 94633944 49687829 477416506 233805324 817780432 412261278 325082090 214925794 911795044 920387063 489731024 185785975 809767636 242912405 555800647 521263019 57671255 915684403 345344872 657376482 617195567 213812 129642721 16227282 529143193 90220669 229454101 448757634 473602787 481049148 59450662 658617976 332915119 150486937 689974906 1032296 294826598 226353510 444355187 531470232 625831327 992977094 777335143 439184012 498290008 709020836 731255438 456303548 364563831 15846043 847091557 952378820 716558275 3440788 190785322 411319259 859073108 633768799 149419104 256197588 606828692 77240659 567798045 203240914 902390673 219022830 368824541 216551768 81461230 1069072 514303861 434554852 855209516 983047486 70326000 924830060 118407507 747009630 269745153 550642971 996721835 115092463 178255135 961596485 848221774 241255904 582759657 807658864 58916392 941354333 476146250 395465724 376882791 821461160 165972721 453787800 141531237 8101358 619091783 173612930 161661935 408313753 374526496 103119957 13102794 256691784 846868397 366478024 90041637 679768011 157638149 755783242 342224345 970153224 959904756 21839936 120305299 599641555 899390944 344122794 853577197 180303693 391399398 508727439 423944162 409902841 478172974 935001087 847198788 454825720 109934399 424743207 832404097 201715109 10784911 230350913 137640447 40045528 245933123 337690808 537363459 781269385 848865398 157267118 447703932 531760788 327573680 825386867 35512773 352161729 944770205 941956863 254983470 632548418 269353137 666274921 172820803 756418077 428679835 675572832 399448152 497421505 240435723 268585417 144942881 168766750 113714878 92764406 277125320 931241841 567903295 250573066 917129455 828388219 909098457 718069670 538231377 670854116 219464236 202016709 80557555 47510175 52718754 910936043 781867018 212851230 222101253 447543875 59059291 127356525 100255636 506076286 61919291 770435721 910840775 287148006 618989371 350317677 21687425 246588700 715364085 491068235 102317242 900650785 692388638 182293646 8538998 178607745 5741154 892186279 53499663 836551076 995286563 37672956 176857429 102117023 86293912 430671448 148718091 253219068 188752199 100466404 117006704 561674879 281228696 678172120 988729084 419062115 71768528 265109110 285074335 247685856 601166670 740660576 69109610 98412948 15768077 533817702 108236184 445196821 667163961 146468829 99297071 721680851 456956517 849414203 13532111 411977186 519042637 45602932 76496922 242506946 18207755 970248297 997860596 512565807 307920121 245539808 106148082 60629773 720650785 62785930 523321602 609910935 600694512 496554803 895357863 58665434 153903973 152499452 981432971 6539884 807987121 228605723 432672232 589804354 534844947 370120227 226251435 103903019 409001386 569445577 240157432 143243415 967843243 506685794 474266044 186554669 90460167 927652346 894042109 350791352 275345333 334077535 438719106 336072091 157354013 182960676 732101862 43027773 132462824