979 806158240 820782736 919337985 931257438 528969478 852929071 28493641 498933323 290998249 300635093 263948348 349227581 472636284 801964241 223989614 280657201 296626760 681491856 336443830 539817832 770084967 892117248 664116766 758224352 735695740 761891633 67142388 559530151 403322037 992182222 499647533 623810380 484485109 812624088 86354983 95155102 789370717 823448655 481779973 605098522 386635178 386693708 662620083 797287380 139809134 672861074 188336859 719640290 872471009 998996264 652238435 866177120 105448674 112388354 144531676 942907250 986559391 989828524 141563836 883413646 198068084 985312923 629624919 699332552 88689778 455516545 990989723 999105451 913221820 998687323 899245133 942568328 806390506 897194711 709690969 924050783 803692561 920869487 732507881 920395642 127357410 447356319 936805749 989489538 102626974 206364319 471052421 971224241 374394318 463197888 914034383 925909982 965336663 992452082 75383245 131635525 27360851 155901276 872864969 888163212 608179461 908963360 547965716 756804969 225249620 605194325 531969643 960278746 416144406 820886417 372696152 916506321 628133921 807165113 770158797 962153728 926537364 986647595 278340988 886597686 964158735 983046270 817427038 933373844 761751293 988969175 568053023 608988840 83214388 961767378 812677896 882881134 949774708 991469588 390275404 489637655 702512038 788360746 671195420 847323235 151758077 608550152 732926244 952147321 513819042 711686745 348092295 993994282 87942787 271088974 531674373 924068421 753917599 984444139 571753616 767874726 944128944 987612791 949579019 973458022 70059075 253514982 406641641 717808890 612668292 816982736 326694099 527767218 214541190 936807356 967266176 974232579 742690308 896030585 619315437 672689615 787098185 797570846 284600918 317561792 874702135 955676184 724138493 847973503 668551694 851712235 770226418 974894561 428161393 474786852 971975138 985143850 474880273 873514160 376812850 633417220 198429260 935388182 532723513 877555064 234441549 599856199 587741078 594686863 916817829 989323016 36295472 399882897 581322311 994968078 729819027 793341920 310118223 929550040 581178931 770975427 804495631 910019385 351117843 838225632 849897861 986474139 608931357 671573725 207134647 461654996 797398993 888520499 125151935 242321739 61329760 101745223 972897155 973973546 944646805 984775286 976066243 996487985 26340684 797013901 299654903 811696333 101600802 105636210 593850819 842483423 949222657 949990431 177927096 343185848 85189774 104150123 493428702 603552016 216486783 647494437 597132880 935281873 196735797 635054142 316395814 759075790 28481819 332208072 520033306 886559875 778381278 821784859 214298070 256444094 739380562 780351322 847234427 892104636 282868786 544009340 821257942 907723491 855327394 994975532 460451039 473782465 113575654 389412628 699504123 732370858 826500729 959317355 901626823 933004601 713122856 816448704 953354131 962310183 526574172 581452173 30968839 261083260 580662658 978157090 178677667 990996661 162367657 648879301 722947615 824120190 750204753 905956944 650053000 935734581 267412503 319339904 121415875 890707799 221548392 468134765 386917005 921486903 440754942 538498076 515599075 768347994 496615545 593277043 291047705 732331000 299337640 461198339 473553868 678022505 900579090 998451019 176646227 475082679 974722108 997952904 941683677 968037342 775458868 860735440 916097437 946697893 21153027 193728288 145408997 292070295 596979995 866490703 743062372 831697317 986671062 989740479 438058069 986860282 202343824 554472463 622297586 813517464 507361561 571519047 134354762 396967442 309211125 726006918 395874875 618077588 841036678 952748627 507914872 833903495 335809332 967919813 10098450 666965399 351880638 906872768 692801194 928364485 624947845 784744481 150004141 236827903 519003734 958626936 434069952 458810847 901977096 920940797 851845549 912253439 458984067 769102797 639724977 946090355 746054136 846915504 659406539 958092628 516326675 682885363 731848399 799066182 927123183 994192388 597552333 623825869 930346141 970850860 729920478 964818487 626775442 667987869 549244361 684994867 859495706 905604175 195768509 245995014 744169876 961866592 638604116 926549722 84164027 379765896 20712194 130429160 276738749 951889652 355719413 513985111 212879152 479194326 539408315 949694680 202229214 687598427 568344864 892259324 713502942 913816612 58997126 503606139 454956102 878534340 297459839 775499464 887726694 927494392 957521504 959928649 652592123 729118709 733383142 798866736 320969543 659880247 733091722 862828187 165616732 572412596 212516386 430826286 171837762 487780529 255219887 270697764 785560871 974436081 769668207 796262978 880328160 937665521 146825535 269794762 105475449 251880388 104471077 719091332 856864155 898218684 421206792 613758090 341455435 713771938 259775758 407066534 778424229 935859136 642400124 900465359 109593411 236141738 447423473 961431780 876891718 946112689 165912826 452147114 552161411 959075772 642492492 940976484 147461334 705403275 669925670 945987948 899524482 933813896 415303410 763424071 880903597 956779791 820477602 897777262 462574620 586029682 358883578 553519198 421524873 640010142 34267276 548561955 705584557 913713072 589966820 678210248 93497969 513615797 824897895 935336926 945728230 971986929 380058590 927608333 939349207 944511666 518096052 825697507 516054414 804438138 693058286 810974160 305333767 964171525 592182004 612698899 656515597 666769094 716356566 979914304 62714439 694569342 245399492 590299569 414602629 550196961 77603748 585228776 208292246 615256090 12879844 508453880 335580756 552731407 917595102 943118148 899592565 968767339 17315491 571066157 130311605 912635092 957259771 996609513 985002212 992306717 799552878 836248576 502884123 600773210 72390095 834825886 179971331 948165385 433941546 673288761 652101005 717603694 494921072 698004836 956025103 966307343 703429759 797442328 307075078 674892647 998212355 998468706 287649971 765775722 484377190 496987284 919766763 986063219 983855475 994938901 369475393 791282125 567028820 873427770 695501136 774802555 116252279 806657190 475257515 978374430 947633141 973141997 555148018 749822278 827955574 915696778 820866277 843298321 151342889 365240896 69117444 816435652 37898996 927677160 228093241 285091229 66438253 593310591 382165768 684205936 385842673 507775780 440471200 854300084 700645794 888124818 149436123 310629747 503378433 567759312 285679071 964667602 152171700 712222159 274130669 756333380 242843580 728209007 304531354 898452026 768089451 815443685 256945508 332869152 814225535 956689518 158124626 809825852 319281531 887985751 502557112 575132843 260093765 763536133 385240530 952593556 823734525 866880893 857184124 864423969 265241083 509702768 855822039 873444593 916782331 980648005 100584436 211078069 86675790 964508302 928865672 961003058 522182647 585788220 60090697 907779102 182655651 701822026 299246270 330368130 928286634 935259864 67653879 714631978 892598400 915104655 260086958 869380483 525823696 950226851 573736634 801651816 51805158 101758941 662231188 765503306 518050966 651757404 688064508 841181479 258074341 900900841 684816977 687382370 120884008 910260449 388862703 666239123 856049494 960382826 899488531 953081505 374788416 404764555 770169180 807139174 961867255 994485073 512058837 911775122 985181686 989353907 190840644 523330868 51648431 434575679 786682578 923503129 595599224 801641946 75365045 165083392 176906612 851118073 642734036 670366466 397932431 724705175 232005078 362619329 52450753 409187292 819494090 902367393 614722424 890751367 892658352 977458831 745198791 913327843 401734398 485960689 973862584 987016812 534017378 779965350 616565739 948224164 495916243 948602387 904583911 975341586 268450919 472298762 202456760 472878948 876622529 977010692 997690845 998806125 458286273 560508424 449900564 600529406 571382161 969664448 87107836 865848077 749085088 898962886 620790727 865563663 496216571 907875673 937815444 957688134 387758436 424787893 25713148 519339045 565974052 582225350 468370278 559698851 742856191 839820564 244311111 469678354 475171252 566886476 511581846 595935278 520905075 777240439 60054128 695801858 748685567 839824836 396967518 742842841 612093119 983013384 608336847 784571289 244415592 513854145 39674806 315301009 260253066 474481167 915523961 968637793 113303277 857129404 167239693 577224638 490054892 824911436 33995805 255518194 743654488 808414230 875310977 965650969 466182188 977438927 384903554 912921012 88460981 921908310 233957488 474208048 265648824 502268622 458450844 594623516 122366714 155646619 318239819 773290200 11529144 560456342 326390444 645357798 315343925 417562056 106146249 514306303 195780011 769721606 371452160 660572886 205901326 725851856 184532242 233454005 953392326 970769357 587827919 887946920 136076979 826167321 98532023 350645845 627003741 856473553 811844261 839552135 925049109 949359077 584786441 814139605 97315877 231770159 202800619 974081267 494304129 866918076 973661533 989766733 992546562 993704242 98062951 629961804 589839422 860434105 646282253 738876567 111278315 181572141 133472241 622220733 71041267 243086391 708367144 898894888 685830137 799745153 230016340 405344434 371045260 739140158 158942224 311660393 94478505 605391860 786858637 815612286 133661292 291990592 910479750 966871517 799842057 909954580 477663944 911054441 355836885 975673627 377236034 537443537 873395304 886440059 277252107 966099437 861144206 981406890 273318499 638274431 546885109 598766031 952257494 989085179 68909635 372538963 783936828 856887104 494716631 740678500 597469649 680561124 716019236 884137006 219478856 643392198 294125923 353890016 150965564 931450150 43827122 111861202 49072143 242437379 566055977 897318654 367594681 934674986 821256933 968417650 126931812 160620818 479931431 771551833 48066779 929799243 880912477 887311387 689137693 782448370 567942686 974920674 274360424 916457519 436119750 581719811 668359127 743211320 975320430 987205616 741156271 897353385 334154142 759803864 887302696 899755575 290789452 516923875 359272001 468186952 815931706 982161954 933943074 972887175 453909067 697041758 922309538 925714273 381865263 433759729 999110206 999348283 506389065 726720904 633715742 668111936 153794870 815667373 150111545 816651550 11833202 157069387 846163801 864716866 75635979 921410882 72520156 854161526 764324819 827631743 106243736 733883459 901118585 919197875 934339411 995756782 875799361 968740698 148007898 431666480 658985903 683391706 555658528 647290257 744780033 850533810 786414417 789864681 504062230 711871183 90815086 748607663 641556136 951259291 245174738 894703908 705825843 718234957 314452099 526448035 521956184 884714470 909861790 933796495 811796137 986638132 266693377 614300370 97920971 878910846 919568756 960343533 852111927 880197395 377538481 762467912 112535881 117872962 301697569 716709396 425270100 582352277 287677503 884647582 579356917 611397692 41563715 746776778 403830391 994981025 125702903 603970139 835732093 841816417 539722759 690386214 738726955 917430608 795840576 890478777 951914420 981761514 200120885 725388730 653743820 765182999 549937263 857579644 292301931 397146601 130806611 651009362 580798388 733311566 785131923 789329476 839483460 944199111 229038576 689531055 329843040 380996148 446033071 471556149 714480102 952714913 609135964 615067523 119647027 482204371 27547848 108416141 347025184 664689970 391505576 826403151 380686724 395084146 666654023 973625545 841919820 879092319 924598291 953963085 198398778 334417442 608313669 746340997 742453722 831475580 724277299 751551443 84339318 879123567 771740278 848997467 784052985 850936717 402483489 991475586 925888486 929508447 488752956 759917623 601153883 979984354 682431273 701991755 435538454 923594478 610308819 926217660 98398846 939214140 713694177 818688728 330710616 635719309 326090381 550294851 975615230 985015819 474742985 568900310 57305577 468356171 835366092 854754921 556973379 766193786 458162778 605411098 631318341 669518741 147315165 903736619 744227043 803990261 151659646 547358541 76535586 226346723 690588857 977447387 348676781 459987056 244300421 875059849 183731492 481298748 340740400 629824387 30024016 293878113 59734434 467614989 383437154 430670763 245030759 559217543 761080154 900219269 717297338 846580594 43550799 753465729 691163655 846958151 983651330 991952744 400549735 994323992 911439663 935160354 127747359 978672434 230018995 947546603 996560324 997026626 285947483 738882525 443017574 580262935 614887694 999047996 482995610 494501386 586430620 725569311 766901115 914018020 218394102 819545146 636044225 667508844 181050905 308175788 299694155 392219754 103552968 644308122 469702386 920833268 503265600 840042596 870152006 878157890 741459497 897432154 300683007 905521917 522990716 562024380 671720996 685649917 39981705 164468618 50715894 873328865 764393306 817298052 428767619 650394920 855884559 951198611 607400709 617919051 607932952 977087363 58205915 420267094 263099536 824821079 453386252 544969272 454369061 949580455 579228644 868625242 953990395 981089646 640800912 686774826 158333088 877103626 57323148 751588968 640155981 712760880 491725462 555550996 842584759 996922228 422362602 991662062 19344104 791861061 581900820 638478937 288837202 864651004 903561230 931001848 456250487 601713320 383159722 418826144 321345381 387960374 52443098 784127535 470174964 688651881 36841027 217293928 119070578 844474042 264368934 807544109 93483964 993007843 686649562 842457049 939451999 979173819 292827901 916218382 489061803 674987040 800712362 954953405 298508355 889968548 192827597 260908678 438258746 569577691 10129270 309092504 396218994 590580595 610957149 660637918 727500256 730613920 377291928 649952438 962498696 989645701 914689516 924565650 431941629 548491844 637040587 864563299 191112120 353496541 593385090 743970664 825020954 956449491 433160288 476962356 40439324 230118027 720678321 889884413 284386475 766925117 649485653 985535035 483255070 760841003 342613549 740525311 411796123 909931910 314573277 907043929 281599778 697368043 465156169 629407515 56628409 326698884 540978634 553222554 295927121 862973030 758346069 789201262 972965757 974602171 26203511 160659422 125766955 290325312 611441114 667732807 314482443 985356884 745729923 951772963 386035776 413960904 569788636 694111358 971223870 971330131 940571847 987089588 330142349 529016994 968350619 978497529 889620095 914965459 854246127 995610704 719944675 830010884 872278858 908887670 681903743 766639402 801566968 837776004 437656304 935403348 343100455 478736748 292852694 998492457 725179590 995618892 413905132 957305770 130120832 422408945 362928511 897762059 326234796 507116342 572408518 662487072 749593462 981279989 649525280 914345968 332683855 822388571 908509288 925500416 175502320 610277541 316317482 863477997 364297510 807064252 981396988 999209666 719833399 806863409 26669039 793067209 511193933 604139353 392492308 491454367 950965628 970275601 598489714 684138338 807057074 877700657 524474692 640093983 80849563 282411905 611077614 749822990 47101905 989821539 520583847 681573827 387752446 966881033 391734396 928176560 657652589 950167159 460446171 736616701 56177823 313927046 199873332 960070860 893880561 985572664 801382248 917149812 877820044 956504742 460714080 618646524 633492523 837079579 612897089 900916675 335941214 873323393 663066153 931568276 530220556 713601264 15079373 858661786 347098867 954208609 277242354 375011773 821070647 834455193 267151338 829767129 875541290 875663985 234005386 581682597 385248693 748111653 562449196 880669756 284036363 290662800 743397784 781113188 33028706 637231261 369460050 740972549 159941610 843911495 335057657 992143115 723321777 912680535 844021145 983881032 573388221 636388249 524342906 938070801 345991267 403934912 110355549 692033578 238268209 979155575 162149320 638531033 883484732 924394807 972831605 986744041 241929584 535839094 458723452 689696543 691919439 741280036 730774687 743003297 876869893 977546501 26676161 67022552 522761170 675137022 937835312 941096575 79399767 997071255 803137336 934928809 985316730 997793530 709522911 795001301 135192757 783341643 510108117 524101022 780734932 828566784 419939205 469250616 901308298 979153777 957612297 991575897 649701345 981550660 758118701 781387821 479651994 680942246 601191325 856598680 227907622 927785229 273748421 431933618 378418148 589465027 617207777 842926185 732876466 870383243 244238259 255762927 207537048 733251974 728095411 832701132 494831768 668135357 403668435 703761098 980676358 995641114 916853106 947030920 280355756 609371951 256265742 411447647 109827287 382974531 878360203 887946487 714395379 912640844 159035161 377278389 525236939 730726846 233840047 280030538 184721492 465220864 92676225 171500238 961456079 979711217 572676656 864033336 277169048 313308218 536496672 587502358 184410772 428128133 223191867 317492838 97153790 746945657 587271335 990983723 501522365 933676471 470031619 485529161 294481353 442296849 761510181 818463139 606159402 917381540 468937136 886282617 971575263 989790038 772032729 789894822 554679631 904013352 235400695 538846015 756536713 977583175 579533368 809712287 115284680 447632359 700327364 778632878 351540857 767976350 558337427 679352011 415633069 503022150 897249950 930634079 58577943 651830366 958318047 999978008 505117305 821915143 382238460 852971933 763137198 921795925 305991869 447495258 130050983 190501439 987246415 991362756 561569811 877133456 211483056 603963265 770808037 884662364 344816166 495847758 549603591 558114476 918235660 971786682 63939924 275763774 773871481 925419347 664917989 698313780 601629175 685293102 943755054 963376280 929436739 976067909 396787223 653947307 936370998 985385174 810514905 892132903 568353313 866148451 31726664 874709786 742936022 747180941 421051052 760993589 805035055 987457545 141832530 584712170 609962883 936515032 874044528 976288572 476144845 864976953 174688855 334889601 20069712 826234267 18313460 637660427 585918671 800869411 872614459 884335716 117368096 394336569 552957042 566702527 80673361 882716681 863075356 922429818 434762812 466137690 434635245 551125959 358595653 666233028 93201010 282073579 365651655 453121559 86515285 431485024 178977755 857407905 48515870 716991275 663574985 863268762 176243975 753034209 787118401 865155225 313544209 495441798 927577501 930617356 743827022 803775912 741427507 958538169 682988371 803967921 918100083 960861510 880607425 880891540 175741943 448500514 212297609 846937848 511964839 824127029 669939049 741662310 141201032 420844058 912448595 981192031 625330185 906204877 884633984 916503059 240928989 408224113 479264781 961320596 48419271 713394276 815965421 894184470 495405543 771496604 483606309 738677654 973469428 992001226 311317835 800473180 614389659 972185129 139011660 458963544 744441370 907982917 738346574 914022878 566650813 624561056 971381610 973601824 217848243 355789315 578929967 990280115 791554669 850928855 464793540 665741380 681758153 898074000 453949331 478983511 510929712 980153917 800480748 801542020 816773261 999715918 32572566 440860288 450107362 511744981 729105243 750243240 236634323 845250961 785365515 980141048 332117637 363104566 703118673 909623380 217027058 870999022 795332271 895439481 67000249 926865564 337424698 405477398 116926374 167067918 741799289 776276363 242832517 368959115 565180072 805172672 693637985 715110447 621172776 902446023 498713181 752735660 676107246 815674752 200665339 221215796 249765891 561518213 774828950 916359285 779779476 822960445 663866196 718047797 476918000 913128299 562564338 984356097 631284170 797120906 333101258 646920109 157910478 939513493 443403097 536601073 680135798 685199350 350573596 370275812 772206111 936884250 287147113 655289862 334529650 408848456 904351272 930829399 861892781 998551998 467696961 582682137 62682577 745698777 668260264 883767282 853905676 904806255 557401097 761730689 75084519 641231419 524924572 622697361 519822044 880004035 749085824 806098088 368647415 897407629 958661466 969093490 375958534 878167705 373120153 862920537 568850603 751736927 449317065 496668125 749232447 856629268 440273458 837550480 654474499 866255325 346076283 807348711 231492261 338324367 250056186 617092351 988810744 997628010 980178310 995489954 871997912 996643428 162678505 797997097 150706781 665480776 12186429 41910629 267320967 356666044 497012617 604694076 30253002 998233815 668604257 851093730 863801669 884768638 632450301 905256254 756968131 788259930 424216113 628314949 984611354 987219307 347053103 555639729 150278866 383601803 97911219 141194632 707934675 734447415 584313266 789734918 886832215 993095233 79824340 701265110 82916535 874325417 37415220 963341396 898199796 940849574 281144889 542013117 127798609 300660714 257486637 579219481 584040480 750557742 305103765 737053799 688883326 718928442 919577105 963698246 30980525 773238842 560559602 698948090 830189012 963113906 349314025 495714023 141271210 978681319 200049620 354001395 945434408 960749559 441171742 504002933 374160341 552636881 372892758 982292008 671389537 883279284 12137446 188700590 647027169 915506356 799309357 997812285 520651956 706350210 722806443 918268886 529974057 671422548 265253146 432426734 924636909 966444385 302717655 558866543 94454890 789459207 953118758 980692654 169712385 503254262 131424911 632029808 543911599 840501232 460216458 967034603 197071327 430526155 433409013 606353009 21201110 570373587 548128705 713909581 457188950 851294214 92331048 752984215 700666511 850640173 47809957 401221862 940784681 955941260 846133232 994490596 880902494 974816793 790537870 987270666 486516920 761151755 391517852 571789314 29586348 366894446 394286898 657041277 772736655 911772833 441847793 969587207 599234189 752032791 127271974 783248797 458190454 961073151 844916643 924410761 456154811 570536662 48319652 827025365 282614653 392333441 983381573 984528299 140885363 316768978 793734085 830638513 442529777 534376625 666958975 773625555 742357735 886097015 783786175 967055753 536440868 848665488 717415357 922780785 159008212 359302031 669174454 727372243 650878394 872548492 60541990 535492558 905646777 917039088 732924242 844533824 325915212 473064348 288835523 955089973 670137792 941731904 123945632 717635708 752126612 776864497 317203619 424660347 656006514 815641278 739845550 825485261 827284171 903393281 872212281 952592545 344781449 563745222 68578589 597659642 311663289 415001058 976876174 994640809 628133491 908099341 977161518 987669201 94326848 760748593 898007058 924596500 388741343 800782899 114514976 555490596 561657337 591238927 867283828 914377441 529591715 807935155 634509354 675543181 571956049 642383153 784678420 851084509 598694755 850625182 909345682 959059626 240993106 989225493 932082226 958917079 873043594 921103612 894914635 899343151 494013826 775085033 805938858 887568806 804637607 998158036 357830362 559073848 746319614 823448744 559253572 813498138 472196162 950900192 296780094 850417819 894131863 963789709 222429217 368847678 713860815 751183362 260145798 795260858 381879055 735429681 763464147 963127229 379312807 450724202 131938463 371157121 798756443 805858305 954729292 990795022 30996541 525017325 895134545 948621500 367164337 473630033 358702985 619426951 148350816 861436774 293330539 385700295 354228060 833277947 247435174 459509317 330871527 550766082 133531121 695349334 29036028 291436781 952270101 976844363 682610687 878195822 538847605 739142107 811538856 964764211 511002998 882306157 223388759 752648363 597532326 833306493 540823709 543353845 356273603 416737815 332072519 423736615 482425204 960820065 246626401 266810439 616263014 680387793 193955073 751149300 196877299 478102807 699513024 932300426 189776593 218741654 437905606 717509803 856004059 917443176 873157916 995866920 820040664 921542598 258581529 296751591 520010342 529844619 937054306 947264438 746414898 907361754 216228217 823219043 453169456 830585900 79739754 86798828 686205144 917551011 65159835 152765735 815798331 876325565 448649067 580908753 440380684 670373041 174893658 246566575 995731991 998316398 602781858 625545102 918533582 930473474 646319062 936856924 952129258 987753567 350400396 915737797 537892537 620251745 181960044 891889537 515747213 841052877 52057756 370809859 424707996 615732686 996768370 996997473 909309597 934929373 421895457 545509989 382343028 790296242 86999767 543037328 515716094 681343717 215808814 885200499 606112951 968616508 973145862 987037577 250827135 816805607 818510235 953108756 960211824 963485120 854181662 907203013 619511979 709955138 403546561 742943915 331314695 389116437 984900958 990864226 970220496 998922729 908823478 913930804 46065782 146920291 553344211 605958994 875204116 994032031 87811621 199297459 369548047 723372781 594165148 984553426 246390688 284896167 958585749 963987601 578678949 930616696 742536001 896595349 615603466 777596806 254388167 417774424 550373336 920119822 534409757 581927162 36015375 849261378 516468549 911737830 30200363 815227072 117202415 356964836 272719144 866165442 760065701 984870202 833579882 842943117 155948316 207660950 631036389 948288801 757036823 908601378 628053784 893142275 641905965 801674001 377093256 476094480 374807933 865800308 368493401 463229765 446779596 945649790 613629396 724505625 748006394 818668237 511917388 897043526 839955392 875788736 400350548 674436343 527109398 799580408 453957030 758488706 170789700 997372040 680802650 733416547 437832072 663646389 819879486 832234389 421764436 779594145 962710452 982193168 739761649 879177339 924337861 982387080 299860865 354654643 142928505 394159521 718397414 996980584 560744135 856170433 340180642 942165217 172710124 198204336 139139677 411100593 779974614 908205439 99321494 181568965 992812458 994009231 846293045 874966430 959455411 959954534 444968826 794877916 479885204 607802412 214371926 827654606 161806524 183737849 203192152 634382711 936200721 940185193 103325391 642773786 528137980 982180916 697979804 736514475 887824339 962467527 611259338 818655837 588660751 686100779 548546670 827114219 562088090 924588497 741959945 829633898 559776749 850729946 188704128 265522232 76687223 978642458 980570453 999945564 81817637 829648334 75638520 300562983 132801997 768111303 719447570 982336592 438831384 795708291 401605749 678625448 680276950 750381837 155194880 469063308 592896645 824302509 397880475 827471740 581530365 986314698 435990373 973955271 349782629 440709455 508410782 937472312 764593157 880866194 693575766 755488008 258310882 915955624 297483139 474577910 204729923 538388867 857112207 923124562 164343981 540343838 512686559 540534972 645554100 732453911 107954613 337028512 628566029 816146574 909383006 915799069 83530718 942442875 487201960 668856622 876354815 989476567 444765971 966108394 580004804 663319345 593699598 780510765 370683289 655917444 565517361 778708194 488528432 963571745 857317505 987658098 53203018 723848302 441494431 528174435 957652749 977822089 357160440 910782059 988548747 994958776 926481318 936719149 732520659 792833856 266106613 483623261 616285133 627649468 345524676 611673125 391345560 425222907 846563457 937229102 413803424 860182530 479247350 806570749 484229493 878663115 452220793 709978934 171238312 342319548 173120120 209139672 460411472 875656543 798597469 905716920 904668430 907778689 286617430 757485997 647977972 980856381 17497701 899285984 359867350 361597093 898979079 943116507 537457140 823284569 584499277 815704970 960287388 990357654 862254323 969134620 925839652 931420063 927199739 944636990 822367652 959647127 661665092 667322176 952151813 954049479 889793612 899925778 376606200 617238341 660078047 872254844 208506525 966343552 790652824 878881364 755264074 869480823 104699162 941202966 56235756 870687870 871847752 912242976 340954838 616849345 458382779 848239414 691926159 787111439 983498135 984071610 142950754 533820834 462390672 524321274 96207201 853924440 573044172 656087491 463667198 937401405 216346795 620681501 999233587 999286796 596367365 691384143 425939532 798467037 475636231 740733234 573899958 606099443 754851931 818213141 754694168 769533038 517971344 660295751 723660641 947391472 862216307 878009502 893768485 984792009 809603997 921875590 810082399 898723471 390386698 801277954 321065009 469407762 103460024 905668777 954751268 984033655 946556666 957731767 811162543 887911321 819065409 974108199 89388721 469835963 147227922 640046305 676786055 783988213 359651801 849901114 473675953 969404892 341380699 406223054 878234781 920877379 474947572 588900468 577096119 711343829 321526580 469104834 447442378 966899243 444512814 858064894 494038495 858175590 362398323 403522378 779433340 834606568 208043314 362676821 973634252 983044296 746163134 911606427 636349588 718361238 525826749 911217935 586483034 689964819 331866848 822284599 470145902 592731631 33148948 664610079 647855737 797782261 536654462 580816776 941551985 964522238 634410531 789234950 833129661 849035837 758463187 978618220 295414064 624408335 359055585 850874388 40601490 938567836 653426926 702434470 694692534 841921667 412825362 825504232 188206487 921744494 934086960 947636423 697987506 816315634 231754352 926576225 286805583 483632532 352536560 410367775 553656262 659987039 91855309 746345644 265105626 845245942 269695325 635222030 402238643 917371716 25162041 538898232 828423610 860264086 482928097 736371879 728865799 796819516 69751544 851261876 85499216 102210061 225387638 664101933 143728069 861388515 81188052 463088616 239726665 499322632 361852059 935017763 169317746 428811476 916761906 947442789 668993630 871063793 301879459 946377374 82612836 864172599 565804176 694828799 415034874 434031877 51922769 873933627 633062190 762152446 701034612 940125974 289565014 768247398 140469997 622262063 191493967 944132198 918611164 983064545 680296518 782600030 295515497 687420197 859125968 940933274 71118563 174706646 401936273 703936658 798194862 997914725 794767063 908941542 296803789 381737095 113182989 437109347 632723915 837885659 34089027 339681391 376994426 490459871 156208841 219934320 747908355 754812329 446742803 789214364 580266097 703168747 789935302 878509420 728224069 916807280 91042934 443629705 23022105 226239431 311677632 612237737 673538163 894885845 252532864 260947210 169116936 610349445 806548176 937830003 957523941 975404748 774984616 952653388 261134140 982143791 989599591 993891652 923411204 964870359 753625337 940259739 757848970 828960547 951233337 986798721 363211893 815346403 491105951 505606318 144917895 494747680 283168581 885425143 555521477 690180891 193171064 267022725 653586589 957147848 441810643 953299519 943317555 967417627 752323267 901646372 422749926 939771734 627198035 657003256 116282912 867475341 881278529 999404224 196475361 968476696 412892137 936828778 881092673 891004885 477279672 721809501 570086294 831716506 518441945 824759940 58537195 912147659 497556664 925044394 36806295 722144938 551774502 989999775 537179612 777053322 872344019 890869654 835904179 905848941 940586187 961638439 914633025 951905421 36279486 827793135 354037797 512380381 199673674 432684164 809978770 900057611 369735454 819203920 320989083 773057970 331507770 392778159 735842071 792694490 743420422 933232826 364258276 954108963 485379658 640680790 697483544 769419735 336329359 610524879 714523203 909293894 354832550 837226694 690581064 893208919 964265057 996175601 247265702 586586903 172185269 328414621 271407254 302228696 189124494 610464889 472166324 873362016 608976594 874820531 850688184 960460044 385401982 917091775 897322365 899688047 805925689 884774275 860672685 890086125 251229948 491496291 967383739 997109663 811641814 929419071 686715551 747996488 216282645 424723940 456881569 568651057 233854188 965162165 301482648 304414573 379012562 894326644 476648712 806399587 131479909 461599045 837660097 918083941 732804163 808940621 981974985 994497361 399572005 400139801 916204335 957803431 604987190 795687281 274615274 687227445 730003272 997918847 53670239 314421881 410383588 555115828 120617066 365279412 864297028 973216223 30530999 233937148 932282085 932445569 644046318 660652677 182081386 965163900 584766159 900207149 705711195 899792735 780773096 863635442 801770827 937315326 650980781 656170399 206583761 225159181 811779409 842147001 104669591 610522346 371881903 632758502 855894842 996765123 124594757 865975799 106186449 392747930 409012036 510838324 316988108 742489755 313260602 730928866 208860390 342023693 259303443 497662676 300119410 976552633 764163135 850943738 384658094 909080382 686085563 828562167 463914787 936766877 793569574 941011537 441645033 671983696 489712011 740583589 570909357 930981220 760786532 888207647 682215290 814764761 572313306 895587083 931023495 965007609 135368049 876158503 759123839 842954907 832541055 897188776 834878349 897015875 706307675 818394919 716468294 722561281 23652571 382245137 494261609 810850349 531148579 935960758 965096157 968616913 76469177 84001061 570514979 587414521 411564652 476907750 711671860 758353230 439742104 467060628 775873910 804975198 704516644 810587234 216100637 693102162 189176411 951517313 301384272 411162043 469556347 511920882 929543041 987812733 856146835 976836586 883469284 899209425 113898488 260383879 920489870 937446322 695408934 696954587 163985410 296701673 101657522 561618272 300178992 532353844 10888724 102586881 622708645 889715705 145359611 255428796 368255409 857919661 873837668 926713575 861934650 993513986 505377111 763595430 880767162 967670943 771916079 953210254 996403075 997340908 50939729 258462449 924366049 997868713 871555459 914565440 768875065 790284996 135740153 717111390 223513845 559955700 157337882 708958833 109206786 713118658 494545278 497604695 70887328 914857555 692240239 767705981 542900020 829759754 456336513 736535980 673262349 880066139 551773781 740756313 439129030 744339548 664286975 758007773 774680365 877092162 934096452 995363755 54767053 94995494 486071275 715309136 737064882 815291197 16002417 474889760 298924626 654924299 471492759 787875127 888825550 954229651 11758212 936171852 771767794 837246409 226463992 278700388 371593562 900357853 356196952 541781293 216963435 793697005 490287360 841376613 443783815 550002052 92354071 784966180 630905673 776147460 322230064 649533201 863772598 975026413 271402404 385425133 831797148 976767597 375486559 903920907 368257790 886066562 587731574 739903274 935758295 955726961 508614850 700231046 720899038 951520144 907079547 947910786 875201024 886587218 773522248 838507860 398683247 708412832 95905119 878760524 644492645 853711463 292770557 814001890 753065790 782111005 671744893 856744665 451118082 726963210 334061739 637844429 281854082 334374461 936620824 993278107 527334100 671963113 60311627 470662311 357805349 517951463 477243528 507925771 749251831 890309020 205801002 624745263 196134931 804161806 816615809 891447326 161053287 490929039 251661724 992771037 980188127 993075675 732204241 918837681 121351259 587599504 73087013 220392042 511421339 530164907 773132101 946966330 673796893 709223909 639773184 795234630 813196075 815476492 539725477 907535858 952703195 977071941 524616321 771483097 865972192 942471992 529681936 653125363 204703051 233442323 961599229 994737675 978051381 985387054 521933030 536252295 980901001 981685129 153555879 805521141 348260329 501934610 529068870 930949785 922231309 976419392 198195492 652200125 470282934 853295525 40782533 863110908 980247870 986740231 455753790 810231644 635227299 865650593 588703871 736160007 376196657 805796713 873103249 961003556 918506062 990406134 353595099 862055374 308475184 770678810 935645682 951181172 868289659 898613831 777332905 848118214 197702243 282418507 100523558 515523066 995449472 998858189 510146980 843080682 416369263 874825850 476766046 815218701 635408683 905180903 374828265 430832551 695381978 909649285 290558341 884322692 667091651 746345330 974892540 995231690 782241586 957540307 991195888 996427342 690099599 780348216 922086043 945367266 743048695 985625253 462407929 618116372 928060202 971939029 652263061 801684938 181119277 208514929 432700675 791808412 750116454 859902497 691467829 761263384 964394650 971945189 528313302 881301493 795810128 796752458 163742435 911604627 641092947 646388157 948864166 956676848 607743133 788279400 625134965 835310267 890247994 979952034 476552107 779391801 876484470 901742493 525804963 693333505 121407355 670737505 59807173 320076245 715328673 751667902 620599194 945644209 91744651 750583463 743717584 887577517 60688080 723751680 278008097 617181843 948296694 963484041 890298516 960784506 430111733 851573906 372858509 502930043 417074853 548817991 873562261 967540597 294905474 457430388 542602854 726217096 814200784 920998267 591849401 935007745 634130670 746416464 280902114 494879906 23168830 771571502 653637798 780689719 182250889 413401788 973864801 982782932 335397796 822456628 29114238 727014488 559513522 599500853 479096382 899516701 539118881 621097146 370758797 429914452 756712669 964355366 874166532 930332678 344848132 461876412 563854098 844101296 791833212 818540157 320815969 895358138 354677901 925434742 507732084 989978089 848904819 898081418 317178887 928476722 379038029 947215521 741189349 787725756 422104118 928069051 485010047 660933494 57741481 144072427 275899424 938364926 880664915 983335338 267173094 269930981 187175402 997141976 145324539 594426168 276361741 353939913 980267909 995676916 885185537 987993019 675577056 758099072 279264983 946507798 348003776 411295169 339864429 642902141 322416057 575634584 585459225 613569617 307824928 882981761 707567479 915335642 748277048 766744361 227965451 584525719 246074067 441973017 41568270 410763042 495337800 911189097 948250433 973889675 651226910 864057901 732837346 927714709 435015217 663680965 53270618 660858019 541290856 821878393 570512764 732081918 460198159 485370290 779446282 869713883 152220449 475231980 186798237 624641736 927110031 986430263 963282156 982103016 160596437 293495951 387712639 466270115 472944592 940811618 634108073 680664821 334216477 420904774 839198631 878592821 94880464 551974674 901454410 986053658 59537655 135929347 129261608 954505201 549257558 678269542 359249168 499567078 846500806 945971177 839356789 871839302 636824734 989624090 844848452 932497347 864036208 905314632 175064877 575403757 182240928 406823830 617985512 828905206 888679649 904791869 289836426 474444466 257344841 904795715 193494194 868453293 187827776 673474782 150093047 158196858 118423064 899384071 111023382 697503434 437351436 723118844 935868404 944013308 778369139 984214896 666921890 948305448 959320480 979729071 208942885 768652575 585182044 905075889 122533958 723711095 633036525 974147298 783118356 935219955 270360537 622919638 873843504 966218274 921537715 924161489 244091263 643376626 225470886 780005686 558527838 602570436 621034967 743941241 213038747 766068874 309836180 730393763 766008397 951303105 372548851 436114203 150017699 627598176