12621
22822467 356015830 635399644 937552889 429126874 464176346 162995972 172007623 620673733 384413420 276846160 16689447 199358749 659619696 5903194 51839853 537534246 272673446 443311484 172735130 871437154 823571576 180526830 198190856 765431012 241597632 131587087 402528809 481334788 573380330 41192946 348559715 549417900 705296950 363074107 170979623 5504330 850969578 283015543 873733418 23372133 148528528 332631302 993368792 733494188 762171294 452526578 75823631 721180000 607241322 962375799 97541372 634302298 8770814 731104223 961408937 172289158 818630165 194168563 404353775 544738415 970952629 182603457 847724900 513224197 726370899 619285774 428359907 878226943 576867279 99086320 806411721 542699855 647716941 18033983 447093564 40676141 718289370 885802427 110845530 739466332 925203357 104013257 559125484 861782228 173420979 879331600 733963619 973414926 712536348 797845964 473131459 347695461 472886621 74992003 193026737 471027393 623331885 968637072 163580604 720970775 329785983 263637665 735163999 908300379 740820351 945613127 189607826 309457865 856946707 658410890 567416895 362759834 160337441 111908281 190557095 894122898 856230353 914559121 516038321 256301194 967620922 661126439 321724855 463740538 851268431 322356553 865394983 609078233 345298647 631091132 237420953 80079268 555865766 135453225 4937957 364675389 194253619 963178841 600148955 713473981 115241297 272235960 229179097 132993094 599664746 908513608 769655096 857717707 250365589 93919484 190527299 852871717 747517697 977709647 433964106 955205933 640335418 482536318 160263941 870427572 738260816 501461927 435367023 552555559 882620427 421557047 197235317 803354821 18075191 320240566 848474718 663213450 259458576 411398212 130698006 633483279 399117621 994667633 313555696 290762916 202452333 858709741 681984950 11110542 394368266 329797622 615104057 832700385 205505882 118320084 258177215 529381532 687375922 43805360 460474331 152993546 271085499 347803097 76488878 516921333 944448915 106840313 569185080 11908502 183754036 2580850 637286440 847486880 48640539 403981873 951250665 348846732 539817724 812833837 962547659 977983455 387558245 34080456 993632915 887175544 37738587 526322142 429829141 857964648 725005102 347723879 815123784 823803550 844379116 853429922 568811013 123806189 855990496 594763662 361972623 7685587 472306694 958201474 654128816 160556006 302578149 975709261 105296937 342560009 221855193 502065592 616745360 247489357 609818561 746566258 387205899 218830523 577950446 309502596 986465091 442673775 126886175 714277647 93506320 175394327 67355012 757898588 860734892 488218703 647241322 953144757 198482059 513418498 629027505 830875860 859370927 165973015 82346626 147909548 170973071 86140033 376502826 386933350 640049229 328105610 909408899 255446703 129239467 788175260 543959168 773809954 89273278 827667569 851951108 126557723 384339246 770405638 736837031 959198918 783825243 543808186 772316189 976920638 917454335 134093753 100133505 690334965 317752117 303165313 444087775 760135883 324737900 384274390 816001223 700718196 335013412 783013674 35340396 680516325 674830442 308424976 551758114 758402681 727290059 117150040 85378969 692994123 198957802 605737430 114696616 794520803 811382495 259265748 272282095 709708618 636692454 399397683 117516063 169758592 119557324 911983346 780510827 662076309 797976301 145893760 68717132 828200873 317648463 352628046 816095512 482721689 745139613 13698753 733223084 922299984 899591099 678676341 657904589 251674221 744969179 507677379 70451481 824291857 471010110 890698774 558108532 601424724 990052763 674849760 453401143 107389829 252402081 760672011 678103142 249681205 975770411 709753732 456879315 347732319 49170008 40945832 887928128 455754931 877877471 966134142 412368987 980014043 344804904 561012421 266399219 228370971 679581233 724373467 472495939 703596500 263035069 436033379 64795321 808237202 281257941 12607925 931935798 482425327 728533632 777224781 999219159 3927437 430659920 718242122 92039293 709151024 815318767 316359349 417394079 270555714 438394144 408914002 815332671 213742316 921368687 792030133 837294222 770679583 281670992 440714372 146175662 339916141 824231840 923751773 259864425 92032126 601135423 310993704 474612575 462040418 641139837 678940619 15611271 957971600 113689328 291048201 136427956 50763636 842485904 732506878 244371407 333159520 902251271 46327699 834222713 778425549 802540699 718283224 687948577 887048823 781083761 979383754 301832481 557174102 546620837 724691587 30025492 33225368 806215966 801807624 362561072 236145469 752070971 150657979 804133178 296482054 278176421 599799571 384147739 28723325 503477726 267457057 673565073 186596483 714850919 654499193 773916721 513110511 114357354 357884257 852806526 691812680 576825548 863726260 562304918 870915377 114443349 426063094 506046925 575144596 189092182 320297722 351398108 796948708 138506608 553046968 688750678 425336215 52416787 183882926 757831791 325530476 567386275 962755173 949308979 156287389 661600584 748239982 28317992 988306773 379940504 381273614 525768181 746912910 414449588 995979730 330856677 737631404 593141719 64964872 610191899 75619187 378733450 755208924 34653211 179123258 208938368 422864053 567270820 650139410 276310752 751525613 474212842 166248230 459884258 120004422 577340530 226750785 8093628 183342705 914745944 239065775 309367141 435688253 737199424 537155127 534822998 51922960 795403515 564790817 233344982 237252006 825656036 938503789 310014892 291698125 55521383 728170626 400643645 47950567 404159542 821892549 465937776 509129011 389321366 517620111 255845973 502341796 532140362 378519065 400544130 859796979 534716670 931638881 617227632 329073546 684955971 803045291 920939065 534672135 803861315 29589983 753682420 400025949 832048134 504497738 456265616 543142617 226128134 524660049 352207496 174861582 695191033 102652532 838487039 570480206 472985940 420664820 326433990 297903 426342738 976044925 149022022 217870931 225321375 9414902 185746377 68922389 430040380 84568405 524967567 556571922 633070398 945929056 237045234 566234153 859656103 655163634 540644870 471131302 637696744 574308329 610334018 818715394 356818163 279869743 563364646 480370316 771019401 562593238 313072964 133346459 755341314 118581648 795654609 6521478 434422709 315767498 458310421 608165047 94332464 547960160 436331825 814256660 523052379 126973164 984235989 842010912 67226454 477302080 67860728 458059966 448483119 153935515 903953736 556102249 407505485 370374820 897116028 963994226 105712306 457490634 581154534 163095570 785696446 235463723 730095042 594500392 282476593 603934186 404525419 644925948 76755103 939071287 588701790 278716999 91302452 961815910 332398209 254570649 826804460 682897936 252681457 761172101 914756242 499203281 652518707 519457731 9012250 202178445 116743765 657943081 485350555 949259470 304906106 935025283 375259762 639678384 646828863 651623017 865989502 712983857 637424066 754302117 278509653 557425233 720245350 797110138 189518537 660600974 757509184 41156983 23229975 342920835 809355445 926245402 995112274 21508286 899018688 809724341 373266919 285920411 87969070 136827360 873231458 534904729 229575657 167344885 382541858 478229824 418795307 538158002 169740976 780387048 235467354 521256469 628173251 643373185 951559094 423116302 469806154 849381142 715631643 776106456 818468796 500653220 557650279 435465955 123302184 968215555 593186292 550389612 693658378 972188210 626810562 187628442 53822285 282196874 553157698 541573818 90735645 36415794 600817775 358895395 849732106 394709782 380261822 390941570 136402705 347045422 676945424 166430241 393771740 926134889 91180703 88510125 618875145 499628598 166148751 917971898 775279815 160060641 518955277 945515676 489480856 632349171 925242624 790197747 199085088 664608102 546426524 14221056 865927416 11115695 330730138 578981047 541509246 559792064 469324944 828194767 370224957 175622652 819871034 816149703 499105500 826156919 715251675 623823909 886098537 500508565 458665906 475255325 721972268 204503132 255644986 951216954 393718860 147199231 875959717 455899588 453180571 368531898 406705606 787613165 912450364 524754609 155731074 769053214 67142123 252852404 537118745 648707879 987232159 91349693 742439546 515052488 731147009 248560853 713204654 894372254 532607214 726054487 867684067 200637435 231483333 776939469 985665776 822490379 387951863 894413285 9234075 300837930 821716785 280131892 274002055 723159190 609074934 707071300 850092226 750895238 466775793 434338662 994112666 223743098 154438739 207650163 219846899 776818293 428464971 270208757 335703581 688289936 778718941 153218952 850761695 292669719 612628015 963118766 722714172 821055975 690821582 946881388 126611518 863538858 613398294 34408580 721286108 357851056 512754138 907598533 481498006 453015545 30845889 108825609 642858069 912436609 390956400 186310610 723104944 437788054 986204583 732984300 541603393 998760979 889215661 647222491 611430713 588121724 928786875 314362539 672598421 937401512 6900863 802006287 85856547 182380480 554816388 135793414 691438773 396263709 68516426 249474492 412826078 674191480 926219901 274749460 863930985 9264818 139666924 150730415 780740155 821867044 542045262 853519135 160770835 510792528 564875484 123826743 460623546 237811831 481324253 28758472 447469445 96733207 894652157 658774867 904378308 881189277 39168044 792845173 508943279 385964284 953850646 855887298 530160798 215369489 403175269 275617996 543961911 189409015 120644932 96618538 496368212 743091052 298456789 89505665 923851499 779297131 766680462 697375382 583242797 668307548 928853301 209522976 491389250 350750527 779993838 616334241 115914740 831498271 213089559 426087383 116454753 688551860 595217131 464002733 377867346 113390681 66457072 966428730 907398121 401239785 760227573 201796220 103774498 642572914 591669038 7576256 431708843 343067244 489908998 732172311 593421651 870512950 60966749 220506226 861222808 972701915 75415314 808911654 196430830 339728883 285040241 129453740 228643208 53932704 245421943 424964088 506358038 735624959 954096954 636166494 38671192 832642057 572393856 84529557 692314425 513236607 314610461 859303442 189845968 736500959 638698889 566944549 992162059 642372067 249735287 14432077 256105238 580636978 198198088 756303163 219973201 85769286 331584526 970299777 48705989 250268805 259690909 585733756 939399779 207529954 485095354 192868722 174831584 153448626 2102913 569521553 660408426 883948026 474678480 296714964 171982372 253627404 805246041 335544419 432282588 389107253 670318208 133319502 844006047 47938320 12454729 83621815 847449531 526839884 674298290 225758354 730690676 748696510 54194161 293747813 221806775 608870664 59200835 731039440 840472831 762768297 926877767 310637756 509916473 95101352 810511333 870461902 260337986 743148843 420687696 479411714 392740232 946519506 240359275 285565869 194745293 547838483 556585798 213329124 115776804 52755299 50444026 267579600 377010622 210671929 966948448 84472670 670515944 331852605 885291033 850459775 578388103 215943298 886935344 667341709 926382125 5978067 653160243 675907937 214620620 662327052 699754537 909367110 121105973 842099091 384859620 488971501 867023933 976054279 333406231 448924738 997948201 984379170 330968386 835300861 653132026 209504046 262014017 166002416 680432442 240526992 363565182 974758592 637614539 107935943 559265244 742140732 430803914 938551567 575895982 602454119 642128267 845423578 732440759 522729062 860555133 196609532 579472379 293190931 262704741 123914481 599580268 523923211 588734140 626849055 243845891 640083548 766442356 933932166 470339709 226368338 371606299 697142136 688835141 306281513 781921877 684358371 918785564 275216900 316824690 210083318 568543859 145533095 91623900 224901204 340611470 360452485 926088170 473998888 363767370 467019698 905362748 866143177 610075488 680888939 143788783 623566402 497938734 803788061 827467506 62474772 283064863 797931822 950059765 970391978 983874555 89228159 563588213 688044730 822865053 147823230 887782868 555515512 806591559 29184837 4339090 365013226 322036937 654063928 93194662 115069866 594213181 888160687 55032266 928576764 953721669 257678974 173526624 539239735 699722286 771742120 589206330 429289362 477644252 848461818 825597240 349360619 330970823 979241322 103932064 113135630 683678282 755954258 274148902 867892957 747692053 368451553 517987821 630336375 583320160 222785725 899164052 439755274 388919225 309246162 571585597 743713972 907656630 33488678 869020736 471575868 684519052 557982324 476566039 820689215 13841256 265280606 9447091 809923688 319994416 89860563 846579315 539999407 205543546 974162911 946896720 381221839 495360756 236520014 542205871 216567057 508366887 607612716 838819412 981617687 808427197 317029885 810934728 550666202 570645425 432534116 159064896 293683448 847944337 999113710 311732534 949934714 789321269 349438668 719969087 819761368 421493645 104410155 38373249 409825374 167269846 921552551 751623828 585654475 531085369 241836626 659015653 453251096 612273582 579331377 334046432 878022391 77224889 102612299 101618285 550329565 355446395 137559998 601570653 606855396 449635199 626300352 62602712 345123002 970947430 313824645 472267867 50883699 930413615 308488474 920211920 567370837 122680329 36037231 859944733 78566303 243928000 804937190 184752972 640746605 153506309 857876385 334486305 11706851 850269084 678785477 603285618 228907 551294461 403965472 196468999 977866133 562135692 545873970 38336528 412475592 17384751 602125780 222576550 262927274 40020543 862626405 1035594 844034255 293854240 637190920 365589063 664716131 874635729 279372626 337542573 933099085 134014409 698181830 70832648 667512791 723908758 825472738 170978652 595682950 631291708 595028404 60423805 380554676 558698149 652415752 494734595 434219825 839864329 585002578 730015410 748669816 251119540 503898156 137769146 637416717 423562950 203650578 599736471 579670911 653824423 569629964 327181487 194554573 72631445 246047873 545081000 923250594 516823761 214797553 47711007 643383555 851705137 509995366 769551770 576176574 403711219 126804543 645266343 765621725 585253567 787224781 640859165 369239466 316465013 57661972 48843406 973886302 180162831 152649015 372482728 258635810 603034599 574530351 421029066 476120897 115180687 340675594 16363449 910330167 472468111 794545163 608545421 354516156 343576775 190999545 831444597 139815270 29606179 474084233 525052031 160417879 529809682 947787522 486354175 773636268 678386603 235621960 629440110 345840793 309201733 480907882 454079607 767704741 234893243 639245070 660639377 434058822 983542072 602619770 274514504 51809598 101535090 710088646 648213751 285801319 411496250 297274661 148093394 43876869 138484319 279664775 701817304 492588428 562176322 283410179 817792576 659934548 108443076 553882649 985522054 401472671 895708732 148520877 673346268 668238271 128628155 878940700 185804068 392626323 804754593 766593576 89091254 941368762 863891739 416156911 392205119 973706394 326492031 419040886 270775629 522827866 469031433 611131059 850014221 455491488 681035850 438660720 194991825 252957231 573760791 591431490 753732786 49042543 396047745 231046090 887709794 730471994 741124745 911798221 471693568 471354010 898409632 101654707 257397719 792907108 375437012 995313565 244806599 435151804 776265010 788183430 669597746 988923246 160123216 115986730 309411642 117731166 727400905 786269019 560902730 44517829 346869311 553109824 785477650 847022108 937021751 45236379 371477564 317951669 419559206 574528054 385889238 201361098 94102422 296227033 57708172 222614675 292275956 674684003 192512812 290523359 768974717 490552952 509342507 574020348 865375589 49308951 728190457 681956714 180985552 897760007 866147516 169960834 74731121 911107377 176059332 956454998 730286820 559284540 832453293 663571174 479917608 355767154 471648504 836703158 925139222 505487347 776782673 514497567 651774670 485977086 579571621 416291129 973029513 854171860 513149353 893394377 448983418 925063924 635949749 930287151 224730179 544144971 448282579 618133851 556795495 640382796 225530673 199317985 882655676 818175710 154841427 429222079 446073748 24000914 304107452 754004450 171078715 872445536 347614292 752849647 88064660 694619102 695466042 431963242 25831902 131716446 544979954 910024550 989375884 769754741 187484364 619168931 956344377 941013184 905179920 13790247 463627511 30689680 739523838 867827128 133435596 907052653 724343097 174761804 49121417 107084187 128629561 413856567 226653619 570225017 28405657 441958456 514189032 588386179 776453040 537228665 648478793 745668485 118666546 196068154 438240729 842259527 994395494 435999909 290706617 131783620 889010046 693816064 940199074 779393988 225405686 925853674 899582957 339302123 936661102 766653769 305681789 672075786 263132227 856901786 174581948 770474366 142353262 454956168 711309366 671687276 293423413 740758170 73808086 523917484 155140341 677845423 744384062 81312656 831602190 209914686 890855624 554817297 983826557 959362800 845026739 107353417 861325194 518608180 271193961 540880541 503497180 620039286 318719392 21894707 529061331 882366917 149382291 870171654 138732844 962005422 701468845 417833703 990706631 153536458 387092032 801857581 823261619 449530544 982033179 968397595 409287221 578096020 876556687 538015542 117891788 74242239 791033146 31575812 88018459 188020621 651248501 570182105 956853840 269502933 637304179 101000526 547505708 635519537 258724079 422770033 812174895 586072853 751970861 434913957 809086071 646375660 152148521 349509888 39346885 606181244 28268055 822863951 720150018 339163291 783249604 953073883 887689699 539881333 62664133 393505413 329915919 737056528 704525373 123324859 784500100 744438102 757805476 91367273 898478084 809927083 287882503 844493267 423414762 894447678 121393089 172390894 478175561 548658141 111744588 339874149 164944265 739188843 737448112 932282609 202319250 493186445 629873575 728275843 467910057 28974154 978770883 233266761 33375657 228413461 223790820 723748956 588499196 438982807 875072354 108476384 191488028 294577815 321466751 792361189 457695896 442717097 280198150 312969660 163114436 434912325 841212707 681461762 985400271 972450671 286410361 916536979 50694470 589968147 813072281 517162615 355315971 444204730 215589297 209369261 194408840 558976177 714320680 298790187 552456070 386702900 351947605 160780484 440603366 684619823 927366125 170107266 511120560 861325765 440515634 326379112 867285681 883220230 697246074 120392681 993366624 936859729 786918164 747734732 323973712 921421895 484401846 837624323 669694800 833251888 888619054 843888764 581436916 960402973 107724754 627882660 217936242 116563671 976512967 860112122 541336971 325486357 478856247 681418488 569110296 116234831 362032606 498201423 425236708 856834184 831676635 923329126 380879646 833982110 741754361 823986496 827282606 128006995 38222076 727057071 695486009 212661104 492590979 62376557 4412646 6919933 6280901 10956784 471770529 383350835 206513160 260943107 281315106 195982640 163330745 439300128 897411369 115990217 770880669 77339667 647244670 98191300 444123731 900837239 382531808 161703295 366405881 532676664 509966119 953084691 673879899 798036058 901728995 510354347 274110245 664582474 436894965 945375765 368351245 34431326 453197 198856565 675444477 903026587 411753543 990128818 373833235 325933858 12075326 608440174 737265514 438592650 325749857 431794952 998463375 519033322 904061212 773702421 671905922 182090547 57905111 56727295 731236432 797021611 68519203 329385618 5718778 71738045 722288835 518512129 347305583 309488755 157693837 715116222 146214676 433521175 833340332 594384499 270457543 16762648 257301615 805999085 144709241 318167207 29971902 859510376 660000789 250495923 427501147 452734405 560977044 725455656 507540124 373973099 584632180 65894564 155043373 107586005 49606954 990661393 355280472 55936167 267701730 338298054 487338124 374444096 611820889 424091501 492045899 878727581 250163352 999257665 203227510 199850032 934386268 54085112 536372796 637001473 308796863 473459772 625805377 499922493 30626204 111971914 54871566 260417272 287345598 155192529 513628777 516926153 348359651 59906458 13314344 536473155 500571821 594284455 720433592 189674508 433533418 808960029 708512115 677123396 766780829 822996264 408746212 203404133 758437956 577534933 93003230 687267375 9423818 90190155 355590816 589495056 885727437 582591999 936945799 739571788 147317327 461311286 407829354 240600905 986326481 951889888 447568632 978761042 591966815 277457277 431895641 520495018 658257270 853468612 36596338 223068358 795719957 975374192 243326392 35477301 957297809 307956378 370926008 842984208 697192816 398671863 110540763 150252386 766402450 615189286 139269819 791511030 58445931 245151734 92278140 713482993 92774713 225962847 568455502 476098113 92118868 947348201 696030502 326182530 570984524 989134688 408688163 157564113 805887757 749123158 962541530 451342708 185049527 572653103 691747924 329015850 661422248 581469656 945173389 469598444 119756134 142054525 295944448 941322942 744530385 84797389 95922414 420168062 292816121 149534816 774166983 320026815 255273313 200507020 282780568 799333377 754454617 574387090 998908203 117476928 450842294 542504226 166399556 916671682 677064760 96466374 835988467 92348828 794094930 486044329 278194069 890483748 33875378 310991473 327653246 879536388 878565085 226394670 790676792 851660420 886880083 39494478 901978425 555238645 970436537 727017961 119865573 857681741 816821150 904836679 321849318 263569070 683313019 113165563 667498023 384258520 175434762 214013712 118699112 510596172 944064065 836389843 457005303 445255403 485884749 541139932 273273084 700171612 169635259 524727886 457974729 365847639 721043486 922563039 764620117 509020241 46036227 638046322 262583245 792245519 791951807 379422833 764445234 159622336 704056024 597784320 967549278 2462580 601567253 188831033 856740806 339371888 105594127 27313586 712971635 923989240 374010009 528683405 848676237 774637516 584249069 52703938 778686385 130222113 44031542 503012586 820577658 351264582 786488815 75023324 351747331 426911408 51619069 114582863 288158966 526010951 638803973 139175328 277448227 168704848 649836321 144608196 679254237 931994159 915621537 216772230 822832164 964077612 116034490 182467706 29949174 524734887 280868841 143061232 254753725 374225543 243802460 352837682 327903151 618359188 746589861 35302892 523823523 646827908 448098884 170514814 578742599 860672267 261579835 145015296 367500038 127015052 939670465 969159420 212072533 145814018 773321337 18114900 451208800 123216269 980984629 740603584 967278257 332916559 466850108 117607233 17349335 55650307 197580240 359416497 977249535 958172799 280124923 418916906 495164952 604565922 147174553 367586550 457661576 819880285 35588307 192174853 697931296 418081039 130162896 29878356 350925489 266979443 512130727 283939122 101879749 840381411 83687556 954928689 940967894 951349152 655896708 955676429 579841708 1637403 22403551 89993668 428693770 995034795 101329741 70464032 900860640 422823032 660743594 646343793 322167031 212015735 850042164 879580472 388870561 154323590 67053264 924892763 572149730 372501793 418181820 425083045 672740069 227361885 753271106 852526601 174192315 596697131 243996732 322989906 148747086 147268446 798409483 32418854 594370488 659550149 533427491 52309662 171596829 152192312 463589579 953344984 225389908 931459716 47541056 87178537 148168281 571079727 501236738 309414541 432789197 121726240 897670435 964256954 752397708 214260143 311489346 662487548 194424420 690966310 352157477 834702641 832432520 399791852 420516341 282101886 147338602 385360599 862714808 59725686 614352607 501823192 389027321 108137327 813620257 136887662 649246947 538936295 98322641 610157439 779556386 693018342 663718515 21947202 942168737 338306435 622465523 105721875 35360325 742880827 789242244 624506146 954558352 438895081 505187827 545433079 368282911 156002266 145757749 821971601 131361277 688532545 874992665 727312908 218621294 550268288 678546553 820769936 723354129 821820440 308198254 826554168 600126722 989219849 172536523 200780080 349114148 97663452 650608330 486903067 930836873 931996706 395262803 901812351 611745595 472246278 136133092 611279356 405227091 990479300 748677495 164807158 306971558 3506330 539020153 702910167 465074150 736531485 340658928 310589654 513362065 358891657 541668358 649087665 85686511 105831791 560719254 552475411 445274819 270587518 154463130 429750533 659081456 216714444 76770653 647279519 602988336 753212916 523776719 348060305 606386393 611775307 623981718 241287726 678832070 137351008 31702 270278865 574701811 49651825 204935695 663128843 788349873 262829830 922627157 775463554 197831082 5741575 153566879 431555363 237812763 695910423 136228967 297383464 756565290 775264289 680252332 230043342 654367004 656349544 302450641 744396842 832546644 940935544 889719335 2107097 193378090 780370289 770157720 480781685 599427012 236577198 636522614 13322106 418129052 469799055 223211340 442243836 100677696 523260391 670172440 992961258 690869443 360223989 823663281 19348154 409430598 134396141 176514817 142532623 35218076 767465622 755603617 135879266 287169187 648363745 885990171 330990126 454339221 752386422 680299167 635763905 49305284 971389467 225350904 489503159 561844330 487212367 851284718 852046003 137527449 92667508 437441115 176002623 430200611 651889561 980642145 80523449 825953893 142264207 944282298 556788867 921377848 594004261 439224438 217426281 912787493 297869777 310560628 434835688 399297708 3611411 144443924 81957118 94788354 77364117 340856131 853022639 27345915 214433930 59924493 356369991 903766496 813854329 834065852 942919211 875804032 71476712 134993801 211095625 973642195 564069237 310830909 336311949 971118369 667079148 419164842 834122134 81228020 895464704 312318692 90593239 285869710 371089717 700994795 781581317 45096015 845720801 106283656 638584576 201185942 104812339 244288968 352527444 809259386 121203947 919266782 585753914 795093306 112973362 833625506 34372613 463347232 944048198 595600031 269907425 453540230 122790964 798111711 261037923 644232694 129859454 968432396 229239140 520176207 510143685 470467648 766657387 334699054 376984258 603458408 503551648 960659261 562804771 989430188 521450485 620980434 23546480 831094507 296244963 136355158 167154687 580044497 982751975 816631519 606527202 761721994 341685023 690763269 597341729 975732065 638985138 831505513 727878099 308830632 777694112 869017362 56678516 199160883 745923655 365632608 651343083 671424331 986624387 60892383 700599595 454754766 941756185 532375063 663046819 92245640 708001412 479886173 167942254 873252791 392415005 713372455 80340767 887894321 222607197 559570299 886183291 277230762 148576494 107501656 994578548 147993640 154303275 30190603 332634605 16927182 301447140 530341977 413821299 494226148 270963423 875901181 886701547 302083672 322900601 397511263 412105249 888613238 978046248 940875851 869475470 319579427 520428641 213456057 95230009 391648490 135528520 919633623 341473134 830483508 584351257 240005616 541916775 639252092 705794501 61348623 217979943 936129153 278404886 91262026 986032716 482515383 390200160 389127029 254162550 149087259 713380991 48832721 805496158 43320582 397966074 952325107 653241184 234456430 718174798 806316366 937287704 602356104 383107123 636119148 651427310 923352496 965954911 995698251 888532244 733326626 921755356 429808646 999217164 563738732 820924742 249786927 714233668 261608318 618759641 358975700 14315906 659018678 254850228 545274473 328788748 668522569 995963033 900467029 897421179 127502006 651143533 903871213 693748263 30621578 19462298 800538738 200510187 677676585 845705352 425418540 465183898 401296755 677306509 970777118 687804243 891056974 586652256 233223722 324436448 88496358 483586272 760464722 549835388 578977175 337198900 854409104 796914039 323963386 341837850 930959046 724357045 267030457 333990593 42877381 97233460 84343013 276952013 149455543 116249691 894936028 965896489 941839486 758346236 55874363 623696272 670148266 579252148 461551215 565456247 262176561 384426245 991365001 841303877 375243463 857531754 972696217 117818750 630380674 788405142 221446441 660692683 971547014 881097014 995055441 765050725 474317392 365131716 512867739 569160690 50485367 279026361 800119995 118581389 10592128 729913869 211943023 928180968 470816202 294322202 533825816 207305736 125849347 727848771 864131910 162086620 942476361 563579761 682836396 879376013 840165939 157257920 272948654 821986482 616089464 639225002 102593071 680392130 522350158 859319927 883970872 291379254 805875700 226285461 259739095 241349459 361686683 177932811 733068637 913011250 438033897 172218757 5298876 719563541 979350030 575587557 550984070 399444893 251204456 56931606 581969090 871547154 30760520 987680075 931148892 973746646 299585861 744381636 688475835 985638527 367531135 289484235 55064272 703388472 237327722 249919173 636587876 806927866 187152985 87330843 962220483 906659026 35455426 3758232 598446642 176667683 89524767 636927710 217236042 541106961 747869549 149911924 302331664 853316103 632516253 954490787 306516455 85196089 440353677 468005887 364124164 482067026 787871824 442267635 129666301 357139630 962070351 728739653 791525292 20092635 887414394 247898464 23263670 454091251 778844027 469782558 927083347 329075900 322879155 553405503 207874015 939677101 254973201 912460776 827902349 201720711 991476369 397171087 961715588 364281264 283274895 856929705 891445392 704292454 633580004 292314701 818167381 149617814 687369682 640581369 818032766 622441812 158033268 600816105 781148671 955544549 402122530 123623154 889979778 763302317 781420577 972918707 257192010 836012251 131721014 276843673 242350972 145670070 635446805 758547164 600433014 647483474 216735936 139300084 511589520 978146985 531304767 159680144 209775847 833489156 71882883 185538301 933551266 84200245 233743414 156708689 42269839 679185886 307938587 981426962 129013006 752754559 188993921 260135317 992703915 63131106 292303652 863008508 712983726 77382219 131568535 604310489 488079913 486468302 892645925 702480081 947241238 884661933 68112624 867449052 64309323 609543440 181389698 449978872 965196004 446258783 519457790 567262778 44473224 828148146 134442870 149988403 745257244 573914338 596098132 727650972 140124947 237809008 435515317 127106223 446068063 362171850 117537890 738325677 569331985 49096273 193427502 591698494 943376406 290893968 17144500 631683140 358147474 148540691 884647518 411891974 890692829 295295435 870663841 554932054 454723836 599314731 118712751 500041989 826107764 205713561 720549573 33234850 759821403 902057454 35529774 172883543 486253561 23138970 393578293 300434274 543508874 399454064 365096137 786669744 352069069 661542732 769983621 739549817 424110787 178999046 323087088 508450897 305897387 706948493 703922397 46984054 84654971 476348233 345289550 823460965 691641615 226311856 656501733 88063218 539385244 825613960 861831385 522269782 160697480 974986222 465763086 730301611 368905981 772116114 86288025 410382580 97729142 854474500 967723196 223036376 902824012 808663368 228383922 392515992 878138396 677578614 217146691 305583629 123538051 748895714 584410489 415177047 154279247 636005285 524040082 684189765 173138547 783028507 407561544 452412873 988929015 390918163 485623091 49292907 752894039 396438071 301717369 337501715 856047154 119628546 472913621 711841912 601591848 674722701 659164722 504853324 39278314 495702897 76523234 319992501 577511758 649473454 945956622 870668915 696171032 211096378 164237573 131537095 387245800 41128878 603283085 411182580 195949048 751483113 429527956 778196195 292309443 185086978 51218805 282952093 742911748 552998012 986665971 342394080 694605750 923736085 83727803 825982615 517791860 81480920 567365049 457161531 326885864 849398573 547153274 155779436 945090940 511326753 456967746 18660721 733938500 278258650 28643084 105363159 175214524 456536042 42948445 126822383 97299054 783876231 879626655 351107372 491012982 607187184 48104191 827424643 240728390 210389000 89244521 263871988 132960607 943880253 400785402 70613910 602636414 682815318 516918654 787667749 372783444 606094936 652470323 264460714 884089744 518622412 580013328 662686663 237040767 629468385 79502513 570636963 166561519 404253622 71228021 782831394 249203213 550047099 444094425 433508842 839889809 354495315 385744459 401131180 414544626 284859925 851038424 943663265 334022103 7471334 732538490 553774209 891061643 732391450 241381270 104487203 292376497 688485428 46094616 858397384 130798997 742683550 586308819 838120399 80166263 899738145 285183567 679881101 787056975 357793247 688188407 604212645 335395779 597906557 142517472 855652870 424482089 232856122 239268970 990572879 228526674 907331989 533702083 738896409 682996236 2369532 166545536 981881555 535526546 93426349 347296274 862565012 692636306 187427332 599673723 76854651 117093569 358874140 246621539 217446818 814740674 118207770 499326974 993065517 244330858 772713198 374207722 391295793 823892357 458616578 771682797 787366934 253220527 788659196 970827867 70147222 509152668 171723612 665993695 989871222 876798411 536966467 548910869 618561675 805243590 649968479 586588733 628882859 911239103 251545453 368094337 322431238 192227199 665604346 243969000 809484322 423052297 996627506 526059082 905275122 321524640 856017725 944561177 752029344 613569186 69113127 924510145 266503103 986111570 260118473 456798107 789764335 843310613 687379029 54369795 92716539 271117037 570985710 615225767 201450590 932443895 113302460 624744870 134833064 401078207 408511577 640336427 151819702 82872927 684137749 487209795 995486503 482156680 447760072 944860666 661350785 418867235 309742341 105001280 661289854 486392050 512497948 291968338 67860335 99453087 864085150 747480317 371789766 440995890 171347598 593743353 352052967 894107089 461451795 590934844 36426687 445178818 318818316 205649502 989338494 921053894 766631183 885173745 859851734 475117007 997211158 566878638 854852789 656392051 476727700 420501810 557897550 592638157 540926045 315290418 144513075 840144123 253002133 467135818 654474280 819210057 229740547 445436628 65038179 155932264 940707219 909548864 508247045 327174638 395515570 683600061 490163791 786086853 676946423 850291747 426072383 108225144 550159441 658525403 442251695 829332738 754679969 612701137 4630477 675069882 985822035 318600235 762823205 511426026 877011694 259544662 629872822 632904724 30165005 47921506 314486689 421401160 496529011 872433371 154614561 257686366 912446233 546568576 409119624 25370330 246572559 950954250 582757226 751528300 359820075 845059537 429099082 843350734 863365544 809139964 450044088 192853863 178761971 377625891 785294396 126341564 110478721 129712205 713611746 907118113 461584157 560197274 216785133 892128213 503030888 830036009 952489895 551149874 581973384 230167226 673823858 26056157 528527889 833616854 830136251 260798173 41797051 536886423 118079091 649163484 14961914 154547836 28994271 899206608 315364696 648388834 83659662 588525251 276920134 206528103 181706038 333176540 528301304 777002483 165696156 845581429 479678467 578011209 72807626 858304481 143821242 450933061 81012773 834871029 625584847 922720452 842518265 209747562 346724804 49846380 377251973 36828998 142287109 367408731 254788778 884160782 122296514 546856864 641399846 446101781 504614867 341432576 904331666 372180332 75906021 252734712 251491445 203705487 657218181 762656395 198805202 204636158 376830877 813670432 16379205 564766121 919010995 475878475 303528812 758093777 859041003 37494400 783650171 24859618 657990455 514353299 351812004 784323160 3103781 476371074 784661149 726928239 531195305 57271666 360389309 629915307 937710052 996897688 68922721 327326245 150565088 501916968 255080579 176741874 388179137 9842877 450519149 84164429 753739247 57803935 178706794 939660213 37090456 859328479 84452069 594841843 144105862 580688650 205377657 673728340 280736383 551109511 533165414 821103279 319723375 340796871 481268527 715726671 66555724 275548753 643774367 211974468 635175178 40117461 859666405 818169672 514690970 807475983 409926537 755843723 473275500 369503581 347147973 778831556 31650763 304285069 843371111 52593509 566980352 378084256 491662293 794105492 725940742 525753785 771462924 819002372 144736659 872071911 227841077 760936779 76901491 882716370 760891643 590770246 948645709 783686672 541888324 820437747 321294210 908006453 295412136 834968159 897946272 694699932 676488479 615469817 785700937 193366816 284389971 306594287 36253115 594592930 650380063 588786774 269965018 326022524 996395474 619328498 687364090 937176797 208683560 636977602 653402104 693004232 162878520 894944158 379844184 24863004 189332845 635106582 571757675 899822094 380603315 720073740 926467245 199207169 156889767 5137482 636715014 729887062 269479846 602845383 720162019 937187708 600447682 396159625 473287393 710875692 787519623 534609689 282594120 72334752 293433624 450534825 678725574 601227008 795610908 181958835 856240123 866976218 523858468 144289213 674477416 709248624 47847958 282125736 37012993 128509803 496530934 440114769 526874069 434330910 801694985 503226427 323067986 514016161 403727690 833524281 233214953 784400931 517755298 279045285 231074054 395567767 194649725 144240735 342059755 724613764 877420579 82065933 711622060 795788601 5204485 187443511 648108495 75050034 263440563 184026758 557455357 323370615 416815728 42248611 642174284 300766363 942775671 256413699 651263978 930361774 846496597 57658569 312728285 570876332 819605894 316302228 419629167 979581462 223770458 544938437 557241856 587055742 992244229 76828376 352920512 619192491 513924691 268696913 277038684 289727971 375504156 846184271 101238714 569773499 225042784 57976819 110988043 261523672 81391767 255728203 495458480 634083790 362244132 719962900 734917536 963775612 898802500 188452536 545468904 588379753 697759881 434556462 53069490 422443705 150372914 219684230 253918079 139233801 301120113 890256921 630140359 572436583 372984345 613654494 985751202 26938266 828609538 800472001 219593968 749468729 560433148 930562699 440744928 173252224 197518085 706064661 970284201 504425293 586255430 997063261 897928063 552942755 510994522 358387517 229000608 837955325 185454475 981129871 553098210 751169898 35765785 485277347 285669969 501801990 259501618 94960873 529828194 821423945 344045346 370207246 608396552 863060391 972758234 527153647 768183891 748510293 44862574 570905992 442523744 441001699 836222349 746098157 398600670 594982987 265136949 313402668 379661360 7400718 188042338 642580233 664343304 276715178 758646637 387327326 158499846 351571096 293698281 767259978 254988310 166663671 623317906 380416415 818786371 481292415 991175674 865811431 595651086 295946574 835411929 503438114 79317287 631623898 920411344 302498826 378426425 960776104 191423466 667876642 563607069 412341917 294919406 560503462 257343898 116219071 450644652 201279556 636972970 104479567 506145461 655799607 155883479 878332746 581411694 240089404 844443325 959020641 765778394 518245089 310141001 108431630 376032118 199731091 159205453 742174072 203372393 356074401 170493126 756568029 497221309 42632218 717386696 367220155 804405909 809124521 11803054 740820392 949860293 30480558 752129153 124365315 451340968 156219899 306945629 466378529 773441239 865468240 249935893 154311791 896979977 274931565 998927472 102562490 948984428 832322903 56213421 766378462 511363292 804563874 366614299 538595030 398759732 405428385 372842814 19079747 348243707 288415923 371400866 448072542 63258736 483697432 14486202 740872370 212513795 791843524 865374460 530635640 252047830 958387610 684758335 202054317 320746210 810337939 549182378 740072877 59058691 812885804 915741670 292601929 377471264 962369142 834161239 3574450 504501675 31391546 586200589 719879635 624343725 753141514 7686284 923523647 562978117 381779302 735178697 926670672 43630166 261969884 935936952 645481688 789880768 404608131 177144378 103736790 392526437 348355363 43224924 552478936 646445228 166986088 455076007 701908193 319106006 392045644 663709148 960382046 525402557 938043326 872051381 367760054 402765285 31742164 643467404 655250525 131167633 644399640 932164922 15905184 254445179 365070278 325111790 437663088 156397138 201756197 505501297 495952425 662041714 719842776 664306973 25674998 958303838 932357383 44237416 987522932 446611211 339480078 287454688 58260335 856346635 53105937 31307800 701070431 309270391 627118618 226390730 951628179 481183142 904893252 171874454 846462918 750471771 554050109 959008987 746819403 459644340 240217664 192149997 678199472 911092227 622198565 736778716 14135919 429853980 372889924 714317834 948239287 367506655 371547671 260957148 670902823 563177569 211507988 638307436 86064346 444059721 700214615 305000004 309739833 717145419 783790349 554150336 907134568 913829201 476883627 370052005 920444360 985941024 152794035 257771088 17895833 909698341 73005494 922638153 251810308 95071520 717543510 851086662 413743226 938154429 299638976 966384262 647032839 526112781 222055935 715952155 69531836 676977838 444806639 608177731 963416273 607048337 918825265 23626811 696565175 737801340 969446561 234650249 453901386 52858959 523857095 159711576 433465643 62038134 739028153 205811783 361363763 264636065 789508498 378089397 8854940 34255783 191019675 685017521 172117262 477129281 735829135 39191089 267628287 915848494 601356902 973872545 983732019 11742902 325612073 368184114 483172428 113095834 578406897 602179938 289136208 295783864 730119029 559943557 292837447 29746366 887516418 974029362 590613616 785166708 320637557 3825847 430112632 887797212 467120230 641589211 901054207 208572468 768137487 215570626 15409323 475732171 163584844 490970326 191437725 498685076 478460151 263767070 797842561 335653345 825299568 893077269 229602436 41857648 914936078 259167749 99673623 520003555 669078973 537605779 153553924 804762489 225974657 293953788 854930308 442827150 66808270 924423557 750912537 513639369 825520898 592164594 716531973 683274474 329890534 907512757 230402939 52374482 390046701 161944917 714809046 798317397 5737406 349129480 612225123 960480737 856132069 591521242 723198732 618522388 663124512 469017060 174164383 215858874 987612584 669623815 886399811 222220326 771122925 197992002 125895603 587917640 317263526 732677049 423363766 186298937 730886555 177527537 926025220 448116755 466239216 223834934 790776790 83923469 942738070 598680517 675750841 999683898 101975711 920207451 669708785 859091473 50743445 20548323 386693889 80128587 292711840 433559068 432630341 973767026 107942803 512610966 765062573 606378897 898625300 582073708 675484567 636439082 491264796 947982186 59502450 948949625 918001340 687153449 309437945 450046263 131257550 954557916 804450287 957895322 465753173 913354164 358523536 127849219 482621388 122778557 623731682 140763853 380995281 837815867 33659328 615672679 745694518 537505924 405314153 595099451 403316550 211598615 738704452 206105390 420513881 944392202 302663924 716219729 472709049 772634472 773264642 285578688 283691357 592035145 334490356 309869062 935752276 527541000 578019638 548303688 905695158 217400307 944751861 670955265 32716112 344262833 612181206 467475398 246559658 356996552 960895683 242653032 970045899 388364671 964074342 695146975 120909885 849193168 466599354 552181054 888093601 78585704 258919772 180758992 258175975 538278579 709592043 447121935 617166535 25504625 600360883 289155460 850920903 176517632 82687150 719163321 713461284 499411314 791120635 463007859 653565101 611284769 896070299 906028347 265307446 463425004 842831569 780356259 58480902 304788494 422525761 716885586 602989821 524121635 618737168 430325254 642839 34833734 564174271 129707850 563344114 176801424 871930762 850045261 822359681 615408562 24036209 878862044 525305020 231708981 178862468 376660101 985185576 361614064 137159730 25469003 204517982 19647163 1469018 338814276 887229821 188925898 189194426 476496803 754072091 789843474 199622285 213534319 67257535 531275399 137164619 331005071 985154164 680471816 354507384 813943426 450748780 217233737 469401593 907513054 144238045 804202327 755799174 220413733 260907544 69835499 892548927 199365265 285247560 312904609 979908936 79955774 230237903 123810001 425496832 662479083 167693860 542075344 155878936 978015024 686226632 494573751 792713575 592587955 45421299 969601711 128102908 22905719 901234404 354278782 303153670 279625557 830985851 739030889 109205530 360112919 958565732 592629354 232493514 784069454 976574952 556009415 502892246 790630851 155800157 770125918 701943936 938908104 938150057 666621635 245942058 739539983 676789677 652039429 913496445 818207366 349295043 735572330 482843517 997777886 630841771 366990588 860135225 390558689 110736666 922002343 805821851 253138228 191819589 336285557 324296159 350444959 900405641 313328250 843883798 68303978 446877993 783934891 398682792 937179053 37859337 192929585 887503193 912307115 884276982 436748157 57034537 213942268 867746625 285290203 664863556 791930746 160149294 475080667 598016621 326716713 640905025 333704934 244168262 592182617 131578516 951303313 293117110 892263345 782805272 904919524 428243431 621549042 865233873 40368948 414997823 486954143 867669924 703061069 170475308 784377445 997516113 86979544 369957476 920958089 308185558 489466607 374047767 281902440 88459926 218235073 898953170 649948299 559077980 789689507 902692160 490256737 513905351 311957098 756321012 739394280 368306938 681396505 316432504 473430090 370528705 439065533 850643807 838463951 41804708 827594231 506707594 57644071 412602205 414565573 214506096 863382261 296109280 11236810 408339925 182355574 838421916 984657335 419016431 250256718 525993106 561138545 777362335 882166172 942591886 879114533 772332152 549067431 933222632 358638691 47170437 100322734 190623131 985259032 793630810 436814006 846342628 746419735 721685524 138746070 22799457 171791688 522678449 892713517 422795852 700867822 714153611 668501212 928901404 96694775 442971693 618999783 86997330 520910463 648463539 83219269 51288222 698449485 697453562 288488177 163136070 371390172 259013021 479150979 529023998 180043673 513208102 853973571 148599538 371479575 920026124 559284599 750078102 930188686 40172287 220977281 855666125 911970760 975699030 787157247 221944640 358028557 869767791 641935306 374385294 915669655 361143533 6180483 257189509 998110930 950198368 516412052 472832361 87766560 961769922 400971474 179447874 769683308 505801910 222894165 901733521 580101027 319928363 838024275 478522192 64873378 210800917 537178382 538340612 399001628 245990721 798620876 29745607 816827715 742077440 268070679 390574525 793385460 110854764 567614039 527515649 864463761 232050377 959898198 3543681 609733235 259668486 167809660 311099604 329707669 807300616 993380755 920380522 15626621 827904287 961225592 105923796 246097152 816536904 814158979 519546986 236920903 269163666 582620664 241855378 275673150 605489587 561312746 714646949 93703169 728556147 909943583 934681765 268018598 642647698 547492032 937772637 509024238 498335478 35757924 23571100 483952298 551095011 919330397 804211138 228020480 490668988 659566441 629554957 967848868 382436732 516875732 434631616 934926352 769938196 450370741 321706355 566814176 157802603 806887789 527371236 438932892 413034616 908929774 897642541 218663795 591160251 382079909 985790172 968260163 826738832 390851353 551522953 304582484 22210661 359317239 179968229 166018372 895108886 630321707 594314676 854879517 568292732 211193037 239426174 278280533 1929192 343148695 27959354 1524616 635270045 659893997 396931131 948100391 569227033 335613630 612175339 248236169 390964583 220951674 96560148 788560678 634030363 334769013 317241768 807453370 293180254 317909823 799334979 732905785 730615087 653062730 486980789 112569879 854560827 832276499 558465515 718363807 599540584 902502609 595551751 558217802 499611482 459095617 141822587 231078773 724614059 613089060 380269254 486566185 848549090 264583001 243407706 37630423 199532230 939444949 245765176 771536957 265114915 479696947 997656138 535917645 594462352 14528151 516138710 617723136 578928863 813894974 331712731 495504922 121619815 876203110 198891736 811293869 459865186 255270985 851884661 280471410 773404321 425326080 312101844 771249320 327918978 51418100 738842618 53168380 936197861 828114726 412028475 216086676 957350841 499448335 626352695 659151600 885924213 651828378 287436389 635894813 124585815 762224728 387866973 245717653 414551684 243432222 13153599 164475514 449259937 180891651 41509197 820827232 791342780 888211930 627923195 581088121 164738626 379945711 227601811 224247427 265688350 139162288 448265685 288587009 820665828 869783947 455758147 154814912 681077704 540953543 270801822 709042563 192092671 663886722 538419967 326222646 96248076 501434146 649966995 121649687 94850752 169538923 666016999 467985931 570207456 587538391 806912533 919418888 504743456 323686244 121677171 598170911 595274250 545640085 919010984 802485946 515274976 92033374 112639480 673083040 714060041 770552195 723638207 418980042 351593134 121728774 482745588 565238757 315794611 606180203 149286439 390689436 67190069 108447779 772977634 409623442 239236013 279861174 31665406 169721659 155904287 485049537 30476893 109635237 280053520 75609633 166521757 221595621 837255474 13635295 339978740 327049061 206200994 220300235 794551543 427390861 277418457 507429451 644003545 352202330 683868671 180284374 926731511 84869816 61614394 964237253 314991188 675492116 34473465 377367127 268527688 835892188 914736704 341652165 758282863 403366925 258762091 505364184 8252324 783104625 791086187 54430263 740660646 865941327 957722958 967364526 400421861 750481804 494583091 391113590 185123936 369363009 37492356 868839980 530605358 569440085 931231853 455963158 995293027 527653636 399689950 897576974 190670788 812572074 349942797 473121782 223212678 952841797 643192444 165805087 513302790 140887410 285848014 686663285 683073717 986952768 370255114 494138517 177766657 656393648 188908328 223774469 807444885 709508014 176617155 100455335 54282131 634631442 336427083 470709449 296767588 274529851 709152927 478030801 517030062 890569759 114756332 598482942 168595799 625672363 694643814 201919218 40532411 83105924 392287380 99750187 242411009 186437838 704438465 901324079 645893344 303795883 524805416 752925135 499686377 930030238 969968120 447293581 815393415 780251217 979434298 668118336 300048153 232423159 46524243 428027887 718696391 769037836 923966276 692066466 441645721 911867250 662184132 785017606 199532356 484450510 688164319 610402840 13995203 509312240 757117448 479608603 429956308 791210114 672534414 815915534 866406179 604443189 202523503 224886286 648011214 269389340 373595030 752926937 44312397 673312578 586541111 410627269 869053938 901533681 280982109 551165117 511002762 936550044 68031726 694233568 727968591 410533283 87506601 659177274 502362379 575012709 736384545 600274551 903148979 653001651 268590431 653998340 586661113 877887382 266187209 4537447 323681566 121796803 787167056 876354559 405046881 265413743 788181737 57268733 419597501 283106823 473504476 865819039 593493644 831273420 868289542 206740634 202808112 599947310 844415017 668381946 353087003 456410656 744938529 217902364 760613153 526142503 636344270 290925943 793269816 46601856 200650218 415828344 890183036 582763866 31680834 669557044 805694875 265587004 730673952 276070858 662826932 922657053 978118202 191882115 70540356 792861916 448014288 748224875 659960598 878043056 525372202 148617673 101575861 848375072 710562478 926433392 615055551 733796093 536741216 851670997 471357708 169315550 158973092 45813288 603759666 890956997 492889978 640359311 16234028 978092956 57817484 378102923 273213516 486967079 616733411 140560266 517565566 882987010 155201615 492338680 932705257 910229611 36321586 846998454 663497456 932721964 929598325 771255879 386133242 348181462 804113419 231335971 547758774 240404967 74744874 541146504 9726645 668561834 914472960 708599576 81959406 983814998 267868656 505887383 903388043 547970705 454662124 84467091 710759462 732377876 438909959 113210178 708451316 851053700 824749074 416120983 838512325 44887391 591562605 456728900 638820533 663714600 492979898 492157366 685210169 442026981 616014671 963918804 985598235 495738352 696897451 994731785 11617765 456411745 136902260 648325238 642592189 484035157 298150596 351816899 633211498 672178216 558008574 946875025 848969344 282024806 289773986 345601847 782506907 649320294 74229232 554821145 819978646 232367651 518062069 610698917 786925725 603357730 921876325 437143544 447990900 176328044 412756585 88159113 604153501 838419465 621904518 613912313 598902397 879593424 647437727 632406750 771989800 687000374 332509626 264294622 760766137 560620579 735387380 501984718 106364759 803012689 453829460 685129853 969973559 479413362 184095760 902812392 523328267 668957463 993970410 758746127 631053799 814650544 691816298 978439528 976072453 226378684 187232355 984645158 163847886 832288848 581530730 250544723 288717 666035032 847661492 239406125 825307853 362462320 798738527 664176325 112446282 6908311 288935319 382428380 554286578 923308195 433976847 922743385 104085416 365383611 824938791 93173884 779859301 560250424 717704481 959677797 180813688 157380020 80957316 864147396 461340880 905276010 264383664 345490441 933721379 56483293 748639924 636860812 834589342 15904611 417337427 740429780 45724102 549679960 209394820 396437991 317735303 606912869 876231811 145793357 989365799 914167657 144558641 285763559 465196352 846367448 614848201 40770661 17116397 819879507 191143111 228128415 49865025 849085468 221091411 664440570 324118165 151932426 97457103 144467154 61647127 155105772 579813575 723183613 966321309 229624226 275282609 955476641 719531405 829026400 987039449 503935529 246251543 315416202 608313309 738875087 101746563 226507834 811869196 2163021 316158341 563021094 55178816 906909125 260962230 507800704 51893943 148831604 725202335 528652737 8292441 32521033 880201057 478647103 749307828 961930076 406057522 25989262 557400694 449242765 216214110 958167059 847388869 989741679 896956165 572438769 575657885 541735176 111416567 709817099 825073888 538630804 700019065 522172121 983518720 456841032 201043115 693287046 113329412 354525991 922751385 919704742 508604789 219689672 365437132 388639146 315060721 416773039 572768890 281741774 357857304 867226923 964170284 53211436 382367246 556391095 353069139 916135715 759462328 79560376 772844280 58523572 248146349 615659178 794766018 142661591 906890303 423835093 642542378 22394409 983846633 673270278 586308471 171744847 815656244 747817953 655496337 113282414 780501774 244910699 444424567 558967108 278916693 969844655 295949693 548564670 977661802 30077297 381213370 97697063 230270132 397800063 970011111 505871672 696860374 584720429 864030417 118026895 874188198 40017934 569539905 965497495 130993968 905245398 354021222 524543209 515413730 810546308 105377588 147908951 933383136 183707380 314989508 835600442 867607621 764114176 630159255 266217796 659634407 668925762 583865273 945223763 733508115 249733081 908454566 311266661 416663600 83011240 543505331 402552737 323260207 565544364 944931948 803902968 906850095 56946782 682417855 203847925 401050823 496030909 675931559 838866901 177375168 910731566 704017058 798848865 103524629 734453963 26061962 644728640 804099601 144826408 212196498 62288778 468203569 538994385 522337658 768972057 347142439 291785274 829153569 416980153 776865961 938678087 20749665 453299722 473365713 106664855 452206372 843957597 850365601 653887923 313305143 81811736 222708909 159816986 823776494 36816257 247030943 488891963 434562354 525286073 117431341 263573395 873338683 93794207 81721759 99257815 227927550 325232402 798580396 154331410 415152967 973000735 21638473 901372161 911496939 120640874 309445234 5507977 946661431 232498108 87860500 789826289 467449189 108733662 528215041 684999428 609050058 516449273 773488047 17368183 280762019 321477746 479537837 269169889 863733987 157521665 393049678 248109289 72512140 213719713 184641241 210276709 456562755 262733593 347401874 455967930 739015526 100089023 961074054 558009243 74863113 170565604 451716786 357073172 6064150 98655713 314438638 256373392 96667375 568239630 755959767 734496695 686536905 274632921 280051892 10847737 452370232 966934694 958821017 736809511 893289391 830809087 145807214 997185394 427777659 829343511 846337404 667851608 265487603 868371829 165839826 225084724 419961155 296238514 683830980 733521736 359405278 75556128 93722856 555054702 902182364 676881336 371180906 678203499 417937471 849583296 818600843 998980463 16066734 87514707 939654619 304195352 323680783 260130171 310018769 153227260 364685455 353375078 163500488 306677111 517792112 727911513 239118250 557308814 581714994 96633113 159523282 158524569 162986238 564738805 908865189 468659190 203306431 406308253 434173911 851207386 282528853 248610241 723511889 884814175 603712540 437948860 892172552 27621909 537048927 800658519 757204000 707430114 276241187 416448259 644074143 602898713 392550724 349511904 97008832 574294427 818895732 537582182 716701748 51132684 788724468 223293371 996494809 972301102 769253930 38438736 448028160 28691083 141082297 548149643 126992091 194359855 214606957 135920807 547293855 388063223 258117323 632967030 341444816 988966395 169489520 398035914 475755935 303714029 285138921 461611871 218942642 958434450 862459489 122266077 747650497 891003971 582685688 165587052 915737022 322937860 962822466 935783607 479607856 859796642 503431599 955489473 286524964 927877130 721956367 197363268 173991660 459832286 764389218 279246263 511041547 659704358 456935799 625951127 181333940 24185985 902557699 503415754 306225009 650062415 719171424 285588832 811510254 993734695 368724264 39701459 487910785 281008114 981739068 120526065 761999849 228416693 871946297 940819888 91380638 837125626 192712131 207485943 689368694 63726463 902222103 149351441 824060900 226490329 806353965 485577020 585859271 330690799 117534592 364953640 207828809 742475085 249476525 950467769 412452163 428130838 902008193 275092373 132115741 217634949 658049246 106859812 197422157 382646423 212952341 908199382 407692278 20645587 940129732 876973364 966981003 246156906 443330167 604269969 551716934 880769679 239677710 376520713 19361053 833887125 786501690 358001179 952188118 367405682 427312970 318762390 515707311 8223230 769663835 467958026 768566857 266838166 588568189 74658274 185213311 193537741 802095166 765626875 451672590 67264004 816101673 952546713 675219832 995175135 418648179 276626914 474922117 522068416 346298296 292024871 975087470 548935789 903318679 486409705 783886469 234511294 692441410 611636324 76897177 403920674 498526768 531544714 495272679 543180883 358299440 886336624 276653459 206267588 650087997 780531762 466020413 278124269 493941056 165031556 318173056 936286075 502338931 645803457 206665202 201512945 373069646 715505347 464133320 933035544 822209969 974377507 264424702 618883193 49036268 906610135 963022265 308239508 589531759 989690618 223456096 594055415 943031300 822499015 178619725 346675151 108541041 974631572 162562999 796228102 373471151 241505169 175592559 485593489 37177212 625453081 721551568 444482111 636122440 670144457 834903119 545264827 545684550 707311477 313112374 273785188 809433332 652381752 593139098 142997628 947484326 532993675 663615669 391336782 766850531 446888012 338529960 925854661 618182080 154184866 518415468 178865906 205351767 4825276 905733678 191432566 662717702 133965282 714543986 901952695 278184286 735633065 40597111 973222542 928826009 59720396 935036232 371588436 278000897 90707562 43421182 123555391 234143245 708005043 569076505 967740912 205872690 411006020 68654117 392364955 351048539 973518734 541095374 218227198 161622215 3668538 448508109 30118471 326714742 97153504 324336320 497937020 252584459 322853791 379939131 350266695 372623067 806258317 372395018 873150725 6538288 38685118 576941020 402983202 357656843 298634117 72000697 560390731 797668426 733784863 632496304 784605317 890185469 264903697 364304179 117729741 833278634 888831057 264381872 28582034 761377647 382208744 142145191 412158638 25140668 77866429 220851961 171711783 604681558 995290190 468526460 915631160 851397956 264961888 868935510 206228196 534881368 642091040 47142639 989924702 635001990 380665694 47085440 993772800 678455829 654298177 501390911 13007955 199683023 554466197 191404292 320584402 697481720 386118916 915984984 117498113 350338048 885349107 884691472 18990018 206198427 330116979 151023825 421403340 487036814 589355758 227656477 904404475 113502189 678509962 604454960 789647135 233714740 653711978 722477435 737650037 301234093 675442930 863301546 502874072 957922323 689147952 868629848 658909333 589466931 950975355 628885283 956806443 33783823 963200632 332204360 505362614 240761113 425553289 634089277 435514793 697989335 899805212 36319699 564131513 965230773 967269527 139229437 902426104 825329720 217569266 742633876 228973246 636046085 118143209 481321230 751355057 307693554 899364809 196142786 416144454 373359587 307024189 116024335 945499866 532720278 156294212 495093751 257782264 177874345 626271305 694727850 572926507 583487386 150855905 70406452 639263976 935126505 183496016 451451986 722702211 483087995 674102087 772838077 637117542 195378894 736500951 737475970 446914716 225229497 656684331 261723586 68916982 730998741 993079168 303716961 624693456 829374399 570659128 72871906 323476686 305075898 784338817 985544190 245528973 361535828 689090756 778842059 188448372 207288669 941002048 128176898 420135545 114479626 698797115 958013354 227098241 888625802 634462970 243870346 909145356 566876369 973915570 403869197 655315902 23172307 435179962 568395192 753352547 543121764 254026195 154286801 838648273 434328174 672152472 453991239 367534550 365706613 597390651 80337045 497878681 306846811 712819331 183390646 216465434 288561140 168520172 170778706 899539837 508402475 314692789 45584209 937546488 526640242 841074295 69485303 204145870 811996295 74379150 897764092 359491018 38235584 466067951 682844662 144745082 835545928 492513506 281464441 669635053 180996133 895928770 975895869 335215878 419528782 313046146 656618173 506014572 748543729 712639558 167919927 900964776 478527696 354882977 849959505 798012059 537073472 306956097 831234214 48391537 355577343 74462858 360225794 349356142 186553075 879452935 533974308 392417624 150362015 305525197 528543521 981267660 415077800 167434383 392185164 167384467 472386348 181321592 331521927 82645085 548042216 826818843 802082402 340488769 542579232 377891736 763998151 832526840 634996653 541850666 345909476 711563955 421607680 551323239 482267372 650902922 857333329 887351906 704229511 238386787 518585323 999540855 857854639 138458655 345358742 762841907 977663206 736964294 425406656 164295084 297693704 384246851 877277659 922250323 256074290 757958029 360413550 732709968 708624344 758816470 495678703 735042563 395509006 649877424 145969144 423282236 289623928 16360715 233043803 209902817 665225093 108760986 349814974 109479573 911398301 690118961 368211672 62613214 563387743 325659427 306113908 99722625 926954921 249511839 171369732 844406920 314675642 612236409 330015345 133267692 505579969 620683500 33861385 14019228 167630414 773751257 122196737 96653417 302106044 728137159 114694304 869483697 759761872 997038016 108355453 488603787 374954313 520709803 83150412 4858983 563495821 409425215 275639318 3346990 472414496 314786600 720307284 940922748 981050419 918768432 502258212 817989143 66145385 461359963 506913587 854074254 882275567 563689159 361668156 122683944 832915698 50984108 454307096 318589579 445770951 340178858 310823914 808594058 677881976 768087385 83152995 129977377 882439912 170780525 266769981 584019805 270310652 134788093 467857648 488520552 680032987 480165174 315161048 930897934 307503310 859123266 996102979 34329846 822950969 292610548 231606338 224207633 693161154 25494684 149051545 73562599 820597826 351562315 832025689 33261931 430324420 874881087 403681829 998331994 154245689 338007121 561669756 826682944 924348642 911237928 520854853 797255158 819106751 771707493 839978901 644357695 37606257 614161383 965939643 134481656 32898098 210252546 493101069 275059213 412437644 726887431 273640628 68462015 179012654 910571432 298662816 103148636 727359158 648941257 307448902 861639602 885050720 974233666 835338820 553614538 438568349 281796436 910842891 591768561 562526533 933301182 234907853 641311164 668397584 376464787 519454640 173483442 350848526 115901988 391024122 257301605 326354254 399143001 238858633 408998735 583618297 144391479 630060534 763418366 687336344 559329440 927269323 158931745 129932646 514699793 959327645 413272640 848561904 136290046 615014846 373234626 93578343 156870069 672934919 924858003 925464492 51688548 732002114 4254808 650613322 561444529 319251492 287215702 36648496 225439239 858052712 195683913 565012132 774237323 690028630 590451366 792843795 36300064 203190684 920480190 598633423 168596780 197109144 772871408 13250061 562240854 59703342 436672690 162257083 124739476 777347397 65642895 483427000 309291407 247629084 376847070 227690441 649638165 864003019 894999931 92850936 98797960 523856106 388658443 517882818 880772134 3253954 971198226 654586765 919203263 626480535 425432159 115703865 352884418 256636004 891748667 849998594 126592803 261072527 606594789 384792360 223169620 19312908 301294352 71692159 624004811 8978767 47069766 697311329 767432198 925705557 898395860 885738849 18365915 459203598 87482482 354596599 564400739 10157388 198747161 495859246 687492361 393439375 411902418 196409607 278204003 236869478 482160337 333768837 604557634 209307236 732907296 828140654 965871716 789447267 797777007 238453769 484801535 342009446 812151523 851230035 517534411 135583546 696351969 674774976 77196785 908018944 824225896 159446896 659429920 368566211 899009766 330692315 650473869 467177501 614855649 299501490 839336135 749762487 740044876 999244799 206359245 676620066 118078240 945118062 180036379 979918413 555448627 673581805 431709994 511134937 550392370 537574284 612952089 299542892 580671244 76150498 683317715 897429655 866079864 151172105 980093183 950869819 679408409 443670703 763594828 12882673 252518713 356997591 186697925 156649391 859242195 912478704 605250087 786416020 27003138 491125808 393486845 935809849 896405518 714469306 646891698 780669794 408737203 28833929 984225211 663300529 57179949 504492370 952921984 612978341 75559820 544579351 850187161 486783307 896201636 605347184 412782108 749457946 928656100 358735362 737005238 261968146 361880125 85424976 251848648 678696456 233925176 855384199 900502933 51640353 218175358 802215457 904314014 688966690 418398473 381203224 899508979 706668985 507324330 771801252 696584561 197651954 365029658 590894364 892455462 513927693 953222453 367083662 751238569 546462961 925600397 329033545 256420820 240718584 18455598 189884538 93675939 115135035 983863831 802443703 153628997 233475175 558894685 822019094 354209411 441643365 286328434 429318314 698104488 993062638 537295954 565973315 793807667 868940296 958084013 297233694 56786770 573713609 50556615 987056166 152000606 476129757 414556069 137237405 580452402 663966322 519312334 123499797 115034500 320147685 857324428 29412002 285687240 680421228 610057718 70561125 320835634 664759627 15044991 486239152 178455125 885950198 939250452 593548831 207192902 828760243 687081739 429688546 593219433 839900812 404997258 374243666 582000346 635845588 39394072 658904544 807995799 620134408 463244636 465997703 356166904 222478642 884090935 714083283 888828996 88585459 129329677 739452736 943880246 171746831 869769955 965387620 179313063 467786742 846599486 376474928 614688056 901023059 844434613 449480620 393753969 129506405 985210559 995785960 312324446 818059878 385108458 539774624 279385838 514514139 139870052 261868359 38414614 267410676 541680757 887189813 66366312 247594562 72596882 412436091 750227699 932816929 813730994 591728785 110338794 16480715 930532051 527696257 944719628 510532813 466628180 511391213 103729444 287203894 934430037 521802039 98442921 985294 745683306 582948278 954511788 227371165 546189747 153684216 998096641 866628457 251246366 133346976 880041485 798576628 182446087 51173992 512499096 109354244 184535746 374109711 243406638 205329063 656440376 544166176 897996242 767885157 738178996 971204534 260493144 523781831 964982586 604137233 716156676 147115445 671284567 494661309 354053812 23899700 297571904 151266063 101980956 583679730 246967772 589602321 461974943 55770789 419385022 211447488 55670239 682233301 650885749 23814875 754855198 764008131 485095950 432386526 108938631 305311037 658215899 371075765 483512198 555930843 849956958 732279140 261127601 564863629 403893668 838124505 564347449 118190893 50174367 32012926 685817882 145365114 947969962 429696963 599854998 54821435 407718604 581614073 469791832 785832621 358680686 332315668 734886620 19600010 682195551 708341400 483410744 578259102 94036556 581678153 649857711 802099155 126661288 252090234 693712176 154863569 862521343 972679632 77486141 587841769 503752501 220963045 6625972 812174755 223816589 333247934 236129061 683770924 419889601 79504014 341540307 151828650 154743034 193724587 322544663 773815505 556351731 807256443 964048501 286519266 913639135 825288689 309857902 568403546 836683371 899703100 466493566 259505663 525721116 570068836 897319641 785559429 953144151 891501740 939378226 827248530 425336194 867972509 818342400 274261290 112215818 837758437 846733585 69958614 728719161 313874916 950416530 807657582 651199260 529960925 180702142 320721519 384601399 476843978 415702364 114970967 824389064 215451088 971761055 683244624 716425169 212499410 531469127 78555560 844649207 481029317 793229455 86434733 106305234 996136591 429253389 802404317 998031428 567284783 230273689 99728305 514331675 113473642 441893305 730687758 665144665 964297968 820115361 957917969 771659616 248247982 617342335 676396114 628895164 871292548 67908214 653030693 406174150 544971714 429558944 90070699 764633402 828934990 169424552 707003143 270957937 41607305 294219342 945030470 925271314 96618175 848758821 352744075 374639605 220497502 537778037 808161850 247371448 682643250 354651296 384052034 100432299 795594518 899270501 703297472 335236350 628552136 88890339 350268210 536767512 384543279 348031100 51525404 664126116 563202455 100449736 305833812 280193231 579313398 906657029 856529355 683357648 467463002 783719627 168057737 466476282 893854707 384964492 994820254 217211651 502093179 70428873 101541212 118489018 309337259 419328764 550541560 913669519 701256354 52833248 737501591 239213469 66490095 784173842 269586034 451774534 482544259 575707475 591403804 513353173 863170076 410992737 630960921 388508197 331451159 174092255 629801120 488139103 363868398 122709955 398082208 691932834 23074821 128282134 723439894 432325099 167636171 994027036 451788261 393313015 687273021 473426010 232977015 551480555 876494588 124252527 372555446 941218115 94919968 579533805 185786638 565194007 221604254 524979961 755972044 717371937 50338369 401645257 606020876 212045657 670658529 818645447 85842979 858778170 803802644 343053204 247728472 957231086 406323076 89715167 484486819 994076803 442846147 6100164 48979326 610394160 294318237 556577815 335185447 6472333 631102497 382022276 327082418 303765816 103822150 526999821 202108354 909776949 382623396 155990346 842735003 128524709 834093794 469768675 153115329 582244625 549390914 272056634 699111991 49612714 999448710 16686033 350136232 443356403 17938565 393167687 50917625 732877993 980012833 731287456 858361148 396009494 845975652 908371448 147606623 320853499 92774099 753897557 18882368 564795616 95846875 614902988 329866494 877338402 19272352 924490054 212488896 180777784 110644427 72656022 398654520 763027007 752826323 768886448 588576184 29227817 411465523 639818483 888288002 612505355 86567292 55974898 191222157 790788297 387184064 569288150 722094368 621288374 236600221 643716348 429191626 458968620 708192340 924504890 929801041 854207187 619332214 561153362 326574854 333672047 194131298 438815765 103687930 330902927 718323978 66107656 298582714 806698079 773648035 415899274 364958464 732973938 291791264 309347155 755458975 369942868 24240106 680690243 926486134 317549610 71384462 966523090 609910728 42748112 243839751 637737414 370069740 186594270 669323742 730590572 19425679 433735850 651286246 536961345 917736111 72628375 903335831 935091857 609860396 361039194 419399290 208185852 966684482 854518075 507514738 646540849 930168133 537030578 524593409 824379734 850073517 314421098 975422340 525599410 928461006 346766421 402827480 337147195 369565335 690179650 500307509 347500965 457823165 369304505 414024901 200683904 190438267 110670240 131954305 945556042 988917850 976321074 288830842 736577747 802681378 441347735 957595587 544561833 842053557 217807192 427000012 304560001 50837756 515243801 588076211 149185132 32785636 569652096 256741102 119483483 396373939 798520620 328892820 682955062 918887546 568877090 779643937 345640147 612448626 125200390 758644529 261480253 715714665 869378774 29613211 438152230 414594542 839580868 997562565 876575432 427053478 495101808 805793749 651112035 981108099 299198460 791243641 483493755 525489730 842147079 308131989 393698193 282340356 630420794 989619225 15438469 515176158 884263219 171220947 431719208 880057164 287447771 788020914 471269161 627558903 740905852 692333050 288318087 846682577 183270428 851983205 304677522 814679517 629820249 671907606 564912314 197227976 704284286 173885018 399176056 39851236 681177509 139630597 853892323 17714269 62193727 192261700 576171562 77012714 985169032 523648498 85316716 729973004 92608059 721815253 242939099 166589907 372911510 988519766 502004838 662161664 554592769 553408101 916162783 187403929 280648272 520461479 595871903 526608968 632908033 525142852 346765166 863605778 320180230 413700327 724647466 909526212 734915628 848801491 835308680 619433141 122591115 892121419 164948869 641211190 666898300 775555893 34526786 447051263 447727825 685929080 516038559 649898810 465845047 412728088 233735353 473027021 843747500 726677214 586364456 692568706 578673343 557022209 929045138 263349334 776833428 508238190 14523746 758794174 417453121 980782174 779491146 441198478 906414490 819975323 462261734 35329469 784538867 712023207 186846774 256198090 615197044 470468432 464338002 319344246 350963797 372838672 750643157 946363149 257286892 951314825 408930040 730228193 122282381 927328287 942881612 735523702 72488160 856968316 669566865 433619728 820334175 732666097 741857117 449137595 266419638 522692704 490873563 66359778 686007451 757855167 311427884 881584531 422122194 148098752 662631885 381683154 314984627 442182748 756364662 253841465 295014753 941546638 561615722 583393136 229612652 432528580 504710509 851327989 875869386 875355176 928391540 802234186 340433120 127277861 725266951 284213510 948877416 555815058 316446423 244623054 920258169 188159456 936390769 205150243 582597220 847399511 254186523 341670657 294230617 633694884 899699783 230972393 638252499 153077133 237912738 327069479 586396579 173293573 488921497 585987735 810100616 158393960 733389809 951011117 50507591 664440605 910292352 365314595 818647293 781813769 225775647 277467566 895964830 133127224 636231523 248601635 188460681 544394357 91075918 831102292 579327341 361077987 912419556 595618195 952783029 703381271 516234811 326774320 523047364 959811207 772647956 380350039 838252117 558436404 500534610 670632629 47782333 48462904 775298899 780018327 899582915 845072032 109981585 909767362 96539421 779633207 451706152 484181990 532294433 490657685 269014419 551049689 487042185 539872811 979426831 516616085 790312973 260835036 434510054 972250784 151273873 886969581 628478093 170530650 819660504 663984247 148479249 112123886 691877916 625553008 641249658 406666154 713444818 479395370 884304117 640224822 299593623 182504209 572734299 859543887 774518248 194329621 45441275 734393367 602747856 305303747 909285830 629521090 98700146 131699002 806408333 882902870 740469293 131541311 761870749 422004099 563243606 891479258 250469822 65193636 547983861 526477468 68559477 178829790 725716663 609291033 857781780 73068453 17950385 775050719 657149787 186802992 950460813 908790481 190280978 244202335 552944047 256854613 992731919 305607132 150920797 522499837 102551386 752405302 752740499 416922845 468563946 311163380 765928903 632314947 616564795 527127187 555813165 707422574 977868972 907312463 297726207 64243932 651156405 473584966 147817969 166371188 393399907 489882769 508392035 575958124 129569327 124763172 22179430 148609450 758481014 312977876 640576908 829705106 943816321 88187980 979762827 17692971 570856772 851686122 619991666 519841016 768471302 460166543 599524470 447285003 125182484 729139111 362685966 494568985 362957839 91860487 833379568 426342134 676692842 186194104 118980913 287457423 660606845 736322517 866664545 63950952 942182744 997974679 435649007 510686483 51971502 15000031 767016251 984366667 823861287 712152779 244063804 424010905 207698740 521625437 934377835 383878527 162525766 524146956 359167066 680276363 533984086 838065503 4523950 453758310 798445997 429776863 641137215 76456607 279657155 6042536 421506342 797872942 247336170 56730828 112025469 303968777 632536659 516735719 878494945 830164231 782358633 143896526 363621176 36627200 393188103 775597118 835392145 182207757 901534794 400790156 976565693 410560949 96702392 919810467 817857044 331200157 101473038 803727278 231091372 447359340 321130018 609770515 807702865 510718397 866911493 762703431 154135209 252105728 255541419 414761349 642659802 253875252 990818890 356424487 876640834 884184712 299778133 837337948 724378861 261743361 429095268 181704577 305260567 976739912 630041960 604572293 912526334 637289005 952748595 299849600 60295958 25037944 556973337 429916902 792497914 534069972 764774575 659943983 566760639 263471837 340422502 255109160 803183799 978088757 836292986 754199113 68137935 876301417 681464305 423753145 182540918 303022181 997680477 534880421 521963085 120716354 525478655 714898426 921109794 497701164 320763207 605672801 736765245 563565095 87464407 668250703 861524740 52896183 3926860 90252280 218725063 521929914 336404276 618585980 614549251 744202373 826025683 956975810 880827527 816671660 164366159 617984807 91470667 588130687 251885769 920099262 394506819 163975403 688707599 39981058 950981804 431924314 195167920 816188354 857523290 494313114 880485616 22322862 839175234 684997246 189603539 840323067 113162838 882717942 326697231 76941316 38115728 26216714 477161949 128860361 549064511 969241052 883237246 907795156 230577050 60425221 828002279 175844437 128871284 182040952 793321012 992083262 974997646 892620672 946994016 610875121 490059808 395557921 154896099 111876051 947231006 389144363 677309025 558004968 344866597 899556203 794609967 425143928 671812347 242428180 211799523 781962927 86189059 869233270 915523676 879318673 487960893 913858813 230602283 60778982 49185883 308234604 304953084 530215701 138548142 559714840 578217662 946790020 401854387 217654463 418369151 176228442 503064649 639114877 274067946 118895628 913916479 741494534 706787273 314174468 352067947 718066690 472688387 405077484 573144031 492772164 567924950 195329029 535674162 140598919 256898504 794532091 923341700 92656319 352848990 484329433 619522722 169617958 925384152 770094106 684887061 282910515 182094053 629294241 794650083 810871168 418504047 290992425 300466933 86274212 209896345 331841047 912520286 246937595 526007290 484019458 410066236 579559478 832823031 316044645 201817313 116602668 214420684 497139960 583782287 156344042 997718625 82891407 908310640 551614302 600241057 409521209 505671331 570426847 698991454 397708887 594239918 730298338 352724484 96632872 301649619 235239912 520934663 557288215 72027432 671950581 660029795 765912100 517762314 912940343 219105393 441484312 712911046 669291826 857025805 21047977 395718598 568449880 352600551 590240079 82032609 871805579 958511481 573985241 20528883 753237056 862939108 646381104 553433025 161065461 495780514 818688140 707494136 652069572 6025039 88240821 820126021 368026330 812686367 275320963 571104461 753024397 941583384 499283464 5877344 193397895 892435650 721881737 232551788 325185296 698351584 585317556 208977799 33439017 547043648 123531121 161985491 823787383 951641979 38334444 736402176 588117403 347637916 652364433 870820204 252449198 886651179 411440681 733303586 99397187 47002179 320387451 499676754 891661338 543537951 860605127 164244596 400847706 480676601 515990742 820103950 501455776 323507634 719229648 268655018 768487499 722635048 343713840 388592346 241519938 78526522 699793230 78349724 331833542 246101255 674582046 281572890 145945569 188938824 418691093 406580747 899066620 450352835 398068326 845606648 393590374 114546160 734270034 158389584 744636845 115319742 172631390 255399996 798780213 690580134 938093031 2658015 937295295 251546186 826992779 521677222 545291473 521342226 429217255 873514492 916799441 961401241 141144726 99900328 543120626 275128464 90456327 143486077 994632495 876912877 384793153 287484964 384405066 696343293 730303401 696462750 805676919 1716212 702840854 378854968 120955184 888673558 623607305 355225474 868549979 923218427 479648479 573449465 924083066 934070403 215507853 293292167 485587584 720581275 842910478 283609063 262101599 101787968 861855251 13935753 807950984 524890805 372729614 730735099 787048042 758350607 889671982 190623285 439445646 278876949 351998040 947281789 845654169 48625200 778636111 343205005 410084807 827315447 924588932 966763163 235281154 251496123 138562679 592787521 172183794 797430084 260357794 780150547 585340147 548142459 426465252 885299651 327839715 959980682 846476754 638151222 229528696 852832384 769242808 856807762 586863733 435425670 910865387 499110557 519393090 841746634 679430106 320947125 854130481 847688219 69792771 275177419 160667073 855444660 596717643 288295165 68888084 278715439 187218769 709058299 540189386 973908976 627507593 531087829 358585041 212654371 427054255 806653079 293068829 440372790 982719586 317023727 817497763 632160960 205356791 794858593 493522604 807370357 476379817 422008299 697804965 165409570 474301099 603941584 819287403 363775533 539083445 893670043 636103952 732852028 354323889 678821755 258004478 635219474 537971510 684838720 455074778 300174852 150181190 117227256 14409662 835345489 879739174 334725275 513688028 795536965 541324641 32298847 476590524 824086253 356986373 96190131 301354536 568215258 9388299 800688833 665290679 100923893 444595732 452891787 591407159 929559662 173891157 476291438 932247382 735939060 923538615 112442725 281748864 342083987 827704876 556294015 32371969 427943296 534139443 592321075 607133204 125200956 83884348 780413513 543133476 179135414 930382313 711561297 21442977 202381892 951957075 904944010 694935479 596582007 770583682 354267290 176280320 817462640 621072139 32700537 108161652 570992199 815738989 315178135 26771708 455015214 685138197 140411401 444795117 380352845 828918017 357575737 44021269 108287207 126986949 503042341 566286465 140780522 501197286 424181650 431822211 453455485 484938790 792156289 750289393 512429984 392692413 951039772 197094270 8896978 646459331 371674486 963801074 15702947 463224663 205933510 281943242 619789524 299510431 416681699 665236214 895359765 595961132 887866905 536029966 96380327 131652416 866087213 10342481 452180869 6747396 406873206 263239706 693926220 606164606 263948443 468535862 200481998 569729055 688754171 89602980 319487775 601442858 662845668 645828385 549819886 278176664 628171282 641395166 46409883 126009599 728998341 136854446 78428302 917686023 501997294 52511134 702369559 475033450 141407591 957499807 405652616 254086450 460339839 186087116 896494702 453551387 770433171 916551750 971359814 33184461 960717199 245102995 142513049 590601531 8189362 872564614 939786554 382167807 216222453 839203242 45360368 767615041 335891937 668149846 177898345 893970402 177833570 313338339 488307088 313434356 781487392 707039830 636165837 672671390 467931361 556925902 49513398 642685369 776782539 757349387 205307539 790857229 936192281 945866020 320262854 261452616 836729673 694269013 110853791 704482333 467370316 984142066 733691801 621944206 879016865 101175267 1088327 620870972 292788219 811812652 85038995 473977962 597337336 921827211 946761416 703777712 486254410 763113976 6007031 416793626 577820352 382764265 140973973 502005058 936368425 571997083 997442742 562253571 613043386 934966330 423939495 809433376 744748277 462446370 851339073 39538677 593724912 882126143 347422453 100156037 976846390 71756124 9577473 377740799 475764937 559269454 572229817 876088777 669666676 121695492 737440375 980124593 964213620 917771871 245031758 267456151 847835008 264721917 612737304 241439256 162088548 873991501 289588132 261693313 953322358 407416777 259381036 284776954 717435562 535719095 493507798 550257347 770081190 255697424 42884606 659726395 571692647 971693144 41342446 765495530 646969017 242223023 39683954 693140298 345544836 127633861 848595558 926025331 208238087 529346337 885507296 642238139 963439760 743250323 39419809 762091142 990120482 933962864 572285506 906161178 31991390 273047733 244604275 500326603 699360353 192192458 811942023 529570873 495157978 334962059 675381405 311122874 86189526 432615358 3917052 392835841 992925412 215292310 447415440 259345589 66635071 451663739 42655739 598210720 112175257 427411257 304787225 121976103 396489726 405517654 421318167 166508488 742210077 700812252 547860904 63469683 309112488 918815568 771433459 336082842 56300188 366744569 215519862 199159005 896061219 48467062 210490901 412717206 691886229 903278744 196143510 358161564 286286238 517598111 21557100 979473953 386667534 606082497 123527301 2010686 536631984 511985192 468896419 31580496 695315929 816418553 276775054 708782443 152753890 198280808 748548365 172561032 761743482 676396509 326006549 625310077 689672171 704621332 942130447 865854684 422561487 783776920 79013387 651043486 367291780 580768177 512851071 108748481 698722661 292781719 101934507 71058150 434836699 628479490 446456765 138950791 33950378 362124248 144050747 447443385 72298155 591251417 26701556 173420306 365750318 317323607 700585740 467080410 815411687 385848811 258044677 282751846 280041550 668445740 16863506 593604533 828118567 728254324 905670495 40120768 188424323 318204377 318821238 823710765 708952912 193345698 606379068 478154508 346629315 331788703 71337749 935628059 178132069 769769847 714670810 42128793 518517210 565576892 865303771 668293287 991151957 569924164 179171813 843592135 739836647 901215985 992144249 619382694 286841598 478387184 734942677 348792863 448731628 643200349 975840214 692601826 389426470 439698441 363752724 806435715 53291284 66866213 664519450 748646438 345308852 571871694 277647966 614393038 787509757 246673597 100856702 365247227 205680322 301942010 306100291 172703327 573574979 736069805 962107875 104926719 837112874 185642304 295738715 446207410 528498676 247904496 453457447 534152143 37295971 653690119 153711606 817246055 707667409 694181851 103509195 585442827 428626611 922694273 555975847 339971200 319722632 863690099 756596178 782436132 335136984 289888495 576053001 699866454 833463333 654040610 776893068 495892425 355847519 95825598 823112515 79936442 732139595 499695132 924911765 607588396 484946311 445628563 617010884 58785172 682451613 102171780 866833104 505467191 924374970 18604446 236083047 7531843 14927220 26119908 292629948 290182936 472708207 121108768 940472998 238548215 237715334 8454845 939899125 972958192 694668758 916872991 276530056 487132757 38271424 83821952 333452525 627350537 580402093 132229537 766293463 115560396 794594417 309233338 151696249 442106557 494345013 842896519 464261740 286131861 58869272 941908096 105930226 820868570 918314992 312657785 536727895 28517358 381005155 475677131 775165437 623593621 139506629 182515776 792305201 866913708 263320634 99670879 190823046 59899527 6816421 685262094 429368051 121968059 77614701 624489241 699247830 563992113 517132529 178936960 492365336 192374017 322509636 523385408 207589573 479234146 259462912 393570966 886655959 33525585 83532882 156541376 423048238 168091347 514901411 7604163 766747825 538918890 484369159 396802674 157945524 614146737 105047971 118455814 517061103 814790856 960013629 389388619 334851786 949652662 754751069 402634062 74902649 276349690 655236445 137907107 44726095 659439471 273337659 466865929 127935230 357174877 300953041 727473893 191220838 702623163 730743882 488587099 28048109 442295780 986528868 846432215 894211301 575076141 236508850 348553038 554088013 69601248 244960567 986558641 682908575 446480266 613622636 795204690 667855676 149364304 114025898 962178867 583601589 480150811 233647980 254998672 46724660 683201529 773513572 758608147 315950960 526857332 956004521 675519444 136108305 774200184 335386913 903008630 334312426 953082497 357801469 669809223 15879256 87004065 975544189 249172204 840419448 502430784 502710835 363148930 535461206 148919688 523665172 156925221 471714810 592667904 711135710 35116266 336989798 46427072 309686881 58289653 736679008 818040525 128207728 124454381 171415024 502746076 421282793 511753082 702985318 937346401 83041222 873198012 214535184 555788952 884188541 465596413 990674301 775694574 297202805 819235094 534308446 732694263 268342781 502670148 190796967 621118038 55633147 901196670 112183543 821027942 756877953 207874359 507346298 125930217 712892455 505509113 81446516 843832423 139883812 666035757 49995148 870409613 517097765 748416586 257718290 746896925 999751314 318578539 385295857 127619080 871405235 144321529 929808080 645866862 206503504 283641364 992911894 426320835 159758625 219810225 275015226 257086989 78584389 132226634 183729999 476492311 120810377 477729554 473748113 926457177 113989855 678403550 878087750 120501594 133393785 281374390 395028697 653750742 217595935 138737861 902945709 693703384 631852062 720705799 617860301 24784360 812387867 633238356 689058478 522708659 166515401 601946917 886528239 970753026 163430891 892218905 252966893 258251839 895647483 228181827 990296080 273747260 378763585 14728807 203165725 365046321 86637486 308562662 203341094 468330297 260418694 806937165 436779178 406339056 474230104 700113124 978589914 20926415 709229798 519973761 548456367 840753108 302412998 723170935 950589262 545083625 390678375 587462978 820961915 689480490 274276946 310002507 441664282 127632917 384538305 468334435 615127858 845549242 242533940 594338711 84641230 21576592 294896347 537592855 729471538 438604084 145955243 109540565 858028900 479640329 667289831 244402408 567091172 558153988 304063010 700858616 275997884 924205224 181557206 143703361 433330225 322890057 176416008 365562426 734056582 123259484 516143189 418172245 734598018 79365040 642430156 467099921 110723215 844295402 823539044 504726277 346404307 312735159 373177993 878154248 283479722 938259896 731642083 609135019 394053589 944780801 858978976 738686995 800103579 27216971 370942951 418691421 467866634 452252073 889314637 337767869 293786058 10214537 187987184 113843035 384659539 78221711 740852185 578778654 714859376 234310291 33875642 860124809 906341106 380736062 357556499 579192047 155788493 424593121 920585422 232146503 581437492 775361815 5118758 343552847 86973825 695470948 804813536 229112597 388375177 949324598 734488525 557617453 188140766 635419573 851733322 34457289 346754576 769224180 768113100 987444545 88714514 184072629 506234318 248949794 921320297 126231736 645109280 894431238 92415867 850690714 717823520 942331182 432846973 947980875 355000802 605216596 259141206 523611217 486383488 608373151 354273750 697976846 11012162 370223467 586677431 954669715 146816012 105132636 790119729 439371474 867167753 604088171 952751009 696206387 788017812 150369921 359564173 83098669 78725997 172018854 138808893 489313090 637130783 161785277 377730204 735544422 564220699 122908797 131830045 589718845 619989391 773862648 543397880 66722909 919953084 922295147 467367047 232209027 23241660 355476574 360370312 700371004 285237654 440676732 529565036 75511210 687667047 734260379 806940734 132212656 981086175 830823032 174353080 363044131 667956886 854482256 851566451 828759495 960978126 534720568 600892846 134438359 932890141 255678383 954987143 832098628 438239163 931666298 82091730 803426861 389764506 951108452 613139134 462974004 566099130 209301884 295192979 774325501 451932004 943683408 445496174 687993048 604376936 632633723 216978823 347507238 730100902 69777369 878025680 909621463 10390266 595219497 583655147 74439133 733116601 57269655 981332298 79004670 566468313 446821995 741525561 753924351 324280366 175066064 392521744 528538858 884762901 164373162 136971549 311278535 539326531 936867307 735425474 852095818 644993479 109787702 414844897 228245755 229759223 614762820 60050540 731206486 293967850 825044513 295956985 750967628 225713966 788816916 920449150 727982195 912011639 275334980 382216936 340667969 772809319 243095580 965996350 328515561 529623215 812660781 566168032 784871784 415290372 183651184 692775336 438284173 352617166 200859189 134712834 398979915 329675789 307008166 50669423 32702053 738626013 975765131 41085166 774638943 788178206 593025066 658620653 809258463 466641411 937225731 207963131 307566111 584675008 814424833 531479807 55136786 693778359 170209207 234647407 377510889 592203119 557063274 74207802 531983884 901861306 558983574 515608423 28930660 26150401 324894774 581344487 56769861 2474179 472102147 786436750 779095377 954465092 324174956 187273922 975606717 93183212 14663613 335627895 48018240 437028847 719911701 559170115 133440052 869586663 605673624 839022679 136097693 471121747 918114766 110892548 759765924 390454264 463868223 321893524 387374055 866068825 77795805 905279715 837375717 781659007 553863025 629527452 7645152 441583283 405394065 239849995 348130845 95318161 723218116 653199642 653480765 423601025 468162667 294850846 863609709 243434211 28710881 222601850 103262843 72863073 958986338 443975552 972434412 59424236 959584684 280695516 615315461 936317983 256337063 212560696 902127898 85259293 506613447 204575189 577668735 530156152 99532459 591545625 310128358 372904880 137124229 576052438 205530083 490424050 880953580 746650031 413507915 306974480 262682657 482229504 19222578 137894124 879646452 867809033 823892323 664081738 485576392 971793579 510464640 668409183 200687107 833928787 6986941 178639013 702027193 941134315 704219233 85908549 430724758 765608819 735435469 19286724 336052482 204626216 431655415 38096372 249850679 658074737 433963211 846485364 850937569 245448209 384037143 650040426 687227229 879079953 744541983 689549637 903555914 644087744 796568469 758919112 199661459 430379371 939737928 434312613 588572219 327172882 664806689 659677125 948749662 453285077 376879377 186301185 299044156 486098449 150137597 418073820 754947733 236617123 751227888 295955985 876394213 288539444 648268230 585975687 762199350 612518579 187917454 178386572 829342200 4351258 724313718 352046936 559390690 108891320 120955029 362439594 225795688 786049620 248088421 103034827 728875570 288635534 260076753 824190245 203645475 851103975 571209896 949201793 257093996 468331824 968302357 238094646 468201258 238166203 703046759 559134525 563158621 104848922 19708333 752283623 401605001 19735438 958099354 475429607 349756092 110135374 583139809 236148288 426471057 270921372 714450159 677638864 495478697 485166836 611465334 118348830 249965475 454593490 506182658 755097916 334070923 537510512 508244791 24426348 520186553 617674866 780869344 605565035 262426643 949494204 938251829 435032993 599737934 711176757 116823006 398816553 34584186 878079670 165823507 864329195 124978134 819247786 461380016 546419441 695545791 509515352 805222523 690107430 724959211 521337657 42306653 757862150 750799425 859804609 694535109 575922769 45153051 668490655 729434023 307332703 897265682 228293958 205550944 531621555 109505473 518331288 720769579 88080523 992540881 120497497 351650639 432739228 643885942 184013213 859613856 781342211 88242637 976229884 866815799 37683695 200639731 941869197 747242997 316943166 153973774 456227496 706339905 21746897 847203993 327445322 22428534 99333367 641989429 351184980 643736942 45337273 815678882 497940901 483554354 881230070 175734134 842209946 153001366 249741636 182537213 227009341 116573959 191513259 486183451 938443876 286627652 308704112 979566974 138947386 348581223 840739620 694633030 13782226 567051971 817672382 996243263 370644890 955082386 535300255 396748287 687844824 61331003 446419357 401124065 233029934 738051219 717330459 643217577 663746482 708541200 426188190 55674674 301213739 559394278 206054208 667471666 944331758 601789658 128398936 395096820 571224113 58062066 282411820 464642122 798591478 938784757 970108022 947180456 206725015 724380904 82966018 285181650 476346945 784659462 158590456 41677176 487460737 797761540 397344424 321630255 227386973 588794858 118366070 914563247 385919656 807290585 75458149 974366201 37468598 195843213 312007552 31328473 839242263 154192939 484020709 598302882 628932129 368161558 698327765 567099773 762114328 597112310 869560964 386709465 321962120 153541241 847764045 244766366 930606442 207527959 628980751 806162547 880215335 973744483 940869343 866315051 243573047 8461802 151017546 197817254 937722221 222116411 162703554 806218306 825160290 551082746 456107482 336035754 14358319 94774176 607688357 987454373 215076643 805106290 661498987 90678234 206495939 181313830 429988582 337364797 672153649 238196927 660785992 83929866 904947108 313035520 974694854 814312891 959861486 123355127 385802196 857891617 96594668 923442006 451913980 48924112 98372633 302322119 136552717 761597765 976371854 431168921 918971837 45955419 709991200 36204928 309802201 676739987 908806562 488091134 239950460 930909870 622833717 78119340 257567271 427214617 557615141 835356691 507212561 181434038 580493953 690934043 715221055 954563225 652572803 140814135 57884035 273987465 967189578 262094266 761980457 713851638 602716986 575508423 401617712 438388455 252616926 154738441 366296960 789202721 60717716 735699512 94351565 510841735 771072612 59899212 625248137 287371415 312812942 264079266 154936148 974153535 443464005 614284912 212226062 999746689 187299332 154518261 512657244 83915118 318248327 432459716 608421799 191750434 199381004 184939426 483312597 598072865 166671433 97455203 155335958 560768446 46124493 924425541 921284476 652679163 317729106 299225767 602523422 519850799 52841364 524701742 880716692 394873004 949574807 38231536 233474567 850602846 799773098 607056457 32961635 307302846 276322985 831841323 21627761 41016729 536409107 953403617 589084648 778704055 270098373 663423258 90372228 123698088 946914529 293450857 427057233 238307103 506316328 958436571 263242799 674657254 405228005 253114944 826200723 993617087 5597260 788716033 887244398 248540297 144426359 3186124 850054686 905619996 186338754 796185082 637224068 626137963 834000015 705965799 927969334 560561963 870774169 193276712 308562400 273128859 616836656 857585405 246528928 455368921 982829889 774454658 923993331 479074166 462143739 866988191 51800549 939722607 282692544 374849168 875742926 302571852 740176067 185965403 775110695 107130182 337924773 681540168 226500107 470470109 372262333 170006513 744510743 707360142 790411206 575800880 392299813 208463582 125080625 869680277 375083482 73670265 704704684 728665506 289842092 952907413 311303910 457046399 710695124 758363274 696836285 22880546 64607641 968199754 823977244 924385016 460543110 654767059 481929504 192724751 142105236 228306630 316088112 212153339 962824239 866287633 895217334 784123976 916224642 620266102 858102340 656531407 857641403 900309073 222359355 52990610 171606158 117654993 994918759 359894541 351229949 205686057 630426629 798001806 66610816 821084683 941328929 859595398 904824013 451254350 960384255 155331808 53845929 182379027 854727485 909547113 705560048 272493881 363959499 919568295 381209303 879433653 220904821 519765991 197811475 346843576 99352431 241758842 595232355 97334844 538253148 570706722 306698417 969424584 292503977 265065852 429051236 489807059 2067233 677366820 741763025 360101747 974626786 669180502 20679549 463865991 663172317 772357449 365775291 223589094 255437717 5543162 450905 183305413 6325736 870916619 839979933 889077041 724196650 568979369 196143366 233516731 641566292 182305393 583924723 644717855 871836446 89881247 305051983 664838600 456602717 298928544 413545034 191816162 530289351 317892408 558293252 227873245 699736464 796853431 508909573 567445527 615326648 468966526 702882427 168864494 787838459 947783799 540744527 638428922 62296846 440852646 641780311 577568365 671405430 783886237 413815682 660265162 352877364 630505669 382799355 411099189 535785761 228643375 782481393 721581251 364782662 64641652 969250582 122737637 400880288 905054345 465617393 24333668 900594862 464879336 647571534 382221938 818206284 291052889 953040783 525851007 905334700 720113141 809716804 139432534 735557550 52009968 545354328 374800822 171192187 787383656 542876441 485859925 275231351 910300213 654448336 467642923 224065685 834530506 267967255 289389389 156318627 655805984 145699036 606200912 501066568 794985974 424744883 706391649 418080338 773819450 412296216 328484759 586392153 704837788 412892776 776426022 356102115 145124063 372573686 735335221 582536125 567135074 391400819 6383587 801308391 549596873 91016144 423810804 541286246 406136364 31366569 826904618 97531467 394570403 824766348 302297653 970910678 679600097 731860576 762251781 174275821 649042059 261952183 637796980 464638715 171785613 859487589 833435038 378006232 455776618 914935980 926749667 152376077 600911109 479336147 592161674 686794654 129793004 508857956 72694721 36023114 662105598 171491012 606892099 569120335 338204762 405053500 93045269 660194341 113755478 86283379 921599513 724019555 690414220 856753313 840113236 805908283 530420637 366954506 584834253 629116341 32191494 645135952 329659455 300182698 72124211 739178839 881093860 380372375 146148203 14701009 910380427 922744882 1209331 666856391 693373446 207179951 645564252 386606671 714397466 213382717 316679561 284221970 680155861 263060867 193693251 630116518 858308837 134092776 640258392 195144756 40587208 358571659 653857630 86468071 216132657 857926532 197989629 22059034 224393571 156420952 257633440 680401473 27230158 390750773 740849885 274947136 507570558 88182337 908594785 81519303 224376791 787075537 641024418 35572075 813675159 702266944 89615612 27994663 31659916 853566134 748656774 944414337 922008 186656849 317395464 801851917 914927349 724813460 383248452 266964986 174810867 359988628 468700634 20498808 56136398 807523206 31909591 291075431 979871919 212759149 5800711 189472141 910039102 437160309 787037745 828264403 714135404 268009749 604134570 908478911 525301077 840111847 975929232 941112235 742678875 169964511 67534218 724640240 732751913 956050698 696602828 443706289 209946172 688818528 637939382 746330211 11475264 212632803 906173638 118273390 258882289 682542359 441424922 564637029 785487472 521072784 619969360 134395246 499723804 230952001 270201599 60490646 860127363 865282254 511288441 258915473 258509746 987001990 593873296 520443727 386964563 666425604 439610734 242647073 371934163 590232932 244674797 193229710 969897970 254080241 974495248 178064774 181178377 155990013 719876948 892350875 208072513 615220021 517535852 325381267 332380020 805152971 426782000 165813427 640041280 551267561 683690924 53962075 652913263 905999695 412260251 659786237 364855642 386082388 881274029 119254743 953943048 63668124 451195941 124997876 987567885 423596853 704894534 392764045 786976743 357008674 269741334 143308207 625249647 575698044 454789374 776504591 154982332 969130488 276308640 322439634 772923278 35240612 350710929 424512466 39891571 583274582 889813133 817195602 286921370 107155621 738888512 458189871 103495554 412642264 874008400 566963183 712429370 988783320 742338240 363710376 480957981 568045218 537654234 5171530 154416542 442202291 609735122 796483359 206504003 863076863 20207671 181816847 931319641 177244249 974039789 520540927 575495400 331112072 841018609 86010410 220022213 298455728 747178582 396996328 651119762 544948773 166119932 854612158 738563680 610970696 993908382 5479294 340560458 838635669 307961414 572518019 342831422 996403815 812141613 781920523 234007730 499025928 81805658 508557393 689543228 653248602 68927680 785957416 55858841 367240746 442310916 866723045 193020798 81164814 125183110 930074868 55212891 88565701 268235829 148409793 2225745 189314396 418312133 940800320 51262983 147166825 13730058 372587611 840178129 80579881 15412924 898482607 584223961 734039340 477157855 405729417 657714107 33976128 504772924 169332939 912478383 230395523 897595754 265858784 481983705 860961743 928706461 852126121 972539302 549245987 723582262 644103334 942366707 705099895 608709019 876615780 546208718 129933904 291257759 377701999 761931628 616862432 764046089 281472428 304650380 3647281 378594977 492006020 780082350 288447726 263495241 117278023 363819385 375566489 462821055 200550892 522372181 540984011 784666654 848611557 746453362 642658873 574018043 303774734 975405942 185137990 420998737 847085864 315190373 58378265 442996910 593442299 104221821 677025316 563917827 218897744 175013919 986103279 389100468 311028647 293854230 977482492 136677836 877444119 497736663 782943857 305334241 802526037 9720031 756948439 293901657 599966948 318940245 521405944 629185626 808443196 512698894 57721422 307804992 971756275 735342641 669730558 895612684 886544148 880754387 990081831 985800450 956394332 416951932 847475827 161290666 628760660 78321861 992546396 962980277 473706536 810324298 746548586 860234747 75347912 374253918 35131237 936500646 301227450 165718681 300544329 693953037 841786173 946508444 480413215 163446956 832760096 624287833 568729644 86485457 873148976 238504136 177976927 390732200 653849953 476630845 99284985 454656853 649017363 226446063 680277847 592742867 414124964 670896632 91759037 422720565 155799537 614108957 820566109 690842342 74720971 433823267 952820980 653492561 932298509 303982827 930402688 841995410 205028868 893752180 559704045 779165670 699672012 83436513 466327579 677997971 227593484 665001561 848248747 322109510 651910795 168444485 566920590 678068064 800323213 381346891 544538524 540803652 40101076 553265388 113612349 745544495 10202058 600387042 313687064 295311984 783137376 334260939 339363592 449575670 27632196 161924624 94414787 410748512 116029037 117014138 251445160 38907802 827527692 420360878 428378109 189590866 351982882 786733545 939941778 706850633 680366137 111309905 557092091 580151479 29364449 6997507 936174943 616160761 490403726 845526360 487731593 809053433 404593972 692268520 277947863 677899831 710862367 315700238 346887188 388681661 786774248 458166722 691322959 257446141 43259842 827950874 235551710 881397098 311560289 143415333 599518281 207579203 890677085 971484932 617429331 375406842 18692328 707577000 341523612 465260299 866778270 452519054 268415960 479010712 766410749 85939771 578992834 796947669 572169604 675707553 24743604 254067659 473867236 103375655 47117042 813999449 575519426 34884498 479815351 672737462 606915905 484776161 969973040 852340629 414021127 271270662 659849434 305777172 264653448 391438210 32877089 864492629 200220827 250115087 318966047 944845829 460071379 367737504 393404240 878055488 982476218 111220516 595947806 816798009 851055470 124614305 633392337 795038732 658069238 374095315 941221380 425048308 679645685 480424388 658331168 887614635 994977842 407564147 11014101 393685815 384069047 909405379 893730970 414289251 300300101 312336743 564601775 60011294 651191593 225685403 89683614 496284466 290460937 717288332 759498085 61154307 290088478 18989205 127471948 263406284 692308640 838024665 169459674 108733934 767979157 674217267 12184602 11285080 461561650 136360002 606599224 269917943 578129111 770047258 739735638 229156751 240440400 953457809 22576932 681833349 31670126 933796957 567512540 570949084 374283741 606723537 948491810 622033563 942111046 846564055 533195858 140493221 379323658 60419868 539319059 247412090 149574570 359457291 157739402 135216366 377509065 406567518 416407412 792780643 91599481 309569073 84778270 644971540 180920309 391440889 430162874 397092184 735265091 803573824 701542280 450545891 561215456 762446280 312469456 358315990 878960997 492859354 946911169 931609824 128497153 48174210 173094942 394530906 969382194 910517758 332138876 13872910 73134896 4409238 168439262 271401659 662931204 797596729 371448790 626440877 994046546 820748669 963341803 385310688 179301527 321678098 479763595 527288835 626694048 432919603 312303619 750806667 589282537 432973871 571586065 622127268 922096624 830891811 430292973 107432668 929319350 768482504 828783265 771141417 736093063 179863901 520084387 343042305 144689692 791592669 520889818 846745409 566643821 808770510 704019980 471433525 827883610 656412490 852707056 170125437 750768689 832581128 168493437 29175032 124478775 164615804 759571818 987676241 696379369 271462850 142747925 377846817 374286539 302138171 201042127 239089370 142159201 835327259 344622276 716905021 22638266 910406746 329167593 943539181 273316108 446917375 119187122 279880009 670112295 85705147 825688931 638894154 46522739 7911644 91660540 901226718 917297351 55642394 685625530 559262865 432173403 153198853 297709142 454041134 345783957 190618314 940111724 79376623 423519188 368287060 736508354 489468274 548269822 36779491 514780472 340890923 776595044 235397508 472244633 314728182 471195020 785044511 699881386 496380155 51922161 76091375 223875463 283290243 47535819 610734544 98907989 169221459 563036030 59382110 868000311 612405965 575651587 509937183 407033780 706842159 237573734 684769443 758747097 745239412 704318670 95547720 266942434 951260792 518396731 483606295 865046165 749374627 932873975 163188095 699059559 453498494 492637905 151184876 735859934 541591354 277310902 609248989 360851070 238351173 545777524 695703525 301271546 615212334 295976841 521044517 348879235 572589312 129364655 784312669 10156103 139551865 489204794 809267923 500465750 993690077 336097822 936297534 809996325 543984581 884871075 465573448 657551636 366629740 884789295 431336292 592647275 733839063 952822392 441318691 348616595 294363740 839907184 659368642 543540952 395054626 983539713 613756204 868033043 630931611 843434164 694678272 820070667 116757576 993892240 250428763 492089191 405013798 566748983 326337468 249269151 944839197 523148309 22433797 333823105 276184930 219482754 727949875 743512315 11822036 445033083 849152214 267422213 24169143 95145011 885519684 302905179 33117507 436731134 868815975 638755904 544645911 732375065 126250568 253178259 119773247 607598135 348231121 268202771 391039715 787586757 152788645 467998046 808708240 744858999 299540477 255022337 367126736 242631321 41685903 703107887 595983925 300276039 470508275 222218514 985253567 348002975 932619060 814928171 342033099 981321967 628575111 553545195 133271129 64035324 895096884 465445164 821785394 25225303 279578530 845526328 621077281 934211222 367409192 758410643 558838274 413661568 3263870 233256088 984712334 84511557 806011555 764216823 993495849 473560362 856766887 886960200 999959444 370518745 594776367 691631565 641908229 487716628 400145364 83202979 121720450 499042452 950618017 211743993 69237452 186060565 432046563 697117915 4658167 593766392 93071931 573004219 136074406 519907938 587505178 131851417 37211538 405837828 518178631 777404734 419711610 515992918 854730275 292966826 294672775 272247641 468586567 258170908 701988597 433215800 601293095 318846580 879795777 444132004 973822899 173372162 592122873 852946412 970087708 978636610 398167731 3816604 346626551 45625863 843953501 607179360 31658521 902591581 219023839 285472039 808011590 630782719 53506224 563923660 703429253 977685171 13856039 171468657 564977238 904167523 862911745 463080714 172828050 18813760 962522613 861905302 966957062 765753011 66725081 790061616 32851735 852199365 860153561 769104949 522467739 116691308 484349825 384037600 665332091 724777323 399432332 541260768 414207819 992845681 716432376 296142924 599996467 482285836 650451229 106107897 369078734 245621860 876785713 47836747 403232751 268564464 910232403 724840273 815414415 378361151 296995450 503766540 286877958 421879673 699499748 510028968 940634491 524898400 239382726 311782831 361481976 356077173 458929003 959287804 815555251 418984078 8306091 351287703 390610506 832658951 720231649 921628233 79272064 733946617 370081652 753573574 94171381 490319951 908198696 576657400 240855621 490903504 27095172 899423366 643972822 242088318 251244246 888782163 998144916 895179889 360182399 345267138 632375354 704927816 926812028 250318213 483552821 403253737 968167670 395482332 215555965 474581187 588757760 29588571 943379239 919014015 776440100 148092127 297074471 886280899 697614452 654548800 303455144 24139612 634875727 238925023 344623599 18221061 173596500 547690668 933779174 71508123 274339074 899037854 173576599 955391296 84521764 159298023 393875223 208115840 16033984 922756759 480719071 358158664 67896892 636624732 861652625 441200917 854545408 421605429 18227113 328965272 641090473 657466754 225957297 598665803 613090575 475043136 777009913 307969596 597005759 540765439 90309250 62244717 205694595 494971866 775386566 263991152 326917872 638481914 592607770 257297966 821233578 193624907 368902504 647904034 67113072 425176637 119066516 889025422 206211870 90194306 941389436 587291209 333107521 187045331 204854783 881532349 192998276 637217901 523151381 867788788 278575578 433712565 609856121 791896723 678344403 471169289 820253185 96570347 246968197 265412812 287856505 265156093 562399922 343531282 774958144 981490650 194641471 859849687 961253075 145372421 388847469 514922715 579764705 410748251 7509133 238665572 82080578 300765394 189967250 295419932 847040544 994497486 672396897 302146375 142999407 143368890 509228487 532685175 568364864 173970762 329259224 485475365 11023966 961317401 791151781 137808589 549188019 267874366 395265615 633742543 741062462 70367341 461044995 347140624 160293432 289981424 986280109 564545037 709306588 723765877 811602789 300120586 965428867 581433198 646392127 297098563 825589214 230680236 137370515 639812589 511554802 730607462 462945905 25220796 200999700 132449146 276914741 697563919 723241186 720054610 440596860 629485959 964680507 220852651 519075411 329054019 678267308 80090207 699795982 491901829 887097822 200239605 696282025 260569580 195771607 31340373 54989679 205209295 854110545 786538854 307537292 798799800 170545306 621370245 165080396 664738653 125902132 927498405 539271396 268148988 850417275 828410609 465717674 742601264 401374380 971283599 81256922 950576917 943296937 789169188 122088901 285620738 641166346 644347758 938416161 17303026 715362896 119143296 27255530 360010476 204342314 89735921 699099918 207834604 306248987 451135587 950958759 826196097 504535129 33206177 688128145 55941299 512114882 669782646 12129653 119762528 871457431 237407872 481393630 301159796 154886160 343758575 892231026 22302251 102312311 435033836 196411204 484362536 704174285 342856356 396964625 847484834 750532421 863919865 319380682 472242712 343310546 137857539 995471687 309395189 234296498 753354038 52516391 793671544 22528181 908764866 380324487 281325501 360689586 191750656 364039579 140910183 533228071 276702514 330197334 178470205 777571590 241228868 541812607 799330966 224645850 707621705 336054996 896388790 398776902 53077772 86390297 842296526 955110496 415782201 645602754 737257480 869579851 263013485 882839134 43155157 359124933 134291531 479350185 271996644 222962350 720283576 483348093 167141228 14532182 234446765 766074774 89900645 499130994 27589045 342176065 128737056 981512746 763005125 872292293 267883876 464347837 241269940 678364140 916762611 924877369 162784474 833387364 213097625 239239705 281930318 804457724 156720942 738280768 883751906 404471977 281472190 271877113 764207220 202538973 588285328 941936757 323354217 518659023 608803681 585484110 294421071 884219058 370759716 975603203 341812914 463059175 650965913 514759944 201666622 881648498 33074637 924073222 991627246 353560008 623504859 363015347 144250097 639691319 805484136 190673597 956754430 38798342 34189496 439167912 947603186 731221410 592682375 996138540 129105073 588605128 872083827 836018860 700859386 146248258 325025732 254779018 772150606 784713469 964503295 774603483 174131024 34374546 786356955 737898909 383916356 110156669 659558098 893781503 352601236 658712392 125298932 952845583 969059880 911493423 866607032 691516895 338168086 965500825 991919158 185475530 832336352 323861440 806609276 14645625 876530560 541063928 367809049 945667424 661460628 688937971 913436646 595359894 566168644 314679874 226215747 711897832 464980522 528358898 861103003 913767752 629173351 825575795 19490040 839906286 597822925 624188615 605304800 274256924 457426016 679177851 749282335 352527100 900943230 57838438 777267802 669621962 661718526 895309914 280285682 492950649 114590494 743255254 517261787 832729710 142465558 613094983 822642488 23133562 700707468 311843978 274928756 86948231 782963177 191717390 235379426 904105355 415625224 557733975 335332844 171997698 636051868 294880975 826240670 473128253 325471399 894143942 138359954 644685714 924135285 91695697 928839311 483723627 397174441 859827043 946780901 321102923 477445985 414902543 635300095 776844488 151463459 878354250 714825596 860671731 618249797 948601333 777461260 895128805 928794395 745038113 357046908 775906392 494265531 563614606 894970322 716089867 914865617 635064491 213888309 272130685 540933301 978920616 466115560 536382868 411854455 795374800 131320734 130682459 739399884 571389982 707687336 28778067 132114976 693017654 710074153 834283437 511527998 867342630 694067683 126045865 292135829 425907008 64448749 823824966 573475385 806073434 212342079 589848783 707528074 424149023 74492173 109481265 800304492 336368199 965655249 825813720 334156906 101548238 683076901 627685977 128624735 283342656 250389185 213627237 567082169 35247238 969097395 532945673 241248256 19572666 950964437 749532940 604501336 251665660 676931867 275376551 277093175 334037670 623210795 311119535 787575751 415634258 282434270 981107101 430068126 862314057 964039888 658664842 789091550 390446498 374818171 408545471 307372710 434726024 662441853 761953980 517066871 788702624 419322842 678905467 791194772 170937836 421159460 923442482 596467538 222557320 278392290 716678418 779400850 327745928 719580676 527514830 953600037 519065465 198805306 424133575 478309422 765820839 500484033 625284511 367275307 414048985 184435214 364763808 275562854 202927872 110232778 491359685 561611057 572130996 127023860 757941120 806522924 736816048 394105444 17149597 552201979 362546868 609090616 148306807 961710700 809958997 337378296 690852006 613659330 819878486 913034549 789721211 485022157 906407132 622617906 479300030 331349536 651757259 293605282 571441971 468494925 756381968 972895277 956398012 929272060 819641135 300818994 885219098 834707718 940964376 468605849 584190712 835919467 767163440 109417522 500904868 200576180 560598763 351676400 457301217 670722279 286754450 250020793 892570562 924725263 686016024 158617443 173976151 537966078 952707036 274492489 757094709 702438935 468257490 670503476 107207533 498072186 916199138 861112569 325616668 722368090 955759466 371400521 163199497 606825595 872441534 715958971 690158214 97481045 127626453 186527945 530422051 380394344 851562171 810537913 254353158 709887194 773512272 647016538 401154846 171257947 150363494 314857171 786767093 571067849 799058165 629975770 823496928 437324856 176316939 286546941 479783227 514672554 115826999 232180552 991941125 381935974 622968083 260796894 390104099 736780315 589317389 30496140 845079654 872419555 300785169 909391623 297027054 776597229 222643966 767745869 466391670 227706543 751408788 252392002 293523798 511703145 422266987 2374781 946428572 271923922 7504616 161072599 62920135 290185503 117946830 10304008 813354504 484009033 400183917 552752462 632369210 599461725 569793957 147972203 290276908 119302035 295799341 11926258 337875986 444935132 676030884 552948232 841408151 180186561 292184522 583147721 958422835 72233609 604603897 813786301 241316256 837784214 547867687 508297912 54027585 115254670 558057900 815934722 437222373 124874064 406211303 500366595 3508460 761873551 375002897 933031762 391180686 370214644 208866593 801243860 123464564 484133648 265990945 989000470 66733152 384097970 833745906 713004451 105190360 622277298 991030863 612741887 263603818 121040917 769443104 974617739 732081309 823875612 384181706 784089482 721427966 79357120 785988775 810582809 197667268 679520575 298109254 889422441 681553340 395489091 83296194 305779453 695615111 592701019 731387022 180753295 613538337 442692052 617926247 191187375 961998880 353541196 389968661 533956263 726973539 890114671 332480182 896552465 998530398 566668486 810909504 317493160 41349065 141860009 458430136 660164933 504684492 990142265 317903252 499896362 947756958 432627085 391606331 847218867 529261630 260440648 857581132 400433103 698234819 944533558 673286078 293971387 463064643 142444186 121183125 927554388 166633522 13950555 315525648 667948933 514607941 456545723 966610721 890748555 962634761 39820088 44725923 413027068 975511377 924257796 275131916 63594606 394262268 836652715 539044534 264525017 993015962 336618329 432059193 100420776 927624994 505902883 401751880 73672862 990368619 324935198 975764780 892538992 67892193 394608378 853472508 106941505 176193012 924758596 821432779 510326720 567544790 618595636 72753359 286544996 739782969 439574402 340229944 223836912 518633283 398471380 833749954 995149389 514075171 445102021 605649977 178385559 44976580 536666371 737685325 126878211 473972755 5996048 503898774 827282413 630579613 681151299 682669618 237873142 361564699 614956667 704995605 892439344 491667796 644030671 163530644 230559764 290989917 488929275 872313529 769143258 866942598 991019034 483757351 599131922 896636162 399713332 452048644 192755111 855725965 655477868 656238335 868977172 401654824 429048911 224139466 535184755 377113159 280519770 765457940 865630627 189580456 974536928 682174490 180278746 181286468 176547131 60412478 630503566 145141115 592719910 775564675 912180192 968872346 671389053 423653097 835657754 827442705 34539027 651959571 351529196 512679979 787430782 262996556 666784424 988198882 575771722 758816185 351136120 668075481 823028388 554277014 330060647 615517550 521954198 232016656 569221720 861121600 152343162 875660661 98810195 481019100 700983739 856335149 813559079 162103696 142457580 989558452 339069707 212395580 647239087 812634405 331196946 944512281 468816242 76792901 592112493 696229453 318822006 467337428 587362822 747850599 200293247 431677316 822152198 274531263 202767700 797835394 429480210 556394674 522634304 861486781 855568638 591016943 434046730 903210614 170617083 688639863 144871382 404694334 593839517 295759443 96368928 645046883 629943611 113008556 695931799 787569258 494277062 115641014 311964850 42468886 370480217 813321975 584300494 665946814 281055780 960056753 145752116 904600199 673603904 770259356 820887579 785233565 924892628 401640803 507032594 204885056 302741837 325813811 292375712 753535060 555598503 466051522 723727075 255925892 275672852 436908169 354275355 765183140 560739661 415006402 746695508 977732671 31453946 695567125 723034924 265391904 862629972 904386095 802260531 722995106 243072401 741166648 209786645 530789204 848259158 593016636 242205016 911679593 684719029 593054662 648326077 790296973 262167315 666012627 963328303 76086923 373046861 897236773 90175949 890130 753102890 543930164 596999396 117561409 113635868 545995272 678545447 192568371 831805896 778933689 573273167 813106303 521470155 802055422 781455170 740327842 548644701 902257533 436125413 51075439 299970942 673207961 302411689 369281526 205291658 474816030 130457649 106341202 239769598 64595153 915202120 13154909 340248111 172354469 578665951 742137054 822390027