100 100 368574921 651558222 978544835 198334633 114930512 444536739 633328418 716735905 895605284 342311511 249048665 197312916 199251017 388404061 783838485 530223690 167962113 837064836 869808907 453494848 643459714 290426429 870191819 331160165 980740579 790644772 668583331 163834426 892395241 855871279 688693917 909306441 51012223 175426522 62463184 610856255 194125965 870028574 587406188 616124743 475442676 374145835 662087427 610440996 308883229 266324404 39539376 343265252 393055492 172466571 244376657 885306739 349443416 544957387 948524634 831136156 938393776 701904329 309058458 167642829 286677659 683286399 182396935 358927275 930151234 531951312 231866170 743444904 419916882 153017442 696333696 811634935 739535731 544977447 992682933 906303802 136252652 5534864 401261382 447682478 565813099 107598597 811999385 864710572 345942780 975346326 903602695 15035029 950835408 403898890 978442424 258145058 130660223 254182663 164310736 466821855 317654828 532686025 419658860 35111613 997602745 550425136 772218078 54019654 648029727 7073175 719468620 844956337 351603496 142293490 641954164 166641557 39267529 129747607 275864455 995228750 983732116 630744435 552108078 375316869 763040805 467910269 620469843 306774489 750194444 671715423 496576299 550167522 998210630 624975146 924570132 445645718 852624796 253739082 72238896 804021311 11611037 197358851 366564638 47362309 547812900 30667840 320444465 617170349 683371981 996256059 204993215 615356802 410701413 102556162 721948023 607715333 367812907 753837959 991405427 324913932 513934098 945909097 801007450 612135563 564094176 831168356 675884345 133477138 642960516 319710069 48108748 752827335 778882937 380502317 232807470 48129959 305512115 687984115 125046976 570851840 483236941 347788861 445294328 689494220 299044666 708599168 992554732 68985159 916401891 127265285 105137489 512393580 739047331 167736208 337020105 551607943 656428796 760182309 874897079 902805248 725384676 644373969 19487680 365740881 887057487 913673722 599620149 828472428 857355412 76097575 947087325 245915044 769368929 503716537 501139026 57916090 149416861 607440710 785655718 567490039 509942995 204261001 918181416 762260691 937042504 387940511 89586972 42437852 683677570 265073443 639964820 455394201 503735072 958291818 237594065 602615157 302109312 434051415 605223695 479584211 932240017 509407350 948068373 903656232 694890078 53396046 2029909 786319171 181140045 542675059 25297376 43419871 110443624 997084235 346566528 534888523 246031169 121394662 714004793 329948880 74972084 960516897 868581859 552759158 147737714 591235859 460999898 587830991 986168455 465170186 31537958 663469314 910017349 950304979 906395055 655240872 596220585 91812976 809387407 709500484 227594322 415747414 467666146 632212884 939661604 597898002 542750529 946067818 989586517 512783608 572691813 671476650 286005362 479020231 529795977 617539645 322703958 206643493 288780368 905739675 641650745 52312936 928205306 518404759 248366472 866553515 374773662 426473580 184060071 947723615 110193353 869027657 386787345 601035231 917434695 608044034 476587928 729086078 450959353 81118713 952327063 735562253 964680264 218266190 515890297 433308733 691123222 628620440 631913481 381019294 368784777 892566768 869288517 768189609 521256067 633512436 655148090 278183370 426722115 383712176 41262439 30820112 336525865 116965849 294752891 492792692 128386139 536699674 140301941 123427954 896087280 444662568 666407293 743785891 438163279 182537059 814235017 246085655 323907809 39361180 298280523 844948913 872767116 644880926 472606401 171846736 106409012 353217142 12069816 369765476 738511628 956755577 662816381 963992205 782516659 155712408 4942966 860418703 284141652 259124746 668472070 42808854 685250797 55030473 492313338 950585083 91846513 156701911 419184848 708712967 562261946 910167025 988704571 996948488 430346955 581453919 656127361 601457718 849045897 999028520 439883184 146632773 154978346 713561397 789998465 330473948 941178173 645632779 681607665 799648545 609515915 317430575 880006634 533556801 924531761 71176833 273571985 820309715 825268525 821599001 215168959 808800186 225448858 157151319 394276479 493603853 236440522 242401599 789164429 350644167 566698267 117209152 968344959 162349846 351346821 290894959 753743309 840969746 881753885 152581496 627402730 315758065 679147060 55067069 413058071 607599052 483082583 510614485 580187430 711950444 215684507 723234664 55920295 716079301 75626653 441077933 943351755 951232777 596363399 339232060 5363274 738510485 119046611 879505223 790722930 579554615 326128069 363421577 718853904 81456035 726107267 982843141 721544654 428909170 22919039 102366145 266424464 504955923 297499353 481945975 108460636 385075730 445494806 857951166 916178411 977769159 92920526 937950763 199990796 192552733 451624558 613840405 405996647 101202129 680935287 61099532 198740701 874194850 397958714 367553459 816211185 90861770 615805186 213618827 468630812 728987130 567724299 161378147 532441164 714497871 562028106 218937182 20872195 294103050 977650316 539884858 62444301 488171703 326470643 690788237 967310819 435990630 555799538 228530349 459588963 796345736 688137283 602474451 81003656 341142828 839665042 47654632 572891873 581693858 932773038 278789044 986654946 50235429 929803280 360230295 997571308 78640752 372680945 333014788 584549118 759177232 931218886 376646240 201529207 610923897 64889973 241142465 449794218 73086325 844022698 512695256 111571538 651090705 110869685 332264280 275894297 746867378 760629177 855923329 781789790 439498908 344030943 260567290 691407625 153057095 233383998 524159980 190538160 282930611 467970625 322199658 485040606 318539974 530504809 652251512 35937207 94146848 414978367 717449385 753125805 281963590 267473247 95921339 75959074 498199601 377168276 709149030 573309928 674509972 853518287 476675433 427261148 663242989 126997647 686140466 513083543 167120995 356108243 806947480 819276146 197027584 511786704 475033273 188663142 538675658 31705736 552961948 152993948 524850917 729726281 683984883 985915688 269568639 724322535 183733554 684102153 307763829 195556045 625552993 290634356 265371568 43511233 759315434 527927311 97415983 287583266 983751711 599693855 129371160 509197918 352611959 425548469 42720886 217466550 968439120 532057557 778082370 753753597 771853932 729415973 162891182 865580115 456057443 89474077 348982143 378975000 550852848 869966241 303034762 468827966 203483909 89777810 803911018 307656775 444073778 308318742 485709590 408557936 944046947 640530140 230606677 120093412 859057304 517813510 330911516 104594472 971130655 188047523 930629829 355201334 309462016 556937403 995966109 503287327 42054384 460057058 47316396 429210063 631296596 342987992 446211374 60761419 658523844 597903027 375404231 499371149 625220875 487206475 356367975 728360298 706647573 653794263 407750097 524072401 62322580 11945510 389664013 952856497 960708839 608279708 170439862 43470405 843147892 182396425 595053701 440154458 912270986 829659754 713070290 84846058 218142203 429025721 192983702 314148139 79223012 650281058 819719723 884702743 887756361 566561932 851721384 657168093 812318388 451630331 88191319 925820727 64358687 627368370 965012256 25704998 31068705 165836561 90797485 825737496 188952386 89421864 600951296 749487988 637187171 80012947 559071867 574008265 414308292 166024273 991838996 996998357 72615436 774699140 205289121 604371001 471511082 798174235 355275793 260500417 483489532 804034047 643334220 131799867 744204896 775177811 192114205 830947162 884451700 218725775 830727324 972935721 124734368 153475955 694584130 701336123 695990287 705275395 175692062 985453220 358769937 137636336 974665387 672617926 323058310 346144942 327414656 253246261 286629371 934873349 911104835 18069169 644104554 893504913 870720021 344741490 550360434 508015830 559905115 409747458 795008681 823315342 595955150 515259710 681258956 103582692 418258374 75315625 626445156 797336818 796921873 342049409 709705798 392144491 570223316 989289772 212226180 177756980 928277829 74831351 38452242 401030239 592138065 858625529 50916018 101825901 24164708 602896792 47563718 97954897 988990184 504977161 436414433 174719734 553447344 86535678 919143350 453783415 409682248 542307387 509092310 822860745 898459925 576383671 374320499 586346936 475076945 317778443 415376870 297468062 420706199 298827194 499357494 47155553 683870771 283012027 451805722 792011540 641297928 793163200 99163581 744352790 33220680 642308572 60999619 878155043 813936954 865458688 45851883 382326853 473366132 665268909 308064988 885335895 907249757 739849415 506551160 925164449 969141908 977314890 223031964 507856106 643204638 596562144 40712526 457980794 767606571 435503084 861859771 89829335 261730364 367338962 523226936 447339629 568643632 596560652 249597385 126214120 335206152 981367977 606220513 361558460 370476814 255455866 453794734 409826539 404008393 479700848 228726445 342906624 290767306 769016793 996069859 953194237 808729389 222912444 27382924 45385617 308111389 566004549 700716609 639767715 165298454 855745070 113959423 904624004 644414237 11166475 743734207 179824609 164392385 326164245 981758328 311454362 906020209 493183771 501565279 140008081 549398001 846878171 125144391 520777995 436193954 981942338 480920589 622265765 461709316 407669151 532289981 331510759 786957610 865407506 307778960 878188828 174510181 243553239 700577358 490352124 316829942 432094787 43441889 866015623 949820222 228244978 935231710 150965005 340533828 449165865 238771474 453125803 128380463 297651250 870900163 811845661 442410291 820545060 445434461 693084579 893700020 952720316 129751378 90133745 364420389 945231206 273762950 152895882 467870505 723938543 883680632 445344186 907553700 525730081 396254346 381545012 696252256 357699374 739394979 602210687 872685439 596518817 27507432 713776727 185874730 716625992 641609555 29733336 874229763 541851863 225033592 665817262 813968941 779170832 8298570 888672311 25482910 326005825 531031343 393805299 287665037 98852891 522766722 444547940 685432009 915821722 936674215 295227827 335823744 238062904 905432473 165145057 830763725 580576790 826868799 523416460 980716513 446876226 734891166 267473621 73386347 977427787 73979191 160864017 308506539 276977353 857004021 314031675 767175734 418807832 509572776 180263157 4661219 153672421 171098982 242285087 22788818 524635776 689235005 764653149 434316263 277622689 37306430 788432304 717254498 67222024 683245367 234227131 466622131 421933245 164018669 343525185 745182935 277069907 742821800 371228670 8901982 825103914 846652292 183886380 284437669 437693148 891763406 646172384 332480797 413994532 922150108 903575291 153686826 99578930 587769851 410012118 825902373 955439776 495959029 466001111 680320351 834370097 314551901 68447183 103942834 732345508 98785362 278293509 27207996 79916193 894273024 632237259 645957833 804717601 485413885 131459374 251550653 65994886 664295642 929759079 652774173 401662451 258625988 209435297 14551459 962330567 418062014 936465327 474371063 270710262 297508623 191582848 112457309 125553145 40425494 409120816 846817482 773485654 234746313 347173359 21000765 249050876 133979956 780889561 442168917 382289101 982997584 62728551 868044511 443852719 886356098 860132526 774937734 988034924 142498809 577549237 846793022 396231309 244354884 560674507 167845179 383368917 419103521 287639418 906709452 735314516 359956886 208853326 721997377 115897567 229402006 821184615 717508174 53428260 785652958 85631093 776247424 436938616 620007628 999801444 940335141 107039503 370039092 379450565 953723555 98890607 72278023 441184130 956708145 341347487 80026000 628210475 677207662 956038800 662041577 197189336 647951503 679784892 632752967 948619093 442103723 798316543 767987440 865541572 703582825 420028705 712551202 972904897 726201732 232600828 736057799 180873388 98187829 938050120 704135997 337573667 618417921 517072521 140100121 725540983 750925213 995225929 760311865 165085459 913162749 777287809 362717995 253697063 301854026 373013472 663814032 549770384 180703066 99529891 994184782 901724545 979658145 472704981 716437176 472282770 155127824 470477384 181652969 86397048 916661890 173956673 447543674 278577369 109896349 587710368 362443862 996111504 783241569 367684055 767788466 848249794 885545651 13798576 885091344 773082530 501971043 461489758 689279292 666162855 119389775 441612012 865718053 365396095 355443598 898853674 12275080 599647692 228920137 107150724 235511419 56821582 173646999 118497170 580971068 188518599 761795201 203412154 795604608 957575360 871531367 130214898 171290647 714164687 265269688 895152280 902939063 432611716 484174525 759690776 371190717 812492673 843237923 452633876 65204362 764432016 837760684 14786711 838579122 160984707 251197220 630478664 392448741 296325147 81447310 286783039 423177763 392385090 542949749 343667804 166217950 283141791 245296341 430214461 348775276 464499940 585930465 642676854 364133 581420839 959889039 162273524 788980575 785625833 915898821 971886405 176994190 305071611 712823663 882252625 838213488 639207569 141401510 376100810 752194512 859131324 604429111 866165051 431784474 483918917 253366773 784960035 306851649 579861374 274212349 156515587 856829295 572797082 310534955 395537293 331304421 640488667 195603928 837758651 370348666 693095133 488699300 311295699 88949240 43674978 484668497 354675748 617293113 182386590 347458515 745529948 513676637 9071131 740854433 571567382 289848536 67438961 657414421 217472254 523077461 388897645 754483829 471184854 194817029 34294283 915609448 60333083 78432380 736611441 846495612 287606098 693981031 533708807 548760606 493520683 446343638 474232759 260853397 739012969 35249445 560210520 24545210 508056128 965564693 150061191 497005663 186882468 860998190 919477058 397727980 238476663 947871064 208672874 573991011 185769162 462125866 508397686 39727053 797929191 152157111 737817194 593651257 134042591 256515222 117796408 20937300 722414961 680263306 574243562 158209546 45331566 523011223 772226385 478876537 527340624 132461318 313395501 543131178 187692206 689879080 861865027 759244214 784610412 799217927 525667299 32937325 303907644 287757177 152898423 817846669 80939627 80755082 739847301 296806185 241828935 817465872 378478145 198716530 100957557 723983738 928669171 344601732 729575448 111314942 881936696 456325069 41657856 369745247 79126246 992635019 269995176 314063507 8185874 13104071 177632293 742285219 300669582 545082364 198466645 164363075 628174407 875821866 385249391 491693915 230103867 86038613 516809355 79222096 272248314 223552039 589248729 102107216 482408667 232610502 90507309 478393014 402745781 555543115 132842325 2509742 305973284 978216320 549688126 518676993 600531300 443775650 726437832 224258346 655997247 649323323 449303979 783275488 758929769 535883638 28204612 251708514 947423276 396407764 239757133 249641768 694465104 399381906 297462390 13803099 690299251 655822753 468020567 538509041 252122980 344277711 913304826 928261544 233650579 664980942 82151441 10653876 52220145 895390663 316333797 237079911 140267836 987932563 258275305 581839076 991959169 316788437 482589610 221975014 639381712 832769191 926552338 793650886 26343522 82493128 447605419 141552051 809558316 370859267 883267395 771588568 847102953 485204890 368530384 474110706 218594483 526049518 776460296 949898 261731612 409399341 182785006 128316471 80900051 865960834 506496818 465933768 923311483 374990410 295005821 400455161 766224195 593412420 91663428 892868321 169913013 499425267 308490122 640513635 278069147 821762090 540183971 92669070 65294836 230536281 824571936 923333666 466608232 124394611 580594826 304085702 344201283 183292459 109119520 73355011 220855152 781164392 212809771 5619229 279044628 713482583 932345236 319993248 245464815 92704677 420412394 752478926 546335673 423156178 108700565 590809276 200347945 436271020 528095527 8951040 72794025 697213829 65648089 629655158 394809243 6023620 491085838 787249625 152950428 125683162 799553311 756162850 639795556 235323461 839341173 333906703 385257655 196054769 825926321 196776569 31692902 928963078 26044882 281967973 84507616 388194903 464884981 721103427 552409545 210181355 908090701 942249042 841157633 951849239 449760858 748216775 578620006 316866556 357071595 241777198 532307699 203985677 79284521 668582231 517354395 726836364 291802820 437591088 242295786 785299758 332816590 318817118 366689465 946190336 635944272 918296147 828625100 928408907 185275357 231489305 216981468 970732527 601117116 752653076 724506937 199562852 450523488 16043661 696890908 606956615 450756656 195781907 893348649 635522354 732196401 411366406 475085865 874214020 369861913 267809703 400630991 115580600 799020458 802221593 305275656 764919672 143693992 312608123 37358178 613908860 222485739 404180464 856375660 614144128 987385960 114729912 173609301 734187711 677102196 285928025 170386943 818732983 320941721 494750767 656937538 660887559 391106055 739668140 642599021 774576535 242959939 926952560 846157604 685692996 535192453 504236706 448698663 908419765 948335555 333934095 351626138 953231701 846894749 138237362 67563734 539080867 499124064 885020008 883370668 568666566 985058116 208467663 782107343 591136675 157784783 449634936 641247934 500131726 370363754 926578676 265107167 261050739 16463687 112597307 752050817 17401462 565541761 608744128 25259477 999926237 516386044 538426285 694416123 93452302 673691474 81900251 593377595 328771932 101479389 246504568 214822990 484935207 896711071 324570514 37925304 391505017 809689493 356639841 320644401 83575892 333370514 47317780 536115675 196569526 574183851 842576261 404175745 377112715 592358197 37184094 993105102 699585977 356084310 41462680 540864986 770271412 428867692 788379777 709394755 97262875 281998430 696220269 791772296 429566751 779571198 559090164 880628704 138152457 461763570 880196613 91262673 791307168 704799676 644403903 996952206 236616687 855052824 396431850 187714373 947194390 389389091 270137439 932719998 794900188 332766322 537351057 395537383 93745002 844017486 914709476 150441743 947522710 306309395 583379756 94570227 788599097 351477513 469856711 9799242 449397414 491933595 86800460 977535457 290013956 951673208 311222173 469060012 224116176 710022906 201457278 414279637 878013655 726215858 896365099 109338245 593147003 207413076 743314922 159975325 177140161 452867731 430219141 839551809 557178634 23764205 730602411 797361167 831832681 150929142 111941754 860736667 867287587 804321567 586892519 997777976 52571231 655940164 65215176 189311609 27057156 359060974 568177086 378580944 395530134 523669469 902068611 501852536 986111925 832710392 930805389 422818486 13697022 898741320 159158637 740657127 900167370 332683720 980661574 504967236 362479597 956549872 209851361 766706984 422865986 400783575 824242316 409363061 878417476 733198791 105348133 273804772 204469738 139161222 419429284 446994801 304396335 179976325 209706968 283653228 162886473 523658942 206329876 780885864 273815696 285865881 26128101 354338208 870209360 506133717 891918934 889826834 932035129 590585784 117854131 703506242 135181903 732748621 661847456 198307345 295733642 201849964 469098098 61088395 943691579 767653980 34998477 862624831 751720099 340174764 710911895 313341624 367179855 212527265 970139274 201419247 975117441 848314628 206622515 557290951 921414793 236082546 107462989 797132730 727144368 907415468 623351291 312488342 826239109 769341110 312918458 912081024 80460515 821177805 256622914 80281415 993722489 259090645 124165950 914285034 659213843 120476637 337363009 913062912 188555113 515673903 655128145 891458505 437020780 186653875 783028258 895958760 422869010 9660457 670220037 113945202 302070361 733207045 841827962 945237935 731658104 216965475 532325316 758705252 851604347 161329133 702085649 358655533 212513748 307366956 436147631 872928768 489902388 778357168 75804861 399876298 600098688 87366416 722858126 983682608 417822551 917679180 431811159 370051234 332364949 632442349 273476842 125679261 122176539 502713589 885300693 330491314 385818271 675177116 20825258 347720915 495859973 43078904 295229442 309093185 74827281 109634197 687199722 976782425 667597320 797517715 910959114 956874364 64127893 469982044 317889913 465230994 822691212 263045610 932705835 175266126 895758991 171579126 123146235 415910417 531422518 728737332 244178032 676417998 939091642 833138356 801418064 821500848 126898337 191690339 922571590 969698719 594048304 600164639 333101880 802822724 735658315 333791351 913321381 302360656 19521058 78272095 660543393 455175799 357092480 840363840 93899679 681402307 648100105 978822424 832799566 956675010 864353513 416134039 360563793 427518384 392215280 719292161 52372017 155322820 446219210 869297717 206805487 949916620 399287510 664813194 41644059 111244723 311060452 270037698 784249319 371724283 49250486 845568516 504621023 366527672 748757615 644364464 457142689 901770720 971225931 692384896 808351627 152132906 829014493 680827845 662330758 358390758 503661673 268272004 968636597 884724514 124609748 4722333 76016734 694567276 366018644 660599748 150362034 659317395 608629624 453654283 114440572 906830049 94442286 395923913 804745698 6077909 390535423 486057022 138597125 713466654 525198039 658799332 522821196 503392547 979561105 860712077 18594904 851217452 675451249 814303468 267985119 447347811 344989801 634132809 979975317 807985645 308902316 70054103 332610105 93962697 964611999 466533503 620263576 28587868 894946448 442646700 977673802 220839106 71876827 695268990 15838808 561167045 887210248 677390377 54793839 384334377 454754436 276457910 939360692 271783269 772888258 412716240 377577304 372993648 614102180 745197449 457927181 192500934 851144882 351999404 624748208 21307887 139570941 621442298 586735049 950350595 309752139 778227716 166395178 954119762 169812229 572556246 955021599 2282781 701170712 113511980 700629742 282436078 586926531 97926656 213036292 414729098 184329489 466928642 697933386 209951800 222059392 476634042 290430155 331816599 390729238 979355771 168042836 983439727 229652318 814562718 41026662 575122357 124684682 879591145 924927797 836791363 200207615 907005469 343743026 43108004 827896644 721331301 187068106 191696066 876124531 856292530 42204929 644563796 529634453 306841208 194951206 157361512 370653367 599399683 72325989 27885055 160153970 791547228 69859152 321594265 364613868 772806877 390209548 84283909 511608557 996407094 419260557 713309695 924368140 799410005 591394396 874895192 678391969 458952171 332411156 314000958 306643591 563646668 374070143 128588021 381302805 864376644 61741727 50947893 562410964 20918803 578266754 607467804 801658932 542279818 796142488 992500401 675385985 834663448 671892735 537018374 716470412 888817482 118779744 51254304 405354041 539008941 464890775 402332442 765736156 44411041 174145507 141254046 667177666 16543188 409394330 523443472 377644578 43114304 702148294 440882650 218466205 629330986 916775614 955056306 527726315 53134286 194377941 456816121 561944451 844172596 357020955 989786009 619709158 79254340 609679006 86898513 589393728 942214213 397967933 984314606 150106451 191739360 703512009 72546559 546928164 245347301 962389016 447498698 907585127 731456686 395049233 698656603 291177591 667027474 289730689 942400043 674935760 36388851 700831166 604796325 949356781 156602883 532783601 808645256 622902277 858150443 395835402 628032926 457780755 96537362 436912153 148831684 625714693 483787742 350485679 923127053 866521468 190635682 286712451 896612663 935348524 986271332 423182755 18199777 423206705 137500931 634676239 251945940 759346916 200276817 39142817 702633530 262993628 564409952 909607454 174933420 171824774 483510139 887851889 472675168 916386444 48373135 670465511 729397118 808902134 126260520 165186109 154819948 166870242 436917236 695845820 638113456 305184914 753411465 425632541 997197385 289015209 487795843 654618576 985445232 58163035 589636974 687326541 675065749 862762837 355095099 992576646 325902567 738264650 618453862 221167766 847429399 772318925 891727107 770775314 597753692 507051448 355724051 301750948 300254503 925957606 54612090 517986285 954630360 149798582 512964339 738162948 501108042 843992996 558866455 808121050 174817407 809083504 174635156 433018377 59640392 584308457 443096421 383354236 277819495 490144979 944498460 92018599 105357465 218984032 89936652 344598361 55456481 690180861 910692567 724655260 175062811 177209207 260318460 109334303 273746793 660304790 993909543 257155426 45901236 807568918 560411892 515232081 21547913 320784327 733496741 807370975 454435586 104017906 331883178 917313035 159213579 732684052 471087111 531051098 42892207 3120891 889507786 56601972 733548242 522656660 758715804 747930435 588775693 996022790 915301814 878162203 970356484 138671071 694786555 265060395 782054357 378282542 991620152 684836549 50411464 979737645 843038596 236328499 350471282 666411370 886021839 175499987 695193246 88107131 259099022 240023128 306044972 471874846 655114718 879320840 636928758 478487836 34201636 9573238 605679488 19088287 670263034 692045124 149579690 346548474 901682971 156903916 242690699 420188271 785149691 489799965 14401677 87201376 400817353 64739553 197868290 678919493 221017893 375109885 383186335 54909851 13770860 412844425 467121601 236280916 703104277 185646751 662122903 553498995 883582389 842306307 99475065 720044935 517458640 445675560 454328642 35717829 842523383 252786054 778144829 150227553 660017116 595659096 810258362 615909601 929854409 646364127 384300884 921439623 11696883 934781428 838517446 803418497 333036100 168935250 885419613 454062939 710396401 292725896 523391054 136624805 505821853 226164157 989705210 523821925 204750034 807609968 377284269 859518769 469949362 744594674 456407288 207209092 829174960 446705332 800099249 587000045 918944006 31285757 213830931 996519815 634068245 222503912 522983933 380764414 549848173 565226907 436114342 63970213 604346447 152145686 629087444 617370987 406476908 196299094 528263696 56748313 347069132 487909831 217340904 909898236 737509939 160330543 756635880 11266967 486574594 238471932 805623236 52848975 296185992 88509559 554795298 218998104 636687665 395948976 13481526 101642546 179227035 631215671 838678329 694849521 693977878 161063347 894287475 773531649 367664188 831483348 861053057 291928629 223242958 490747920 554466661 404898682 736504989 440022565 938523957 183356763 883058246 362710249 989050338 181525295 904526277 15157927 605095101 631927559 430974550 921220983 34672858 187085300 326681430 853463033 256513590 151974098 379910780 723808359 325550104 222373414 972061343 565732432 123382112 367702427 720373620 786523526 421478410 600292854 481150282 680539272 108093679 840360280 480323207 354173077 368089112 214213025 851461564 859645555 64728214 348366064 133081526 381002651 346749427 235244306 663265220 451053440 452138279 790314961 74461131 152850459 329592772 445133214 488701685 640444813 384897450 883012676 778964145 729309639 182665239 355501263 938583330 9997944 455936108 630875360 305278377 942889046 395633981 884183439 564213604 391657374 35312188 634932584 910054397 172902226 27326142 89048815 878296240 326837136 271082951 845448146 45131630 406845920 596332980 104597479 834081779 637242131 934764707 402727811 835617189 160742748 61866688 572966564 294917829 787524951 807327878 925071309 800812152 218606648 241795332 5281171 709622040 268103099 910990399 784234921 273133571 446635769 134241030 624817995 87690400 531704400 660799788 257454761 616840769 493890119 544590228 741104457 500296124 445224008 797450581 337221637 216724783 166942320 121740066 392061986 740287648 119077289 639690536 432874597 721608713 336970871 464770251 779251628 536971380 933196816 85857484 946799251 235330034 239929321 682123576 124618593 11002657 38279081 910953602 369992434 837341401 677040496 717216466 767865123 542367710 233856941 299208753 367307429 950704266 581280501 262751217 548693141 385965005 777329239 630384670 64703537 361449149 143736266 530085937 909645625 852516539 73714252 521086936 551435585 405768109 343015729 575670591 729132069 305184320 229914235 986015513 351890491 92990235 801823408 533759075 317390778 853571564 995215008 291689310 911890503 718082456 174273170 990192778 616242704 116237001 183268170 390800097 835199214 294855507 856803277 450575746 267667890 52550537 539081456 471395428 466477585 685763892 307046970 472663691 124363406 356706661 590681771 575719531 641591942 11373776 493710080 389968722 483568216 918235581 268113956 46134058 239065991 515993656 630963104 508973919 415570745 158938574 919834982 97930366 306915997 415903074 269203715 548974342 204990197 477644298 326107057 60324782 16949427 804766748 306939705 935207409 413807867 873249405 765185386 514567183 633756550 916005817 533804122 725980441 54061358 445200060 129564716 999584577 72476577 77064002 640236275 529819884 21706681 135015686 661363084 107027679 850782932 203752339 166550543 568497518 742852000 95684539 841043785 109298663 859663527 850554844 536647459 419342779 981167441 496767303 334384485 247496186 422911488 381198861 447463029 968624780 364424403 898734257 685749491 766836386 416413777 15188351 384433471 547483906 153699393 808937594 581309078 988427764 766556030 759892248 333404820 753127172 895167527 44326187 453811370 937367117 487560191 197440083 986977913 375000620 116820468 852447995 546926044 697723496 814602656 764641782 514882934 587586056 299473359 239827155 571085515 939543850 990603466 210078065 369912456 44892552 203695755 12914012 332139397 158674358 457293745 728495164 89460837 53832005 168506918 60588429 556491975 189623429 983033320 696330403 332658090 890970506 551817167 966279401 263916128 725632748 67953124 921954973 51426126 550074337 716624076 556477171 436145880 791867930 926982723 303406062 301476841 429202183 341551138 576395335 465521633 62021582 812930355 483684891 173134384 306012244 970308766 84698492 771040314 249418860 101491190 990494374 190066029 729139412 116401359 691466334 371652715 407598438 981163740 774370954 328008913 837496503 789652613 86976169 881100116 352134749 733349779 894189195 743032203 423620930 283559628 509848832 727221839 168034465 340699575 89008317 930051244 951539744 20779757 210117930 346228632 135164303 970233925 789195041 801228206 87407507 890534094 152910265 304564051 856027737 312107909 887951153 351366399 653775985 957483809 669676866 602447845 161420300 405317622 13316104 932520501 644774487 970534994 872888704 130754052 102777563 732479865 107513407 881568902 141282916 540427212 768287512 127778441 805863561 658528513 994613367 640940830 658385955 450953006 660489875 107124703 911617104 847940617 362509180 688729702 778712284 178543865 319260662 212585102 401144106 869571831 867191599 909554245 162947973 949610429 993532505 647509616 491563776 334768123 612399669 520150422 656060087 265335853 379757927 387953310 850334451 447536199 591487311 302888854 925184857 26793111 945532421 171712856 700951528 83464942 720105877 379579197 437393539 840171742 241152950 689593892 674491217 626083240 399413793 313682670 673503289 591594143 440393812 457544194 278552908 386775647 612995059 139399825 91533080 731455243 739237665 593482574 862940874 776953143 207237331 866152211 248861596 951975431 423370787 337191195 364269333 523640602 913724610 795209166 351119573 159516783 984360522 13138178 663047199 87918818 380745270 494580461 62883256 839452618 330920273 104922402 77060844 429383837 192324139 83131152 113245773 104882043 696551286 957240030 356057734 163636423 909049978 991223346 312708849 810197371 355910941 80445772 259414454 728915456 958977407 529063123 145622389 106227076 203172244 752488821 589012210 619373964 913792158 821209163 360816658 351363462 896719757 940419488 939142504 819093452 775121234 618725456 539348012 636267873 812670140 313264814 914733453 959311420 965913978 240533783 147215432 155222571 686676522 648558132 251346226 851600457 572002991 194632410 89678906 427872954 127246551 581701367 125552952 251461195 346950320 109577931 450782889 821767324 754674508 985000147 905320293 979529407 632626731 535992076 315378709 721839553 442916742 924479738 346617533 664331643 591877852 755338512 628132036 963877430 793858173 306321974 206337898 229890326 176641778 517560244 521225107 60692202 84274624 275118305 290658390 355972141 980033442 905314468 806267212 197340574 213049279 681553825 115031667 490598836 656520366 858350615 206743680 287390342 290173518 354871397 574162756 815767966 514209962 786905797 22450371 324087971 667638815 572701082 958643863 675414789 583541854 969707461 256369761 783538229 449264023 236095214 322155104 202868342 291976544 434307248 737854692 539775934 749644141 899794090 173332275 997572059 698139560 358516832 786216998 346408153 277951182 228172199 984658733 97286863 697169724 477863049 585067689 339928989 842913053 349573115 726695390 287564334 595136107 868355057 670418502 68696200 594412994 321565893 862890537 428721147 89902142 126478891 86406698 162061378 291354476 420520641 485937087 739422539 866935536 42880845 625417158 770508755 485814432 16653800 134942949 118453498 544549720 105080757 143401647 478186415 373429504 841542171 416267507 977569242 180018343 963546114 926225632 39543526 356296853 432176904 400868651 363711059 743462484 967295765 559292991 18406439 265735093 152947008 467197245 1542617 262034891 199338423 404371704 299796116 74729428 400829666 918576364 626270849 928849298 455519314 206524090 913979169 941034228 655604963 510989213 625585742 22810170 772847062 196932755 290241769 615982407 302648365 508559122 485188135 424857771 890252793 283405351 50363134 910167000 840533148 324017720 115799841 119858342 724643066 629020819 136698633 563452393 284989601 819777837 5797566 936772928 337289634 946263444 296875201 684237849 849547724 102114369 528606851 37906429 937603483 369692420 116257636 820956277 457867155 737360128 419033174 362756386 388551123 895555154 906635641 61334872 65585251 218058354 815267448 514042054 38907673 169348905 210202099 476320489 64468625 834611600 853473851 143710841 562172284 830934571 700130170 858040134 7839292 669863666 311054985 68686019 695457871 84250597 622061637 363439047 503440441 420005644 769577645 161668796 871381940 610076284 871522331 338343678 423822655 681134075 740837502 313389575 138023928 510508424 301880757 111314344 527854847 907011580 162054647 272541976 8164834 804836405 524806959 56970288 377780816 850287271 970499587 39258096 717103860 872793845 506095532 177912098 445443081 508068944 397832158 56175502 778739322 150467277 762021380 298785326 944386175 193998469 355896256 451782200 331309739 807927457 235577801 138036541 985063651 619932954 694719337 430379463 217609345 61105991 25516936 839421994 517312966 724142964 817026150 644171356 522500844 179386579 485291355 122792763 697680428 906323472 839910244 903451823 739023873 214735330 511330042 340872816 273646320 257950393 978385224 656630384 364145650 276069218 673069370 336957857 454764081 464669254 96745816 349911252 206378809 735936118 274898730 322035733 958924295 661429297 534511185 827151039 769505430 878989602 683857040 711913260 357460087 135130519 901512180 242401595 590585993 678916955 673544896 492608950 375278029 617068386 693279068 155517942 86189958 169813020 662632032 590263430 334425624 144923518 125059120 587938586 823480888 302742035 9269879 866286574 7118348 451075615 733370162 840747813 855793293 982594697 762606533 96750580 982038195 118831132 434282179 290730967 373402388 42133338 965749634 251516014 289832854 861134746 743619240 799635428 318457307 194322401 792100689 191452295 41522442 333558833 369072789 654331276 624557838 700803086 164131333 986679220 505370097 439619093 484876059 926801996 279493458 109362721 164115052 18766138 779949522 820932482 804640408 625996235 993761267 64871088 448336641 392211111 925533250 806064593 543565915 309268238 595965680 965379270 339090809 684041587 635102194 724152696 226201282 987447482 845703521 763732329 876368886 680971360 476059110 641711288 288983525 855670529 732944904 657354425 144168067 5778530 306859247 682922173 454714532 476803145 58053538 600060237 126841486 493235972 791574655 22578667 246851125 884186835 697959831 914812254 581702574 464662461 32724425 882433840 637392714 900579912 457767210 807441821 100918336 985068104 344409036 159238394 507004860 438045155 9699776 406887328 369575329 914770095 702234189 177031603 394325928 770716463 473492209 165634270 105145055 748973562 829914405 727297646 981977465 581918198 568791638 253476839 784427329 779448055 801290719 870875169 494339661 29715733 98394259 799326836 48461390 414510333 394321918 509282064 703937058 31733719 82006480 93520141 175687216 300704171 188322411 562581667 143969110 867578099 814004383 865197496 864532219 957991155 325505977 7161282 187455977 412722138 226995059 989261803 806426722 537717998 270080801 308507272 747285024 817205202 554810429 488717635 877526976 453995180 807190 693724757 894281807 104368951 50449929 385147531 918797241 592365073 108316116 696071164 294923594 34686248 227568505 85365659 175167921 247217198 698587056 480218283 518092779 524787414 864201557 393426345 801073991 53093496 238765087 522114882 151507369 58078192 937137701 332084863 413989419 627962935 457697535 312453279 973160049 81468977 963847192 535628097 119435631 149378090 62648403 916673325 583143562 305554888 737333753 419413386 373918390 606693763 274443970 588913077 670931717 996676104 166357892 10602221 528689997 399426487 901984938 140283911 545419067 936973999 582678369 966449684 718721051 332917672 470372912 617957449 453761277 135441901 105608145 882720413 900128335 429993940 4588021 520212126 730049542 144482264 983289635 857316372 724612416 544005358 976167436 737372017 69005077 432685275 531146154 535764925 899858528 86923246 282303619 556842249 206908091 378111030 286558006 902387789 549224694 620505593 546342608 274064272 323512361 148787593 103519557 687628833 696480914 762752193 984739743 297843288 483608380 680678770 177940772 988401976 646892942 468000317 88274804 229610908 731995571 303440561 395965301 54044766 715873195 885418687 36887950 338540032 408452524 784955589 303617064 803777112 912583804 830706310 672955754 252970315 408589583 32693679 423973833 908447981 648250801 358561760 270343284 804545430 1732802 995486372 67391129 87650335 353283026 800320117 102613309 441727152 47199735 113044509 452778000 744001468 807502005 868703318 598592538 35405615 470801805 885870898 201264943 406094173 925955395 328290718 828016487 21793442 564625411 238538379 156057033 546588948 982309567 22509831 319704992 540894669 121621013 392395399 991819575 173209265 668646698 312666724 34911883 679134632 159666736 130440530 73573804 43398978 604974102 490498294 735291480 410587949 868117533 277791742 537941358 654447897 729825822 125643302 55196722 56386986 773087967 884144815 472633766 109040424 604503400 120848626 535412431 46246358 558757493 957125145 916378032 541433479 407281958 323656933 854557777 258862287 93624856 651927745 258011438 536465540 313137086 342977680 682099039 114781275 623399062 164489859 524567568 491171788 533031002 646792568 299538390 928784729 927624283 429239487 126729518 51353633 553345956 181116777 504222668 365064122 891098865 237274467 429028635 295896869 803809194 507443402 311182760 803682664 491788768 1112499 356447135 643212637 452100200 499387739 210707186 113308014 921982327 237633404 31792478 702066806 615698825 894463733 724177679 901894273 842450804 356478494 950157246 598222516 346011742 402790012 997119021 431450381 304002975 176068851 727454542 547437377 377834 258719081 96885321 720343186 872529848 970608321 922888917 281107452 825565598 527814846 735950628 717241371 82136241 721921854 466216439 653230854 848310969 264811283 95137574 555953291 25859694 714659047 448323688 499569794 926153638 907771417 474103477 749765455 820192790 930890406 301197197 565988327 458257300 74456051 687436982 886237568 271727534 864706086 112448886 207125290 951533775 227994506 603127580 553295595 987408548 52031680 510646906 118573300 629344318 343937107 857235265 527520322 952250933 947557311 653248457 598952252 27393517 88940557 100752856 595958373 926046713 601035134 344759202 898720627 490150430 257204108 192539287 529524165 315576808 295514479 717131561 178132487 451940611 721509547 667492835 735618661 181906378 827862118 124518447 232285846 723124959 520225384 177761908 450568791 272902707 854269800 929734974 611782552 408437726 344044592 833897735 944998946 104948454 535464716 30002056 832984708 588464380 142937288 506366582 343534534 741683227 734048894 502779079 563796893 609050692 972714261 764561048 71323278 69949513 10224158 323827415 955564861 493302596 322381197 930895339 88521616 905802251 118703410 948600708 856357249 584854219 441652174 517494850 298171550 960474333 350601538 539626430 853021463 442344584 435478790 102615629 454391210 609738336 33336524 477475380 283720193 999141269 289039636 453558958 649835198 869852649 923908285 339626809 732305784 750742137 763374750 230395472 421198912 106431288 242670292 893522917 268001351 401508390 296922215 699674327 762268525 8465042 413172203 128451031 560174629 899003923 892311135 65244650 285815040 12655354 959225894 872231520 964166013 452635890 431882900 320948433 95432700 499368718 504623444 782792986 433392343 983286150 436205244 224491861 95060837 860694133 780605811 675142390 753055063 197913401 378667050 387154224 45752740 497353256 470740020 765592586 8838136 611753029 216869174 413140955 728623647 113885900 514554885 148730815 919619600 497418524 184911536 49372796 504568103 953577314 860214081 716973689 938093308 555939158 67862623 766222346 832232153 729668721 625533401 921203718 312218081 852321150 33794647 858235856 584109235 203951784 77778029 518337192 656885030 193408035 882525685 843894061 995805129 541683541 105932098 295486911 310029830 88911190 857087657 715964308 869062340 360160661 292952132 183604239 786822342 453771401 629360857 634258618 389628645 662889521 282202159 66453069 219815693 573344001 588936678 968168937 231884279 532810145 543945187 633525397 36012777 423567884 969177041 922368192 2177072 215661497 91355642 410549996 947578575 30189931 853783130 938621466 537453612 924277591 630608515 266068769 918961145 813259711 829109067 447323899 613129890 315171332 107318911 763897549 927165624 128316453 119399336 920867446 162843101 213940456 343155023 258426503 8413187 634177627 651346117 332787228 156292827 188200176 616179770 206360001 544608318 364330098 253140191 696316025 127822247 945576936 812638932 668497666 381617750 678626069 237715272 24937990 656101151 885375126 560916469 128887955 397933911 652100213 870234777 60660955 715546586 828733319 297055259 64140644 166149865 564144692 580731903 915833270 424734715 251908645 915319536 622981936 756184997 661600888 990947401 500326901 574106230 955379813 148279734 121310985 672225709 168453702 383779708 693259844 579169539 327537278 579854320 671721876 149636760 625134462 773948095 574781078 852535125 445356450 965896180 718605123 279127952 388727840 613397290 889476080 426304710 106943211 919631087 969378149 825510270 137715410 553138061 208005172 602928779 10714232 206468392 83229827 435120488 359908717 470396552 750535204 164415472 793039016 133672390 350051300 469309456 439136984 963090787 445790771 352463797 174216235 986207287 430678036 622928024 74657621 540411383 615670835 843317670 526343157 559064279 143684631 26441201 180797429 600888897 183255602 146357766 102937333 131250701 950089337 646772099 918881955 160779997 695424892 162746098 363763257 563563853 632689858 237732100 546492035 62526541 993143932 909632907 666372259 548445856 18389952 305129379 451118545 23949277 386855513 830450074 118030922 879122885 873081393 627759006 396679738 368114083 70352137 542119493 384929566 137860585 430806550 522686903 922856953 114368142 276888906 3366934 932629896 573464701 216045028 459525249 547987991 220067620 566902756 902428778 518493338 477740409 72845923 684033993 136361294 30574282 283159709 299175433 585182503 80364342 891246081 299417636 772374753 577179989 717233524 506680521 123838831 930940792 216003584 911092167 996493609 188400856 241969375 418210914 976319261 895797567 421306850 916633925 367567094 532824334 476689975 959389743 841044999 460646099 491082607 959247555 653142699 888510182 980804365 280316310 543888534 66011355 524542547 188956408 257211508 398997310 127313119 385880968 274235156 673470421 635479411 401371956 754857792 315654998 594528689 146243620 787734453 904459383 642953405 364819522 829698447 178063981 256513654 541913902 915395952 226813459 929322039 958003550 241973553 104799314 823062922 501404310 989866905 572320618 118098248 266494781 143694674 720145066 833104474 930887573 965808951 258926867 799859272 583947181 485974409 594386014 109041122 611281731 914927905 696837252 33674823 8200754 200877301 177807030 404941500 478359110 333713879 277102809 220794657 731511046 304501865 131285184 762484229 498646376 914420557 620182040 40491156 197703687 813802928 807890805 516227738 938626241 478412784 762059301 609452465 466253561 448132144 636996877 452229714 818227006 745887993 212612104 375462524 749354044 383244651 367974032 806179211 308810711 994079842 592511256 797666599 834249771 373988033 257148657 685150728 320209694 815356731 861065112 392489698 70726255 510162054 352409386 147030137 979731902 434497683 321792772 785937319 243447365 281168888 953246970 433073144 242959173 350943382 305905345 530076771 666958952 405235244 127691837 936836032 482446366 747807248 142365390 678584598 615405858 149125996 755177270 110635168 496194062 462804659 852847169 324923709 319491075 683477279 580249293 82725311 448715171 326821921 305459952 5936987 338392248 53720366 289761507 115825587 186905894 961735996 951494236 121557224 341132752 512420573 971510778 41601009 616601794 858921280 208657267 364217178 70026114 434593969 700410951 293732773 724758964 950403594 395889976 873686006 598137258 382211245 859435832 803900009 887719923 494214739 224861531 657636870 236530692 385033901 598096949 973667810 717948878 997241514 196493038 807412858 956440 245623879 219764650 704668284 949707920 707779655 441895853 118195485 930219409 874474403 953373587 86309716 632334595 91100900 61801903 103516091 136142976 35232945 369662549 953461320 763965483 872581760 453320913 941393308 47563269 267627074 525181841 331617801 12755328 429679971 914787096 54108203 674839808 578397008 938065830 587550459 556684298 491087226 384566748 646083698 796211197 970097661 430396115 620903725 934951743 178302401 741960597 43483177 89089853 866932509 774187377 431404289 804114989 466386284 33413155 9272916 42756473 621653516 127119402 902210709 761888627 97054991 984090165 108073876 820634233 631623231 725966029 847213179 437574591 636727131 661254039 266897973 292472010 403080434 503860832 832052648 371370486 490032433 366577616 861768526 101954045 405824356 495143879 844911072 209428360 505087762 560708288 617886114 310802905 319488906 181518446 72068229 802487227 66711312 679188086 276242864 884370076 483127961 609353981 323799437 172091737 778987923 439461528 195107029 821768558 512072484 977330780 410812073 712517455 506360387 143544874 884610494 697299272 396872014 987398374 545977181 679630832 504218034 652851836 554997006 921081587 383447489 797324416 766402161 774200457 93527791 817850876 83302712 89100256 982499391 692822213 320905066 853815046 963910415 817811401 593247761 145335882 606971984 318463320 676001586 510092868 117765246 274074710 311587742 239933763 537690353 803532102 870540568 793508765 369734961 901670034 598988042 561304036 856472526 494634015 459703597 859419573 748370616 851495828 918034253 351125675 239891173 564597645 39897825 936110790 340884002 60775556 337842603 28926124 67166681 63675685 699161096 280938743 120195906 842635482 540769592 456883331 796682051 281560561 334757926 742710191 121865961 673847309 314054070 18450915 602733893 98546638 483918 276898548 981044042 832906002 191771129 950541445 761341005 515426229 161585266 194248876 369599322 562670032 418732410 32272554 76480422 583598524 200240532 347255819 865921312 529602926 457439133 740737308 530632718 196412557 307858092 930735139 85704668 278596374 635093936 606041623 749141122 573460908 417764058 284036042 432045046 70619757 103855033 645987778 3634194 914316597 822331761 356598374 66555147 578714581 289340098 224359832 742094557 565150163 716526596 262380680 59312236 962220234 177170776 95198648 877047158 345720047 1848396 258397441 379250601 387470761 977659758 527184324 715774607 421249830 597616074 655267370 683934828 789099424 37549735 176200896 763933889 18095909 705073621 938878974 218101447 362784555 824836645 592293000 145402033 158052758 155139906 771166387 791873748 430263284 154609623 669549561 827704893 579788756 700657062 795798635 641654517 130780982 357654419 612969051 664550319 923777844 471558545 163703949 285025044 576854858 434922619 960000344 266503395 107471320 598532065 43303319 780653448 190225897 916499488 21860673 551526397 570004397 76107057 682671984 264719463 5524973 155777009 448747553 581997109 372156292 862199805 769131468 394588195 783084873 881144451 735973164 490693293 1685147 235768898 188143572 820573576 9833335 432946981 990252587 493682619 935208720 327255997 519175386 919592979 224679875 487430939 595959736 332967687 238988394 881081407 425406069 26317581 850062332 972080227 507319406 356786737 854728487 625837477 868333777 75496001 550356455 301697558 843822421 112526979 440617913 754156164 879731412 827356531 150342500 294530101 392333526 500691331 923169787 807597032 193855388 957543679 755318457 601194591 397679396 718882627 788238930 479681995 310076574 866854100 488322148 802166848 94537418 156669018 535554784 349643296 231717657 234610738 189534795 804136620 233765843 68684361 754758966 359098000 490891459 433999164 134184381 98626342 479576588 103333472 934823075 745211003 904022644 726835789 139688615 428477929 491738965 664744073 496509843 873342401 752142134 801543363 537141562 518515822 103085068 55920410 969885745 399657137 914701126 970060691 553316605 558492678 314114598 95679028 349275677 464507095 694584339 138333710 64339969 725023131 85818622 708636770 873038659 31547833 456232910 967091088 239182767 417681361 545903122 706954702 42610760 158110415 603415907 620682170 621851833 400041175 942745258 198277077 368326151 751787924 718075788 56709165 9818758 585147328 134076290 41426885 758459162 164470965 825833787 567661632 832068184 340869323 791477570 889936377 768742979 613323397 37237096 932547211 144979657 889079411 402722709 516205927 692783434 493793030 846164361 411930793 712961526 19682214 133075592 201658831 990671891 772057855 200118834 772128810 668878547 121548437 57358375 784250503 432160549 818688402 730507187 826692711 90326301 290109411 931843124 524907830 308962872 734680410 217353852 125425349 91834124 948829823 609363496 238761567 118137378 215165846 854446019 5976645 721509994 50613628 81785942 620735285 996821797 852546246 929602684 429870899 995271536 855871256 114189879 607366802 217897387 447938842 499908887 122861321 578799114 265528883 185520505 588781466 950840300 655365970 974031314 546165032 190874644 839382077 481369913 755256187 276864305 439049436 529946358 993329126 461095745 943660878 476222839 609546426 871998241 363563788 981177856 650514536 75999170 482771079 28456809 980001569 659996590 527765068 171376977 682557843 1509431 859328448 717714886 699700396 804370795 252066790 590093505 901483280 490594843 622297375 44326882 736252462 502326976 641524422 625623350 916212487 896217577 721489962 437836035 849535226 230854854 526147400 27076554 107509990 682657106 147741333 832703569 163431606 306195288 513435515 617008948 763151397 659681122 483319511 23324748 732749159 249917676 927762201 698266381 784098631 999814012 260250421 299494111 205319576 924556914 189992952 481824261 613163311 113457992 321714696 491595033 337414559 314107799 954018189 677399067 72369994 19726677 792498961 724898619 379638541 793457794 991446832 408150822 998769337 744303852 707615598 842343002 62890085 419283454 178094328 661854780 794434390 583741826 655337296 777877845 269798613 31663021 194992309 689274441 215100451 264647066 251467571 595716203 224234369 824452556 421673060 535397538 61667395 662137296 300012493 810794126 126289862 36801636 108897709 533070857 975767602 427280428 806648450 770653081 811536930 970586230 565123677 424402900 201975189 266631596 248153694 628299698 113967458 530248246 239523659 458036571 161776486 61844453 231807322 395434834 198158275 574914221 291762702 206891096 105173407 672182841 398659672 499013106 52157033 301082790 776361949 976190752 742662225 421418556 785136756 596085350 102898080 885253610 402526453 609486205 352800466 635078380 636469024 446276579 624318747 76097864 901223998 298040587 785603751 473866361 184970117 433165374 2475485 737251666 338666330 375972218 875533324 836890652 188286838 338866561 560895689 832072424 461635380 598161874 491954946 842124992 714275649 909358750 18684769 952594275 734014729 780729440 719132073 774972796 170747579 102230215 7600202 712435523 832400506 624854042 559612402 452156728 405370834 556600924 379123117 768052161 862140898 363162311 602111067 779007978 504146974 120396742 263697735 899873150 492607529 240973174 10930208 532279201 616927042 416325444 871701818 77980954 201238630 828544567 549967315 129891875 931487834 510771533 887334133 187278683 181676077 969561957 828171279 645098003 303444532 257237629 165643908 819245989 138519986 33134713 947775413 301470811 498856653 578728146 635673239 239079713 237207707 796218794 725893117 869658512 293961842 542516285 351671560 792263162 107392522 884263979 139304453 51013967 276726318 531699158 169166467 928313150 586205071 47874111 854877079 808195053 327178623 52220169 337994892 593582680 206574875 988534436 713784561 422155414 379446567 803751400 97805609 576104292 109314745 617116472 847326554 603688306 44177576 661106429 411789516 36334089 610591491 521270199 591244461 873659216 760517378 196199649 329696786 87159819 971456533 430227667 790198339 541899084 426390011 406462875 129587315 715789033 592185498 24337808 538160330 388813492 197100963 155701409 752947484 70180936 91471966 36495819 182576642 223235736 806351650 412715542 880478005 908161513 299100713 116758335 428419727 867319594 164736702 544973484 40353545 660494944 127219371 888729863 278702333 414523277 499121323 380102376 742829104 933358100 31198376 658565499 462338284 734721530 684864860 327119516 436036885 703434857 493989067 121800463 962955586 221838962 277178355 747767649 30629742 708049790 929826077 379869083 169771562 855099106 317865039 271894849 583069423 985415011 506038321 97006906 32473316 890457895 885017804 330003976 416054873 103563592 494620423 969485490 37772760 272050038 481606292 940090398 545431552 807981395 276577314 601010208 475702836 582117037 123736555 214377609 972025691 857521456 12952142 864205775 878520331 197053780 583407248 510863283 91044985 420270296 336113581 126006028 207453782 313867221 124218110 88475299 812828119 492922948 301321659 435218291 54523364 952174937 135952461 372745740 524728009 561227646 978804397 877961161 222701918 862599281 449306353 237899835 535327533 554899714 991792342 775018445 875730445 369630391 755847335 770633647 187947232 399224113 402276543 551978903 744638054 652935045 981655651 288540658 891708451 569867027 951244445 50981363 31561119 242200954 427811048 919278765 632323855 436203847 284334626 954682493 66917314 159300013 957979631 490269382 4166684 552592179 12997817 279283422 25429427 896524732 599293244 871426099 357879763 457123026 945914758 150754892 366919259 551190607 837605036 611244717 365431029 345703709 633245072 421930954 970020475 574229738 961952871 716074701 376892917 66057988 352031863 24670529 649863545 289680229 82308462 533079985 422624072 13159522 184629648 886922878 14760970 576538317 786543950 997692500 304310847 891026954 856849938 572084929 685550679 492846759 946268295 179341797 801312815 829617454 753075198 62752930 6338205 781216060 630762698 829149290 376306940 831107706 374479430 478265594 86571991 77494784 540308208 60479634 49995682 978247357 656087595 676124609 125019692 858650252 355162569 849004093 303779105 271046689 146037787 953768044 998001609 335273916 655005758 159709835 105027948 441134543 408588588 985739917 363619352 397886811 746321997 528101498 108677465 525623293 615431723 221374302 538498303 623669266 584501680 448058112 649436013 458399958 589662592 942978521 692755387 845318320 476352924 881318836 619657313 848842150 467181866 503343242 560381663 622243726 695115533 25874560 779114160 110319143 613993580 827692630 819136637 6450156 456881725 64660599 944933214 54084061 38784393 176731674 589414561 823769147 423378602 673646495 101296031 341797498 526584212 551554091 56571007 997229157 410135426 131526158 755564983 28239777 76805964 858260166 207778867 416608026 421659647 33457155 911077188 674526100 118621645 649986122 662574175 659255690 885361786 674646561 399527346 121320858 555652345 643873149 398193120 449302693 966239248 355670385 8377754 539379209 958077322 851747942 523335962 242202589 545361734 42883796 705109184 322493410 769806046 753249962 746030163 396068942 529815914 632120840 636127420 401451129 261569047 873752572 647644457 535610834 69721477 354582053 277990003 935780990 21844971 814027104 286999996 851337154 100729585 431136587 53154416 303456464 684127306 476658778 830455710 911264694 464107161 60062770 513266765 596793861 398093282 337510196 76081685 281827062 387079355 617469917 927506233 404125112 124823423 308072755 701661560 925453932 285919465 722057150 283788476 442739041 645350723 46791349 180995629 495166126 770943402 882375081 762012081 636100239 599757722 700334897 256590256 26052466 979768115 177789677 123297414 938976412 730250302 871470151 489065111 719198339 175021077 324812314 380367881 49360748 58514603 746911430 385220268 59282544 192146429 954348289 508645639 591795544 613302789 585202005 125169609 794385147 287723112 394888994 338931159 405935345 653331477 23104473 828380021 990365786 460969693 373123102 474045250 831126361 955420549 216541795 497310615 979299025 579631068 546921267 838859692 572413996 412687638 235157781 255818949 333412584 658424906 18864364 339642253 107558044 222655575 7624463 670818214 124065035 516688160 978832449 182679882 630857226 635782820 859788375 551991950 28123245 191344338 165515666 290142908 372401581 542232903 10662190 118366166 574750313 227417081 91122077 770835393 734429383 314704444 493807850 525432819 561165671 766724346 794143587 167647117 477264219 585481301 758680841 170492730 44274337 376139743 740533352 496044811 5872837 651688172 525526768 913836456 510628167 188277058 25659962 354887278 165832004 896599488 565139210 649836804 595280993 589563966 317403692 307094665 461565198 999968028 63625664 419183149 719017628 392472975 853133750 252549328 190468184 786687093 275787858 785968422 56805333 267616617 133920145 574284341 405939677 940883406 801661789 231128470 478729364 99465493 184379022 369212539 853072566 14904128 604179953 264895640 73125256 493747653 705781813 149520959 897892376 853486571 265474252 877345954 303364677 864981437 286018419 762352808 754609056 254689804 917689698 692154866 39603849 87426674 108259182 649610106 153758320 371174497 367788303 681936845 283458466 146504796 536449808 880944570 102085233 725412150 841003271 938156242 645968430 792091665 977569247 558913243 815239535 631268690 105804737 335434254 414707963 980746995 349413307 297467270 268019789 840981106 58558127 754496307 19524118 86142110 397175302 917327902 201814289 494431988 670381136 658543076 585667756 16395381 653096151 543873537 148620354 111309079 556317931 992877109 141380536 411235993 331021430 537167378 82973693 623541157 602195498 686059802 747505673 432374738 994844409 99654882 94312826 851231108 787684380 299087843 585194543 763893137 48993008 195267484 227131906 971554982 392509575 281233047 107428608 453876007 822932551 187580109 605702491 462563199 641743235 814822954 837322534 714872551 359212324 455122620 3006831 90111831 618733672 33570852 925160352 276287552 777129463 722182479 606173246 490292985 282170719 330331561 284964734 660671188 763193940 96881250 576189829 234563539 110450390 395167083 621481922 228398633 458421397 852018577 769562066 365480388 310568353 113989038 511396636 526276206 931127513 733194691 577386420 675522869 897938371 61870113 515113838 463505227 722149953 979636272 994752679 67051049 273371610 648818173 274281074 493730907 748245878 458564587 564787143 864734650 560255935 890315248 51360947 61782412 647450043 692509195 271118045 368428448 599624743 938069586 118615101 635831738 102304443 597459007 565142939 118730379 328130307 768375556 583350633 489060855 301864365 538391010 691346776 533231290 542503732 747688471 597999696 177243934 246046568 726863877 767807948 570710901 179885749 748503819 784248349 577628585 727502667 91018727 51089367 56751791 831106984 666170813 225930442 366934533 681262646 954269554 187106554 502234890 501189085 915154068 139997038 802164421 172482729 550772538 975320563 309175461 869132416 938698460 733434055 35952812 795655108 414157900 732292315 447330744 63450495 248973059 687681415 855549502 800102259 149512143 475829811 222955624 830962192 588135252 643319138 164908862 741942947 222439573 522499961 975360847 925829000 389145919 648890518 256163644 747156635 592564234 247269723 697484978 714770073 752837154 709727444 143060616 172276786 513309309 103662370 853245022 209800064 870073564 688833697 452278700 212741329 738947432 311444429 969473192 752409484 326456423 807566756 247556691 834713220 74310626 801298168 977008609 130008933 87085664 826104412 928417760 144364298 9208249 236257045 522963169 792483223 802821140 329701833 565572933 798266159 679735249 629747967 623566027 519273122 315225566 556310638 612435046 689776810 355762737 982561899 805410794 964371572 42392823 157253189 533801622 740789784 446803921 892396763 224553616 936450639 948984676 968911273 507542618 770473213 482243743 435173389 271329808 697404991 196989622 724800971 453496092 359194679 697352589 657271290 437252085 711550575 499813292 204926732 402076698 544325565 626448934 847969043 444393257 665308837 745541010 770477423 961940482 916244999 361536376 9241774 730107273 229770699 699467952 227368765 664305450 760999293 745233198 819817529 31717963 553846468 183942628 156186264 285052851 301316740 606981105 415745391 823211573 880180899 898977106 603558468 990797891 610214164 604703386 165994969 504825530 976175610 328427924 308018339 306226114 789037443 668474383 267023738 714767816 788899177 450376188 628425126 152642828 255612357 807948190 881944222 839641481 571559236 341742662 700587565 856328853 451960394 796312848 994855790 154236537 693402469 113422313 305260835 628721402 173720150 672458185 12743721 118083881 83503600 528174442 85410871 316416448 213799697 228227220 886852862 303945809 604068458 961175582 131184327 117290458 366470226 514461423 118928376 831289197 511005226 154519237 196457518 749519894 976567695 668533891 501027416 567531395 296159700 804748129 738602145 488769651 116103411 158500067 805585146 845131580 242978738 871324218 141452969 438565990 180237022 273036739 582893231 711982310 879563315 725439255 457648183 439149085 471736090 951034425 278806375 133772415 309839351 862813035 993522251 323311099 277821170 378585303 937410877 436341373 322434943 479286186 724212355 425693232 257951282 128062116 277446111 170235423 926588090 888505172 797607261 176402348 875781248 86207904 625122993 914498612 412656867 279816958 831077224 92198155 62511987 898539927 32670393 125133599 692711966 480707264 90637957 259552738 31695037 327412217 835777265 877631393 255441478 504418212 615504401 856610249 997194707 162462363 262407665 331857763 898359774 507668134 419141852 370959304 761358556 566081337 904498427 768660624 148954605 426585168 905554932 357474287 418637159 895399524 842856288 933809200 358721466 964253317 866660022 579737698 693411396 935270995 876837857 167292043 165857882 335095804 968011205 642977457 211359628 294488237 228528336 81064885 225381041 418686025 452277538 710990176 892659514 799462201 348989761 634732448 177271582 67196888 43333298 484787583 889502619 930933402 836167528 819908255 174397611 709312362 696768839 401612903 187430151 546176199 139675793 164501843 886921400 125853368 657725389 876771046 940893885 90204519 137856620 949332184 922099187 194792448 875694749 449654797 306262866 933602835 677222829 240299800 722541439 23637871 778990877 599657519 953777910 558136826 355636275 527268209 807286462 652710424 580856488 367349946 847052521 364264244 467624067 969155251 300098915 62603461 963683267 798888254 160974486 701861184 38490398 50330522 884311043 618263783 100998214 722805176 778395000 137793377 186424766 572184746 536715296 763677924 343698648 371430209 90852216 986514338 864997280 31825599 299758191 346931105 501172317 999680201 398492707 583969243 329872000 458341409 229291348 86132427 118114000 334551905 90656797 741252819 918054845 710002153 256587400 57746393 106278968 636830716 11143271 43249335 220128357 372289385 742456494 706430738 394575156 748946292 946968247 210005879 500066789 227330982 781842753 317675133 891729714 691006196 14739467 932606373 201588256 783147437 717318784 446155982 898188916 772499131 42608942 268061348 268802238 135744207 755592562 707087914 450701134 555785131 83518074 269383494 393692703 641453062 533038589 748728241 557306633 568034196 375044772 761834496 400669316 629386995 758299103 320387856 80636020 184408627 958960440 863558010 948785858 808859337 170716076 14000466 557009997 515632000 503900308 136662031 162088216 609181799 248055845 528777000 411478916 123235701 577942529 707941537 674824685 483881317 705533231 259619542 54243464 246206044 251940741 321131886 307795848 578615284 605682517 28806723 256318130 566356911 40713914 419816087 810495984 14664589 859568864 675892766 167435843 452080277 192500746 641909816 41597689 458162025 753350214 974888155 381651167 382235381 607240888 914062442 517204863 238579493 695159752 716203586 837625539 242010469 896301944 640785004 90932738 709667227 844891080 361997907 762790338 961479940 875983750 481310422 922966517 958470197 979391281 107831927 86728552 362058093 364458068 461428358 707795264 386975819 268464167 535606223 914978183 111914725 286101588 970417 242514838 229307739 934407221 948954159 286919367 799675081 286275904 668453647 339006718 415413033 972598661 245410084 135275865 552344613 485313934 584308834 316077677 523902396 136567012 365055425 405780672 470698101 642214924 736113188 460368141 718474924 304660936 12111081 887065328 591986295 309142693 748792065 18336632 933261029 561430064 924860696 90263069 734296598 818985343 524997821 451882506 22554986 75093070 412808127 473908047 868339669 432992387 991787914 420377260 385166602 666593229 94646599 905194071 733003449 678207351 948681415 226790290 657597578 170850823 469653093 200290718 547121588 514713767 323734636 420834508 257096240 141786506 202773579 465093534 400277496 2826840 656211283 623881348 944299151 444437205 894920271 985065370 827404586 160115341 821606101 441188061 663909660 18639012 59406243 171422018 880929617 966044677 617714109 982973840 757563141 16555440 825177151 807912325 726167611 434652722 705231715 804783398 806250835 480320563 521926172 928953679 413150362 162102949 569071232 244918930 910234659 276132112 26878893 911640619 155132643 328734662 221262190 953384741 777779335 631022287 604733921 865758050 559030404 847719841 874173453 143208196 966905074 238384670 353972689 948432435 725796126 111706700 812922923 737625053 140100785 895725515 943820464 527535561 624575106 366089186 949896493 392482575 640166681 248554694 307206690 963467051 877803701 430232276 248273174 31600157 665632258 137183235 637766678 136568827 928139815 230115540 898322011 171011342 155955914 372767026 20122432 240533873 90851180 760412053 471352096 895851213 725057021 206310125 626579031 659451436 278850542 588867427 210048703 613319031 74994572 35493408 842580913 218412677 255333967 293249067 382709462 87508853 826062993 959758637 553337208 756747368 121330510 155487258 695343428 115490284 252929070 802286332 131997090 525088905 6550264 80136790 527121912 273764244 726132526 125897363 325561818 526011620 122739930 529361512 145525790 990279100 203214454 72584918 86320777 950482263 245795321 598310995 819905665 148392241 496085926 480411367 157103377 135888779 547373988 858150124 837317834 691877213 545416017 914909065 56587248 942920016 707995226 136956894 799362862 767401150 60139469 277676235 898422738 989576647 537739725 212019784 740459336 363640227 963358818 293815725 483775599 698258297 341606501 313306520 875164119 225410538 622051086 140025973 231881695 131782498 736612314 962075385 826945338 904808331 458816210 670527895 219993456 877381630 469378682 986130820 474925343 360021736 611560772 778536587 203259482 595857638 777863363 114575525 570630101 317700143 762378138 22199637 309424722 968609483 453449943 362902704 802830531 682170020 89735899 962636254 154935242 984467119 637633850 455913758 184491578 42253779 966108028 961472377 110667883 44737500 24677457 787746587 359001658 10677558 761880078 808111114 626195218 333289499 600113933 500032081 519831045 35910121 626355207 75840812 863992974 246955877 232964133 511933099 970995613 866680425 336097547 38183128 704054968 897654191 92845725 171398762 76004720 315921765 756215660 690210994 635319725 927990802 299798032 235140006 800692695 401443292 239641538 279307670 486586731 663242605 25419903 798389295 665151264 569545053 293478358 241954137 20673565 172452510 171701137 117520129 852051107 815484934 132133589 69285535 986006331 915890242 379431476 333417863 691820003 617133204 845732721 732415382 982970831 654600643 243506383 270738435 503980518 790336602 470238793 279171998 841757246 240883264 918024675 351704464 539808897 631519765 745457858 617498691 75292925 931259377 411433942 201226215 79412289 786101213 111611081 106896772 925450041 589108189 368569625 961687027 304400641 998365229 380066808 131599587 154290027 49943632 728817853 472495852 561289092 376193742 825852956 589009798 117957272 997028551 325504243 175480595 861736704 162705325 199778926 597778027 442302874 661126959 839299738 353850655 788731712 629715455 634544215 860276435 936398931 700011930 725341231 10379415 953378765 376568806 45392312 3873286 218814117 133490407 85779568 586263969 427279886 546250884 643689539 88212800 154996186 36443206 621861394 490226970 683670401 190839774 283990080 890377995 528528607 118150576 908445654 137008400 268967070 72536230 780111135 375687993 983545767 949531518 738650722 492848624 108090806 302210181 18575136 310751354 196911042 783749083 626114668 1545245 995620007 347508614 409019333 423585085 926452785 736239262 86009850 808141900 71928948 607832512 817863153 529847545 667189005 935019217 956435319 418335961 206043626 983742176 491259324 725870474 226848298 67916313 659373488 366303542 878983895 817757691 412157077 439463068 575687303 984698659 76734706 230291776 638989493 952187549 820842161 644535277 910819404 900278966 547120381 242097595 256118795 709711702 736057084 640597480 614257723 364357170 561376303 345794206 532420988 46958848 921152486 219845374 491722190 906455892 877775804 355330163 261534911 637029964 567134832 401728623 880577185 611448684 505883890 911384980 818921961 602967775 667215500 797232732 905872219 56512186 763211069 308404095 319192222 983616360 745708819 600828347 725339111 294554727 603397678 778600633 536759008 722061992 398450591 941868574 841462889 956249610 233300513 756233259 228521696 35445100 954380112 23095612 6414087 845394957 658324015 808307757 482047626 997712322 229677445 547115992 713528326 124190229 167413490 40238285 488506026 542805031 656189799 90155520 390562985 926508935 866386085 197193607 384282456 737612177 68237372 742837663 777778017 175005294 72708127 676642322 45930139 238761652 246004728 432058315 386159805 645771723 804205634 858259039 585449562 67170613 343888962 18508254 783513717 341573089 114443600 725578845 201632688 233357200 294964469 495077980 530709051 66542357 337857578 797192425 905637548 669423321 193847385 897531303 676714604 901633361 301655674 734159009 356719525 501652593 589515050 997145324 884142870 952098569 977527684 429259874 170674476 92177012 881082146 508198217 21136759 592311262 208205061 997182630 259628433 809120505 998834087 160495070 422497884 943583728 322019008 313244574 112133967 926039775 284450469 585675160 640139293 605097287 64214020 866078398 156482097 795908900 156886901 762647039 461263226 748058287 558341201 556522433 924211480 1640388 560842372 620988511 126930250 787743296 384998902 110762865 481143910 861458360 279529132 5037119 188116477 325982470 84369336 509099647 278058081 762527449 371428728 288591157 384671856 153867562 942234420 31088690 359759531 560956930 814377828 74301533 643785353 521435121 985483519 920415569 701052033 270150642 439519510 576406599 228401225 5892445 604563023 822279915 619157344 893879525 474461301 789003003 454606776 917108620 178693802 437264153 279573191 323989353 169945597 17729790 968810689 182513959 237292107 596183554 119966265 808781853 933325047 725417984 251150642 269407362 839010702 237319712 38169669 191809546 612532387 489216818 224740892 924879821 949787776 230378363 310646644 264696071 734586688 17761997 138807405 327694150 450438127 964058310 296016851 332537821 964728622 52556188 471206896 431660125 38404825 853334009 524432161 64496971 49710672 509515985 106816377 909501952 276367116 250512311 971455572 326952851 829980837 534754524 280134555 366959638 806284101 146172766 446647112 365595047 561019102 278923829 432526635 581921336 41696027 251961055 675855168 566744880 121675375 16911018 48266323 674969276 374258229 206620602 364970375 375907680 551805427 438220004 248559460 811059266 42122825 888801479 181617041 843329339 779912905 295247516 35399017 813443081 487187193 649665842 874442632 857383807 849924596 175314666 567017102 987323080 88411433 133632779 737869828 646499885 152575894 14565344 493445409 911734352 140506046 237501962 344311200 827386458 795085648 805808544 489658258 392159235 354940020 584738521 46268918 359413137 952798027 808575605 265273059 319342861 842541495 659326258 811585852 589031033 732315324 716504394 900534590 53830722 767025664 800943441 100640555 218518696 640409789 635316387 285757937 273001979 159045223 16286328 671589372 738934265 364675349 68922420 673050378 580784484 715327957 511438727 945262857 63711124 202766558 805966007 409687672 781496466 195285586 403909126 781698436 460599004 432214326 73590904 438433331 430763439 40431839 450875103 174268285 710175104 604254525 933928936 899451626 838525986 480138313 342819815 37781895 771766523 382981013 848876538 589310897 72494397 888719851 282007378 498631725 665541565 901067846 928310642 578845008 759079454 640471674 225588436 829212119 342632174 477879427 368727164 219149802 478244100 259208395 425115108 208863819 351768774 471066836 577180091 969713137 989608429 641283816 660744650 273804850 382340067 213246125 708895842 827343849 584203205 877623494 910353778 354835910 855706250 862965056 208517468 127984364 463465943 834423322 403851306 435309059 460660746 679954097 44552789 904642434 411068641 588837753 99025832 853241460 784463013 132246889 921400275 107208991 728814688 305173068 652560460 750456883 804788191 975343271 493759142 574348642 357724252 324449474 103678979 107696457 791634084 146755960 817255116 532464069 406292052 189454952 298711112 836185675 322971733 730024350 124871773 742156896 310433082 129508698 996729522 764174247 114373403 248214959 875107680 455459190 1715428 828797954 732173378 192806040 424117107 85964828 189440589 66043272 208296366 977695314 767275041 13594028 285636914 476931760 749556180 191481786 802091899 270875597 178134846 905301596 645405904 638928384 989058689 579128558 60009675 723681326 510079423 651501225 888134604 761080309 641994150 284665092 276873884 932927400 250189089 347476612 290822378 246835273 42222964 191589835 88213846 478519927 951607097 702987064 524273860 125835358 80236652 213368243 531698553 565577310 306208699 316977960 794651203 320697388 14598672 308870395 381508535 981386995 655213046 362740830 411897022 241299115 690972201 937430647 570053492 962575785 554895199 530181978 162068759 462639924 350364224 729737792 765937260 712685029 74862995 695117260 808629243 95934642 241341458 894775278 393423315 397287221 467156501 595823221 207175950 440299419 913840141 901074098 688435276 525718753 1312136 586087220 802888131 925688989 192368066 43938100 410850446 380280925 828047919 936337748 916628136 390428544 924759939 282785551 594074378 214321533 321581025 519374580 842394678 360531264 527249809 291933171 932940536 324440507 555776755 440536194 217281323 441230144 616175019 272072935 530721012 311543628 744943540 144498571 432382944 3299275 961267461 510267022 330142457 853591135 27481043 28021376 780194634 42414096 458413253 351046229 741023923 917370896 210951440 540167873 338252928 11189498 112441735 453576862 453852440 946228036 36519236 68528017 649135024 73581864 581485435 41660877 575133925 728729863 459891626 486366630 732529271 473424706 373065504 363367240 704061424 235427086 108316643 371220127 96258396 511618636 379951934 182040715 352549018 728776872 994718021 721367822 872096967 111547378 204122043 311888874 939479650 153869494 673265826 249131223 599038779 747984021 728666208 621921950 11396835 11939669 690551831 973006333 825978237 548532586 21719810 286092208 531634525 665181833 862846679 165501006 930929794 777086138 178892436 308572391 200844247 55431452 241569313 153892897 799585587 656092844 724325848 914891547 482858628 651366282 628918773 502476500 39905200 805314418 854985593 36330720 763975942 228516674 55372777 799519814 296455966 877158179 328240614 922814759 866153271 834006176 693122385 545554406 856941367 484882251 153552734 117441899 603379136 946640356 307713694 520928863 287756918 616462128 948821698 675137659 499020464 650900885 17357997 94351759 12002712 551997481 452310235 398207337 848127934 3481204 91870860 946864459 735791405 655757327 275908809 530903240 401152936 150907785 852118525 63698887 319246895 171531146 788512789 121989422 821874805 400609619 668025066 404858720 904116024 880549345 676458764 715963519 810283150 71147313 154531387 768965332 729892898 481556588 625431537 6797719 6377666 359597809 993200867 222852457 350004506 267727896 62762537 134884515 168084509 697941789 251860138 322213494 353234710 166495556 707198012 860475014 779562322 850148183 994145748 618115726 174172534 176911805 286918352 508956957 883559696 416128608 772309648 772440702 925884727 91154937 879207979 733597998 385778071 543496193 953364009 720627789 823594713 576185624 907644863 762217073 569045301 730846633 715073378 561425712 891827769 827117702 543140226 26504509 135836018 143632339 782938946 746698622 525539373 825735433 17208028 177126708 974044499 778768848 128809974 471654356 951204004 148516444 891913424 846240881 525681752 443262236 19458719 264767360 96469689 745271957 324790825 551900126 477258830 383662204 893344090 36199108 380134304 437901243 797084547 882105936 27486681 938358014 519756380 385795609 107784436 852010962 901207250 475332418 573856683 705256470 213283044 693288668 546221165 461818987 672311676 125316135 289813316 95031602 436295887 848202028 67733835 957573828 751969143 504622767 570095305 188345220 990019496 496990171 929981113 400570364 693884592 395479141 664994310 149620440 469040224 954997005 244495995 983238144 479511362 914600144 135008457 50109758 866094410 647542036 770132999 97131954 741218689 391724974 571312921 275247422 278741678 837440906 908164984 386062037 972633007 154598773 136265920 582384258 284860833 373919791 687386872 736622960 705446087 197253878 476320329 409835298 342930457 599134821 746468595 896871414 466319375 603362671 625759707 904713936 664329040 622375553 557558318 385607921 397558558 57734527 488864790 177204761 317603406 851845207 583971274 207473625 219272900 967184675 960586835 668483071 387792042 860634071 104001879 804774699 706675534 8353749 29110167 788348290 83786764 921523158 501098380 659687807 502958767 448699405 270680664 947321640 971679178 244556515 90112551 570851699 651623261 269801038 610828612 939873670 964346717 691298611 710378062 767813629 320317449 578016064 7498246 67377090 388524567 72188430 938343294 920429788 669785114 438601402 305473731 353461543 27989637 95767292 16310492 430564950 760078195 975819624 729233279 520191184 196933797 398011854 211060103 54319259 148692325 171399890 935191918 351462136 748787949 846173082 744126832 887137624 901788322 623315704 981082177 130917932 655151511 860961514 566338815 941930574 534313253 372165345 164414424 873132117 931124846 950694455 236137600 798043465 646122088 988793657 779650592 44826365 570611977 281658801 672418039 993673091 155890275 927911160 104518337 377087078 72198753 217072344 895501578 707004022 352973330 262433851 69374775 895643766 523077840 288649146 597104296 702128696 838073789 719683024 190151929 361027115 32743160 308318684 947969377 874881523 669431008 350822872 6650359 129649736 871827370 587295144 31881053 92329869 797028045 647830636 620147252 286432727 346672281 832995563 169065298 819184921 64494928 415977097 593733713 555607821 49091083 559889017 944969560 485126637 299603120 400220574 776935428 960635399 290047651 180107585 204350257 986008098 917444846 549264678 842023621 556370216 583404574 366132899 644413359 290144707 708948554 715017791 894221815 341645056 476492451 703971790 487888552 516132778 406538825 276689055 252019827 884195469 454040434 918929796 240554905 968498372 899657776 724611907 57757232 653670558 15202107 453793161 474108844 584802645 590999620 51674231 967530926 51123190 445662632 108994999 464621034 164972080 793693925 372726844 713119756 792704970 781694875 481117228 240448584 614302164 543174501 27151395 538962388 819749969 569237040 713674519 797392549 385252946 394008143 280368328 230475110 748951326 488171591 886119524 177871836 599443507 7209019 842752254 1631415 729252884 407376756 590940623 428353613 157202805 216259789 905850586 595919098 542855877 447487541 312752191 431672922 681465966 989865705 669629398 977341390 616249403 743157738 384120965 211340920 675929231 847555850 484880708 611679015 468691454 787944956 225685101 583095915 916360360 432239040 47003843 416488989 836788004 963102039 534299775 917259596 56233738 998691790 146973831 690372913 91205010 697890229 961462353 938648218 580595784 244177322 222290551 422319385 383554514 139523037 636003033 577010 539190114 174242727 111291415 560187891 351800195 931255609 230767619 47725898 259183154 864584197 963966287 112552086 427934173 230299425 632992853 300712145 520137874 681361278 103962707 452001746 38209100 416321619 666197890 804944852 512247197 865379688 537539586 896574346 21445054 808353009 387860875 972206446 683818922 128207411 762466798 998101143 983272645 885729392 126299146 683737189 660142132 735335808 325158442 265582785 590346250 557445872 802577 195490161 571544366 747969410 432080870 850533569 167236666 133805949 475021097 136281642 401948244 536488240 24518701 660475884 217540193 827085799 114758699 614808565 654925808 764594278 140729134 264090683 19855793 363415515 227262776 819574812 273241461 667506610 280362028 192116585 221313655 929291776 320775344 993837238 226971322 556568285 702449674 781326167 997433789 952183856 243698861 737590951 815125331 615571519 943090594 235856522 466391246 829903664 836837802 251396922 81189669 522848889 713248576 533502524 828404329 576570283 573895516 790170978 767091772 304630079 885060608 894107407 610798308 793161800 611497105 269974215 255018186 815131513 879053498 229575661 906090013 773314495 601819373 226580123 36326352 185700173 157246561 417387805 425608003 982937583 614942415 273605691 514853858 361043864 479852648 33948863 84310882 559099307 155560722 736702359 761295518 11239476 63425234 242646184 765735954 243481287 563788680 173955207 338924089 64313800 965481907 578454147 245692389 157800117 475424567 649580595 216046468 449038349 681771531 981891205 654018973 906473101 581772581 543493489 198743069 38215680 786818817 881132710 918408578 561867624 854778792 204347092 2383779 155451161 138080116 541157667 245580406 560780311 657912163 151266399 661533748 450115767 446271189 278380581 351162662 22446603 470566799 702597588 971620284 882436591 449745530 734580102 48157066 522379136 856687364 386432457 442880135 659811323 41988456 135646021 502801625 490066481 508397367 940028048 600071349 265555662 154646184 5451561 528648064 195033530 360143293 448049150 175240095 513444186 963559834 721012401 576741698 378471279 761847666 447521563 202379659 609698264 523434250 610980571 223625710 872725607 684234792 903424293 739682995 763953219 853135967 264016377 297193643 111359097 603180565 291975463 849257094 554044446 635708278 861146184 874333850 209015114 379949437 8129726 524987893 649806732 432580113 526930286 363760391 479750019 58752660 212756708 198843271 177672861 404247054 505535574 38977732 16744517 186105535 398860613 599796581 299812294 40214244 534501239 511451089 859508321 124670212 78517344 704756598 797278341 987539560 438548481 555945625 926855471 355917735 541405581 9399368 677029357 355709596 694442818 319385758 578891099 264760845 750079880 11403866 753636998 507128601 639015082 598216492 323684413 570444739 31278178 678969241 719678000 799658770 574517159 20929886 35251162 802419347 979585294 129873773 249086614 118627412 948859613 133256134 863697138 47007900 388796265 390818596 679364244 333141393 521476450 423559844 397889207 698089625 138056129 163963954 116509351 145570532 735346370 850691806 89717764 820583030 594238256 746025119 499872081 963390000 224373624 893428034 676121860 643665880 779980243 184268524 561327840 566032543 314945190 503222863 356017539 87265404 686502278 920018334 328621288 541556800 668094521 951125089 336276942 959846847 786808010 759413252 30635414 539072635 224275885 488314728 114709238 326717182 839273184 907135864 365061162 400813362 580281726 160695696 672236636 729843825 230582 637112539 533904233 73387895 678715455 531729113 716872714 962651344 793607292 70370117 196414807 109855492 355823765 945819746 266620153 909808469 778136447 837055102 731067996 83119176 113902949 302769144 739898839 244689543 927802236 278909928 885167811 105176216 33794248 603711913 924521347 391125770 898737404 780868472 964771449 762770231 558148925 876822543 186667663 68817708 120870563 591527652 490708349 314683388 544575826 863702074 112581880 573504246 13256855 848034111 170476860 54323401 429055508 949240584 401869374 466963312 139573422 757352733 283549442 150040516 626068076 376498808 316184260 978890141 61301014 450315972 471569224 142195449 384617215 584407859 777743248 485402139 3761476 642713219 398208183 746335169 961399018 223991817 266871122 370670964 733690430 176351165 997257024 889298378 976050343 46338094 623893150 289570555 742789796 632182597 980454496 796170617 958753412 439977939 531770157 741978794 238861394 818854391 647231939 409514443 876191566 352047719 851486710 617606275 743162154 736472061 43466690 940275853 438456662 765915840 168373579 528621570 418012096 435669085 364697423 997924429 825170383 804832340 534378347 256833723 904911912 278971237 171663053 83574166 884567994 602887692 377842337 877862382 886281415 533088456 481740888 735743819 839989738 824902651 388729038 331335200 197486795 552530229 756561001 9442525 793779751 52391204 243100558 529957817 456351471 319488527 341744572 713116758 579841549 937365985 788483750 884641941 316758302 812576967 378126799 97312040 789600398 95404567 15065259 512151293 639919495 411588870 709479875 813563280 153729227 550343904 420708236 796313645 783848246 503246688 326380125 17155648 47738652 917500279 117368069 642012435 272917418 410925944 849329771 518105649 22915926 870545217 193123096 936323444 401762777 587504889 289939014 472216751 468599796 900655841 999722495 208427448 527047912 873345079 230351474 254232667 924108203 121808281 314133078 381271329 730154397 611357050 670251148 847234391 593529324 718390296 683381687 433914809 7174033 479345356 524891251 838047774 204521887 465437406 303434623 503058517 130135938 623961323 201734822 953441773 319375043 685507205 182490101 929830059 605208890 592742461 115204378 819625315 533436330 181881625 488104232 74938421 635953718 162143347 324179191 428297593 809298646 162241128 37533125 205472124 912552567 54801824 893021089 319980456 421111132 46176622 438238095 926868994 211763797 869079927 687696579 506289059 840584843 649804960 192319282 872916575 971165764 584481290 27024709 259720567 304783435 936290057 682123357 188230706 947751925 834628643 332235463 559498932 925875339 903718130 839260540 287697698 916335657 894784820 205836640 105320156 752351294 796086520 69417512 696676135 406840593 741638340 598643933 242888977 90283067 653674316 942403051 889301568 24706411 105457821 52733790 89268997 138320676 855085563 743878407 794060305 399190680 405232399 553633587 11522267 590677504 407397264 699802775 104886214 822973573 879123208 221514603 896040761 596121138 822947311 476790508 323826610 313418024 547066152 618947166 278680863 486194048 235064032 588087770 134833138 462252545 910566993 507350951 606041063 120247307 128790551 845877321 134530786 60935859 131220817 597522293 912239764 397235991 295572988 198440692 284224806 442253398 331278443 430249601 567289661 564040884 982472381 224635670 230268952 707945820 222929590 841394821 925374872 697659252 260377903 856981435 497313024 498862358 497707761 2923066 964627243 592814935 56094465 986472831 178946990 319765319 321538501 995912632 98537812 158188326 134111092 51211552 694517835 332182703 990778289 375563369 584844723 418554688 206402086 534266974 431928152 361935641 399898108 830079055 643834197 248380972 128394346 591302355 15494963 666630125 843252516 373388111 122842478 206150689 56163716 800320445 466075382 353163594 484183601 257899858 802241194 762304699 587296553 428617205 156778866 767409533 731122875 739405467 771359886 17605796 799885911 726661305 640010575 206501999 658657792 648627349 478340942 319793622 364329768 528330155 922765195 545552275 109946270 843757736 673251465 439629830 373438782 9449543 76570309 742336377 630260356 588045913 85877944 781264394 862693913 379320097 168339382 854309722 63400725 969605037 671842194 144843138 566366317 941832189 677249339 454982853 418628576 761045080 175593188 12991685 909186131 757039563 992255817 311247404 966816115 712438913 685143435 156936941 505484729 804839646 563035268 220669976 49126903 472297743 250639024 35745245 831679622 680725066 980320919 95588394 671606995 699616765 101155546 413857459 352243435 458330599 743655874 193847677 556445793 672871333 826445068 76258757 777244136 957108605 825554463 582401955 33837569 162907143 877530920 633631601 665357510 485267627 605748975 740973730 485982148 613208872 459807818 55475224 942913007 883905811 90939203 959917115 889889390 713732477 707476489 3826087 292975293 386717722 969080824 711783430 895803736 938795318 3327962 694868094 959433147 359598202 284461176 286945650 219354049 48898950 445834322 647006431 346723909 373637229 725651137 643038850 488192230 951423374 838443617 344346997 347380604 346420433 779552552 144461725 470888570 62640220 363310251 337539182 182804932 850271383 704154746 918153059 797454688 384865886 506319681 816609566 92444941 979074058 606073472 812240507 675793762 988018340 422365093 27005783 648850606 87383286 919030310 677125124 195180874 454214299 375006237 468039980 81637308 501106789 840489652 986080567 811200978 500959534 556054954 950573359 844670123 59472424 928510423 889640663 96246319 364252441 474035576 772137314 258947746 345804535 584308718 597868404 473824624 97421537 404847633 118691266 591884677 144667011 780469057 663139464 919074025 614511632 789938085 118932201 327047009 588721815 300328935 373265846 257693511 604719561 601787528 736299180 819863948 839010455 565428685 304622826 693349817 483350607 909303117 404794747 155619335 986737204 976709054 566226943 834242786 89418074 249015677 771159786 99193170 692692797 995175821 258779017 335150653 213043977 182077522 749922144 177730063 912618348 422181492 668564188 91703046 807291616 295681785 670737287 757134920 942778136 246979150 174613368 872056313 272842365 334579068 224297879 766994910 989294744 968219229 880870649 919272891 737432371 83995225 411991782 108704449 305070811 593445093 646428105 215649473 965493226 887421464 770839417 384003804 386325915 779249701 614183212 271408827 37187787 982689106 764081944 62506407 140860654 92608070 285041047 390483299 618836087 79691938 418085963 108814291 718033225 771371033 236212710 522183175 98259339 386872339 455981910 663357948 223581098 808820214 182154329 75873611 896055599 774283836 655581121 670843264 781872045 599114625 947420533 67773488 2071420 999899730 208924237 369868825 920738153 602319411 400155943 447954558 941013774 125539392 684381854 21546481 668937413 388211639 389894108 802499752 408420172 710769331 670914739 34541646 770400838 518361640 139435194 585201896 882790900 238035315 722970623 539097706 867000503 889410601 400922802 712409349 137133509 992622002 360033135 219961300 128062912 304951197 503896147 58292680 54531140 29710911 772656414 232987133 361121198 87450447 211658096 690856821 741235057 382552132 25629707 61813769 63276463 903050251 553174349 29824758 61814392 317682394 532458074 984032286 966489474 851600465 386844104 638789529 702976800 78974673 318861461 570443821 847314667 576949279 986605818 956376322 796790972 392536903 609430878 710736901 986629842 344500769 890052011 160882650 815612556 745736332 729473098 791426294 65078168 583519410 926802543 285009980 48789293 193151788 919325625 455265500 483604164 744218599 963765339 493201608 61664996 397523767 450167087 954150334 875140845 655665728 357332864 307038351 942419322 794859078 28288443 104099347 371365203 805640541 31557358 940702637 703815570 626187639 400443665 353659668 83388232 709684137 457961024 611920501 589686578 955168881 804808109 601319808 351458913 116771331 821844598 661968100 796848101 448009959 865653643 545909565 658957537 47644340 267994398 893912135 983807967 67948786 948949495 529245107 92286647 744347467 520562190 281243985 66421588 750088958 697901007 491353672 665419657 581144582 17020928 484010870 837039192 546538021 199349957 642530758 58016724 318807207 239773152 277239974 830039576 609579137 311190835 153459440 910502605 226541259 341553968 59027718 612751147 944474955 735405547 697882417 970769483 982610998 836790598 937456247 836632668 453103821 189788611 194413300 71851446 588807855 413927486 509543312 519777565 573854211 300970352 546305635 552148572 384630729 573642310 315063931 387349010 822097209 599975901 958887655 405880579 918536918 284205901 990625637 262973589 530748149 242156066 398452153 48846046 192817725 202036904 278628072 722393172 588614544 975592435 800644243 870305448 864187666 325587219 766846273 903998509 881995868 714511551 67318702 524460401 159000212 387175798 422705576 57001349 810046301 792520932 294999178 947585556 183913927 565472645 600745002 670948994 325798473 112093870 344063379 414604532 82443569 473565162 783799837 158973135 109388993 680144435 41028444 908495301 789590509 506619002 479203956 864415626 557328080 627198564 754335818 448147085 698790899 495021296 547964462 728639367 812810244 37958747 38034616 335934193 244292944 675035798 410418407 688942326 790734369 218773695 887673449 197058468 685611292 827817437 352576677 594730927 761768310 401111490 9417557 111050875 879036654 488321323 769354026 727989296 132405771 302207702 476558422 844483322 621480140 156907020 814269945 160561673 27865480 73989615 230654099 815837847 571268329 283956686 920677592 724868065 297101100 472221986 245905759 761992890 373047366 534610096 432995397 64310275 875680088 388630735 288177662 435623510 81403166 297063929 617569984 514155134 960192246 115737188 290078895 324054494 482626347 934143346 854084949 992644523 647231386 463295578 392151250 425441524 518353350 471303545 835914543 510505160 351362237 450261914 184101468 715412250 303913723 716505994 132871150 123755176 256567892 170196787 625943559 535436808 187934116 668781718 1921564 359392856 34241757 892526905 348648044 95029731 780003640 656249611 27102201 166036345 226375013 827778729 7600528 536807796 112069141 528714176 231680480 606948624 743357500 705303616 882248877 953550731 177332076 748174507 478327060 298266617 202682022 446455755 804675864 360126609 902354096 625886642 610561183 392172959 855544958 41156583 487207468 923300564 572064927 406234973 321122687 944282187 211921531 722724487 974853902 918319953 566533021 823267536 577320747 646896703 574033745 67939020 910087117 838815776 136339695 692822401 510119386 957991514 516950057 142222464 543029347 87773534 827470424 518879983 117740689 359932375 475881396 960273677 902001098 703772223 125085206 445994068 787592407 192208748 407275930 442881406 634013115 466286416 457267654 9142557 49632533 257215413 13296025 245371694 654598359 381021436 442627242 424038322 654547083 267530557 463398133 112646251 286944974 138679577 290979087 688202163 900323091 955889725 228946646 344854368 43467239 142786397 14926202 260057800 402972852 152175048 809442911 194739660 223317153 662160513 455525696 384927326 76772562 250454288 233062154 581157911 536510839 897823945 329048671 24429009 742296860 596718773 90496952 671995996 300168371 433169072 950732869 920351750 531468633 170187176 402067334 11585814 133623979 840293488 539837624 395777655 24378644 829899058 198216530 995370351 48510066 115086731 644910136 832545798 588953881 760512672 389455774 776554826 285141541 439502178 751571150 609107313 562862709 247642036 434411369 31650233 158070028 727772959 825837722 138833041 173752342 299639537 29698285 53522772 445293092 565752909 309221952 857235258 505467489 72862970 382146658 392132309 524872109 832559673 589707523 774653296 581076926 213692230 662714940 251009372 692946761 631498014 954777628 239132828 715215599 343136203 899281074 780985458 739731245 616639036 953138401 106722277 185213876 385097514 180323627 197962686 615740161 545470566 787101652 948882976 559244748 499066740 26272495 834818060 559787300