100 100 679412296 219488437 460883814 849270582 914203964 853087291 972797592 238148533 946904899 290109986 878518725 133817730 740480232 643820517 917096260 361836001 193985347 733429883 872104653 380983548 500671422 566464260 145327195 972673040 493249674 777638187 38819143 911907155 906346995 257025545 258623328 601814060 266979480 599460988 443719038 309130884 189149864 709427522 926417843 910757065 689599263 433714872 678844829 236311506 916842265 131521314 132172601 335749409 260265005 261600777 666555834 64635774 688192767 836193907 833696864 188665110 727633215 437862997 41559024 435281156 623581611 828669847 785284956 834057221 868579465 520354199 871801138 742626129 194027775 580386409 244958753 649361090 603189758 390492845 466638139 674326567 359721385 33098294 965267450 930461815 214720073 855214148 851084976 557023049 605393755 82339977 695397523 922093311 773872473 523069590 471146963 607159728 974506624 564488604 480417619 496295419 282643884 296027987 906217854 600163215 483011138 180580987 928488112 765310892 530992477 327290225 226528942 963977367 343904558 610128921 982083341 930266838 210061670 500073616 362451544 135694749 288433008 726891781 715998929 768593494 231712992 799253196 831746929 353075991 958601707 871215239 416491433 427696734 493418246 942568229 786762353 671248682 441502038 542554642 69538304 114339626 543697491 582956365 522195744 870628589 419228532 212069031 289491957 437924711 244328151 330006602 535067892 101167517 156522397 927304647 129676349 82391994 490480628 301857219 366714491 527487803 781868841 880454494 391912264 690838056 908135161 836416902 154527439 123588086 912967803 591476905 175301325 885082667 230871293 28274897 214969604 916506244 783654171 998281254 419919832 182664554 852304433 46490521 656055260 351933753 107789887 93225911 25717058 203084266 589777316 410557758 894106391 938999268 223520119 8386993 446104025 451126375 44782853 560632358 483216291 372091394 799659858 686908778 479334689 790422379 433956714 464997590 244202421 880175146 534633032 173585753 840300511 457758183 548517927 926072606 293259895 67514477 787629034 83721636 109764185 795656776 35677714 966657157 198697230 630465998 530494151 14807731 296604760 343595553 682592636 248714762 841594754 34926294 317648871 405128586 751537167 396583085 243803414 55364997 821615436 817411892 923682914 39043288 399901510 624152754 88676010 727168992 404270064 623167509 373040164 558527894 509441831 555655071 498107861 745262471 874948265 545470498 619428237 600278386 76939545 187160056 655458734 992883437 785442808 863561164 154824129 442947161 211444791 515703481 910038080 224831807 954516341 531938955 95652889 198414655 926708440 147590847 999361072 378596274 466857261 690605646 829883783 491410093 193934588 789528756 478367352 264808305 111409007 101571842 699162279 134906277 382931576 776922036 146213167 19146980 221921978 649729957 131200942 786266527 351284018 562249887 843493393 41427385 464215775 354558072 669116302 57463994 955593883 937444824 696313828 622015967 242824284 56315571 81143093 897956291 822389711 766994269 279246964 891268735 627054737 862908921 917678810 299142043 526306393 467828387 515378435 890675596 382757005 442678137 488376593 238422448 676990526 446101290 619874428 457844213 869298408 506012853 989698701 241472598 419254924 959660369 980093667 194357892 664711573 806717711 740807090 944461114 394498702 23554199 712160343 192856159 832090326 139221596 601274759 595086147 118812818 51229102 584228122 240722699 227231048 901853607 416986068 960723328 448980874 437625861 704837407 882615332 420466514 922759970 503931160 828832483 116991689 162849881 682072181 876796156 62335542 511318281 312619311 570086548 665077983 670110493 301245487 86991738 7690490 499297652 443364174 59018778 649770129 449052492 846732916 459481796 889500383 750033390 245229650 633961399 954285700 49330699 372151911 510424722 44110634 64371682 309095819 515278602 175053698 688946695 271444575 171695633 554819764 795320081 595524997 935491750 152078259 368356557 393245176 355624408 620779206 423041646 524085116 385118893 557882564 25425652 914578648 788301595 716703091 510964374 301638543 677919808 481227668 960609782 100940988 773647276 297900846 213878777 937895313 587501989 693475012 150991785 991376088 390759341 417595521 620313595 525917449 811376598 964272935 667578398 621422783 546532725 458233273 495584052 730690455 763148987 624893697 121705499 969468225 735278539 955449352 498531156 796991932 574897679 253835056 375777075 592699521 104781585 938492222 646194690 1608429 458703125 105714332 555706095 468052356 874980649 646426303 414156995 128332119 111899057 334848681 814972384 13018707 976270237 748161496 817598206 201802986 427385190 838015936 326719541 561060075 550567262 637330156 311452583 179242750 981727301 185340988 638736625 340779953 967112822 927860547 60383345 122852182 225070045 523366884 304324269 249292520 460212531 729964897 748714372 310210859 999507093 985395806 939362404 511936157 102276549 458425220 206282598 807092409 445893598 426248607 890222413 861320286 16738993 980425501 696028401 320365253 624692582 874383475 855208374 702606798 602238032 344717685 446007469 981989527 481176063 898744379 674701557 352410801 694373700 930409843 37565433 724140921 627072461 561261655 802893205 275063310 705552159 298289786 62810111 352967491 492559514 922063719 435060150 564390802 335354976 838370993 207110769 252033049 270960918 803253598 926291276 4363391 45403124 549081649 103039622 876568841 110028454 254129272 490363332 464123057 278763687 826260618 548487702 27579979 204892973 117934487 429030055 616117254 409345105 498857150 603506680 818707679 732347328 579235566 386648077 56165924 406350809 986702207 753976973 11448956 13729332 469166113 916902654 459313513 912243345 860340616 891312703 722967017 454889716 141668269 77929899 471277108 419738078 110824497 827794165 955761973 980669442 492749892 742202431 569998555 418537619 225874054 405197819 85006438 480182848 311785520 980222688 886155120 739845003 618148708 181694797 339526292 515738085 585795425 276000171 751510248 447662451 950260929 830068515 958953876 70584800 707866958 67438324 846120313 353139329 391050708 929145609 830998259 215891545 621652189 277015948 514231408 20034154 31607010 229629594 574334468 196764969 915870900 680392668 788809176 427046736 849075827 304139850 509434760 240400890 289588135 880924238 921956668 771724703 556233286 377194148 272369004 357253769 944929287 980850070 185962997 247950897 765561653 915716 224150904 271941458 809000235 674639364 608336723 217932525 526242149 936576991 482885449 196820663 90009889 228731289 419624720 671993716 264705789 849996859 998392069 914636373 700121173 898403225 729791371 744422274 741720305 742545024 562101725 593820804 725085105 852054462 176680875 90536048 739896312 49178610 48754852 207257063 415074745 715302146 562531594 132643699 159655335 814357420 231565763 443988646 35083621 541191075 92765896 815530939 167086279 960942805 86028379 574005735 173992458 755931008 607945126 390149236 14144989 332291565 544155612 120851517 63629326 291653209 632955559 385561537 326653857 611570331 416236984 524008489 3435686 16440767 925474240 938942685 766633728 757071541 41503025 343714078 819200112 332237197 459455332 694332026 274324152 533520655 547268291 141441159 965490046 369500664 438052998 117446728 273033324 895136620 564329570 655224471 217456525 629205674 480967029 740369537 356606429 602339851 393297612 306849103 718814113 961649890 106902769 217449207 550787119 537102321 244037564 590695438 323102689 653981185 555395995 203353787 582357710 931792100 438912930 576649385 929327259 54151594 134456954 654374346 145435473 358283299 437264988 966266444 352371356 285181221 447483466 88541239 657065726 419924968 813440294 40087781 86494738 906372510 946453722 347075537 840657745 104573931 286984351 863836136 758978350 908067265 163833067 961550918 892298635 100034671 648319801 775550400 839493886 999030065 424831439 478288975 835748684 455740678 495409535 157549218 752266515 154427505 2595415 506367454 220149955 692851492 592853444 191155775 634960379 887113203 107348140 39789099 241509591 232756944 732076391 877394821 280257465 659971964 682201341 897774734 522892913 38468054 847150704 378187801 620165183 739438380 556654155 592808207 295986225 898631728 202073399 202189528 92361325 503148519 797105977 961651312 370824967 250985459 425998643 529437087 931794284 610124284 205263967 566564402 634793112 185479444 369432006 280010686 3689555 595088030 684623393 281238045 60944267 859624154 670487460 300945687 456778343 219644468 621626893 264945534 634776495 377109225 638654878 152818882 507985738 369617550 875169679 790912306 888118034 759289029 772136838 755384990 966231401 661357644 681791843 862401911 782414721 164015314 286800323 711479567 54292099 972520237 463492160 672058366 6181844 22905247 760703670 340427234 411257393 360498453 352532426 158571639 62704584 833655195 961097007 716123150 503692344 70052493 611616556 945966256 913690185 253236186 854010849 762995709 411281901 935687710 520680417 832635375 142051012 857003598 959399990 297201968 912080826 867483186 602759215 761272953 299034584 115942327 904406176 83137946 207686141 484650762 4658612 152353182 473088339 807378396 809159083 777933105 13718202 689381876 689838407 713320315 590569613 939964632 95031372 175407023 285771383 984233711 833786399 626299912 654321216 111755919 388995933 614318653 141608727 11737589 512804441 411303465 654127467 381952462 67635264 415249104 213651594 191284648 281641630 940649155 536476363 47369670 919629965 623160480 670031472 559969787 8217840 119919963 769603889 309536191 50318445 143863120 855876210 627000901 424654935 80692348 904322191 924260033 582335990 423134192 357231096 39098699 625032379 327300749 87370853 723498926 3586573 77212294 208906509 958937804 854507312 424923722 432899908 85095839 831581315 805727133 293337085 886952610 699807574 843215171 75245735 1671463 943090136 251362392 829538727 897111998 150679518 482124913 192151227 899540278 17018611 425425435 982032228 231612755 874244194 425122996 248655617 402974022 616715922 812990401 844197878 325540187 802951452 937831880 240152154 581652629 533885641 583764755 601312686 217295638 162627002 517683459 134802629 855595821 144343317 996669481 998749108 953206951 711681066 126207827 749710873 505996881 161835158 114891963 2128643 767891566 634023987 719974431 24494833 478934124 885680970 231356431 567920509 907536147 87239725 850571201 294345834 949125143 79634557 287994383 722498461 492475842 678399473 926473738 564968287 710323435 639462399 444295383 534798919 129328594 15317949 625219540 753564135 605672788 225871917 204938555 948669168 452152178 159585180 594314574 369810208 310776263 393782197 63568381 49518420 386065654 147363308 226555844 958860507 492196826 981749127 467480781 985475351 904016191 264636510 217790095 226208981 87190838 453493108 865387807 726564944 897231183 168244801 821157419 891688576 798775199 375804081 736832554 761158697 482439324 37210730 614950455 964973288 961454903 553260507 74388455 868412516 947343295 631150605 99655704 887209593 946339545 642523572 377253571 681368225 205684247 442478187 449012290 329171334 651945918 777350335 916245446 193845449 994089557 941724018 1448738 960811575 502584307 949915004 485766652 321657628 794370515 84333034 183286554 107087380 342221385 698318243 87377584 318545229 308089826 8783128 157759967 252682895 677747862 877644646 688569846 420882468 50411638 152356443 910807630 707539116 732153797 877627894 50556667 902411389 232427477 306463829 706313141 387608683 952505947 513651742 277701360 149216200 448273250 15228610 680501796 129418448 963566918 882793986 552578919 210679901 857083901 8240428 953159182 62819589 4006803 17740687 167977650 143386595 422679879 490763536 759703699 959356844 118700249 571310079 965835240 589775628 136091863 441820872 279454812 523064386 154399207 537983578 468498913 479383434 563680908 520344047 83215790 767503870 733363509 828996824 388054421 78219952 846322694 92428381 333218020 674859363 601067933 417102260 209394850 294361865 336414342 340606909 420001951 601254675 191495936 702553479 926839663 753465564 66523004 111559975 386514639 273042497 121723783 264230791 484041530 337171273 612527547 789521350 555832644 289234851 154591368 49321390 97190333 436667673 322875627 796102219 802372958 353923309 471748691 591242695 245843696 315133374 383739371 589694368 799328514 571006966 928702628 615532091 352772622 744327687 571022967 168368225 750981436 140118037 88490916 75286241 429926821 121475741 238289132 399364298 93324767 897503609 273533389 778525977 160706788 268764401 802077664 303677172 762593225 708980721 480405976 551519679 285191162 33296902 721551580 910094767 474055542 592399090 207749674 244879777 915169998 742973315 598807072 883169621 222181761 427470859 974063953 908258369 29000558 878063302 754611326 449737071 740425235 290652090 999414568 911908301 319751618 809792962 141661155 13609346 259133449 668047130 40749576 668493594 243284773 703332463 858517797 114740606 286941306 578456205 551990763 695711198 485405817 988584564 584012110 954673553 75299911 544529149 770144816 308425099 353016980 294990569 454394968 44213030 972054062 767733327 590739708 532972428 475485075 263354236 993843792 59869640 540293770 231450869 956272771 529955511 592332943 811703259 212918306 509318655 37783435 775505778 242080722 976902732 593375524 201057169 60472325 158407811 463253664 826200149 846898642 978957829 501004250 611055695 913124499 593896102 929456815 987120293 171780225 726958419 537424264 605091210 299313075 184637397 148687326 174536300 581507546 651543868 888977294 722479222 659117940 112199247 272075635 35915655 834293042 786230479 174973802 763677691 555703422 590360374 979864000 393120128 536481497 280774602 927903776 801081965 648371839 346789265 570555606 165304795 184147821 284874704 1380930 148223933 76044710 992106063 77104674 820248916 600986368 988537931 912925326 509033084 191088517 805230521 273767811 321566934 384135392 323022662 28675989 482942799 390565681 330518945 31052960 602331553 736922748 105979459 76942942 257446674 941406467 633746649 341499179 557793098 590674694 75193009 946261123 283260959 986408708 975072176 615760347 954118097 395898825 227196218 313636081 531468495 606852375 624774551 269263379 906587006 479223578 890726354 914010659 850843373 443000551 973819846 369736448 24118875 741911438 338203969 416408442 23635334 133334665 329580537 76760881 511042271 788451448 241941973 240485645 112070437 253025091 166673832 426257482 998783518 982868679 735445898 76436172 830515642 426625109 911848955 33625982 537826787 190251416 957811105 609242239 626695778 813313903 845995889 940768156 796881229 260156958 210848149 888617919 788363203 559320701 886718548 854249686 245882868 601552446 849169006 773896934 463192911 812753185 966185085 194437340 430869230 868374280 79057842 5150370 155481101 387945101 21877312 701347306 543309468 310210817 945271929 303963665 181498855 409307236 874776488 904219297 204596092 221512847 954646978 740841534 44607967 33939258 39705061 218435114 703568143 682785132 185656137 347465679 680061101 808282399 829195602 138036190 719471696 539459717 676547157 374797053 119971238 227795673 152564724 58828403 945481835 814756727 673390702 437363431 760562060 232918978 903508546 452629340 162474608 294651350 808188615 792470406 23005798 913406812 828864733 450083598 788549222 444003703 953340504 3140598 63364868 991010935 94530077 79656012 291907403 439713955 970246877 498640557 120104768 661430088 576641697 888753023 466429240 750661588 168752776 378465637 49550143 627598699 164420616 602590620 318070567 881178809 677861422 195320165 789169246 345984653 613179932 154172603 163737942 968166166 677663795 439230798 701369714 589461284 916836566 516767231 253123552 804730335 681469910 498558847 986143855 388809648 445855997 486887782 760866498 897969863 116836620 483723027 671690657 952631235 131074982 506360452 742250985 575779791 499116443 652953446 543382406 592965387 881526404 351311268 627005739 982743764 412884106 10950181 441589868 934944787 542259946 957525444 664257010 487131748 77088276 166378643 701999124 644365576 455921491 618624982 65630371 285515577 398164230 849983082 979327435 617408400 141458055 961941584 130379963 10202345 413729409 837366036 919367895 577356661 740267833 995055411 122493218 575168608 718744183 797001272 544137642 898482481 780088996 347785171 879483525 369723726 525279888 627102215 218773516 819096108 52098230 603026490 977075607 965237888 816379601 893100532 995682007 918657775 853899108 458820971 113144503 369191229 913013921 396509749 131918146 781692375 357598947 697369194 406552094 382589350 19993138 220597972 113611607 251843402 912412849 437276266 911844852 345993408 862442960 608248085 144282738 845767385 308649180 374809595 264775985 169949933 648045657 731937811 838209457 449224381 935247546 451309979 337790229 354470771 365446998 667280456 789477975 521044722 479474883 498956581 876426526 226931215 430201459 411568425 977676831 510187770 534908459 553499544 710119710 988181375 374977047 660029150 563729628 871509923 939672765 148289294 158033520 391681278 977453987 174986337 559039123 381467176 847727774 101131230 567030273 694856074 546386992 471075137 919066849 27644989 367964049 266851219 374616968 441569654 879587774 815430195 828099964 669664346 330436273 528726219 278312977 330318150 122962799 585339496 559641321 181431199 502959402 130823938 517695738 577741995 813216318 644986676 771490648 305365272 571182830 758706677 106484467 788061457 412827248 624245252 559846116 580163132 504818981 485569746 904510984 275416596 841177234 948284978 104826326 68085397 982723601 985023824 380655513 817481185 879423649 153376743 410239290 254902205 290567559 423303565 707690690 53801598 469261974 671002527 712449861 313507523 162626513 872920967 691522907 817291038 767023639 483909938 287210414 554017039 877871867 78431119 802550132 164520642 667342344 919270808 156674579 68282416 987208818 753256634 829532189 180763083 503582273 842783057 964517860 418898858 327095343 841216228 873095068 870507863 380763457 778703374 592379661 406950937 81012433 907108127 234076675 202640942 274918955 162922373 880161934 133070568 841061329 804267842 943598866 842156003 592831015 468065827 836383045 211201997 732457166 696723926 689158655 852578719 112075406 631778393 678198216 322539743 55069323 146314265 519131147 444693329 10394931 666011381 163318810 963141892 686138725 34667182 245752969 552066452 81104361 98432468 364383378 30455637 815082024 597796576 942299970 703267641 213401834 634626330 298290281 532491841 368242709 925263023 924398275 581825502 690545683 54596448 89338882 572938535 962523382 163622302 281985511 145589700 445634629 427261768 983807372 974161116 426113136 818368969 665605813 526346223 746370877 14628746 872523217 90433687 450219436 921447589 94993425 218167199 357569562 91134975 573969560 25734608 741103113 528239735 669105435 548190368 579015721 615516406 327275918 860330086 345715238 664343097 781900645 823884137 596624424 825102866 573088338 340656433 595543557 246767740 758437532 155546898 950728829 962887834 302591693 375929715 982688339 287390468 415188006 670158099 988861208 279681122 167691774 779551346 882839988 59073882 307150332 765515169 715708050 348145353 826820192 154265727 169022836 916667669 143094832 256824999 207116985 432626081 712960847 565341956 977433878 583291220 410653378 895131679 97521517 385567993 493763863 573468988 113154775 49608624 193426990 66516073 382036281 870506249 292339625 681610456 825969360 800757642 896765439 805341583 882578377 927038646 921475063 996381012 208855127 703794904 347409936 827380195 702069089 827935579 265736705 497513571 253572884 544102608 258921398 909538775 618169345 518634268 456153410 368003045 813553658 735612261 738252095 477324766 285814698 984672305 362295856 689136894 674432432 862271488 343152664 883620345 657873026 282645388 954421230 883965817 483007918 814562748 739451249 950169787 520541982 29058428 673323530 960008655 804932696 485209420 774981875 591875162 130654583 902333871 8099853 330109076 660164995 568279528 728352506 484681500 233616985 325083112 961851745 704154940 758264800 32471408 512177395 17652738 96957301 881608935 599407403 306951983 120275214 284508765 687382730 23970580 422492240 366915250 618956967 389943038 992406322 975717704 313073717 124541897 731916055 662503687 616247521 830484641 856178258 883873486 991830272 443193787 903900694 503226693 85996783 71587981 609208228 99339863 307842818 271896855 935888206 223509744 367168277 384756869 691694614 981777031 301159545 904048759 491497806 637687665 732706711 817133845 983534568 72615263 941042491 675694708 691048766 8291328 50725002 806637085 112718198 890081861 928215540 714122604 413747449 471789236 608602037 116539690 858961205 286110662 868560376 180960563 386504893 333569014 586653628 15998687 688471602 875284780 440856089 764297339 561776039 404447177 541238679 443573570 786807529 697313757 803465081 494155792 932137678 914328957 941814118 192037577 944556569 682273658 16168673 905827373 201094830 338946617 500339637 491420679 75830455 263567552 996963415 645939675 866514927 40675494 48159766 458307532 887832671 698772256 323549509 145167225 966697129 987143044 332286086 54484730 225678928 337866687 288307008 655538396 586142247 299206735 558271837 419325644 532779410 286878347 67972408 427733994 712818613 141090684 315487182 254787190 532031349 619924279 660278811 408130604 839181420 327828792 309024149 977599716 476928036 155187806 647082083 784885004 611000754 122273911 827704972 208641480 277326280 85178280 64271820 959357459 269982413 590498574 921042407 109366508 514992302 211392850 132748848 306190695 937272354 841936007 18158931 482339054 395821946 160422271 343856089 235770251 842896904 631665292 330971726 503330787 604238006 690577339 456212358 252456201 276320367 668701086 994700809 75006899 424349331 569151737 369047596 176674280 617453793 834367318 315104983 273777130 505700106 889453784 468800917 728123729 682143082 183598982 460309236 791756530 265957496 685037949 919935010 791001431 252504967 989893650 735491706 290718293 93917196 853340411 470441190 428488668 570777107 858027175 440160265 733918030 864754584 474902158 709291882 37415845 871742377 352069440 774201762 228164143 174071110 940547477 828554930 952018471 383228326 185495225 69157040 730462688 130758814 142724046 997971932 933032425 166434484 475864678 327906118 247130375 197327945 163284190 639102705 667492538 235931612 938249525 264678221 670294257 980930286 886850268 322311071 155084118 875577637 598349161 927731764 231122632 16029105 609962373 906064603 128849867 635693715 167853738 94714041 859071801 761912849 684839426 270108983 480667704 5560455 981430093 788379204 10399523 634002867 958166690 77542892 323457163 39329253 937492334 649117416 721640902 114048670 580335404 730212982 672860070 944527243 298227072 977458578 149453629 965265800 698378256 264041694 165372707 188390959 231493063 39623234 899154992 773149884 721312321 207853554 399612856 485382735 970799712 661282165 84292428 364216439 983578595 12640876 395600480 772488027 71759985 401135691 348197234 632109298 224051466 404861285 456094595 767297741 925168704 556622713 150624142 126073391 993145535 679079123 601612982 857672413 236518847 74555835 424419686 22826961 976477877 999855274 506844620 191230971 941594046 161798246 925052283 127810016 673008803 116934987 654262085 419592731 335820423 886300937 47171566 107390432 337436002 162809901 820539611 112977828 445234578 785510883 771022472 623423225 548052374 732094288 283786542 967518490 845266361 770565496 328865293 386500431 808082835 909073338 201204670 108858932 834469044 444737626 382768068 643082791 48636233 337509578 335309935 523326049 704687085 948600550 133429129 622694174 311939693 638692400 777129635 233546041 176668649 299658050 726041771 982254196 670589901 632788657 534393450 769217141 303658236 365706678 933636837 871493358 289494398 503012250 398692800 659238508 68356951 748525299 126566701 709974645 757264578 547401042 956982619 963805390 348217208 930961567 417939018 880281430 805404777 331019966 310936835 476665050 446411377 199344306 784217579 48715626 342534061 956895655 491445766 560945389 977911286 819077777 336526164 754645555 608232731 932088838 579041749 379465634 522534558 870130140 314303694 624215642 532178719 33974185 867341358 415604749 250005300 898372659 703102878 408414506 696603561 950196852 736772802 692872411 365156852 464507001 817109740 107204450 237825148 729639515 551369076 253106850 570443693 154170268 141544124 999502994 968716190 527706686 105743655 582336665 699101355 530742442 643654845 687972815 832414421 981924815 299540302 750913325 435960759 500529772 413013647 549548209 251537188 142997982 500048060 921694293 424079328 739200008 20409986 702881915 977715809 21235110 904187897 958913278 327081725 886555097 173300090 909957672 878118833 859219376 60264646 940937652 465921478 295586983 901100974 283329675 336519231 95869655 132577342 309095541 307245266 732737583 965740775 838749245 596350904 304918897 918083892 592647928 666441440 862591715 841392485 916427187 107525578 485416626 703865446 204307130 407746852 975984091 484493011 897767884 359102981 501651544 778026326 393750256 850357958 310218303 879123936 459490744 166410559 582521037 278200479 11213704 369155977 169290058 652825882 98150584 981745272 529364857 174759686 902224835 392471882 231971530 544939022 873050169 212864360 581404274 608123208 202442667 216276736 445400201 414603269 879860067 143515878 858479125 883042975 817697774 576228890 535084961 529283456 61289669 909921454 948054658 892056741 393893753 304708579 94824116 762954766 914602776 232291318 959595360 547764827 503765715 967253181 604589443 57934627 21526422 427509980 633774764 858364313 858980478 436360850 309902765 433824226 583332779 81700365 833154983 510970811 850115765 49217566 150464412 473388989 207497083 452161939 492374284 625403751 515640570 9039217 182899830 77666743 236548621 660663917 277337616 498971043 800049484 652630294 571768602 22026648 386273810 520159837 232553985 927155335 891814219 622886103 644579623 683325573 795915060 73548512 35699422 416179300 941533603 893431873 2207884 930994689 912723645 672034005 747862039 402250981 205731516 760845197 523295646 37965049 188088279 603540462 412725500 992395385 211319020 698816045 955179169 132209864 865500881 7497220 167784003 462077042 280289678 131490533 768293313 256664464 783984389 822367426 634782438 715613377 691874626 544429711 402768153 795687178 783047747 763654357 973224384 320442089 584858289 525541799 302618610 894204553 713769498 101799247 302484699 931924215 909924464 619022974 56703939 698866555 231684096 941997706 126125574 417345527 434296438 621689894 463103358 856486671 590491244 407696686 95997119 706118929 674022802 934227133 568569019 858758250 91917606 22904941 28078371 754553381 464846457 884739856 209192135 765163422 461800270 22820466 286064206 359743770 163984477 394171554 428953875 73809761 375311431 808798820 152488010 77966403 338734525 880739080 349919775 536114898 342387713 644918353 796135711 485204284 608991975 547705142 193503280 690386271 586967175 939827458 591195564 571010235 13152323 24793075 461093396 707006054 671199168 15539081 820605249 415606247 389342539 172140023 839048724 672613007 925600214 266634550 150381870 485232167 161252379 892193707 762599532 208775012 198904877 279389291 690462084 814245677 699673349 831427259 248746142 565271919 53493321 823281456 745947315 341926029 244295960 71518704 830866430 627512247 48149255 721187572 603340261 903232333 831005320 698316023 188438945 263012275 26565369 14130013 313239119 607230955 972060960 27827403 615160609 969166398 222462082 184534862 989863045 492547073 488976030 405431627 205964826 200142926 861913860 926670592 663427665 50940128 242406168 863799039 770745265 144945794 591114392 676186971 28887231 550571780 879893680 969193207 575238149 447144004 387917961 831947420 444862531 992630121 899819831 370084968 624146401 205835547 796491968 727190266 970947074 710007797 955421345 516177130 491979177 692820546 329710817 475717771 374884778 731259962 210983109 983681604 824646707 397008044 459454992 913165255 500049545 374119216 124108457 714919609 920816256 3539177 201941680 239693591 378060997 558580818 363901236 327119710 872367412 548234302 152892282 47253437 820330450 72694928 527339968 677125626 291710827 799192713 705794648 671107603 177099285 659197872 976259054 245437512 2409067 227390408 291011533 538291912 282513153 223873083 393473788 519075057 141622830 467933982 874515242 761451515 378567746 758002923 658553160 934377009 378936854 34885597 837099211 914681891 657621982 260019864 136997722 960153635 93593746 533054634 748106162 328217532 648556117 39209655 234302259 21620356 430740048 862042117 386892183 791516214 272026583 570241466 895539990 542159283 375410982 916861228 753901953 895808897 797238697 357124081 910075653 165337655 49864112 228470236 636918234 537681711 113224674 550251612 231900761 987007558 759773430 59258479 747647109 203532923 663468357 668907421 278766108 834409685 271011519 751099066 984262784 152591905 797541643 95912875 915446634 909517344 245412935 745127941 400136774 267961410 291709449 824495999 966231477 203421997 563337472 709721707 525342333 911546513 796941514 55138874 376286245 856335164 781970659 868789300 775374618 18272801 588688993 100160312 158807754 66162995 200980230 11393617 261537281 686915395 935739007 211997580 227668157 131302897 818179482 755679745 66345402 53975377 358746052 689520118 486620493 341203604 293232405 255857984 39069669 138435664 315126697 650792310 582758096 867997616 604505573 509887514 477343650 389734400 974434145 752721871 943283162 727009639 847615720 861182580 414852153 839177071 921319436 30153815 192986717 297893660 604121813 205430488 781482663 96651763 374179977 502976719 348328624 198058139 434862450 638763431 685333860 473775146 87016100 92839086 364837021 350717993 834903189 608828441 997055362 326862744 639703592 110438983 141570040 307680811 248772500 146210937 768784979 400303247 694605248 673667844 479551219 842591154 844196224 687419980 398061483 827038900 119931645 350896544 32662879 140273399 332347182 711058186 728200610 309176286 619824809 506016842 990856930 526992843 876241823 113211873 237274933 609769390 571366648 610304162 787883663 182845545 610079709 844747465 324240175 691569915 161421687 634937731 668143236 10597537 557673386 849645454 730392792 108873865 505998698 572369777 826166739 39136651 438348168 961295770 211053257 396069631 517686040 837252984 581366332 405142856 79894355 66623657 250288654 70815361 587615988 690000232 370524866 624090687 615637982 288309925 426002264 506240866 411610399 857210796 15035439 541398659 891730810 235913101 610671554 574826835 457575216 512126709 452756782 874151428 794351902 407245740 422110947 911048421 737000257 571441628 830584491 395849033 718750026 787616606 584560975 631415262 262219405 247598359 800614376 224742132 568133445 998682552 374840277 198933231 80667798 937333213 12746007 432118524 838987471 941472176 179793043 953525084 437699546 662482770 494216987 138250375 700396537 492435830 453980013 414016330 641963514 474752930 141818740 911179014 561921295 415623236 267725149 917383633 919564547 436123330 785905204 975880324 720592387 690538894 54886695 385053671 662618981 195969477 429118934 715693830 20725877 612521515 704090543 768914526 655674696 75926219 178184728 574931652 934474525 150166919 214437524 437098396 656003766 294123748 613703572 452553794 167045061 101400160 621062090 746959563 839463375 464624496 857032217 399293180 699991337 411210021 905471649 224664547 489764441 950794600 167655664 131219423 282069487 61559128 164894643 511102524 285349031 467294166 702175737 214267678 806423759 479375940 427703060 503620040 352927611 718991592 224054544 57125039 412339825 19941507 821402348 932308037 654901713 527153866 731985164 830589290 430580095 632827857 521484874 435066970 495704086 789474334 730764837 602312395 857291603 585268239 964196106 583653524 194255353 741398427 888152036 817401307 84431509 660810195 929381882 783931832 486069984 321733766 619213214 627234904 226751046 394732302 40774791 579047251 293683332 928011655 542378709 567046242 572207358 858404610 425084385 182333821 212611921 469529280 577693387 766465558 127033535 660898355 728619314 641106544 907744661 290349232 89177034 373016456 572812577 102728195 335981091 86429679 475279999 953114416 676478361 680703073 862346054 449152838 969152462 118107730 23534523 2580082 560041405 411496699 280638372 759375166 668761115 590022645 593535105 25208341 104700429 220175624 91259279 623520828 194639941 294879975 277871348 493568960 40500954 260938474 524197663 821830454 91319113 988199599 771989634 854818332 832634376 240729079 732149729 207801419 569017345 520037771 166405005 176466206 865040122 637311418 590576813 601266503 736351185 701358573 398502476 754444258 701542676 280943120 375684740 859262716 587791751 288467920 363166379 766460 46335733 964422221 793481801 364581243 379432375 230520069 466707560 653811473 147655094 919009933 605642230 113537561 240382831 474137985 834462273 836243412 973221768 25797774 224706383 515032344 560370791 426526875 413717268 559162898 843349201 175672654 7274752 374418951 431593347 558999332 684763807 410760387 900830688 253206857 799401474 795572720 419040730 975934064 743997229 5881584 220335402 961312554 606011616 42366507 642210323 486561116 652759292 372909026 146233217 781949563 213989114 534738330 317031802 45622291 581445574 943179886 508823582 645959894 130864471 820289729 534909276 438621953 697657989 564911966 186428689 647756239 564081699 435728002 520244601 910055309 659783208 119782004 706817227 598617370 442554824 743279163 595509869 69493466 72677560 40504289 258577241 920239874 425337375 950412336 859940008 785033301 940376666 26133908 950810988 558537904 430308241 182352796 547609463 191480509 441936112 277280295 58327860 891301338 883966404 809184190 641827851 772391836 149129949 35014019 211993051 932827225 696115450 657082093 569169951 842673733 518639831 248108643 765279303 584508102 142024100 974448675 149552974 376624162 810101829 233729022 572912941 798780940 717358339 545831121 188810894 152479809 21880698 902358933 550565239 803238264 773350146 75447525 71386761 215860740 865287663 741633823 342134823 489121667 574775004 890542293 357540178 26650290 371238248 552408308 123391798 710448037 271001705 118669341 487326736 309799070 373159203 978730725 314285637 45164198 801505645 424196786 8244371 446714028 535437548 454675010 475453486 155587586 685565100 833633129 602054497 716578823 199627285 866238139 132233152 376936341 33588270 303688529 216391942 544596393 304545734 832288720 924337005 82401206 383168187 554880177 546724942 338244082 318182085 218809154 715336464 439183067 902967170 762343476 505339380 813836255 624020142 871066446 72555732 937229989 713969961 994162693 95038734 139415051 924044766 907009030 277627300 959271866 938886749 362504145 620020046 391449890 213227221 806031446 894144265 889522589 144979516 506453457 132098363 141545784 448567494 98178711 249102991 263199289 533938267 256351525 445012437 642438401 933390273 306288559 94133649 852382016 85988071 182210048 349800225 730894990 746715488 578852182 981636391 670924966 182632393 504197276 126449437 506655502 25003951 4783584 5917145 770388296 297004794 15511185 785289961 134287208 924677378 536960457 992695043 155442546 923571095 73564918 124685816 913079418 727991621 239953530 213002343 287624676 234501523 579275790 732559426 351351805 949810927 336809374 998059630 453029901 42839515 478552153 211403080 173199484 12499605 185266793 923365944 848223848 435029654 649622435 782672793 30180559 590996165 511180038 294258983 107680588 71764623 157339717 158015864 540363299 710694659 216305978 118629240 815308858 897075088 357087285 590527431 237532705 268280620 731800112 388494279 697012188 824639687 227190108 674126615 168137828 485255976 587138421 728810695 821710620 693917198 799631141 111403493 783698834 436801829 118591739 499146341 564003908 218616931 904526328 554520331 678098255 548920771 23910276 579299489 184836092 385964927 392414000 603039890 681721054 150274148 239941825 384695354 763563512 252346685 748908639 944447249 480289724 421123891 724481857 57077299 275065976 152226283 654590058 578256404 333870903 829300506 801924009 667058598 41498931 878642669 711307123 616173176 502368203 436349810 817256345 678676045 717193959 813755988 210143575 885376010 530625377 111277744 600545630 780663989 120332980 821579063 284836265 30233853 552280633 217399527 26662385 739518943 862440395 204094467 688630662 432438817 478675916 320287888 985760501 497977319 404172647 986152715 809396517 354042575 646987950 560944287 282468514 788308933 428719123 252967294 525023939 838192211 526468303 891889597 130329583 587965997 164834775 18047034 388271453 75354187 84832794 604032255 595086410 547490887 937702995 333055236 957100463 260054053 766117031 134249364 813392038 870442591 447841143 412720819 199107497 249533204 998516471 321497175 687408277 885386097 6681791 505045473 371697620 850046074 41858393 568312742 568127349 441281187 812229673 248038787 587439088 369390137 291576867 491208984 535278105 663971228 897066486 606252406 182965721 7356215 343319972 100471647 743318585 403618503 804214912 372494045 126978451 598673518 860507708 545826299 256828062 763539601 405211312 988595412 82055846 59038499 143319282 644988994 486662345 634735681 1737710 827965592 721924392 74636963 957144922 690462769 163239182 980937542 92271854 279623343 190173594 314752867 61965623 831666215 737072376 698932599 744686096 243489077 361050965 530236044 856067237 32303258 766902402 431571879 17496461 254159474 424559716 920539197 792280287 33340973 892915965 843716032 695311857 961369392 146913048 578376045 879224821 151488520 520348853 220763759 435314834 338761610 841062997 282495136 238182064 938229209 672160715 901044564 853758585 566566291 394060459 714981132 705826483 57402217 59468129 592305771 982831114 35219600 443543631 131773141 537309740 318848270 533842640 15613011 721568804 482563483 989362391 53003323 464371227 293590738 429055534 830910625 527754035 224299386 293579542 394939469 901655670 555692742 264442923 620754649 641166893 931987144 140724983 450390639 800110253 992766765 33640652 171717135 34579216 473529900 406560491 419431308 569031742 354349080 286622919 608831593 487235351 413248934 279500241 406162403 379375 939807662 22934656 945581777 853879711 59415121 84293278 220770376 312700652 719762590 630213881 259435074 203474610 528838818 12915732 273499865 969476822 383431176 620817487 373360750 324886388 507793790 735778620 313707518 440884945 587771886 84816697 673637046 259663384 585524599 919307625 979892045 19250451 215201538 482287331 359669963 705806621 344202824 626828945 828536001 671162954 272403517 998778504 334553068 490152554 719053702 664504592 188017082 592903864 387436765 211741879 866165418 922247193 585444367 359785727 649150593 177457646 236060114 819951992 5747399 197898633 22220063 676330041 268372697 137133429 957586935 263903706 427864132 904320847 304219656 298944588 243436499 265485892 992571978 689564841 222644755 18056619 138997196 941785049 522576337 708258299 321337742 257101025 648102695 101321658 271937593 599918860 743129319 765006714 587717019 665227251 705935111 366998341 763256156 345537022 177787486 957254261 367780748 893023160 199261603 818361385 638992893 874194398 938746956 91167379 161795690 1203639 384613623 244141624 515252323 508143435 654406619 737573255 165772116 731445714 549255510 136585874 160657603 366218066 262654223 716587571 347736586 31716211 640012644 650274070 279238192 404814821 742014062 5909709 988572068 155620858 293557034 731322017 337834355 555549972 417747716 870560737 878518622 267798791 272471215 137530943 429733310 976364682 144097766 604911430 365102102 803058653 808215819 793313457 567532892 471420749 534867984 477310136 843670028 426712427 92983548 946636983 725811832 472240238 35781264 469854908 894211102 81881683 205248928 549568793 595766746 201540541 112319380 980580075 548645879 650481134 195837823 647371519 806305501 793551997 307336129 857897803 285314954 513834740 380304605 226406647 223439974 952524933 595106164 800593401 875912242 918179816 735411275 566455897 783526592 282200782 654531765 681194058 301593580 612934950 955372567 495534989 482990780 120087942 788865434 93499041 216043347 983673478 439217871 277037804 520616513 113600802 544605233 919805742 934323002 856228220 751348780 443415531 726638185 29938596 601768841 831959184 169261441 340720861 122382131 659898895 195802058 935977726 369888537 145615063 935334740 516727736 821579872 346851791 108864671 846441414 848694391 897236501 409262619 794732380 642783730 996021722 176523478 113850212 163804891 849677313 829162579 484995201 449494123 758081441 777466023 629919010 767976023 871667551 945253657 647131545 915568563 433417842 651190544 96908302 613303288 916327333 851387492 770492431 729777139 474344364 434050876 966617229 268097515 597182861 352771289 69724363 296786309 240385773 428118485 98620895 985998698 297839092 908739145 846443455 290810505 430743541 212941909 237248927 39355770 977260340 977992181 941552600 582564181 198425199 965827853 692369035 449341017 182127017 142735448 665455434 992394921 180044093 126774665 946451693 72587416 555622023 134492403 513047724 742423036 203862376 132369741 158490268 571156543 106510392 242261350 483036007 378711214 898472856 351593120 526623408 464450721 579620501 281415374 281464800 870573403 420474751 981262045 407487242 516368653 213774130 487223030 860085726 595425860 845952640 93342073 807023226 307195670 732820653 754170661 570174265 594033790 584669170 832124746 74898680 337916467 518206699 331730320 649385417 463527797 265160330 288193950 658531687 279517811 782658773 400806703 517560055 468475688 958588317 634763708 866666347 367641075 569077006 730889273 758512317 766548432 296354790 912005725 187309307 725808669 571772938 177978405 802408284 90294030 601246819 50878973 277425943 260458007 811345598 337113082 776425492 350713205 322770240 7544265 806135261 169626736 79049250 52593653 634036651 985857240 899377775 368142063 294758717 693398556 363429095 588901255 212308571 773471250 39875871 815748709 789438574 395015886 739239476 469563773 835986986 9224099 392454419 659903266 764318669 223584017 931006313 371578777 237207793 529824491 714136965 439841746 936619453 597460970 861327379 959436795 924271632 751210068 491651023 879605386 880853570 571981465 108408513 925807657 536359579 765493659 169581714 647961505 966286557 211645561 911158947 263872222 778694594 264557445 763026362 247479443 75085328 203567650 870331302 729221212 493413599 511086970 704875362 301871486 523326815 715281065 308540227 697294170 542142348 643136929 444382395 746866198 980455512 209199482 911530673 652414319 993038525 514134331 608200470 951750824 924375738 299782193 724722071 33727041 113188709 295148254 614692409 636084948 419384037 869613436 856552765 127745275 696587026 300775741 552772905 997073600 754972877 898378585 201064750 147201912 759069468 209227395 488187453 349919950 538856038 154562855 209716223 933501060 488093225 490661757 127802469 2502119 499099732 34413919 859005813 169750841 513148123 902457924 488676768 123382336 757222521 357737858 42781873 217163144 80972744 825980422 835783292 908356136 52316603 825024627 612577007 460767801 543147133 218990894 441218904 191412387 392798091 638719657 487416224 497298396 877765771 558565526 596033199 861478823 761930915 951457596 721231010 904977650 280159672 239328092 16378415 419666353 485912674 567335608 551128289 488835179 568134442 255866944 616017357 249606288 853498325 279698454 226793973 567020160 546522621 556942280 506450712 725026989 993061591 239844373 15374995 930835164 362324956 212166310 106457898 684950175 278077474 606892527 485611621 98651937 836346105 192768602 184620572 817623746 856196870 931284843 454407023 431116799 497926256 930121807 604441651 1723176 750984218 549624834 831714235 838183155 806713360 599052119 588320033 854549219 233369625 185465960 641297944 261877165 542024602 92898458 132778108 96519530 47110044 704926223 519440218 87968057 140152784 738383430 899551868 749073941 535992970 61135633 976571735 116436200 603681061 307191133 53762205 64432385 691552476 816234213 327326957 462352430 5633091 10047885 500998948 763451317 3997139 415585219 298508824 439496409 467739334 858636318 655563655 453180506 639881505 800405599 281630017 401467618 919346014 79281091 690612644 348927074 490493819 65343276 333691851 207538568 845773809 760187881 758281032 240466553 303597144 100067451 823221805 339070362 355176947 573372777 922826532 255153850 401104334 771241546 445586491 992192332 744189063 648556491 423337053 683140607 911815744 160476755 535263415 829021418 3397681 55391802 541839205 914100638 676150938 326889011 71748355 257164628 28000958 105457559 221125219 543522364 458953146 53732770 383375828 489500481 14086748 813979546 158883604 758119433 767869823 99305415 896651695 483206771 287508425 874507053 267108595 698072200 170575419 59111401 792863771 192881862 37818391 924541617 283537137 664213487 630849613 780247855 473391496 549573476 617260283 108789178 562163532 485695432 798720622 529224257 743085684 445491411 990603225 978963714 505552752 287968274 474055051 254159895 831592027 447362273 116578530 519755071 401199272 320133977 559585839 989468268 695577800 115561708 49656383 981364528 804749698 916619520 403732279 932990783 719156917 383244849 422594169 606807409 798139965 581641303 795600546 603303834 379565524 59760310 115579257 813557183 486293076 367206905 37910999 916068863 453755792 185141869 760764438 578048721 105144946 598592245 689006725 27498753 582856992 190764494 4816946 481888043 960637974 596687845 642003980 87751800 182207690 309339681 178026014 541486989 864262629 678771157 231828557 836166946 475748470 760279204 852911506 782096800 723528649 280459729 769653418 322752878 863517019 628656561 669863759 173575279 373696310 908911099 606651203 724703771 485866940 57891655 554604731 750881509 735023278 522800854 627884306 939135737 260210840 504427796 587249167 576096801 705247876 839255636 353413506 919628107 284351558 891390025 941791847 564468392 180191871 626637383 400912507 1304562 476375294 571893968 859745327 185308403 920548132 581384280 549321682 989017358 569194286 345824341 48095935 727680981 332663020 481327639 397548593 685552750 581731760 838299639 711274234 715649555 771663393 281997174 235092398 853877351 121792018 978644083 366815533 911121724 688782522 596792862 982934205 883436568 440886425 157756004 318036753 196468602 573897588 257257495 797529407 771684973 153340910 240998235 115103354 720332596 719392968 836898711 453540909 201833478 564254908 549278164 677139135 837969322 207220307 75414251 140459968 593662524 574755341 194220042 835045544 888077877 292000135 878397565 646206018 605710673 258390130 362436618 847167805 778642000 719293862 280018578 854183431 817272022 674754681 200405333 66482288 127923426 564791227 688090562 708317120 716513009 170432977 297001436 353509707 237029619 742498859 927408863 600870870 54452090 159881321 591654865 833244359 803000021 368237111 957295873 67843716 742314503 74972204 809596423 567344717 926888148 694539029 444172555 35845332 66707248 287371028 246465699 117549532 995455403 868197351 187791063 362601291 243537160 617647856 403584328 266730241 873594542 860067557 794224472 873340349 591551062 336416212 500876661 699866064 688016465 683417525 170806208 576614671 587025925 830934700 500506470 588903676 577252299 260939327 805677819 164215834 650670541 699830520 915675676 899998264 601697453 517913192 261070865 917350033 395427001 503162918 364777902 880900731 697743154 161215226 664792300 428696084 274015562 149215450 927151075 261885565 46509383 155850600 873420681 37816402 406329805 45679879 952228553 953969269 887090480 317670658 589594720 269461985 103523436 396306201 720127182 169908973 716204344 249108078 636807995 857129192 260126980 717911696 662786661 306303231 186007086 219815810 734609164 601098277 585932470 292928739 4233105 431833848 545919553 257136050 280376101 434966510 548012613 417064025 619652154 167927992 634764150 380372976 64793287 202332869 229881811 901202452 796797247 949697145 83908306 309522198 845958752 283220305 732664536 881754746 69163562 634878738 482045518 862087177 205356398 221622694 157882083 103181977 497075684 246870257 248719472 227281883 939394748 739916702 337549724 197881330 126135999 552322693 267670668 789145667 221570336 998023291 782086866 560138588 211416861 622607187 181396098 539463097 522342172 704953003 486441019 993519615 301668836 388140674 149901948 615374475 888385378 681790121 346918507 592255620 572728991 688327200 213229718 596653759 273832219 404928784 483848389 565899729 388747378 763355873 376969978 543168465 562267261 188098826 708686127 208566729 25598703 374807173 81944359 893713982 369257181 677826671 250686713 58008124 891255954 849191071 889227547 389803311 988903340 482817650 363023743 29020252 822021900 5553213 653579477 853630948 406644444 877319542 20064898 328087623 327200700 786740007 415050958 669044535 62886245 995133331 114139303 290593415 152891986 868322121 1571461 593413368 361004875 376976130 552433481 911960466 615671575 683349889 278258607 238532175 811316218 266557157 774377644 52523774 693795734 904817122 659969881 755703958 291251761 99109673 123368778 556811037 160668890 542944052 53892595 426103193 297046971 687562191 35091528 699481980 531276743 582211397 451061313 171729840 96707401 276442599 67924364 422106005 803323596 322602949 353979685 783739160 888565644 311628279 22844039 523970062 342278271 327112683 411555095 464649584 924941922 136194855 37238232 5796403 167591660 8538656 614123794 319682593 368323727 782059457 77770502 980035366 801433381 841535742 270553767 580870278 680400160 477670562 515802054 741157985 148354306 94948600 284738125 407571777 251458774 709966624 524320825 701756484 774097686 608541483 581981336 277542709 539800252 736021276 956676379 939506647 432325122 292535551 906862935 16632008 229994904 413708489 155903950 212771781 765265828 2245874 162443890 953605376 481996905 209501943 14096381 752293416 333026895 114984455 412192105 223025906 351536553 771832575 168418648 879543808 953208335 836065356 576746620 251417381 779338659 246961852 972637801 311614436 626571999 599376896 772253292 209658416 627140038 584962464 906579387 568379907 340191502 240557417 931549567 650932841 255119098 675475884 523860620 787970557 350571848 195674932 783124483 572274129 128340604 216785312 822945527 521941352 538304219 999238628 947320742 744388388 456193420 656753541 306576277 363943297 914674827 576059049 590930594 34610575 126601886 839958748 558714913 705432247 269547982 171666479 732066188 964154609 558581199 519611371 120030500 793346620 438381750 535415516 692524128 407238495 128678958 604647561 599182167 227608104 24062574 380475105 512840129 651440632 6703842 937042453 354763719 175736772 373362903 337892461 445776690 604465102 876481178 290999167 159392795 980107963 573447887 201536972 283997267 908050906 907376700 532490569 50477766 583785187 160778453 796694083 730538586 50443858 828411769 594099255 653128887 95112330 974080272 628369846 491967533 862068062 336371919 753378683 60042064 216876455 646597277 189947515 550864170 246399893 234147809 57445114 758866780 257780042 137763600 349302180 196683018 122548950 203005282 756117337 580317305 188620546 34108583 23881251 433856166 626350432 971406846 272894814 770439691 999072807 792343593 549255777 887574770 685320828 411827089 407670590 280115993 56872038 959881696 29752355 648023581 524312055 153539307 889636856 988120965 557150952 671812025 749684447 785714266 465169094 250552376 351728067 499094981 359457163 141704790 575849764 374790161 6464666 547657589 728518739 423047598 575877111 68438693 810438291 723484068 150240310 777733772 238315633 405895859 731960905 239175018 189711163 680562441 153123591 570582101 597677347 655057810 652537375 375031023 767862241 623992549 872962842 405453679 1588958 539225318 281641503 278127786 11187627 403690115 734542414 280749545 436565751 646316590 873274529 162308225 928995514 582552023 492693916 581618004 646568644 818188163 499765567 750068228 217349961 26073805 314962248 602599624 499071238 80097146 965083133 73745412 389294643 839407218 445102021 261031766 729635913 738629059 886397185 985139203 955261268 988400927 591395029 699659363 498895611 564073449 389206273 810713717 206456883 184184310 736344309 990130971 488949386 202058935 998220101 698454252 620900140 72051352 593396166 149759477 136970836 203657078 759746182 432035651 454794134 210785640 13845789 747355980 154961162 306769732 899398410 359910186 38718263 656745798 249205309 31183985 586909534 945068098 261719225 375955361 315915242 230830591 202400944 786766618 394724504 354467135 453159113 355706671 106677016 292151713 906045998 98475419 376454514 716206644 394841648 610362143 960151128 986924429 914931252 625359234 919135800 31320145 940969173 474032557 272004425 29710171 771649261 326925590 948904690 531147436 341517505 953235117 572967125 20924299 849634926 967281413 584484679 906440348 767556091 675554899 887541228 94587634 461767297 964988898 510246200 564060676 65623789 996800 580580270 827884570 335452236 221829322 361155756 271323111 365093008 595925505 882140568 117614519 323294769 924291893 694607928 659361458 117971149 343493909 43683592 736112390 488485597 863096290 408259049 832586001 944668917 589021192 226039296 803828190 868025093 161073920 759089838 625768394 85417174 353783854 627045926 303541257 610312230 145181907 569262076 39764749 76674431 18896310 887148652 876792341 731393104 685040068 585532288 676102603 146060750 600656589 262649464 382658327 853456915 353039913 446565062 277866702 193960117 342846407 369653870 709432275 93290199 493085000 877554352 753237518 304469974 93082625 459074806 498218538 971957828 386840602 433703499 18004294 591786958 165420092 622401199 91237166 210251996 356271896 881761283 718262595 804791362 645477536 719725828 602873119 330450919 496600641 568584234 86142914 660757076 547831349 364337777 214561864 961100021 848457168 160303381 209021804 536919624 826672071 697209732 560742293 573742882 380452183 655705236 262013416 922325229 516199907 359952542 580351626 753285550 146771251 145520402 985932016 207180768 176552529 331839512 709793159 553121485 977795246 641292395 977433584 98015347 759192985 308837896 933521021 867718826 764898102 861391662 628581482 615473246 213645715 977194180 80679893 671630723 41079274 248019800 419749279 507841817 589358935 167933358 409488389 860412644 736472554 216557781 520317350 211575667 282942176 965609433 951035094 290447313 389316500 821924953 117244211 102327347 789411925 296372208 198156384 373073985 98146958 697359405 650552540 372884543 750479507 201184076 52446561 363671093 660751821 976049123 720679258 888566692 625731293 602160424 857276947 148738559 36558184 898604218 954400989 628311191 628397715 593773210 488717401 485637445 86401013 763774695 46357418 461976967 875199937 45707902 544144903 37438560 139799984 933895420 269005269 875453016 532620795 370856291 787667826 202572285 390002908 813776885 935178006 730145236 184599069 393926256 805311743 883830686 208329961 401227638 360276847 873424313 904780867 425230184 590254977 139512327 123815720 398478769 234574986 439342140 1423732 308335673 326548599 958141375 528846588 370925326 568347459 464110925 942883421 898358752 867152829 402441954 873221698 299424378 758281351 938845418 512698392 170261599 660049746 930040854 615395529 624177457 513196051 154414083 735133670 572924445 960000688 980487098 442468093 4792687 315274611 662881061 986312180 252458635 791136036 671402779 979562811 110047541 405760835 192955802 995595449 340065254 562976580 271736415 431958833 623281107 383299424 450066854 351635518 606898857 419314474 758576129 494603903 95273997 935916866 22739247 624015175 665129596 624490033 966011525 503026182 724739433 73203819 212493628 303132141 913842352 914327609 126161442 285243686 867955711 199694604 447665045 12049081 322005940 584592598 540600883 57266103 516795518 810720996 201696980 549694667 870155711 394558791 827961759 798432676 956322214 759788508 635399223 393664360 811782962 413457736 637236875 244433254 917220894 39324259 265656770 231837902 807536923 283371201 753791090 696571038 653595504 895090250 437429950 250878345 192055059 912405841 580022658 227181501 962213189 313039962 838649671 877680229 170360775 264204220 176816739 161807774 570844793 917331166 578386269 618844235 663687877 515523946 785371650 764666355 352592867 60893924 406833481 79233636 981835756 345412057 887174349 446714528 223108014 1765319 720452600 803197078 678735053 181760454 808514259 384444654 706102142 620701728 716378567 826187899 467690787 529820005 91735754 383540379 903934734 731845900 347416120 459301393 242706327 947629185 2843980 756543103 325149426 399003232 127984103 445000371 615496428 816370393 349112210 416976264 502847165 688222711 324894025 423998015 805426890 712117837 123951747 415911133 258721471 278321791 452654957 248170052 531783677 311406357 944818313 104113466 822842675 391783996 783336787 337226665 970213228 51288394 488808035 244008054 980012607 130940219 718795639 514318640 803252611 685515689 669627155 638207102 224594045 779953381 530271151 120091469 58254044 992370575 738272543 118761993 912929176 993825461 295210059 122140748 714452415 602885694 47954465 778609563 892837065 856474286 276157693 494061545 521521548 421087532 185656250 679748154 647556452 269528447 915813086 809651196 913510214 439315186 512704737 660446221 297800715 669269206 875341621 832404023 981149658 720313641 608277189 44677598 382122465 335808026 739406170 935563524 22045617 218232452 76243872 798024710 174422372 446650885 210803948 203727600 895387739 18213122 243879130 501056668 369710603 152708197 270493948 835538482 670957662 554171748 444416686 243484427 232150325 506632766 899950584 534488330 598833129 562270706 505092341 919569576 937633738 444072244 752301392 995093497 522991120 677295680 124275394 35759373 826563191 241425040 255283759 27234111 54370264 933937714 675715681 503466911 257545141 920663050 773636090 665306998 201720643 554534194 294545741 120708749 433303793 455180390 660231016 886530504 799835193 476452385 212777731 358383542 531644272 715762144 341035093 15480426 660766265 745507198 674024116 770247140 142019451 906784818 789618248 990298709 367577645 573113657 910088283 167432795 813185943 900663525 282669599 87711838 996533071 139504869 868441617 864800070 393392613 601541451 905681865 570708925 763903589 67704913 102032470 356620324 433540075 12840431 289874087 991030709 600055557 344543257 768677614 800962084 950744052 701537024 98266513 569483764 803532546 672941855 277273338 115659622 542009163 551994351 324979040 299240972 806986619 572283345 973496082 271716131 389122826 105931707 203709668 125255043 146494666 136228240 194993129 800314030 945780694 572244216 153404175 572490796 85596074 255170940 792713335 824814881 98110207 312744717 407514547 326171713 628275773 38947198 557949173 413167283 316474380 413167451 733945318 492888441 846348184 270117660 457191226 161813427 548540984 454577410 636437132 317960512 462169711 372807221 183670835 234878452 379792159 298558647 229846398 385915632 40600240 663862396 686845805 646187585 454682895 924237525 186217223 991986349 199617235 983571784 495457788 930936618 969955577 589620235 651140376 133273545 475711768 203273620 571459613 978367440 557029031 328460113 878124443 340575946 109807758 529099271 952331616 3044754 271970396 552468719 230727654 149296740 749639911 444628556 805345816 86236811 148435706 186586605 493440334 376540309 871664173 525104594 943819868 629504699 499340523 967162624 587631458 105551861 389564254 107240250 286791145 2008324 159995615 278444641 92911037 801867036 36611350 668290881 46080729 818413979 512424762 984684034 124386235 929311936 176887501 698400463 975366627 22882663 180021548 64258376 64459178 990598454 638432821 419936095 444327329 808740513 267307946 541040857 863471775 932789220 892429608 736805420 525718207 579983856 887684374 406819553 690770066 469624678 808555141 23173204 490955189 210304921 122081790 963375706 80763394 394769113 346606835 94371798 907930986 393898494 243362542 126870434 373148624 862557309 798450416 882352654 311990425 903935925 61028783 22008980 710941283 832770140 272448539 382365189 396658855 176536820 517007316 234191238 375860626 467845295 581189736 291657497 468996329 867983934 184898875 123773124 230593809 574166080 902823026 322481695 604728198 117491512 579201869 221788466 279492988 616445572 376696187 799743899 615620024 607339805 414306205 576599419 3091909 455167462 836447650 486520751 349408594 312417423 573764571 549352138 301742927 647659817 3743792 502825794 821985260 148342291 196626843 791624777 467178389 823696600 376791811 839015218 603972911 277031630 509585414 771209634 368798662 705544620 73158694 343098425 18830554 817347464 11146649 611322750 530146328 648452027 542100667 344034249 120969419 231689403 616991658 871084921 472025462 201109213 643235481 517359279 799375742 19873615 106491937 277103214 226300487 11751077 219847452 54767891 478542404 344447991 400040562 551045880 857036867 796946477 146467039 803877261 486922222 59406765 610631579 971410821 20369703 755915807 799182357 986637298 498015869 82035843 252526625 87398526 648958248 503411573 712133933 400513673 382065514 962948759 251888967 303326254 954475357 353425384 483917806 15242779 544169758 913452360 258799735 742082538 484788306 242327938 288094003 462816373 644676819 126136336 717054281 142219814 815989012 685679861 254108931 422238156 9806324 589039319 477330630 14868628 801877415 454096766 271129956 243577426 836012391 592327833 811021074 253931869 59321013 57786721 183430935 239607926 221663219 17526771 831785306 187082394 320996773 713711740 429613387 855786620 615480059 790556974 630615734 207825281 69838415 652215190 451013107 123677840 935025449 172540855 520870737 666198437 192059516 444148082 415939555 459926989 115357466 330706090 891121522 346026971 39189782 447657658 718821711 868339313 186345954 151339966 211094522 529572669 682964298 5724290 899575558 706516381 91405211 824758947 192040079 835727220 447244932 692636675 267534957 295054063 381465620 85451980 871391065 296306306 641905988 856938575 167664404 232082310 662994286 705407619 828822771 397961488 985524303 110477610 69226484 192234330 705608229 793175729 696460650 962279832 515373039 535859364 961949058 669574953 782658855 538018710 58287401 232236364 804285352 850422434 538733657 868739252 433581539 263661087 445906170 436977636 403746619 19884061 462135291 484391341 456555837 926165067 90283677 101586798 70333636 220103783 423888306 763615908 783334513 153123997 92841686 779291201 341515518 594419686 732716350 663760191 78681107 529707699 133123079 627180605 524106806 471715946 880971782 670107325 888204294 870774675 572042674 106682807 894490492 187582964 805829588 74206212 439289015 576778845 841162560 965965308 421820788 775968718 976274153 271678576 692101794 395241458 810756496 352396990 586736396 122885548 473848312 901700741 181209776 354150783 249891751 779470124 154890070 649439650 905251386 535212106 552302669 17770044 322831918 340962461 281133743 513872711 200098264 84363142 601679505 188022850 252551513 34912316 909492524 327188919 803699532 558682846 604107226 747872454 171683270 572200900 121661753 98503990 103201363 346518589 124817746 844475924 27696590 231894891 850542586 706178288 766376659 290971223 275429831 497693436 706840329 433886820 32788093 807855620 16684591 132820609 736885200 718641798 773336193 315563801 19872283 449982233 277388161 33110977 667104927 420504208 628884540 7015633 765085516 634589414 667490067 148720322 109460479 930059434 147737829 631232562 954879898 697909573 716441270 302862956 220207206 180052236 84871027 2503787 456576308 431070025 57214140 982677597 94701899 117921218 972004794 687919313 80275920 293082641 94536212 574888325 698383074 201726109 360134269 270375055 316661784 848575830 954328708 595330397 199431699 306561861 631134873 492298402 982227683 738881843 124989614 181921217 20257019 602352776 254345241 359709855 949117682 999398089 31970870 833433079 979881840 495388412 536430423 495231706 666269532 376380862 218278815 750558217 919944705 393512474 998382986 173234784 158012397 47817191 619654871 816713722 294957587 137181193 68345274 493108775 335939738 791148129 288253063 843898224 984445824 873271746 408098852 9643707 415956105 303595454 327802595 513576026 913449987 815542130 514738111 752707788 503386208 637962181 974170546 111160150 58433368 230635490 288284049 999399001 110877254 988767378 120468447 333055318 792943836 675104643 547642152 533709052 79037671 235765073 137450779 599776668 963678326 618399026 47782101 132445187 585563676 10558604 247950849 912705139 473595228 646023387 487569705 883869462 638775506 875597863 576976700 426070658 993580644 445822249 123121682 736747686 866814563 306695518 180537149 407139235 695731641 465171328 192281278 921136639 696912202 329779992 241941419 601847585 167735057 557590965 453101582 401511781 544963091 133510703 87358875 405208205 81433103 839122686 845457150 405584780 249221858 324670363 677075262 608588243 836113848 134752165 570096895 209075044 469246159 849382633 857411368 568708043 569130173 887060627 496210400 578147892 508915000 34407431 771991236 328723477 665534121 286507273 934667548 591887011 31450236 250162656 458019585 524920454 879934225 179973995 606719467 366265478 880340152 967232225 89244889 309974479 283033802 135780443 828970053 57430999 788634353 597565855 585142400 488885591 388026010 28380909 538927704 208298034 632405465 214727784 232017989 621673556 731444515 555933076 257080822 988580550 975211587 784597951 687707631 487371734 353760340 755307265 477816912 854503707 38169869 765445528 444186792 319779124 543001292 728998814 716811068 368036431 737546510 248627584 539740721 850363863 443839989 947853836 716659545 497162947 832898824 919403826 781572702 324063780 925580051 508303869 56013841 344407760 96431421 6814247 903584022 658233522 785338429 72437590 26815572 232190593 319076128 915773415 382672955 54051102 384200984 390871846 273835245 187530657 937806618 979490696 710172389 637925782 640164719 176898138 761675011 646837442 755589224 704864064 369702966 64823154 248845859 624495265 522201437 511538021 721606625 285823168 441444742 349605064 942533252 408859529 694656515 501868713 503605843 809651949 47979036 223796916 570264855 892475861 819546019 113148042 467567842 127629426 776508062 190601551 669594299 161548561 411585053 754841980 816113129 328626762 587033790 262223517 644641701 358385568 737983013 198433302 813653272 816835202 782812778 588528155 121238857 279660372 269794153 999650922 223010047 919202484 183380825 691575649 261025147 293883098 558364321 34831418 550188388 522116716 397966848 772694507 908014005 326502828 61440905 871774769 122435925 778832384 539904802 886738894 692490474 541184382 233896078 610118880 495413332 310250517 742967782 677047259 772290374 37789911 591904677 176643236 390864874 457006716 373247692 890144892 967931505 566429378 215769668 748113791 168679377 704685102 276563211 100779921 752557823 76946831 930192962 604949836 134449499 902262965 347051502 652866611 760914258 213976517 672575736 246721016 563687830 675355412 867365366 892101841 187910890 203200912 84596534 769977431 855934261 487995358 723002827 782437152 720036022 199317025 524562015 872223892 833239329 607810687 258612494 363106131 128509116 704453287 700869851 683082927 208259796 219417728 658059285 2345039 147679782 50189295 853740608 960793230 72900580 520898015 539537784 439965293 707115049 346525804 796215725 875570483 642785779 670310699 494611082 897988331 219668446 198875249 844962993 642832482 748345079 904329660 170696081 554320520 959488201 249227009 118023644 256144126 686584813 361146077 807277527 832618276 768424185 752249856 383597457 670551832 735492438 580306983 462573417 927067520 615890283 226082138 235220868 832386667 646131852 765533009 269949252 46303612 146866423 807855732 370275059 295010107 688455994 970629092 76282058 977704175 541438305 355793849 827646158 112900854 802532537 455140189 851900301 601812043 91581606 767328928 238742039 842320320 884518011 524405773 911954885 782642106 280631819 203170930 529119296 105735651 48929226 348801159 960064962 992670773 120288929 896791919 706485080 500057445 336648405 315286150 296443090 955902011 465143414 171040758 273428073 199570116 71357152 149309195 766262192 199978544 911390054 113608777 710283222 501390774 672958856 620668071 307922617 526125426 716836172 10440295 815426880 795076799 309975810 113446299 190903436 3815979 583201798 778410819 31990454 172921566 923538041 391295978 477085578 577603311 171829430 719696864 861876989 224473638 502465410 92154066 335543671 301032203 29388373 791441781 662681100 343258864 411599790 181898414 760610239 902012476 461413811 468545073 393867210 410487190 743862760 861021939 109745760 798053006 944293315 502073670 402722410 609226883 207048058 284183938 724034032 251287106 609927865 207502568 444489723 514628703 54536301 915467526 604867281 68324966 554155680 953147151 887175546 764555518 385764646 786517946 583409827 680141316 490177212 179587723 780575981 963590310 168313223 342165206 741349989 771508600 682449745 748072257 584024605 933558243 356439754 747403026 650751755 338839231 497415665 20981039 897063760 233441345 128923197 660276035 887441302 204812579 88458657 531360920 55073331 706253055 594910476 203490237 422469676 482691410 929462303 590317257 4190484 974434891 624299595 165253430 520016395 718746360 695546163 104663998 817859027 104475075 55650877 203283301 856495894 653046097 818535796 803996132 702680210 583224787 58235460 828787199 605493748 383050377 649196455 612405766 826924632 316774422 271281383 64307314 944662224 490664290 928469714 979291636 393069669 528202699 369956108 486531584 815039034 452279954 261206857 674756199 51061218 407515561 243045944 918425614 816816381 172143038 889087627 339175117 628246272 33479193 264037844 874193246 305494851 761611325 112977389 96820524 150823812 559773267 511043514 618370550 822392759 559173742 431964386 101087000 386179639 540582956 383493312 216032732 108785630 754371501 562670919 153971872 867349829 30757372 383116266 839886250 851415506 338040184 502967297 655619912 287768001 452723848 486128143 30498387 876462910 576326889 176582012 207736811 313123662 156827641 766696947 443098775 120232761 164406122 964594747 181911691 675500241 389014017 116635930 102011631 907662431 169746197 618088324 302906427 923623063 492413587 857995707 358679506 960136051 571489749 723862201 101568518 147417590 74266167 547007646 85869379 168936600 44140793 67994143 376314565 43548910 236404024 430703238 469902553 545704009 322480065 451073901 880742085 997991607 191114995 861094139 183370495 283500393 98781063 135881107 614057026 892648898 111402461 282815374 75834276 204563225 939933542 182116974 72272633 102153437 317513018 29917962 404317573 413553283 638366909 885725436 636635888 972886076 27828372 972330378 142946368 176282424 939988517 40489018 408527308 145926779 375431695 797105269 15691651 183210212 43957234 189751442 83330375 496667569 597110630 825998063 314195955 167215999 903097 314503539 197462796 659261625 793184119 149062269 273127750 651157760 717994274 740518768 283070635 899715042 555445949 744331768 172626119 336902089 407509891 539327854 252081939 691266625 476887515 263900442 481192335 322324762 606275250 902638355 907439159 624204994 257473672 801144602 697217204 39199342 522245588 870908119 274704850 397153423 649348116 560084113 273022626 39890622 922290668 973665535 465990597 899349663 382108901 713472675 97095091 756695263 175777662 417094002 130652630 29263766 345107348 488728734 158312042 423895431 884340831 396361301 801668339 26828269 222941558 175648404 843662653 684102874 744668283 799027981 883346318 510818356 289373269 525944713 59056820 200747175 183315363 41147048 409449469 905031269 952064010 662380585 731332426 614659419 9465432 102719761 333038288 935933289 150461996 858596438 220296740 3348597 533056354 565692143 115623774 949436260 636174687 856589156 3349492 919931160 698478274 482113681 773433992 596977826 737032801 928864586 10373987 775987423 953469838 412278163 991649653 332624593 913729982 272430532 919717057 293820910 969071583 281868984 701292302 644353633 255182748 558876133 266271135 167928200 18127183 18912598 67055784 228289937 57628419 145983722 329493381 212705764 595607376 535820323 897784490 934901781 50678263 751510930 249776147 761530353 413112065 427514986 605362047 882602955 17909861 743149248 779916472 850938196 828783847 579501716 839999940 3848202 358030677 775379098 309510920 297042011 720147635 403165019 886629052 18857231 745360895 957859385 185971460 374661044 976699919 375048934 935448319 150417062 67030826 420001380 97090949 790277925 974262810 794655439 748545617 827278285 789437405 747818472 714732710 178178194 110424521 208186708 846360285 299600667 704886783 726569257 230536516 776076812 896498016 621316723 257701513 334631805 80187428 563282564 173913931 631071660 342966106 87572110 401770286 384757939 510717415 794451430 632129361 757392896 281284406 164574149 440479637 482110434 106327404 444751071 474045472 954749059 993410851 430189119 103727182 566652272 264846506 565444377 705788401 813219567 420634345 995415655 521488943 65861039 482520640 790177284 901338022 312739719 651072716 759544365 494173658 253913180 418695550 133845857 913348650 471992177 440345343 265314907 469850810 329007776 663916795 79397698 21547448 318665484 2429015 680237161 854722305 67752212 366989236 94233115 144587795 87629618 453448586 591792053 526203688 648738050 859287316 197059669 545040675 364819032 827720113 43155404 153185233 768206989 634643269 286622068 149579633 125618471 241445064 132766950 44557115 788903330 942427439 219624385 971392994 62711394 560702040 833185358 89478160 364488300 927483284 984291474 27249515 344263726 525153207 78545618 506720277 341404075 15269147 720528357 412277306 186370489 406306196 713972525 363772456 277412896 983895980 942992808 561295311 703543988 531322900 189193847 777732858 441084275 289259955 752939553 925361675 685652707 332479487 181133718 999650352 995156045 423622689 608871821 746873225 532247841 593620490 704014332 609891434 231084108 193761411 384085522 549905981 391107650 352488501 157904314 948822954 974827197 906281007 508218962 63616053 943391738 981545364 326477291 210547563 565523175 562949280 656292535 202845737 960458479 508959528 373174554 211446193 129906522 912784924 196408054 532684957 190781343 769508788 615993923 132872637 992663793 81717758 277102598 696996803 497410281 383870564 676433883 866046629 11974449 123430583 960637060 894212368 593627317 628191051 338975770 623701321 468968455 132327213 61922580 866941660 919024456 803388509 676128452 555245873 20044956 782454727 577333371 303638910 745977064 760558892 648702539 25296963 668899975 639715630 529724453 847375639 304098857 175845838 723667198 321307412 510527307 763618913 256810050 684757090 795738299 983982127 980084296 195913386 270081293 521144202 451306281 603198459 414575446 637941376 193798429 537996512 595514506 100195170 163789970 341024828 515644577 547320734 274046061 991648286 923148592 84545537 82510165 675601449 308134371 846652862 603261027 783266670 653896474 454987792 286535664 422507600 56073476 753649941 256717255 512441815 320937204 44423809 595428035 780290722 838640085 409961529 911750918 309617100 482833675 229206438 329370192 161964958 442012893 359981989 550229896 663304268 42227894 611690694 817667068 252698210 417180024 498192360 100765652 224747810 896837080 452891120 253890479 606164909 632397685 48428774 596669231 274543104 414369402 616023018 91781102 279718641 901769572 494372738 764423304 70417651 459876768 186094748 992792140 916404746 358536378 102774341 318070921 145538145 974608489 36967835 49343923 415737767 897871642 531665502 825255433 932684666 85783447 522603400 229389621 474801419 845741617 961067407 622556851 242776384 921674936 683784669 566559261 361010548 651775159 299125121 777993321 469039854 511437827 440092980 704578013 33518032 165935151 238695310 697045124 324718053 335478187 279234569 920302550 164909098 849550654 945049729 612617579 547075053 42710312 660619687 38680547 632870414 801807176 945507399 319448929 973110498 698072389 253829122 415449474 861042265 884003812 121223933 811165090 448870005 429779289 640591222 365360185 946916523 572867425 828118130 665543419 151194265 290388452 963197097 655521028 536398577 182808671 714750559 966545596 403479544 429726428 460895033 906450289 10484732 730348074 153196178 893541025 32811603 521588558 228795293 745379508 499246386 20201539 295389362 920679653 647714812 625394643 935177957 892512428 716990201 12470772 182234570 759123279 269185564 214876472 145015306 621020858 224482418 147291475 747235075 526493129 890610343 775320305 740079062 197889324 661527129 641672733 967252949 197484202 435649381 975486451 949788513 222015020 928563074 691365176 343789936 667763433 206244845 287632796 103758560 498474243 988292992 162941615 531047181 664756494 237726590 724736672 589401400 269245226 445784185 131852515 774568252 511855957 145998729 118928362 899461806 886922647 790156285 616392191 742024570 135234183 918630561 97679918 319168639 669992663 723459652 364953765 58120031 804076199 358108429 723210371 539617094 705853472 931792787 880427853 781715667 684454230 109733297 318885317 767839263 190934110 126573821 371807614 818380312 532939574 812457786 726220669 915131417 700381987 997861619 618309124 59731813 507988967 23280996 241856610 676839279 803248836 126354365 177633279 759747477 658889780 231361069 772646214 25743714 189979148 51094529 408297914 421771621 918080320 873416253 599919484 992005427 571922727 752158796 64302081 86473203 769919428 991470411 204822295 72763809 217087535 192487738 868043363 794661044 539334909 219112970 513604447 444368274 455990654 432872441 672128561 235874202 556513447 692512817 606638500 183096953 151931821 522821009 597805726 787584673 517705926 449923574 644041808 918106346 170191880 581848444 91903845 130497127 542755274 819698467 193826867 858822912 948042380 621419585 42430887 783409881 3641522 743715942 235514500 503113607 957793493 561967337 476183461 390446422 235244366 694210697 149004310 256460058 916550970 535788521 297037727 466732642 598827167 121084421 243780705 515739919 421833924 363630168 132398664 338036165 561361741 95835712 25958419 862210557 926050301 728680832 118215304 562057087 551616847 830903187 174454234 528021935 118136277 275319188 927800557 751684046 596749911 383762063 239139905 924919928 113873866 325810575 286974756 275438980 39257758 317620244 308278629 360464889 337766561 464094797 289850160 34926478 567047389 56156962 146451345 386145274 288136822 296186973 6564939 621923052 627449714 620578443 899270202 81271772 898107166 227250967 932825044 628424225 21634787 897551578 527372149 34890380 647389750 432225963 890535075 752446764 616013305 363461529 329116948 749284725 148496076 188860347 31411220 134476982 698963333 701284465 732550669 217395231 866972373 39723385 913860572 661532958 139387171 728011009 661626718 790476459 812601727 21224762 559044258 643902788 761016696 746637305 676428254 584651563 628264577 753539246 952457460 479702225 776343075 761298769 772418368 861083970 952689788 815900 260608849 931703116 325675083 860324931 165969660 769542073 107698808 237116130 164172098 391408977 340503401 695419989 598781918 435406975 710498461 752109516 739679774 859934925 745498220 607229926 153376564 693495983 271227269 110937806 201237755 607035424 399478340 88805614 752687437 21647064 475847714 737758899 964194336 848371880 826441340 694208079 190458145 643052222 574836644 684979016 613159664 961822457 194852601 290496126 172645754 691698279 353314922 443830935 495418027 426604508 287514209 723780986 889850988 610552598 369046157 828070520 715886570 737142928 199423818 830616309 310934155 94276649 393946806 573571851 843900460 178038516 151703933 369076070 761446861 668123461 921520237 31933963 262010314 344946 612206924 961030622 293749360 446163814 171892218 50251654 317502531 52862065 725623880 952357324 829249932 973272349 426843660 345932551 819846653 180976978 63770104 431801775 947820007 31072982 314709715 564200048 552002597 275501114 700433516 474051859 787735063 277047666 827949041 412071663 165877939 762078829 879559516 381549007 67737401 185738929 345666073 911522906 757525220 704649025 543860173 108019415 861105980 277190572 824241764 482663307 416812861 605470196 531743110 362207223 598710254 848058742 894050325 369766946 25016823 581449351 822980640 408685797 789947372 939702783 341014267 196209212 129693353 702108078 276044473 803216112 124296266 733235305 152821783 119387679 206044213 79123533 336792602 898369394 703815262 566230172 829484895 738811268 59613474 884985692 47915350 246956327 484372925 477289130 404118776 947607603 110785913 408651697 551748745 480426065 829587864 457103738 104721718 548473174 881399394 848029823 908468431 406354295 504589196 354084868 583009598 626974934 570817352 107218286 898876873 949192801 668187698 188331159 181563867 362663215 281255327 743779822 868464125 581810080 899627394 214894020 945826901 691320041 826552458 871769189 51292190 98171612 776869892 506760336 543959510 283439988 577665196 172229707 490602777 571310817 711349436 981732639 715453240 930614493 129685726 919903435 346622424 898317630 613013721 809845469 606385244 720345368 345404807 882586366 681764129 34074660 374758129 169195155 695645130 832953214 77319764 160079342 312568981 601714867 216156956 171784265 942207013 541544893 83032191 940094850 297765636 610037006 942124522 976346718 702705874 412297384 809960290 430303583 525231904 490599656 617419753 496258628 690716305 136410362 343235325 496130701 856614214 806693089 367331347 61303004 747019688 341209272 976510264 94171096 747295176 14549252 920330121 844986692 434321442 343799910 132021037 302706702 27320167 207983756 964585729 298781484 637254176 981319403 912742860 744007094 32505919 496175914 216108293 210469791 289525859 18593475 215307531 954992491 732909859 708610246 493731884 118366182 11627201 180684491 112722886 216401001 180799113 205154273 182485549 521520778 779634428 399996020 960742373 829830808 681755421 953129177 519777225 538455241 880113095 139482147 887616393 303049947 586966730 588947631 170276014 272405402 360185824 802404449 714988352 283349383 917669166 570873031 980638375 299882260 586725072 66473256 703849359 247765666 17419757 959062820 89633969 878691961 89178879 333656575 520363886 740548561 106484888 832996290 726786290 900877228 537908382 449234858 407376900 535493400 748464808 350321868 465647461 195922477 682607761 403001274 669690811 566396374 563319421 598168255 747709515 916507614 753167810 647829652 801230286 351412363 900888053 665452072 719215765 411455493 138152366 148951706 610327822 775132214 473940503 158845653 139140294 793906998 510153091 857531700 899699755 738247275 908549165 623600741 385816020 57004224 225706157 933440878 287466636 71145597 767011474 794444300 256720854 138300872 333918522 32771123 172166472 930094458 791534560 186063300 564221681 537278218 90200750 113475604 45506259 636258858 402084974 868303483 660043548 228030374 813403205 299841501 939603354 621656968 266254320 610452291 428668819 806739290 230305239 825741085 888616259 10417986 507793358 828998239 233100958 614814496 603483352 297160966 733346833 6422497 936247541 459627616 766561420 586390592 685907528 372738352 522317984 745890171 638761072 77217151 487463502 167366527 173815748 866699673 424212316 921687787 626032759 450017184 20071404 556664948 322843067 689276927 340016460 414398754 18496601 779981033 306365934 525234526 931284724 844245984 647846669 673240560 621953828 741203976 669744129 58824097 52972299 753023021 933942165 469293973 230569030 334758410 67781997 431090034 477704248 173790155 966788419 2313721 282894619 669384283 23435523 830425092 908319600 930453634 514084327 531616180 848409591 503350407 709252396 860428449 654125191 375678859 247360157 318420448 523753451 872383218 569381873 167857758 677526501 785604378 703591195 872970416 175442400 771096647 852589376 476712446 362773793 919604684 727432770 136399740 817207275 435050218 311408533 961526017 256861187 113272050 985160358 764526686 349681578 405853993 599535651 37820952 759691962 52408062 450936795 430444101 253055986 858260279 546266205 781279536 571076566 596721567 791854601 907595 730248831 384918526 250254626 364077976 593751029 54585095 575808983 175301746 340129708 843872915 525653159 552053453 545435740 124563931 645948908 54656863 22218243 710316839 630551488 370645803 75179164 956272480 408426191 741092212 146328701 583305664 888637541 776802016 556109739 792154425 674876578 170799223 194838392 548641563 821901588 819488636 727353048 355002907 691544734 91819446 684723370 183290774 36023183 598942613 810456515 897308580 203612230 629907103 391748678 666900062 390917895 519216055 971510851 59847354 361205513 800923171 320058234 605913087 396242106 710312114 805595547 870438705 326684712 258286511 624875941 745321949 457418452 112101619 451851380 780534890 38733166 102492153 580255663 312856845 558536519 296477593 149409343 665046586 667641903 779196425 853316281 408760234 276628587 750019785 896141691 736325818 399253087 47867731 695216614 621665539 757135520 799299380 122361438 563507303 395880233 499731430 324735529 496549541 832049375 38079976 79964449 832996334 489431572 218539642 517800876 128275311 640284636 593887839 278501893 764532135 368066043 267943727 474611581 100981035 835507512 151648132 811558220 218296510 931445681 113193119 676719623 547463512 739910563 448291671 645235115 986649928 372708046 976012970 885792052 604886336 40268029 300000082 925126984 368049040 843748042 510939848 895449018 369533139 837512979 955515325 710732125 216189882 209126702 759524270 979741225 510315222 177841625 638479897 226730609 304760180 722306424 974146318 639741589 748216286 464270131 358771563 688886985 532463375 625350360 113998518 784245871 738792984 482305324 896197645 283973386 668911176 885827939 738020627 586666588 120763296 471691350 670983641 856246033 296450652 553413375 785546955 636053117 512485665 365094762 718928054 519555764 276937474 586130663 904125173 234897906 269976602 752393230 200560904 175882812 256521266 852388635 886611861 267437161 380924996 932322898 34068180 306672304 209962979 677042021 699867510 393956994 51361405 802578932 103668771 928952772 274523170 379731746 616358174 681623574 466317 156814627 832162024 83081813 121236840 414077766 227192124 957142384 881024329 283415994 969812808 523693710 312185767 376893005 577096882 446407821 771605714 875052742 735404382 753014725 302153879 671586651 22235230 467453930 16046058 883230800 115868319 50207790 551702777 283644407 954451483 611462566 952882895 811856671 486707561 383191605 494045629 818064308 35592333 361383420 27286644 946785164 128200080 630609308 101937702 304345096 550699116 150910497 436311131 618339995 15173430 398475064 589937564 525998291 776772413 823617538 580067521 67877559 568991 730848708 646155169 642423702 968661215 736313042 891877377 241025254 904458124 573364963 962578587 227887827 796623650 990723015 362464861 892159095 985648012 751514494 518517459 743738648 521745204 972992463 198337756 377582916 536114202 636150724 282282460 825636612 271473168 406038015 860305528 407624572 955920259 695666569 677666078 571034993 388699824 576984046 304568868 219470368 855502139 725536312 690917957 958404682 177441941 590491062 484061565 229502168 576252727 140632102 519178669 392554943 200047479 680327820 316893628 498241679 562852553 909311680 678791055 630150750 317726208 563368936 62357113 384043085 461434521 271310371 792488382 351910212 351024582 410410756 195681327 250647289 895071137 988598869 35652054 730043152 219548402 210141210 15181172 943065866 685915540 716150409 959643903 593112075 985639380 765350856 548912196 485232547 829899819 716468268 827990840 606781102 207121202 131388837 518383150 499683577 284520542 444392843 773527426 314461302 771191906 567862111 278577709 510812749 868409953 80485618 389252556 590304546 139041195 869769374 921453196 435991101 252037614 666564182 838166775 676734394 737344852 156124863 780423572 111062532 697503369 777823291 858497780 367912049 181606981 488869151 986009996 169392567 615556485 284571140 555508109 6591676 942518968 800343136 942735598 66501003 964198477 53908598 908357179 810371240 554215652 234437952 993900801 805405547 71194431 329184044 34788819 93026551 761705572 846239246 805663394 866382813 367022099 730824671 67603007 981522733 634156691 869432293 140703470 638787027 511791010 829758845 777398053 491035967 568708781 75924589 528741038 804299817 634480745 332914754 79679199 105797817 355503397 250342625 844204914 132828163 774660654 253437816 883694480 802474501 756006354 778452828 470112679 209132256 324366372 411112124 533736503 395493201 396759020 39501201 957418922 409944066 965312988 811340282 659917640 983424604 623635818 130937322 911838730 495835714 557012891 926518360 485864105 199684266 871338189 386755805 855258521 567473043 383614752 824285322 972722124 855845019 307523306 219045142 639391324 571148864 851347709 785113936 585964007 284206464 593662945 840904072 98451425 320116458 318939452 686147782 417397277 476065044 371472585 956911501 306608494 27464502 21195120 879926600 323336376 869387650 858579830 221862403 718850900 895777886 105793560 309955820 104838083 636505517 508149537 138026586 596215823 582400142 60593030 547242524 816372997 429639656 128401651 577794962 878536576 217154136 839028977 950824303 696311197 878874744 685559192 202770850 552766196 495005088 442517065 149353932 678794842 251627863 873224349 438577238 210391340 333793376 721910673 861926049 196760562 353258978 895802160 693972014 587214033 77306818 115754891 340498435 2220463 577029336 466102652 798590355 645022276 9789983 968593688 52671449 363722846 295142450 51344720 22622193 601413869 471005871 167702328 213413383 979084650 926378187 387968227 883726047 544947648 573442222 262620956 215526951 905867099 417762697 72907611 264954909 243235911 336341018 40669246 464861763 940230944 614649617 352681520 410712803 313638063 425020675 834013131 31044244 883913517 517561766 632114612 34382220 861708529 948434950 946556850 458043692 430966311 456602862 525900617 288875116 185221260 186442878 893957188 26260456 634243340 615065192 933942405 800177360 377172939 310351471 975136609 183919576 562579685 10320124 730749651 982558584 633357542 323985063 44806268 209050945 278055215 377629408 934107938 767755647 569183232 127800771 94326239 621449729 639318998 245160436 382622678 292312970 820164255 352570040 219915798 984664914 994644298 460700398 797009475 918297128 69129927 321277505 217410553 117860340 850141804 414680383 235399055 59974952 982478709 427794826 390661574 998492123 7013911 236899180 690781955 916352429 391468727 672934515 599206934 768918146 503776928 134464913 389969164 553135631 826611924 360791546 774768036 958830307 966681400 213846100 465334062 23084622 317741599 171384875 770181148 641117110 415880891 881089178 50844730 537098476 761032877 218207374 493769719 688714002 633141060 923274446 898412529 83757181 215931107 378235168 27821344 425759046 86545823 337077315 430512695 569626708 184243420 474668879 592452613 391447102 764522032 683019018 648461887 417174621 354229715 537447557 424802985 3833080 108529822 242579650 862995985 411116189 809980943 535285559 473048842 980047132 232689385 362051933 202017066 146197690 969170587 93118443 84091874 403278737 993063962 374461688 68136834 552341775 941583793 41891386 844308977 810724296 217448244 233622278 822418229 972437100 679436338 268038200 13576159 957096301 583425826 822040262 46243516 544610556 529135226 185572184 290190716 162507435 448050410 583079950 306924928 214928346 309192233 682035799 402673255 481090360 246454387 607929801 687788294 906577451 164834424 864031850 82210037 474833111 46156816 446088994 5842205 525499835 201971653 452167930 688958877 29342918 53984469 405248815 872451157 175678343 636696722 462363738 913121350 620965226 23999380 67589648 681118870 796509438 986118837 935918556 376777766 899960056 425961590 756806823 813292091 227987765 379167076 888651416 832453324 470331787 602356274 525117637 403716755 952693953 145964136 891826399 959612880 158859009 253489136 724640042 220544195 459969712 82210122 141859362 626895243 949753850 381771645 98059154 126537423 927641886 666323959 941966941 703758237 481302071 125144930 802979205 823463189 65524004 804545787 692796424 949162433 290324840 114472500 583111574 845661780 80227759 74485475 151289505 882505894 352821490 580129299 711406260 946892143 132627374 180054064 205893183 772032667 189109587 608869956 440266992 670553038 419683416 393756260 593129010 179449575 782538781 996842031 92595324 831117843 479843787 291287224 281106531 505930402 19026879 702724499 302376705 227868270 691314610 300598992 10183756 908233911 866529983 407300691 298852386 405073631 911484357 981861834 726971878 147393281 226132732 109743228 104879898 636484655 296474462 823171519 873586357 458884119 430546163 396072735 523005550 799711076 626273807 606470925 544163379 52554559 36229562 213178134 109793478 808107822 930062547 50355223 107349476 508930467 895782440 805431724 232543625 983920290 738445423 165689492 867361099 992271286 261593524 701241366 646531628 118677266 730698120 952313184 193217261 845799459 305345812 680742037 461087265 880622675 11663620 892245581 868410806 429404746 440429388 321154314 549908511 787843745 616932987 476462944 433323185 928621823 743246120 457866454 907709703 843866777 623082030 738119311 142808218 400237805 988950872 293726724 62786182 181106609 374182197 984096018 814651808 452705871 215465046 472827062 757279271 307049166 254751325 375431624 697579905 243553174 11825133 162591861 239004759 470907865 704729967 946255224 656014493 816258165 503760695 356425010 921072391 293377153 765056411 596985761 513468680 777433917 192898856 618413840 279998258 395110715 88347651 327336879 620189877 214357264 717392422 422367971 82942775 308169953 270408695 463605180 720078977 437183509 496156994 182767078 36530463 931405743 889298136 763485522 915845875 207245870 145576807 394561089 710475229 542356888 733542013 39036687 87608257 170595209 575267660 253091549 473146925 603149052 50297478 816883338 500592096 169948112 237059049 563671815 33838871 109598044 213272505 765109624 13317658 85055557 996868340 786731245 662475488 530886625 577824109 488424712 752741295 666658909 454026913 572365168 542716215 903141249 288832648 469785250 761254271 49957518 413804910 164110558 854852179 534584374 974065558 620364252 133296430 860735645 64023956 65568758 928800025 230527711 55549846 301518186 991652386 843265884 258477117 183184840 889804355 506618697 819770703 522083444 23876565 575261564 643970522 164369857 316854011 828223609 639536456 584029378 425404888 641475037 442819606 246053267 687157201 80127646 616610927 672050932 724919129 754699889 898581712 657890016 682224721 702239324 508454976 41359204 358048330 179736896 783293473 575564627 121815165 656998009 832142831 208491647 568395843 649667297 898130742 13718917 686247431 119167230 850462016 42828893 808839328 853852797 202502596 672520338 501218585 998273161 882679101 858942753 59561488 494403917 754059753 883501600 369898259 92498455 986328803 861052257 932247176 664167470 594592041 546693510 558830268 631223062 51920775 483342965 87242450 206819059 831585644 282638949 647205250 384088526 530129927 832093544 186725432 399971751 800041899 74162043 210057543 574105538 771716007 406230271 572307321 416222742 72573242 738986250 523576042 301759567 916513898 457388876 566720392 850083959 742037359 482611251 806098222 738441661 40377040 368383987 812478181 380349206 955013289 704901249 303219994 555126123 740190982 159481752 233021073 376645475 958131581 722005059 247393761 889247897 957001290 933955966 424644758 821789319 136962163 470160064 754597817 434186048 973964154 510481860 211276690 569827523 855661405 268730548 397045855 675068579 568104967 717907432 584560661 256198909 933494653 339851853 338476633 612616010 450097913 666181995 933691248 950251128 168529635 193010815 212313625 881203304 472577217 531221026 857491277 868057501 54892330 777559064 189200327 969321120 122535893 925714112 932102815 169275608 482315954 579964012 565735633 28563375 959700217 688284112 789571975 541505514 105444495 142781457 344678254 666406113 188179048 367089415 27476395 94591617 440168540 2991508 935494961 606319753 420488758 790110114 658950918 473994454 234027653 363918562 332449772 756030372 358827593 6326701 506859299 806249455 874041495 146313040 32921428 293419793 638076990 613837329 421489360 805989804 2116027 147080336 67936936 660291589 405433673 408475812 157857276 256384140 269101736 393741543 412061512 384638039 991007731 835705824 594203346 536990625 24774229 841654654 935636240 166014414 739965046 837595830 507536426 310901797 629209561 716628903 662326477 498942719 229025962 598744758 314316323 642557781 659825716 640137121 536715479 933368908 608069502 680575350 978323020 576115894 488226422 270451683 170181051 833923490 155990437 291337795 25338290 464070656 117853336 386209758 776064370 517235032 144746996 968518690 237228188 43388217 445795732 523554736 595536848 204927084 338609122 127090196 170868610 500118773 852137284 536411977 591584811 698385964 107977346 283355739 327574150 14195426 152872111 423491709 914446946 297025456 57407063 947138587 852509793 449581749 909394518 802439256 721443281 971417997 381310105 70144682 19207829 669279812 865741073 821278008 947705356 8990928 560745830 84614732 39576872 626918050 60187765 554147822 307911431 97121162 915128246 968498581 306226979 283480861 497239191 875866759 902578002 704573799 448165019 879396634 423898619 599744527 401644001 884072347 696813547 700258258 741649156 460596622 518220596