975 868959777 921722392 691829302 777146809 284291561 924639325 414747183 970401241 738194385 944192119 770182645 874753682 894584194 923181350 700722567 707712825 187025753 355809530 845143305 849251960 441469339 782537631 163477148 574388849 29083615 992252755 98096665 410327251 720424777 795070797 895459771 920394179 265133114 563753342 80403736 896931719 211765703 443254139 43167139 800068193 433294387 566657144 609144600 672880520 951336441 980633795 607354318 616154078 964593690 966537868 771738066 890375698 561091687 808907893 793256328 951056783 560580955 933511546 395357851 562092359 952653661 991077991 176022263 720929284 515633468 985661193 721901158 916745291 103399402 639741996 768511057 775015180 548098404 834092102 724139521 965961332 174476347 311163156 806352846 914975622 472063356 707226784 267233103 882537966 302767134 571206608 473587162 521922901 455480180 715095516 999544684 999678447 966769223 968314284 530308680 998954840 460204850 813949028 85625964 564214654 187651343 877948423 308662885 843689716 534466397 549881440 947162756 965796907 914924190 954546438 378905679 501288668 160379293 455467908 219676525 890238967 638510860 684326512 729651858 968575538 543148026 642932588 785981162 964809046 868099619 896044637 591708101 624336236 897263783 940766801 557581171 892109673 404993211 718629817 187329050 489150507 776519267 881701102 831878870 848523061 427156673 968236925 505659598 805487800 378197866 864984374 559513078 634453967 593826789 806123028 533021254 849432033 714208576 893829481 703997319 823053911 990933410 993505406 509193156 646423690 77028061 141784326 418531236 439200685 952953473 985446277 145086191 610395244 312998835 431650204 265084407 629688227 896057677 975560123 751165855 962056989 457760298 501294006 497807438 589121760 568806621 570342504 669718364 915833102 58866128 218389778 281044355 354062203 325168701 511306563 111938131 269607762 100220563 407446352 908027008 917921463 156440325 639060784 271189071 676330058 278954878 661138760 685905711 778773155 87574509 539876299 624533305 848463843 281572265 863682976 954157428 959054989 806198822 843188035 86093149 627646194 208649023 657996751 462130543 667935679 321385671 892381888 949910348 976202615 211736153 553055169 749100431 785319351 673293210 914975947 110165295 645400760 663861555 928048688 821394656 986718001 583964584 988386518 75473241 733304886 546139777 743941598 978175166 982635883 875821250 876649351 78238577 883320588 818433782 946033974 302908966 456280895 91166556 359963269 651884066 883929931 811903066 892568784 208161314 723946570 232916414 709634723 921981009 985277570 259965722 665647294 94897707 794339221 307107391 372606998 188469770 852061191 459338136 489015762 952688835 959283927 88034602 939599819 894223785 984565709 474217108 884929475 56333571 843777236 245346578 378749554 938361522 991925929 623919425 822014812 249144591 757652288 372095984 680596591 771531585 778692329 266124433 544731959 183333745 580930847 723295443 919175150 643977112 833048831 564591941 679264332 919347397 986037840 285348289 765262003 90822597 172284663 353621337 600243707 327649556 529014918 455314211 782956692 407627085 835995366 376190164 775243699 890732849 981683422 758727947 960498707 48771545 335954263 302133463 823900945 622735887 970826139 218330879 514103312 381808076 455477092 478517665 812278994 637102911 852438924 549729779 963345852 687114508 921431055 688178846 974547180 911241350 948650023 493272598 575825277 695780166 763491484 687660476 900154506 866679672 873017815 655469298 720798100 468653638 597296929 288381413 718410116 965424198 985104249 579148653 903798927 867408561 909827187 661142729 936860340 891418980 980417081 387316496 468073173 870616504 892924180 144987971 186260175 262929416 421485580 548281271 684158244 265283268 849580006 232697522 823640971 294451731 629467678 143457617 708057281 308913674 963597908 351906781 844582874 99735838 527331591 682987712 881132608 565830416 816952376 681438133 730379289 858358512 876203501 622984573 749284562 100237182 604624031 772066989 958615323 506171992 971684319 545856288 741780708 894476065 923742870 489367108 787004921 117974651 838672981 798523973 848675059 510021894 569371588 530927124 753544345 694298347 854262397 481127598 715412001 615295475 861998257 536622802 599349854 19424252 570351026 611186342 643101954 720321665 952316523 789846536 792058457 965722944 997302197 983640400 991919704 347520700 807681849 754117414 869377575 764564001 901192872 786081151 792035835 207922588 853089195 370051515 779197073 947749033 980319609 811234011 963128950 475875653 916388143 467623600 737283784 112749857 617178664 837200644 894832312 523632706 672165271 640468127 873107187 718751112 929525021 856868912 992624994 402624034 465314485 283607866 345202162 20979582 72815280 97612164 377606330 686421758 939780173 752857570 899259518 313971516 431923609 743997293 964485081 326260402 333710021 661718095 959743992 122125566 410456702 278429486 993624871 753433878 947524307 735079851 818706817 880717162 926092042 644300639 782773192 557801095 963913783 607343995 795059176 992144741 996030563 556361861 837398497 421522582 746889881 662425361 806473931 363269229 960868083 331757786 584689115 737255979 879057481 36631735 518200387 723989838 946854887 795574392 926658890 976025270 977784413 931328482 976116239 478011010 533669055 214363242 520426193 327754699 441443811 540608693 735220615 709134840 832163694 732632816 859435572 327731442 641015939 897330432 980945054 681829593 854713395 740411834 986440073 628259539 914924215 598680456 652976667 930463887 969187231 793475304 845904196 997963190 998621082 594030832 778797475 764640201 797128437 806365664 871566672 12682093 408599562 367943964 733242934 226750022 836904734 940352040 942221658 991043654 996562810 156230867 699435588 983375487 999726615 339183255 962840752 398489434 476388835 246395745 949134312 649432164 922641435 379048496 573644037 304954282 967153403 592357328 803897757 980656035 984518386 772831795 969984415 541304281 838987705 372611746 890911045 908164592 929364138 830921736 897162023 906994416 922771475 602467615 971568042 813925839 837973378 914934346 986393071 950470074 983924128 65721158 110739052 914119074 953645821 561834639 948812007 446200049 785427807 987375872 991690657 87377776 807118694 272181069 276947350 940086771 999896505 838121423 872326946 107405617 997668777 650612656 976801642 399689120 580562662 168427459 717445431 932932112 971935556 365748698 850272028 557167329 859782370 436446692 516175952 613646080 942363038 667803917 700290277 23655477 287856110 95254449 630541014 89704881 750271194 661707738 870291192 381279628 697558868 656145530 972485209 621847127 996801035 473499408 710820406 236927624 298192102 416487730 879139802 146436670 501914049 198599893 321845653 20639143 648701684 612024774 806004393 516175636 756589508 110978033 391731801 864455136 869741384 957995980 986588972 369028905 971830626 896531310 958361277 564639481 997866053 532407135 765357187 93875448 459673482 276461228 632942474 548513660 641438199 497850632 744032738 362228380 462174258 864844634 972937706 569847680 939223619 92099092 438481900 883457339 936790200 106093588 967913694 835283113 949012894 414462692 826145363 868841204 986327671 483774254 932216200 50999252 448837301 741609285 829272529 584499153 623051292 413443618 607603791 311975193 809707901 94290290 590253877 562449656 913157509 426334873 622864323 630557935 948359966 168249778 550585799 317725865 386367697 853892803 913872491 751080983 862948523 501400675 536238172 577698394 972549074 678716238 883599557 655382811 997238770 70000753 646789543 419991798 975112102 745456395 866747286 854102022 952136223 589904395 696042668 872086054 880837912 39385804 869432243 223619976 696374923 297165665 867335543 369654901 675545966 826326158 849613441 467376497 516964539 531380025 650450380 680716671 687200438 939399368 941965908 931826723 961992823 270388597 420754874 590741319 594391899 772068745 974482404 606800526 623879459 152832525 394772596 106014526 661871448 162501220 744768588 870274297 948110403 800196523 863655310 690610935 847883856 113005951 329407247 911854042 981088928 73537068 610833978 211382052 792353710 315436381 640513748 197268534 805314828 542549429 611585829 655349821 966168022 170217103 384189001 858724687 942101573 139535668 500649745 883572420 968608990 223852215 634207528 450393653 933369433 954133018 974088634 151932131 522204434 991746655 996310830 817718006 914488748 750813831 825547505 67366013 833454123 891934392 978402955 954236728 959793875 253279895 987946970 662547938 819015438 147636346 582639379 156764376 864888945 775264310 974297665 893549361 919858028 158812061 999731314 819995668 987025736 835401283 962908856 792833249 814509984 469399306 709976171 44641023 116958451 279164990 380399671 969596260 983048731 500746443 566422048 637479275 775295272 222740000 977474058 602421240 883790687 210042404 221438703 239720018 364596032 23169835 154712283 805128162 898705536 90482155 959336920 623335241 877460949 646747521 988159588 674993075 816100531 581837401 589363332 661256831 744042309 462393337 995222699 936058191 952333406 291526773 696350084 533313374 765894518 877246707 938049375 609513883 908714310 542346080 580077877 789743101 919234065 352618990 972878035 978122526 993673446 954193543 976780052 40360356 698681488 51800323 832766716 303417823 600687621 30626502 497915437 976495480 992484966 810189754 914465614 420540975 776423235 95886095 519022424 81282185 319618580 163925680 247665846 975641441 983832888 947279674 980084281 725710585 990591357 479893658 771579418 777994796 921092568 521220262 666214228 435367489 494744498 560337334 914774137 192922051 382199635 752856723 854783833 495429113 924432872 660978227 920306578 110896157 296033004 210239129 908487460 116241946 937944637 55173532 864560001 731239066 946214262 781629507 811308594 683245955 984683603 279754638 918273893 957139987 981930541 584067618 871984994 348166201 481656140 37901858 946539251 908170191 993196622 737844026 754371786 803383652 854699792 652871214 992270756 335851357 993792249 72403110 694657296 888677039 994763175 951080837 993303372 966604932 976029021 349234959 871618416 687412542 900892910 941918760 963067213 231409762 441762514 280808788 461363175 516588326 677169653 506359584 608412263 332298835 673716745 327379896 550833454 313973259 744502384 203916423 504045171 565782990 960752011 67671407 766821402 386846266 664819556 717533582 829398861 402818228 505498810 353870502 836472201 818241175 959998789 502188031 513466208 179116969 362578009 662831115 870367812 724141925 954520618 279786347 702275275 106972178 880744632 757138219 794314676 768330043 823312170 401894138 911916851 394635586 952914010 395732208 708690425 649321824 905968076 910356453 957084450 352052172 646732496 218397264 475545841 293542709 526239127 209067627 934656442 765563185 793760065 691353448 875556149 410531251 548379634 299795454 488036732 513689365 725972584 450563088 616149289 980754497 989686910 311996298 350772208 83054080 926907410 633278731 767332993 167984426 242591735 304396250 331992039 854617836 914307543 896826919 997246877 821169727 894239361 135119747 154537440 308671193 619846495 316888248 956202136 281060948 338812947 911531727 933414708 284662333 647049168 696800532 907089651 860316995 922260979 730159657 908484929 88967214 470039329 711504624 936572377 855257873 957869838 39501033 234539741 276355906 519423799 58711784 464455761 882138149 939478321 599566614 728983894 529269871 783213465 95498268 830363109 158641934 264308892 73367848 288582854 883614707 890363984 482722833 989119639 643624167 962690826 905738079 939013569 380850004 803002688 172674395 328240668 470263870 819275568 935528069 994394283 635458919 731261650 573288979 925399143 439803503 934595254 561023514 923148881 926646255 980426586 681474742 762845958 829722619 929462809 749532638 891101904 938819296 988226032 367504672 428467779 318885616 833139109 280348040 327737992 301898291 880474418 20939346 94405946 609066438 613098191 826496806 828554467 673731738 924351004 855072009 883014820 575182405 846798798 708728424 969362733 588553755 803346393 264318300 810372182 738657970 873323257 509826596 981293241 727719467 987618891 191293775 535579582 14562172 601136075 234274908 643749989 248847701 693949323 822614040 911699902 702500114 928271311 494621720 748545549 780283296 864613993 496308982 511173252 925418947 984378412 786438297 854139808 362633154 639321035 702188001 741599076 760082540 815490737 142805438 284608820 361662587 922897342 435945685 853588209 961227993 987923335 831312742 990944753 933132792 955900503 189202235 561228928 252862654 795773858 761282324 847864899 764559728 852996092 25787798 121638997 807695508 820313315 448979125 624226689 299142572 524887857 280877151 329928604 177803087 929498669 510622325 791023454 640729393 666832976 642863491 718748082 736533098 911777498 731047653 997077761 164906984 608285880 12690524 218353030 184423848 329577102 762982299 893085736 473924802 993302329 714238292 949037061 729871455 819698163 398258856 756844104 477895396 560891812 197038826 991642542 650475107 688963636 231521020 333244375 461033571 784056862 104026428 892881933 143350892 618157792 680764447 808223200 443319278 918767239 242134999 804698781 412745477 948302672 102133371 833548457 937915487 944676097 651399181 954946647 152384846 439867965 753597529 855656345 110727735 448568088 976584020 979026418 887114663 909358645 563197214 935581445 849550435 866108234 787530192 882757108 301491949 708006190 22938637 361231651 333479063 562578660 504397638 650280540 502701561 709439524 969005666 997881808 254182066 415103738 551039373 944739438 267285890 861438696 271880238 272411710 499415363 551345047 902525674 941577521 434910101 597744294 625371919 900298631 937027652 966390004 662363721 873955724 302933055 318178204 14963456 597184373 227939528 770822727 379047256 854953920 117000983 663123966 896760924 916670091 508230358 803517768 54157365 850365074 212462242 836839042 26968076 482274515 13718383 781128923 96545173 948347807 255962810 463341527 965649111 967493072 328354152 640149406 82857981 827027842 627918355 952334016 552821466 839503645 265993257 552289772 278270953 668943089 609778566 695784170 186460137 653395193 158599801 343568961 176803781 379798658 567909862 989896284 184956304 282959779 630499371 733995737 996662973 998709570 299505296 437619502 22307166 98966309 343726956 794580187 786509529 975205989 338329818 915851302 146530814 150069955 775067839 828245000 490424409 569304674 381873146 973193197 365096117 439900579 305508884 733470829 626911191 654495527 973815310 996923820 503924837 905788224 201093388 253457697 741848941 897303095 165803049 929580518 43003135 253308459 972681413 985377619 500729896 984067941 275274916 795022578 475055684 547013236 911853763 952984114 163748972 748459092 347657695 948172403 559223246 915091707 585346897 792465676 603377371 766289133 452294222 909657227 604873961 714659335 832130074 886449286 695502246 871820071 631735266 995081807 612575063 941998725 557266967 745670596 23284280 62293030 576827368 806239701 221061343 651184104 566124241 990731275 354264271 729747018 972423532 979313227 819189800 864805673 168841569 513228758 797482610 972289275 822296652 966488873 161722738 331715867 363960899 809259125 769879695 975361903 746640422 754258049 568076069 703454297 380867163 867143498 871231022 969278344 171311902 989231852 187064401 693916182 737358533 959100372 680539702 724896568 274807731 728039357 925380821 990794286 750837945 956689147 383244299 735865550 735518272 773856269 575251939 639453458 607015926 736022101 683322747 766703297 42782830 242998032 387263079 640845578 147178605 829855477 563902523 791529251 383066565 480564982 301331559 400567815 519879446 552450723 476988590 587142727 56056512 315179184 826420615 987767961 937534903 994360029 162652143 172724592 530981506 824306434 261086872 584862716 66477222 934842317 720188607 931118581 676476071 705301747 690322610 806473813 28434253 914649446 836457687 857690552 613479562 720934334 165805144 749931340 621695873 848456932 829965824 887085731 159502662 613457807 35361832 545568797 73187532 348368970 280124521 532428948 507225791 688876604 61476799 613747755 421031067 632270775 424654217 436125863 203678576 836381393 906832690 981533002 429465176 653649024 229002956 335123940 878806438 911143069 820267114 874472308 205190518 812487283 757117175 778012118 289030968 674509417 425411808 772835496 518390486 998007948 520023539 686867662 383637550 730300464 143045432 973407787 806587705 898608640 907008981 971075034 260528612 578252993 268989969 838989777 836000511 862553294 296484492 771396072 759698191 905626028 283154823 735756603 419399090 854306965 507709991 854980709 249282786 778791229 66200062 625512928 452252882 978805061 809226052 843281505 814564359 877004933 963365543 972933660 175026622 415130703 198784102 340906269 85806743 378389047 576032583 983142761 193049752 893592022 800185665 873746154 621106711 674730738 986255725 989664345 699336332 743083704 624188890 977786885 668551899 841150244 754035847 755808752 584958942 641521371 106589196 259483671 702349542 925113593 771545380 819087954 156831154 333615132 575229278 669289237 290486835 675950203 571309783 943145344 12442879 383717773 871421155 960943090 405002427 654688078 249911407 706449752 907233826 943740106 872514250 952193387 924122759 969711832 687258529 968094192 688470275 807565305 486420258 807057457 727230611 835068859 639712083 837917066 817354360 991282380 764777082 817603050 599423946 626795609 902484972 948551678 305835865 584869955 868798820 896956117 19946469 620453549 317583953 953630675 965090772 972646267 914350538 970334264 788225438 822116384 305397548 534204331 792839799 984660946 270238755 723580955 114317981 238153565 839126993 922329703 203812793 842715582 373943634 758953927 741234962 898052976 264507896 472817972 668611122 825482668 821025579 833700977 357154239 659166638 553446829 831803775 887092986 996572802 706467802 743242352 64620330 415843718 890371392 944643961 344612834 625058010 223508655 694182161 355960397 904937746 998073374 998859412 927836591 955458814 331476932 964707666 214565530 799894755 618202018 877455838 682143693 703583481 466230244 610312811 54323622 933209083 60618031 284897270 799090895 876185205 837533100 848408527 389883654 880229148 997351784 998213442 495438996 873429439 445986127 979616479 105943927 486658969 941165625 943733088 557616264 877340013 431044083 652917849 767892103 955478630 113892916 319450610 179603985 918978178 466526308 478388429 418423020 903751360 971136982 978308260 347881308 620453328 377003641 538399429 516812322 686685938 90910569 610465947 461147412 597667195 344416688 544432007 181267049 438877321 296655143 815140215 230688246 890217492 167733754 911494916 723345672 749886342 916968846 993663653 517323192 938880474 512961375 851545865 629544952 927450067 376526431 547323570 830881165 933476399 392295684 647189910 75692113 518454709 783632805 872395487 496700705 612888815 852198398 950123123 636449414 969054261 821167912 825218681 861062673 941187269 748871255 784532310 248826169 531881116 263471522 362161681 820476588 938770670 148793492 168645123 654049795 803489936 772958597 821185180 576884093 925818160 512591617 977156431 592727424 614270954 211213792 731165111 481875194 518300193 886335759 891538226 498971794 765210451 81331767 407879470 227585840 783721691 870449545 996022885 362918755 464384090 742561959 810738598 933616686 978619343 964396512 972029955 504697940 645363425 537125040 540075917 529760739 950119417 714047997 853065566 394628816 732486768 755918730 829245429 478210576 588935359 697949944 883820904 718833180 795813117 785306574 834321967 412027257 659036303 585025876 587666804 385867341 393047565 964017976 972314436 68791229 833527262 326295570 672184236 148729547 941591304 752037150 781973222 275388430 510332465 939173231 961519742 682182959 885061447 676199743 751945649 550253234 680155787 254305982 797090579 153530059 532910570 496839142 971377115 851939798 871623966 90230791 313746854 455070125 616509565 234963263 960885331 539799378 782165404 102118972 145496647 12894410 812906081 495589307 678486500 190626576 947821605 114194442 641678509 569690250 637745426 33936562 930939795 443136801 548885817 986024068 986777885 768134562 992607543 504198768 734929792 542627497 943909355 28921999 514871804 724140675 824683015 77832233 770794731 801121895 950494722 754015703 767487642 772861175 893512661 419749437 916627308 876897292 898923776 472563413 958960451 245852230 657760137 237025365 970660656 106216172 330002003 840944304 991038794 288364641 642088960 244891642 430385718 874659565 966220850 658942494 910992086 362152273 456604565 22672310 212592819 519999127 545187862 478149895 852451379 722682075 856074972 14759409 142419405 667757042 868374071 861228904 973945038 947262486 983867560 291285308 827057610 97628114 593754982 446240954 972044619 196721807 999110222 255316392 726166810 987420946 998146478 242457370 871887233 124293901 408377974 590620326 697999240 962978458 981593981 793145087 865075358 499941699 578364023 30439336 565882276 127725062 267468479 879159925 928178619 362519485 982573783 252036283 909704358 961734417 973007295 286394178 587005975 297682416 721950626 634067204 675522832 279361104 720921400 317692578 577336040 610420558 713914103 231727318 287186314 549736661 978947908 754640600 826299101 665184611 704130269 739986609 926165383 232529794 317887740 328734351 948075860 689255310 863937730 879274814 999558040 444449106 527052644 716608080 727622302 240403157 369198564 96347804 842847402 97234038 683701178 899722236 989741243 104264029 624499060 157540916 901578394 78220439 681998759 446834801 745978880 322556746 633310915 687733817 914488504 808627022 949285063 249437698 332535082 55386189 787125654 84485969 337958712 480694035 482473541 246245435 996080364 845569364 878925193 671612773 931505048 764450493 855108439 714742370 802544391 954488819 958468566 947967355 979513514 269770795 766243695 469730206 836922100 887001376 941317449 437093950 746470178 94421106 567860122 359292365 835258821 741881046 932177146 618972760 882825919 833117520 917367203 589278231 976643870 282879620 653453380 102962916 325211440 229789250 900721108 325052403 660491881 687678923 957711019 567168629 823689220 987731767 990954222 273147461 498544288 219255852 881267250 688778780 932230942 590364166 757992548 168496378 353667042 505125575 884652023 63030449 788513621 234950573 299131813 844003122 883704892 712664682 978282608 495859772 532392899 796230334 842146024 766802457 969312406 363889421 424678482 469708489 776646564 892465274 955084791 288035848 972967720 526763438 712644458 480328282 531165242 178329991 464562020 679528520 869354141 480512213 978198195 78116690 697300941 29490041 434936481 450863989 486618278 750228763 806523092 154953934 676796918 834001388 859684802 801149311 882124358 606842987 848380551 400896778 407222447 445504458 457228382 975001137 990301830 366881554 782096528 560708846 869796496 986443382 987914642 333316037 673525472 948989828 994606571 601919441 990016717 124947581 982330712 627319780 959495004 767664833 967321711 423383762 726841887 615531585 730156632 874263141 984365771 738592406 824326762 646880084 927513507 98173827 608693379 708904782 746026944 649997018 677384918 570370629 935413039 618816370 784787824 102737053 755892727 307544460 891037675 620286169 790914165 321264405 383250749 295385974 746725532 952052357 989696318 598962386 676524609 14376637 928849746 200773856 438758374 897359499 905380533 991185844 996675796 891484371 910206568 939824674 956317243 62630557 969748511 801360062 827901688 216924990 851541270 101933436 923857657 528633004 560500891 913215929 924879415 771064907 927522134 967867650 989282226 626232018 663219340 610276716 861164572 519867300 992446874 174350487 399004893 183276815 578132287 420075076 826815371 901009947 951904790 207306910 387420235 991150426 997230497 77311178 846251644 975975253 989235927 47489189 560271072 400327383 460090396 597173257 730567115 544901669 911216405 156278133 709018653 987057378 999419070 478607480 715169271 548058645 678145450 89631105 247371450 405489162 972293806 986942967 988781080 717224340 985749006 601716269 758141208 983033448 989819409 497043053 742447515 480602640 621362580 971550144 976246923 278429163 627819745 480019808 676222324 715935528 811158166 420882192 853985629 895205327 952559334 235188483 763270453 670381781 834418611 480594098 840225536 203443169 253871884 194085549 997333581 475129641 617521526 320718242 588830036 791672598 953527587 276376870 298451053 757308544 792910989 276456958 463543029 557847666 921193422 832223616 973105087 260067888 909534490 460560908 536585173 825814861 880680064 656221225 820042040 602374400 716192162 625416349 733987612 43807824 656581588 182149146 514560039 447406124 631995010 186747700 672375451 143358026 179970210 164954380 726920356 521967037 794772210 956686248 965591733 326943346 676788897 830723054 890128550 455536553 608044733 132597610 434416088 638805128 916793865 443284441 558518912 571038963 749237377 554468791 626094093 452610902 519036836 814457224 972664015 534041983 993347347 652567819 797484018 94483553 692002454 962830362 986290889 81767021 173826415 540924312 958140761 222493792 890493836 216055101 779901475 547749530 877381074 417563729 626716137 72776903 611025850 721413443 815365522 297079408 997021080 371109436 487813234 929221236 978522939 177408408 644642616 567800488 607747632 612845259 746429418 374743990 402011932 938049212 942886602 162579023 954171149 323312078 561661113 237972923 563321774 14339713 753132792 331945061 741583194 685589113 874739549 378540828 554969762 680877916 979981585 788909981 878088191 585183566 775250930 913928873 955316936 313682609 586212487 300036474 478412703 508660309 942754754 719499433 860088314 166908155 933915891 173134480 206670796 490008143 920266721 100159579 694113830 910870892 915475491 223635461 796328100 716197246 825066858 519439774 608849524 930252546 985704698 976304651 990004704 317562546 938473046 118255905 840922957 786922427 898015158 934707823 988800976 231546534 233585222 547063657 710401821 840305258 921459143 157722407 344525822 242576190 409604320 669176689 830490623 904247812 972051283 314077559 570273352 686396738 885652319 77561965 229580630 806205569 842350965 681042777 984559540 264932621 634843666 363846148 434268163 124991422 832101275 775370227 901347818 513707295 791676937 827469931 916881351 824255865 967865116 95777285 663369401 179795657 943461137 19158695 723963527 442551380 669453344 203378137 428258522 891226023 927807595 950297546 955844641 314179506 635473750 677700190 983095110 31543714 292553601 194316454 606891502 569697508 790637431 585635184 750813991 449145918 521442472 440570461 619898024 99553109 690720340 876048512 891309695 302200083 381466663 195117599 354254646 201014662 770323618 456638702 610706391 249446186 561976959 14395094 485295968 770995335 848196353 716882142 984440547 364232315 989537018 922240167 926532606 854393919 872052473 721115914 733293202 441109131 590135111 940605748 957746946 370479418 515068673 667023690 922031652 194226170 324134018 556711627 924170133 646552247 775118214 475815694 734201210 289089366 550344911 849978642 860873609 174168787 333234327 351058656 928536719 726778898 833613080 324759092 910311609 625204407 988935287 232943942 618357883 635593265 706167569 860889284 885907921 848640349 872765655 308085642 468316406 67318382 799467973 357895123 857276826 895312753 933473129 478589406 554090023 702258843 766447646 46079609 692354858 389103630 738100311 663109566 819707623 926875924 971674277 950416986 984460978 991098049 994600604 691947901 786571051 535559192 809650670 57824671 864461559 558788272 958755798 901763234 961559107 415267810 925405504 753031919 782642202 901300445 982160433 225957103 606782275 117058499 376687852 656016658 660671107 657673314 780996372 173200633 500473177 999103501 999546429 586571189 808372425 603742429 954753864 278456903 638101684 361849202 584072778 186638813 245129577 749900766 816127791 289663489 724613343 835917177 885912459 682864012 916437976 806107076 890821589 947512130 980560209 412981682 542992365 621530274 967248957 597095654 698632585 245508134 348790602 690410303 842438624 939363778 963161964 490908510 704164113 686876906 982306853 639842535 879041605 948727201 997144811 61750950 758878797 60069581 73381898 936094134 983650237 819585186 835636129 468722172 859010827 790223809 964263627 706535461 969998945 148755428 661416010 348549756 666334300 916884271 973415420 307071861 952326199 220424482 970203092 518585250 955484389 862873680 904274898 352777213 746754445 323617687 840739125 509312610 729517283 698491666 934036798 302951923 545021781 739200489 762270138 406193699 473697146 289789821 413883814 594149248 705083797 269302441 937274371 399333923 744397176 73992792 178195346 613389743 899383635 411390069 946734037 985762329 992739878 702326263 702781666 518557087 593329324 108094997 491995732 982471260 995640299 741160779 744497317 186877874 834951481 472352081 922696700 619405813 755041404 643576979 809725944 159184536 242230279 112988958 970251094 253916691 675014894 602306161 736070487 397241312 640742142 535721837 740418549 304744683 612008637 935123049 971832529 489933319 619187556 57456699 80841040 420735678 806080977 550434204 802393544 319301091 598609496 575845151 698868839 668862104 926783685 423671578 679529777 617989538 682626023 804588171 990979969 335057319 388367047 257131836 561082887 744863260 981170831 227026072 629825125 235156401 286244196 990348442 998825284 777643098 813049495 217278915 836807208 927824775 964803674 548897614 719966832 410028290 797321465 894238490 964371729 292635164 326991574 252387524 336203126 497827028 636861159 361194992 477198906 301714264 948552679 680637087 791511341 528516749 968373772 728507810 748237237 523915031 726950380 823157810 929549198 278320869 907056973 465103151 528396283 826350236 888133896 490735001 645092466 251107913 614528033 303999059 758976160 281671862 710063115 469299149 839752410 651014024 728732923 409425311 816706799 139790602 603887812 960695749 966034904 246806910 431070164 748932839 954253501 638483559 943219206 452358466 521949789 858715456 974325194 631206868 885792718 86587652 542000864 901004310 950417628 768206810 941158731 687631784 917031652 275481523 627390772 928311741 959765697 248941006 470950014 502106294 718236916 383440247 978799014 566242056 787520690 623128156 992854118 630622708 950402591 742244311 876639580 733138979 973142939 93766983 298222212 865519497 981498617 828298201 847792713 857554811 895901384 359212740 967685832 573757420 612598615 98602418 844995360 418142200 422072207 713201668 964877001 325478706 718458382 274179713 409500948 695621444 735669083 276078824 854848052 281300433 331431240 262543215 931710136 380214505 979778809 509314175 526505812 807279011 947833563 879896459 968127162 377497021 905562074 941167097 985619299 144034437 150451859 98207022 315390731 203341863 559782209 385471440 462852799 410601502 788240944 36042839 309514700 231855185 665987513 839004112 942595837 508250801 798859661 404324665 447553359 493053437 648061701 443375554 760482536 117867091 909601632 36932582 376581215 223705678 491101864 730701484 896989650 934713650 971907022 74383276 742476249 501477395 869211223 739340056 870064537 889611988 925339492 456588303 960500853 897961841 933445425 829871485 982134603 378697382 485814861 57149496 268721804 33879357 872591499 507018472 799044875 120265178 337362732 636678574 887534045 435891264 704674645 413525637 834237913 896043560 987997433 139724890 714271139 139410649 567904762 921810194 935716096 830883980 838418337 309487474 584555895 221413374 653235657 870650434 962490612 634785938 962188872 639426893 856008959 933305005 993688740 653114264 677953425 607163261 992194543 123890263 151341536 475517651 679152773 469620241 976086606 695427802 977412418 872194449 910379945 157911682 329468557 370860866 843969647 626553674 912394849 224193548 258556769 309932445 820335177 706758739 801406445 888265303 990852279 153376589 756050235 965604765 992902079 809404338 889917747 925370048 943691169 98014696 636958556 692018750 917478304 358116240 934161269 760320749 988149311 631324505 636109038 728458966 941351718 464098150 831770182 583358007 636184078 445149615 625252775 839369841 861955949 680039191 983483129 188181996 667103739 665448221 786577442 767798004 859548255 358713354 790496761 977729943 977913098 809589328 826793453 588748237 678942890 238374163 887795285 957724948 982716042 61124600 630519338 467588219 524122594 85825382 907303208 235139273 402193632 430212899 993681892 964850181 978020025 874906268 880903951 957247403 982147380 494949965 917453122 287775146 563912909 15829687 563351329 831055612 854653400 177859059 523635869 659271134 716360175 350477617 526684866 707704521 850102153 940127431 979661886 850587155 927670731 383051844 628596232 577809691 695607562 441983666 490041425 928019818 949053827 870583975 966375474 889147226 942202115 858275675 977094768 152616047 503148816 801185026 860595346 719203690 855976694 938397304 947565421 213203102 828833861 541326405 852919133 144113793 383167522 488747964 947130828 164224586 832061070 556599838 735116670 401617245 654451065 772386833 840310391 855268414 908352374 438847140 693697615 946931697 959329521 414620819 831932127 900654500 933335271 277487105 512688153 804877868 900657921 665709918 692070513 677905369 826748129 986471240 993521991 250611405 498108855 724982092 917745631 175245645 652374304 346118173 792441641 186604440 591992016 363450563 531300537 380888733 983380806 970211224 992759635 246400206 283925152 638599427 678088537 184053326 196278883 475830769 988377188 339296124 383675974 841940911 956880946 488360366 818569463 128325869 844161057 806982802 907912514 307610857 729238589 799689902 839206982 602056895 963995121 366671105 525148729 24881302 408916946 964487163 982543970 836978081 973158511 230247977 579906116 571528830 678591788 653475280 716038526 246972529 731047248 258268321 688307086 67186541 237873168 480558651 988601736 234133966 326689247 851468430 941501911 595707847 625429314 565221776 641125742 648732835 809830299 26776677 855707408 618475793 812155858 697591877 837308527 924026083 956091470 158364495 948729464 559991908 929665361 745019617 869247823 850488854 957925823 517099350 942698276 135251866 801355718 507718654 725179907 497218610 914348968 70565949 694370634 678237778 807086220 410630497 423773594 546116663 848990492 658533865 836675348 523339995 616538792 726044568 751219122 581067349 847044103 604700258 751197405 509630928 764908020 636181971 843786707 624535135 838512826 145469651 523173250 706281127 986457483 968403531 982685668 348798119 667205574 898424288 955236909 455222490 700514218 788678361 826936713 70870729 856386356 530449178 905093630 186954749 206317977 291289110 443794062 379195971 941600932 216148961 884769822 214525246 823307828 229762286 847867996 756669294 877053534 760611474 822478246 539069127 567701455 816718090 903160172 839202370 992921144 843182748 973190270 231359363 789728879 352234949 651935357 866191036 888174592 284803639 812700947 378414570 829089928 889225756 893586692 443164849 753589717 892363316 936594220 138742588 416819302 853202892 940944158 86993666 680153017 126887838 775208138 786133050 976507502 48513994 261948345 495361416 697530296 894888946 947690867 531766969 822716013 618276224 997912234 462804571 884588493 304737373 503352958 694354754 888784292 792587764 952901817 902444913 904495661 968565258 976430098 355307489 761919552 826307098 855787992 473245243 476126224 877223635 983378712 788484983 868478327 450643206 998544417 529512457 964388720 569477989 895448183 875156211 965219053 771460906 955995827 918247071 924502631 33382021 593517453 579679852 745863996 833908809 929350799 965086427 979414832 991558384 994808900 731983960 763067982 722191449 754356789 840915769 980189772 50879773 604819462 342307943 746856987 780364525 864754131 850294044 975638570 962920239 975671407 899672263 962716793 953686925 965442127 379711083 439727229 902649215 979522870 96022238 893251834 231761892 749913677 306972756 557877977 823324610 936211710 530371241 953237273 398863262 813874864 864506258 904077345 678221763 805394581 917434028 981855359 339988367 815163400 645278015 678835066 510965472 758307679 713163959 721890275 72698664 528941137 268577607 736304121 450729247 487677452 319444842 621529256 878975296 913884656 849309307 904673278 221966969 830908222 448343344 534178658 290260471 481739824 153277684 510861951 532372104 894168223 911280113 914566755 103717564 369683511 311062111 688067804 316867056 379901696 830308349 966510560 432978425 920564887 694348463 921779178 478549553 548271965 149162108 294935077 869264599 966027826 644408568 831625028 708790810 966770438 557389866 594042453 588366993 830393100 998641115 999016747 486803709 726416726 946709584 983742252 821609002 930193732 101496356 462969889 200687271 205514915 662165266 769541001 256564436 645848863 986321423 987579226 775880162 843862928 144047673 856266708 846244991 885542235 173063651 947338161 369970178 852491677 786839463 798764325 442114088 836547056 760024555 864624527 864923075 945838263 341451248 470292146 274209755 406220143 100004196 669009640 505191685 515713689 198274407 287129523 793461211 907362579 753038609 827836365 91069041 259451300 841722304 895941667 466216822 639852948 572573637 595847632 133657722 258471410 406931931 503449103 56986627 204966254 457368560 502272657 688363293 921075784 92233572 497123304 664594026 834949952 993912670 996297476 16595218 411332997 639453361 663429854 505699814 992969237 705290834 986317414 750167127 831286473 613643133 704802456 670754027 745230576 683361307 920007065 388976715 888686754 180506032 823036276 746417658 947453406 177788692 447234722 313629940 352549146 160459216 921045690 220280194 559964911 190956334 884619043 909918122 940673251 367830989 582983198 53863516 103243712 417375546 672027043 690962234 948658422 234384273 723478737 540914085 871629126 286811175 890917704 740167535 740837357 46597799 409771186 997823629 999951865 194421709 501662034 536324273 757747671 93916285 130550599 333953953 661070734 657128716 823903777 541293459 711622386 323319161 532969779 924444180 926980661 255380798 982483586 472644030 494146210 998623240 999874369 934038267 979129206 425229806 954746690 853522358 877226639 891219531 967092512 704503912 756550875 667029904 932161002 731026924 978816635 458543986 606267699 533964224 975322452