940 568289424 872657941 429285322 651306023 784208089 804355625 560578178 627833703 812713976 929099618 971113260 984838003 470355938 883154912 586183637 699454694 146564283 391862660 392616346 705096717 183511123 952391454 151079595 948527351 251849535 828257340 825049768 897421327 197419573 440816652 60229175 616656021 406282643 733372441 204133792 880766041 893543157 923566503 770559237 781476239 184764505 496688416 218064665 967457662 820572960 894665953 239935605 589011571 612872919 916874936 790212718 899669605 322893025 607310458 790581858 905822861 565202269 597173032 835043912 891496591 285712736 438715601 316752900 773401226 713097048 815447734 657764889 840119686 875558740 878402566 268303540 453532056 127322072 485835150 926490393 935438619 173349194 854832035 660427593 727359588 527714828 687563461 155261134 933688125 969248007 972637614 214509388 757363730 781406168 964574158 197673103 393459864 439039540 560606931 600116737 986643340 718852672 725592479 235382985 358882256 263199602 860240546 83404782 889752577 355452515 597206106 603255898 943980165 908129540 972697264 371976888 815890045 938594388 945653739 761019938 836818661 166765940 544951349 473242103 616583751 162723996 485446004 350115482 777689790 140956982 733812341 826808082 889778942 945838506 999723254 526523409 884022076 828345843 947824043 760291579 873350313 438220317 988792372 291332439 431666846 932884136 957951270 234745468 695284344 724673563 780867677 843041393 949030864 437284236 885406400 202974288 846004491 139670739 395373906 247675407 968976780 794282128 958953977 321606993 427902207 749838604 843217360 331697562 394870329 402500153 680655127 424529214 787084247 40824861 446285069 361969568 448208934 438589449 559100816 746880103 988421759 615209803 894702696 462535542 759834577 87454646 747312818 850635767 937053130 809543129 887285360 266156988 726264610 742198795 744158106 693166231 733140449 37079538 406985397 199810483 762894623 154736267 339719132 712793363 865771868 648967376 937485582 943114223 998305591 733449632 778683227 582036073 837536449 595769589 874266224 452559459 999623246 412849792 471595060 76368264 262927378 626623798 863398835 256458464 705798617 156177880 384808837 814870434 894918497 133078751 440514811 256561597 456259594 521521715 664349287 934347125 974323974 61837498 634406217 640073938 696763102 80711393 473485192 372713038 453942044 81647251 135529550 721553087 988022015 818227157 898884721 715078031 966216618 565749710 949852189 273015077 326803722 773726593 813385694 945123428 999307534 92833887 514034624 660235740 939178150 670193142 977862487 981172557 993310085 15164142 566696702 133655441 979963611 44320259 908093799 603371099 675415991 945301528 957393724 579862103 866092800 281457564 438923388 662236329 710303136 691111766 855416256 526495249 776291825 422333034 521589126 45614873 815091650 72371661 476086722 740114110 817522531 209315371 911999519 653282560 890931901 125932888 217081586 377361139 481086502 345537514 626791176 799433640 812871041 40266845 993732153 503839623 961860134 687737091 800278118 187767289 601703294 218664817 727455796 819214265 924826893 841723214 969927632 149890302 521859637 409288425 575832928 132444502 217463443 857451744 944574342 334140932 899727235 11112755 952846982 417631396 875657351 627765737 714899003 174845746 893446778 988544292 989345658 293804927 601836351 550857595 593191169 532236643 663428255 304002884 983041402 551849680 615317127 361096054 967800818 959304376 981485363 666110328 843484038 292023521 763868070 289574846 329912416 102146030 564820221 486392325 641599637 611685321 810729360 572200572 709241458 425781619 813639230 638399451 982315393 990963643 991801746 387858488 892305371 55235694 696567014 639655325 651604216 818307181 959566829 774260028 912721845 842801717 967358788 656836808 923320246 80803943 672055828 282214112 312870943 557704158 655086217 692698958 889215174 984359914 984581839 420140014 914675091 172572058 257521407 551149060 933522904 690882575 923249908 532677480 555805889 665472113 885565498 75672554 802142964 193266536 824334902 452739218 696776786 625014435 927279116 549310173 835868182 508960103 539425172 301529083 950775740 456478744 767804843 363864344 600701998 777596509 780955358 130070295 576316157 463173454 846398536 206357986 669585997 231254316 803194817 151496878 651946259 628718312 970225300 756385608 977963487 599760667 914218087 793342585 976286602 353526758 846199413 821413191 823761101 203497236 593355607 362324244 821959611 707624624 828440542 960892935 961719213 223898647 290351798 337970596 791174048 297707742 899473401 621419501 907775762 441473827 469088966 511063972 825496962 470451900 517805455 343012611 913994847 415252947 428744039 827697995 943451549 836742051 864557305 997141977 998889669 349303949 918822191 682048313 783238641 205346103 287987375 982120179 994348341 824886633 834843611 644516821 709094770 583180020 717967977 665496676 991171927 813759916 852637342 844059562 860077570 451645981 742701243 743355182 936871448 810444779 940529118 35902717 512600371 560781648 641050106 605215936 819721667 970443325 982166264 67593892 566249071 648617299 755008768 822895095 850506172 30367599 86679316 779596317 828072136 132860073 285226560 296449144 534846646 289676376 560423911 340210014 457761468 437371374 840532271 37977207 744205758 302062964 901660711 780802332 893794311 170890600 958411798 994240099 997146997 215395399 418379483 992498590 995352989 323447154 633995245 86002056 781430709 762979785 886649285 240085193 264503543 554998101 651195144 999491076 999730610 51627075 72948113 159536522 652021262 210598400 244805114 768777060 772737430 75549791 620369564 502281919 529516786 210266388 374421345 463388059 518000900 493634610 660145677 624648177 777371812 299377473 513234969 229635912 323440100 80211990 353038672 741947386 793546027 362214004 496881250 520153915 817073279 779202937 921531561 923081809 968708344 519070847 760081236 261551487 366586359 453414583 880368495 279924568 623485765 591809487 654674366 380974460 787003469 175165565 277664507 689201082 829962391 284788825 582435735 98554692 600708810 905510571 944866064 172318955 486644594 188969507 731327238 521774137 663052481 653380557 869984326 939039185 995856365 483963606 619093120 294774809 614615701 920408426 986664003 360248954 495497007 575228463 740706192 54986586 366308449 777039754 891254459 303489344 533395583 578913628 904449597 66575403 206211546 859546640 891452506 985590225 997431853 766831803 956265876 639792309 728330173 609549999 667871269 719241642 830463688 445003727 793342374 887319986 960844241 456219744 982103176 467776812 617905785 897789676 964854785 934154686 956794392 240745608 592308738 913600669 978191477 898234200 983650620 162332545 989684584 120650469 675071906 216847015 241610177 664255651 725609646 280813974 396427347 578436430 646165171 98850387 946503204 190526637 453935333 518237279 911668604 350547407 924830987 10254703 956310317 730752615 987099653 957820083 967944812 241187698 332582953 524654425 748375875 384400924 524158239 618039456 877200639 495347249 734237028 566169782 751650467 800711475 970982545 91749139 975211172 233476380 479006846 595851084 760120205 736157633 896063213 46437421 119240747 913264689 931571639 983804577 997891152 273500418 554353105 145101411 674751891 589947760 914674057 921974439 965652524 672914787 915038687 453084831 913955540 528967104 959610835 164141469 538549832 630829751 959217120 888638060 934737648 875468117 919679761 602121229 621454226 787834456 879246735 371739892 433252583 193169188 197425287 59977695 295492821 401142962 432819571 658823202 686096254 669431446 720090801 789108616 919049227 398322780 672254360 380159078 903630852 115174305 734496564 383071293 949935597 625516560 793446061 412152569 556606116 582437361 917120234 334145454 836574022 895133550 951197703 666915549 768183018 360161221 472241104 438341372 458170354 396263763 935195495 227626795 580296706 82795954 140400462 588254477 772266920 317557760 375552849 546789998 857457265 594341134 920364317 618861237 942479647 523465434 838406530 535797048 897893956 63337176 933883405 53679181 599217682 897307232 970209615 113170816 636195659 189214688 522769385 679050870 730822564 896780538 900736944 140574998 649508269 155704538 792283464 741338580 849604892 474114812 879255852 662098952 856735079 198213721 600260688 219982263 265351403 406367570 841919788 644969400 796248384 457661166 588246148 197364640 354851557 524507022 707006546 142371503 919232791 767637141 978580862 490001375 612161683 399503826 448611265 937506480 937517281 595736152 962265242 441208860 454220341 763864888 936203365 338457380 995468846 80706593 671337628 417088292 929341110 706356367 814021650 962426546 994351093 117384784 589936233 230132365 561653518 91912267 375505329 749715341 780908539 496225088 512291049 14423516 685031122 762674750 941436703 331781117 341164999 708725337 869424370 380002910 854154459 935908167 982594619 181403489 660245679 179007573 698493049 264378522 453133719 151219659 411239212 664536206 896587994 828723496 882591268 198121879 930719103 330398065 794316840 978146140 986652654 820387033 828158311 50351906 482528934 206215255 311939275 924860982 934752646 953185868 981988839 340474551 428584311 42262548 107805521 632599278 892489399 867477337 936921434 493282718 623422583 810195923 811992448 861957569 990482259 380796658 420446857 553856715 657866747 386313744 767084081 123707349 611454645 850230264 912274290 751947580 849397265 571914866 659048486 305720369 786376826 688734510 924477633 953379544 958675108 210372341 247580004 621100868 777569806 19483660 916337815 156898923 421329241 166809671 294998073 951928581 968020043 205085327 385196258 874891486 942372887 423424066 746219504 125456731 864266484 71149381 350573871 531314066 968780651 859246622 999702953 798146365 911570512 928095969 932307884 146670906 435152100 805314601 987496795 179778803 497700384 914993165 998183555 948182497 978339763 468709838 663393931 821649445 842560245 496757723 625436674 912436188 939276333 502072305 643603419 569954064 862438331 823594683 828329067 893911281 975097605 945340648 948551663 122531682 432603318 770541488 788597271 482933656 498983120 289639206 985672229 296794450 863017799 241828070 623022483 994115015 999137196 508893418 827176742 777682681 948756201 922338791 955849644 991864555 996121557 32277760 361047740 826346277 914527806 150985550 746442041 87474279 959499288 893387499 933435223 707934650 932568272 815216231 881875062 155252785 212680976 622078296 892156921 46768007 708917907 240391229 583665727 26838014 903592463 745040970 867659080 797354554 964264156 17015417 886284542 939594260 990439997 594470618 687176856 906478728 931344970 957079131 981804482 174197413 746766791 817976365 958198593 15173566 250037826 796921731 996427288 256134978 359883057 200775410 892840128 510176683 732640045 874686581 911873699 250548803 991096015 989226875 999150794 37977688 534548366 441085048 900767799 731506781 986096565 920434176 977417562 386157513 390700557 497860621 644741650 105944226 710985428 590116709 847772365 610730530 850515757 85416196 554807388 995361485 998970013 833764434 927545731 274669659 882191691 348812294 845334327 45550309 524522039 808136898 948216986 498644975 899115444 750234659 824602435 875589249 941250626 953583976 962333560 537573613 962643367 588353216 765205062 275131631 438164331 147997185 509365742 652066009 915053446 939690945 957004743 236167099 715056795 610527746 982967478 184265507 279146044 463966124 661417179 198316312 482682277 770410429 915661425 590838816 775961699 907353263 958713801 155863127 192204989 154648813 379590908 648963728 865100193 882405664 892278306 102946827 671169663 261515399 386993256 651562931 926569846 113875063 935614423 449067658 854858228 390254160 524196088 487898496 582302800 810047737 959699203 489834888 672402765 842842718 892916951 335403295 998658869 646709448 696367199 49695893 409648424 57230917 147063226 826897150 879494997 654781874 668037698 410131927 985171905 422158317 948204850 401806210 478584244 942467986 996455231 555786108 615357633 80632965 924243450 699181637 999289161 682769516 835281914 222452358 232346390 659057450 767275447 377561604 499947391 454428996 632174876 222234928 864502312 575710893 820682472 170891307 633184991 522242741 997129267 174055458 542214511 185334718 695108052 388207091 547078568 613139794 752586435 786932400 965004155 644617736 652299738 687011210 868607643 393931988 436049916 93180196 479353841 477898100 548748758 75971174 896914589 812669790 876941953 859729115 971826776 529831416 726494794 888302390 914847122 881199422 959179710 84482467 763528656 368566171 952174745 437267582 593241670 382552458 812689822 538115025 658150766 882317321 914161228 280373425 634985857 251734381 499278898 950371342 962800886 847203287 955106594 262709465 530286802 742216489 842981748 370249185 514903753 44333378 124746564 422037543 790151655 226016114 825421622 981084585 998315129 443651372 732634516 606934510 708331382 396371554 991350028 585697152 968189047 707046356 793847721 338094020 723259476 122593621 855829228 526314612 885318583 81902607 351534861 644963839 873407755 753656143 891797504 620020833 940713238 411774993 955134940 764286644 931298755 618341593 832925734 324414787 755411090 500008863 933967147 276020961 381057530 822581616 956959182 396569139 937348588 448790604 929881401 329776222 542697724 56559690 321217088 377756065 629587919 11616659 470895388 754844162 992983110 279417261 708468796 302193629 996081970 392618496 490804483 772056019 981000690 780031096 971158816 271866477 765326151 188737998 471092094 433347799 519087476 692757258 913260470 178935693 692756259 418781212 478049855 255459435 604825269 149615176 739637827 319961110 412509500 508266285 516987640 930098081 938952445 214069937 463929141 391987480 951085666 25849308 308311122 758665968 785500125 534905836 960293746 869490815 895989963 721161838 946341606 112635055 981330245 619088192 862304634 230016655 937714291 178063828 302966276 689936806 847477672 869170866 966114156 872940893 932204605 918111144 926602646 582772920 925401477 776694903 821332708 792442822 878323282 423058633 558046353 239840729 469157365 751201668 840086341 798442535 803639561 427477392 538826544 795588900 903939992 375128369 701387466 94434913 842773032 101210896 984713569 752050951 774365064 620299594 943079637 414657942 555621063 25784220 636924157 981694751 997652563 105827408 685201545 436036197 896420466 631065810 827203932 483330108 909561300 889938170 916124394 427143365 515842175 520929013 937107071 384062849 917854187 35038201 225662114 923447759 948027075 480243653 956720685 948481997 995142218 335042293 963412038 119771413 419422457 85553170 937485086 416957763 788511132 739299165 857935792 75428615 683016033 354451729 403663560 759206543 972119890 715521079 756404194 262277026 309846921 494953980 579629113 59263203 309852825 30772620 105351897 730626225 776477621 174986796 530148414 988547314 991672715 59216622 877226130 812764431 839491378 595094206 675876781 735326850 885647075 886834899 986241258 245869544 791719286 979569058 990105989 319471503 645269733 949300415 984991162 480326741 523754676 697596213 909821289 793830547 868127395 758682377 987358797 343060726 786025895 192763397 508981438 492790877 822128967 99385423 370623697 983854782 999651705 44719806 724999495 45480527 289037334 564813991 891470575 156453611 410861562 95791377 421393267 558769464 631313728 123853299 568098346 208312150 547335676 544679710 717429853 602133041 754844508 157948666 998934869 999263319 999448076 503644908 690360280 108923566 358824107 496281066 655910264 212794556 503707963 965420664 998498268 289674969 951476464 153732298 493930389 430186141 696786364 400314148 914052690 522468843 886573597 738455878 936370880 402394173 578509621 632757285 847881221 130380271 966130285 674799325 718908760 400369198 823984066 624174335 826947433 215838143 487802936 136330674 603909219 776705067 783199862 238356952 322595881 334557807 520986212 176532865 654545921 626780634 953405541 86378367 675596128 692314171 841048969 110730474 932826507 187302412 477106838 556830159 606761400 46005721 130189329 860260692 958774022 729080494 916019791 328525105 815040757 725557768 977285003 765366087 950832624 694858582 711024109 264107956 506491119 126428184 158826521 128648843 889948608 713845148 868188834 679989007 741225004 154809217 529182109 279566293 531421505 698469625 942311606 842329436 993842436 750215546 921456605 913564975 961669693 447385326 496821292 353610049 600179456 912935592 922614046 650091459 738079646 957121478 988079700 812238918 834415382 332213132 638802391 943077370 958432939 546701864 846718911 16294087 413177645 823399104 974391424 717721354 990005922 839264610 990946857 73332232 629531094 947333876 954376885 257578402 933819770 391741061 531772306 925406876 932566786 90542290 294449869 339647737 886359123 481477319 663038077 180939122 746100626 157704492 594693786 75951532 109502063 113012595 567436590 261365758 489899712 254353232 551022955 544057993 881933430 351307673 933431683 86575660 335395674 770219031 854762350 183890668 948766160 489234006 935191445 759510064 832332374 497768269 961985211 481270964 897963961 909799222 959681815 653814023 918035050 574942914 627462931 644279903 802652765 218503425 840913628 157703131 276902557 840418771 957971205 840354857 924122044 830464600 963033595 796445581 963731291 295088502 750197541 604767570 972703197 900001811 924570498 857852810 920109996 189209669 599514347 139306358 286220527 851279982 977329266 397332162 869259182 541874618 612996575 860964811 877013310 563496802 662721330 136846436 308789869 288148574 901118141 202601419 653135395 309583527 647998791 600129449 823980551 262917861 706636186 184993152 793351667 664893695 668150945 755761951 843314906 566294072 653319313 328128039 737478470 980293863 997113431 552908548 593950295 399679770 894924474 706558210 728955593 642306280 942356201 545853556 946567507 975418872 990583262 522268858 671802563 767013639 999056122 390350514 658836688 599635079 640004115 873622456 962371803 81624829 521102249 940175831 967572941 256280672 690652495 600385598 831623371 13562419 871891718 406825712 596801403 111018899 328550443 224685329 834061875 796544537 914360832 452143502 526692256 79423941 726768977 30334872 228093141 934918210 962390575 403528304 761100560 298763355 330984815 767992686 961941371 300053581 766438263 822021191 906993898 156605753 479465368 997100542 997214518 593041696 765261701 897385816 921555037 359551256 829834636 167372063 747590599 815324093 937574250 683775648 754328698 238976202 891169217 925435514 963151528 453854048 495888358 520928983 913839944 64830139 565690095 661245157 663235915 545062665 856189970 143697404 388515350 171501624 772870295 145421977 955171448 250016047 261017289 447177408 704208367 359634816 825561577 855098460 921236595 949048763 963941196 623584184 663173284 278968843 964091525 521132640 789781182 129319274 328015905 552682520 762541126 627263114 825558099 28681406 396741890 539411554 612584828 557363314 588763947 857757902 934222073 111415438 714061265 839694328 976608589 513886154 714532399 889377630 981324634 951844463 999405356 806613764 999227062 43500078 475933451 172485249 697036921 363375077 890088978 537625828 713303074 472253189 851515216 670542728 941716285 510206600 939837581 154012754 673479376 458229314 516647585 62131961 741095475 657645243 775228740 891061002 926458235 398090621 827184477 528518305 953723214 171221552 512962981 623124317 784734879 572069847 736023748 844428718 952029374 796801153 814930649 289568549 610767070 647768071 989864017 945270927 996325924 294687499 900166667 27833323 929401700 834544265 895476661 408955095 811757364 57391331 183404424 101558594 925299950 717890425 744558106 305623283 599054226 811271331 882892658 469864871 846282106 289160254 908250885 655275457 694020822 30601390 637586396 857985202 934531500 562366139 951222241 334838494 453886488 671055490 936594660 898609528 978240511 415905970 508916393 629358620 959494829 758796284 798771101 789029916 887277784 456041886 941034978 570039357 637185428 102253949 902107389 449762786 723747344 628570054 696362911 745477280 868965060 245760244 330220747 785607614 930081460 42171861 166765605 646964181 772858785 827335853 864575908 769264903 827174000 192449161 810626951 57947980 698942820 360813669 813195319 622103107 847044934 406759963 459170214 165372622 471760999 86120394 830989745 630556503 668981968 537273944 697579858 102015975 610480030 887458014 950850050 660430282 894398305 436020094 855323531 821091397 862807123 188235767 773541579 294689063 562938942 132680979 351683925 731830211 919049222 264945957 783023065 551927405 979921913 968545077 984166139 143502944 534275963 578507555 624720881 635831648 683907876 697436774 743566409 519873037 636922473 615579141 694902396 58144964 731701153 663009667 849721140 588658383 677575834 60126844 673781460 640892813 913237728 469874788 815418495 183730020 684344517 72157713 862345636 750419402 970024445 209290025 793902808 771483089 899105917 563078394 825216145 276457599 985395176 966012426 981721408 351956822 606886504 404438310 836678780 828438755 842122734 367433995 437450208 606366605 892724932 645522094 933447016 938919746 980328431 505974143 621545590 262025588 524509239 867519687 895677034 413302431 517541595 144092716 284793100 300867815 921979620 458892307 902256935 151445324 314741440 658555193 750908824 884403732 931310928 428832237 795856507 577111308 748816723 683916999 978203109 429854714 646827188 94135317 847627618 250867162 920176594 801252233 946481719 99218057 769670630 758679976 902825557 608703800 649134989 43335540 597620920 296000229 659737883 899345048 972838361 855220131 858167982 157695736 323084033 275369051 649865104 821844795 892234120 629108283 794958415 576294555 677450637 801359228 820795534 601731183 766729342 711556542 783005913 659751573 683904172 613611982 689133291 526909225 981188323 752212215 899359969 950274821 985836304 397043873 940628715 962159154 974762657 836218049 842014956 527667155 778574638 470367089 963416427 476607493 807607691 390434937 676299074 658468555 849425991 660489968 802300669 877360115 904853899 278976309 364337281 389273289 440037579 575061905 920346430 19452618 543912821 714636031 907225861 651546551 953687499 67611201 674981181 464765475 572844508 388157548 695160864 470704637 800995413 709330718 982723709 972741218 997105648 82786289 133029611 61098001 323661309 81232010 855547910 732996875 957260048 33439605 643651606 657880613 948422765 682334615 684372858 417379958 811312958 52985222 959471235 806867305 950924177 921579101 933592483 570259783 741151699 985372422 990984813 705012407 774836274 110134672 704520855 41123353 837710691 147169525 764565189 403123986 528772964 489499807 867097702 64380940 585062948 722932635 913603860 207326462 874483188 488669879 678724187 954623089 971471099 109765497 133429084 281456997 287748081 54828233 347721225 176267180 828929017 73236488 705067441 310174671 469207012 472507250 742272485 609539310 797545246 775314140 833733542 890856597 957902758 532066985 988445168 905386080 963921068 726713401 984442476 854871598 882616018 448038750 854124314 332245491 430111040 307091805 636590565 527290305 832291884 904744923 937823324 300992337 875261173 526896815 855844031 390721163 606586338 894023340 950253404 451697091 864395077 181101014 474523409 578905944 887387670 277883870 950030984 549764677 626693419 892698118 909838915 288582360 699112934 453023968 960594335 795794527 865588465 897063162 924398373 849096504 875741428 545210936 724601415 602575021 798663200 768482350 806870445 277613281 440827347 90960302 911074313 319825606 806353350 547588177 844407812 348792577 976547953 602982326 938009865 430268739 635277942 355619054 463330617 339681140 499392200 995473278 999832815 392756944 861884654 347537908 779489481 923759672 965184239 616292442 910441886 55302803 817012281 83252378 838141374 755943022 776310155 831627286 894115722 625881272 903416469 673454902 960505263 383152171 815823880 505616252 783914926 789230535 898808978 566149557 743336486 451779917 918759103 927940403 989243457 482276339 507535993 726867579 781649688 186359694 983927709 693607818 984894809 34240073 490706083 746660847 829486391 455310966 530847308 748995789 974924449 794974072 811592358 398067716 964655353 23304473 414752569 370507595 618762935 479884652 999669672 257720470 399158533 747217365 814749273 687501900 712632016 201155902 759996411 500181428 765640618 579750901 817046829 439238356 863503932 539139344 654274872 879662897 933141297 664436571 715598638 170922072 214891264 851105555 927063365 772785899 794904678 619160000 772433040 163273582 302713542 40494741 639159556 260682317 340445082 618199919 952426496 606974110 963967965 496772406 656084649 447113259 671393301 496735206 764056000 618216821 829780672 257019206 306844453 157468496 981474318 968825512 972312767 498098753 932169149 925434021 950453085 866227871 908365995 202389232 402121430 34506077 409531387 133992095 173243737 582146693 999270049 269510361 407729069 434645421 577525384 444217738 730472080 971989762 975807651 185341252 884995960 904033322 928968839 220457359 679806584 699269675 706413444 87166014 182303015 235337441 292116547 25027218 303338555 304592708 831899264 598966635 765224356 703489038 772475048 757445383 927809287 608769171 990133587 198121469 470014577 237226805 780985224 572151696 806201955 687143855 847055768 740720740 778743911 713155920 792064665 943123825 943561419 411469017 736998071 40847746 994349447 109995417 711619593 471879671 850043836 634403413 833780036 102930304 246691683 982891006 998033049 286971306 465482081 744057871 886761582 678477596 833702773 317858303 548497885 496232310 542311906 958801746 973441710 832551674 848597909 920369536 972136113 143470603 805628412 501222231 791974378 391577888 445525246 102837026 772587005 899437462 923165856 240817182 884391185 323355615 813902579 177269436 871785710 39836587 598464409 486365876 564219089 272275861 275613091 430968149 520356864 337879010 758143470 222790249 434038684 885430790 885678937 487046347 712822396 577653025 965117605 183960496 536044311 782230087 948951819 478670346 906169375 805736000 896505184 379123799 899314458 951671973 997710354 444881263 881820347 264406677 503123230 400954422 544753405 832512170 862174022 225638724 835866479 599058047 782576487 247405077 704525656 404491270 793518462 96171741 899130113 389867624 981121964 588626189 661124280 546177464 546425932 843173012 879423078 50699980 441975979 275741428 975618745 253555785 338367668 295654109 640783542 29984088 411964692 101813901 424059910 658047141 685540121 584068960 892344790 280992819 615495265 847526632 900437552 434466007 982213655 804469539 815512534 238327611 578117153 395577152 581396108 201859153 418761613 651586427 734351048 55394929 842655507 294784844 436352502 988573153 988720381 405607470 604133217 555677853 964266599 176736893 503512003 973685684 998125123 154690667 534069269 272160876 526379429 479997506 881618738 835610581 868384446 778516960 804979660 232170822 594037158 572750003 866001854 329839614 435863896 957770085 960655462 258683956 837751691 189077986 695844552 742356874 808216656 567965420 572889392 672708444 984574910 331500603 818063612 562086006 782513186 38478353 743938676 27987198 472114223 751711998 946444837 232960675 308871952 437812043 569921752 174243981 367688156 173728869 496634190 238110030 322689774 716391426 743151199 133979177 966354795 558804015 835432764 475621204 782850581 715500127 903232491 302012672 544121681 270968530 276858560 898941704 990876724 585574101 693839444 609671283 672313008 970066052 987935248 623375715 851203294 748889955 832423978 946931582 977422855 778973423 790486565 366812563 962315597 348616527 793607082 159962218 384258302 157430687 428011539 762643669 991778251 115228659 451529503 439893522 754673697 254362490 793987747 782494414 952403619 507950518 836178262 491333872 744169523 81657891 807696587 489042444 624098186 773023427 908617667 613251531 627439055 971439793 995096560 99340960 238024605 385038598 745354944 536896081 761138418 335767964 667835065 445920815 526133635 364729082 699144471 502522625 668418303 279701798 642819228 57627917 190005385 702245126 711011391 545182033 565836109 840056034 977907509 697591964 867033101 24018936 679180311 871228263 950970154 546054160 695803396 598036486 638211778 255601025 316461668 184371378 782788591 509631528 884290954 433909341 741076167 691372317 853794597 49223426 414449039 380310945 856203967 756607878 960590237 100197762 244567416 140003486 199985771 727814539 886840739 891353173 911899470 422740204 543491907 670073376 754318204 145254339 768560368 850316710 938481825 33015087 921692035 238505783 941351325 11843205 816149247 645514590 902998622 623975478 655316821 61333066 334195491 751992317 879711699 513527317 534860881 268073637 820846107 593127846 679253723 565829959 998380007 357978991 517305719 770252646 867222702 875290648 908219705 742128617 961479036 685537286 809651727 177403024 998516021 334033033 767073195 374262171 923686942 310781705 623793662 964439174 986766360 213004628 675396432 812766521 909529678 425971432 948660265 135588582 585759114 819608369 974497919 463776501 782329363 633499712 722286533 202168813 602363851 668002994 832924940 183207447 874125303 518678997 917579368 600257067 960360261 181708644 421774935 863966735 885825123 151618953 385179410 742332150 914977814 468345615 727190563 814397796 904692794 153790151 255816481 161048220 985867513 796206775 853286775 189465452 307612713 113622826 747135294 355197877 701741239 994843157 996288979 480774981 840189110 58291201 790902607 541301864 956588749 870571629 970620471 361335096 683970615 338226872 808074789 568344914 670555397 849499494 875356086 619363040 840563226 765151154 955867497 593003817 757694503 804140252 831398284 945888960 981525325 263207195 995976645 916599627 962789197 916116629 991136546 13508930 347742489 17709042 648045057 312337795 314050210 286607580 476222195 523607350 665555761 330464419 916608344 68112647 247386941 812077639 912580143 420838712 782678903 268457110 277176437 804939857 951897706 655054252 988565901 115123361 261504131 842499865 867399573 209421817 526980624 228489428 280568160 371040919 712919144 566009491 798667670 476223508 636665423 159090483 547552499 875187560 976004854 31985284 380066421 274946135 551727005 76706335 759398007 840779178 928541221 802312399 945800065 666059712 845357351 232148775 247583934 854422301 995473638 929480941 966855817 459296922 868173651 564438221 996143247 604318371 860304674 206119775 284536107 873536321 996312937 937430949 958257731 440246305 616775249 873244540 993172082 325060357 339726602 790745104 857716249 839508890 864773886 727925229 928324831 726971304 735401501 282520183 675963836 139551112 516140249 826932447 933147597 574034718 953965042 676040745 843464479 669439959 909615954 615068220 721688549 276736377 662811725 244866758 657001835 501290357 513838825 477837539 626331115 645499825 859810526 81220527 113984828 217767044 398993083 191128078 311907562 572558900 615024736 19147476 950446777 131063524 836210664 117718849 737271870 566217549 797741249 513192831 671937525 454999174 476193304 913945714 915182875 492642807 616374005 225459352 365433114 192527645 342215909 321987250 506851436 861370091 872161229 550029236 651624010 867635475 945937973 536603704 752661072 613015745 863242088 362989387 746503654 832267319 887818303 392263419 761244885 940313460 973977759 708822546 734209001 324358610 862186029 773279515 854819873 405950500 685220979 881147734 956886558 432989780 882903809 745843258 968712816 864867621 988434420 197341395 701772231 153251902 654305076 574998692 635968948 922272981 939847117 919799205 975721344 464539455 768907581 775137845 932166242 825861142 837703703 674920846 891812978 588994812 803226953 287535429 387766479 262284946 903244234 720065518 992698378 403698650 702869045 925296176 940941534 507775118 916262887 469436379 933572001 63880526 210524677 58499767 839288628 608104041 785453022 876029015 897965163 63496310 166789531 137938333 723723680 703637101 983419082 909734019 914729288 713994654 816555335 776528982 982824063 892636893 920443102 739071188 874950545 989852365 993799135 305732630 609820483 678457321 892840002 456955749 969618589 200262877 277142305 676712767 937603542 109804693 434226205 845950215 902916702 132373055 242132169 186713926 333688884 92387951 733569621 265565009 996943779 222863134 979729699 120365590 527334768 544456606 695218000 805837532 814112103 597258080 717234941 772756549 971029344 787477458 908796107 709080913 925628487 327233381 370416352 877500947 920876960 34702570 361574224 917185418 933709958 681131460 819818441 576944995 925683177 75315542 380457165 399952390 736654946 815458601 959011616 957764888 967762270 713737134 847309285 374452101 577771419 132483773 587831165 126026509 797718556 711223341 727999497 288966515 815029935 699781532 719883290 55058461 297135571 761539556 853255949 245951845 258740776 836581014 924074712 905994498 943948582 588880775 794281459 693265299 929560043 488367617 592606618 166931228 307417105 449397191 836028534 615021385 845512596 462507356 577918314 17387732 586898518 659685013 904450434 820286312 976286279 221053807 615479970 957996190 966330958 327068109 903198036 316526292 697392864 185359649 889218258 586822214 658772607 792945269 889477163 998785578 999854313 27313401 442312912 800513292 851395233 692587004 795863889 219377606 294482963 985661758 994155827 596527554 816636091 174511366 645457423 126459511 983579079 618459728 646695917 378616179 948757514 219980790 975305904 591461453 839616102 61716333 334683039 10604383 624082678 488491998 739318365 582067506 827992127 854943805 989185169 783128012 864251386 699149430 737011445 354355113 479414136 433973691 973597654 120332709 414764140 306881080 735627891 644871771 850476230 862154197 906795947 824602645 926796206 193702130 862869639 78708936 117339235 939920147 952562841 931867163 966122269 136038655 823111285 605020454 930382893 977713415 989245674 144528302 471995529 432917123 685764096 920707396 922891265 327831655 673409951 233550453 938773835 676533959 803602739 301418911 314892891 475791233 504947805 789645966 966682891 850639204 856253206 815220596 966522066 487684520 510148953 456628134 474842464 877710610 999494935 177708894 220878965 846045626 928778935 985161891 995217462 959873360 976935564 442052140 709546127 808034235 944533467 259441083 664041803 858797858 915379373 696739323 982213729 739136905 797397899 904712461 920317818 968777943 969473514 23416355 395859264 957317418 987966172 136621054 268322506 550523936 982359052 449677630 918095142 247128290 432050985 57774669 442925451 639426718 785147023 741108443 857170983 62525789 739936703 240504048 488728820 623211032 904470288 315626792 671018471 303901672 848651525 579670123 980037108 695487034 982146130 749181322 995458582 291316828 957794094 768851867 963775755 874788306 985264329 402400646 938924975 151671749 446397456 682385371 814161301 52104639 814993321 163360158 253606256 482199570 712537564 681812206 907854140 620200236 658370049 241383235 601426800 634976025 768513237 386699297 574079278 899305422 990914908 239956094 624948478 975118553 985183780 569726831 680103057 330966672 433635686 372224451 549304813 645848149 956925876 59961156 751822244 982146671 987030267 756391205 869415740 653827303 840068133 593062965 612599238 218083145 606446655 468246926 630175334 939656404 939788533 460251950 879296365 633022090 738066005 594696766 925444307 619827413 820448443 805613788 824537110 163623745 664573106 146406179 359611959 199513721 961990531 757148224 857371212 402435705 996490658 430451113 719647254 927773104 945920648 880831604 898622917 175450831 956075188 205090284 696494965 981735129 993903986 799972790 993153715 782663638 791590994 169107867 744765046 803566332 935147519 189819980 696060607 375916552 905498436 581730673 878281630 729362786 886561718 313986860 603056721 90267867 316301149 468775784 763528496 767349319 822488109 879378322 932795988 834790170 850998411 680344317 947303719 220634540 634149988 74850843 960695625 375699970 554779285 538493883 871257966 43177941 63512112 801746134 952561391 586729893 723595238 383056452 664673133 671681113 934778143 918880183 961367018 316945730 705064736 529020787 604495271 155057465 558094813 22519491 668947864 47605649 472534809 443866502 567886037 948991300 999468911 645886448 915523509 456198118 744913474 386534633 407781311 998091927 999478129 802832840 891476090 365061168 556133317 854345859 857422596 370751879 478482262 735491829 778303250 579506699 686454539 793217520 979402114 390146561 454390877 455996599 819531778 549536540 742742568 956168532 965534557 750584095 885544158 15208288 59829351 416049590 636536070 725704244 941331597 291538224 793885547 590781589 628904955 310112570 539259953 623352172 807078089 65853227 448844036 705234877 971473007 804546305 863081597 702231100 839138368 294188593 552202623 607644339 761360303 23940251 450009594 333096454 430671444 479545841 577852899 614582108 839509733 610717039 994311189 844690886 992131500 533547969 657786016 106416856 743049194