2090 851632049 485135635 935815719 369440314 31199373 704369662 916037867 742059424 175435406 596718420 669042917 758650528 576228943 622846397 782620903 929553086 872349055 389204274 294319160 472622360 20171035 350723271 830023190 261582868 372451472 830218238 800927879 894497753 834302623 798229329 964539359 863702593 418285708 311951729 266212832 559961065 158824149 74804288 32079507 545252684 229403381 885286317 203180135 994594884 977566777 95109245 993315147 465891872 751746994 140564038 62008725 478970534 487714921 814999327 828011103 722910030 800771029 982275460 298818670 143024526 974081656 862323053 547615924 744919632 206891507 931205604 461189441 653498501 721600199 218395042 925681581 512098050 331515285 343178355 433455177 453331774 427665729 2737471 145347662 498722107 70649840 533083262 709281503 77268298 876369617 592989074 992169381 626063123 276533264 833899357 118425135 876431181 938033045 718385910 613083503 278524507 254620763 678582541 677468458 816029934 457418612 361999653 10494263 480077117 75536658 608097599 106706514 540027776 314928700 547830574 61992628 950473119 718889228 170268457 408033693 343143339 160867522 79843232 790701790 206926095 832487174 879201855 75288820 643815741 914197469 319403089 614994586 839596183 234732340 49826238 724324006 764061740 462531134 404425743 181079101 716487125 795850625 84740460 214628756 749477639 289349905 394631116 471966502 335887047 612204234 207220363 565675007 256444129 687919880 621012074 301904700 154810475 767910103 561506684 57568201 114807212 328065834 480774868 221732554 737101213 803059112 524961725 606044664 452029047 383411454 498692670 330567579 239720599 419993937 298426016 443141845 927480040 180893762 387698813 76824727 116194020 975715549 567930388 543905466 888832507 607139690 302515147 268090331 170176117 393024001 968713547 131368615 250335052 196001718 128608355 336765285 867252207 760511789 616203666 88476474 743025498 15999579 653756108 814010875 390529645 631784259 19815940 453645191 377820376 793388111 152510364 643054864 837711485 694428667 277991401 44652064 386382900 616022926 166381285 502396297 822457111 221416087 735562267 938876839 8860614 964959180 89288854 347097438 549062512 301215265 376016171 568915615 753808700 513464829 755432007 213204708 990819663 624169933 917720006 573828494 318579101 306834109 206369276 44383380 734778071 992586214 912218515 979923326 100117732 304962680 202332523 145075444 861185326 146477285 483135458 105425223 749007577 277539445 982073309 239581240 992220602 513622970 620884087 258394621 626520050 987002916 480162219 590912534 134786866 111555060 961611401 143599449 546299939 539641426 354685797 409154360 393648338 456692362 704658755 332842245 830993108 47087973 46907207 364421237 600208818 422013306 824348065 853622470 740324688 287574154 515993483 460907841 62590846 270137451 86594623 607520071 708177479 900299608 309085170 14312783 815476987 868130021 70911833 720272738 488276655 852456924 734455226 846898307 449821116 194093412 216836509 324811901 331037488 936157849 253170504 888561874 642113241 29814625 966211464 621073757 486684628 196102780 309693520 473217294 578694668 840457493 261007596 928952658 278589653 288555927 345973512 548523103 367067502 588834575 435736669 31827638 662346004 477228255 728340844 2622633 141036246 586811850 439101784 367311510 93020459 373028729 392036003 152285518 144859191 636994049 157698520 486800010 472140837 65686062 490500474 931420075 486103195 955191363 205452261 410100042 120465594 530701420 935152254 717490667 576808024 751552348 663816478 983702840 534981681 959393101 72698973 903789255 259788815 782081246 560987230 648630116 645688490 503040588 906738109 41458689 90234439 276728229 588422026 128121360 655478847 830676516 967465882 228457372 556003704 210972836 273484736 665193576 106254639 607942773 588637497 941796471 815614138 11292008 723332858 86442005 303037881 456184554 391682306 110749167 374181084 195775697 47926131 181720345 16556836 49675194 621549726 191226232 306825338 819060084 248724259 44571513 241371576 350931496 911372934 351291328 228433824 398315439 364059293 780848861 319376837 495037630 27702147 674724163 980788165 344288990 894950306 37888790 300645056 38628844 813930733 74813612 232568881 562506034 473836618 121173654 874527443 487818179 532580075 233950528 152820112 506455536 566819599 919253483 883574446 212321449 990723055 94995984 977829728 569524219 780854711 53898470 735907926 245408861 428264734 734451713 631084833 372623624 910327994 535243537 483155916 507305452 433081650 875048057 412829941 233582075 328015659 585584804 794438638 944967717 635998853 257768087 34316294 694909516 936049183 807608608 349561501 445430937 581328655 664216341 446442324 557878955 758207799 400268457 244937115 888594699 114127624 303321263 206066318 155366140 980286587 759335156 355066305 586809676 281601188 435373013 739821472 7415225 776845447 332065718 541239293 353192848 516283276 141004617 904707512 841097807 368786443 999051320 993541068 746957089 96531102 132922724 745114906 86621809 947297945 306575868 869715985 316670048 126367720 937492552 820410182 102472336 788065954 833427106 24080290 827861441 207399852 372570386 487501198 917714381 853669668 394273656 607316459 509368816 180494963 500172600 42644829 832166972 906694691 226184925 575036582 746488785 677783502 725551448 967122826 252150245 986473617 727018619 110799825 219470896 507124095 65534172 729031689 144213496 385683827 600417366 878816718 962490134 924427461 720937131 830909530 70507702 523886778 485090868 501945550 388437485 537227083 769105341 951779049 374344954 130482953 620206868 630587229 692194669 315172628 622469933 229883101 289286475 536378036 237575635 389418322 726436657 321385069 315848413 358132676 14084257 370249950 194361602 899174608 243940828 987949466 776373309 364363732 772265088 744532581 457126227 788169017 336908056 319984503 641098496 645926574 196702962 603981622 514035404 498621887 969200525 569215092 142203838 700529949 172213047 451172881 931051915 561144240 719524491 445856686 77389549 757448243 38198782 836679190 167278981 65721069 331247718 230656184 866958320 653109240 16123061 414313413 792500199 243296599 925306858 770999031 516537099 42727287 556520336 437601437 832826671 662999970 934273488 372140354 662466260 410965970 109753350 454578721 824063576 918624002 671118953 502258226 276638464 224257154 881383478 660234362 607445990 313491734 90729619 976456891 346400158 524515473 340349856 327543915 403479391 819835043 543231465 922850502 505644709 753286387 853629407 402541172 425171299 750779790 744771024 476786507 590805094 642959205 488075631 154536828 501401531 579885581 194127514 509634169 363196724 861557913 20711176 869989147 909397884 405331039 312263017 560553672 427452297 464804498 860959979 461795164 844483799 46624320 189361105 980213564 737476445 658929213 954047716 930837676 539641074 286084184 836442363 175236547 866724699 124507794 877816154 421756681 723081028 16725374 882526140 773331197 960494450 443768587 919868164 382533150 166112297 406954330 488329893 749391119 42066178 615220681 520871095 847743432 929940227 833238136 17597075 478200289 159730704 671329308 834826453 632237742 727863713 920463789 561227461 820486282 821223885 931987329 700286371 454255039 35490325 426205973 671223338 336236242 695845433 143290017 584098927 257910412 736758026 665647813 58463636 367027018 507577245 162884428 572346292 965233507 921657737 293135358 786824249 525989966 757992490 903610749 931993909 8646999 96093278 708774519 345494101 506004372 494503819 908825232 594350910 156967785 384654332 594531148 625076178 368203948 647183801 313443907 194182211 55010709 353655890 927724095 492971794 174339664 582201369 364789146 932085296 684610483 903921921 475056435 475661083 986575954 738401874 881752646 94292991 116747643 28045478 136311723 724024758 979795869 147519716 573055230 541440458 528307885 773114826 797970911 94714323 427489340 202928534 539366058 518261659 919855401 780640379 655837397 493107921 884876414 190104380 782710846 323576103 484530070 311592491 333187368 604998181 50453834 125667066 865934807 487621047 834368465 226317007 407484911 521728094 722962058 975995110 990512661 924762475 83865940 304361495 276828387 549424996 221898731 66673598 876513502 375510760 540398450 271764823 184528105 224747122 392970517 100893833 215677011 549575879 539960313 949840480 667684324 11553855 949993617 9453424 507520069 420788035 457475881 771145970 436095139 613267394 607130768 705594316 442770265 20774119 151522096 595207188 64509714 590156954 405280858 456695076 128015819 704788939 690293020 696724219 32106301 354684627 208640641 52338539 217699461 241799553 839179425 957179928 319226993 897075023 434728671 743176490 113163122 653407810 150661803 593177101 481984206 267494897 819436470 174106366 433501937 863580607 660814448 124444128 892583838 968246679 125709537 684244186 329624611 685421654 977505403 598524689 495008393 9598967 356139750 786970665 279736178 630138316 523467575 61120942 617798319 801508264 179242089 281926880 827416747 920080182 232865756 783584352 255257230 458615151 676458203 958486352 619059001 412088811 323997771 156980736 839098640 940963787 338619002 735924181 793817928 348002054 463424790 393775950 598975925 32968180 83344926 688136789 697333107 604378914 194658581 239814311 189653466 61364943 491595367 907357462 254857655 923876872 361763345 485523965 501365931 6305836 933436765 300384983 466259759 39541207 329937044 201309718 333155815 267741115 186907185 790584497 447592505 465304732 175626945 405142347 956323686 506050890 123304852 3109284 522569265 494861822 923310483 734691301 969864694 258936635 870646923 989104576 969674808 935139490 762534189 896559447 943064138 31274004 800859730 612064828 413608792 647981702 401330256 810390668 760329123 836355654 389704992 27379292 506488249 661334947 411578328 254513937 90385078 71739562 896145963 430478931 851502766 164953429 561587643 407139612 904045433 301996670 220510353 611363285 194670386 9419155 504687200 452301782 201209854 887361737 659829791 575253431 775998244 694605137 401920691 985409752 241864829 640160834 234354424 971074732 660665611 977316447 979722023 451575399 795211582 78329681 543639984 748841326 701404115 176557066 496277024 466260824 862766627 273482379 632797754 12546804 522680807 422114714 112255523 580286787 686956740 224387622 695305712 921069464 509115281 606219400 923977493 695273077 455300384 145482579 483451304 122910703 952481957 817886926 135078947 489847760 308341783 243991727 581368381 799892179 433700766 147535785 525933737 786617359 344384013 736031713 355344138 736878561 808302514 10556557 253410090 500435296 955018509 213933166 229298805 24288895 82093461 146456714 51177349 419610595 231895049 916815577 24704684 844428904 16781976 678876782 45973847 131579688 666588168 660970992 629456171 641353531 711852128 171391008 207435043 207973251 554908193 677492475 815433355 533913252 209632989 596417059 523583092 509115417 304785427 724460027 173708606 876124404 96699614 784773713 809762650 815602121 705412511 54562125 163537233 323609789 223447360 991809714 900310324 91978503 446094103 724369828 20827519 726975447 798870990 27344646 818082071 525916049 817224141 352205251 221135271 332778765 296300381 830835595 114192890 831638105 200955086 255130922 607655727 781867996 319082642 323536276 509556422 520349567 918752971 54936088 294925492 453583496 277806572 959277375 508978273 537525426 142373092 961426306 386703292 576317992 563928604 654666946 605142220 985555280 650405498 306084527 686830732 94193331 256814539 550018685 514765373 104066266 40044746 214981429 779947960 558254385 824038282 229173881 237545334 289807921 283390247 742168956 372627583 760262358 519980046 859853354 115828859 279200175 944037272 633453439 926891414 106011784 33044587 48412808 280215190 635876933 785178954 503634352 749960216 380357930 51958724 194761952 404361456 550567722 201890452 390555317 377647432 613830223 23550589 905976006 817165294 496712233 359923681 809378944 942544204 799779852 231845774 791261481 652723102 927717733 944750138 202654159 333984321 866417798 980581492 100384358 536124200 150634329 414726536 158987690 135820098 280861406 426459111 622436664 415076822 970083172 248497342 2566837 936563789 267870036 293306293 361054306 716961126 735294923 977707348 924067800 462488679 817674157 956474446 803303195 605010092 896711923 229039649 139581840 946250562 926732337 852708144 24850523 115949684 345153266 571328073 753968451 39796273 682340947 499212458 634224136 695623013 453020411 174411553 33274861 234014654 358975581 11227732 675982156 706595736 268377856 783065987 819894117 934975571 859880812 577770305 315620527 286015121 293858315 319643006 740601444 313300004 969007025 998674222 462838402 502715462 556110438 699485053 745405685 198348660 725464602 670624919 545364347 64119562 534459256 322031804 830716755 240927773 853082043 259410787 891108061 250542223 436174259 443114142 513605111 587888739 649765754 543241921 120742101 512965743 12258453 233248168 685062163 770780554 10942817 288264671 707256905 2482175 115648753 695855464 712914904 234734681 726128438 870288143 368553591 903057840 154760683 228377760 840744108 753581271 981302035 12857573 351423951 323628975 10322986 597127315 77854947 235529185 212568817 505319969 395143443 503549563 383247268 762298800 991856852 720400513 389957000 549346227 157386332 956252404 714066403 358940687 947001210 11422344 134691921 36649301 512091430 230814912 184431335 202939628 144441578 859037913 613721241 661952253 810752469 52318162 680231839 260363114 474108419 898816826 576239578 187025882 238060588 940801082 480356180 18350267 569345603 264762554 585179519 866453476 277017391 790301779 281489619 844387362 691617646 85784491 358353350 876443874 230636951 984345174 865019474 64406187 701782586 25119615 773749053 723523382 224337357 921681428 530767472 432854402 855086105 348450162 821713738 48575711 580529334 254842894 133143263 867691590 573102693 514571278 259383986 100091802 123226056 575874391 791842275 623329119 40926519 296509664 676565632 10669869 613031761 567790522 421993065 579779979 459096087 332145620 343854333 72718500 765773517 769376439 539105088 788952092 753988239 826875539 859600352 243366209 451155483 971340717 951427363 91115204 575945065 710013476 246068712 347162657 199388155 859095244 981087150 197534035 800665174 452722426 765018130 849553807 597788264 552633669 539980975 812623586 640416149 572677967 143124422 284984557 279862746 760402553 69738 116441676 306878319 248148035 268390309 70182478 380355822 220281443 162567357 305279911 694435114 812445150 210419708 732270261 169326539 835612754 194864658 159112757 412603119 808391805 996323507 819824684 234127358 186059543 190541004 868435904 71869818 427468803 100246684 985629895 821975553 744363284 303274491 881510452 312801629 214390685 403555794 908959283 673772158 625678626 906750794 451153349 350721188 547742827 671096178 259482965 131229206 602179995 800235735 655637508 83384532 450123536 185100386 278975436 562615263 86581015 618313780 48719164 58908583 520336721 324060995 956334150 61690605 195995150 217763067 273945504 326030941 374940813 710318372 206728935 948456290 88359934 742935829 619108209 458393307 306359084 742016923 172730452 474015238 260183051 369351235 235755964 433257140 644081799 586384976 416405119 216184129 275944646 343539442 778548738 181485645 958071639 865266499 461093832 831124243 934190978 41406866 970084048 172283449 179318886 873612252 738553972 448289043 884873193 52313983 713738114 843018293 688789953 427349823 571511787 665917504 187755467 557417079 44245951 748242697 59981947 575683107 521929221 866902434 597520410 373550170 372780167 684012937 693125727 920325511 309181822 727691279 950680572 95803018 126056406 78174303 60948872 502762209 629065256 923302356 407701558 62876452 333917832 162089774 459300071 504188403 95171944 60605966 685325672 720597633 354947724 120424751 573976312 708292508 323105603 374811072 704473816 938601936 442275710 403161328 692255410 914876865 736659117 58410939 25821550 405881703 492175290 447942454 531408734 417037289 67974519 659064396 804323190 441803382 549238795 677166055 103241351 180258822 135616431 811501579 358174828 155435120 142936844 432526791 19604777 104117810 659623571 10474380 920342240 606244270 418119745 542095663 589033637 655396135 652964307 783541827 207201826 912906135 427540352 669885437 59292186 8536206 158655149 291158333 68691183 372861898 113221868 691089598 151844301 369421974 520066996 977866841 497708403 609430325 40731746 421374556 215562005 684909738 762384907 605546461 726368401 334252298 685203236 604913159 865631829 61439263 120314416 575741748 175496521 262584237 489176994 182951570 914746224 43954263 734955159 419225258 931930734 675450442 932271397 411933797 205085225 625214322 420050840 583214252 517035986 859265549 224856644 194441708 711692712 429105769 81685674 730923800 949809991 935741161 920743359 989054066 662401188 244728002 114419861 340955383 119410588 465935105 465701555 282334788 761300299 83709787 983579901 134079168 130895338 239104905 148643200 333635643 736830055 438666660 279530088 169770865 587315995 660582334 379797032 998609705 700434467 213364302 831327073 28161356 609321633 21761208 928586200 283270273 351475088 805973095 914571353 140694988 432637488 107790297 24438273 27027996 464111248 183287089 904504252 836875272 822841680 574205626 967787034 282941431 605671556 435339326 217537631 173528260 941438057 298891238 531729463 390708032 296929385 814623211 687767117 482935091 505019521 543986489 425957645 743029005 620932292 602005527 768488973 284530791 439646889 307581268 316942786 396653756 499531731 942189339 649146876 129526860 514924489 736409503 906701592 668190426 253220620 566079268 866638764 901434711 309349362 309964587 297054207 645325545 306914673 277209575 490274170 47127415 880922964 273901611 711154208 874748714 120562974 691170549 282568514 263474395 956177606 90025330 640455250 720593670 652978044 489487911 373051081 596475372 198164431 174991853 574783952 790327804 108914337 680082836 610301380 278659926 50039103 872040761 567087639 211298509 199825973 676440636 277479476 423356335 453637450 568800233 920040813 900671093 770115763 284162441 53773908 602576864 981507665 952906857 396946377 31450651 109744755 343241636 659178382 411636294 471840457 22815398 821177955 808604802 427131233 930243650 697975861 432658059 212071749 731218930 742422518 997377765 372505807 842220348 389576645 246831433 881594693 221825266 425956546 338745464 967979389 630792321 273620737 796924214 844251188 424969998 871832981 437915719 217373968 239891435 95118866 839607041 422642908 380984948 782419170 579569618 309323956 443805082 356641538 38925817 178869776 861358399 338717544 536568078 428171741 289543374 814146007 95515061 302383511 61139314 921041219 793119866 297577349 224047336 498275356 781574629 428187114 461948222 737484336 626071443 330575943 98995321 302093068 291635277 207677890 771850500 296495854 80099010 518266124 388439612 44372765 695983546 322688910 151167219 573514941 206600584 907809295 158362543 450028109 111752053 967870105 481056305 505707574 450601395 621351982 708050960 65949520 143965326 923741626 59689210 897718625 81588138 298388436 226223107 358215725 402854500 35187806 382462470 547098286 815028093 79631644 164978822 444503447 864027892 503752455 478661450 832859781 809908244 657242993 305297456 719020471 837718437 712568301 419025583 463762128 717284023 684207379 330372465 106085900 349194637 303840228 144819613 852621483 700771017 419278166 860366594 654945683 695971647 77148081 899839910 478447703 792690617 163734738 233331810 579293688 692687613 268172332 443784153 838324124 176255294 556742611 612353222 792592634 648751158 992873154 899373806 922820110 362283400 494788275 546881364 924457410 704215722 787051411 572739934 339979636 255569527 806464593 786754552 130341866 710054351 882093969 287258368 339987362 794037956 403863578 859880928 681224021 681970273 727901814 461163895 67018575 644593843 893817025 993102330 519952061 287379804 140589656 700865671 999537104 26431948 129833033 967231034 353514681 961763993 627903216 475396463 86589488 468654952 504658021 700153420 549596988 811037640 732508180 208262970 154061629 48107895 119113071 497521487 481585046 727762652 964762351 938512200 276360026 255892006 69840113 551681616 14627 557825289 993844416 135964077 214075403 661545582 758467401 501910977 881697803 424250330 251860735 636087833 44404813 198341622 337701604 764113673 684612157 505403665 420623076 599158830 822814988 685738397 944290923 758326818 404648117 97536560 160385810 388781021 263328220 256238824 712857928 596683293 200164996 89480750 523946147 745970328 178602494 277391369 726792654 492483510 316404644 584672197 109101541 714671645 164741817 270420441 782330387 653242911 894489717 522275160 822928864 170345922 942888795 914998712 473340358 798191441 262674409 903708792 430579065 949203688 267655860 901320860 965481279 667035131 437293061 521849062 642673786 179108083 654026461 275303892 200179062 420434671 496630482 482169601 420361582 347357952 745245014 643805676 115733449 291512973 100093708 165280568 432720970 187337889 736002064 956040493 303441745 695122921 206258088 899669630 413252328 312618366 961882927 446329862 216718239 794652072 984225731 797281905 431096856 809672089 510858559 635113450 776954671 205036684 426757681 910916842 828294027 429763910 983649234 937289523 758550356 69079463 700145999 321280671 373564376 310686533 23001130 565694770 40292014 410158871 362373464 361846192 960240009 753111349 666869917 215267961 698790659 787698950 956491826 665061513 961398017 553271217 392397857 209321425 469151088 645454382 334066260 14887887 858180582 876906967 811106037 248890495 285483788 861494863 933850280 856499132 582951315 461031022 417741332 675407138 369437661 850362895 721271889 340026313 789606641 69606481 536357219 594825674 23661492 821821325 773450054 527991408 647705250 626993696 987479140 282014407 798248557 464957830 900322803 568250609 198076277 482392273 686673563 650417887 474777252 748176112 198614469 646616034 710022780 425707606 835636721 621566193 74424935 695301747 541664467 918861516 449567623 504230230 975462936 692387921 438878407 304517408 159935330 805696988 89918330 803189444 370358492 384682125 818734328 815407959 762033695 704314216 623067471 142629112 641113170 835675601 630692376 259849586 392378572 938745425 382792456 171678601 413491019 686973182 585464330 916518923 93996567 856865940 686977570 231841121 250054082 873515338 988653530 357345292 912667602 492112427 230046464 790356277 431280264 537542821 419905836 611380849 652736954 832259279 431908205 335649132 906118167 172134439 189071693 519014807 817449829 486106602 105007291 911888746 418702464 632609085 505697953 998919467 223830503 904612234 986858497 472490508 548224123 467339454 911902572 346272730 495998871 886787558 897475933 731048240 93167718 225289499 829432450 831793433 584302074 170665056 694432626 515485 403390314 923993397 633393528 173658 819148083 225861377 875478092 587426750 381662090 758793948 201633948 832263281 233556349 419434483 129192169 971629068 872137384 708868204 102050219 659970234 590746117 83871300 916253526 801850410 689321027 84373042 956593580 264348501 586674042 582889468 544855464 16863571 221977057 190111613 319951236 530266635 226738386 770201079 16833611 805307445 738085804 151162620 356702434 95772130 753086006 402622819 209305512 911898923 27273925 476584831 125607865 70010080 367813707 504226816 1089856 763915303 653265293 205456571 303456105 611265679 693981528 450488436 369596641 29061353 722529180 105083306 948804994 779904115 785962052 520807600 469615413 259158812 232826805 247797013 743565175 212763041 549942584 854709149 603025260 273123578 978581585 717425093 677985876 49104634 614949533 380741980 719250615 26357047 440896565 864810779 398034984 986250761 329874530 984516264 644424298 559934149 466078446 667012189 190844289 909759448 985088146 582957308 28542033 720899843 74985459 437076019 750598300 383993280 894822329 153837487 505527187 33384501 196790495 99632127 96457525 347091000 859070956 755285786 620565699 307759669 995545697 148383793 15596949 431498765 815716228 693480296 185381044 375707609 860605711 342278216 659518736 544337375 710297087 203660941 125965018 681747392 627461272 940266830 205574520 919284294 489305274 83167255 724829473 898003424 84942795 968824244 173604254 727005784 651814919 39146941 405029791 562732849 732808695 886832392 284267413 362170117 453797147 281900273 335472835 135074761 155359242 433205769 763491880 834303348 676004599 961270784 779622498 14861965 71314990 32062148 53642570 504852715 856075800 941340598 91654934 373844618 245883736 113349517 318594347 181445937 676746020 930671982 798236041 17247245 813754530 925123660 30961751 600832402 208057353 249882194 266714143 153870751 319285807 273801025 917011716 672697483 852234605 243245510 485816965 107429872 987990429 308413814 215410116 859974145 431256210 627924893 302264383 799307903 99072175 520953881 996543465 629550747 223190695 630977992 334667702 268974153 86172299 153150598 729672508 784202454 573848240 169644948 790622137 788941106 778796088 250295863 845869935 366669883 863788828 841296510 324757317 884932647 164208721 965128425 837264681 686922978 581176858 807905271 453426188 443647314 56009433 926314404 583482217 12156628 4795550 496455147 572645156 943744606 288368476 61860242 105278417 770417318 340079339 964982767 262808013 740767125 564589831 61319467 121247827 370529065 376017299 937733493 496323107 356293621 680913659 698310574 834585986 50243844 522556805 737972291 743286599 632411702 404674131 832608632 126482718 257707514 642683407 66252232 755441177 678799036 297037793 339211603 38087903 511305834 915017908 465899653 930559916 405970362 668193230 804880634 944815936 767954499 980003593 511467187 450727819 23642301 569619819 77738030 342599776 858004694 162112850 698490038 177528698 243978269 529004786 610009359 621907104 775589889 249300047 796242122 24576250 508013735 952708221 175785270 534082267 76225829 145547341 397381291 660033153 486997924 707121252 203395167 144768883 916789208 923766331 488149860 706972870 843297549 673231926 711212221 587111270 855699903 564844502 535607811 947005471 764482790 441419616 735434212 208971258 90424588 795005846 884001660 177304392 248436471 208564178 806568306 457604832 694553955 889140274 425246526 344331942 252681759 758870649 321843636 53165012 827750427 402992628 782804123 802837449 429549760 425233056 828733663 640128116 130840556 741691455 878253238 890112141 812536488 788604835 572738812 460726664 316468561 685133014 612804107 99477524 791127120 784286389 495123508 492960821 682765204 713103508 28405291 370357525 307368904 448391500 133203877 690421722 311064473 963113349 382802934 916637795 387060390 53725375 927317908 836473125 915297069 933738468 705068771 581952370 485882225 425657703 522624295 800552943 6340819 785852789 679219342 529862331 935432278 57139921 514177850 453245789 448409238 567906271 876526186 762893106 795167288 544120839 361240540 367577889 315244174 54299565 363787516 861125731 151121620 32027459 785531367 360734837 582882144 842116490 836483671 563905182 579370380 193085150 753239932 778730624 684590555 983590886 862110070 27022402 118572046 218410312 767014044 602709105 220207707 240882475 476406497 197647587 24744663 189427820 981234149 66015588 976204020 823370407 486416212 597969964 677129729 8358747 934687691 38513341 928735869 507176404 674795358 823356631 730158052 211477313 253633051 386961475 514202941 669923777 145603438 441225566 519107834 428279568 825302266 477360273 432219714 935834690 265119073 596123805 565989164 625381335 448453521 241665274 404992454 153714841 685158071 406082274 139884343 878690345 809047543 261188021 752758528 629779782 730614974 957718662 977783690 251506095 836258112 75359997 547514956 875796077 123861812 107662436 527088557 547948348 570676039 374754042 736784869 482022564 404379499 516833260 430738141 132158016 316629232 396266649 549704751 351694841 197614750 483874401 3579676 291174455 344138643 619445813 695141799 224251548 361575980 515156523 647724325 631009799 955245096 542054124 253241673 29058804 982018274 266140331 948560083 868276595 543089417 169247659 825571865 40270705 625554743 807871473 783117929 717397867 185069773 238828251 472559756 24782003 155607335 870650475 248295805 656255340 559469244 856832334 76114127 62485669 949226779 341882457 442127035 262858186 210150346 372333517 908460490 758690882 875262993 132255341 646925255 377125218 220789393 293736716 380300109 232033052 31594390 842137070 819930228 954063225 381899173 890780921 6062017 855770105 859796020 677501477 77745347 165619471 698480965 998257403 774225666 562294001 195700580 966499524 766652392 493775082 227582861 64704586 886718978 567878590 575213238 11871677 293599365 778968120 936317820 514102069 9699386 819834758 4018528 640387961 2300239 361084606 82749328 494705667 721625407 806669728 344087155 613863484 893705660 373914205 641280225 923769447 707992300 237425223 560045494 45501299 744649887 631781435 356870235 589340992 6991561 860293280 250884640 311116751 350014555 420061614 625333352 307943674 106964795 391787945 992364829 414464036 316933148 193064391 418835994 310704654 393506084 448523336 600708881 690014537 105049784 757952223 575559927 792698236 47177047 999983173 431117060 686519154 875857112 793087013 326728346 151286181 146758946 143989743 133523548 630741398 690698931 475991778 302684893 853813015 679342322 98316621 156852207 196851104 671010158 854483764 777086239 862924135 334325090 770421978 971497088 431421931 211198167 751806726 159767735 788451268 42320477 922369099 402837012 682716332 558970923 244288908 447980768 6276715 139074446 207290883 307299612 246801332 404049360 632584742 649735109 500863313 131365794 773467608 284393182 503165901 188797475 864432976 146612589 587761701 687171681 749986502 113698126 724213863 410710030 879157949 300237328 980931260 477172144 447719144 27044838 190434712 699175166 750508406 549575444 175294366 957998770 893647757 237706622 705251659 912500400 63494743 999021134 662887204 334887526 83476422 130844484 14813488 858265656 709661653 979072271 634510760 164030035 633141146 250281247 319283931 933785711 93760652 841908202 379818783 11756579 455222300 814049187 138162265 136139524 755479715 286595051 622268482 23590561 503793049 110819140 367401527 874974119 406516769 247327359 166408138 174628376 726076076 219450262 15053891 959300088 799629311 495886428 323706480 424116773 64753093 251288647 513882713 605640219 715326381 857535958 958275205 816298218 165795050 542172752 964216928 271086618 241648479 984474796 560919755 652238697 180287121 500676525 283813202 368657422 849575720 933343236 234442975 117058905 278296660 946248883 99982151 615461217 625432292 408291453 109549889 201727482 146518157 256608217 220170308 814694986 879927157 995195675 119129053 903741811 150111889 592986071 884931718 23193234 586564025 69789284 243651432 308795668 889112986 622319890 701313395 408363819 468904743 390529971 635861290 343526515 285768622 51115220 766217236 720482423 253170149 430231706 280817797 845025963 583189323 379211629 634844151 279272649 740816897 805945049 725982993 180655861 326969916 996901075 167015661 693513043 54426979 615728882 185327242 250441547 458136961 259962992 696477578 736062376 230453985 113547735 726584658 936969467 831002016 496852665 616969305 723401356 183909093 788744787 707673786 662141253 793733891 101802713 200990251 711987684 115122252 392090006 599110487 882220742 931531664 614368030 435408467 81603907 596300942 243683518 467929811 311992668 98610342 648998588 463632025 745860681 263257193 848218671 568115396 319929354 175161520 838813500 320356844 439971970 570954636 277956325 725863485 707434782 224200175 313637282 383849265 583233727 739473579 640268880 581689214 716470277 586534546 103729484 171718942 847456892 735295814 12471714 867409169 440722166 416252926 168313259 954856200 49570684 281859886 404837201 924164753 256634465 60789182 773983328 962786968 17786302 47341571 329526866 289636956 196899781 773364870 129106823 721893274 996890860 375422543 754481831 106245341 427094429 23528779 797476327 69781223 327629822 606217336 930042190 262991993 983942925 85732498 919521317 463846089 978565459 980977080 97035437 626905116 614758893 471612575 815798141 54433360 297775769 957016564 581518814 794676987 631916511 996586858 647995254 484309244 918809296 800515942 630269746 755063884 973036420 570227917 925378894 491830362 658005790 814992763 350143035 94331883 521196698 389405281 373921014 965232030 125901536 968086024 100131349 542956978 866640539 659951438 940947977 687065499 527870683 955724531 573604790 730818509 800586793 100729422 658488274 912501165 215923509 745604461 990694900 262418654 527246124 498463899 68248770 12580786 361814740 257081864 965169721 777678135 918938609 300209793 724825177 75189156 192896888 588338201 908245119 661684850 241781139 52947953 38030881 400297485 771367592 134882371 698362170 987234820 693601032 918187006 793156247 428627333 493712710 255839949 575339354 370399316 169463649 944220784 341241165 20264482 260721649 547250976 700832990 286670852 121312732 89689335 178740317 198342817 709323204 658015753 871787659 352777185 955340213 991833059 831995873 127927680 141853017 520441014 350101896 75408689 384105098 278376454 177714240 635201249 47020890 944212909 689339648 26085737 479097978 663979493 972634283 82991370 626236268 560703875 575545060 912064237 76776887 821813520 795907483 522718218 128702457 532942383 516976813 972168222 999454137 911227201 138555037 381537557 207571446 271570649 122583322 728641238 334303748 498342944 771197834 295736500 16228387 261107145 224866739 643371510 864344702 111830369 646831901 40156289 898056656 501002561 191539215 869276029 174029220 71077228 564821474 710617600 436660673 434447146 138769662 533339991 532147589 940421191 584210608 848587216 63814150 858318311 377234535 830803474 385063758 371551518 772957353 870799187 420443808 709365967 952497815 354976234 195496415 60800310 804810556 676293338 814257900 112094378 52507464 777135636 509387958 249837660 540074198 516602979 67574202 841128294 244398385 432481836 870340433 674624595 458275958 843321490 973120737 655403583 139566786 106038733 11329814 512084916 880393131 510055463 826238653 120332193 621535969 163910914 654632976 565935245 131333510 600907460 85445962 562043518 328076191 418301083 871873154 701337357 744781751 759001003 159406804 534244754 907780678 339859636 144851288 384280124 791018213 272728257 784011374 317781156 226757064 902068463 831280037 324466562 181787566 367270159 763265619 846064805 386984136 442792951 961750023 615650455 768633751 797603160 723121579 567880956 178120126 284389644 645967036 72766220 605541310 705845887 487572552 245581438 591006927 835555056 60510453 164816235 255991391 198580719 834940810 115957367 377040321 145296885 714398410 504827154 917241379 881657827 461300365 897896798 127886259 182023627 420673615 828048092 318074539 724314132 590573076 106329084 697218103 724846732 557048551 442927342 573645364 883975415 369401757 728802306 366828236 612870787 421886654 973919541 942310530 17938609 961666081 649551900 121927213 805181871 340960475 447577327 172479553 420177789 727068986 671330515 226973735 564338795 659000119 58829667 771768769 299790719 353772259 581553395 92998627 827873879 43861150 984067498 825882195 447584401 871177911 604177014 18466413 696730653 368163696 270596401 191773920 262308137 116975623 521533988 567838416 327175463 484315689 787849819 814573382 447582632 747863124 375213660 846461500 813547861 970609942 915584104 389841222 949199513 564333352 995192317 70464370 988456480 615228735 415174134 172632191 427168859 54446456 441947970 216271742 865786032 506318495 75322570 800428546 523415648 557604257 363146405 17679814 369179124 551623943 749543915 647202773 217713633 399565953 193174379 770182620 137264382 885208977 908878722 765793263 336840976 515414154 876432272 953944482 728790595 940139381 774725927 362151034 901867558 601576748 977762566 4817066 363543454 320574305 24500426 104368988 558644024 498392769 357692300 421047543 881198686 984506113 204655724 397414725 824833239 419615880 194996528 325794248 437315647 60190704 27842883 121891823 929601323 950697844 338042559 360120140 655832892 824561170 97973809 459098827 84445497 675677223 473692322 582240675 244284685 445071803 671256875 50944847 201481725 330270445 974316444 965680528 539436712 848252040 262825160 850268586 871100535 140271806 93449769 147923876 487749001 945850484 78690619 417227615 914294893 90769537 932141224 864814010 794109519 878769668 974569278 747157464 408865069 198654351 117814732 541251949 195034397 290622471 124235273 85962298 745977680 891996102 675381472 83367706 10215608 373377089 350602767 799126506 586199333 843088308 78940480 211077762 596743863 16591604 434914489 182082380 804558831 510716688 604850820 763515370 911422034 243575627 418175903 133906481 662408188 157548143 621720338 68481537 136773054 210229296 446198864 207223402 325629319 687925485 399201599 225775718 445955976 688800725 997538964 285512619 978522744 801338757 687911548 157710250 789900233 731091865 937545204 533949894 788846485 497940744 319288093 97441486 723200209 110301655 598182272 923791746 571188261 347584568 511795541 139674852 568879851 770566642 871145606 536900551 457518230 26617515 537660552 139596422 50437350 871545068 136541588 833167022 629190662 640989771 556980581 715299207 252742483 894476094 724827654 34977027 997657026 984028762 204203698 56855335 185196560 297659595 505220351 405311145 710110833 127016511 1807431 748618561 49002653 660127469 165425958 943424377 39912282 479997749 591123769 64841112 537478721 865168768 382480897 50338202 998921126 334473661 912353756 510042546 818512280 965166174 755056286 541772824 849897064 589217171 631766884 273840572 707877676 823313190 606589443 158009184 533897171 57788437 124401014 426727321 636553933 658181247 926147552 822974895 998333482 858961504 183421752 305979145 708717496 836679022 956034886 827290276 115704742 258178385 929814992 896862962 895001730 247621200 367698952 902727813 394856084 450854835 378186610 186635285 637326851 686107425 743693430 287500655 393923397 605206898 904239484 812162471 986142412 759790124 222801341 935035207 19379246 984062158 51531281 170124979 179956648 758595822 673070176 418946658 308199605 989517769 849986632 385097578 362669193 285501408 849579794 446624303 275975134 464585793 420611108 28352574 116091441 166279188 708041231 996956958 216673798 892120732 329335048 292565680 46896949 99930234 351482076 2971264 420898669 568898366 849557367 238392352 344774859 735978473 773136675 588840892 371812931 291195502 226354254 708848915 994951978 653800662 44343731 526897120 297566874 965923186 679354396 13430516 175479084 297992455 49303195 676417693 431858574 531684833 870134315 690374957 619838503 610960443 744457636 884749933 854762003 646629219 839285383 197156573 807276658 315567360 591408697 281091680 43493878 858330658 556995294 567636696 593331032 533470185 158234121 234130815 73138355 786768202 441881919 517833776 219015079 108593411 338712350 394504659 859658500 594130193 652008755 566417147 877471732 996079709 204457803 767264376 645610411 407139067 309427624 891812618 406720348 518662734 417588796 872368032 936152251 559031146 297015005 962417081 41622703 488697255 742340793 510086256 313014756 746781997 357326381 161809056 729836469 925584829 500871036 626189846 44484180 721285662 161865172 146437159 795145006 814496933 165276537 936860012 423540819 25938574 600105447 469234292 822303941 898668879 492809200 646413935 212480463 206889063 394481666 809154128 549343955 335144650 997945090 130488290 410361083 70811956 707686322 651379534 395574620 956649558 528685179 87098707 446738962 154523575 636132834 309713260 52548096 525553280 812200824 674018025 238065561 267674887 61003998 760179881 732599171 550671132 152285717 263092153 830560919 239292720 39029784 428987939 676957541 160292104 450417264 904590099 407694553 516120902 301557668 38039764 32140599 59066382 373053555 764949785 593817471 345174649 969288563 553334221 463018536 364986886 123866579 492277114 19334289 725158765 20750912 568638137 346190052 505529222 261844596 38886472 607754100 920675046 286705276 453971199 644053956 960613777 260506744 343256860 1115012 223773841 608729050 31359964 364969655 280522433 603674943 967796641 500283302 706018188 939913609 459963395 627725754 754849390 734797814 686591592 537420711 76833391 508753613 551265524 118553085 359882633 972319106 645799410 422438312 928816056 245159563 695115950 202854632 47779943 778951694 894128272 780777765 709346272 907540602 329289013 141618123 141393267 254240073 522365739 182741476 363440101 746473574 332161019 567283860 223567412 411296329 387866713 3649047 883601967 64105421 238406791 369002900 748126185 870365680 106422453 811452504 7030751 326442780 661169374 727881668 339425218 549656343 885813392 574121703 798776091 865077899 128764524 892126207 261564537 477692089 691792317 671414752 614106120 621770807 478633946 697797900 383237214 260763413 967087391 696142952 704969796 757635788 224558265 81998299 45699954 321915799 713465685 814353479 555973722 382494877 949038943 936429000 861153603 677818478 790853642 716465649 235306553 686213234 835210990 206223627 208195503 629139832 190357809 487826173 193003119 369022887 550679626 402580286 272916425 41673759 685800108 885913640 674478421 461979379 428003573 313127206 261299320 448761197 377219724 608142014 144799052 72382184 703122678 289606833 457313307 832749129 60461335 355037600 498309353 307182297 195478319 926771057 428298438 635541205 593748062 659496348 400574232 126911669 803418196 918978464 656461614 104945225 594447557 148638911 319982688 89471234 674183157 869769173 229505939 755945769 242483154 935654834 155847724 898416943 862154304 436915150 836863636 867625330 181342050 501948461 153977204 208334408 700866117 519158759 190068680 776996450 826174828 955449728 932113022 381636447 418985555 800498947 380420913 384497089 348216023 149283140 263775943 121139957 122293768 481988623 370584980 910846991 663491900 622028185 895326299 602598413 480592815 521389056 24332156 305720500 362995615 520683672 581928289 238353247 242055676 626740341 881103942 132570500 46374093 650331653 906588507 769772151 728357498 286814777 688257350 262015652 389589677 629289009 991721681 459523241 261212020 260667440 590823873 514281883 255011195 708613557 61770081 599192175 701523108 996889493 187733230 725258963 238689373 87832415 178412198 664694862 118183809 362826438 988782148 385498786 352362925 254533560 562420515 92130410 259480975 515283886 925378873 851214724 865190823 270373745 295841650 741112483 651630184 173536527 76268964 12664554 719306167 123287372 863490582 28752522 984027565 978388475 471415376 974447898 449276165 6797576 862733380 161085917 622301427 76537076 588852173 858259009 728884998 286781896 401805572 972863892 871547997 309330727 685223294 474658244 430515395 963145949 782585196 752789606 956871023 399237626 926747648 399526407 887884155 370800962 319996614 813905483 367921721 664297704 577593672 359645899 812847565 67616977 148686759 994202211 39624139 432341066 99450497 734770409 534360669 673166944 601816709 618155710 428717492 776998283 474841832 233455435 572716074 152673160 599370699 321140042 880257225 226532174 717455248 251453793 747005306 551165015 211216822 971174479 377877020 585027336 102969969 651858222 97681316 868539776 301785579 64369363 674216982 108884071 172928503 467399003 607666310 87148861 512016877 601111399 964931377 541734066 328649943 313611053 32282837 539202382 139778462 893389836 32958873 128719439 272516736 259675949 460306474 789889749 717705938 506579419 875852288 61446732 190527339 556012187 49262579 973351776 224794170 61498174 778374572 272718187 394047707 523300166 22541503 553077068 909898100 989068187 909492832 536950364 706194118 617378842 8915994 816746576 24714386 891603319 920547950 369404417 525057403 19044083 292932218 199454418 730632481 176193497 155146894 954358289 974708188 236841340 491295893 695067490 839620968 141088369 246331941 615461897 842058279 971940040 601028405 214103168 261618673 645954495 859146322 87244090 646519047 565643603 230879770 748050373 131774210 104960992 939357420 380261824 791754570 685765262 941350950 666109095 164562165 178231633 515557893 477272043 947249815 258546117 62209771 455773186 272799438 954018972 102437341 995044780 55030476 567693730 473217574 744863430 314542852 73711342 789000967 139778974 705404546 75596221 239715699 929677400 796471568 607267773 920198732 415656285 757403284 289503229 464877005 363073333 915455212 824400404 948206087 169296078 715147328 905150690 769860614 792498608 927318523 596586827 417293213 536090550 787251062 847868094 988060385 368356674 289305250 146730857 274823065 987687314 823652571 729300911 594802436 493913218 882994590 965054540 227164827 163068766 98425457 375364433 328879135 63689677 831813228 698455808 185645494 607902096 142475296 194117801 448115156 825049415 627679297 34141472 192645468 633820031 661324603 182110253 72889753 548126634 616406120 729613021 226417956 509211501 181711665 752451106 355078919 673488949 61611168 954209706 418084228 238123514 268301882 405068824 420172222 605392413 186195368 754010279 628601724 940388717 228987096 626206993 668411438 294950789 689575282 321812248 69875082 188680572 350710182 102302378 443717155 163585638 676361762 91483984 449323668 300185114 269504771 375691547 110357759 713229158 822752656 854355267 552644674 704778727 827273466 969212900 308738438 721611878 806300536 701519506 782914648 884213345 323012984 177778748 98711472 68541035 776298821 784820913 805452905 44077181 396993814 657126568 698015008 119800254 345361798 951132663 565416586 335935822 636282056 203237806 753270700 314982521 510302652 248674309 764911928 546284140 959058410 381913088 26311489 673264429 100117944 349772941 977792495 378103717 51213092 767510818 387279972 794256810 526369163 264558414 152486994 273044279 754529395 174761174 204514993 390339955 334801332 182225906 966304353 261858478 742884675 950757361 331094498 5765991 202811566 17558414 277935198 36544561 818276108 504415720 770443062 655215984 932771904 722836299 137346418 498836015 347040829 581564221 55095667 491284318 310914825 472437709 415210840 712779785 726273253 382089426 911884819 388438149 694641349 983014262 403467596 223671454 657902983 137135854 367203414 427610303 466873297 313469066 697846892 174621756 189643712 756323289 308361331 284768515 613021768 154335710 679813969 952454937 891590217 8340198 953952415 980598144 26279911 226338896 319617359 545898233 997318032 26462803 674766128 373671524 98640648 493353896 21653436 168367472 829624560 621593720 991542943 689538572 342742770 819347352 459929360 494665526 517241799 759194554 554346570 262358715 305009598 572849672 906904548 165352437 404467166 710027631 562966184 44078358 240514896 728833052 545039334 404290847 70801624 955090667 195915519 689466511 153726220 799909656 579028078 4605837 972994321 866432120 299263330 587272136 287235239 839320470 432913805 20936031 114277830 422812483 391055708 325109409 86609772 541944069 196735451 321625790 306706649 898186184 816837457 943674306 800081224 665265757 113793075 398267747 979812427 637264437 444983087 957362843 86819788 272242476 686323654 302776932 580962696 719341664 953733955 550710169 851035401 518687000 287340782 637799805 824132737 128023893 632237148 672673474 667324208 857149500 620839750 598995164 933029839 674011067 191011837 979068456 436430195 547367129 988029429 310194449 133100692 385191064 382224133 492273483 262146312 153001088 651085836 873787551 136252052 357280044 764661837 256379185 834944825 722419464 850002980 985942362 248757916 976396055 272946840 134286992 108993719 453333648 996785746 556126440 843854747 884149442 681310953 675305091 234004029 490249479 110253040 677339492 31732322 690688163 383560324 544705199 748639591 136303758 447125486 235655205 598132324 655356377 757119072 719870620 344683798 26132369 252014071 381780469 158042273 983763015 243407801 86573430 864012891 919259534 135032622 896063945 361945830 992014575 533859555 352104000 909560551 329894259 135667686 467528033 445367319 970583479 659305863 10126766 722572249 794534750 117460189 912156369 223448901 508807505 489572318 47626881 956857691 83843221 946641671 608272823 248671185 490733794 842475334 526334341 605153348 722707279 743927193 701749695 985339302 469786597 151408355 312597398 14092843 214474495 791151468 317231271 960652719 548324458 19531638 149646361 601105091 215543653 174283269 846211618 337135001 727124268 692789283 451405973 856044185 194722552 311445802 290378730 271505951 800494144 674261124 211513289 121941942 290031920 115368443 525280091 29977490 581770817 868853026 348983373 778775493 55297153 764265110 866126820 133911 220360541 217902246 982994754 821357504 502860568 253553619 133124186 584453631 880101567 800910128 963103323 758865920 217824515 350725843 100597771 595688116 390815379 404432 237137478 937925378 153189372 747382972 286626026 77462266 228335975 420687608 730378131 545113136 544966121 838948814 569501135 105373620 422357754 741045732 259770129 14373459 175795251 354317372 600379773 196725666 222698568 687312432 787518128 701849370 680345433 383033812 417177419 747111115 922084267 754139457 877883574 737289090 554139800 944205849 821394460 365357973 544249019 824790917 692536263 431316772 243891046 677354229 633106491 876216329 832969252 99016937 766260034 465946636 788392888 117237775 477303141 52721689 211716559 599155693 387085260 294134407 338265038 580005060 97782230 388651508 690642657 507852772 516831015 636956267 123383141 124141185 95105396 515283293 250894126 583069633 902160355 443393138 530884506 567483764 992039655 268420042 338533259 385726183 742998356 113396630 173642348 234725232 116763994 192001110 984545021 495543616 253624143 207213522 191981755 962178767 662230745 329511571 498436092 570182270 952100329 290854247 858396530 480213734 891774382 254357998 893659737 504792201 639714574 740727793 190150583 173486083 207774110 648671613 904476993 810285431 68357335 219921374 98963228 724345822 886133247 862340475 855319346 524709925 943360175 754182647 363628936 315184399 278127424 350103604 914352247 396025256 459077317 206631002 233566667 831005243 964081671 389885964 493815201 588503838 930915628 889133916 436276417 255232602 897074544 128527515 140880834 288333184 359795017 185437864 68181405 926192656 448193103 742534577 308930377 668933646 439759473 888396845 627909587 220761395 905746472 384206137 529156928 31126861 643835443 122279640 60986983 343941792 767111283 581126846 877223412 718448017 817952136 236697189 918325098 431701187 922107634 376744762 524643941 313396474 608724060 867726819 874255554 468772417 812222006 989570264 671353779 297473655 475602039 626451323 969385224 383422117 296605287 490848716 645564476 45195064 256504635 829926959 741224492 609605074 6264787 962582488 700170627 986615915 319619059 230127988 405379010 322740857 776373816 905488723 371048622 702955612 632075910 947781756 69461820 378542591 992225792 316661468 529615831 43918874 589806304 895383149 72506301 644184525 790649102 149583298 4073709 29653512 385972541 492738243 360882959 912542124 133403769 841340731 520154283 254022977 698724206 944790762 162652235 917326774 979488362 147487320 630682719 380384356 335783704 288687420 429660569 959914243 183791213 358857522 731633368 882327110 44066439 201670219 722862557 239555378 987773473 805974848 889295315 867861532 402732972 241906805 981613516 269654580 237842274 171107946 841698419 533416746 837123662 896674682 998482607 70409334 749443392 145100342 726722610 972223273 315076456 758530095 115833290 634785285 12664860 371703741 544409949 618851267 559267856 699207642 363322825 337501735 681479540 862415253 487936771 241252147 531078611 66883594 792361531 457792735 407955149 184491425 647278149 276394746 677677424 968298061 55409465 832812856 772258776 612568856 229923698 310280135 123040374 769877407 170575096 797427438 484503858 917408254 516252945 149247025 542907874 445517695 570308027 785110242 665180826 449402153 646154110 772109172 624912944 649224173 134369683 694542032 699477466 221573377 601701951 696733844 103950856 61680068 179122743 377411837 655080498 244746176 32920700 858577916 771976689 222077819 150126850 429934169 922405858 390708027 722059088 186771051 863260239 715155586 384328512 510271332 683561632 417719818 216789047 385546799 926393145 475119066 584138859 16931115 138685678 111477192 320338762 621573348 851329203 843143477 924145285 750854725 316056879 289830085 486390603 293959718 389677057 720470137 806765579 602985740 675958356 325907530 985886130 377595782 878335205 199423930 65699901 837571942 453028205 833754806 494161933 63009354 403511748 642582169 382724618 808121031 331999177 134063278 25774788 652937470 665793953 874898240 492426589 212185802 800997849 635352920 813724937 165543550 782879722 169067113 978180915 983496653 230711024 976767000 927529165 443379529 606860744 33932095 470857279 491312914 257751233 34384644 967822027 922466597 768803642 468844689 254262546 476910810 344838144 889108266 323357622 175292915 355887883 880520625 30318625 649991620 392503341 871367539 699504730 773706363 226694700 243327977 850160043 376296554 10739069 394438331 421843172 762165507 750373007 638609315 200611681 528101863 110193966 117533871 285519977 761944900 241414669 386896570 982838887 2949295 579996325 830562210 716123933 856765682 571021269 193379480 157700379 935340727 628723759 939294493 649281188 315181881 402287229 294898747 477582652 413962197 542740952 623108299 935256607 654742322 514375231 174560007 621378568 199090959 217304950 802382743 569398336 920441119 379849123 735547254 254392454 558967073 464783709 406001005 351679279 438748931 937699028 132903069 479518271 594650665 74675733 632817341 904620037 891638695 777992554 718824755 640316849 16371181 361544435 354970643 870323198 336461108 740676820 87552104 328366828 41512197 802921397 159960979 517745421 868002586 146547975 704050149 462953692 731970436 792409734 579082269 721518416 843686550 344930298 100449871 76247234 832974261 246159116 727531978 600981055 574175374 842146442 207402613 731740473 787456708 472786333 796114085 405223882 775861690 390218321 428678223 385949773 792398495 436445008 576055885 699725436 590733548 995379340 315592201 290049899 614853388 395590615 214783364 875909842 786576577 282881490 867941772 476241302 728282092 560633681 419188635 954351155 65673483 613250464 730392883 460418863 349220853 407714205 213472603 985670474 867156604 672494491 793141445 682636088 291151833 178675249 259106950 219747171 985875721 708619904 943223518 488651530 765184032 522748184 150352586 160562321 110530949 161469711 450101929 815167205 3180679 490111550 634455065 537516168 452064710 799409022 308745474 69941151 337254288 126316562 687989220 801615156 923319821 823806916 112802210 576237161 64134004 33674397 577398884 887691856 204821584 362946644 847048072 476006392 353438977 996423672 323350339 840599019 510563110 152713594 771333873 4012785 498475133 459231586 211208865 346523616 629668112 359993329 13654707 478546333 984234250 704072432 85957163 757301020 870844603 710877259 72771597 45317293 645358420 582954770 310531280 778706333 592735786 402195811 556076631 216488857 782302591 722455791 239643985 630390063 393732264 19200678 693151645 577347342 920745359 488146733 283681542 68224 193840329 725385604 865178721 301259696 188265107 457938119 663155194 917665000 530316545 49638992 249672570 629464709 910889574 65903455 977739194 193313017 928982779 809789597 18960936 477166299 428548642 465624533 598366818 736305865 349822027 585438613 860864518 857344519 217257376 62166393 583229246 466135501 324086597 167989347 604210580 184979510 668374232 427764352 517724758 711247649 314500147 320769320 207785798 61464300 414018794 975120569 202402598 727716353 344468924 841554126 225603878 689015835 993748220 443047302 910201241 526044726 598411294 534318664 567029306 333454523 703687548 955916136 13477339 764758385 940349192 540723840 518002014 738048466 189774870 955875692 6655643 247430757 926748649 715884040 94343667 774791665 855016387 84554583 23403302 821825419 951857072 267176031 445578736 571076610 458024149 774492876 453176010 197492394 905608775 670519666 550051730 45483360 927123736 848134460 733688674 166628819 721125636 860704667 3223609 442654341 551904176 684340104 345668305 543524144 81759110 992257017 556991844 213539602 411512683 398388613 22987881 238810910 188389678 632870178 539457080 658625451 334814547 146204910 603870576 901846466 323165060 866703087 87573232 535468272 898086165 434085874 534572935 955550729 708782516 998430709 122588524 687548226 566933522 331408957 85052279 137046222 781567180 251171733 347754390 774906297 131872480 539941813 576152958 261465402 659144906 446913461 954521632 631607777 885889582 860636954 927294001 41206091 129505597 438485535 969544832 931420431 293595128 82096547 924946808 822434302 41126686 537743553 920092097 579916222 948822252 747004592 775271112 362829363 331949973 22021609 322666028 987142604 595608456 31698193 990027565 407357016 14649391 257077158 764428324 976269269 433514195 205213139 545077367 113659222 350746672 649372343 647565084 122931675 787551312 612132064 626127208 229439703 840434724 244537805 2478956 58288163 337287747 160779942 936659361 676269091 267335381 504399346 163360156 827166565 346685359 641916847 420472946 938560610 413396239 698636835 229337797 763252651 59009780 418960893 851356527 205381245 171329284 928408012 161535055 441632582 321555566 68935981 186218246 5360367 558156867 746976676 240926166 882284147 470006332 815973336 727158930 872841202 315369747 777222285 673509555 146622027 281234258 172976452 523731274 551243503 179792928 170698344 278306486 37308061 553648852 781761367 455660669 872590014 242050536 339975823 279004225 595768257 607894492 395119847 122788393 539530578 164918929 178418091 525050245 926402197 441084932 174784015 556033589 791729542 455175762 455728453 974019625 209117164 783033737 421177287 58769397 20353780 228041098 450244388 778499013 579917292 589141684 114617077 299699295 334824679 676903697 286304953 42191825 781173119 703223072 915332950 23946444 601716005 122910707 591431539 306801418 455336251 38186796 839084686 416011373 913355722 418220652 470211806 318155261 147721222 630455557 65203581 239570049 496170581 545084334 530156509 476533171 443550558 280296845 608313868 418749427 445595867 656088574 765986374 860816943 244755949 835955004 758156824 793225167 494403730 302316579 787279437 490509667 410963372 775388592 859561243 424465788 883305311 355758937 970552488 148852955 234811143 670317033 920161950 170620516 917248501 515657157 686073807 104631151 892470332 506559751 504407022 478018257 854198136 155939808 283186759 111556980 257439279 625011080 375943349 819595606 480573186 811310116 620968456 122503157 852331988 735917043 245831669 816398106 302892718 716330184 317324733 538369536 517351075 707641283 567073972 28399397 34768202 377806530 753352319 115655232 468075421 279401310 435879087 256673001 777377602 367182491 232574068 3045549 800151161 670909632 108007754 398193347 825494057 262697154 40898598 616756639 12379585 596816548 376176218 920587241 931302432 915624388 892789938 83016072 247795816 592778517 493329824 779547385 881920232 700996373 200264455 585749770 564171888 693228923 754451237 95187484 629898319 223908413 53252825 673603022 241311238 277212311 199426915 838872084 820395328 315685164 664358597 958447743 195125725 965734221 15585630 169844414 244217801 738303021 995267599 776002029 153015225 278370448 597460250 29434988 196527845 872675160 385763361 559257189 985850813 259272453 163823644 795342789 961565334 33918008 322950208 454148464 752672710 855618793 43604996 190688611 378814032 355068594 274358916 890459022 294345866 57835040 505495702 445616622 546693794 529974411 820766448 402202731 754053959 333127786 90047942 75249361 448995432 386147250 190197960 552406385 55721696 531921134 880495494 11590974 679588162 306464866 104411853 388716445 788956850 949030073 213654039 557121634 302964881 210518718 39160833 455766020 585569954 997056081 638816920 426378994 746473700 469878173 330095810 33104785 547722895 332899892 899554311 414617893 44514497 705985506 602753870 56776386 596146278 689431355 408981392 607611158 768971145 69341012 604860747 202772628 148730342 579197669 143844529 640620615 666517335 38290393 904542392 543367908 129132971 627006569 825793039 659451330 143364730 763189900 707539034 552007985 544123418 783529801 223685594 347413771 369136592 957504356 964849554 337992208 439277254 86438212 876756100 404735012 442023703 306687134 403486224 375033694 913076631 354130857 742164925 104210169 222001127 812419138 296214236 441885950 936959934 715050125 210202042 391444279 630202494 671444587 719579747 388120420 551181429 56501999 743383536 680783781 356690067 361215295 102907515 939142495 390880466 937569317 201924328 493695898 520048379 453298452 403322417 268983165 30364725 530909421 545887311 294886748 265653466 987695111 378479965 853012326 734808861 554610257 265641110 285190368 734077856 982929304 328470214 191137762 341778068 7965068 578809221 289894681 477135896 373845637 119384451 766872928 101418950 897848351 961407023 477616638 952888588 78080586 207780226 30346614 173102732 563397833 887289890 427972287 381954551 115639390 52895572 527158438 433513701 526385679 312085035 760007014 481613247 233766178 154869205 239789600 574466266 516223924 209656713 538212246 881728253 581198641 749877212 615372466 174735578 343422032 671898713 685961305 630344304 680609852 492646844 638639463 923987898 277853076 331131493 866290747 535292250 514618090 314060033 524649587 267913642 447818190 925311639 736803198 274246842 90934181 987424953 788624204 672950332 1087019 650354057 231989320 373018433 561159751 273487996 3878327 767041990 980588407 107896436 129967524 36893520 283916139 758851366 459474945 486240913 130115498 828928322 147781610 756427242 320898083 374124888 98069105 547282007 922815562 430611188 885948002 661936877 815980134 35031369 652286129 105028496 571536597 240834010 507598726 347089150 67721159 600881510 557926597 30005121 420967963 929382293 578934529 194121266 47620100 313520889 949673968 175267962 238439597 240578000 788426293 704264359 319732538 78595098 76441428 288111904 494220750 770670497 367580083 290517207 478340660 201929484 962900341 20678143 291378890 232336041 41505095 596347621 501910551 42186561 708237241 533331348 150034540 752677432 323557041 788326715 885577142 831608226 433691703 770908578 228260970 358869734 631756070 169092330 548665005 326614979 158426516 682166270 81301450 916699391 979007023 978532357 228481125 426029433 894662645 820598716 896821245 792771966 866585706 125318441 203403454 108451536 357369400 519340867 927126388 553983156 371430238 490451550 552299261 966604854 129656540 278298623 529736401 585444676 623220279 3335614 571905938 422901494 672877996 617762463 185584986 724826704 465606804 416313878 46409819 199979079 16633691 47550545 269586307 807356118 529324719 146547046 560757499 21894733 258842846 180820085 427981060 315783089 781466624 837165759 762436608 237148213 618472094 4470636 356475809 637645382 453071640 948035369 515242872 879454468 702571818 90362114 316887099 828584354 636292266 170295932 268541850 917382332 935494284 444792857 972125648 996706426 945876688 444079972 461794972 312821692 360543936 113793646 326174884 518445265 617919171 847417266 8563357 251573736 932171142 115409242 652501133 516535625 444813281 925048060 505018676 264512270 340906188 953199412 877130368 533025653 42675829 113680778 831271832 783428918 276945345 586275071 445295831 525603128 868676741 302282372 430205418 862768533 116103720 663481042 371386806 824901528 196670466 305533281 619570579 585761816 43064494 733044930 223253973 100115988 532295488 143834637 354284006 978244066 583035955 216806923 686851221 224980155 662167039 427094748 967874048 869794016 229581161 437735874 514397294 997867051 120413927 355592682 412009458 958059371 21463698 598374961 600144030 675809094 109023963 983452286 312729789 685751077 562187725 933484382 362699535 657263519 964730825 17801465 484263329 913704211 149238559 476065617 526586494 620685896 457581859 248252304 765733438 53996365 537145324 332871150 449408689 914567598 346964698 900824671 732724191 862433670 533368718 702463777 68826594 640986465 658061740 15928534 304301185 590989907 266236863 587732748 250676805 773035817 548674490 571034925 83907885 906462953 36396293 531667175 708902242 526447483 649763766 125835837 141981111 913095902 151972065 328933869 185792073 673441343 513364322 987015112 961894393 938697986 91217064 377760362 185242294 312140381 47478264 495724851 276148096 503764298 380682338 782527109 996295016 125109000 684356831 654729194 286209504 11493172 60438501 607767383 212299306 493153498 3040209 357876211 914763221 23127302 561978214 821114902 86128738 42434869 875987517 185269491 779174524 578700630 959087318 454965084 420622935 645531741 276532194 798842711 578652755 201256070 589185140 728038933 470576020 370390128 863760698 413339742 561121525 121277573 38849971 348271028 752544223 845749335 489877284 788919089 213338129 869271871 596305440 930566442 590264155 411039296 120412206 205773163 810957487 974104094 202492965 752421676 422329029 721950873 100257297 516831344 886028788 187074454 378254486 646010359 590298678 203380388 885437700 586874103 194517673 538819316 88271974 508024428 138051688 739343462 577382280 827151755 107106239 420052076 410940474 777431977 665229616 272446027 320721175 288547589 623641310 531710119 91342158 94665748 921170140 412998010 838585512 890003853 425249891 950118642 863548168 3424720 814149299 800209905 543693803 341027892 210686219 303719727 378112310 338094035 793490272 868653870 687160219 709372080 960565598 654858171 836689292 936789832 931913651 180272728 949980346 620606854 330256467 228220823 961645038 735357480 337056193 619670976 671558993 577090569 935973928 444241259 146614150 492725719 229203275 328255867 275371949 783170016 99890018 143786563 536558708 211500022 467045761 934095308 649170113 380365180 934967119 377743075 786090376 636088618 809172129 745187499 408526103 879420241 215463231 866007998 544446234 717072000 388168380 359884519 241228380 633932634 3814137 716627815 280190577 144428659 368857724 288070381 382688785 647533163 330828982 413113129 370896517 125151823 977209857 434172207 70888837 384326643 754681784 274698916 545854019 582970781 855292272 626776657 818905080 56352292 699490762 854563322 911326282 710955061 721099755 998279667 101238225 921726002 829342931 892939701 293779467 658372859 480786288 238061953 644635838 312364325 255988963 907762767 190914780 72694974 692269903 374655887 481488444 579201949 486391684 448314297 560635844 962243639 924209499 816767023 251840452 300741267 200593338 922458951 532630556 818893623 887701023 911129363 158906975 562347419 640055892 850594911 416289515 757191450 572878477 392411072 355871740 494409968 836721953 919039665 29092435 612388669 66522713 422454969 889963339 233487886 777183381 26677665 860427991 761100630 916022272 223984493 211829028 85969714 841533664 472974380 896856889 165570347 360221183 145786402 782807643 493639200 104932296 607626593 66387354 169146524 920637051 329967865 818520961 861429020 66278456 956653448 537958551 624845754 622170802 775739702 685448196 892698358 849208341 964733974 699940799 754766441 616894637 782171722 917520295 332607404 551161471 227919672 574459416 885957024 143370034 620649710 858771576 542549493 574653135 569794808 503253477 921247465 375458386 270264370 901656620 360080847 427006119 167437631 932030655 3045482 537930888 602034501 860821481 20662263 146529720 603190207 726542782 740475986 368281752 385660230 570330651 354868429 336964616 965845740 957011260 590473057 164912212 885726552 151170066 376370212 978698883 640382376 961750468 75941100 12029905 868326330 661160822 368296232 69210703 371827868 752246021 8925749 393928254 789328048 448872870 177969990 390528030 18251026 299865284 447258928 124995197 258107171 376213166 266462814 902714591 882863781 303053732 238783877 112629121 41555104 947242817 518763765 976058748 943976022 585314590 521347330 582001177 274463070 110560271 305419496 19870658 599394720 375025410 834713499 565854846 594533076 548034138 926067028 7858536 789847968 624785961 417764351 297992849 830122338 870134845 395820891 377002792 29498978 138980544 640768741 313463460 163049925 760714554 948527987 247076093 343190786 899474173 950501004 452368696 82659502 691685844 988948775 882198543 181768254 430940338 664910471 612030021 962956818 965565060 481835250 957863693 88256858 428372149 770689374 607324255 453210047 566258574 641100357 171982659 303469896 864159088 995993403 585670751 459598758 500209610 457909162 48468868 483479293 465930559 985228050 139281177 845164564 245503529 755722068 261932145 555133453 794370472 510874526 64165886 558163478 767348157 146739138 173635276 162061847 56116347 143658144 775154483 969249048 413496684 851067423 286313072 210670750 5648836 165682318 735966213 211203614 460102773 100598872 751570314 267803648 514910768 366416278 380535427 418092482 70563584 499254513 270998430 709528551 191902183 315765672 250490650 817372270 650208172 673913860 725391512 195198988 461190464 945010007 982557186 956379591 227237988 159470875 369451518 20566726 813283564 93940601 341482018 897434663 314788468 14093292 830536846 932319322 484048665 445400899 470267207 115553119 370972191 416161068 377700514 93750872 434008391 649698546 52844842 968624053 933134356 323022463 379294162 598654012 106393537 137815034 181488931 658725137 201683264 519213795 127142778 236161611 909348443 279606502 366503205 533280864 838689810 646747402 876154072 508931799 43771430 126007574 922244765 833513144 978677726 393663858 810965377 992824297 373377344 894785866 507139113 467070376 803174615 390673173 921302918 868666434 23741214 248420146 856835312 836535704 562554094 846508610 136946626 244624678 629846158 426791145 869070380 357666533 267231751 551633032 363054079 774005260 924197138 245618819 566909812 692312833 992253725 743428600 160951856 984598300 164692354 876765124 384218444 794377698 179345299 92993943 715302268 962845815 235045616 913895427 912213349 306296282 527803414 81483866 740862585 838049093 302614421 536293274 518039286 830917764 915694570 247282957 917408468 254850472 871198819 917297589 144869838 822099723 186913682 947176705 700303648 780010416 689427210 317418523 904438286 846354755 148732900 180374676 852491219 865343543 422797185 565197499 715821810 283195874 887927460 812144411 416108915 640354713 862431613 299002092 108561390 150199780 268330900 594105322 395426503 506046751 674398630 893897054 422581505 304440460 575022338 746253498 825434416 134978109 687846554 100572602 564970133 78858463 770474342 808432220 173081955 722261988 26388172 643163772 356043417 227727037 673355503 695040218 836979905 632339323 109309016 449626064 691162496 25652871 463032383 348383015 12152828 296211023 972305900 489018589 144453682 926285510 100943967 656339201 344488536 946057062 346413533 701105946 747330968 669802275 511070863 513106678 136198919 756303325 166791902 277619127 400678578 96601451 253915246 359258452 211334631 741149811 895638369 966912067 734976200 111293232 133090887 756381763 636303185 558864351 584356669 615067883 455651046 798593702 321313 61754463 495109591 516358155 12884930 322358081 899839432 854117994 302544865 392599963 508176362 296280670 980908023 151033536 319160674 84185420 817023737 256965595 883688583 616345483 883536752 297202269 713748978 77916448 955059481 920228559 498975530 835007733 474868133 546632066 902603766 631455265 18150021 8001183 164973068 158123449 415957632 447552998 700931215 783574525 103455966 582935840 798301676 997730030 805695498 274709231 449304973 221385815 286340815 294824846 352469000 537444775 887607483 935595386 555758286 493892799 945993065 699851720 354094313 311411076 228702635 855100140 363371872 430523957 671967454 587758044 505042928 756028462 956927401 256630482 893643570 915221004 816039746 10472610 880332625 878483356 488559908 244430853 145028424 227647438 735053410 189673477 778398089 696611828 831537445 735596052 542851627 814884734 615126877 605264504 151083809 78660557 648764119 847049154 17371814 526163878 665473302 81854978 901439790 586836961 826301579 555000592 637731113 326898126 41289062 510471146 611360322 303112437 490380726 416600620 349834634 494643044 25583710 231713886 39662516 831038977 266423525 143307075 155977006 815311719 164255649 347522682 7196369 868081962 247445890 555126709 259891951 52466205 384370410 697134684 316835335 518149060 956652958 800674843 90477043 892679793 411139235 166585234 301257173 905481734 472872923 238772395 151147035 155833092 609553765 976714617 825437461 175381421 547975413 778658889 414485501 550270007 742560080 488327496 318904469 544986284 613026775 661234521 732521067 920386860 808242603 236509657 650328633 813968486 196755757 808349599 498028361 999917122 491032612 690168675 245246154 599583427 721204180 550968342 665090719 208524112 758166154 703929208 621938361 255174715 130162515 350648454 27089849 528802096 105949845 439322826 318095420 178691116 857702477 773515748 950700700 365477734 450345362 269684653 364653769 927405000 252560978 351052457 465511733 29895908 708890876 118578503 12564424 317076495 328853788 502847911 46084317 608332040 145581036 767264011 867000008 421167749 572327321 375143174 665052120 608965463 175422790 35371481 158238132 777524295 265996858 655488643 763471590 177631106 496481965 588075037 985085494 772970589 757033036 162155038 281293282 209006344 370612288 607614038 320213001 336288596 955235004 999478537 712738260 530435850 772988172 703652973 609485604 430870260 775187753 860114937 202856042 153714181 656154086 783697981 828250666 832684742 558993614 435232893 115962886 468147059 651769446 512133154 395485320 871540975 194025850 604492355 325668903 339642484 208403307 758424067 299300811 145531698 557663235 527028742 737718294 893519865 816327068 21889266 903486430 589481499 192835360 93224201 304262702 918789947 73895183 846446982 454772729 685825264 979168698 637999994 171700573 681181475 224915223 994583113 649500956 6934826 183248665 785673559 95058189 160217816 953363691 607598104 249628258 61680096 417628847 491004751 910960264 742975465 326727603 959872235 675365604 198355600 1419438 630693003 608287947 74636064 307065564 167283604 712974385 534637609 196270590 924996038 302574768 884210910 484359083 304576739 134329725 763147334 219759495 523900015 763621088 673821437 159207942 672833465 982667264 101658771 576643618 369209103 334423307 320929763 644795254 129829952 363680027 296255884 94522353 199119142 566279748 922561072 936858889 975847351 397906910 856000423 912071083 559211432 396987413 948831598 152446310 291038512 300769243 642412056 791692373 724411257 962194944 115068281 730139543 827012188 75805738 225466016 378836574 328457141 572689175 846546280 725728146 509711547 670840712 448102667 61102555 867482271 271573041 196018745 794539334 783437648 59558361 174454255 20455026 107598809 855601662 212593336 436549153 107657277 641304726 432155005 879942307 324395057 695967904 410612431 676648473 328432006 863982333 87611384 650430234 843879768 461865149 214184846 294626467 866857363 719501396 884563360 818886812 499233310 601788696 729353853 90354252 207858012 552572075 681693723 706362822 183407653 648381859 879967326 420530174 734114456 241459425 234812107 160741529 27109491 714683711 439545444 779499894 963405228 276980625 851044477 236381209 844424401 620998206 52025958 356333695 723385492 252086495 802853189 686056605 815033340 371536177 753093007 411678704 50176418 915541321 90464038 71499156 530329839 70913921 468732933 79709244 942409305 35185712 499520773 289253215 531710911 506619627 553262667 447904334 913227067 994994598 582217240 166862238 951482517 458606695 149938651 733804809 678077184 733190854 567354880 181213435 663364044 151126201 914310902 272301488 496337689 288941330 123695579 526577951 351296605 687804345 482555359 367013133 326163525 561849700 179245214 375537109 681347878 499181594 671592067 233574044 888703656 163151660 499421027 590718794 793064217 394265786 999603840 394433445 683933090 811682906 114498329 619111624 384377474 601207721 497769113 226889591 281945489 220340411 408569048 388582851 635931502 321275131 802490468 904883708 915164192 540824873 844194309 912133759 345067890 114024674 26027346 316024875 40449059 798545161 88779610 600323502 101009566 206740191 810695176 979317446 12930027 103300506 148714969 809944695 192493350 40331390 711172765 881532955 911852514 396268236 306489639 824333967 334451135 561997235 908470851 891139599 445697014 308682914 157548367 523627565 175392654 681782871 251213140 509116756 834625647 306668569 352838653 772305600 905605342 253132551 768495652 670794612 895501830 562860539 755428347 146043010 767826446 941614207 969799205 379244092 118166886 453312996 672283582 160768129 796361888 369405987 666630176 212785055 401468817 487128852 311882231 77931094 6914161 392311282 152639428 962045208 397466757 636414296 399415799 503972133 237550653 815950721 995983148 190457393 286990969 353917589 754961133 923671953 465798230 775186499 541999974 302987783 394742994 391419740 405394976 573992927 524971888 847994429 548737982 19262048 83252316 368350227 630274477 985094411 224601792 465850825 987548786 776541703 277998670 683337233 142142978 983884109 524771002 892225439 16432959 771350276 67726158 673284602 464795950 491530267 413751791 541110035 616442955 255169904 260410164 281636542 423120803 923316978 380455329 406071498 201010521 853630027 930955438 650463955 987252424 702577015 322358954 698396875 888273734 536542845 604252379 466572961 17309319 311131072 697420587 621142997 116084318 434163368 967949951 44255608 222397958 824802180 352731524 426169117 473172109 524767024 429769153 827381684 446826427 372126400 89175984 965813082 820103933 402869016 110336535 781667689 787355413 729611400 963386894 542114031 564442041 560305005 236346740 975974072 379446296 353903465 918034117 674154489 200140454 188367085 288374885 110411715 739316217 643375418 23006365 519958978 377528955 543706830 782098720 188097257 906063056 963767886 333488183 259524811 838712572 753947872 582776474 764653468 572824906 302695352 202348387 520225964 300647337 223022812 55877896 892314947 456222925 454497195 812667954 434942574 481996416 779661702 686990595 363877654 406114900 709820284 596304077 640839527 853933428 644280702 768434783 263459680 510355493 341788104 414353407 626422887 457891990 47270165 27232169 865433763 815999700 944670394 39328807 61324721 785769773 704609728 847456891 998249167 273779918 37921083 245464692 933563865 498634182 692568223 951462373 182559972 106646067 998188740 808756627 477821424 224046549 327961551 385666754 482525009 221443027 415581804 309545976 85395741 653833481 589991826 868347662 154821968 601262109 41026466 726092036 922052404 353939072 529617696 655806912 454533148 216850723 681434743 984839178 483065582 996903198 949571437 617441639 365467212 960736133 562431224 246655242 660912551 893424078 185788632 850423832 362353722 169562752 959952149 118973971 361713787 955533274 774301315 201869770 289420283 738998753 467915999 508631968 782469192 678495900 705231967 664193324 269378011 111620445 320392696 470228154 366597520 204957969 279956026 247602042 405299830 500718293 603585884 426317924 434142418 501586298 547666332 478542716 574534002 461784278 631616280 298139670 698533766 883699668 764869162 749334440 967237192 710373736 767904201 957702744 10869851 115174559 588020317 624339696 134107516 11246991 370475543 894181271 678816336 751851418 217158565 547962137 150022099 444434852 71958903 608963418 710279030 852653025 189550217 56737742 205600379 272699574 373415962 252644844 355552858 801418902 317295048 13702721 51219155 814014590 788141570 435429862 681789994 158283359 70799476 543314527 763314445 857732870 656958509 62957242 529817227 779325084 741662079 409206729 799224113 520338186 321112121 405187724 293159208 19269848 819202526 738164413 780310883 259462114 940670863 160053026 651871301 188224059 122084372 132007578 90481970 365042554 82846319 982961116 408422368 786651304 655985515 563957184 73192837 632160903 503335980 916237575 64253835 375277479 766588624 882273528 325380030 187404935 159022855 208716440 748563456 73779197 208414257 147996069 681186002 372448807 640030461 66435211 216132751 157776552 768076784 818784157 205530018 833939885 965706232 721843969 274499912 861289855 490693140 840181492 1543028 622402189 209455103 218681213 911631778 528650633 544840170 271211230 590505173 812665605 304096834 295808267 203565089 652130646 988700853 89112449 688388343 54749801 108159481 429792170 112058721 887344793 322830559 375383562 127047967 765992295 99795002 57319505 630350868 724987752 581414686 718014054 885924805 479487258 339917200 201626603 817473114 1354482 677995746 653288247 686109722 629354616 5528019 664813505 239125494 570232093 788861702 608883064 127398869 559656663 289173179 226961651 208429199 451150534 301885960 930926761 527854628 317736452 794896554 193989450 135280384 702848497 74304046 335372001 759473262 370100552 12691515 779153436 990132688 591834417 881794794 774349019 967118356 714081516 675384472 497029310 779749358 867677733 625389299 486741748 98912063 937027782 642068456 90021364 314924372 172690283 37441362 38174607 166297251 462415902 174312161 172545917 503481522 986564224 619157300 291556222 755554664 432711218 714238143 883401416 721225771 872724391 96641433 292402404 323465630 886420719 323857866 960880569 650528840 136406074 408585553 601744029 360573030 527356894 469546626 98362566 814620670 961894687 432921840 74462727 368466760 755264124 816504617 581836634 737496677 576115008 748985377 964297089 559612828 911335108 244754162 398137180 248679238 317455083 793853012 312178762 174548065 582339724 76858904 424426233 984072616 821387062 967560174 479656370 197403898 839973460 249492804 291511899 440649210 440829339 19108432 150189733 391320142 238334188 698658467 239727983 368656091 93921655 857424131 812384718 463212137 342691071 594079231 937646882 606771714 825374599 86657052 998100089 603872278 880180305 168183878 609834101 563398854 229802995 131043620 727732026 896308617 652977159 575771900 943583568 564666518 160518834 378283978 176328545 715355457 911424956 318540679 265948493 99232590 712520262 838143084 221793979 746545958 620720965 171197972 607612753 801168676 302450288 39277267 43318137 705219930 584285715 128040898 927888859 866078639 875967606 55525156 814285004 406910520 789727517 200811981 498473954 989329095 298942068 977280551 980598818 392639332 349734322 446451648 211396222 291116113 169225889 5940586 655936848 718853524 635964063 463195502 254478801 824481032 661282254 536351478 883250178 877363179 457609269 83660664 507362168 22846894 131540803 876000899 684224102 939575600 911613394 372585162 891277548 719714958 162431687 214217580 540665834 413484400 369439435 735373470 213274353 630515872 828533312 519078705 339296490 443787215 747616563 670405415 353360943 181728045 443161306 35868847 339555340 17665937 381816478 987354561 964634046 266107015 392891158 966460987 630741615 135371801 188195486 102668260 211750660 226201724 543907529 99175118 348694712 42117771 656825846 885385083 881273542 689660380 921024311 226712754 976674578 407513396 302788247 882078120 417457231 814315587 185319859 440548213 937035035 267898677 960374620 878120600 232773528 773632680 245492219 451307670 226582303 288475316 39631691 516006448 322150134 978689281 235294662 556120540 970414198 354500494 989603319 953377512 482435691 86762166 70310977 404931164 334914690 929845317 384870377 8711348 868117469 239221855 712853895 547632106 299703104 169167896 195290833 532267547 925808710 255349593 809458564 861033051 447332973 781690703 219404808 175196699 843622656 601853453 544543243 314613337 946849171 841396375 565428341 652397957 531443266 298276851 497833494 741707597 352900893 553338018 175646882 457988313 436106026 117620734 17313295 700607292 216044256 447223371 41018756 299465570 746443150 331658535 276055684 815976750 708633253 530626243 958778191 136154456 769689075 5158231 354153011 361628395 696388247 810090657 845699316 940468200 719637659 655691424 330300467 967748510 481115484 457090279 482087164 836047179 844523389 78151654 231000546 315562276 631248288 588292956 490564804 485304762 832589760 830749411 531148800 795610893 141861757 349921596 986069301 849357787 819433048 340898728 503971682 440825609 672147195 86110555 788836801 476264303 574713653 289125328 914968265 705256299 940565775 817080496 684503402 709335927 142214869 694337008 333139945 442703900 400814929 50850348 834970658 2104930 331534562 631898433 635238206 326293017 478437652 305417275 938226917 487441139 880875978 264762122 117775863 813796064 51710020 773480601 351947297 216667316 15272685 190380263 527977791 362893373 944396578 991604733 986588797 680292842 441673191 914448374 544361619 452807800 562805896 822207876 931248095 499453198 470233962 573000660 159241761 839945056 984769541 667944842 155759902 426111460 429083116 74881389 313697507 887749883 612947877 985940134 691709147 439987945 327484303 806372747 979739849 463263001 877893045 34084701 683751631 240659005 93903759 996204869 278660785 252168146 920376474 776801372 455520904 45774260 557278685 729886279 923178988 356551575 323283913 694407012 57994925 58220288 857147924 566832221 348901896 532904047 804598771 857652071 683047560 54603498 254334627 373337219 420299791 53495125 261972077 80200196 801128478 261263116 22189725 672372691 991295710 191929326 349232694 292653788 770046844 786204448 817087631 802573415 547080137 347071177 143758343 884273316 391007818 261618301 232903777 437416035 572504187 25725945 19339514 693148193 846316223 924967314 54281353 245915277 622686358 200758429 633008790 809612765 704299924 277207572 733594709 704000785 102913758 46682925 743048548 978071899 905011392 345080703 182950625 940356102 695503698 429064094 812416383 887392580 752191120 562438880 280217549 185299236 385601864 64532867 18740640 300824298 612917766 103372029 108606538 10513532 65974901 178206 659610771 376027786 230066099 179640151 272629328 154420151 35738575 112264076 200170521 465332072 379409558 829468022 104158110 272159056 110902033 883376242 633410649 178878095 55520886 329165244 43083182 106216274 26095306 888666016 481883399 685561322 865238979 832090846 820500862 816738221 999172615 416187162 729245299 976538730 51370573 866027019 628554397 666193330 659713113 700780250 638681849 589558631 868266953 461032659 89368253 791263000 450340440 544171320 456833918 864998674 125817928 549488672 621143705 68147994 307684488 353294594 115495588 236971429 712557005 938134584 171600217 116569824 992660545 376237940 90401271 283670111 926003854 875347677 199279895 845024817 461476288 744078628 201457957 138765123 701370245 770569328 678591017 617933085 949109974 613418877 513982455 921896579 901642454 784796911 558522732 969405821 387181268 886039089 105807785 891140332 254271776 37976616 880340730 91528627 796589737 453686219 382407480 233905759 125934243 853654692 824886353 209320891 93438524 55114235 353043085 579887514 610270727 688466227 631561387 557783152 197652178 353617819 48365747 804684834 833149176 31336276 217758245 732603282 266490306 376935045 72161877 859275087 41314347 943788218 45431460 526388596 767952035 373312224 684999297 603462503 497163107 390020491 252019874 503992844 859439872 94624788 7973485 162050994 603627490 24295811 379511930 598748323 2904882 925566119 46347871 261343848 468461109 41307135 596455184 651833491 101426798 670155740 927743032 984345254 598359148 786107704 681820418 228131402 501571716 238001379 61074102 132754122 146474369 812693208 546089273 611889560 160534755 628579006 994340283 21810672 790838218 5728391 199918788 628273611 795108922 863582965 666090961 969107462 935506347 63010334 47468523 58430474 245943794 500141348 24440476 614405397 622670810 456321622 108705672 383607964 136367772 42754630 549754892 29990824 249788494 921241600 359622405 282721514 674229708 334007143 454770692 442405173 213822217 797382518 353980276 349015732 839284135 782926934 982662492 365318254 398777786 754082528 781757812 596679921 739547845 692054264 900052926 5156655 190101165 433814052 108239290 108918481 363891779 928307055 212021544 315535538 435776979 36784610 970316927 85037863 244333754 187113583 660552306 294036288 895129193 425751106 600333882 569389061 453725719 279818299 472909845 965471670 347751667 944846495 283177198 806392743 853038698 19403819 617803795 410922860 812397712 75038068 224657468 713566189 458591955 408305712 228438041 366615403 606420178 231351922 770524578 359799262 101252970 297770211 861285280 448733117 539790804 290923558 631862365 941677443 248971900 238113738 579334638 868915406 728854755 642176388 860823857 669781037 133478159 381996610 441985497 195644008 890581785 14070945 735742628 332515423 166972473 66034615 718270024 139148729 95870238 647337224 502983184 227089247 421999576 328155155 82637924 942891996 804588524 670963159 644817322 430497756 125287478 503977562 581475372 534809137 881317608 98975280 317075566 354639121 154775174 66956534 422198912 100809860 633813443 886614104 771127861 592838600 103107951 495654355 136137652 612390741 935765122 783855004 190713097 206786729 235734643 201765149 373045823 610775902 256475044 37542020 145722575 152359148 446389953 618418246 962152549 235754307 56718879 618735780 712214271 775602909 98506368 274625031 507407260 244181545 833430365 339677653 510993793 539905937 763111244 927048043 165980808 909733850 625273670 159437773 304190292 514920209 874648435 214261350 17312654 31759549 994424618 723362114 143433403 112680679 494440541 778707909 190622435 103156016 891337890 691720834 415646428 516404177 877709798 476710 718548062 835485746 44517317 989703374 186220149 356195588 280957865 121558854 788072649 774913975 961012514 500529198 94190648 93986533 876649228 911917244 572239552 895059473 832652755 59366504 129982110 631499067 721167382 273346531 591636730 820630596 642795150 796944716 666669914 453394277 77857992 812938682 899359750 797637374 479540543 951831492 153835355 214335346 917440138 951228703 854301225 841666593 786594495 863455533 252600268 904582026 900611059 454873761 441825636 701224922 291165753 655074324 706974051 542324788 65089731 321999696 433277442 932820508 569507102 982086043 859354618 284619158 477901564 597121749 761256469 342023025 576883786 856538049 434288336 229101535 432078746 569534393 605284035 416682736 781750945 50743609 592704821 527930940 201131789 274109447 182468533 910651835 695372032 296624983 781219614 603752978 502274596 525977296 202709621 519413100 273972950 100592499 7496235 642312379 33018620 794979480 962073815 825061460 993721252 765254447 766170929 689647920 211537070 625185856 478521589 770083785 830398416 394708868 988624883 486159697 856255250 763595297 808676074 931239825 715867219 412586027 344658657 77825979 267941952 749210040 282204329 496655615 902403763 428693325 99333587 847891350 341660478 106505588 141548852 367753227 997524939 582572224 570601206 41264060 648336254 836431371 37685145 729102669 245497965 883116993 993764310 600952225 111202129 379131860 174249079 396841459 441183202 76646395 376306211 923569993 426283896 457718057 453383263 50958742 388412775 668805838 116495050 762994954 179990759 523741007 756878884 87421428 290357172 143531105 371504532 123001422 22327916 628050045 642972878 504962638 820444463 218348503 149439542 867671170 26803598 752451285 787251468 278768236 497793681 663404459 173759136 457612744 128545794 645793579 285222220 428131577 997913211 827780580 256924492 710270874 595974335 622682907 43505181 548951339 985231975 322179161 763138060 916685768 643371036 574529275 444404990 230032420 748937246 56802964 511479384 217256138 498797972 13501073 861708794 801332793 771700011 145308926 86340166 446176028 10289026 597215011 545572635 270310183 433043739 845706140 340621309 902495249 417918656 85572851 383435438 21635492 989349591 180093449 524332853 691794834 626418771 457192651 823636534 689346540 696684286 717218731 274612674 505374009 246557462 650790262 513589545 120022234 983155535 801850498 305456985 368056768 263365139 957879350 279342427 58934736 9208353 181003084 271018206 134423845 137378896 798279732 605836483 458190850 763256988 390896205 389400896 420533477 490198669 34305033 950414004 141542385 421491520 885614990 48517295 355742128 359449463 278861085 575464307 419978252 356178045 674753433 742627453 389108295 708834974 348662640 900243051 153475967 697463146 102780621 478824009 922059265 483448516 773047616 186126834 449078528 40383201 952402119 586563944 727178723 787488009 692777252 928160195 590968402 77453688 448352493 973266858 711700404 169736368 22075480 832303334 184722830 123720065 667526851 985329339 249971554 10823948 487696142 919432824 14787601 543339509 802636829 210206639 439493879 948645693 482579397 103748333 25562363 381413778 187603375 92040455 279575569 210525423 672548637 209427647 567168156 915960327 333673384 943928542 315486404 900701588 355185695 559234648 252681405 136702081 977682402 374057827 753046610 564487635 217745114 374686780 398677687 837724718 46333651 52859529 459497341 677414538 537974577 329239683 257481582 201119782 210235715 352706174 48753968 463014033 773265005 597858680 889560343 195418029 949322198 641694350 597360125 743980290 837642401 325713915 471102450 246691706 520420914 709271679 630294324 846746975 467036758 795449037 883798053 330904625 736092152 96958363 969562585 899816921 66969062 172352498 800898768 142511879 984444053 303040595 886301079 351977406 529682826 882759409 188168737 894902854 369249534 334814132 570305323 660822049 895325898 747811539 600261489 670359270 780671703 710271473 981541264 862174774 977419391 632324493 891074291 779441452 232718351 532722532 491264293 625127769 781672150 293999454 569239790 436757121 6163538 974922339 595811435 533712522 910693653 119915467 630435454 723414715 468994104 845744700 294861796 748526061 791375316 24665860 418444619 643918507 754499138 917658684 482713466 298560358 123500327 29866131 50236082 854145973 184650056 836872707 584445471 234979301 189172254 254773647 959504624 81191231 440348182 993886838 288265059 248286587 388035332 272839977 318968650 970459216 141477803 632363606 849923590 38769683 992162476 61184621 213367883 532128008 432696334 511196949 123147925 155316556 661850682 218783514 111191533 451987902 997903383 63865050 116632127 724387998 637411868 103687590 270825713 473183010 660183869 393477272 985974082 799751178 484030505 307266560 670978985 451235326 559232059 383867943 53186082 603455310 333673089 404942872 190052265 650769935 908904986 391420267 765870334 457512107 794532747 562145270 699313114 855845361 126449625 3065760 552474225 467311507 994084071 335999791 688103624 92159821 794854635 888633655 2163536 671024054 979733861 377872294 550239544 839688124 148307437 303258718 322852559 678422440 907565709 301060319 310858175 490401806 865978018 999875819 224124016 103097578 929183248 833318811 392036205 137249391 276891956 895738097 812927370 373863531 791908736 355745811 48335542 628783391 171888513 229810414 498255556 536872081 118135100 265301212 13053440 320836826 920452098 908443182 773980849 380835323 382487069 327818861 604030838 382750232 525485270 425511882 548790801 662515977 199423059 455010549 47358894 759727055 540055921 890400856 871163196 647058532 370691025 965671694 956928970 249381741 897991660 354786048 625673951 787555641 382358453 644170777 914245873 752062484 285509700 676042109 580382817 948851291 688266592 672081140 17299162 553478497 660990809 630152666 43559578 330476071 934764187 208979916 467727187 407734544 496424044 993603402 691929036 941067876 919120676 757295381 941276455 321257171 497167155 226970088 625237997 258477437 948184281 921013105 478147134 866481163 481128008 407195103 249336221 826921439 504372186 791623151 583038026 938772269 398189469 64326546 664390694 42834099 478572579 475536866 433754803 535548924 162998267 602299539 761538979 815472438 188650963 410071482 984890157 842488517 723308373 828556542 994083483 110460125 207875903 356088319 132396222 63115981 927444429 270324647 310914486 826539122 183962138 548652845 119329295 19726679 463305554 85511539 893982084 301505685 4350141 435680441 75870076 709947495 332811316 21720602 999068252 464884287 992704933 27420597 547337651 870866099 518043505 167356342 858065330 83447165 862823012 347976453 361805981 300860374 118872069 907059701 840366725 503133388 476771681 149497028 344073216 321471277 376482223 635953359 560206037 995499711 502665812 272792157 411763843 298320445 110147735 147475441 655845337 258094978 887751435 129816412 509221212 346102086 148602922 672102831 367801932 104607529 725892294 824069943 707167983 457447279 976408683 303647116 822830544 899371198 658330175 953003298 294130672 605531516 847695094 448410462 231374247 262407940 586337279 453317623 142901168 141566606 698557828 430713256 202604233 527341946 935354424 838439480 69510792 436951268 333007876 265471342 242091802 578232459 109194789 279263347 679513245 601791511 782191728 547287002 634891609 681094274 308411851 114715961 309798758 94116077 445256196 211692837 619944277 390176248 245920750 278944262 34443071 698040967 346018789 343460957 823111193 283574736 649204831 713793811 328039974 732519434 318943005 333508893 757899258 64207781 901394384 621135009 924412044 287054385 142651062 468324943 899680794 798615775 351239898 515528723 193999347 976505116 852697848 70973195 684278501 3377901 145402432 274757609 840657932 957979501 625050465 235348103 389464656 340106917 423274405 874838187 937308800 798909498 149984032 386865345 536478006 231219227 752543522 754380795 821113144 365405140 252412077 185594668 414795255 137588208 474640838 96111859 869428790 386266023 212234201 581561740 454687640 642335447 343578485 761757099 815842295 889372559 88506257 205367289 808059556 580047675 549973327 823201419 230592125 914859636 913098585 570597802 305867681 288798162 853081323 899542043 271808390 692747090 34298542 181057869 168981737 783649879 486007300 388390903 878723725 532127127 706289100 4102929 721062322 41882200 137897613 341056722 120679489 813470651 767119682 662347492 285470827 79669633 547470912 805961011 137707473 770331639 607014081 273521681 624784142 518263965 186973572 52615485 160924775 808847328 473491667 303300285 876322641 110485432 159752551 688282826 948224225 589728694 830240916 315438840 418664192 197357877 638590667 808685236 661377744 365884557 446414667 427961942 52938182 158206508 632206795 401312909 905158778 555799475 666069476 373785320 415142629 608708488 125421772 15320414 693327988 571993529 500009723 337059936 826391412 809404128 240595374 683955518 949299538 953738528 565446742 89893053 178705213 699392863 571221973 755843390 423838550 133074495 199700388 518301262 204407885 900757611 894858742 635362027 267350403 8939033 334059403 346249245 483089549 432233924 400305381 188540040 586498196 777508792 299935793 991362066 67928867 680496562 520511892 151847236 114008921 684143188 211126802 454484446 52578473 328714348 622756800 774143249 410829073 532420676 12826369 379539904 931998489 598762941 825001363 40423172 986545762 117399382 104530370 83618026 104122618 107660202 520393404 986582084 455660415 846340336 823561029 980652845 738890530 786672556 736230191 692240037 277994527 678992670 608874858 191477942 893116447 418860683 836500184 785268029 243117271 968148421 758520508 156118952 101138502 362344288 724240852 675061658 648217119 67995432 626461782 538864578 810840809 803918246 330571210 886961040 387213523 635813653 975341556 665300834 572314066 450922539 561421046 355873876 209344588 867001019 246498573 816368142 840648191 384372477 626915374 922692013 967817937 77507657 760169374 726866277 653577110 188974761 31913445 213708700 88354513 420751321 365041453 475952534 617516875 758185936 789387437 197252318 985312692 620591077 990990391 85315288 385654552 561755712 783704227 697951807 525556222 58130142 199274803 526580766 975155555 451210424 781437506 518342971 183591511 367346360 884266907 484635634 232564465 246331121 347348274 322677651 907425018 866014326 128878084 117881839 657726584 96204058 686559801 385813584 722941276 673260956 116142245 880812176 992777734 245107574 3167225 26638176 955814969 850502438 364024271 191265102 920997520 204766365 337025642 511808988 815166383 255301643 548722928 472293165 289876955 647786890 957829722 816226221 809249503 168282030 865436050 496547416 236524024 354193830 898826077 657303800 907810832 621467314 228468435 917939351 880925188 794858025 115632738 252270510 635759814 773758574 365646913 397215112 215499354 199676693 409058138 497857816 444502671 98474123 900831488 812205830 626712962 217057265 968529737 764576595 90753768 587784716 516127006 591671430 808469333 117800530 15251331 967441727 272047920 302211934 576527466 783712315 388510497 607792115 930414545 629835546 209808566 904634523 357972029 605032698 99860808 124377751 797261473 233928047 237812923 390179536 530930135 427427237 76025039 570468258 902890514 682728203 696831167 90584917 245082530 570336925 229483636 34511934 69065055 405343406 638939491 741806117 527412861 208595854 309858070 701955251 450928414 338198802 893827873 980564339 190752656 948933511 13486196 45471390 42113917 70808361 322256258 971954560 279936370 798932850 950007721 862338947 851103327 412048920 722090425 129876746 735544725 516501148 937804172 307688380 677546803 727560797 205660613 429027683 415607928 941232071 239873290 782818156 41375345 835233026 190155463 656823402 215667718 189284974 898614866 695282480 217411001 742515941 353741678 808900049 956230712 1509503 768263410 39947079 410295884 612411059 876625797 313031793 282413586 248990590 77643604 158675472 252669426 435832280 570678301 300771136 280429524 295372820 304700591 427318104 636640030 895349841 693736050 326633150 623059070 954413393 159204394 868935584 355242920 743724850 734696144 648389259 724665823 327792852 131204296 404838347 527162234 358982617 66798696 863493795 342675694 357476047 522599428 561934824 290457975 667472355 197325036 375033641 130960004 895859144 593951382 329901328 420284160 725112053 493358258 989233164 360022387 337054542 852725618 444010693 388225160 496773673 389046890 652328821 781360611 755782731 303440083 675900478 327538469 226200618 623224350 810892738 78508493 215032980 712542948 504650355 861385166 309921862 340651489 468917974 452333538 725053371 845950270 401238337 466864190 523839966 666436135 786799767 453603269 912447108 345318841 87753867 58882831 413360851 888456469 186950838 834651772 853573897 760808415 758432444 409343424 246304115 296783796 569952256 238938736 831987616 949002714 494471602 805203513 905633788 185585657 454752117 536522271 630361580 50237399 292522162 507655311 297859355 996908514 4154575 185240571 368768282 837806118 177158527 629875584 415192189 806590472 438224902 31607259 487566896 524250898 363092376 35101935 773450161 702753592 908793758 856392000 700826405 533178139 129016644 781119249 458290752 328823162 841604865 729446707 886428484 38239660 737624329 551571897 405141368 982047793 120599930 407711232 928535217 368819049 508897430 800498478 423544263 690406628 900454212 647119990 842515996 181820253 712578689 324672332 313161694 720744338 990625311 802763232 85635497 804743995 487241138 744009056 881696685 101739034 287872386 696235251 472394734 629089003 287117555 477212280 25293927 758738717 657674599 486859630 106972120 243837404 305515574 235101521 887776286 774877995 619317773 374284860 716733862 441237925 576353956 859485446 356074362 409905170 896518899 440971586 983476116 405892207 779547597 744721924 557731353 28418623 798048154 312843069 330397808 412805553 890258671 250581774 54557758 807487904 263408251 425163460 938061771 271297683 54885903 115339336 151738660 360718797 831262956 853711284 454319266 490540731 983029332 448332222 359648294 732772719 681248291 999286312 933559481 164653318 85912560 345613719 176940412 899299037 495067376 884656505 950249102 344183785 79675788 170687438 790289635 739193091 341317029 337252790 381964838 256091430 31608276 162239866 815730985 62008290 121792516 1487020 113392236 285842605 259273949 927120384 286469463 46352092 422727875 740194198 962794944 535991261 355959604 553028692 735467830 445604946 135316447 605763588 668456634 5248911 800307392 538933231 172588158 489043504 246280327 613778237 925869551 979899056 896527889 446822381 619745965 578053505 596610053 988135177 741397079 959400692 915124892 464281998 319772392 117019661 493697106 460194630 512361007 703383583 477982104 901090472 883096794 293332806 2241914 33257719 772297552 735995474 155511093 50494919 285911148 872775769 183046873 933584109 25746894 62532494 571890489 155771562 853159359 14695333 161910143 542799093 620200593 241505579 495805352 645902186 826028874 554328197 241885649 125845487 311062499 868445890 889355069 718838484 536105564 470010123 893857007 166316836 878581934 614372929 212395792 930014391 793871324 120336818 778270107 500924754 779312444 852276332 612789666 729301387 691823695 439016890 241413107 201020953 854460097 866714018 602445811 93496936 608461795 746395327 502874087 469962563 563156679 564007508 977036584 408799411 459678116 403982644 313204132 669413216 762443607 333505146 827325122 655005029 861401627 256522106 910726012 259052307 764844290 756095739 345883339 890294176 72068533 599793665 370289270 581977475 342253940 829668551 388075253 414680943 777649670 897309349 711369731 593674858 262452798 466312860 299850423 208804882 883431756 28709888 314703505 571039414 915199079 610170751 459476361 179468781 831638428 568017717 58710253 526787450 165102974 770570334 282367916 18763890 161787216 517695201 379580277 447941652 946521682 479681000 982052607 864328447 90237679 706531184 520268378 759942819 304219252 593756622 332468294 780209347 455575651 323510891 650183028 25249141 666952436 17022637 64955147 625991479 825986502 356983973 314628046 374505238 15036589 995272315 781639235 24713263 38157916 12423275 30727714 254687757 125086956 128621290 276013117 665117051 639966292 595519820 55707318 28946696 238256718 175094235 258646567 29619525 521851227 50212712 313682212 596477906 241422823 419887855 321877426 625029425 12155710 215562670 32339296 66583377 519017631 220795828 993231169 882254715 677887192 758050611 143402812 923002580 542998459 302257973 706038593 108095631 305198963 455707252 595741811 706924561 320576800 443544955 398356265 515078451 805605901 379466408 73806019 174778622 182592478 248674958 823410782 140956031 261387093 776644566 522825749 799336906 491013343 182203800 338102262 151762837 536692840 322861224 993432460 779666964 962818920 544621142 544489765 172953629 681509841 862771423 129919611 381902601 738916212 613763853 77991764 563654121 134243431 441807369 749600515 761799680 457050 41120885 16862777 447997089 50127745 635210751 535337119 143681269 576837130 972908044 262686101 981487368 838227981 267652191 89560582 264114073 304496476 176336932 811996133 296869393 746022785 424750879 661043102 736205499 857047413 142305354 765853694 228985697 10763532 969153772 824106814 807205278 537770973 615151101 865421937 877329911 814437720 343438968 393252008 619253706 905597288 984337435 392422796 862483376 650562891 358023599 734637998 396378844 932431876 1348104 337716185 996419428 147311532 313302278 527129282 417824710 764860352 438631745 433510929 808086326 259208690 79521766 207345614 952209281 662282369 822896837 775716260 384493663 78727566 807392578 137185463 775852605 213335490 918950926 205146230 605122554 108198588 726016437 494194141 43199285 411733088 147745264 617142410 725565821 852289383 273374658 75403036 447945737 99120162 287912582 185636303 80739694 806991755 249073152 160876617 742696091 295580116 480977665 39548393 581043753 488166193 551060096 983381228 253039988 504198790 338057234 544276276 869472661 659370675 469610297 815120958 606896038 39599881 639208797 587148151 145706954 860434195 640580673 152017033 980818648 635297331 254467892 510795474 127950959 828795857 195153710 202167888 198102748 818709959 764106506 972821956 988642599 953792011 280803831 808725564 526410657 242570470 430874064 149827449 485863975 688994751 979654314 160143253 232049741 843881555 233717284 109238988 335429750 790354627 800547271 427014400 749529976 944782819 148380237 127056198 867859386 546601617 296114934 837432506 316859413 444268736 727185840 957026548 11017797 161515176 871560194 10372115 151763902 424288462 138320846 256183623 545220200 274281059 272749687 310805436 412262314 366353692 584644350 653094612 361255796 615374884 233740588 674623342 966622521 512196572 491176741 585976315 58482293 882446539 43455784 115005802 144581672 247603755 267017785 903919495 291540829 821327559 321139685 460780917 118699697 676078543 892114851 933116903 611889973 929721683 275249571 450319283 632246287 727492045 113300545 741032259 796105783 297211557 839821290 157141900 976642987 974809797 979854767 598670854 67248293 547264470 564329131 698843639 230217569 55702283 501939513 913478257 1188168 497236718 92715814 723950573 6454945 554061622 347738345 35374781 803019373 762625336 528757769 883963063 52408002 241038415 501397049 341166967 861598426 446757694 717390760 909802287 717156363 634558122 140420964 971351920 208678310 33820933 110361065 7261157 712348530 513585729 965775622 555994220 849450261 924891286 114469971 720231887 941866495 268687794 563473536 126505707 955354342 101809180 660777866 148085366 583329602 180930769 555206152 244478628 694886282 885932949 814304324 566025272 590278661 6014835 377750838 556877849 303294785 788285650 652082691 746675127 42007432 94538652 835702792 119885140 402623111 244265715 867518276 741586255 284892078 545224669 152295623 784285055 327246840 966053808 761865771 674056126 606663706 488502572 77961264 717653788 378950533 365765067 129087064 365102511 612244472 939606020 56833649 324152825 466167367 786229875 967136746 844161029 106968147 686305543 510365852 283166426 740444522 935531739 907882908 555231119 831492078 295047745 166929226 966402659 750501059 974601661 487326889 130417658 634302612 510131545 144712655 113840298 270818063 696690444 393939245 479422840 259103141 80033938 845914481 57538520 224729534 953298674 51065339 174636375 847533299 619358380 625655047 736561508 71945950 642363049 431922855 777584413 446931922 583087434 411698913 53304838 46625199 7467184 943962468 623824509 12503929 222022217 157371532 40713459 519919860 374153954 779641035 779791106 390311254 699353860 838609909 935227450 947109131 913292571 703061183 420336780 562098468 69271805 420845629 840938998 91108026 454237554 837080358 468888514 433161759 507620600 634682491 814852085 238969539 45951863 527311440 803130489 556803397 463487518 681562521 934509949 189719510 143897679 251028616 350121263 128469899 900649313 742930115 860415383 712312948 681660793 915170683 662698628 202798859 833897640 660989425 497759046 984121015 680855055 59335446 155489777 996948204 723381563 730014431 559338487 768289308 377603029 789016665 775981837 76819659 68344251 445959430 255429626 571845443 956713989 681776329 624052930 748958453 942975318 129901549 475675555 989169599 835463406 554028261 720037827 420805148 608169068 711017460 942881826 842660368 797207312 418002990 374956158 862429912 839307738 642642392 200785391 152395084 396947063 489730503 927355629 916719152 71153089 516395746 176299621 810653602 68905397 922007281 225418323 255223558 250198205 267662673 894424395 523248176 409593409 505601576 126568072 710695197 39814822 907907152 70153902 379057254 493473810 193823697 99488336 220336678 836442715 154260728 461358400 480597296 1396954 221912410 402088982 429568870 441301567 996850618 152108619 144662506 670324712 108301826 24943386 785270103 400172922 276961328 340489529 467834980 765759292 716073873 303463882 119956947 790212061 240998102 526738622 642220488 788171423 57638208 731069986 35126852 619461619 260517242 133099239 294453807 199613865 539258060 792917728 980246623 733629798 917092904 740431806 2972916 224492065 427968953 32105647 60292381 414057278 969035822 988238838 666988661 380947377 277792619 150015441 968021552 757791639 576770887 960925007 489759671 597804119 45864725 444165059 684959782 413305654 120722603 476470401 438328533 119605372 820733897 3564257 103576242 804231318 916308627 583740331 201957598 685322075 490333231 542116176 11111042 833151385 291050233 773549376 401516665 11657446 524504615 130780176 467279745 435787785 760412951 30996971 684328943 928612714 877725114 542404290 214028901 624923105 403374599 709702884 980355541 114788964 420828585 989333669 840231612 550079011 926109235 525065999 224170422 604105383 441781394 366074997 327885075 667811260 882921158 310261368 124568969 503439268 633309280 584053202 301105395 299274097 936109297 669458804 940530045 834128252 184122411 872956916 169229256 899436369 990167848 831322704 121278631 191632906 745364783 154873129 93696377 192427348 199022135 249738580 784361494 162946818 215208835 206504188 116590222 205932779 564610054 495016035 951265556 985118792 706365246 446116952 562255572 823957121 878901773 682315815 847333750 775218279 795408826 677812237 820094962 96492358 173084115 536353996 388399390 336502919 850653413 459231517 292301703 662353338 523620225 287419732 291308505 309473181 849884813 628998525 495960914 69542510 807820982 864308421 804003399 396255434 811586542 891651499 826780529 151910107 857208288 551593967 220673824 153610641 997946166 560039451 895335755 471119246 277499371 470763639 34835450 105167033 5946482 397467949 929029692 608443720 301218962 953619915 715336798 264617716 867100185 855722043 748011491 545054957 445796272 184412413 661268874 71312665 67492594 841499805 546318697 847228800 662939766 59106610 335507699 605839718 534604178 12901933 997417132 615473998 674432439 412971439 184098928 991708581 107276057 424275498 602225665 193863664 849011476 464097091 676587151 505385857 467647310 49988295 110443614 753848236 117145660 156158570 892483750 784066493 932732834 254098782 650758627 735338965 571921351 78228614 710758339 384608007 861460904 902115313 250576574 906632831 575061530 707617497 380628529 239285495 836161505 772691075 231886638 133030636 405363463 347902878 204172831 401652262 58785969 567208290 207470859 519403302 934467888 859694641 216307843 6618900 794570130 325072932 393371219 371622373 383373742 981810036 678999133 189369237 283368184 986296687 445825835 516111275 852020008 950164218 259949810 987086639 632299561 6676082 500190567 781025864 180485961 616920145 879331998 492960562 663890171 122028742 320165833 814787370 818325315 547993692 530589381 768010864 734165165 348394388 599724973 157855005 360817093 830104245 854623113 257451344 962214534 74827375 27862047 672958566 639702193 626594121 997160100 736416659 653376569 70479691 722388632 202514991 338436633 906873280 70342344 654329820 85100890 104276916 557099017 775015873 441397096 663488031 365060039 22726701 243573032 569726509 259285591 147889246 794938691 249080691 385416711 697345816 930131608 283725101 288986726 79542651 396605774 766896128 460681452 303012547 52278830 981865 945289746 427843582 35737271 173513691 490531000 884248652 4698906 723842601 943537190 844846593 360499754 255513414 143246077 908903290 473384471 992673595 60456596 243937432 498736517 153819330 572349260 840135992 154602691 69033333 656561943 981602519 220712836 46865936 871813749 247275197 250438612 656937686 829270005 667517614 468503898 104329060 213766433 968869107 555106397 465615774 546695134 684120737 96406084 77895592 89290273 190854521 587168975 100800234 904647108 379779088 903760757 541447807 92999776 185204034 164170584 177168102 879184443 957522993 200813546 635201264 360548443 894214187 566744459 917814395 291022743 412433772 673792162 920112628 320729139 641303573 488747497 281532949 736235803 175483408 727438194 845148167 923877082 113135534 562899882 210994869 638516531 366037587 651317906 790317415 517172697 814984100 2667755 792219048 311752685 261994635 873339656 291050178 952126541 693403037 84724542 968239024 860306858 931076247 814524561 493842803 114170021 743239207 709248410 304536071 215718388 317857614 133857794 668675306 845280764 739265087 303037821 210640814 914995019 135444580 281124833 52706364 999911165 859025707 789407075 528511310 698908339 683713506 479032077 752696363 896369899 730591025 896586818 337488502 944149938 921075550 910008476 416739040 604102761 632600393 672606872 162581442 669085853 922022152 222156757 76162996 368058972 340157417 835742261 821077591 278822484 190947787 797330933 350718035 575839932 689420429 191726955 796224475 554704757 601067930 965853678 744226098 439942036 765590570 559300935 476534545 340953306 54811095 244602719 678542642 132159019 438474657 595970430 789590431 753400169 613717949 367020341 669955693 676313698 845246743 635996669 70012110 952840832 832027039 452381900 236456119 887765893 146156651 207557358 664785567 92381214 276552810 861062396 778953469 849134388 180222930 61842246 658198129 75550191 519333733 832484954 712251329 485273663 885794253 914534782 831082613 425183583 784829631 318558479 945715035 757390621 22227557 367151521 841073042 100384359 755101647 765787968 43328580 963460266 587615646 412453449 994602974 604205030 856008226 32298656 850334080 165346297 502750402 364963691 614712881 38970618 687232111 392976130 710528372 653122229 376130471 314017587 1189119 425487310 446876796 634848776 377840581 20243849 559808333 997616665 322730774 434560483 795693909 271885468 435804527 723333135 280355511 557624342 631018736 762483708 675316866 910099628 65403298 495094666 440859579 648841244 71786409 19953762 600968432 899267961 637427362 206055249 249784807 866575344 366719705 423356718 699406241 541080608 119854372 876707833 56085776 125098263 399773117 605527338 376098067 193340234 643433250 704376509 862586376 799126602 86236690 21125010 541013037 117072176 131553412 194467657 450489809 400064147 201654060 671406995 754915835 889007526 370682751 636142820 495478706 366096269 394889965 246429009 110339555 954654252 393266279 564460323 914094180 276934825 66619873 740259224 652587674 403993609 803479943 696866333 144541646 644629842 439325258 244644762 920898941 438094574 32102444 99506214 994507825 809950543 338121879 714940897 595545537 980414166 499439451 56106586 162576678 236424654 328404899 944200838 216334905 176040134 414940330 923461800 63321457 541706119 521645362 768811783 663327341 518287231 493614679 939960531 629080418 540682437 494949519 259702159 741312203 930977202 957528926 734414635 681884988 44532166 718375633 155215549 198171946 468816732 294474774 478150808 672629001 140082321 721998528 424475098 831874055 720487502 943794687 375227436 696047925 669306691 306051444 485385657 440598937 252567389 474259163 506307902 747148858 705491750 55983798 890587144 742498188 66394437 89270370 801279826 592538144 757850828 742932317 454690155 601743243 727261877 736060113 352118985 305158308 995342234 505877089 526105586 363793298 455520198 555845886 793151388 112382896 569229910 347269826 346386520 91193292 60023522 821098626 437050272 416392215 368013823 562823290 290191424 769755921 588507478 240185725 272891662 636929088 169891991 728634586 795628664 212604074 53381350 853887446 835895342 218626718 561901096 720457798 980074212 305886524 507155404 592986823 910362250 49802694 392765020 908651612 932712370 548329905 536702162 576144944 612607093 43304240 599025238 420716800 193378791 92821962 664935034 661637013 416857831 419695625 773287250 977533646 146238798 112435142 699608200 51909173 534190343 418364946 26856286 171914546 643706705 396985325 208520542 852656841 450173781 198749161 983075703 363650677 422969397 791788626 963247942 337716927 973791024 912710354 134320659 981523130 484207104 149668887 390213631 688851461 896086285 312234404 854354060 856361560 56501349 871949843 893174164 604625167 343101886 323726896 980220217 701524184 608677956 549066330 614823200 574513693 853580117 606215998 185704185 667088632 942885716 410793812 636974372 613727493 154174906 528400476 383111662 761707471 515910538 592387326 341951537 198306301 10456176 990587868 214217373 887377963 112878779 14602253 238227666 828249779 959097593 642064672 916972377 998639028 641171519 520496487 541862247 647610270 114782616 333782437 343181609 614978032 538473511 968113969 811284322 821109135 401655908 735699123 475651695 23748666 547282907 492189049 246591690 508272304 108432283 846473998 29327154 82995145 471255159 17826155 338785137 664431285 989441355 85014757 463850487 402632947 136503081 651122937 86020659 279678903 429285417 279940927 359506649 900883434 702428285 720682729 300845741 32666458 678549390 925259879 199594165 460253919 923306751 782501633 490160661 990917630 393596824 552641461 255325906 103151971 593047775 613165605 979673470 656839069 226205350 235969366 902850797 658291664 382091873 449647720 789094508 874284603 870290608 257552584 828273218 767290041 845998873 75423156 227982938 834840232 783438455 279487393 439161454 933593926 517335404 290810460 868984503 420855284 230673859 817738876 622993499 133160011 241139377 532222773 956735132 459893890 601286548 661775140 501737579 539018963 675824912 650622810 716102730 45045563 245377778 619050771 159515505 414360221 957216497 877125797 46443443 3159557 741750979 940896354 884784568 940750378 942095362 980001404 962144554 361215283 219106191 96539271 514389445 14099900 557692283 175216025 944323520 132074693 224645027 239885497 310835364 345133249 158670485 2052407 841203961 892233790 191465573 503957816 859557837 721287726 173455558 277159599 7531820 920313415 401070318 907013474 602267587 844022923 11911841 348346551 174925900 325802086 523412676 932356494 673930464 545338235 377317164 169208990 681222263 776602439 107967919 880548424 805461591 620192754 751029902 925058308 728057733 26588899 533873770 704917912 537608013 950436919 75770927 938928932 290156632 272098499 751437332 421817874 322429039 633997416 797295300 52491645 829442842 249597660 437128534 792217497 891555224 637309415 784943067 253532842 267974526 830520563 385794747 775026665 400359555 623264941 774719421 74411845 845772982 857312338 319683733 753667671 843536332 155251172 841698853 77547399 515080819 970380692 416568083 532814406 319226823 825886480 198461354 163825330 831320069 121228917 354677862 361673177 101594467 295280711 255292875 174656035 670373218 277439842 409374798 870020068 513625322 573751562 803883964 11099561 309875498 564862394 654376240 26053106 88975543 384768708 789281015 712397464 278920732 816550674 399322128 188063878 580717500 737303459 49905825 594063097 731897889 794392952 135210873 854729636 482941707 576698865 515448806 741060892 179571832 352810901 266619148 840866741 123133535 247142247 480889323 362484008 505147571 802824106 476027722 865661451 448703672 290357324 31021935 543350368 982430797 14316159 96837922 348708029 168412311 838753047 935715223 592958532 161861362 649026018 645455415 150907959 938961209 447275008 482987144 768392429 341419117 89652946 735500923 522989098 612660855 932582298 446978718 783376058 392242932 315797628 533103524 177751691 372556200 31895782 252255711 432090238 29247161 26107496 502472859 754697596 973059986 530155288 526701749 903314474 471427077 867597370 486870046 41844205 623211317 684494962 595460674 104652836 392335014 450381609 387608777 141296505 738796543 196404001 122950296 660488898 341041252 888303673 499027021 870349565 231987494 965314659 236586810 562623696 193621982 987491545 259299446 211901975 957354451 122185206 863339819 823867149 581294555 275827502 309621474 46833852 735154221 975511947 971933146 983963111 774386412 206253612 630738151 253561163 96343401 740634365 702582914 781847488 320589556 116660391 170725317 683926422 931078168 233605912 225580479 827354870 59395518 576499520 628841540 960075203 901486385 253114820 3560417 345034466 655072749 857370751 334301122 791689203 238022695 673055050 250399823 274949049 349316912 628331880 137201412 408029756 298593712 123922694 586725951 230598076 401559557 193989759 843644710 483977167 194032058 713556509 201481598 394375326 815975355 929077118 188334148 815869492 134191677 841528181 610529241 200305617 377334481 552498597 69021513 208385472 236857633 980404964 515968366 960536705 844655098 425149374 473733170 685998599 112271163 453938183 28180649 579257717 743526795 456786585 524779801 854325635 214697456 173082139 597176450 755371461 815628384 22974145 235972786 744502490 637024171 205639747 603613856 147726744 778379449 858796152 958939461 691836656 887189149 995596866 41052651 543786550 165767876 996711629 877681979 84004330 916098127 531243174 618625651 684519196 257795817 119286539 129984296 638357455 576651278 143654853 847464849 554570834 391780545 599077222 931910282 182267711 880207219 121587617 993261578 537859067 322266860 651434941 615214484 14779598 34530792 862038629 751056732 994374816 757031210 6536356 954524537 703991126 343645585 681896608 431476653 42459131 776838393 94029321 180156810 145013627 973243082 323899425 820575037 319086962 768676542 813580166 685530603 167300262 422681019 816867387 22557618 188510708 938158758 219895684 844683668 761358293 45348373 787161209 911329237 638675575 104979244 25175526 429568086 663528493 122275667 250946540 886152599 569890801 379010203 575418641 517406462 85202960 486064497 68285626 69577211 141094180 179890522 20615658 460200546 439722596 848526818 346082511 557647290 53320148 703155284 458560556 268176419 69526055 695668793 437835136 190431563 360252286 914582171 446686029 191050697 942496166 938735060 346932769 201801128 819330461 426293129 795798925 641961829 430256841 178272812 536713576 555356686 208416105 499100157 47523071 227741641 139209262 875782681 31008339 437076373 569587776 55262878 116721530 967774273 279460847 951012637 125963090 104931598 998564956 61207713 296716741 791344203 578068016 236326732 833036562 87985953 927358995 720699839 40092605 233794718 682456585 251522598 549118305 662471665 439078966 922782776 958209906 427298137 248067612 526440202 688742877 87706303 577601417 273218110 755229849 489755616 740400799 73801144 551144690 34898340 476750515 108345596 795594048 574265634 880593048 980212975 157598279 849236740 714770943 744447205 597575317 228204921 896389012 109989805 616298884 878894080 847928001 184543648 386917348 578065012 970826633 361313510 266824391 654060739 354730877 715459601 827531327 45255529 669195944 578539178 666095306 405304139 48953335 89893967 281555853 900356898 42239925 173004168 671169957 116587192 697124562 405613159 961160050 338853775 384071458 706657255 771144733 26063621 259536824 943871678 256032086 318839540 244102405 586016539 456037197 697630528 376579661 23856109 610778454 149956517 833174836 471040097 640144997 739226453 362972549 236589248 936142970 213011516 143120012 621337282 863534803 34463610 703769073 657284406 92489238 95482293 499890509 772257684 488754163 446798924 416658067 111666627 864166489 362448852 804956512 242730233 818977166 178236311 740938237 138791215 625903994 227201669 688588387 855886096 607593792 533521589 468243887 697695660 712964534 550322255 878444338 401210892 546332945 666730294 685141787 217431441 665500816 99980093 763949614 976895679 847132205 956913067 249480544 654785030 133286846 144614671 762371033 487306260 393066635 875514833 667375103 340432255 727097682 248040353 51832878 220612591 782392654 37310015 28773287 805019711 187103024 180741418 280687454 410484113 288590553 320359879 824463225 500124870 71091523 939925255 815850700 174682069 468353732 467136859 988544519 869467670 175829513 180780295 161228776 669387225 717594784 979926997 454149874 840553619 63197910 52496830 136870060 41172254 301557834 20124330 447794270 474530037 876290018 495322372 134194880 836103418 75297928 790182517 271238100 414137656 853268706 218739998 720633527 381218235 59798217 899848634 281524603 21771911 681599257 304100739 193428067 786699232 764949971 785025795 340393010 340429300 190955782 782470035 274055309 403718971 647436656 865769386 830191819 958006106 104980732 353688927 213022547 825179391 73862688 121953379 715454276 680051302 486800329 161360800 168578116 693094163 581837225 558413649 459650777 299287798 273004330 212915537 700192788 709222159 499979126 586600553 357075873 6470662 687149273 658145809 517970207 633997178 853596504 629294114 749533659 44133003 948884289 578200494 495261190 209155330 270745686 832569887 758012416 4714060 371626033 642786398 165573672 928595388 600879733 506493863 173618670 343454837 16401410 837422042 841412270 483263471 535121984 578887355 569966098 346496010 762449213 861750232 131925810 210962974 850237385 327682379 634254563 738674914 946840672 981257690 557802935 299743223 989396131 68640901 122468222 885217904 684477456 110176280 317242681 487479552 61686779 504408519 681143703 915672143 13051075 917419965 716193615 608483254 712901680 378249061 336244315 278323852 199950721 682717565 720785162 851666124 777692292 45445983 346432274 152346254 631528571 209367488 13541 626901998 775115760 581031596 10918251 6787991 619529702 612274888 251430448 926323264 953805189 390864286 7420354 842593234 247264578 471578140 967276882 48333183 471586718 899516161 940472978 454313769 964590518 651767670 941647760 1721510 366944349 778988309 988310959 62915232 462685795 430784515 905127252 425916287 630187907 618924343 989275087 523795357 59265177 257142490 484653511 941509466 777030043 161837148 341353365 64298303 50039367 286913224 181214535 801424717 225093516 616963543 749898501 315228268 491180387 45868314 543079685 288512888 635167432 879192297 144562874 905554599 91588341 227339037 830429233 488252608 634103441 354220181 100966820 639823681 482757571 245022587 661215271 787513008 375019659 390144675 242381511 309986738 299645858 368788025 811487093 301533272 518569462 438660149 899965407 959906536 286094541 320726430 463075921 629707718 382239657 377903589 359607647 584950984 664793745 239484529 962827489 99235563 21922310 830339018 978595746 226163773 123953348 914808620 247694519 121998281 96037853 215059759 907419356 892815150 182282786 39213371 269963050 267383270 196688706 638965027 546333950 777348559 44956012 184059937 773527800 318579939 328094166 162965217 101195823 704578798 378899681 599224465 897655901 465602127 761477525 241974678 718865436 173762525 863675720 720485810 436852970 126225219 341933388 430891301 95408600 964244274 387006889 470746172 735552096 918025259 772424039 945203464 850044447 706994206 598940847 595576690 833421758 999329816 296596240 34107354 624475994 426830409 456125918 465784278 37970468 322464467 617047487 718945636 590476837 6734703 80269600 713279474 58928168 843852651 690140070 468428281 751309999 496001024 173299836 752223141 351836714 535386550 613982377 305255316 137537016 540889181 749363862 280438648 274686526 217939527 585172168 916996728 890445678 493726052 427375951 127998610 378947235 905200240 809206290 530183052 635616771 286885356 87275060 989724153 645738324 101581176 421336589 621271662 878262287 570131641 744074051 681216559 619039206 84956392 50057911 298812726 29313638 164178253 371022993 45188811 286505948 954171594 257051929 200291388 822562844 638911821 742551214 668168571 219119616 929993557 887474792 630235167 358903456 889757475 460644924 905207924 814127351 565071525 233257954 458851816 923123748 125265169 308657776 860044927 737201822 314645358 415763583 619126080 129757821 860967084 338748897 869605085 679769061 267565839 141194090 769751657 284315026 53751816 802870188 812686360 804456796 814869098 7673957 632268656 737117075 116546148 151602433 10777674 613517677 276035044 860896832 886927281 804059925 776100900 700565931 143231069 795126127 789379693 632077643 793456915 687422972 363832618 497677201 828002220 815418792 366892889 28898082 25812205 502344458 263323076 765288245 897631016 422359165 530403017 987697093 164231981 163646763 272055763 992135325 670161590 68154313 424364533 98668886 522272945 738922420 633018287 49093372 383728426 170422320 248946503 780714200 343159384 780329024 40834493 539781138 391336651 218160594 932580361 805509104 324519335 611651790 187691710 84149545 665288788 285671117 54055704 504088829 977306335 568353528 693799515 827080286 126826296 554302230 876560823 345270182 939623859 652256682 789866512 21673116 215570933 483152602 781323400 441453308 332799566 670437173 174123350 367806167 863558956 165926078 829662634 714042101 112829043 498460890 255372689 571645476 578753491 706277617 477349001 122421340 313936192 746384497 678881137 802180710 679254178 97159378 475976117 25207110 161897841 408637738 354805554 870035714 599358813 136553217 303641368 671601850 684142326 182453499 760834084 947039319 912497037 902513210 983031558 963325329 368468939 124885038 253254220 291041308 860969643 167843152 338035108 583564815 346303095 905887758 549553670 171993123 833564197 413631641 117217660 919138576 108055101 223256727 666518857 738198858 380691504 856473518 362533672 234841648 384662597 145507821 256672625 439111573 739624534 973522199 44551786 622521143 909757682 191815760 131803838 740380178 380770858 134859881 780573000 101397807 718323038 230344581 307930842 225245947 458104053 635623945 159865064 973080015 247483300 209974205 607394647 424905607 557024173 751145371 637698427 52730044 446582642 986101889 864814831 312795000 799034098 874723322 845539739 775169789 248257935 212818919 500972056 148006685 654108379 640423675 179538165 804541289 925791359 563512728 984239671 262736419 420709149 705910416 519556499 133560364 978219262 916357431 357970642 719116147 330198781 160831251 35742478 1809801 792890936 189351076 550440980 326465089 259422707 162916677 702149992 939871912 222407016 79085831 636732531 194303884 161745523 479251541 869147387 620754496 353091856 513227619 866199332 571704657 472707756 399483991 424046234 17482102 595829469 162572863 915372188 826472316 689595734 438491648 451652760 457225120 767713531 668681314 727376917 588985835 226873899 62366051 506659086 958287551 45195413 126995079 417308475 870096409 393234889 837759702 682192336 569199895 255011575 251323000 625681828 823760254 239626077 880523588 257260056 635108750 148150752 497437496 876962790 360173594 800590516 607087746 260425219 19003523 389287340 954454270 551666170 900068666 232485149 703087454 198819713 705659853 621674881 113099047 277578667 459650855 947763996 387641268 448525955 281074959 400384410 942334468 700173748 195720377 703416177 926265714 90785998 223230568 669620434 401844141 755178909 130186022 615719587 203664956 6652609 561991357 246409592 489279728 735443169 683820473 936200477 955470120 807717399 719925014 886477335 344427787 802419243 525903558 792823598 107084282 271576078 660241753 791729667 10184572 881901091 643689430 435248462 127972486 99057305 822401581 485694314 28460036 788775205 451953429 779557134 368377697 525352062 392391513 261961065 426944019 583674387 327505709 724456527 648813781 868303207 596890585 626976832 794767354 233259147 974151543 649631305 911039710 33292816 152998222 231950043 509912496 1698712 636939535 109894937 767596596 385608450 493439444 795373747 513418701 729110392 389740224 732859754 417793591 520336256 61716402 109520038 954562896 346190808 768377965 4482719 986626684 832547141 468118708 430492785 792859656 735062930 46591183 221644459 94472406 646217470 82790603 351812109 576601479 477303578 905618587 318124885 784331060 724150429 475349392 160627844 870661141 315500998 583074682 23132030 135305994 610054247 572843764 278431590 221171265 405898407 336528455 904700148 729056101 641193933 68458416 151542688 4296723 529710471 909683624 919546813 260166684 66940258 148952432 584666767 230202589 935006549 601018882 453941874 528860301 262422468 444801925 623061756 184579818 993853679 840716440 523244074 767609948 181178962 461102798 864802886 975176905 119268338 435950421 219823270 796292300 545516786 287957580 672029365 364626893 865854436 155557967 281102064 128769845 332494137 16952967 679386525 38109823 86383411 471262776 352396965 721934246 697978623 898599291 731932293 60014832 895394026 138195914 538089363 957492406 861112978 176043580 729181402 923041185 365210800 966556319 199668528 81896883 765833784 428661952 273705856 305477324 363580948 627097809 561525728 822352011 825632314 352040753 506625870 19449145 815936069 240430711 652296550 583962883 26898627 540905316 316036738 354702106 510377499 651279520 195026277 491356591 653692037 473945178 638566201 748995862 897295480 201716827 470848778 101356257 656170432 269514588 809876586 155315885 247597561 944355737 722137367 326528908 585814900 848966706 882236920 497772078 672820131 885014200 992816801 322145449 956635361 590291753 390884137 789221227 114179413 700839994 100138264 518205912 63122367 847634196 483656932 592895459 432306758 772701888 715380270 330845895 621248936 74478492 96869652 970549141 646775433 224046931 410258318 208217469 177292909 857615630 391157269 909412089 175837415 437235753 960535080 137110358 46475862 250555151 203135072 241577410 48642067 462389670 741332066 980080064 219291512 522584663 734309324 873744851 331899315 688425658 100408909 843072893 279751604 663294155 601981409 244176368 21273799 28782777 216705747 317014822 987809337 380500994 249198432 710370381 646609589 51901858 112967996 650520453 330486750 876058778 493203403 891959210 946659260 726453848 207566675 421593069 464113750 292362457 571337812 833924427 542145947 548493361 752414833 508364636 543894994 185772568 289733538 258032535 880627252 756607387 409700599 784650532 290813373 100704378 968497669 252823473 593157888 646208742 398177816 369906746 976503850 33392315 275288741 542057713 54315673 421661925 757646322 736209745 398948465 64992642 158434093 687570582 132919535 5020026 404061587 290585040 53652342 348398167 617157479 440984188 625656730 324397178 297986106 125943374 859262543 749593604 866517208 923803710 632378235 599023334 843637142 108868845 203115582 92103250 429867712 154886316 449073947 758324879 182648815 763151414 554459083 184931383 726718394 951819506 576005504 564727392 115632125 822390692 207624700 78825150 588256618 954936834 447805664 635937315 756186076 446169484 391871519 212416045 729226820 510237321 743613330 975202300 749264060 132193926 51633645 18013818 327504694 121461818 312441952 775263232 78860580 844491577 651774012 799151723 582621662 116388351 755659597 454074999 194727857 840083062 54640113 276471440 639251241 913518288 729833366 407273946 23610256 310526131 607261001 152719627 593167534 842895869 943116357 122023773 929824598 202915562 770294653 569583735 347675479 892424389 840863498 210907833 256241727 270289587 417569513 626041902 682817665 116088939 24621071 229467487 512433964 245990329 680746089 395282352 14648512 864505328 977503098 138933217 381627470 549036542 557710804 552320457 374145173 475683115 745421404 808524601 635799103 475768897 619742685 217691495 769045753 812035988 562030797 259544661 680732022 102844454 841813897 388850984 916148139 162802740 402261715 326360683 763691168 58244797 704051248 519484546 350433127 817005972 993098275 349599933 609522503 543040470 606027044 9837474 125565774 657979414 780885571 597515006 483210094 60875293 466528099 393191120 181456184 111613604 740385035 32573430 386606728 756437798 702524599 893498180 672626867 941625379 641825669 745085182 780741292 358536335 415879609 789450560 704035342 618614082 785443911 53122873 979327138 85758032 639990362 174376108 917065421 513220730 791010680 376466023 930533296 129002554 638254491 785760430 583943762 118851159 150468187 546379763 816067913 248272071 841772290 355092088 212825458 782945882 369223442 545227678 81641716 162110857 169140315 795078651 400956197 984822666 775878009 84997841 268454077 98169562 507506472 298621030 432726741 652246006 783861867 299539961 460411684 690672649 791603029 696475091 819411873 999828723 729301361 205780580 228965061 87240488 661197717 71943032 689169143 463426615 444431261 747123004 999664861 310930793 651594025 241424689 293575992 475110935 484806641 946431167 381534750 469094474 846964962 611515175 537527328 21432069 897097022 10483694 113381780 611716351 923457839 708831867 488766086 988338817 623254331 67350908 64180042 915070636 525782843 991787384 789130488 258938534 846693183 653009156 233344563 558833085 182740026 114801061 939461305 740651998 539713415 959436702 537632792 713059759 438354344 732510446 395575640 687529468 774492168 992021010 352313345 114788936 446624303 479826791 472219515 116326773 677817065 907235197 728204085 657797885 345063443 967373074 659864037 329528909 423096068 276324379 740253867 416891437 731754292 973551427 910066417 658186877 478565539 699943807 678428399 885461584 59234837 536998207 94555310 118162846 589355699 532858303 623470297 92869255 465105506 93496177 586561035 627839460 403091889 44488441 995317782 967383864 800583668 613848009 838565148 521781716 783010788 501099869 297689112 2669332 716246457 649845791 107223047 812977266 523568822 118087409 668956026 685487286 924087779 832553758 694001273 831374417 550636845 281106926 519264082 808880487 26146147 200225621 972694075 675419616 146676181 107811880 99876902 803645712 445854408 510722697 798171683 149824423 722499585 391060089 341872964 769550168 289325479 936937051 876514625 758182156 17953449 667699566 285621498 955959491 173034612 882424797 265873607 426665916 698510721 949850526 636907534 480834135 819193103 848150696 21891799 957214290 761496220 604459511 281229161 399812248 507240181 714657453 365744017 232783242 882361189 933050266 154080177 305019229 743005227 522962206 908744128 425745667 69692059 558406325 478968054 74411785 805543845 501070341 263160064 456845451 423092592 938936088 825689794 238202912 206279726 584302952 195879329 200594278 692140456 546913897 686083235 896374988 230476492 902906519 534400144 895455186 859327425 558226713 515909358 659736348 677457689 769730726 247932416 455912815 812320102 613235472 458915942 166358006 657227343 453309517 633964708 1638984 432918871 773327169 592496570 846060103 463706169 295814423 326924298 932579579 710974884 946509789 310333492 911372368 33986178 988277873 388358363 489040503 448581624 23408767 904761902 10232783 28467578 524631281 578669233 88273148 115610465 762730675 217033853 6869477 118594845 658404576 508677884 146043816 956173976 313186187 731337706 263645190 35296797 987331913 502356431 115310607 610884798 402547059 64830407 555170719 15290984 818536995 461772930 692528017 123785479 589685339 86176782 665908669 436895369 737766682 198469573 2066769 484838853 748177932 531901125 519715407 609782268 235300883 241730935 836531949 333526021 323471253 250055637 979471989 477418635 419566160 794923460 993434855 979289101 466882905 445132127 67816555 702683267 624482352 580912767 657404614 757276933 623799091 750708908 183386257 857898611 18861640 69517397 878002749 424073883 810930897 893642626 177103510 527219301 857286060 805154489 474746583 472347469 812522105 845596615 684399265 632334543 987136140 725534905 95785410 345251616 843235348 858917962 123251528 658399816 800685953 295216520 285481174 849351547 777612913 233724756 148083519 267139702 654074573 183664625 641092504 116391105 668615970 1003863 598794276 169892414 510690128 480294547 465176147 537960211 337117922 181389389 862193773 887607171 293379709 970203353 76502008 86816773 572747068 664266275 205433528 647527021 799484528 633348690 891954946 696082402 114209431 794142408 575772637 22011896 810224213 373915637 283781739 381347626 948292929 30479802 514248274 362966808 750692198 899821286 73036932 922752535 970937509 579478384 675298883 638927422 442813995 892937484 85992318 792444478 475312550 297241241 308242779 472648184 81349111 267039605 899453195 480486332 571180367 983908328 269538046 710072070 648454751 26400925 810875152 624536872 154681801 980418857 615516819 895697488 221920001 48794660 301364852 731806856 306768679 488819350 426411527 741030375 874324813 846493752 73499087 125972455 385308299 821954554 971071765 383710312 480856530 479866063 283364642 739665478 90230697 965329435 835880810 976634424 983555468 421572571 728445687 188917897 350085170 701655234 733267042 930387648 930772831 801330543 9693656 271049506 103534863 557626995 215473070 156040905 449729125 624021863 546933041 310357721 718725169 206740421 385855170 337933463 713946357 315116919 965456763 143521483 928605503 92873312 834146340 338492060 964027773 929296895 992386341 319422387 656614363 980742279 737030769 141676370 517564340 341758514 997366611 589150620 651062416 86773968 952121153 602683339 607268784 530976436 188489614 975944816 911735836 105552375 930047660 243600658 182900491 263732493 462663131 642809661 396040913 811589847 151389264 330446200 468536953 161291095 613686691 169860498 245112875 617657035 653623719 882363887 421523379 720153620 348151077 629564622 176589872 268582070 215637598 818730253 881345826 236157160 232774241 495103602 810393383 559769043 55738940 138379678 377938902 820093271 138305498 942972128 654994479 365797979 454562423 319246139 766437203 558954823 683821386 270782699 709330524 97589022 273555307 282076462 94879596 749619222 145486332 201133848 358555917 852273748 737969036 477024152 685573919 365414029 126575156 856166977 18160002 165258479 80523872 639043221 458503355 374066485 679443640 905020402 872258502 787882682 749230461 920991617 891685790 284888441 880621944 824119013 978730477 910713491 428869378 352683722 685046856 220176978 47906102 652948745 648713555 885715477 977102116 603638695 551232793 404975498 186030531 19276095 468009261 210683767 59059467 536613210 589890138 41400404 363206235 412026035 205275112 889383435 993356575 707291073 58867207 705269444 46175464 123115720 57639001 987805394 272184854 151276890 615461824 941444016 301759483 776190845 926227110 582514351 907764532 657189361 20942094 745250193 474277285 26939885 740376419 154754894 51498004 471433285 665057884 531471658 608677153 54753761 207061506 507854272 741094173 157127702 96183828 481196671 620789224 241500888 347406712 436332663 675589073 5173349 685542888 582892412 354458336 645867589 506625097 4203365 122531323 179217223 172346074 93402441 722808454 990256440 907345889 480148964 895036072 184417781 301681813 797210944 563879589 46777198 711202356 630324158 193291433 420633719 812404586 902261518 88640922 560873533 22763411 59935536 44379511 350909394 493320496 487822968 209709080 747847893 930712247 936163499 315872554 571731792 672597619 951631508 894960374 229336059 378441366 879250665 624757655 313489171 401156230 353292739 433731043 880279405 724023573 544160052 449554290 744912838 756026033 187801178 937471221 11260933 371473197 293529621 671220724 426771293 706070128 820086771 608100830 863013455 629642040 438485300 511337994 481362971 401182550 963437912 37651810 865175146 336082888 332489585 47932901 589966377 885937024 263314716 888511741 706270569 447126457 296279061 140065472 145741182 34641009 514733665 592062592 515839929 638855940 536024813 184609699 440605702 836999538 218748391 846948868 662855786 228181457 475485241 946821544 847598002 899115586 401106263 42145332 7361330 862228127 487709890 587451330 199161665 489430305 8833851 544789222 850859368 999854383 441481459 557887816 502541034 563936199 79214426 933314315 540533837 738872265 66485729 370066135 27628338 715887691 241601562 692820859 235754442 890656746 252641772 785187620 114700996 735512094 802644038 983637370 390522203 366737688 243052709 522950127 542756279 887344543 329064068 184314387 820745787 366979434 323150013 694280886 227783059 247394162 601925142 307321013 632688881 7039899 230045289 865329883 583840235 487996578 447961912 177679176 325854401 858035273 638462932 126700588 774208306 681813668 332649430 711005629 133158606 80468205 649258921 754923885 44740301 627566348 795715953 401254215 493571540 492539438 177760447 999051673 878357375 351111233 913714207 673395236 963987821 192408221 229491048 373905710 96600387 69047177 311772414 843442893 335917244 441493761 23265027 58754936 271304036 966373709 977125065 638081693 91675647 3698045 128039588 671353387 73185473 391873425 964373816 912459491 195145096 24197281 254113628 198707062 864178860 168376200 684104515 555913637 408325273 541565120 830574830 495500115 604072920 35061671 429836339 820860314 838567339 58175089 743237730 88898783 830819150 20906835 571771306 273126217 945720500 806913788 996486721 536309580 263459101 233816010 86774944 410660492 42062932 703715816 623101626 212284974 993115424 270877563 657963225 983161277 457026253 865809754 999740868 746239419 126291322 77330323 253397851 515886421 179582616 230327316 6644744 957398500 264013750 965592307 896978752 427224924 115497810 950034870 805494394 690354153 132625927 524122217 205052963 353886625 910734894 346021777 400878192 763782920 707644005 829465421 464582793 447740757 630341017 121569836 277577771 776390064 897479474 971602622 304818046 931158843 144426014 74575861 419176843 877377535 668719155 454105753 492290806 968708795 369735544 273225134 422061438 595021195 90290898 835480496 637981378 358926414 231303277 586141287 366083075 885894239 965940241 854965732 103257612 350775919 352536883 320699318 298291295 231616011 796216443 960216819 248143715 511705548 547404294 68386000 4970587 849728599 900285022 515179569 413448217 424983496 176276417 852536994 61439326 63748089 664158207 317953913 406529037 967766953 134257772 913153493 861675785 406973728 514895721 512539715 733177310 264774934 570515097 817779356 433007829 916887008 155735713 825332971 500662577 219898561 196862678 412262749 837939835 905908632 395631667 597621904 999456598 332743582 44368249 893748130 34341033 812107624 507788463 182978865 917687658 740208772 696248047 923424462 234452843 210408577 415091216 423250688 775745913 128782569 625434353 713706166 613847757 750677657 114608129 765602088 166238432 886247695 262448864 505249635 270186354 526050518 423161871 295517169 768578452 601835102 799868026 946897145 963921640 245879886 406908640 591071989 116338328 931483701 389120749 209026258 854288648 903903259 112082855 39188808 606970802 131368530 822301116 684061594 805887903 386694043 786477970 835824080 734353750 581019074 52300664 369534323 763223749 673995654 51355645 284125762 184522814 107337566 36527576 171457272 777550730 579172263 298150324 788480459 158009834 939258357 803935335 19350114 710659677 94771908 908851552 917628642 295217213 245644492 84218353 798040294 931309056 299468339 271226361 824214867 683677446 118160997 15450479 747263335 699486216 105921114 360528566 462106633 664597699 876789533 397380529 530306069 236294257 87952088 632891199 312864759 671921200 29455495 49182866 533472560 519731288 530762247 592608050 216885374 950075891 285602551 736427261 514900397 260622198 427343764 531293970 741891417 959365690 260672741 25333984 167070499 883893061 812227496 403753736 813322531 844560179 700690404 377286351 208467661 443905525 34140319 788071215 953594420 187690041 961364467 163189307 102060997 564863635 899063712 623921841 417674827 551091717 509111172 588932568 821245405 703641613 87953976 923437587 534909190 386639843 839934237 169237476 647918562 181192827 837840234 969311 576919706 233422463 539688927 930345642 871442790 895154981 765680933 57747491 391214255 316757900 265343395 353054157 201050461 232628972 97901304 826714066 542207700 980640508 926999366 506891383 718677561 463908299 796279038 44168958 618987534 538349410 291413755 758237705 171042824 812864609 567227065 774652587 555909378 60701664 547921061 688353977 971025320 21289150 767088316 479121685 173222406 968794442 487445561 668281798 452333280 669287034 326604660 469765377 855454226 238101236 775141124 490966031 316419440 910367690 411385410 366773369 6184615 142981352 810328027 585216701 680390492 417278611 417772346 189053209 107563280 93032756 440464148 395642401 617457026 988555046 946142179 82412784 395401698 158429619 75661224 993412454 71711382 467553249 837446078 961062868 319040821 315330007 980241948 871297707 852139759 294026280 557488588 874154431 707711951 621665419 455234152 640158750 612292883 168536201 6080813 161560711 497299533 262157045 863748847 324732610 767269434 907540034 100274705 157227755 764456097 822754066 694845404 35986633 589537131 543622866 508632227 719618017 815529179 334940411 139532024 554592837 511783434 225647673 367323667 234959330 472872059 94437906 861096495 834597271 56977319 593709449 287246818 783825579 433675307 844950971 832208843 451429720 195375159 895991590 101753992 200667563 997183958 661778290 98952299 435729211 919276016 959036379 440269348 646931043 297017814 226164967 872334450 399452629 709687482 83950846 808279281 427121885 968218747 965646799 961995450 633027418 235282512 688105554 673936472 270062420 975056693 92063228 641236374 206293082 728702278 180181685 693079885 757532622 157097971 51224238 300645153 123656060 63132230 284992652 483084766 878017467 841523686 650101391 232584464 695493502 8791670 985654218 320244052 689528095 933469037 717205049 373226463 727671324 25667961 625152640 167361428 971782525 103901933 425529192 301599237 580274051 18790981 183252969 176824760 46696355 777557074 194908410 571219164 351494053 200927790 663341559 461306900 505322563 761825426 545506256 539038732 499832350 742348509 576974899 668983949 768544340 10175304 798914807 368134852 588969083 466505870 29978999 799394303 111153750 266156934 732396556 959387841 919444446 359609543 211844331 190565426 440700188 290325931 885005442 599480858 320786795 218310509 580039135 219828025 238071966 860033137 22644162 670570753 455250586 373580210 779922 373123188 937877246 896517161 372695552 298794047 763933226 124784338 20721448 702580986 760132251 322345589 611899791 627147155 512803076 320857215 886186104 219949361 394286472 856912870 799314366 855599081 732928751 334735017 270168609 453827137 935174987 280976355 207942786 102084710 751348607 849291436 127813088 255350597 11762680 923371520 974314327 765792746 381032610 719249124 43803164 422825030 863955617 917368090 604099116 514421364 885184848 636608556 814817243 708451947 216908008 502395272 861232346 702374699 148699003 336928698 353964317 386294597 931107685 457947034 626945754 327427334 698934388 620093650 134306273 277716877 423677257 830932836 851494277 958806876 196265743 819442421 651803587 415219117 110471282 46973807 384145647 964893912 245036620 816238934 198449724 497416168 115778025 655664714 65499638 230268613 404745654 537970677 647460027 975657286 205988478 633437519 419164338 40988891 962658088 678039519 759777090 321777534 34884641 365913951 634642515 669800447 288043150 46117865 173290016 754115978 538999409 832348347 406015784 302297038 489156804 709434869 974144340 617972113 139041964 830489584 277893292 846330016 204689630 439238534 423947734 765903642 785256678 949465724 380895285 145169459 773944302 914631352 373550134 251604114 71741049 923539895 675098606 776322214 731151534 159927953 216652277 851063504 177960360 288634584 104311892 584050489 660092774 141196426 797160421 149602725 438324121 985160131 337777703 578242360 940668382 553900715 929946449 138477110 20799126 208863822 126414202 240712863 915148561 20768032 148294530 321313648 773914949 543700113 965428924 624096660 66378522 408681845 350485706 703783572 996880598 738388970 565318260 253204205 980779087 970320847 584223296 297546291 745889417 34177636 480222404 661276813 642059283 926977324 629892140 207758828 14412567 715848799 3721837 566144572 212351828 310361544 432204714 337788814 980017207 905979015 751013759 593652764 90783261 758982303 39905960 213642774 473062288 195017325 470567154 492362672 729874268 814204757 467385390 552876160 486210794 644069757 868457281 628966995 916325467 785416976 874572956 877976610 593178489 964498034 819478628 207643375 689213142 39985452 392095662 417213252 628615683 484494952 183111792 848989204 384445561 347256161 28501253 216577294 658240634 880067136 715663905 933064671 23729081 458855129 209439505 527425180 871321598 100854450 183980805 598598208 970493888 242356280 216459916 587260218 969927272 281407852 8018650 89706712 897327654 834844334 492128290 749220798 364251728 818430904 14230622 682868923 505401616 613897931 613566854 608558970 901827831 340373422 621890409 672343994 867447023 556665204 646950946 787935353 848537377 853379343 956395232 278890451 316726188 500863939 228960682 399602254 28435408 452313928 34397350 477683626 620956734 881104769 927799691 74207291 854589703 815662110 155042484 911317097 957409088 492328248 91018243 965217723 392085419 430982496 502011753 139641901 283066011 707499039 463400267 33463629 359115754 706981352 497709231 928880488 119041590 466235919 944255681 40874102 288794707 451473528 78834609 245784710 370088454 842429175 820679452 989613851 157233185 352879859 183087333 312921005 68762039 526947758 921901617 582346609 388516567 743689093 827092288 226229252 785753215 10463235 214368753 388362815 206931449 331372076 160154712 127890395 964648428 798625034 664756997 469120892 37929333 384408460 554023453 469763988 728814509 890692089 798281957 521083986 642135357 815945711 967666315 987537093 679349351 816947510 957186286 655778481 542881945 391849221 577632949 997031025 219601852 830336780 995163163 505843122 812224603 586764670 355516558 908617014 455467736 46063483 452367738 223468808 241626577 891549632 449083793 4308675 733864993 614768325 949903364 214537516 684232076 963903869 827960079 770627140 271001803 867619584 937907682 643462749 317307409 176532846 691750522 596276054 479098112 39019990 183442497 760557518 693193998 618868872 554298671 657655333 726116108 849894033 831801800 615448822 303475270 451340659 451848543 652423501 61231573 853299097 121649521 418953499 547849754 783966586 981534615 740083392 303506364 410631268 842685816 858970761 658587785 432139184 45182912 936165479 410380703 558813455 660147190 234681325 358705660 781073729 536907671 783002463 508005420 672544797 243097323 878471976 235038669 546719208 640546586 216909860 297309136 100666559 43481577 967556215 856493500 105001712 269727503 549802045 911736011 829219782 290404001 728881234 834585587 729140302 673962940 368329596 613890396 746824978 155473286 499121068 239371842 791772854 632389641 594481603 963744005 106416284 949581013 75739742 610042042 564255465 48302447 371236738 378227988 714301034 376434536 878178132 895787489 366699764 278048906 968978182 62932762 189395487 644432098 167762788 938304676 350635274 117424858 986218119 824601208 860072980 994044584 846164556 881677856 807743549 547936091 304014208 294732209 276031767 157462812 789730321 160348995 898140963 417228303 502650723 69955547 438555210 796749613 716844632 202726105 172833529 902156691 920129783 395278504 674378426 949874042 925557982 183699361 400145725 2960881 576915964 178990599 540149301 538643784 179663721 496198612 664252434 856681750 367088602 611816364 76954154 66014671 53286396 15483812 785817774 341684026 170387264 961217080 290367311 148518607 673582572 928274392 278551898 24894346 444810401 429756758 881472265 750616076 520100548 123403562 518691560 391276106 110394329 962948711 949442253 751165213 481400124 247684988 211427996 7278409 940006211 541098452 160305722 95040547 46489787 625217448 818832909 734855585 880005282 515080012 347931791 910087286 760563963 56184909 137315883 405672898 383948651 372482153 556769439 212277042 340987542 536368709 19500624 687769899 453795852 159628454 813194873 76229792 428606448 728027151 559514811 143262541 420523142 864800366 162555012 504716272 973959780 341702989 611358740 106236816 751591980 106865610 770996015 235420014 827200382 47803581 505653835 834006169 750075233 638523115 2618737 310588115 864056776 644253255 199936835 187479800 447994214 132198663 925738238 250037914 884796149 680261241 32171983 939186278 831004206 322889501 48204905 8634344 123712150 846792118 702485298 861295659 718039490 155046974 7910251 580841368 997742197 211175715 736824652 3707519 540878176 461099969 530948296 138137764 545504502 728940749 449361142 76236205 58878989 402151910 459922181 395250135 464132691 421834201 310966642 140610209 987452154 386710113 497006661 680731600 734696181 43663502 216066831 226746497 155617287 425153357 560334365 442272930 88019014 193114484 799584939 483543499 902198283 750548488 128384611 203327694 331200825 964861631 53867184 932108972 955943565 56702479 961617579 126835827 485036216 52182935 543006604 374921327 305904087 728710622 325026598 107131808 554906663 838306116 96986577 776256669 445168485 10396078 814589516 66885150 683622232 647705328 785721304 842542341 365917807 306338153 773338006 728894330 515330284 399023495 104792740 786743096 153194393 125858293 25697330 204858466 587852958 212919907 670583905 420788824 763354020 31446065 891093161 307631175 247439375 392669199 341180052 663893861 212185422 643048841 273708032 389540990 818420870 196161503 185271768 520951997 405946105 873132079 785045648 324067553 632757631 768122085 933473977 411296312 907517675 355373772 620598258 245930740 227434994 289580046 78416372 383182321 395923191 671058601 664832335 528426645 596322820 63483227 877168578 571093032 768353045 26738942 724522812 933003274 992578023 688668756 729322245 861822262 340858775 410476073 97812785 935951798 507673312 406435647 491040475 828474393 967808091 519645430 323060035 996706600 542494356 970191771 157276220 450237947 548761246 352983750 292183249 427621584 113286197 2039242 999055488 564702354 187691705 649756185 687075187 32108757 964275488 724772732 865463998 847647200 71807575 847419786 966406319 960436411 96458442 904408349 721009695 328691706 588037267 541921889 575896415 583409409 797001799 772602800 38775973 377798547 763815024 592100557 2450742 558146022 669003441 882368690 952661093 48069857 798466794 12186155 826628135 436762078 783268354 591141616 870498279 255676651 263795753 928513477 534205477 212554104 489215166 500059526 110798869 822492168 292519697 327056413 15389800 724829823 842100055 84050716 910553816 869034358 899261106 916216715 497990662 616697916 18269782 628831693 861559568 613616305 840284841 973147007 511536250 329631208 535459683 561165756 103081707 407264426 305056413 97211767 537685025 339638400 716419739 977267613 366056217 502062585 989954343 113072240 520742838 946261296 650165975 183056365 508494124 487632395 245565871 522569561 945165837 604378601 515472315 80629550 312937929 493009251 900491291 278359682 945576261 240796499 686950457 603773448 950229392 395642307 755769003 715149977 147508175 62064774 541574068 188345144 942517341 123066805 737405088 122334880 409003661 697381203 295988904 654500399 283063683 622631592 627712067 858094935 804217287 481740967 302310576 605954679 793861858 790156169 936876882 679659736 879973456 627429638 559695498 606951013 995843747 25694475 985143435 491687314 410691813 403226204 782521051 812809464 768209948 321478298 492822928 614172228 550266194 567476715 639018648 805578669 121965833 85208490 137671775 540941521 920722457 16384950 75863786 891236823 893757057 578863858 328169882 41686994 645127857 404599790 393025450 817942065 469559028 518123224 283709992 932691679 743967726 875486913 967018696 981020673 635954317 838468824 32066161 134199851 103808256 609032220 355614555 175931758 46257226 683675321 606530678 978235258 586183472 205360768 513183965 724742299 254960574 833731629 816683341 696557288 576039568 848527783 156365381 702718561 426545571 225546191 476748254 279738896 672451448 390899139 581597084 863608515 866908333 682948168 20571846 490888700 431610545 674579050 153724548 942903467 736980645 713046920 949579759 959758326 40315024 902123677 596439468 166945492 209905720 364756962 60917051 549061192 684753491 570861756 212803902 877085770 434073515 796092309 848148187 21579407 104099771 773696389 685872494 608907078 912412882 453525761 874419599 397255453 536433567 730320636 286937592 154403373 701973847 738512385 698671298 815383905 164943631 907830066 694885834 11544442 756159215 363603244 849445091 869504960 641527006 406107987 93786350 855998069 169805306 689582876 659145352 79621875 75992584 919094396 377199227 578801070 753332213 285129816 431410350 442535484 554314753 846977254 250817233 596255644 700430117 109803491 694513199 640872089 709669310 496516702 333619112 568997215 542429749 977813972 63186815 431184579 221423174 101227997 394691757 213514935 301728209 100543844 521996329 590371167 541598733 498673683 933072766 879736203 298248228 567909056 60957400 162576514 658227619 241248621 715926897 532082224 546547083 768997894 155041139 641721550 242691408 993211691 487067084 763601177 884418022 600173923 529959946 853412447 958670940 732221797 521591478 171921712 719476346 916372871 561848493 440847232 715847505 428647011 930707605 526135553 806358459 441317797 204812087 219377959 151866266 779278604 583131690 350629709 663170249 111800221 246219946 611715878 435806920 983527774 89147255 418974318 772217888 448365275 643723396 250375369 9054453 241061952 672542260 633009544 716315025 477162944 42187980 443528859 528882314 968557864 576813714 205375626 440060582 883929802 930006903 780681708 746162529 747023887 665235561 636149066 823053072 742919469 449525664 551984998 606747145 794497548 349762177 474206120 113822442 558052615 636012590 492085023 904418026 703612537 988686840 607465720 294173219 213975786 874612465 14246427 643868339 310010180 100695869 12758704 319827392 479711139 499269885 609310266 986106829 614245984 730779222 624994526 547169430 373411216 24699592 299358048 228556365 287278499 483972944 263952304 158834792 860720737 474207815 129531769 153453842 116956779 102990536 183199042 80886757 335413411 259218086 590034384 750115026 524555150 59849013 766757615 900175955 637148220 462872646 279681023 435305856 397630163 417337944 305163153 301064728 921645733 712450196 609579330 652917791 460709972 799318960 392116782 440900666 536313071 968849839 740703461 613775345 119651917 96521978 3217562 411883005 368301665 865918487 180561178 247369939 230058364 324164541 463960049 584273561 744030411 162074389 151402287 797996859 951560148 110612569 215447721 794379370 893396480 360252874 671436093 149032467 701541200 31740272 492993750 637851474 305824904 137269052 947009492 606992760 587566383 250842995 422237281 968836608 420305871 419734674 489804752 716957234 208263188 542584161 818762369 525577065 247160658 467029079 548796092 375460275 448490429 20564075 892722683 348087224 421839845 930798325 323552758 152892215 330983867 634189813 424054118 807189181 511255905 613066734 456999895 431473506 298789810 202138704 334113346 692565137 212999147 426926914 447125111 815915021 50385955 830879094 695875012 287238846 51516918 959432860 276038376 389130770 749538533 456958397 190656902 669758307 131817546 584540733 131465226 106336289 479524755 576963068 193632968 705629297 31926546 399524632 363156279 863338023 101992870 991930643 697666910 110994576 472946601 667553572 389857938 401572588 459590425 497320665 651273165 903725677 328239159 482627758 281601366 931290208 837143900 14671795 206326811 440889487 377275714 157304201 208406046 377370954 196835811 114895080 824898892 757835727 273302854 237774048 770567784 990319776 861213048 533823011 877009110 744049012 943287894 47875448 664945179 724306750 581231573 962259926 416122057 947331713 593119623 651374388 104014591 232581205 314120165 303901752 438153719 839651633 251841989 993586281 481162696 571024829 396214598 863007783 138183926 928501419 254330231 699405068 136367119 450221311 667401208 106373664 924803661 969542399 741901589 68340119 509550544 451866170 695210392 407905974 688024365 45080086 533987932 111926172 791207210 645156657 256422499 130529804 469370341 717263738 289914251 443664120 735145245 266154091 43631985 645806997 522764784 209846517 240065007 79389287 664956774 490706099 964377609 877413281 159429202 40117723 972772719 326471044 235251394 511313835 375802887 84411326 117320633 933477378 518640116 930376096 898574498 249484735 995821166 736234137 767143020 925352467 385291432 502950712 945032152 783481733 5006786 611580559 135337857 32673247 815608829 558505216 743951373 372679845 369794538 415506272 89397240 725497828 59031418 326538496 306148319 973901655 937122258 257089902 828698624 861576076 861226971 792855580 390749594 672216388 176350927 962052537 260380615 858212101 589430225 614414114 755159471 700922189 624092506 992711560 198645189 722862485 798265993 978939422 581715670 877756197 914605186 685711945 941510101 983580594 321510943 75965538 870822620 209264047 748388557 289034107 444956593 268325503 404449782 284415788 173753400 26823633 149006709 549960770 919608097 894642604 956178090 256202904 858629154 601431580 681748654 291068541 230237358 3272951 954539229 793673907 24860085 358319954 75750408 928510745 648920576 893378806 500692066 834694755 708780065 73512028 510043762 581509133 141297678 984983662 213117976 878132773 185371703 549126835 681822381 531965589 19866859 434741510 287990508 306578692 253452816 377547341 657223601 667372858 539721960 92364421 746560453 25720318 856038509 715317758 829789789 546145480 223419028 296679678 308079513 915938177 843556310 454175468 136728537 416960035 362087581 713159345 288590883 405342581 485491167 558898074 401941392 336845636 703704786 111890241 907036284 965017361 159002238 119833358 687080493 639731131 3928769 69374863 654657293 367710669 131153166 660165341 948409401 196256179 899304057 226114605 270651473 145273697 372676289 943925953 941504542 995174268 168691869 405305524 43468367 762374624 99060532 737284871 43010748 285119185 276509314 250855930 882548296 946585718 115470934 362754952 718330051 249307419 700790130 297604029 611794152 678596764 586521455 231875196 581647621 832203875 221479692 528130101 173181032 148190917 779412706 895453050 6121066 939672433 318763204 904074403 89750302 204933163 364490947 351769102 682171051 165854906 909356481 765400252 920489565 167941802 446833769 879433094 372423750 414252900 911137671 702352512 779189510 310589526 176877568 892234706 370664061 229591118 660774382 999478667 152382416 917198109 618114774 701294390 429946377 297764965 614475892 631535569 355562873 748012920 533739125 779269048 996440370 25170434 218844738 445196623 424400908 569648474 773239975 640958936 386512150 922165078 517486842 460373224 477574574 812515930 950542967 176076919 786089041 975756648 443284945 421089571 352083899 188269709 288219365 481068345 219758841 293576108 360179527 103227137 565948945 354565086 994559084 57555531 811274667 674070030 201425979 645728549 59284152 75601730 71974133 837021732 19075678 636889920 641846210 505899474 42936769 253745474 279518250 46839206 384750687 837084572 316864547 285800501 988191744 86103011 161741042 355740312 138096797 668001732 247330394 105702887 945129371 477932345 995597414 284731719 197825729 432106283 182140915 122868685 544777926 805684310 449708357 814971047 386191123 61207767 69670991 464642434 443275162 15597780 369631920 786023504 8051653 76258387 960217412 333399437 220105041 461319642 954982316 133953133 208401065 739784744 628024082 625282815 203628691 939255591 37181705 726919916 955431403 774513959 824822141 164188138 278831734 636045806 760132315 366293674 405290425 289961465 354716744 220260743 166625357 319911508 241511380 813615964 342787001 997357760 405709474 372627256 699181751 615668535 687493789 260674673 256170625 869147037 723163609 96421624 166688279 852252920 226396933 663621298 416483113 27926927 189636759 99867954 578226957 37937303 801638003 58501888 616199420 621140831 710064242 84488670 434190081 138151384 394500982 960727075 108221485 515409317 889252870 329948656 827160318 25225799 39225756 999259389 216485113 105413879 295224685 352942472 40534128 113417414 249997725 235275331 494427729 883404555 899112730 8159818 326442886 85555585 330760295 128617594 46840320 547438450 156920936 924117740 18315352 499957266 592661584 702958245 964432229 545329368 947748580 301680580 964745459 514300281 8953307 5031465 736457864 178411120 182912529 969027364 899005907 652831257 647831500 586467479 707315800 817195880 490740277 440767156 18357579 598066483 368897239 329289487 783281155 819390289 112185671 115644705 196702141 65997691 384695584 293239104 824444654 816944563 835608917 987031392 241848282 260375005 515523749 591712292 462202389 837003372 330999279 640606966 342703380 4822579 123036677 937486187 60423648 566599872 905675444 923673540 640075289 819769229 335668127 570688008 226812363 930460811 323489492 212840481 923894373 203318286 205504521 289816551 848187810 385828102 907844555 483425691 381989047 884779313 437305913 495509736 668499941 739606871 910787743 358690849 726406227 691778441 951785793 5011127 652476391 889292078 276367431 941901325 247796784 948320906 81904093 232688083 193421595 68865796 142596584 173698036 423870412 985226614 943780723 106369974 808457548 828611282 792458575 487607168 135748485 467606520 657649233 517520419 131208883 647920602 194415787 123895374 173268037 652682146 583768006 432096120 585296076 387321156 988019940 321177775 328662824 972426516 840417561 672765820 17580237 845148936 847334579 348951481 291413012 415931557 785537062 797475232 542561013 308514275 312837530 984728638 985594631 528915882 494494735 78395989 613938803 85187606 426365221 730034941 326516887 86399328 368634750 670208039 221677853 686217379 284811499 330409766 396347278 167200147 800854704 760991610 165113456 941005773 213935564 736219978 533576666 900872934 229671050 404078232 104450223 119374039 593319182 219896706 818393407 568345177 104508631 161047526 437781125 737353425 141695096 138551243 142031756 633472224 95736465 125980658 379758435 354316243 189639995 299773754 767019055 661611368 187867791 830416410 758922948 853495896 560956527 685582200 208791579 735661846 677263062 925493215 133221417 849546823 704511339 253805481 805400854 134959738 208898155 298583152 201831525 420878125 758366718 989813483 167510536 822403650 821784806 677428167 674923421 682051706 508923880 446988643 546731090 335498167 986931228 859883915 288103607 668350533 873293974 145500521 121645464 546830756 232574100 12817552 924787895 563953432 347434259 747853214 626293787 758399557 472211600 82884853 481896555 800872812 25057995 465381285 150448046 23803191 93314458 548243829 370616408 142648275 510147668 629583730 988139911 6885678 159302210 291473024 943901743 862809906 645437116 569456296 668599047 303473163 271023306 909786199 849310038 772077972 382535915 339753790 179751642 608308657 210753148 791012129 635868102 858214173 961921561 979813800 651521368 146716878 758118510 134041799 602454629 22702828 954209570 459834613 228597019 194360704 48625409 896367880 589326492 846709378 816567322 155955325 348778382 224439030 191975966 167049973 917985979 329617411 460456319 90052224 640298614 867326123 954283112 524289777 807112787 870930830 916551257 719191716 431689645 125637649 822449050 242415906 936047028 495245312 379979389 847638804 63709517 131044420 71393528 646812853 883155300 915485819 999136980 197447676 49910411 772440900 467647470 308071425 403125523 325672080 952777282 288989419 671947333 19035321 518250714 898967697 603235539 723656699 518228646 802251346 470746623 770564709 372765551 569416264 274060784 968161628 567871090 679251591 161893544 64192344 212048547 415827651 564456519 228031499 484316357 58622056 23157913 849674168 250626655 388913203 289688679 749770691 930258664 741699712 537981573 190365393 405259130 443841003 628491026 167893032 100054273 123204488 785019086 274972097 724179754 428273675 504358223 209428198 435288044 985354673 95196839 72919785 174661963 367136666 274785880 140994536 342774720 240272943 348100374 896817365 539847751 672423538 927055917 21065617 492087674 150282562 421253584 667606610 402658140 480794792 669100884 944308184 849864603 3162769 975324998 881533253 468432980 472431534 239134797 782612691 191116353 46279459 252892319 307662882 388546365 42357949 94953877 679769285 585530505 283989149 580759421 648259850 656559414 814144730 774363825 481094493 942349087 503834400 250478337 929731542 687365351 441519312 908147258 963577845 729509291 261501801 676242791 618813622 891078157 167400400 161719540 918592664 53088399 92468017 918923098 749105138 843254157 955945287 884371805 938232645 196694901 181635044 808542802 539743919 306389614 697149434 330960426 770945021 517629363 812013840 249740862 795098420 699176564 203117428 707372735 570840000 215170390 908733623 758147064 769282680 978731682 777143433 105264620 870279510 355746023 382510876 183551085 626743921 903054005 234086318 574141117 103720776 737109458 578672545 238431246 186090190 44528156 769472943 426800683 410078498 255330082 437607782 653204689 986161948 147235116 802740320 921584124 38811733 401127960 184342626 882392185 818505383 932576184 752382523 977261227 477111855 333780618 391646106 312059829 888074311 67268009 41704138 910691841 184156473 903759685 931158754 32010466 514286792 591769879 13768981 190016659 72858691 683080651 196341013 513909795 593908882 270080929 793086942 456425504 426920114 988283720 915546647 460846617 322031009 947196244 231746730 77964232 436275620 320549580 950228064 399079085 474303335 559290302 411976941 242247147 613562447 97016872 703055444 189706180 44302620 383610204 465184651 215802625 836864534 487739918 909464564 575413283 799286650 970886768 77410519 918961585 440872004 63948701 59919770 287498174 515744381 430432265 74256947 646826895 67477414 791543776 476933765 987456752 139723883 689436971 405436656 339570024 508186978 567916645 494834246 415185949 977685084 695604544 948110181 171515165 528430133 19353042 298764965 420774570 353778880 596430103 43367027 717704327 16319436 721475795 47545539 401981950 127664351 812797730 383198550 975814976 784183563 800865747 581856456 307479382 670158210 165969642 404462911 79947391 783940591 316258321 376481979 434521246 311993679 350704775 374923731 772721632 389861604 38848610 656761836 223779877 118798850 516724200 907954102 232790933 361122426 848857291 210594458 532939563 769879990 931886672 410411103 75374029 706437188 121514800 715629327 188722783 929439772 109155650 894097551 349194693 136632142 897833230 217557381 457179457 498085985 740511015 124937790 237302338 493914360 769373992 29907394 731342618 92853940 931563786 463017866 569985483 436264210 794897308 8743736 434433569 710913496 189814724 732750157 40577248 48408864 846639678 30347410 968208222 546296449 998527541 264843750 397411942 234559728 96997382 765594706 911126752 594245321 700034732 678529250 223758108 892717334 252078793 451543275 285092178 656323828 650788946 186601113 559868559 955754518 838557048 832328485 239757360 666313689 653192926 276220084 929882209 414545826 1273426 314031374 152944975 81946324 188388616 771792709 832571522 607727247 312517932 283054203 341055058 862878269 537869760 971001486 160732069 464732841 405467739 872563790 718865214 371798510 179222903 949461187 229152421 916133543 143511566 232611989 469382836 270784807 492273002 560752820 51394421 683300333 971395740 15771953 57549071 702958627 668043338 939988504 977721155 74850264 415635593 31437014 580158002 785764886 751397410 725011977 844253737 20624844 432419736 924401573 620313323 422787980 983769210 239323150 670055171 246732632 320544891 387438558 285889486 869526835 710550943 261364731 161092614 226692438 976967402 955935915 942227382 41297838 234258465 945796554 733720729 927684395 756362184 523798908 459476113 389843309 19307179 564089739 320505477 209351971 449812545 472361572 416974991 354191626 739982098 856432820 383184757 732452751 857991985 880417548 230374805 608447088 128342704 638941293 166674917 409297129 973874974 859028719 446378059 732887196 881163571 191376223 501962844 741560846 6064070 906338789 304216854 13477611 24302494 684237540 897330605 471965643 803887115 568608718 456167270 196771712 817889569 585366045 428537174 360526160 180929022 435772587 258631117 294837759 445988989 277203153 85239935 749795887 395027308 61706044 89388491 333765770 606172429 905381554 840127589 721985888 649666530 337016508 303337791 692183390 43283452 931602556 149198462 741256423 406486500 444749403 851142299 63740762 15465468 511384081 555065135 654420038 899937863 730401154 335964129 278287839 116491016 497381485 434975843 487318141 627604008 939608007 308282022 135862065 677071807 407624649 171580546 110240690 147925616 973279636 153819663 530909467 357160495 509002150 827295459 410187970 333540234 653760887 612098345 709760808 65635914 175933516 277153244 961292406 119259096 920544728 903693259 81328248 580437269 56375971 940267061 473208823 137373120 145801149 597293659 993687989 74986834 841335043 237013349 712653617 689083998 193471089 186114895 890861171 588216008 38449723 227447480 459298894 655877589 408250256 71236988 399919008 66547915 78611195 986571327 978126600 118104158 440696606 903994342 139601332 492122656 59841001 56442114 623436530 967978217 530918342 693755332 110099205 400785021 593218253 164096969 569497458 335209730 823632142 355765990 36659195 479981163 364560725 820744796 478604012 191765843 166064094 199287789 343233155 968596420 571002521 857359042 697514355 925140954 572678511 136857922 478679075 963071145 779263165 447261810 507189546 279384343 718456175 292949126 412077834 863680608 858234704 134092799 804967612 961021317 325516430 860393879 63649019 46958144 447172750 168377199 977283367 834223740 402803055 619810708 791139481 852622181 207828402 174169418 501258702 707643177 808037645 274281059 770307461 106599 701906845 640645174 810099276 625069375 978460412 637312500 960066844 937547963 654436212 935465064 453825560 863873947 385200085 624349904 629697377 446793630 316272591 62929653 175215234 597814570 107136770 100306619 138849138 248826909 767202749 883128653 941721791 947382566 639719691 910195814 74231198 138585988 673506920 826429142 345545457 928359022 188436515 328298709 628431084 410642045 926878679 529426175 23951086 21963241 128873314 989940327 55833971 87965138 640039123 683744269 220761546 531550423 368546325 57653846 587547492 237036030 494744185 298542832 257683157 640211351 294960738 153741743 482832877 953739853 41702873 316745559 370357042 644404898 515985545 291355354 12855120 501946646 5400000 899141057 416267233 331754068 9104537 133077407 850689501 264126940 937175932 277499863 889554098 723805090 927428307 229124372 766429555 381851469 799188125 353304678 277860720 461222004 577804616 254984736 516420683 882227672 401533867 8427382 564237854 228327761 420984719 444968699 293561104 4290137 693073662 301693438 69936239 965431417 178409349 524666441 829549780 542094019 993414569 97077363 602319051 72429407 913413233 55555683 67153613 111062573 285027603 49456245 779855959 895134821 312315490 784248230 573330960 978381335 420210478 906205552 8961429 233262794 709347272 488323353 751642108 792575783 789827749 718943105 690473275 220924039 463121723 912993423 422350039 834189288 41134273 154305991 8650675 13937542 155206859 15730115 744479356 830731081 159402897 462203938 726184080 600174318 754041682 659006092 99243971 891463398 307152404 419521262 394803608 732961912 914387656 538882943 511182563 595098199 985336336 245355576 142856266 506695657 282949549 264964159 770379366 445506927 134308149 897280803 34580999 751246981 816041888 298348454 38162288 93377815 681639314 831803886 801157145 462508383 439161913 301302901 282860421 420825782 279582889 361400946 503533607 537687310 714884769 667674371 168152228 131418664 636577212 519937319 277815428 206945451 692240135 324328034 4030999 389643953 615912761 165956745 908907665 582882278 928770310 744093575 591473216 26243725 862610324 3697793 872177538 773569053 366967024 956330480 803694638 682610138 600760410 596433405 366185329 493143975 418913956 549696056 748326095 396985177 991775121 22907274 985091076 128981184 160809947 824667876 152534709 460971238 606721562 584372792 268340675 207528519 382871492 927304299 27726762 223664571 435200957 439152660 591279857 440571125 656242689 487246654 587721309 828165784 57038114 266142416 684984753 674264859 442724379 32766937 400937799 320107613 356579546 403348689 127003512 365971704 841189198 806282508 794260179 104080531 224005935 479099785 401706956 167237511 549929323 418483813 54747447 70940160 707947685 207174530 862592400 330851345 731264124 470265032 516498002 498675827 134136923 574210337 578227478 315347942 836580784 506403103 776357864 23832143 856394805 566508320 499253358 153185750 568138831 468421416 409100649 479188207 383841400 415686254 647389920 288336646 791204035 576319408 795364858 53507455 298938609 378667925 832177873 584914496 346772033 856032094 875359962 639721812 200901666 84448735 239460343 287770229 723330786 283104184 220643619 311763775 75810155 48746053 450018426 2095742 511575274 555719614 761751929 327554251 206821814 344670025 824266718 817143291 39125505 619623273 341654969 531202052 820833054 400798637 375369025 476138735 892153947 47387889 922864126 532016755 532710068 182198537 335592318 824383714 184370622 866237486 481306476 920217110 948998337 912785071 121553717 99436276 268594020 220522827 253998667 247675724 625958130 426624902 774888061 188139915 541086641 34489071 42458661 322159420 957529426 68175978 374552774 788909677 622301360 150522278 534454860 170535175 652059032 495822694 533241118 711485590 793832858 950712091 224818537 358264487 32064311 100444713 209073993 678824629 402908297 84314578 443615203 672549947 469593056 309231922 208995730 909911781 470797588 94120958 142203812 863931386 195181038 814524322 155965263 448824068 286765406 796394902 759629683 759149459 939680587 113214890 334798139 94803777 904864633 481765962 299383717 713407516 501099198 895478739 329851299 179129567 711321434 483408461 389134460 13620547 254442908 650539972 988688657 669613708 887706696 639421368 944894753 112839676 867446848 291062735 678477677 735633270 935528970 901206690 720116948 572624338 661338248 94786058 247475256 588224970 675670847 515518414 440403249 479935418 733048356 687457766 687095548 269897870 987406498 936678869 589148552 866371573 581190375 92820854 614804774 868572480 711168671 670542190 933260467 943857182 712675134 379766369 57092068 536891765 952810705 602516069 83823638 584995623 423316791 245947277 257696990 809637540 851992290 34446390 182721261 652784039 952434796 948600582 615516497 58908917 161902157 463218193 618850300 295538364 375716323 184309274 308858481 691491873 735516606 270351730 943137176 454254508 272351501 71480580 376226201 58415379 202148653 668034160 529114547 198630814 807473527 519119099 94114070 289343222 834638223 19323453 305906404 849555222 228080554 114663959 350206700 608636883 233835840 814242543 671080483 996841884 97904273 762998043 512155179 918746266 653279618 108336599 757757198 700599967 798469201 926709514 529906118 268779330 768252229 115697409 672984940 278495607 255958646 913415777 313779378 818615993 263872563 143328672 221712162 904433145 687802369 627093597 679026546 625212896 874965680 422145766 434570368 943826894 2029194 577404247 137574858 689550830 512941021 889859790 134799317 33099726 991124739 556842898 491293022 222852828 184979015 504675913 294047148 605307250 257755650 691357332 279030803 894400047 649243792 720044729 528319265 109263788 830401747 296990537 829184205 478601506 756564457 266658211 366502913 651869472 790837252 709966215 240061365 645005689 619935525 82749035 562261494 512317965 280273911 953563232 801998160 490741890 170344675 739585684 674850577 12978119 329713257 859060314 834806635 184227276 76059360 34442876 384928525 536682899 659530125 32513817 89363690 497392871 59134710 289432261 981111775 263458818 544260986 332170582 940075941 634186785 256348248 763646641 278693271 111624490 927463020 805750168 253650218 158326967 736356114 499598620 86822597 954932358 531092954 977760551 663273553 462667196 906876326 390103735 875396072 142086492 386119418 494759639 362437261 205841392 823911161 712074396 256090998 351814885 416154450 942082072 310472633 17435380 21972403 136822847 964003142 498682081 96950586 874132225 78904216 141975052 844315066 817586539 601567049 574796256 235850780 702932104 361303816 297971176 525495514 253854598 347266864 373543678 940257168 808359003 791849557 489208028 870262499 13604897 966614828 687119545 681593338 313352504 493240575 169057317 262151850 77994262 328426115 175778986 913900265 23766335 791295398 604299380 485365600 831565967 705112832 684675491 822383249 712481965 234985844 591151396 456620769 234781994 46878161 79470038 537745379 228727252 14808787 151356415 219084787 180705274 401508731 162512104 944005080 603456992 389897016 398169885 587643286 853912186 394501216 690589126 138492251 848750494 75232122 295614859 742900560 598720916 12025485 131414021 687636048 558742746 98378426 833228081 132863903 819544408 82727292 158381926 929590383 921714856 713090641 116428157 254089337 102710929 220551888 532933146 216509152 255815518 199275255 731000583 448227515 19540642 71982399 215372050 976180997 19510449 500234253 324555448 721457232 402808915 934189991 921329338 331874112 70787534 401988147 219841387 637939418 151607434 384888643 75706424 282660413 363157510 164357958 957661009 287523086 281368633 354867309 465785430 522742689 204071682 571895957 642423037 764685865 534418518 823196663 772307673 343168569 78345584 336982549 350148499 712375573 123881999 350113127 844468568 349023551 339318769 947748467 826404227 910108849 220502496 225136906 772572274 513295209 243533208 752365556 328150643 966331926 73493842 998905816 746382744 680128153 16857518 227588503 815987479 740091659 220593 900219546 653734843 846495562 102521788 360046265 392190893 633306384 657136376 756905793 537571276 612481814 621460085 491677882 441365991 902242775 935445911 581439968 537800530 855606146 540993832 211781618 113297108 166957911 625889279 606097860 85318615 395112308 112892526 893134709 276979364 543462916 899403197 87460627 982336283 598914531 793241473 239826706 500324147 54402210 332311227 435477793 867877842 864569451 902557185 137506479 740354578 773175757 676085429 827095718 313968183 222405293 199978898 220879365 226142033 360947017 291929558 941544059 527149735 538436351 116676623 991150452 238690605 484885249 403220412 638167745 311254583 71910397 646911060 355014072 274331468 813502828 817011608 55842908 251917612 995169910 664531911 493281787 323308006 611971626 204380053 183558544 146775198 821627290 247941511 182743983 788367524 696366129 237340065 58755604 852169695 771549135 967136940 890589212 106404406 367355915 965964405 426781230 651046837 611588169 660492129 752139690 951236166 845969662 924907245 789498672 675898558 469691465 257440306 49757138 124570600 776238921 703407032 62259967 705496497 542343144 28766217 748461330 851774853 449489960 844513569 741555655 584597637 490846126 433989367 229700485 226612776 423659951 354906257 749036357 908717328 296990846 167462443 31847092 951664414 988084422 2299225 871169923 784192929 785591203 176232914 685046654 218451407 346712195 688538890 584031791 270063122 688568012 451692974 194861579 997303914 315354616 283156462 750232378 421423863 14779646 813111211 335944975 13712668 278153695 151123351 327406896 219118098 79107096 303357043 592857959 832435616 396801657 743994378 698092505 664902646 342200618 83789148 582596369 682534847 978941275 642012394 824466359 536670449 799822245 209169652 509388980 120200075 921049253 372492174 880078093 970100080 68369944 891035367 152181150 325352618 403460176 921195331 953057355 683406727 327255057 17315013 588032359 812444037 764718189 289625072 854743020 628925854 794222722 465469897 750292319 694908816 771423666 555379996 698796791 476020243 348750628 31287544 280648757 6343803 441149863 470981274 36857834 133135387 438367091 981914471 702954978 215630855 970578349 948562599 914032824 968232137 82462074 775693388 522342941 876304774 900444980 231184063 498747198 711101531 629026718 785966589 451353560 503250355 315943473 247325891 474362575 939283197 656602199 756178459 243440537 80133670 784481909 11989667 545150293 612971057 897438741 659967453 589333055 157233465 137809156 512519477 725380660 815337769 310413339 55479825 579433757 910381239 857957141 164184480 727742531 159688265 767546555 920334227 534304796 999658179 302778310 512469978 970152637 482930911 787580280 369498633 82843986 991902163 766831941 22398641 316933558 332076530 746393515 342514400 133245831 889813075 513688229 143599449 168687751 106782515 314741546 46252362 943541635 407607978 988594083 747155949 512656006 492468551 560871689 321820487 292837542 410087807 613116101 307128943 147963585 769236281 356251868 665396814 20962068 794716357 746302920 819756009 454486639 158089983 808607774 843496592 553584354 639091123 826181744 254810796 425856822 442205852 257847070 827401057 674161978 967370204 714651321 704681417 967978139 814559667 484400945 850799194 999924080 634889291 623204115 103577323 126624829 195711165 757006421 195899534 197178486 509534235 997517421 183340959 578903594 537963897 242225187 384867611 4336111 183818869 837252785 125101994 359704561 207018543 133398269 310797611 668637030 76920217 102870353 807820627 948203583 881199229 607748153 310523799 866248081 472904460 455415397 545491784 230717683 337492546 322515731 431511779 453268315 754103616 694507509 252535114 331056981 513852097 303238549 689985656 100241903 180086956 764739806 800279888 464556239 903238835 819661437 214904249 971362677 87327138 643351440 892067230 433757768 552236920 661954691 703999473 369224084 628894008 236249282 710012652 712257597 209656251 288913091 110650821 108852553 356815828 878130518 827663674 726591954 105564964 600599989 72785352 947146167 428255562 551165194 843727253 357778043 370362450 748375741 140334529 491592269 556861049 948035734 540657947 87924624 452945664 217854425 899072450 86631787 129814711 67508229 786389821 495797980 394716679 852353153 98478931 141416284 198357079 421184186 909902165 416750798 275439350 50183577 340502063 12782725 535834677 719858666 701079656 527431450 404806436 910529502 471345525 256774571 160329481 464267797 654997537 167179091 143119005 596328439 52352761 674892876 842008135 628764427 117326566 927062958 764730021 134902176 463781244 809944814 439779616 420147495 688419107 237206440 723745475 275999916 802362120 750185639 462400918 539616558 928483702 844247045 668021989 7476051 681221868 916642362 466413337 781251342 56366251 734789508 814053098 268053623 321913521 780221784 852542513 356406363 458418126 51546178 769328185 573416801 427835856 356911528 82950655 441385182 492051464 224407096 168140850 522633992 869995746 352824631 902144921 148666792 418417832 685491130 255611695 166947154 144812389 18457866 208462086 394510157 848447856 753786555 803790964 268955497 867958487 73210197 461804432 117816927 210325964 842459098 237148554 952144831 449653125 176086490 661786586 363746058 350172452 659926838 108872172 233118387 850896761 859887209 92673201 686708075 390572436 754955742 460783104 171938218 218848774 500382320 253933860 134115744 284395971 431236691 923833132 759776894 278707451 616799091 174124737 986762965 103122967 929096729 264060575 236458447 504596325 863725501 190062454 644793967 150834081 339470541 603311702 17237179 557170012 293852572 131562081 694638259 113532529 591797316 858549987 367026936 906478349 201222892 329495984 284811368 42926446 777794596 837792624 863051071 623111865 133182450 392393662 489432495 332979504 464171652 955994033 895800345 940470105 248718237 954745877 549745593 890466165 584811203 541600672 517815477 638625049 468540299 325234835 177712372 616747048 419928559 232204416 849872010 558153896 636780373 362813394 402722810 33822676 299681577 466132617 482793581 592077319 252944824 743187018 460134087 570647444 212053297 604021128 993624990 123250968 872776057 92134075 879691130 575787582 608535651 365923714 175792495 518007992 304049007 622766958 150925352 546758420 59920566 573210589 320629528 146563497 272477384 35698249 146810320 780602709 277502485 737718445 278952842 167663655 371285432 165168100 300338960 323078779 774193323 636472735 113088930 23914917 180992770 7741282 585771952 221384871 182165491 861953965 568650570 894645354 547872851 138459115 813780245 699802661 492589587 228238677 223216368 771567539 301269623 43904446 18193277 510646141 795555580 877688406 537472063 428983024 971329582 962307390 102471624 103490892 274004980 421109050 874104240 695183226 352911771 189114203 80424780 947557294 811548046 541853732 19288795 939935547 452251165 584568721 27697511 818266566 414466392 297111577 63366534 671606393 236904036 807913359 860309954 741980068 191380704 681633345 507200583 46880987 356947473 434594019 779076749 163329520 370708297 626154344 278480684 839383122 561239457 931478655 761709006 849390977 180678822 642854079 947428211 443762829 641793161 594893236 508868823 770036820 334664282 571707228 816699801 351060085 259795350 106427453 418879594 281096354 938038273 106393909 107007675 728380023 391066958 284856064 127976824 367051559 107334108 583638272 970902438 664332011 342841304 198084426 78245255 161983300 278145855 934565913 687225330 372492361 992330745 152600157 91122447 725904193 848768721 983441462 888496097 519773578 653162056 819237909 300087767 60096041 491569511 493111510 655291741 12917584 290496824 309009894 21475154 370255274 740003656 195461593 915871747 975512634 942316196 666888195 345651963 538410129 75578751 102680047 942721038 381360811 376991861 124666708 683833780 4901019 987680465 452194380 170899076 87686949 767500667 472878580 908476248 714109211 268831857 680744791 340793094 148612494 512374385 155377213 673160559 243876819 350941726 348968694 776386811 583293860 274095546 228264437 145831584 57249794 686929176 598461316 233624343 481043346 157787568 265250749 20785300 380864980 372929845 733712510 223929042 223745883 335938880 335075098 64481792 979069381 467934009 387325789 399678087 538790535 992472891 107203634 200603121 361040129 417746119 868623731 917680224 188577021 499524893 454973709 863098806 416850347 233302322 443683611 161833038 655702274 254840579 380724256 270636518 822733585 459723961 865683051 95176318 512822311 468565143 943573094 217260496 707145907 208292014 510836636 912805782 645794621 129129643 772801766 905250927 495883682 573611776 1242608 349359409 440194389 554271067 185713806 919042608 898006301 723437074 608163544 153701619 848534928 619186684 894156222 56850275 991296838 580422799 826969223 240547591 877270778 248947694 247113776 909544038 200843028 847213456 739142573 434657057 676017357 761129977 675668819 306531866 317327399 847923465 209533204 850621559 904806586 439466054 540899996 127501846 256912082 200669660 611236846 446322334 355420551 381098738 910328567 293045178 383802392 599440666 695780769 672587227 136134497 583229369 120806066 646832167 417928691 193989520 763442751 983423356 827223402 309316169 775190438 967319730 890283327 114672474 143562318 293468357 595936355 552396935 869766948 526709157 528864055 491475349 220909412 752991176 735626354 52136095 888353066 696011748 237071245 541456171 492852811 945952711 401282337 692495917 44302205 915725254 799789228 703323547 577314639 690188649 945584292 525855908 216191709 726973771 697797305 945840358 440683787 36946061 302999862 856587268 244930877 63752260 352054346 87372235 842718769 141903467 379922965 243934314 148675390 548365668 155797239 118044712 954830209 605355997 570468575 835466419 538606682 931959267 992399203 389987476 183450560 707519275 126339747 687282175 732713819 257162505 586214727 376191538 209930016 734574135 425415246 910628811 850640405 346953480 781738226 26730966 171899228 215245733 587720038 966163371 820658815 852427776 152508616 657963961 957715441 816962510 716102405 229794722 143477770 427908986 117831377 10335955 920535660 881932551 992943462 256328592 953237532 634466477 833879148 448099299 586264523 667663430 296720521 244834797 561272880 273062028 270991921 170424545 923724123 157494516 907333156 64630046 847198540 113378195 560220012 948636205 279177055 196252445 192235203 579423171 205642159 144496567 280135977 380416082 155958646 218638903 153432487 27924914 391788451 417694925 837045774 162158505 603829228 684992728 88068466 654424192 472548328 87029949 839226484 161636536 155307025 270769359 51860202 192714044 528739676 21063045 542895696 533258884 991897381 809444509 659560666 791895991 189524055 618627426 987823839 852375344 735410420 787871189 983906505 745701810 827056855 27029191 373922097 980143509 31786793 195723708 601828334 672592241 873189536 293379567 720358530 616915622 573162761 969272337 978420173 708255748 403697694 746261557 673124822 583665235 633488666 762183690 203495147 484140991 972430165 160331879 472585747 55299170 643408572 449891336 618528264 983541720 930031089 824185866 481004311 69432591 990319344 595931503 19552930 585827252 371098689 799507756 265675765 736133975 933710011 458338298 132298388 436642147 122662961 865196636 678397940 431946917 20287974 78238863 3447027 443112221 693188152 728822648 391672093 146635778 651208061 117698356 870570687 110548103 470575994 157953840 611410566 409639384 357697534 476520282 852626471 728122015 371265079 195548586 739702978 411705843 822270787 746049597 305280854 139735628 868480955 666093014 795185074 416105622 494186548 978813833 668951188 349297282 8141250 12543363 182964884 638134706 585143923 282449102 843136789 390024148 336610679 47580565 667748525 933599542 59399402 946468968 889399219 823402269 381444975 950305797 205955953 261706757 140133297 240575559 55024582 93437081 818541486 967155261 750214377 238464147 486147410 309204923 829360604 773116986 813663000 10674985 557755625 411216178 28875429 725456326 883724824 920144830 495958210 147351892 856851594 431904298 65720451 9020664 894631855 324826292 406747789 606654845 852624075 154228887 592392177 943927454 827724716 992896611 477898224 204640162 199752538 912122457 115149835 542862638 253506330 668287668 19487733 10801534 338413809 703087581 540211422 499464951 424778572 812089997 392500940 87774446 766464860 13671568 428052871 446064966 79805033 243680636 51715547 520544811 623420072 890468776 79035919 484541469 9118960 485384527 307025396 798621101 855179961 532958529 84882542 630583047 628914301 910290819 657969698 595358933 564561661 542303042 227532629 973263020 345848464 941009132 476052279 792748200 117994200 94156931 829269569 389086046 318286886 139480066 710834280 92702948 919813016 289234832 851888258 587588443 852304625 754308404 61050129 515978860 231482161 260692625 916411612 117803978 891085675 373417280 78075377 896257671 678554580 817773202 116803834 515235612 444345978 708966901 595845646 257866269 524710141 716234815 116518145 892945185 461363189 988572865 631645336 821645313 104726210 132299026 538066602 540833030 246787582 720370423 99125526 468894310 914604988 945226005 895993271 505158389 804332621 537159162 674787050 480206588 155865483 480639063 504812770 45172194 708283407 152972779 45646558 434765497 595819887 253881669 932670480 175634298 433406759 797913096 661189476 616897528 899632151 301584598 986908928 534816770 565257781 260223426 658554666 870023557 81978902 850868050 317663963 394732680 100352290 149033155 406653365 891812376 715688483 530189847 588869554 311538408 326895701 370151272 200116936 176141636 274680248 831700034 644950341 176151953 860208571 640201882 499826282 369479181 871593015 627440284 175001821 666700673 77145179 632154511 294086758 313494310 465925083 180090246 674663541 971046798 84565246 327023686 521352154 180334417 293786824 181065363 418048139 921210916 825473481 59058478 975808431 331679647 487237580 988337949 477812148 328941521 859522779 980537592 147092689 297989416 717449688 510384857 255691835 562268892 482773701 920725759 527084765 524122048 568443860 15467446 187668193 562565121 848600631 903096059 658567059 4023350 179923679 330297729 10204341 115661677 779477037 814159014 631295703 450883935 319154258 452468476 519472868 605278238 422710120 718499982 47283715 655004376 530874067 386314969 69990546 629773809 332554016 305341395 65371771 526399837 790465926 502742451 130730107 431274956 56591033 651738978 720826167 604223464 462304955 759259005 911719128 187945863 510674312 714790238 314145717 796535006 774906397 993340626 152978692 988722843 94624915 644112519 755312160 386613642 917558439 899564111 239396327 315202220 704698456 829555765 802932967 95571252 153933843 943480202 312095304 583214637 630590967 967237968 475510434 144144117 224021196 828041271 584978837 512138937 581412899 658286327 335830609 231510443 994645500 265533892 642237912 872465583 871628599 163766547 947876296 20951558 172666004 994209407 69571387 107995996 757190503 710540035 68566348 890269127 538021717 630645145 627281757 184052248 717354751 12941088 338312339 806242343 304166273 789047970 330585012 528383702 389981932 850509769 545944462 102573947 977770088 847980028 922715634 126354562 683674679 819743214 633924427 816145880 998468435 649302439 860160427 389915596 329794749 937682244 427803313 751511970 901886290 728262634 466032273 134815078 689455567 48282684 361481020 423831829 348519046 86577556 448206031 740390860 773196693 655096084 451186794 430607975 939985749 984255803 714734118 310513667 356250942 707676921 530336931 84599720 892872129 942915226 243667968 65187598 436903211 26167146 426924462 988192556 867920842 662553589 312825062 1670823 670523985 159528112 585899129 88849135 910640615 447420753 451358188 873530617 196411057 590282506 80262189 480571293 849794855 209280855 597274901 438501720 841365379 680042332 259598303 942524669 684411411 739071040 949250779 928272142 923248909 667960413 340366697 689670018 66784049 260416523 3433247 652206421 467329416 79114860 959335611 5120641 278642444 472806503 351898894 722698167 845602176 826207329 537799754 831069806 902606447 581305166 926391061 953447220 239728800 154398246 478501867 848497251 879016753 243996120 616637896 816782205 15887856 505072362 575168821 784409601 878389502 986921082 940189548 319299262 999320240 55078285 737754187 444133496 116751603 296864019 54519467 323428549 128836096 565769106 378194688 394085003 633642087 364099026 967231216 654364861 304835375 524091115 464721950 420044971 95837069 676229945 893747078 314543301 834395139 35449878 928202775 141389884 659752258 913638107 397944558 451140839 556643248 246757575 787196801 796266529 306208735 525053666 282634334 497724955 86266306 843189145 258510921 35981964 889023408 827589158 868846395 584313828 802037440 46373305 939969474 904882485 170017488 141878931 509846651 14069182 52742491 160011946 976652458 188450125 740083364 992780732 177244468 340438081 846827842 327165280 477766839 668943736 414114658 314102522 285111942 575649188 759501597 577127755 117367021 559525397 392713582 292082560 381586722 838597931 729461185 182172774 908293701 299954606 902818567 748192549 378726769 172859840 869882104 936958685 601602550 3461083 519282256 775691886 468648697 959406430 29857915 759872647 839750757 67642911 363586776 256609282 827427231 977799908 463544473 251782016 492757115 838761616 215479731 574567117 897790613 226401824 277383761 613147657 15033039 241667424 191988610 253910194 75987142 498994273 831986012 873913014 622894574 209856137 927323039 239294928 641267320 477615894 336696161 621045391 576512087 483719966 359374888 571670504 494361902 707403778 107927720 298587952 479291694 28013740 882278382 703967202 337741763 673122728 459084790 341801504 725572803 592241571 299445821 616008915 663340246 254792662 867618348 375128862 417784632 819005106 530733243 831052301 686889966 318544151 383473119 343317808 267007004 897118324 144448064 466404864 468455423 967554498 57705879 666618512 369162004 287885104 411153296 585545245 99739998 164501949 933371205 854453079 698844159 418325870 792037223 402967708 226245854 396480093 58969574 659391608 670439393 508338880 549590586 295910276 794661714 529517030 221867639 7690642 558952830 851030999 484067066 987389364 933550262 801408452 3925825 826378490 478358492 335853736 135645843 578082847 640551170 297132563 135618455 681217270 119532770 992418012 515237437 92910697 277764491 354189320 354388889 597160305 760285406 865981240 297861299 467775150 509695147 814200754 981272643 948642962 340333203 493704694 961852517 944366785 927349008 992682966 434668877 486700212 498072619 611586538 610637754 521522298 516835541 168070525 189353832 708565447 224402446 423765484 439324137 719495769 254386501 273971332 484615444 995097195 260046800 229657469 179382870 580103868 578699247 333810376 906109988 290883922 54194417 655744382 451359684 969352797 905738316 426084543 828853261 46110170 972777046 385184178 491476552 978662008 57457530 922477469 595361351 500477356 289115548 54886544 767311149 963450297 869676083 968154757 491879752 201608075 699705756 924009031 624685095 527321906 343657911 183930342 306670743 977297786 504357845 531405796 893287157 257916603 699325060 238394108 641995179 732818064 820609317 2731671 714730338 143517539 699620896 18022520 793254902 55748327 294668099 958695877 928943407 822228967 969125607 522611279 50777933 105687694 966837431 718516142 204160807 854526763 146325851 516342479 422609347 825581696 45289446 563700033 3411324 44826436 677765899 664368109 880844380 300771207 631838704 190456339 12918813 959727670 81640755 983671065 134377556 611360518 511872038 212424938 600699441 403060554 548517604 863101111 472324572 359195602 192802131 713326480 21915161 916801352 716372049 257315387 934720345 514365033 833504549 33989450 735404850 256244102 441465805 960546491 661658157 616418291 235694976 113778549 659106305 942941760 304501935 86063147 450145432 574701 759477650 826202384 369673802 101211782 585888694 54696412 628428697 388476470 865869370 973377448 857234711 262308924 497956816 860995816 148477079 270876671 865477064 86660704 164505502 604314086 778910335 926617815 485824074 762870765 238379216 169745335 494116833 981365157 215058160 604043482 784790662 910569343 973634452 384969263 229015816 251767123 81973913 850104671 72616975 876164464 972265062 835568635 934324762 308496075 745832442 695368368 896192835 153495636 699320747 923453002 23310652 563228804 973465436 748101861 588690188 110975948 322708229 235597026 761770642 155011396 636697183 536654878 545183689 27890387 302192387 501062024 357804452 765769957 354664372 507490041 28705997 745015055 944936020 993693859 560453716 268880531 717636474 725277645 11400909 335086386 688656281 230436156 176504830 961613534 892067717 335329941 273549146 88090270 26926858 306008811 767151000 883811238 353470049 622142793 605840563 631186034 368470893 669966724 811559166 780601912 532249326 398105392 491695845 642495434 164385737 215518374 733319020 872287523 893749899 365473327 301496531 401505116 197806029 344366527 188524903 779819058 6038821 849624142 19618134 934474848 262469629 160075750 661734007 662163890 478391294 153903145 639651637 507606607 28145995 528879518 57206255 217016587 657178909 294986421 141524007 112159783 504128627 477646023 681868918 96549464 244127839 936386545 412273947 975963728 967576279 351368810 466388819 782240463 809128327 138200510 861457047 766924662 831113926 140686616 486892103 611920225 740096341 194651015 901834761 111808330 608725245 747909695 350765942 774945406 541701043 539276570 16281460 465991283 809360094 110989812 677999631 268642141 49392344 300505664 635636353 568165884 695386782 794314281 339125097 956159658 650777737 949429288 850004810 776037183 133299450 609622644 59887514 324938032 13799300 831386520 312511031 783406623 291266422 177789700 410266494 580375164 356501564 31334213 425729611 653822634 750863575 140625999 209667503 867966385 85317858 64676379 49211717 802210521 471012344 450236187 128354951 574291901 816153161 1781581 724950262 507933066 291407902 305920302 80156683 350476533 115047204 371276453 240234290 458097082 689820992 217596326 488102934 772298694 591538663 267623 160113405 448589207 800677313 516938781 220927115 438412294 409395127 317700394 715144283 632717216 237382477 105219434 42014809 138120127 623279610 753607217 816428556 223296538 236466296 343611071 768086367 230914374 891515470 701279498 245785008 612265074 324198444 725142223 342377628 236006127 88843448 251146492 42844612 850538237 673492775 455991335 599167636 455148134 489908823 414295474 871350504 190746093 730359763 610670002 440962543 529248200 12323366 528613191 148249025 184754532 163791135 138281643 196799975 174709540 494959982 949966773 618773831 436183699 869268988 749853242 839594022 847158327 168516079 71324203 193442738 288725051 90400323 605891240 297334721 783755315 721686883 357821999 584730184 439117892 971597179 130092711 933575212 82674535 922385065 988687502 566540828 450656229 423931924 854064101 340654131 605816898 376357217 951512465 431339129 918424336 950138656 260445958 856925649 772633172 438630046 607967830 32308116 375828105 155336526 613557487 147548576 261839022 99466266 623159405 581578340 297190889 524607377 190594506 301827005 269048488 148746783 401253676 109422517 569262707 937880386 636491225 459688409 462616516 615004248 415261599 370232333 122712353 256560673 885327364 44654192 409044314 985231210 88006498 478672848 604245715 14128078 808669569 742221682 154683573 91651624 365687228 192988441 579228459 979835388 998305708 251004939 513369915 693327973 499300257 583167131 776467296 320500430 486532161 673301654 869466448 529620878 182286956 508714805 548746241 59877817 104468978 800957761 654536193 134995186 932091832 75129414 474192599 765554523 635947192 56280389 358616594 956816733 178778812 457132945 420060495 347363019 637297913 2771502 413048824 82707165 264184602 140344451 838426705 27029666 724771443 660654081 12070324 261898335 915816793 18036057 67817046 977560823 982553756 575632163 922074891 454652223 863915550 721624644 463145090 607531291 354211748 827196662 694072274 404211969 248856958 790753571 203423915 541676864 709349662 827326913 238743292 446411161 775654009 342281060 602760493 363470134 285589315 66473597 589471533 678087085 635642961 188426470 105056044 710133193 835915065 96520128 924817468 384133908 80813561 49352796 656210507 979362320 77234321 184313322 763583154 526071113 604761553 693357004 728759643 245091226 547953386 770125198 270240454 509573431 848695311 518097304 907140369 132057505 854979046 504262693 643480174 266300001 767430542 606941455 757481178 469054375 460799909 220657043 803173061 797552190 128207685 165064997 862555454 921427607 143988942 79839651 193981021 743516843 197575029 81559681 319449067 925833429 311313942 546168749 881776337 88926730 226285868 376268969 496325951 157403162 681040998 720089172 295375703 832468427 562701885 433526787 844722308 200477343 36972907 542234365 524698599 59008402 131862721 491994775 352297833 579851362 895165737 173227939 217459741 622924122 387354710 8996627 563047782 481956077 825604699 527716298 844284478 803371130 147847583 410976136 676201528 931344152 303297214 325618519 666881859 656418703 196148768 951002906 205139846 36105284 626265578 387289610 824605498 493758557 610224634 709570466 105897186 96096778 928601649 785947465 368514659 214423133 154147624 820620523 316236399 331360677 350899717 191412138 990331211 99066870 847898749 590878708 180973856 245900182 169769905 391527106 434945603 369832662 128606531 765315892 863174312 911612127 644449564 23205699 408684006 473928807 138060397 386266235 269575199 948518624 546346419 519744533 49231293 620322986 264619572 661229871 764386080 402523783 253156631 760464538 741655996 149658888 89396689 436463051 960370771 572436629 380272223 252653368 556303055 154567597 462529656 228037626 134373612 350620869 722044101 515897155 992087021 991902482 89310755 238262895 519250184 384475275 625469643 166345861 330319142 931472155 990137471 836078054 231714168 188049143 930863379 278457243 87474548 846730571 748269197 912162359 967033601 369390462 505810445 466443050 463611869 726834074 787623442 867026319 604904096 377326919 37927013 423248548 339351095 638459166 579257836 117006707 589309519 637595429 141008616 439478877 373611898 804187981 405212949 180966103 778821311 984518451 419325070 20917749 720993538 535118011 904339687 47522049 892056470 372150592 780596933 550593130 780671068 78584030 169612436 630461783 711287667 263738868 485557294 383045845 939020888 931976971 475019897 344854439 584466691 482703077 455913702 670962545 128998776 330148455 372962713 468628556 402208907 737077865 824087047 322835714 381990289 800870849 832226229 866765072 945135609 168090304 360716029 461540598 562107719 344995239 501624221 842692496 44867003 165235831 297960168 817987221 337496007 311375889 403529951 150160622 321244321 856650863 457639309 233641976 68048280 135689221 632723073 811368432 293856635 610791267 837566971 960297183 75647816 38378846 451177658 889861736 749635650 597741101 709789636 484533951 431810748 227541722 109225207 903374141 792847115 925471078 781482899 844556149 718927643 473294197 885802339 992199284 283385746 1188359 586322534 885269763 724791238 389512882 773434387 839026075 204825363 709701023 505176011 671976815 157061109 520706182 555034202 420672999 89582307 214770142 374965013 115544987 662326169 356546405 871622718 632404373 120776547 856710200 212334602 205416564 301662612 522446979 394838322 432117785 199367574 590175414 965771540 926812595 659497338 616981462 962664019 744904808 510117836 444520352 940025174 748078928 269651902 304019143 902234120 424875612 641576880 50120192 532469518 671314988 497156159 169441893 357822943 118367842 769395187 971215374 32366585 601188554 724692473 313177123 776684348 810251789 681321958 912770617 387561376 302187527 975947040 304967558 221513025 800813369 231460486 197397685 835547680 933419052 216007258 874086592 439690029 875006274 509633063 732817034 156376360 833258420 983122578 156562685 116293871 198915159 293853857 951115338 297967134 26951907 706123257 280956739 64915376 628960601 433303404 618739125 367655071 129528356 395921913 995589385 242887299 442079156 498388664 410694113 259421152 182622296 132832514 925129155 316205364 888961449 196906764 962137103 528524636 112517737 542612904 394327879 828969741 793531064 557198983 672260044 198297740 191122268 402472075 796080050 616325619 659891151 148332356 431584279 902345872 182290956 888056078 404541779 853198662 958685403 263342373 180661762 412903061 283379983 71481178 949273147 512538894 187655156 643196272 40620220 51650283 929717740 578328567 879298938 306641152 707070109 603665691 844096998 837190342 67220275 102206190 654266127 522450717 100704349 514270999 853600100 173594457 779499986 932555665 153155060 687275310 105902313 78254461 28599060 438884560 754924107 693753419 992373546 786147714 420840231 387117382 249204531 201321745 422573041 353516933 529328528 330607520 813233928 403767653 425109591 775498841 800121629 220819666 176930865 449211724 41165875 145648062 297545513 211833415 751133105 72583812 51876184 835585846 292850005 787494554 577642482 578240074 268164516 911778721 834130423 455681655 870266873 784509866 454070690 448510739 404641400 343113899 344582597 543772272 331259978 687993978 645431613 859946298 109166926 727250330 746934484 680246182 567724557 169706718 898276529 924425065 56689335 238409855 407576760 332655987 686093918 426706401 690163850 603008297 77206032 750249599 745172479 435835657 205228917 770406401 743428516 319745474 131389561 671663609 391317042 461539260 930871231 942049890 379126395 477438254 675849532 921156141 133130786 284476478 793857858 218323170 285197515 548631143 265379788 407407460 793809783 238146507 372341422 622686237 652056563 680911794 454498507 397174195 255845653 169994388 876679426 761364007 193325474 104934662 841480734 797310078 591208683 794779004 143970596 202743753 348305119 428671788 674092443 541358039 443523832 599780366 897812730 970927360 13657347 822309004 771733911 634236611 469795696 55428565 826078419 750285200 785268690 317260152 833668772 177992217 396279143 547949576 813478776 736706298 423861310 626139574 359576668 62023601 907263467 496593200 381660977 854883371 582201879 373427128 675198112 16531056 150704918 709892421 661408571 495503141 412700695 765179170 834411448 98862442 626761056 23940396 940658178 255199076 427938260 105555316 924871697 678484871 538513022 28932975 892882982 450126698 237957743 716488027 927171182 867792954 415862617 264070705 407503687 429186787 667821227 59522917 907015012 561126105 654319223 428508962 52290815 821473989 847435699 523953984 362342543 546371282 589267200 393192684 824205984 181903411 716192871 738757966 698215354 412887672 861571207 785764684 220622370 703180977 805185045 11459242 909522613 87205286 540966230 845675313 978285784 524429588 159671028 846468145 573687527 467133890 596203135 757331924 600529834 249298463 954024187 239112713 44415672 190435167 8442784 482517241 929579547 367637109 23545725 367770890 768938236 100683080 969967249 516089463 119338935 707115284 469857967 664243630 247628188 637139404 645331647 119240505 544461259 781536763 150512518 798304206 396690879 756325124 96057119 929330929 816904630 54515537 243005847 639270766 595062260 361915545 389554184 719539476 395404412 304959331 602883750 671143476 545247606 330792060 920153648 474747137 507324707 777088400 976894166 852507095 859887437 946041720 263297556 367203869 956467177 37910001 460555792 229012336 169221634 609846390 123417925 185369864 949815442 623869847 728267248 869745334 16635492 139718159 287909738 893445018 694058070 145877419 227986609 120780630 394105132 305598126 773355510 545244038 247636364 791932956 244719845 476250407 733247425 666660874 383260724 765783560 988900812 201139942 975516922 993119558 457795211 375782573 71166538 750333778 966663801 867470581 758144845 216255298 918857607 411752123 6286499 756526668 961399684 160172760 381965105 903828737 503320526 22569129 482173620 291199013 657796434 764275887 194995011 137508549 76885367 250880772 147530614 551919582 942498076 468581641 814559162 860916846 504342657 215526219 507978148 387423807 39692348 208056168 231662293 371145809 343638669 367904406 180163641 2429625 912325760 441741182 547498383 347162029 338991262 561550709 657197979 282882631 544469623 240234854 207286146 884580045 146553653 260326299 292794043 839382658 458321075 695812101 555973723 999066386 221006413 863990963 1965421 895277288 900880348 565269865 682233357 897168183 126428736 580796469 111420586 469580641 251677760 972351285 633519079 642939201 127202963 522672598 382405946 897172933 980175357 303767940 879743908 205954230 865851833 197163176 422387397 436435786 463947216 225844816 779668264 425007915 790123579 638998588 559590606 258402294 191831390 373120441 481831819 708626551 711447192 683973859 500968537 692652658 545934189 244737807 714854596 393231677 487701337 322537915 211456552 766610067 528535438 997853345 227128041 793612566 285075464 605137687 734214857 504281351 922595737 945212836 699630362 380859987 213189901 228891293 754156288 165341869 89322273 596596725 910530479 224714600 200820822 795916256 434745382 2852141 443362077 527004335 572617591 746832004 807230141 500002334 616465261 878883105 896792737 893672332 240464471 301567997 409178830 668386630 432203912 584282584 979080641 318542275 627782752 769595901 912333392 428588576 574804816 753350040 805967930 439764370 729700833 974293471 952712959 339902264 646499982 335381205 773137379 621754212 917088538 73234127 208489790 980040330 790024869 795885218 138837953 816873309 162788539 98329404 959891236 462688411 274948216 148128977 533402435 152921580 601727636 655564203 100845167 469673612 402094840 402125724 235918311 196714666 162804390 362370391 801046376 230489064 901087611 113040313 833526844 758123389 652739196 952230904 636116504 694606089 397736661 233821466 756259528 883842633 944558800 743329799 368715771 335637755 875086270 843788823 942063748 332617425 530571431 24594665 145072207 697321543 839446973 996632218 473958315 960347442 994118405 144165644 839602109 188043409 701676483 870401063 116991927 474781284 967284866 979085081 631479221 228833825 407773511 583297480 918393458 185401128 36667659 988657173 936539301 507153236 447731397 583262560 425263583 832985863 847332804 608204631 123598000 749302915 231853866 799973955 632677207 180514384 117299556 615907406 213253741 47942624 989570231 941968763 670401415 358173908 578884536 712115478 978601770 822798895 344967128 605854271 389811412 473653285 786896832 218252265 588957809 368562471 542560773 284992128 204376303 837682483 666187518 809369725 896934082 308248604 167505452 36540696 978037306 478699182 682380828 370067721 704800738 816636603 409950420 899685718 864506315 224988857 613117783 960830907 732445191 788524802 6612995 282187181 455185169 721630783 508952512 51413907 375754139 302287766 136679027 70067076 5723547 220934293 93270907 89664749 314907273 122797382 778595586 481202016 55953574 592319409 880610794 536638985 112450973 911032686 216645451 493701177 969966011 459877062 373505348 340009422 535579543 630723886 355594034 135593256 662912111 767637118 749690154 135425189 732347006 319476490 692150807 879226993 549790338 6992825 959002963 467762665 81839354 806541945 39471697 54328137 642623918 729388867 382925304 846875605 454025354 588071015 772098731 466037691 229193368 911635925 723125622 272511838 721392181 145115844 704745328 8532625 811138558 911012348 145516273 747829362 753866312 423204731 20814833 106886652 85727556 501540853 967699874 884899895 641271898 600301287 794677837 205205903 65487928 173106096 775226427 753480827 255953764 170568993 660797219 903073531 568787872 583382603 460084121 877267132 977334306 252690306 62983579 802041248 170370669 641881820 328486830 838428297 263512825 903563451 69392799 683883243