4434
849721019 499145135 366778041 893480243 14606684 532012866 436331600 895470810 337447975 361340907 701371268 702154456 325608151 526730983 792373346 115803245 81749237 402343067 67591217 108729842 814737269 886719198 9308756 42985242 417432348 235729475 589627551 898063084 574427138 838860566 829368960 602370411 451361762 231829308 736781163 519666252 237363405 533529866 458405837 906623968 865587 21897330 828066699 913298303 634864285 719771354 880577567 508002480 376695280 715589363 883061702 295193273 573662864 416721057 40065810 979181854 244425260 95463484 390462994 555157495 170448177 826670219 447682427 401541303 261430382 850995483 720628527 134348324 728564064 770922868 109510391 519786061 56063868 892022563 665022129 58384229 874839775 214499485 368286031 912419882 555960874 183914592 647679656 826005188 84445827 667802787 327674875 423374013 905973592 44931204 437926459 827980623 568380219 497772110 915190623 812010436 236536738 421146814 403995951 388797581 985528134 312029995 769134755 153952188 762236931 439999728 576750258 20218755 726385753 845889991 715965066 237923726 27431875 894383184 284781827 786495540 849970038 676769172 299244752 95618555 162811183 153318692 744607785 907408917 721192171 407720400 237491438 111634681 499504977 461797816 582643218 238843838 514550779 740706593 425572666 257273397 842767649 276241272 354662633 463288346 724330775 442983259 170283431 493544418 626425243 855253195 932702034 509753487 838376443 611041793 111138810 226665715 741641257 696312690 930842416 401009394 828599375 724205323 584846391 458005831 623060752 31464844 994923022 525994406 226901754 488838089 349086276 857138189 698087658 604055874 213560325 784542782 334875221 161565262 573144867 505674460 124427641 466399925 462974730 299185177 744277868 5583906 663656863 138206678 588057544 935407833 106056575 236375699 532596405 499882648 850746105 526732030 454341727 682864165 43166983 224234521 445364748 477877047 204810760 547541897 973509709 275306002 524689084 634170677 818835696 190995433 166566868 368603291 853529364 363661463 625424926 463498117 66806566 925705291 862550029 941882810 816801237 365910753 781601660 757891639 590009409 904407401 879771091 730519767 504354685 886982424 56118281 292158454 774573652 277723021 790151734 405711291 949840659 997411305 447609955 381251684 523447726 312826248 152464060 997964974 444271784 524153664 79851369 360102849 11327151 198112145 764600861 838733177 43970733 91811083 949588363 333916976 612012798 898625341 393935998 273554269 190524183 17171034 166979944 173671331 425954897 49566832 167545781 834843673 881283441 937255471 797478391 575720649 936952802 105221145 200957635 532175426 663073023 525380616 625419833 48745637 63838469 198710210 101277325 127636082 395203894 455326209 830300771 219510595 289348948 484237210 124171847 547207548 990431561 562343783 798905376 480174046 561807969 289641259 301316959 30306212 402280106 96051604 369426623 923218215 65451267 918484473 665956192 659217416 253437829 958707239 495729264 716718077 730516744 816416781 273474521 89181928 329922122 143594090 703391347 125359368 206869938 425017370 961776812 797523545 216201116 834244377 94086207 423663805 747422627 917301668 581672430 793689682 622042073 277921022 898011562 855846541 417410639 215047487 312620089 126582605 898416495 123456793 251444702 820837871 961021148 257615993 537178463 755160610 169407133 359114293 252671895 593872790 950369987 7428906 796357239 292700268 640758207 479760327 53138270 515884454 593528645 16967659 856819482 997661908 828658588 61684804 478677065 800234707 223828313 118913562 55177969 747289865 161709067 637322383 573408157 744957485 500056477 30167008 714162230 826997314 675565948 139801976 378477072 284494393 633806921 704379097 154480533 427959424 741603494 356513841 119023498 871818304 474250424 926399934 866415177 531825389 730401935 905700084 385833524 744354771 878991753 438451925 217463977 379692665 847463156 297637816 864336165 710790767 852621237 239712760 887781453 703916654 710372837 709373647 298911781 161905658 886452216 266583738 646361568 721160054 681291530 4573636 594985424 977331500 939855646 375850380 292873362 959503846 94596366 652501115 481446282 786282823 170430368 415413832 136002631 721441151 712773332 55925056 702494065 534371301 983589534 669616034 272260831 574422425 362927287 576290581 901387366 295978789 877409758 408831252 1802551 452872669 158799989 356713111 73195873 538389354 956815047 721612826 148881477 713953476 559062608 631173519 491201646 926402670 456082941 512621460 982399128 886812497 716326 502125764 170266572 218456266 423307666 98125855 109985628 758067245 301076899 558437853 132547810 918521085 839464683 757850130 628173474 727309246 948386967 895260120 210925090 153233156 650510519 46402788 814034784 258075661 284468153 344392108 711978839 264658472 599798350 512438374 938385743 365143103 784649117 926167975 622186753 887732771 236895310 563029432 130280097 978054410 839990828 357664779 559351753 354286042 753652172 25364762 843138488 809174353 520234164 642060161 416441642 271653084 91657064 388203113 659010216 862104688 604099258 454967854 682987565 386125780 538075566 345685930 486635660 413348867 952862371 798530290 854605845 121664255 709363855 907007804 81958123 951952416 367511326 502300898 831196646 714105452 359785264 490256438 592303455 890580803 828994082 164137284 91145345 625907175 474588869 534903460 157973792 670138266 969146393 645496480 400403477 97315966 125720875 212371402 791047023 155484502 918028655 273360668 852919613 588120528 943849710 719336321 979825154 20527681 237413921 774424071 473654738 553671229 834025851 86561253 222473877 233718594 271403788 795477347 956921141 868423385 187165149 445426503 688463891 670375373 520747407 138601988 291890545 977770137 559473432 527538598 709821855 729474048 539398802 483758854 201572275 297276556 95278673 443694249 430657826 779589411 64301466 48937480 427813929 938588757 462592477 264024547 523946015 237823152 433989119 958394541 518272337 36464073 765057951 480330604 141936124 282975736 948857039 978811596 458137581 625373160 19587300 237343337 752041814 117916406 311971575 645303930 700382946 506022664 903941821 721453042 330030407 712127321 392111405 599400238 201677810 635392483 193244615 362809581 732908815 91864394 275933301 65797379 632638973 574065459 443706705 126260847 662054107 620740861 43717984 675012167 353853971 532544563 620081355 357859669 329344568 494204058 525031886 295367376 892260968 539698008 276224694 165714038 244001312 288300009 916367632 696231322 799133547 439283822 52515490 336561344 236933123 487494681 777676244 297621417 44552340 487303820 198387644 459134997 264867559 487686179 328388419 899529077 442781384 25328061 187654671 67807959 258332681 63458145 435897818 269269989 807811049 267599564 149719055 673451231 813734869 455954847 925935314 845767910 309185246 600834374 104706101 74230735 462124744 453176866 853654080 312268812 110136921 91855394 649460769 535528593 940379598 754042711 585689474 179305465 569757190 240837714 723988764 427446509 679229293 888164185 381487237 53089214 737768853 700111964 697568929 253360234 604193459 973734752 775540198 25725104 203171115 773261063 66814174 156756839 734605699 472039853 10820649 86338648 184345739 133268205 284645640 819579216 223680942 645405426 205337386 597460578 774237386 519660866 906900200 454775703 749977397 97956720 566028575 827979378 823192846 677801826 759865879 106258539 273402931 67984542 14555078 326985847 193328841 9958183 895058488 652027250 798478840 953714453 138862676 583801126 528238338 569284418 538066044 497882932 785173675 252630582 195554606 396202953 685106252 871039176 682521756 172971779 78720599 768500068 586531541 86021587 690427713 796446141 578710789 851937347 219818575 511722698 643619424 19217457 630595076 413473920 233461831 683822618 908897534 900608000 504062018 106335612 95237856 319518332 831296612 870694468 804098142 574618109 252144889 790520087 367360334 616272000 10232835 786297415 379778278 586017614 804778410 998973182 36300700 259027751 724513093 722878624 750716247 799668416 418640860 670710146 413552316 968602564 294237143 213994548 709453516 844361484 557139652 335050185 483309231 202708061 485229971 74363335 748983300 317154346 700178619 352272838 697469141 318281722 55739513 442184703 472002779 423608356 156169105 247542741 351296526 674493957 676548735 879466304 587637286 85581830 500350682 196679943 24598444 201458465 76976902 265452990 911580420 307035296 392515538 601872888 186295016 594703901 550056986 416714138 142825922 840248204 127560302 846901206 536271234 990310159 540016325 990655332 374623127 327717153 660790544 527031723 564523580 521439509 988647170 396168739 230669004 111560092 708592824 509934368 168131543 596093907 737219216 194284335 941111913 673803619 126874375 666658398 327497539 572334558 47572404 268988846 28361254 573055898 942146284 7542468 11568927 274613048 688220266 594874263 706268215 283547689 348102029 807696298 929951446 525111221 611886000 545557804 310414808 50427066 171797441 766009423 335135588 144477256 498429480 187983240 106938282 247047740 647785130 520841835 554027444 820373548 499765226 171460832 970757896 273469042 798806898 349268781 896371926 124775368 27808501 956297161 826668364 332163065 17004661 527188511 407123073 62746931 790470740 755045570 71313425 513678592 701227174 847024967 40103618 908637784 553429672 127426021 448761145 282290239 135445615 240859965 655962177 917574400 40183829 612302701 436222857 285131636 677944714 140307968 879959419 282814654 515164555 835391164 724467657 722155968 573220015 824207126 278269183 78448980 684487388 332459311 978375795 20075742 967765363 965588221 967485536 635884214 442911417 556700656 37321484 885802962 116390022 744302542 539249670 363381983 273994877 632681063 371379939 374039492 710966851 302719627 723118929 622258245 910153091 621106609 288669115 45398441 506514862 230472549 628462242 762076004 850493326 626984195 87410788 138363569 959498251 510510867 707166700 426351467 658651777 115311126 747579561 413478850 521728324 415585626 125827374 825209176 895726648 525647621 94416856 956942710 362354050 451797597 53058039 945472610 332977838 178915868 473015277 491213021 864399314 465781419 178441595 832554177 527868864 707039288 302825413 42281126 61847269 531846901 307761116 931191660 728161775 898824731 699499140 755136850 988646106 238603102 945973316 47358547 25175159 92232914 232038327 443266020 9103478 726661275 798519789 122799161 190342440 318205636 592368356 472764829 737564559 921019183 527027769 429047517 791993498 642118552 182343819 628192730 81739008 924563315 203889683 261027362 637032989 308330355 616988866 826467000 889282198 361864778 60835661 615914229 208830321 596913078 3596157 706374960 449554187 13933520 704709980 624238869 150897647 566772001 519740830 477725997 195981309 634702116 708540233 932681500 881850662 738617779 324675366 354277475 709184111 405818379 270566281 46061228 483300467 173386999 528642798 699784498 872683623 179300687 354725797 297166656 469672211 785376057 39408123 573339682 601894430 479209391 10858793 299505245 566341746 280866051 144642185 331423272 602323652 429589599 899414498 832076078 457061521 895458579 896700975 803575176 749744187 825875644 248402799 42849511 864827828 784727342 95151852 839232994 732565392 168069170 812111283 504341721 620651371 170899815 413902784 385322551 605185833 287283257 710207252 912904417 196927440 149327065 606445754 137781809 12905874 446353710 594064175 772400693 436425877 294812695 678226137 486380266 639447850 615138512 649283834 905099461 434897879 590428718 448745262 971942749 380939439 590805485 694126023 62840887 558074194 406016808 669752963 573049805 260282586 139209766 797002278 781077894 980697776 809756153 874174856 442272569 77641239 656917317 773624712 323587228 774455061 879808396 131979442 686905824 679602336 624298711 422116960 270746779 623822330 27641724 972976443 325459801 567695273 421606529 327782690 84323819 171845271 284116990 377829564 71249091 410310542 388319344 336717269 55930742 853464994 802285373 772257746 876121117 469038579 537383828 4967757 125877660 414270787 636385248 807689687 961976791 707266697 838338552 576686404 720188177 870406063 708042949 900989141 718892461 481453888 262969289 70465287 547230400 334485176 820527400 861145809 409210110 703819157 309735907 105882454 88228432 994158018 557869300 2561829 324659142 776278141 198287634 68675914 147325156 593033432 900416905 486068449 927368838 257026510 246513986 796619080 835444791 578482630 934641818 787806962 916263554 252637557 134041280 129054544 459924117 928231332 764898696 711939659 797788938 127302712 324603892 961976609 178890890 498292184 164828888 59455114 743614612 223452245 833404672 151677028 126139507 974050496 139069913 780047182 533723110 263366996 760942092 106083095 152481207 18411351 964048055 971612056 29443192 513977941 673690339 169596544 153327986 928877838 945287735 33968588 521362084 781365714 438391691 978990632 622651176 757597085 727934032 667672324 505165951 725779059 190598494 990275598 183091398 580060305 910075084 706492657 13215858 149439678 269737615 709189545 751293798 759387081 905478198 590314970 916787660 624719746 432045861 350582157 171466722 920753436 860752667 259233367 498436581 612305277 847802168 769765872 212680253 860658273 134685935 698475827 376050486 18778971 166355124 447211591 358094595 403332562 893076867 256564987 504227652 723683091 595816268 237889676 264050426 367674074 964006024 857409513 302321139 846255209 677280750 214023979 614273735 389137848 978382307 461384144 225551693 591542784 874008181 536849171 314517601 631891873 333619694 192865979 178117309 144257642 592810972 295488191 556245414 300069431 393857681 831118888 960284764 994388302 801514188 740174340 727733903 749836259 444672115 276897513 154826194 580844610 897258003 260242428 688452981 410483922 551821535 171049029 390673706 582292575 771297720 561351305 366459572 253312700 363495567 826821621 911607884 734124106 533323994 742135759 728024715 309078485 461928962 260651659 717876014 918844657 819768166 552602219 310552746 519315946 399891840 496085811 855684588 458127289 690093807 204734561 287974163 985868029 477565959 448895420 810724602 554131995 396224469 693822898 715000810 687469934 210432814 248798608 612422002 287243741 376034647 349928685 537431921 999211042 651623927 699636911 553010699 471934080 698918320 952684837 576435222 679568146 483372488 47532832 118705245 402784043 776724683 995869778 705875002 429856364 52839543 308614732 764408354 713655045 412351907 861011890 470526736 204133458 409328151 540889599 290680425 61078509 174627246 345936774 80185650 129129424 369074933 727297598 855162659 685931989 813612858 661171653 234741627 1524144 778420236 573651152 825710380 984016009 334196532 349682923 150943602 802703118 467176531 611707388 241527049 287092122 737789038 429016453 991012355 619691095 813586490 6468628 310460502 986646804 708868763 227015256 563332257 437884400 956924412 542511972 997992326 485307072 592646521 414083169 263678720 595873709 580530603 488909199 845111948 915380742 883032021 980357229 368714342 657049998 696393530 780708096 847463427 191009050 657015143 244796963 828974733 810670026 697762910 308873256 61823261 234152058 307158747 870486837 488356988 178318923 427928595 552800853 118250926 735643920 39208387 426736813 153546713 159380715 431031226 291905729 569380092 259921069 762155206 442700398 854290219 186972329 562440633 855954859 915379416 555007773 718420828 599497729 817010301 129707869 685786427 800503367 599747309 568858247 241545099 971455899 667624167 660104835 913347296 11935804 673700008 274998710 768106306 764713039 286681061 738496551 330677722 260805519 313700820 977055147 549854973 136654718 287095718 254525367 649568346 137810207 14215764 184583776 10231762 672701290 137027890 762238878 31575320 60024889 801551903 959224348 623687422 972243563 65557216 285985278 98560976 886089966 938913652 155650256 56613373 257581821 423724473 267884501 263052123 951845868 772158950 504893509 678690892 611767744 419421512 583172105 421761497 677035923 48742478 707653567 85198760 845134421 301858151 646459409 978811323 178375003 250647951 699206157 980329161 232249992 565815636 232127009 93557824 687156773 264188383 49382843 612282833 97174679 217079482 415430170 254825030 486142052 65305288 673228909 179287172 178474244 745303166 199334436 508822126 406083972 402546759 228736421 73298048 289595393 39098426 375529926 517615912 966255663 237347021 547428468 450769194 395115414 181094415 381438814 659505761 198757671 992177485 616013338 747241223 140782225 844605281 788299245 783525413 197038771 125161257 432998250 998119720 140489333 907879719 989814587 667006625 757353248 12795772 129641985 986045456 477762151 239929297 901480046 858445796 80744144 810572306 876661810 837660011 967547411 713688068 454967708 982319236 755235560 383908341 641219164 47408718 408182162 423584343 299358710 397610382 107736282 260042432 443377446 935168283 885131986 632639627 569876831 457337241 149588184 595376270 462857757 938417188 974223761 747867041 291615283 608047362 907709249 276949080 964104592 734917382 236183209 236392969 790307938 930593308 253103688 230891571 720213283 498272372 826033238 143145054 256117468 856361062 67336806 944227856 454224208 658650526 496083066 497301268 230597765 712209798 199561531 210799160 430564029 966669681 97186570 832365348 93933961 51054375 832430453 327951111 286576682 820758558 652356469 423068925 482411662 581434332 215675271 906209435 271704921 480617651 378435315 189000108 472863918 294518549 958629817 165210485 22853596 158205852 187233650 56036825 969213250 119820051 364468975 399180588 43940369 586205961 860625600 736747300 878490993 401300698 584047306 818097649 955591571 364630200 410440772 25733899 191159250 379741165 105628128 582369137 201776807 162261952 209306164 435978249 351920065 305696364 717189726 745353131 169792530 457726768 426392599 4649417 830392223 746122617 231333163 701053212 752114838 268946039 208858952 61190063 695482712 905201276 191543725 50628381 281677576 739368849 563895429 360239137 44995585 843660054 485793199 556067606 539874044 205241626 546825484 531999374 630345947 948458691 608481994 49692873 325632819 135406143 202167927 576651856 912898450 804374729 679217936 911031779 480437833 352669756 844035617 148396292 406499453 816924365 476289698 833101176 145343085 510812842 56109687 713748502 351607246 359897237 440146055 745919865 521436618 989377122 80494922 476016968 629201215 60897240 747148209 674143741 825615949 547704077 25565871 122031731 730325116 568942580 759712204 507236957 10010485 325458193 271935282 2851721 226886570 785489750 840304997 186151921 197671666 784211236 220413694 731206588 247148902 313738065 622983235 108829488 166091689 462385462 712093284 1131209 484799592 691557560 786241441 812342170 957251389 338576228 46777680 453443414 873722657 516826281 434971223 916507221 217730863 278842404 49320121 814777536 555508022 268207596 861063082 341651426 705182673 280494117 479980707 675844178 994919757 728151308 897100422 274118914 90601670 182637198 773056725 705979749 961009894 461323857 516006473 130810245 552138421 270898119 493262452 310013868 884859433 819720190 480488550 178479816 750505796 59951940 959338336 797521993 545282707 990140887 969151486 835823476 326397781 836035481 809768569 434077241 781427181 985656622 10670752 240920526 446951556 914248146 334717992 919535773 659695611 252988591 262736706 850368839 332935998 84410693 264830605 404824357 844843789 76282474 842414031 487068674 791620255 451923270 518518386 109364788 362452416 310852095 784062022 711716997 523826321 749856373 214020512 376057913 726731409 310749256 474977053 398341326 430402460 608079398 457287747 969488067 789167723 802516677 630535289 488017951 626701385 488329466 430376002 197677346 44540922 732915122 654850112 194098340 490920381 172069863 408003348 860230935 6610117 120483002 797352146 884601593 481001837 16509659 98910508 137268379 335498033 754695188 439146877 667582716 994275799 825898002 100020152 309487967 304872934 868180751 388229660 862836170 676341465 242711000 598169447 403044384 164273858 609822264 818742466 839562123 99847391 18082460 92361673 892698566 669973317 331488196 498874618 437384010 654446942 983485922 589168481 9219344 70134445 815646262 287839839 114461592 380209059 282197571 116120877 781819794 772177942 283091761 979464301 441962716 105760283 11516900 558783663 271850271 367596266 603927466 177864387 7724520 684161933 799364628 325123940 877316561 466322123 158425118 62826922 105938293 496418047 686899354 875976429 41978103 462853581 447883805 965912403 874791654 367021450 955329917 7636299 187767789 235642861 522871535 463336146 48565460 769128780 19131069 749253888 677769697 527729394 476914279 658276385 941084450 41100734 159727087 951419518 456455491 934290047 604231976 17217592 931739316 751033642 172185130 313706795 521436659 14943716 928894880 145171964 73345275 838302934 365519063 406909046 528956194 550011687 381140639 865430903 179394466 811573309 605110183 261346891 467092237 784722241 58361231 327416620 596160117 441790823 42766524 939591755 38306179 310998140 784420197 697294364 223924189 277739814 5930808 109683679 548968009 167014889 882559329 793892644 161662142 161426647 360330684 372719965 971608371 201645730 613314121 92105314 852245027 944132123 102257492 20758741 335461321 768410238 854751550 810983355 739004269 684696339 802248273 792074362 930973600 461723499 902602130 261729991 323533588 265332474 904569315 283006354 666763874 833626439 830596601 180832140 610525143 234532444 357151117 101673334 945996474 240841049 279841065 699228097 833998407 93942847 376728556 652440811 193919856 564625143 618480486 774897049 771933028 657045429 98634719 449173787 514888738 593488081 496569638 697105910 369869181 150211349 28687317 208726500 545635656 457670560 717027427 253530329 570449247 918337774 985350851 24906598 466801989 106410243 928253379 799380176 831400836 896252304 83176519 674796014 359437778 430683147 45397914 192845559 661211782 943835490 350133048 674792530 682510624 883381702 13150345 542789865 272383369 845111130 379470742 977842284 116001247 550761847 40869021 874569992 776889787 821808320 660072469 592319459 266470064 285073053 402229633 847511310 888331827 369761718 913187253 45624318 5326597 514661895 796542786 593200943 482925511 2861916 70688726 797684237 813356389 692097844 659888422 537781705 561691590 81112449 951082532 721251474 302094784 719282419 136428728 792605725 834957897 459742434 926008315 581657055 749635781 916460692 676258285 765133583 270591261 155136399 374255052 496197808 15527040 391925221 387368735 725026559 53349034 980594556 165161994 648622107 529303864 738070975 508864495 954506348 194640175 170603861 31180143 486913099 33418653 454323028 202791864 338192014 415186818 826065146 642541003 24969136 297175761 595238065 741827620 409633980 84540253 407229790 529110827 855466903 413390517 150890728 605248819 579113402 987217611 626031417 281294638 519626013 275519572 749040913 885853902 38361409 925327767 349477776 903952117 45567553 557443665 933944537 608659349 960559677 799419899 379489625 35282523 114646917 342193709 466537577 171263545 774925165 826634175 162884143 370567309 399634784 600709601 489517194 679185863 262013243 202346374 14760819 231208836 148887348 728158802 876563427 147954174 215471504 155855680 955983772 483973521 941848767 879574107 271771961 996612198 237104303 103278561 134332919 325945659 801729625 292477929 69328036 951679918 220300779 864022770 409452156 790227600 496249986 926484751 641991881 227133116 636508375 183098938 932587340 15842867 263048419 727028306 934480643 832430323 949909022 518307253 478677300 621371713 315504327 723806971 980276873 641659813 703169104 676355178 811208387 117540492 81195326 376957066 356992697 819841058 500693794 118479453 35970577 944538729 333969402 787950653 174901563 536081824 555669210 109081240 76958050 156209215 355867881 232137018 836601378 352224574 287096274 948359665 452577748 632853562 465645518 966608574 891448650 85728283 530341637 638114381 757905461 297367606 553406077 905012113 117233655 674623372 907967476 29276994 556501894 619028087 360925083 112800725 871278070 921087072 383079039 443702785 9403503 886743750 910210754 586918091 922181497 773759250 300661035 88237114 73018832 534850609 904458082 379045760 229850139 524565300 793818699 843189178 105426574 39410966 475996203 926464860 780872662 702066473 921105197 108344975 679205034 979926059 601538495 649881711 414467665 373937728 289834963 601588145 599734863 918422964 334225249 592175107 737481814 726567708 882213923 348937294 828676763 408885675 68236630 919788095 245603220 805590545 637395693 59216284 969467074 982803039 920685146 505220178 375790302 661821771 719668919 808782053 637976850 271745477 351849337 558601841 349617857 723046456 887909749 162326360 536446225 226993323 439709420 543713840 435263959 124491705 617150923 190608670 47364715 170424247 487343116 514153367 981909603 761484148 831805803 985369543 901872192 103931054 203940111 774008451 860690493 324682153 888641382 598448286 466720459 343150411 224796772 490762001 544551565 338038413 140824349 668055201 439208560 524180260 612461372 223301429 144291690 540652277 748193867 736705617 87061090 190941612 46565948 555587741 454962646 894915775 53503904 950676252 865612509 535964994 455551744 753082565 935786982 225665302 56490930 236160162 9061825 412995707 763350292 113763376 638604893 945942406 871351315 790656627 935725050 975840139 861819476 162003737 177872367 891432124 719614264 321640683 401297563 417834694 278361187 621550845 951351632 623336968 254809279 130181154 313589476 154496977 313432360 908791789 72100933 482824526 992538378 904485478 678745224 318381329 844360172 165988168 96877135 552142115 630195396 133903653 576922667 882616093 616137030 368034218 527701295 788156173 184903683 204845806 449779229 114003595 50917720 585427366 174093510 760110492 248091068 236019070 826620722 294751749 73361920 34544544 89527028 323266527 379186675 391454720 161483055 167182956 76673878 550127445 930537610 796128671 36610677 641543716 487806447 395536475 867757630 289465439 834376064 258589381 890718289 653251547 945505931 420039591 291993760 208172429 918428393 121631911 145264414 396288997 845578774 196552330 787753674 70657148 829843300 175278571 604098453 167590468 970337436 191329185 538569511 706107201 750467169 43369184 630665647 170879397 197917731 535355649 743895407 45181199 342098758 337571054 354590448 945447070 157601315 392482645 593032043 222765232 566514817 181699263 975337047 900998043 950141174 746905228 84353201 54790104 321715921 397470044 329047687 197681281 684883602 757665412 413951541 330330456 304844175 960612322 678934139 305796459 875103484 731327628 246075902 906209691 718547106 783522060 736011501 756976017 624315829 3471352 918453919 648715230 333820749 183103034 508648544 493799638 921823374 97564031 815490541 304703090 931681989 455399184 361242362 331232111 883616102 698568494 225210046 238579334 442909882 417166358 919361948 103097192 166143463 120393221 566227750 364268685 572895263 266660378 678606482 78468019 661638083 126045960 250203693 210465704 238106945 118307312 23629113 48812299 368686393 891950772 234221267 266326543 818639324 945196862 959375118 975344243 767139624 16674901 508125561 232937005 412165519 16591007 13748005 964057738 208589742 62893016 953621598 644581651 118169471 949424219 207155230 375031367 928000909 331590360 307202064 168120143 157389664 56030861 939774913 914208621 550789389 904707588 963330639 971486494 283591789 539726644 612220786 794421890 146358819 371229207 546175620 875608517 76231672 417721081 752429253 571267640 357056683 815757692 384055455 249817253 129906038 678731483 618819787 984308976 872719056 20410119 122978329 743039529 784250882 957180452 486568204 498194792 169230580 571716069 951590964 196667752 480475279 252838522 758327241 934539941 469640741 361758799 601247694 301493742 408204778 366446084 806483501 321011706 531769114 310093866 22518044 42993393 681965663 414168932 110853981 268650695 281947531 16998748 37437955 443120279 92301514 89745177 412784417 74808957 829068708 873961254 963527130 501532757 782228824 829019027 156356504 606484576 943879797 74405563 932890379 603478005 721197439 644037208 857670980 95015018 455744783 663230254 857189552 487310641 129044971 207688171 773539142 146128546 951360984 284700470 700405147 547746194 262107405 50866891 203740547 425464661 782299136 639083976 999429496 621243122 690398218 516763170 220576653 922433447 271594266 388065795 604535813 755100983 123133390 778213303 732423898 585927039 534812046 318138636 940393042 272391661 9046968 709812581 230910862 276687981 20049912 735358468 798869900 779531347 832837438 150218696 835075461 815199214 67135585 202184240 472124766 585586029 302619391 832046782 102344460 628357946 227790411 504250391 775540515 427398555 968046146 6273723 217608768 516986763 667489994 88367292 744963649 993265046 268282150 767553924 808263415 944130708 178503204 555723097 290475929 877406644 464302795 363672842 45572667 431667768 219746356 744060045 979540143 305138262 8569481 344268315 265910963 655469199 493555330 142343629 480856715 695283614 302125786 28759607 825578533 211885348 39811470 604677681 32920437 551890655 744236849 682298157 597851613 672922843 831849826 595485245 415517126 290263854 404609404 289319231 266400814 81984518 498768802 20147387 835471914 884061331 246095015 875233175 931009980 25925836 519189889 619439210 826060033 478248231 770360163 296158216 947130451 992686718 519579109 907724140 941473134 430999559 465872338 403364862 476513023 168500126 811657854 818980179 963323878 820389695 236961790 205815422 255206116 518374901 589458470 134586582 240457652 822807824 432261537 576087415 125490458 881486469 198210776 834660232 286298365 758110671 171128114 695033345 915306773 388805056 244854755 555228568 341501205 561801639 780996001 314189422 478690211 889090527 302471361 591263266 701268082 311825717 727738704 535802728 774017381 320899720 704684455 407463161 703671525 636119006 132385261 290937504 356548045 196155788 314552025 502299180 149093642 191857949 265015044 317917194 73807706 386486152 944756496 761707965 545981450 484515621 457227567 607293381 932825884 906142314 927151479 59984464 986657882 217203475 684171904 594782243 707742626 838336093 283480220 838119438 623642579 744277437 197897388 382333513 481940384 26998095 213062194 622376160 427105492 910430543 275403656 565920271 909672116 866128523 600725240 246995461 594717288 658114842 255049119 782366640 31596640 889841111 782839979 983856250 771635077 57403123 529535380 149136313 216356030 311595373 696723238 911969862 631212049 135435269 515787401 874291436 134686646 514575445 646278539 308502683 707777902 712496887 776863235 785537183 69219165 280142541 871715918 939445881 924922802 156286921 329232366 515346282 720154886 505886267 720496509 458499607 674616919 416398184 960769607 89459568 634575015 681092184 408650147 795050318 227297969 277764802 460240160 851339352 589729947 985158633 569609627 178156351 924788167 45313553 134181275 738651790 825280588 440811135 971756834 938542604 208275912 450154284 230075799 731351849 782229392 520073959 260669290 344323010 48403656 221820950 532872360 757808586 28028084 52826621 264521610 217600155 611937242 710212788 983383303 740392683 755621628 400116023 637035642 862239183 82787362 394284963 189977790 451020266 941108176 144738093 227817210 35903681 450251130 461169424 84082688 340847906 711146584 896811691 772786567 655502369 182754581 330768668 208883859 378176353 332583950 662345639 406749698 231800109 768840022 168508806 488140861 12753868 228307603 451330606 808261783 494226792 718087436 53647769 704093818 599604865 26995442 848344513 28258863 401924097 153990013 703940086 763030840 117591438 416445535 650347485 881183583 585541390 982449018 54058420 103692881 756182939 954983269 369160464 402820127 375980014 176103408 866611017 746606531 718754343 402237658 355559523 997908776 849920982 66505052 481693545 599788240 727455969 59171421 520689631 570650891 503391946 792416884 361930826 60092505 388292738 888735196 683488033 888502023 331792468 451609149 484765776 62240584 700290507 371782610 241644533 929047508 303653967 232992795 167232096 468516457 682788889 525564743 397397309 579143686 571498618 309935400 448401827 811628218 863516750 867262753 889909335 520502523 651096665 666446664 332295477 656538754 478666166 811510773 686795842 155031963 336020924 121468346 759040734 926068992 532182138 453535209 605599044 393738653 209056456 293669816 995159561 597392412 891486503 33189813 124656443 345979277 697898917 478066978 543216466 518274453 930430058 162783034 353041399 352933098 761197430 672957316 933919953 849474830 520277606 242663308 413915363 592645092 760331593 656517150 203570345 852840922 710040229 877442675 991386857 896856600 194866408 81204790 454564721 139071099 417026599 504279599 457788200 621459309 446796463 260301120 862266611 393073650 52082333 799052516 739369436 826091541 225075871 417510819 581448734 999170689 848893800 445492176 550306277 421212181 865299134 939193465 418558911 591868439 598590544 649352521 676608829 829941 738493998 807774939 621377042 290756731 139454420 288435860 848546778 757404453 279642696 42778575 447845904 496479862 511315860 996834895 828180240 716605398 738520603 635573826 651569416 406169157 49174547 108298667 337309831 576346966 393857642 880319900 901219431 382409429 78907778 939770478 327022068 873855042 288021636 105150607 551116603 88367261 623217881 953185991 273923637 42965609 889433472 145314666 574061009 852434970 265901293 472081611 111909490 289537138 748135903 494441071 325106307 361958790 847336088 307243053 509417902 668780237 454085982 127858428 430555304 643884649 662748644 244544601 220694079 251026229 254277518 11493598 826849340 634931159 532267822 65794532 288681904 20209923 468653826 787172791 177920014 321611977 6146882 628407857 753949588 345174480 905486936 826653849 156640543 432566919 82507606 436267439 210867256 196561241 835021341 935758140 731019473 799661160 456420430 454132171 395544652 507221159 809073212 507434436 826555678 118610555 662820486 407694578 503099846 292402652 642047247 290604824 930275018 922273028 45102027 788242889 384573373 406418154 458944601 982652211 151903442 530603733 740274712 725894912 12977541 241206569 154894761 576351952 128716039 734150747 149294922 592967873 61757607 51966430 501720345 954537552 819910763 404474089 688141620 974147284 896858252 906884704 799629552 203544205 563431458 13382422 831842571 766117119 346705791 194951014 292522907 287054880 579098308 716576058 193222816 394263547 34284728 940904160 173718307 840294331 141476097 185102771 103730010 474399656 168770084 489234092 143949409 214266911 926876238 538881114 44192737 149179456 929385623 802418541 999306828 541165752 114356097 327470745 999283308 220028993 872687146 867849873 943561769 967017869 13235909 137149522 167854825 159521667 756385369 996465108 272810075 201177388 382208387 415258483 792975487 142819235 185400784 879323883 261359121 43524991 76866705 667539503 530182247 356761408 10802495 846605007 677956197 566265924 239859096 822367429 752602965 543762648 153025728 562339804 586634072 111284 124208564 796831045 937938304 545235236 515774158 714952188 182984760 396872197 603262253 860195793 795005221 286596396 120163568 426685145 204245786 170543957 353448762 91313230 916720060 434970070 674836285 459497281 754360777 555204692 259308265 962330098 514466423 567280567 914064917 783165314 397894351 109209782 456793216 241143077 74945029 265973567 740687146 913989075 54852142 856528407 35484921 621584239 321750533 558427092 556168122 294334312 988587044 266004338 557275352 984457913 238418258 486329459 528791729 374977817 582084034 390375548 252434361 17793917 630048687 909636124 577643593 704411551 583890001 166932021 129667181 941636412 391354791 41355225 406559427 621966863 279851495 635142081 904531401 535949114 473907035 616656711 159448653 651002383 416171851 899500659 244781013 568036615 593364896 803035012 637952683 372933189 581931163 705214283 150477071 763886000 856940874 82352068 754824554 646420076 542429664 40947314 73753226 767865855 56651071 111904919 776184172 708426592 635991623 404380304 711726907 472589024 783261755 377124820 325480732 134395185 28430945 373014979 318856614 422171159 885570355 968272448 712853035 258474986 201797527 884720572 585294332 159435857 792266528 621182836 763408784 51018599 405662228 476165610 824309999 446654378 821500705 437949779 919245412 411174668 828745842 915112165 932996 598670720 96506860 855252564 185600380 603828793 411106346 838846023 789893488 86515686 239444925 143337079 911886396 361572717 377583092 380958251 226029042 352589637 377319047 3407214 715935251 722712783 911010148 582019420 376288467 769155178 822571558 452323249 157515652 88346774 277263170 114069205 709512787 115140549 718600664 117657446 994387549 268370825 833210192 841687132 737622050 444391019 106400270 605226967 475565617 439465901 706756804 810496603 471078932 945596615 43581451 902340079 311671736 617867764 220397912 301154811 880700130 590426274 410673685 341396599 1093526 318038574 781835495 810458759 365516439 231984699 349489739 427564782 14273438 435745668 570621355 415033410 520760978 669880752 290549065 817135196 311785408 654830858 420865615 780734095 611958337 136607320 909078476 608745132 815837631 6629692 922377941 403483485 707210820 506498369 933858995 835152204 228288311 635792442 66255820 851782336 181745068 855630158 780857010 796553310 276199303 429996782 715513654 899866752 227689472 876153047 18247442 386605238 453282275 690509029 529172503 781624105 8469536 889191721 723739309 525919380 966215804 79727100 78902986 404597659 202582207 352798541 902680157 499039484 423046294 303339605 574154722 960857826 339774971 921537869 353195604 692977353 504258678 571490585 371883028 4502466 67698593 674065714 65964085 5486273 354528739 947440772 946146607 129346781 683239986 559259439 110620964 222842029 350898836 968144763 288182153 524053952 723604426 979712517 988694918 268112595 639849806 273680301 422248682 625488222 188030439 474167270 830132717 255995482 751476862 297725452 409286652 570771277 142511885 219489829 710967233 603165053 312928053 558071338 474300909 177019300 568149907 783363963 356393685 560431585 197415163 759045218 300348858 552678781 303512562 713070245 498641529 726686563 522972534 860826326 7447036 659039476 700844855 961203599 41201545 12422747 624806102 808118201 149511665 938675899 174660744 79692381 600207386 421771803 423510874 27366054 349822363 813630699 404023948 52663265 618958848 970535182 453454904 258835813 578044203 606083858 588267946 109564670 103415283 364589255 613140539 121592526 415050943 43555431 481040956 61736100 128528078 160482933 82455651 577480828 404326202 759534995 255595893 129464393 850910555 854194104 731118928 979218662 332549982 376950621 681853425 428901359 899021649 904879229 557293486 496972799 476320635 913406268 266422449 230663914 64204471 571126853 133215665 763816479 526023025 309787401 302709424 386520102 792827963 891129985 654784865 761926173 424008616 886027494 696509260 849289850 378442686 696257285 578595323 277283108 674816843 657580215 729910465 124432147 884360443 384286737 776379675 919596892 240117855 81448860 421005944 350962060 108616250 571577666 750998457 151854600 646793784 136555111 774245267 489780287 278614001 231072361 688750830 972643545 315387065 189935781 689740491 21385894 643565061 435291161 987317963 464766664 968721249 466069646 470739510 690756224 291696042 164919501 277783128 23015528 902135054 322242735 235010945 757853392 314912122 128667644 651457297 360080472 300545433 271490789 730499374 39048127 114547003 144618635 191533010 113352523 151263950 233950407 805077845 202783674 603715665 54123763 98694983 358621608 888444319 478696102 362192913 282622474 140719175 920687225 868230941 862300331 182304638 251309600 696913032 627304106 848881425 244096762 721677691 244270879 813858622 441711463 375161061 755550496 880300750 999468785 389611294 234150072 896761813 483113188 718535120 651991211 582137141 961492887 327652821 653275779 393176254 908546189 459205559 138773293 896630695 600829108 929585843 65234986 411041698 858781984 470580371 663342278 901067330 857166774 830409635 755713096 832022962 350687612 877376427 175944740 629216899 55033188 403041979 565017507 862944424 658999495 597675781 766579060 251956994 844547009 252402996 404911634 524161293 700742497 351806939 468853942 233486658 813377447 797059413 333113430 108666670 973540762 374225579 449780031 236056979 710317033 374420610 467596906 32402941 710809561 656761804 905609844 273984812 337536455 723540625 832653328 536326565 887200164 233025793 104572667 783099259 890846875 5619697 721592051 649612862 595105134 901895015 876865515 112720505 952414021 374976876 760355729 648929500 646411778 559233043 714317523 468837976 23446692 149426746 311880802 609092749 729477738 862967933 910016965 554509762 812907151 877968209 294305306 899136187 414554085 72316556 603831294 413604560 201776112 661606051 783440883 774539110 978561495 862746694 871491405 119697735 608414014 864858733 854435127 6651767 76342831 116993735 482120366 253860308 260236107 15501594 319088862 484655875 389831458 420702270 360871391 375258756 394899774 360510745 269851927 725433845 350536176 848406705 845528172 109551624 144480539 726992321 88201520 151407860 417271308 80693683 872894459 405308405 266431203 459374955 200134371 340055350 966065216 764145819 346812455 775444128 114069073 668518291 650479997 737564589 21525662 167457317 275610751 414852660 763585607 285551273 443258539 299295678 230449425 752241947 317864289 509275615 256158998 743084790 186102942 378527922 91945332 655413150 55561201 306433533 31160349 631704756 736086477 99400240 912351872 193862874 10681303 201468413 691679003 2076528 33806974 72823318 652157941 999783524 955541279 617220328 797084876 54323995 336903345 998363897 319795651 632419641 865780372 51689820 571778437 452722038 357352689 557690337 988772572 841494738 227227604 829647596 990468383 460263442 747208295 428597159 964804208 619595547 815278017 829651917 466599684 211990183 571680822 885550177 16471842 355412986 612573017 663469864 824987407 755305826 242243107 418241975 583708316 675927448 235611187 767093918 547907716 552345007 60733686 898254855 439186495 368800268 891414269 922548794 440134208 353709112 988791792 464972740 426541272 402857462 321943422 705713399 94763986 974356543 831516051 552801990 386085623 349757357 513654231 957595086 40339594 441628808 757501157 581747556 106375391 261160795 499189214 839922072 539013558 941367035 999439559 357359297 152514102 834867353 756300059 987589620 80766749 569146427 617706274 36366886 636379649 72866108 195238092 409128203 883754239 527074540 968326468 992140194 672345045 146494003 803644363 352210876 36212670 735916594 700526254 777800830 837596782 916256272 75590084 850133591 15383335 409240357 984351209 607930499 43526970 234790044 113276609 940448724 36744361 178973536 175193008 756076245 967536428 391489162 989770716 268274036 709090240 55151464 339698957 240851732 340261666 261472599 935551715 550903888 657523238 806881496 873608200 103197738 713911317 974880745 813061363 972269025 252783148 701223434 672983543 270088408 829418813 407409975 99224711 311511039 886175927 66680617 810922532 667180065 899537958 542196939 662268364 944682891 47191287 554098873 12631068 298541826