8000
264704197 120999146 136987924 40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703 340240729 965382636 953292241 144902419 86035524 289571086 987645468 423893886 928104871 464748969 105872436 123582647 242780928 505538017 199537013 745991283 983136444 65304379 842202106 646596193 140145001 630412665 134706415 170189559 917006962 498351627 78228861 784928508 545206283 276287905 127534371 580361498 602636875 833497706 569752320 168745739 687931378 25556222 401296664 903079778 244718550 696658577 923575834 20801451 728508574 144327567 355924229 987918030 767675763 39770237 690017157 35094958 619519152 803294929 322191158 334280933 412368057 946079172 696252934 727024412 429649275 739609644 879769415 84017875 429336930 578822041 559811577 192014409 783587083 235524450 277645214 641105035 776026757 478219070 115129181 14794716 647713890 894892898 720571222 16609338 29190516 796633468 940732244 641040997 243193942 968755343 956678858 9273458 747543114 522400393 605708171 235611799 713122606 952769734 230441676 782661943 119932537 618863044 263420409 832590609 341598454 889752736 346283651 906815307 693782514 787563199 656787150 558988762 325699987 408388854 484659329 514686813 546683978 168335178 925036722 876453250 928472013 452720553 11844689 152089336 237462880 322160445 768682370 968998501 643437693 43682975 50514865 225072892 729100215 432384534 267319887 944916772 470850912 634063725 30265497 170224154 233237753 310521575 363661868 30383316 169764888 450267291 509435980 637917173 871736242 398793145 910647926 108164902 535373865 729080956 796833592 454223174 403988143 945062274 621479206 158107041 272551814 767759721 136585361 638455939 61417522 286340474 221735821 57584824 684185411 747165460 140519367 201499817 652532397 746971523 597836965 403721689 956715523 163056092 661594742 716321675 768003151 590039320 568646343 716350006 451084111 528630621 313480942 118564698 359276034 829011041 701887370 725160671 666415978 738132895 114167505 659739773 31924187 55285186 560410488 920735596 860283017 130521101 634454758 758692855 367621879 37543666 929265562 700477795 673784691 852411165 71823458 547390766 338428922 269296694 866684149 689572434 918907490 292588975 817571123 959281983 237458599 110596904 240580147 243465869 754150540 417951469 281530082 3734782 837883412 802111064 342905930 634546070 489807159 227640803 152130560 715231872 928498199 246388488 150318222 849120860 925374177 144892127 398434867 729447157 621850442 452366143 469546842 539193693 387659516 713639740 534692970 516992535 857296504 338125822 866018073 835065313 510544637 841323884 623928018 263447616 97154821 157189035 626682906 850977848 865147377 547354125 291373786 244996624 939186671 470490191 110958524 736419272 379219571 498680309 361856442 100482924 442510270 773429065 207078157 857344783 659400969 841728390 692474075 187583662 175274604 203919131 521450008 542450577 561050789 483834181 666635165 281236448 744939400 606001978 339209101 825332344 409340060 105053325 334942889 701010888 52772808 89618199 62382450 312651094 267282041 738280309 813796994 153189966 976016018 645498866 305360396 624826185 89137985 804282524 278984850 215551309 168847257 594398943 553423322 316656379 938695783 362188486 979254770 615808805 280079020 162058869 734380867 181183810 369453245 10097001 370504521 99611572 71283549 375804845 690139394 298702528 556804228 57525845 328898093 541889825 375688946 127439949 637860162 88758221 860742112 825399220 195532272 296560866 898263825 226507934 152656046 744845166 27581792 599790352 363219948 766909962 542625171 231657310 545144535 908129469 857808700 828842600 58937965 640541108 137921815 28350886 652508654 643869973 722021608 678993723 841257574 133264624 93113222 542874973 243438394 898920791 87870405 571326178 595882116 80857922 669576241 881037234 751107032 508469231 307671666 507999415 520756793 745631224 52014388 230352221 525650738 660315722 503767010 204996751 276291221 664210989 151320875 599909211 925460171 408720654 240375863 829642972 167269687 511882951 651482680 361674598 595158462 843234786 901936204 785745600 501130119 423181627 966641925 366621967 608618061 936072922 771638072 796521561 282814428 707172910 649949343 222508649 870914963 453849073 301814340 446156727 275123659 405340166 639133553 908796254 624069800 989896706 739052214 367907666 419326829 798705655 949998257 404075252 381212131 844178042 667444605 85885665 866208268 221166146 963673720 431514130 572154241 589291507 484046818 76028159 331125923 943448847 963269306 950314008 454860215 671912499 631376617 421669677 686364693 493511239 243776850 33178914 771394023 705494253 780656564 950203751 401551808 911153562 222352670 713096228 4873554 522951161 898293860 876305539 713583463 169501973 692354474 590425869 138797942 423932057 89855279 953274951 36055194 583694890 284557380 125583279 109265482 517158975 679505068 899086402 30153826 152428854 400940805 814102622 387312147 863423383 522109047 930181370 411641248 441522916 638436687 157747928 462976946 602205583 324007774 608422754 241156717 927009838 525235777 26330288 350816998 324804570 64281672 458859964 757421184 484881735 231860715 741853637 100094374 413476035 861509035 466379692 737395667 473100877 485500327 883936894 566698676 853582737 771426223 335434231 892162908 637795835 374816020 216075739 255716655 839738025 818202475 636086218 292502906 760752795 323432900 319170370 627815219 116770363 270748787 848522386 566176918 269382538 760197523 716607965 269854968 452119349 216095588 551878799 561995103 605114428 347367663 585069043 796207312 976644436 168236723 526468099 39759609 169964459 665264332 85791246 322395252 811953378 920480819 73868602 901430342 642875472 819534976 497343164 142912010 159574371 817081938 260807988 569032646 461284519 931522758 357440133 92109771 695786347 988662715 997640683 88222446 901367480 731742988 163841780 795671284 106337837 806399633 527279853 85692509 825600827 187824050 978085038 662394583 493339852 956562731 339381673 526029630 893915970 145225888 807361520 843153344 237366813 493349993 584803239 594170986 919760600 109872641 162436711 479524148 339756055 612937461 118527668 98267328 610994557 89281857 974945370 695401048 488129989 515133051 652937312 917441227 877139 82935094 369633655 948184250 720802111 364262472 537818844 418022911 244117671 184035561 902811118 654967618 916469760 642095996 634175117 537000401 384222483 441025849 754252108 675523106 32679843 818238629 282410430 47210910 316296338 827369309 740322912 858165232 7145962 834245142 355398069 447978048 322237571 280944444 129467789 533468369 896433231 245263616 269187614 653873631 804440053 301129599 224523527 859394320 625589344 151351159 485191725 34390845 720556424 552205755 302378597 558013827 702629473 596451847 589022172 635637210 166517029 880745027 229409044 663049001 485274459 244268086 135905818 523871556 712303460 234812541 875650875 400756756 940668164 520949196 119219626 375497475 770641585 893349700 810194255 206506864 518646675 94307197 284576740 839760004 944915557 426487833 651422108 245042497 588680664 112770657 54022602 253354221 890134815 540428524 563498599 286157085 765106037 766458105 830410082 156562027 526645190 830082524 224135858 975930688 151352644 730750936 891331027 393297837 424882569 183509738 935502917 236199293 961675598 210839789 724016131 163052826 12296602 783841626 498039791 72802301 186391175 532449389 213899035 848004693 530340286 5263801 204683471 395997628 488334502 616630150 269207415 693423687 281726246 20506370 54478886 507281136 160954027 734642588 690886710 963151748 554242922 969184968 734914985 834765732 790446548 418129336 669525757 769724940 653214462 340192294 446159633 818417818 541094465 50958912 318296181 69311348 723009320 18516670 406755068 326864968 390541367 407070587 121389775 685191434 280341374 108644580 375423282 227166411 938363350 750969264 374953701 492206462 481127343 729265460 953031114 854789452 237031361 955067289 866248813 228444667 649244495 324406271 120797077 314646544 58959399 3288366 854622117 468356745 979235013 661217923 520611197 686358881 517707400 338566459 58201392 815107772 907610260 767597128 499736218 545302930 627063788 460040357 184461369 606809522 728341852 668869817 577081132 222858265 591152692 879521451 403609733 818954775 373903993 993650663 67520448 295570354 99912702 862739997 395323616 677553429 52838932 40899335 74571117 987025786 980274186 972506541 274079910 688510330 857273476 67448884 946779393 59277318 994160143 742529501 981347101 343974824 696929226 335495729 610436273 714037097 57759471 388800742 589706421 973148751 250362369 835072764 745491860 446644573 679685394 366181981 920499234 641446830 637634625 917033537 350931057 376037334 429588715 227044621 774188754 428291718 883994450 138116461 365355333 881966517 720462542 891208039 897541378 792786923 740165942 736566640 308601023 720142076 316224772 518309911 968134725 516682261 194774701 375083203 581689790 172010851 974083704 139773573 46131932 614258835 451778839 85044254 54841683 371155842 32688198 227359267 627867173 218086483 259886832 87690949 552123679 790431707 365164248 993199867 214438533 525514196 717361563 275267118 498031960 922279250 640263313 55184923 853033845 892457772 840592168 1497454 939173026 200095662 386617574 250518793 905424128 291020254 318554790 182317674 868171036 759958543 743402101 964108290 272590670 145210301 558711506 6431291 576740159 346371626 708335123 108782814 886683076 639620797 635280149 495628851 708843881 925044897 751828618 361829421 307252380 296901157 277039009 806187232 966648629 827868799 435384030 946003994 230111596 254914868 825033134 500859488 180162076 361262826 920210341 260278945 365764956 488480807 345594555 468285234 624776852 303886936 611534100 579438333 656556351 483966138 265187640 107309654 428717427 198663185 157908235 442044028 640996606 436201726 193439789 190420492 261241586 665487283 534264383 957831147 301089289 11767269 791758022 583708953 460867723 414240861 67023643 983581695 276760071 500438783 234987801 108274186 130434554 545097741 390697210 365340919 145063248 498558262 282226328 239181386 296809897 904454862 127684268 41286107 674661093 291235376 320030778 184913596 92560479 952676999 55253119 180546445 30812789 554302058 695132519 517189915 703388469 974859180 117868168 270053958 896327490 376709502 673632190 767149833 881704834 964880104 302535903 602001468 546861009 97060264 671912025 148983304 344455096 411219983 53355848 906949892 653950149 722415925 511757107 374955009 463044908 59330876 192234027 159152727 172889411 299328356 294774001 285003714 515236887 163104722 932018058 50222750 333718353 896048300 599823310 192971476 229094308 271233381 987654110 312395025 663010848 656290079 992357741 513466248 402349816 663823780 261409511 586869300 369789943 902069349 14172062 753661660 95943082 571827529 617837612 647268509 830257029 890038098 169851886 565844725 776190216 598197634 503245086 625559816 547964489 272209697 138529390 513923574 654534785 205615967 943138496 658568557 630241852 437709671 18347837 764150335 345049736 764563407 562873877 924757857 767271797 264847882 208590218 695763092 486722998 753780893 411412053 683615559 654504861 495572504 863462759 81649353 156360972 656212310 344347487 522532087 674322957 772754401 382504813 283637444 113056838 818598886 161653117 403319679 472162214 482206539 819855435 965366074 270305618 568219033 784120490 765660275 766570706 164475300 355126344 699482278 495447045 444955096 489464749 219112219 65713591 838097133 251937582 322001531 256848551 188960288 767550036 272345340 479200957 87352390 99012961 445287289 168314448 275664509 563514901 167159908 779883195 346397947 392992668 25760189 702020838 30079278 192996196 631509811 272423795 815534631 210025365 491905563 584976434 936207830 123234176 654588759 460569576 107590098 269179541 547297558 574313044 925044428 784355441 679223879 923769665 568020502 365573722 354787353 675678625 51127089 57523374 694331547 375671543 462603446 186200699 242959815 477423230 676517257 783662211 680333413 292201635 276548710 926598897 374772176 345015913 359835451 484644311 514191513 75812147 106726487 792961294 986069221 811470504 326844789 483541822 167890485 878580049 728115681 630441652 323511842 405749267 889386649 70867570 828112442 987828243 881979169 734115513 986794047 415836684 608512906 225712447 920571729 778530011 40036682 443105047 641823414 119124429 982571066 221325391 163891898 793163035 805231750 97992718 293525566 39546955 571072741 776098692 407240324 488427067 649107179 316884442 945783492 444543766 24383556 648574126 577182746 397938019 842501265 368297355 222133398 727082060 603229813 233905817 126624795 741115301 686285480 849230288 792349797 74151035 319412349 760025767 431058587 402283708 989951581 951623217 942880054 7787522 96318278 141797036 824698886 284610016 324189710 201229468 287270550 77076299 579587745 11806335 202688136 909091606 446724464 346389051 875774799 506786030 555523731 343186917 458821880 737177059 508439840 388173401 537904214 697289446 140344383 321567162 167271824 739604997 704612620 559705514 560600261 816650958 119129315 315716520 315098105 429778464 309576236 719226127 111911609 890698203 293353875 605073599 724820109 182903306 651402209 634001180 886580303 993429671 83052065 890423862 921250461 273032776 81049760 797700534 960899906 580958888 774143041 547283135 755976733 432350378 52630965 412219035 785236117 725905096 17940348 319555704 397193188 406578863 964729909 264285397 243856996 398903836 138192750 775798178 952040907 139766927 42555255 983120980 354637607 822016968 715987073 123236486 723820453 749169788 815937448 578290717 654556320 153256330 305417025 491086025 52147732 842087012 659078479 738686662 324940706 196853892 844563438 421152620 727595757 532781024 676989925 337918799 38453609 921667613 939183211 509076112 267396961 926756361 383999439 565923289 778615180 301446091 253506461 586064396 12390763 631001458 817994465 127418462 948760710 961866289 376861418 344868689 700995628 837948064 530851682 670096313 921140174 467511046 303845907 363435738 803126080 414153414 206085347 606879792 873465775 202584227 751458982 572167891 907604234 627825851 403751021 603757491 582561767 538929085 532514767 918832442 273793674 439545813 208706984 650308057 784517284 63499080 259686246 889404673 38090460 745132770 235645616 134235085 551615214 614422193 113289856 110144583 189393771 222851359 404385813 17742111 167061525 290312090 717898759 115758646 98534195 761939082 141885121 775404672 108358750 447055924 461909077 490104749 929540101 890571488 391884765 711111526 652668063 678065313 994928440 646336495 464605337 609375769 504389061 661507256 110207769 929363722 963643910 724816031 638043775 542264669 634463236 848811704 170548120 260099213 675805453 14597411 413462606 191777371 152629222 778401429 435531976 848079839 431864925 524711881 654388006 378722728 842459397 674004065 477003614 582311124 130496785 409301425 855179348 898250815 27643657 768502103 170437508 835244956 140741261 282874134 357330746 296842355 887401070 676944985 836878078 682266768 906940953 317727664 305555510 385229877 410794445 413596785 371349392 312595583 525802823 351488546 581842461 193108793 513172959 742969097 197479318 513466672 684540552 581667856 281666870 308886926 353283426 279331980 73384035 392235728 962276984 816070716 47319047 276169551 718888801 828061975 292807821 744971877 558208713 141260723 586827608 194094446 943252358 905959970 65358326 428198132 934715415 160532221 249299128 823914025 981118344 404704422 940210457 281536249 620515663 565924034 435329080 674511619 843556311 872397059 336766924 925952432 672152033 701182368 898111849 395125956 477218909 64204492 902835592 103056075 45460000 316754519 774717766 18165494 111285461 690113157 161806378 182269284 262075956 939517373 875305212 415615129 476865129 701947666 530261884 833033641 229045521 733397390 293132279 480186135 339716824 960114322 418090298 480575771 156894870 268102167 727480484 641859318 423543470 775549946 567829123 940694796 624872739 534188976 432894823 207766044 730050753 474815408 260996697 494933045 81449830 971073125 322360557 519744743 541967202 997354483 302555859 656407788 516330370 33506266 231664691 932131618 318648158 213370101 39511963 573890351 65352386 555437698 833399181 146843857 569930289 137108021 524991054 533187589 944979618 738997324 400083704 597809251 37316259 36161176 491053045 469690918 404379331 541722440 132172132 667553250 943298810 703102786 560416375 690675834 642943558 984149269 136256556 350360900 191999255 961634401 213042967 969692567 892659049 997465186 123588691 35748414 556016968 975983091 50024237 842461653 188767486 119626811 791397635 460587862 113127673 261448246 565680427 577967594 657882869 100506446 948502219 295922599 965195635 884480793 593377270 473570914 74669237 472369932 808785330 233291624 966128928 884299751 825125468 231390215 546928945 305921876 542112407 308752051 106017393 245157535 564546573 417932628 34894532 815036193 608877724 120577986 655897903 66919316 689645237 606602531 269399628 120871574 44487597 894559263 514901843 967867598 232915852 722799697 346343196 27297099 476080436 964176179 15229895 566178879 819354782 435864459 840362267 281184041 545919899 315806632 962431831 357488356 648928609 180031299 336355841 194137048 228498976 75400441 564574044 531077556 489585016 111677669 11461595 260081353 208783720 901894367 382445488 883192942 375550774 230799997 329992443 386451291 348130595 441109663 320876101 197577352 155540460 468601844 230673560 935363795 791479583 975232443 321142871 345360381 280984139 64126458 479913128 603726262 917453573 631638042 941432199 911452460 73990283 975144117 36722761 670374011 212353694 70187766 619094713 858278401 479087663 173023464 337057372 557671684 760196002 685265662 118989339 231032472 389757267 71849023 379914549 873131289 49964074 184329926 787023735 98497972 180449832 160212249 110070651 912719038 406212392 155963235 637901680 3244866 9611948 493936432 701827589 348063204 826123612 974896259 117960591 795700896 407813943 84569876 452584810 2611725 277132776 94992637 96457191 325034220 761351604 215097964 335413396 17904914 446529241 307341439 67354819 391065991 39591635 451098500 625300851 785395967 424924584 229345829 18604129 112605131 930722335 375120520 266777004 599784041 446586182 278134439 494890163 472107521 436064367 229006058 311673964 804624004 812345409 394252349 659570032 467555993 738136526 444494497 493275233 398696524 321864047 87047267 960688052 680724165 866554511 95161217 75629141 814337306 3776284 586946581 409739953 511015714 467802009 431806324 425341654 795335667 840495237 818448109 155135801 487872273 269087989 485549703 462335130 993482074 42176726 675091629 892977218 889017283 978315325 123833309 365969421 89979165 706923528 54471278 93171431 935933743 994882576 281864615 277145756 216845010 938886903 139494156 75603613 515021573 34438996 702190980 150372707 52635270 757693432 872319049 171697723 820366044 941351475 340925843 255576788 6254788 137898968 477057142 420384260 374006933 333397217 219113444 510747719 396295906 372093459 898980725 436147482 441829178 950601441 631200816 750123729 902914519 111895213 860752610 961302668 994914344 51436440 638234037 591035354 953925490 831483645 619094158 397093576 479609567 658850278 982160371 547980418 359848584 374779445 814226230 155634182 719633048 266881150 54782200 58609363 14362184 798907423 181687900 585834745 265584848 322533706 565929321 624863139 278959661 393666739 424826253 20882413 291497349 121420281 282242892 784876128 639834018 465868689 901977335 536674807 351588078 415236520 525493018 996419939 846586727 57737408 146669256 271494423 2939135 981175811 579213571 614972695 12570372 880803008 833577813 452615839 440271197 344418788 463199645 4891481 562942391 434857558 397083723 647197702 16327666 18461866 905668851 939239267 764611428 142658680 976731933 306989823 194555963 888593394 264666538 571791094 1337740 918220616 963239896 369455436 11018699 78173249 132497807 691857524 926273771 681918482 922695256 241952079 470022760 244216884 956088634 218551650 823455678 882299995 494672960 362502383 953129724 510205937 918269420 199826825 593570260 258869525 85830817 984397481 251527985 635820224 835148060 426109311 386689723 469320813 809212527 7922529 38707894 416119716 206544715 550244313 80777816 666101675 618689758 696080552 436650996 524253322 458125098 600085958 4778709 135857570 696372127 196630640 801476747 558936033 369608827 660742262 852887560 215635539 159725465 558205324 376512238 616256395 436285204 847407678 124837664 683058424 208209016 791349868 293734471 347876222 5380244 905731349 857602433 580770526 891686686 548140130 170651360 208298894 207099524 778968423 471550284 718132277 94332880 361557856 654108857 226363858 352591844 471724938 53515551 905791466 137253237 830985165 861622901 847932936 157965211 278384578 573726654 455622611 201514224 559157913 854760352 194361640 956075649 396902335 712748156 110683231 433574043 215425121 486213228 367164480 506269940 929923754 97932012 884899594 781562427 905132013 990091393 592067767 49589634 17237187 893265442 15140711 525913550 295982371 213054585 614445188 149457042 930959470 298388247 691250147 390102127 212263954 97098911 361128760 463986383 711647725 249312941 612675095 224184782 722108456 542402017 499163393 232010903 664263915 526145760 391413306 85122762 560236148 697296726 387311896 345026142 609989942 705678949 648841239 223414864 319173830 26516458 38498984 349106418 349072293 462145252 868684527 877421567 737696098 70671066 692653512 549167888 766709739 416623844 951114738 979727953 761739536 467686207 266799832 994764625 751561510 682459815 313760675 766781400 282366362 587327145 878546360 430346026 33920914 534361728 96374149 441345947 576063225 537728096 546013677 244859303 564141500 659011744 920825514 307504929 464683024 942667900 99579430 368573569 275756830 932533228 197876046 434115282 776545338 916844185 88943831 683658795 131270070 199886670 873370419 145938173 72196960 509768421 701373972 147049537 685086341 944112893 882244608 608041664 757870207 940493127 827711389 933683768 975386875 688124497 258205650 831535620 857125394 961966874 403705435 573892069 688969709 515992018 188949083 355844485 197457955 571624723 126789422 313076696 960177422 944661329 514179776 721647053 120765986 369723864 19566463 135311578 563087172 167124878 559623926 312840755 547686231 756532742 620489200 350069956 908286985 373802224 123188122 437107988 508137864 242805667 531250251 844949262 749542510 732359062 345610134 253766877 465539822 602720453 296058291 496740152 285399959 554651447 125876601 139059395 455963172 249519746 53289479 127680827 871322612 911432275 328971306 905221291 147622120 806518552 793757889 928848647 19700823 77468684 273777602 172060906 846428085 731169487 474501300 514394980 371199707 911320984 473286312 531967055 102440498 919228878 256913461 108251499 335712162 682036711 794017634 338872712 518604812 353500207 674718097 647873206 409438782 197106172 950516398 367462304 892240618 322706136 350577962 585454711 610861805 333233060 351346635 938492433 438417910 743846069 870700522 466026220 582742842 186670018 354368746 427144405 626397502 62787303 434886166 397783740 583710625 290489398 327759629 418317194 360793375 117823859 801119601 847866606 643441463 14131498 320652025 618300863 722463421 918422549 818391957 361742407 517003545 59104666 547184259 744341616 192924360 186360719 218807541 452696211 240699332 161711952 648073637 949090106 34069196 77048456 458742536 56526320 863314093 746508011 304309896 217702859 294623607 272973601 300281132 469049726 845086357 794695419 369450307 853757703 598995068 657190067 487249038 933673331 568803359 598681470 430343836 833313342 464564280 844927055 389176733 477437855 981920170 372369481 921903707 370734025 943311247 847961585 137536186 235776514 771361287 55637513 795557609 898131730 241064519 340704424 616832113 707901306 173105518 84358576 817376420 835381545 229474999 190710868 475450433 200992203 688997683 11692547 345957337 586302994 640909434 388087111 350181308 510302243 768169672 987044767 303051563 256215393 914708055 574338928 774860239 816051754 626240832 493090552 767928571 646390499 425823386 584164700 483553210 60448318 972715608 814305139 952370973 322902342 657649925 297785170 413345059 336457761 257478116 228541566 910465627 620764843 754414522 959917094 588949866 499455427 59900973 52134275 240359529 228202830 89717772 124241443 985605493 701416125 961253982 898491671 241876530 688507069 544847834 726735746 429014698 4469662 87093655 339807900 471539418 388197873 466712789 573775584 8261172 59066155 74130618 480369675 371515154 253928637 490024720 321754699 648084774 478292574 872567577 163427738 649174283 321071300 740394330 921695705 568100957 291346174 473584726 121369219 145582685 962200390 744837167 83688444 118959764 868885554 577735209 863566441 677950753 40214902 204147849 459468332 123812895 475152716 605177492 553432668 803867515 504468032 437230059 975296330 770892131 149724999 215606138 632019017 759384040 452498320 849483838 960322941 559976958 728393738 526560315 274654103 579488176 366358114 276524720 358426968 640515806 58821028 424950454 213625537 751895478 7407044 148129145 95935666 344453611 347123956 213852411 229213519 272786898 691323345 743862981 40640064 843906359 413374097 120454051 520645438 953369539 898971865 397308088 253210865 968777328 972554061 94205587 751030765 167857291 463725759 940118008 119864343 121622652 819077059 158545197 454869452 360711001 530475282 95147844 653579923 589054547 264290623 466692761 327512178 90900202 275921883 993151963 130188712 883293374 233232444 870665290 375683587 32815219 328904180 406960481 702378279 19474838 767262862 860417644 549992600 874984413 877931891 119952924 742973260 787522923 825813838 194830775 256545865 973246370 287558458 590333584 10101377 233084094 849245759 469321853 367899630 83321907 214232453 942020731 960316603 945346484 602477979 228977874 360822514 577768428 364567558 799204876 376408449 461304368 939999194 566839757 249223565 121013797 614714929 822085225 802213311 339950006 530234595 640338425 216293989 787002983 940605353 203143180 259035124 585020281 66533579 477758117 816705789 679640379 917125526 78271989 699564951 662591022 854660270 369946534 505449088 10740587 905159210 157676891 986310957 367765143 800402814 885429430 979436547 923547714 454624538 155587152 714468624 253701856 408890784 122612388 384467715 824474776 710531803 827943396 780512075 381531603 709624535 673211597 564549699 770973769 95635715 918760119 192520911 582782036 189797913 247991195 286630236 166635210 248527534 760805951 618283662 836221408 317959298 863842537 367936121 423261492 746391087 647886944 742771247 785208889 956135702 842155362 794468468 201987341 287992148 974317661 72762559 182081520 777516131 614791180 454945782 842985311 863703999 636924354 368736073 53965911 905508662 943253433 747249675 376278677 52441210 658375796 839179343 748744226 796076588 328738782 982941793 246080455 950927027 711689541 691062719 156796270 80470490 258116449 906738104 444963698 450193506 573032303 381837504 2893498 137570079 908287340 784074875 335327030 175330550 683284250 317389214 156969037 889500145 675630464 386149467 82805889 382813855 112644397 328364587 442512812 685650677 847526521 204725235 49205952 150866896 300862463 292196981 592533356 300271489 128549342 199414797 126312600 152336951 849677772 2228723 863795659 126763438 149195721 747180964 475777618 874506133 626893673 533061418 358840473 142908517 777464392 713002128 131253779 475047494 51851178 63491221 337905062 404319807 259059823 769203763 761537737 545469906 401256405 12606786 447589826 291079757 344960568 690773631 724593365 242446936 390395368 761759424 364680613 971236912 60181114 270621461 30036388 552724063 846378550 922589391 365795615 519250985 211886191 269143767 125851375 445481658 390714626 889253725 483376977 633043405 914852129 511690397 811665376 115203772 360038988 898717399 320639035 384112666 603366713 664471927 106715250 155493791 988108217 275113853 910417422 834464719 114301291 92728343 538772397 955433191 671086334 519883591 490544691 406733525 679747185 385361471 736763196 219336498 172230871 44555575 529048100 241301887 573417198 429263391 63793668 237014713 387247606 314744328 540946819 925320397 856976482 635633924 273695029 269403726 503758949 131902664 922175289 643876853 739192392 452407179 87822540 819917208 246734785 189183149 256236937 979893948 575556901 108091603 809340529 124052196 992387115 194277319 586251270 80598750 929988783 280915684 120029944 877060791 672559696 733446708 224774682 445667398 41649227 726452132 847631726 118208691 453090669 26660098 840133662 306757871 946250490 307716658 903816923 188149960 700408827 145108850 569942587 820709686 207695792 939595736 527564238 48133262 771345552 60475244 139173972 907012870 104272232 626487218 410042167 382183666 262564499 763684865 777112399 744637158 883090642 545691746 660648262 738554574 317069335 550367132 276690837 213458910 511152387 855767808 3693357 101924987 870372855 81294911 798499560 277550048 144547506 553356792 977290876 204484921 972903783 21377171 340544650 728274380 962227968 203084549 115938637 405438230 437608206 295274840 812826151 853011394 625491108 991641181 854199243 370764383 977543984 95601993 802344727 422482605 769466893 453973533 56843854 241884015 599640486 261329148 33047930 437437914 230619891 994943599 561037528 23366821 852167795 849669525 735768205 441735532 311475511 565797403 677504268 313397574 815299241 656715021 64817836 605608447 718267010 617959333 3802907 700833651 558156276 798983779 232631384 389361834 279476467 790532581 864162704 94573608 439477820 851604858 800261559 499951596 20220850 57021516 261048819 702989137 85785995 442292464 87197830 111361922 521296034 378145765 351571091 81974910 488639023 275503872 282546327 740433031 161901160 279218975 144606384 511801208 536122099 167241006 482823292 17265492 9179492 557021383 547051585 502706831 406284210 193301634 884765536 637045196 290268711 928583860 200684552 188454119 129993671 521949236 701475436 650163874 579906147 408403141 602041624 899863130 424910186 427154543 410600958 839822700 531574916 858135653 529048390 997460021 146051835 829241232 182018180 990616543 181189841 841297094 719975128 210982869 862381861 325945220 287585792 540826565 943939576 413400576 781539891 534915801 696261771 2291307 800070396 118368778 357526369 385122496 387183991 506556483 311237045 617239423 290438106 962022287 821645392 592265013 370326742 121551977 730126658 542280591 118116826 134278392 181529281 56816617 974314816 138886409 994661374 626336141 899570037 642571859 810727038 282346131 230904584 417179705 173078824 853198925 276140848 374273380 241456253 241475994 106936626 285870537 86661737 278455613 282583695 370627619 522572238 763618793 327991307 335725400 380787766 963315302 799455305 571814119 714840990 177134182 920242287 304076602 432664274 891756139 480837102 155077124 26874971 707597993 102411142 355677347 930326726 697353137 330459839 819795977 990473827 818088996 328553135 735563632 354203479 525104691 397419047 663376787 75579759 106050761 275653815 331066426 794614113 761255893 592099850 52573467 988242385 195742027 630297221 624447627 3290101 407029284 919727265 377604459 85657248 901808692 367910156 245756279 780602260 875577425 375965043 902635395 472123218 940211619 621963119 473552100 437169315 496059528 801418196 632160693 665254440 186596471 589196355 645120839 908051943 824606089 502363878 483243724 695200217 637720561 37685272 320974351 237523034 194393196 336560019 807055420 698458670 617857341 856527093 190344072 465206287 741671925 820047467 170178554 542174196 818370501 841683868 769984908 599792404 206659417 593818144 237696622 69437986 126666633 433749467 539409878 365768060 295918889 682689620 66416473 60685210 99789793 718539735 956937905 83790106 554203949 436495985 546843257 832266018 890244382 305481755 250616500 351293741 202418990 176311787 555492145 735855381 648740765 420579519 792966671 677817479 611046417 664829411 190887024 147185199 285855662 673678950 444326200 666591203 83973120 97134311 191880903 620414542 525179352 55662091 800066895 515776106 896657279 725506145 456003110 819408215 819933612 312971446 113167182 763646812 412678149 85866385 179655245 112414738 908426354 389663095 547880151 743438237 484306683 857393393 751464505 931869178 861154729 674704256 678423750 397842799 227586672 606888723 679931940 179994442 653911052 69483423 138147599 401966196 995557374 202934340 912615651 819669590 749552905 926652564 198954851 534102758 997164516 664085453 911838820 855882758 482832885 636547437 170161256 345812515 741853129 774685789 627889938 710300780 353089637 313508853 104879944 279818932 280411139 278905356 72203009 136791414 496107691 988842428 394610814 892245126 996162335 493542973 306965529 686721922 683924397 458591534 78807420 711651936 977073723 779241863 511206097 374662204 879692292 581542081 967317479 370826413 869716094 643958125 744502957 900093944 836292164 763171960 671609505 564526376 22938111 236421983 63799104 472129867 218031292 350503103 898077683 115527869 993845975 143259061 967940863 178856680 687731554 739711525 920845881 934159262 325612145 310901391 971560237 581744602 959658043 196348510 55654897 804991189 504049525 34645459 130477583 894632825 18053874 736584679 893385468 533141262 12040792 214966428 154398202 266652832 941115384 567756828 164260031 725085161 256903090 996101301 770913472 193923645 769849850 143795399 97141978 80861313 605592883 37354467 90157427 760033842 417946350 281775431 262343606 447021305 285938585 198976393 932970799 915401037 793695600 996467833 967331259 429704091 943227466 458059666 827681699 238688228 782701455 171672165 470767213 904418473 430945572 575069448 966989249 873001741 76080594 577800187 352914994 962438690 984824305 508704377 258340487 868705010 96907017 551734504 737635161 305163589 712662446 643686200 36999398 150640885 156183984 105130062 459058621 429622688 152767827 812780082 340529438 206268597 628571434 659595804 580886101 21669995 456402231 673887617 115473869 401287589 90957755 650776554 95862730 846807535 810894292 465007578 263159430 372070199 666562818 412640180 515851645 479821003 398889727 151757816 987184916 22055275 159259264 678960024 650190324 568307160 180042955 390806648 163458286 641308076 232236944 454461540 714885549 958916370 110790799 229565224 333685884 635162402 899179669 535628622 262385525 503426363 745837939 90986833 785262263 533900148 977408877 309498525 884082200 257373877 796066784 255068392 34078336 986702568 389198897 400671828 78971497 168020352 966512279 326223208 456406756 70491623 462087401 856043203 96738438 456549564 668825866 510329427 831957757 705977801 531056336 7121549 542037465 423398057 837830125 668969163 925659036 357612473 577210692 157028012 795350527 808652194 915642019 19113077 251412041 591900780 766043957 797054849 749383668 587950076 368351607 962737103 507688624 313971267 736663033 548866634 765353143 289887177 540869006 822098265 171501406 433900345 293825737 709913480 523845899 933922023 721514906 545692489 542195602 686598359 762561429 529168314 855983854 135230677 530554382 368445798 846783430 825422716 385437604 713259130 550186762 439226513 530572467 163797813 456075795 440903017 530542088 706896408 398895835 290869308 36646353 278886010 547433878 806841410 382129116 514846802 414712887 46678220 609235810 225698042 911307722 378582266 164011415 719261299 861143381 909185820 292278918 287185812 685453036 237509843 88317972 328695088 1280971 910127729 95928435 667574378 774842516 11788514 83560999 773051599 248943358 68867118 520446145 175328468 393626180 540448853 223817979 407707264 317688160 161198366 523020114 473464852 286159157 595879243 211714876 162402081 880027633 426953253 785981863 591077166 119391701 598685856 921633718 817457194 5093560 371316752 152119471 582257294 64864527 17282796 732469507 886251286 337542071 520066979 719968141 9017876 192828221 417667695 331393768 916229371 486279117 406800021 55487468 729155366 299773987 539217920 157379518 897521990 454221447 428952755 912979679 200997321 658912280 996846330 85371950 19227173 126001586 579381389 779596858 196720362 958463114 275362697 773965679 211014771 745007718 56488833 300982135 799030173 828471204 463576264 72019375 858850441 854060762 292012226 347939641 198413419 228943201 223360344 242627353 485716023 501463998 988164966 787282486 822253708 106786949 68860502 431879316 910667372 651549967 546377734 124085517 748356967 778682469 63556597 766172477 954129113 391994371 17438057 977740537 93555410 653171557 825492589 15459900 469832555 862644665 296357767 622993657 162235576 320729345 685354964 376449488 449163958 23994732 310130037 716329687 555138496 832061523 574355223 431380379 992060153 504973116 513970233 451440093 455493019 292444878 214686295 794828654 753784369 475235368 882412795 669495739 870339583 977366167 570171482 719464447 697707312 191203262 396136582 601831948 577762259 595971593 389672830 471567854 900327205 916302038 384557708 630439996 389103228 982336818 905549424 495022744 368144712 269060477 747260686 894825836 119008161 419806641 658239988 279720752 686672352 460373863 790279698 238325488 540736944 335581590 327780072 914999322 699861976 912574132 669757850 949534273 972713624 847827625 181024512 343163094 673607185 186145349 422158418 207840385 912986675 751148139 318967764 81689914 896968466 257149855 414326084 778334331 39199304 679314058 454326192 526030341 659278017 836269486 182270160 196373910 787966379 111211486 360329148 653855770 214550068 922942091 72906017 159877993 534976161 848249756 152647532 617683465 751764707 24016690 512774877 85741668 756370468 217784965 884210033 158410667 451255275 527988267 209911623 987610174 319399192 180669742 618310707 682230070 642046698 258760080 443519829 250105722 559503090 548172565 933096422 277924958 525818762 566375664 543547988 398912971 514606983 659778398 987148314 717985036 410351826 139927609 884339882 528806459 208446507 888472352 872507811 720641718 400237114 859456115 894240899 346526535 613653053 985756774 197935243 436913548 608628346 216513285 74996775 129306459 805002167 450303349 93468645 492406674 129673744 322302301 301170636 831351448 45625205 372962991 584066017 142679485 192270295 334160465 271583482 556840143 149410606 430270093 3730497 647158062 523034167 215658204 40306902 953544072 395794498 739469988 515615658 424275436 90985918 824238152 380317889 920473402 565029980 787684294 292010893 689919482 808302173 435634523 993128278 99640565 314708600 797569049 764016913 119785702 839985550 195854765 177875210 758640450 797665221 671938934 81226073 925435521 739760947 906616013 333387481 174141460 264445069 867346588 275069326 736328305 109526529 482591049 161778277 231695800 240570779 781270109 484617228 426387419 85855955 688241065 420648460 893944989 55888143 644957037 527965663 914844076 846557437 220946504 603147269 402662827 302927897 259263909 522815309 334224026 398305096 708002951 358529673 707722276 848656915 867155218 255223613 216280271 421477941 718766947 650479321 86655628 606818849 173237139 432663335 746993717 535963493 798015907 660753212 219074936 766082705 934048943 915191977 857847825 605832741 946863079 537655259 920293468 316390784 175907954 369461694 882916917 383165494 592443560 802441744 696249656 440759439 590297211 859204605 571475361 118237616 795057040 984625728 870188546 470983319 210611888 941298840 507366086 250693278 506501663 137622204 343871692 393560412 555011191 143369385 481206585 339024992 884144823 857418137 494968512 365701735 382258228 723302139 294229687 586124678 299767927 171985339 501921897 920796947 911435921 833106526 597417326 954538439 698469064 410414134 513226908 797880662 809933646 220075085 107248794 808483520 335917404 968107981 477599186 377892075 291836331 781607013 770720655 887397559 563068997 732544397 928597031 820924396 714814887 849945105 301861303 742043669 764984233 104426705 158764633 629392794 734928511 215035580 670228643 267116199 446361687 440295628 187059739 980084486 90666791 50383642 394049626 897770523 892229885 177154449 20761558 25447564 966427864 620312904 767407986 508246645 787104295 657657082 191216489 855248638 556456818 70539689 984231093 410676077 773145247 224077147 447909798 561080157 613136500 263780277 252445910 820259402 498440064 437614242 538948880 279166456 312890597 486263695 661306100 589702430 484818334 221370524 268755131 931273459 510962767 275597175 457884943 875043717 75583606 766361535 391521871 655522116 345582366 6523141 677048229 302425238 735529582 353099975 12322320 631683313 891717840 701615737 118653881 839077802 599457878 763990650 796443224 246476647 325835975 929013657 659741074 469119840 135117572 190682266 874553318 526577158 613470521 508806679 305067812 372356052 241273403 17925562 973062949 89666068 913468246 247600950 94394011 395153333 981897618 473875355 714514391 458491960 833275551 440231989 94788610 569261918 226161299 301776187 8907602 759021059 653545778 918538975 544516982 398391946 484285586 656729794 79405112 627947359 285290078 198751249 811995952 149769005 648930768 520653578 485282264 227688045 378430520 376717991 592880288 31187844 289616848 203774039 785666406 435988842 609643439 618756374 110332205 659543919 26519415 126147774 304547280 244187681 247120004 129412393 321878724 525756119 359746027 616173697 22777238 768015994 80970376 680948495 903905343 805766898 839917821 33126126 238663174 669642366 953300181 454587626 295967258 886171728 146448486 949507228 478806275 263376903 983676603 651488910 44224454 138424684 305220879 170199972 343478321 739994517 609517316 649035321 485554469 560924499 457778114 90372033 424943363 329164294 920196736 474094487 925672790 311144606 908170173 949763540 993269703 753456159 314744499 184831728 271732962 501370483 814901185 858271397 761537706 203462374 500559104 853020802 344001272 517429538 393836047 346443359 867358520 826058751 19654179 363866248 153742882 251011713 402648719 710985434 229475334 209858234 310740440 850681528 227093165 779732357 272372085 251211944 793676937 450578474 592098264 414013782 968388589 105111454 831680141 130774086 299474875 320350389 657439963 877659987 668400021 317715916 64797977 916778458 104160233 619194037 675348550 331002190 700947441 742311670 573068047 7846008 655898187 133302294 510895100 82123532 145612707 298236891 574159046 518949175 49078562 142168288 389484569 117031056 991862176 818460370 378403892 653139262 375968383 857597867 306123367 730688125 298119055 166422391 693863450 841436360 118721989 681039480 786543977 119380350 127447952 439278921 427546614 519350727 632726666 540419743 742960921 38422633 359357618 181760646 481718372 19823187 622693803 853165275 274757509 511430145 357505201 142526487 551824106 157470291 802361073 305788453 342949249 824398113 534114995 781750392 25596996 845714417 124232085 379678415 260132263 7712134 62026013 412017556 361124112 185708194 290950137 476298420 161968289 491982270 590406179 750269802 326182460 752145814 750811181 281552915 195957733 580929744 753242651 364034266 335526813 119722646 159606657 750023804 601114418 630470181 409310014 908279963 513723134 434783269 843634502 874868537 618239124 483600786 124995815 603201813 223546050 520588180 928344367 191374555 398633781 295524940 913343470 712468690 785384273 914966011 169727138 251282808 752426663 580660713 915206454 791527035 29694364 776335682 741994011 902163343 968759429 581580273 444418550 522067353 934964348 170849944 132587942 119460365 11004043 106925981 485770881 506668563 778874697 199772393 189777497 221250043 151155080 531563021 784646302 906470057 912059199 771408214 462467794 203176731 475912141 765024700 763287198 970627684 489932428 728244920 450278909 252025746 248941279 566694541 327043848 911399741 703608423 56116225 120202390 718452467 572163293 136280981 462437422 87075772 897556398 751947273 185745445 338225250 864276688 176825615 509006726 753073560 252585348 442707916 139830087 536585662 136565077 133945785 400999593 157140970 37361176 964273187 125050979 228154825 514268278 939251040 45136387 157228944 483725219 106115834 579503381 647987876 170623964 536814503 494502600 586956913 833726294 942297316 826189740 803223508 965263104 838830176 212962503 131381876 550573948 676754700 732900368 136703028 215236448 378169139 357891574 422164509 800149336 238023797 181870981 575846247 413400129 306436092 737275771 468988892 297800336 910756945 982424266 144934277 59521785 465723434 703535338 846801093 947319530 946386170 754213282 438648526 31023638 360981076 994182647 467263740 309190564 836349705 185480480 872074643 600796725 270824942 448227668 993428907 540441572 308393261 580465302 34334902 289576929 63232308 913165084 274459450 145528116 406680145 182732252 811716930 742364483 529345854 374213317 687847916 938677001 214586660 375261728 133604976 817299765 51076459 599741964 71025950 297930749 539001619 525268627 772682004 985032053 698537031 263290198 703364775 296073180 26518498 894555190 177586685 652289339 189804555 363949223 688980483 174034365 145903197 778362959 341993611 179207713 593383866 820528976 709527403 609705094 71391896 815093431 423424240 713469982 264685751 45334637 620929498 375075366 341793344 628871773 835279993 278305638 303943624 465890406 613764760 859612742 518422824 711744121 809863747 582675040 393682684 106436578 93171950 747909107 631826193 172565683 724601749 529880293 730362082 919932127 570994207 95336373 328066187 509556842 176556599 110296480 797564744 276033647 269427888 404756180 703433227 722403205 154179710 948844530 952930066 760544894 596041785 368838600 805515823 374854929 966580000 840782479 159979821 444891665 245363924 610647523 11190119 101862118 634616698 314918404 706108476 502245958 936832801 99160757 8403340 554243918 180900949 100590193 743123279 918230135 402263428 856834873 287240024 630427824 951752190 438699364 461650636 563543906 494829859 289298792 977882523 794928518 668161196 601993524 440818572 554252831 93486308 916519960 546527543 871297555 846086083 118215966 627053383 124263382 485454494 927023055 104470787 672744856 980708761 342549667 413762851 221363766 997891846 346084705 915641293 649339775 57671435 682076383 500600267 31367517 983765391 418113177 15354018 618925690 764294837 807799167 772160721 410160982 141410819 895173428 137577066 616891689 736568120 964630194 403047001 467932621 586799132 805147126 203400690 25274252 611772205 189301576 110352303 464608227 968502472 181196434 187900412 848035605 472464511 167468136 427553196 141358063 622390882 207011926 820911115 270663309 513587505 298678704 467953602 75733802 345963622 533355704 942625244 706199135 907720405 93950212 696856808 863637184 646394120 233097089 618313445 466355033 717708954 411920752 962589154 493959239 32185968 727098513 932811660 879733954 993396452 950209494 451102512 60005983 423090021 247948115 984100786 513630034 295133589 928440058 157532232 657355416 719118659 184038217 395156107 852686023 491081615 978782582 873258652 384657221 653962449 978124399 908859239 933395173 371353507 672028198 942482861 368390621 129973673 285651526 49196849 956884556 973957592 423165560 384697394 269131298 289985949 174114187 592604257 611794590 589593253 617993317 387737531 193738783 631696557 888498543 823244775 602748289 392648130 923151096 831052549 196444585 815642327 99832100 874617689 284606974 521978483 495440408 319656620 942465510 409016445 89111871 499456774 206068892 760688132 750774067 524198618 155214175 358220995 249743650 13203619 728280044 59136439 375125578 415397678 162221463 342270203 448078277 108283662 833513009 421298399 744974027 316792579 342289093 457807665 234843971 155447268 446549690 436744486 411821813 341517271 352640704 775030219 847968060 821673619 592393929 449691536 354717302 947097635 375509295 221544667 368028880 623351078 262280643 110261526 14848292 152193320 884706480 153850833 394818832 34394794 788107131 577437524 759822501 974002420 519062367 955220639 290085715 114573075 940316376 578129019 386301364 926312076 109334707 752737498 404836013 912146388 973588756 88110195 124958717 686185822 645155330 748558031 950663040 642903101 650045503 686463866 652476812 652714344 695149720 315669104 779856519 476156638 496112673 994762023 664637835 971669696 689343467 148754215 675733434 469971506 467974926 624838643 822651167 240425382 733912896 60956544 510026504 816388306 206446517 171769284 215721221 364178231 575754254 847806347 540245778 698412380 657473583 859643157 965392363 634269912 464752560 280678642 91186017 558088573 634648577 553035382 395678617 962752581 834229733 462668830 301294476 493792496 90020792 634160202 958848368 19566333 442928367 747484199 880644938 48375221 851105186 188871126 5737259 58305440 498929104 317582206 340266688 165659499 372925769 681161091 785438183 972361817 40499376 537513149 940714894 876473475 359574357 689730137 765634727 687103241 347126321 214494609 687112451 267538383 344044515 571534619 704913056 988482222 996140562 671257712 70501805 230654805 733360228 552900298 641373406 515473855 246861956 619388040 73725244 588802848 508773713 779399661 259025850 521337863 307591742 368456118 738700688 79440145 466545511 495940691 867227483 519301869 261890329 488753560 760207470 155760844 267136943 266347721 391044535 491048090 949192162 210128777 291305727 810534095 969141189 920894192 350890903 684333295 87334721 902846701 207333709 235358597 750276959 665529260 378263972 987954252 295735605 714753500 451649137 110407873 822333531 886541398 640449926 887022569 642409705 833251046 697670115 338394568 358698837 654198160 35082371 228359929 367416049 436004911 806869617 463734619 717949718 270393840 287624108 851129577 670218287 45983210 480886693 108373853 929743738 690059511 589957858 98711490 282758735 211985795 772097254 235998580 569440287 873366542 343231610 15104659 821498641 467104773 254654513 444519812 270394500 228616627 800298941 787356763 73585972 779981590 573689795 122307541 744300169 568808250 173521766 320268665 689343787 501266348 701657028 966606258 501091190 616047414 769504305 702621869 967305071 137725728 683253559 189341102 419413162 595536461 580235017 740965280 697379414 413480614 867950198 704268915 383721425 175319220 697182881 984763421 44099910 963762268 202947127 520880119 790704490 381310683 862360300 680566621 903538840 529537327 716142011 394187119 248137198 968419272 315696630 475798225 369184634 493271679 983380378 510699360 274258773 790802005 202997632 691464607 441843860 840860542 125258347 968345612 172464046 430009662 173440536 717403121 420950098 424740394 238650867 799721155 547075982 66644697 575819178 535126739 639537714 562071352 409044557 760672724 350543175 226601476 393986211 981185372 556587781 957611552 128475898 960943028 832385834 965528552 347740666 440890481 695355787 282963831 169584421 288772504 451345608 193190219 831292995 59791900 318898582 993125381 224553730 646704868 591564863 326811298 387133600 571709427 899723406 436004514 266118969 192322030 835789119 164220486 915423995 667437798 898344555 864642391 459949452 148335672 912369218 450194700 836795671 728039847 308055114 84926973 782938784 383195004 714444244 486575577 27269777 864085093 103038010 799373165 886357220 776587531 238411511 23293260 911793352 219680036 819194740 328785044 902661428 426241962 317397277 458956479 236028910 170488467 335827572 374453288 24751139 86860173 212046798 568726158 188103974 190309615 906678649 29388930 635744133 423315080 504687399 14939007 159113845 74331952 437027219 268428788 467430884 337187926 912872656 12973762 808911842 77244330 588230606 224782997 681088726 601943257 538181964 14013401 580521599 641442792 151925838 425755498 919995853 945272230 445042601 458543104 970183838 967530352 706407986 340805410 461354938 950233845 679730486 158958860 585646955 856010542 35999079 37386572 904055197 397037875 769590877 222713878 112923326 307855649 269104131 557558154 869814339 910631216 529575445 203964389 524356941 249837204 388696849 534812149 915098701 870527559 859903197 423933626 625267022 407408209 557490276 946575466 8961013 352705163 254681023 123312696 374255660 563812306 810600559 331333319 613467190 66289818 622996430 699044917 814377188 23950689 646875658 558437903 434670938 517618438 296742130 794562561 296227741 469208627 971716031 180104515 810086158 997535220 801123203 439883759 655664205 583975272 178730952 958659510 941561425 126527375 64155612 844992402 354019276 249493512 563344755 811458723 235767115 51237434 484795663 89634704 334544131 797204489 735663576 835927144 839312896 686911742 418594757 666457670 309986867 183787356 189030476 479911661 41492270 492587636 368564424 759245113 971552886 216405228 925400031 133163744 412015128 618827336 240433520 802317129 329859998 545482188 472804752 545175271 727670698 618586072 346065972 898305271 927793470 571557041 11537694 3262819 240869545 252605930 104255447 765411963 995625946 475801223 883380992 710956149 175017807 107349704 234390259 874314554 592450732 85094912 943910487 557950373 125849038 823988430 619517504 914431376 128045297 356834730 904954716 333950859 984252136 608407262 243520666 360442377 164420760 353298523 726683227 958230007 34042363 750912281 415518301 921761828 325821591 874698910 148576343 344820766 676641550 761532458 194141005 926639055 616402408 74206923 646487259 428961882 455485451 112021848 227763778 926457736 130052891 481445099 186270021 378170502 311496512 632480877 529930823 522062072 666958659 353207295 773337052 32896423 254618266 792341217 402669036 101152683 656383302 848487176 972817285 949476729 435969500 137704135 676159526 235913603 408106829 835505973 182564401 778993175 775715548 350010821 632171775 891953327 23779590 372157991 424567800 34153086 441671918 253484044 749098128 967282533 1503304 72760552 213584272 460003388 234570381 840532340 136508089 359117086 594976671 311962509 184384556 536335708 492722297 185494979 314058716 418326963 417959955 930498051 95165741 458986320 190122853 823646707 544469616 450557736 736779849 63581092 314434105 546383677 389931488 484596189 615098459 328314025 495146063 968148568 494488027 170673320 872794445 135472569 454066558 810251655 646343123 112591705 571157437 654443330 382833758 941319803 212705770 152075858 658302622 942141273 130311962 46716720 812444823 853268332 245370945 214978496 57888764 928653163 806942596 701906960 80315315 854229262 847772313 852715914 436129899 609266740 525213239 577055939 547286207 216128494 846211792 889422115 266725671 882580348 560201409 673714028 836848879 593792524 226237189 453637965 893590553 241180547 752996789 518941352 651104892 748368485 569592832 484097960 198652480 285674217 23232420 818771729 66281393 710549266 674931745 908761670 817245282 846454714 711759829 61996376 789679516 278189860 222820572 817386173 880113847 78903549 814173865 301576659 924210332 610132593 147405523 192803894 402258302 136477281 489643870 816787980 873682548 794891758 234667306 986112245 522545868 982233744 529431722 156963187 645366352 767459296 190466177 463086597 165926258 117233258 232754402 614468081 212649907 410887309 388024933 775909719 769840375 363846030 949204399 8169415 36010443 359672862 424100652 879339263 297553421 246089015 202058516 436998804 515993967 926626949 960511283 188040136 312953038 412462444 50732553 992441913 232983813 900348153 261941624 526188018 633612254 89072637 156784198 202837265 44991625 294465863 554478589 197569338 127558019 460389985 388679677 952945297 576692754 887757422 600748437 484468167 152093971 136094883 507945952 503477776 266669005 488407946 55183333 38209539 29166043 244637995 384066781 132466345 369898860 472867443 932914486 407374204 348506995 57906988 626768200 3257678 806341022 2916125 521626740 64657241 810226465 125410851 161573015 530129225 660861745 411157149 870956787 408115760 265669009 773307574 431389367 12233905 549743226 197566922 42273208 198806523 674237787 369216452 884573271 934418465 195852510 784569291 763977177 522031933 896468079 630663757 663059962 211332038 543385917 874088998 514673002 238415436 379304208 814930993 601654585 971252522 727852353 338645984 417028623 690627488 814766582 801369268 716727735 856439654 789512598 654253907 400445912 392108592 216428188 681823745 433727091 593671641 236526610 78172304 286977715 85436829 668783527 699951364 537504537 303036329 54527409 598515923 464972831 482296466 896881344 117738819 150190358 736299690 578306271 62761433 943940668 804598276 498169228 627906298 901584597 810081870 961632328 787751602 64887574 78009619 919161223 524998088 29555306 913853243 552146538 896296449 128660495 341852158 43000651 40248007 219913232 272609186 614968727 654879098 31212964 709255020 680463022 959936221 55947523 265525619 34990497 778451390 648635329 997687859 98151446 925530414 57174037 969609366 638262709 313231979 76892044 862882377 179932478 587460935 151012483 736024698 744766292 520307986 880207507 413047003 714171969 382821023 79323938 296598009 404750347 560668242 774936248 386511325 935959351 844510110 683712515 218836429 372979139 759491047 598465309 614673815 657210841 577037807 809319602 653655172 572500051 762862773 695568595 86724711 995542591 208882912 647313731 648925931 22910414 945307572 228336023 223121639 559647519 551943587 961175785 485801102 463502327 661287973 193629784 935682427 494440499 737466000 912270698 20310546 969725137 888133797 34806064 551466982 874146387 65833447 186071995 50595833 960351036 643758360 716566397 815685617 207950884 675759069 819772682 42120223 623160373 903698510 790033678 210495127 155161285 378619779 851456862 983522835 637378375 822179947 535836982 60739329 327316315 409977453 417114397 908537863 928454725 713746665 615282373 852292178 182263544 141602539 371363694 53873937 737601664 903779226 521421153 650074056 192117340 843379925 392366402 960437526 935332096 831288963 846580468 727209808 726859181 509786000 817182260 789834334 974487337 899860109 836379355 144524791 833016270 347988017 417142363 847533773 744253492 368689536 644398530 469572866 657106044 798903237 601576417 784975548 479684326 14180699 527622562 109099945 824345151 750616808 807018427 944891803 513502274 730235109 503472390 375810499 478251092 793740403 802964331 92152925 721034258 270641333 575528499 412483272 349671210 555855842 537525257 373347926 824403310 478846407 552430238 590063606 276081537 232817070 357186779 507880151 82605376 41073700 669840894 315657860 716880544 29519969 875763071 764930973 671355950 704310458 839183373 212541094 938195726 447026369 791016088 469541864 285611922 747197037 704775109 878625756 132353349 951699138 656617051 629058717 866040050 300205684 138401353 985574956 566099604 839372226 446512279 629519669 137243970 247829010 401043525 769675188 173769111 464389284 895785118 893363910 753508072 795010885 722893096 600553026 224269361 343318170 165249247 322941768 824423174 530455402 24311276 844568016 801501488 675406441 422582433 76775158 486272533 328273991 774288298 146516377 902889232 533598730 242878260 164660284 802311331 147787243 975178940 553793726 830122732 839750455 97716823 57912494 86009563 656563184 964832184 328482639 855262270 903189098 872424895 340968445 296782907 647726224 642265778 679135320 93862286 401842086 572454034 996202293 902356419 449789323 348570145 268154357 149722296 448079808 29156634 487834239 379942806 201381991 354824082 293109745 160196437 641694350 785882783 609523367 79113194 19399722 365976093 646845697 334760584 618224823 388052916 784088859 748555144 596782157 675730599 835266783 56393136 509636857 172981980 622852811 839933971 879045545 27256835 384274483 721994202 394129407 247353645 816903400 247555772 808074134 468848865 540090669 400237831 46958056 129752232 529473509 684415203 507412217 558897981 973490554 604514256 404623408 581857746 948894553 64402097 252042737 68819086 501675323 364896016 620469226 108974165 237976795 43155648 525308147 974397495 368517503 884382229 766049332 670493067 917692970 708873607 924480386 189856315 822046501 308311310 749502437 417407833 373162448 420204452 833617616 958098051 506112912 717987730 706089823 961592071 694602359 598808689 624814425 274436277 547209655 764545000 107376240 203612743 487823297 215399591 794898080 9536403 64008461 75049008 227413910 271959452 833080804 744116647 835434828 390073357 260863244 336331115 51863991 799432080 74046216 415393287 803611743 691878828 834285431 855306899 21583234 458986325 395830627 887773992 739294227 644415575 455738904 772236703 780286556 738052766 830799685 935648634 565162781 31484485 709078505 364974863 485289918 126042994 873935501 551927790 607347303 828326389 698606106 152284176 822565802 761547464 775566931 701361438 87937790 238775030 594061227 36943858 788223202 119701501 780561060 133073510 773161553 275412214 43247349 598825400 165185791 927303099 557267071 245005328 425332764 158426306 886789970 338949233 921399011 661862659 257977232 37767272 20427875 450074296 357857715 344873631 522474775 687533056 687986422 959633170 948903297 521276193 78669326 888434678 167849918 623818993 841499142 527925154 474718298 575999232 877309653 850350575 261696928 352886643 453878575 260478837 954004812 317956294 75999896 444922466 439319780 107140488 937987645 493138389 310512344 60886651 935814999 712663417 604100117 878777649 591812882 612352221 831266431 60691502 303506463 576533241 986014775 213409512 894354033 554690056 110035786 563766151 337945405 428290045 133725511 260100003 984801802 95141205 477163399 601054218 936832937 236898127 366344556 956042864 194718737 390787221 356018097 656164262 613029304 816491491 40768153 635180936 111647156 751794920 829212025 301665136 40497451 855848804 554887644 348248934 317384298 480548972 385598717 726637519 329090433 665240973 260744255 709660619 103502765 777002568 562644697 215515999 902027037 332258812 30076893 919430498 202906361 508855268 520852914 719278592 768989835 735087067 216446179 721986320 921596547 182319974 726965274 466191173 472241402 247590289 918466370 790878905 707754171 200557162 968827092 304800083 965053185 783934828 38452251 398692351 717933887 687481783 409283143 554444281 685231871 577574384 703027164 394387724 847726355 832485303 491841679 851182195 856520780 856223400 452992939 613934972 175054573 677953558 597201904 884932923 207271017 797676251 522537803 968648386 850669262 142142505 802372255 97649816 886855365 688620142 987477118 281208062 156847822 251068394 176273581 139894733 228977965 725629958 416112481 329373289 484033025 860181125 814322385 68089164 535796179 379928463 718623660 701590032 471627144 399031231 118565558 227989036 740905445 60825216 76524533 579954762 442787796 596007936 331329706 687774916 808254227 698118991 382781491 980182815 54703724 938410496 179600110 521952425 546486649 720423463 649072970 741646025 72486622 926197644 717835059 264745928 102749410 201609900 637094626 745747841 341372386 762957408 824813159 130642637 113982348 48398852 706016123 413219694 376684837 986466146 259246087 220056301 636866038 548822184 94915438 466343569 307992518 64850310 8258554 465581489 811853455 645624713 933793952 311434721 705716797 289536044 497402512 826874824 599079168 74202930 926902878 194213987 497445626 265455137 443707750 276014863 799886765 526424824 353948278 601507018 736617250 941745603 818247308 482498189 535884209 773981829 539346409 65088715 645966996 493949663 493391493 444834453 834395598 556084805 269840804 571811733 48789496 426865214 328078923 977967487 896765050 471734320 789050856 506668475 331854297 497529476 158127557 191085450 253909000 363152808 409424686 616975901 594933895 132804679 600528581 476037996 499558937 556029115 494154660 722966436 666261552 752010330 185143632 595865596 40776951 636522104 358621736 250824412 692917794 581476133 561585060 698377378 645141951 777563983 567516122 554748662 261516326 261108323 920266372 355104050 170816567 825114247 418631052 374287932 569151163 275979476 662835414 208453363 916879334 523657955 267871964 693385277 878529326 398622905 918199245 273292421 639246184 449976992 849209641 214199342 420860399 280932952 352424568 120492817 830761413 510807033 763954933 699064444 684746170 980622285 975998502 575921129 915787526 1418807 783745451 802862891 292298990 220110831 740604354 355192284 47166911 406940478 64892993 171904575 93743334 817452156 828821324 382835554 155293092 820444031 556652108 669328130 442829159 138348565 166902465 258921185 110958988 280548148 781408937 69469523 433769380 237727740 444183179 422411265 146752149 966775514 199938141 638810587 269760044 390280896 906270514 936656348 764784722 27517707 100176434 218002337 380571285 382413290 526943797 108559784 386225780 159939452 305795234 698729594 10271901 793802162 115734499 795751951 989595154 41947140 204574661 590627757 929878930 323039780 848198290 361849494 439577605 659726417 755644134 17148895 181492901 723619746 794053306 895136223 177738608 377684146 695651668 597494226 254588058 754708329 103725752 123921224 35036052 29933475 649538386 311547838 167640081 58531279 568863975 435244607 345472232 613080243 871282504 74972435 757974037 905158114 94107780 982095559 608536194 453720702 618882031 565868783 941014628 458399691 529426149 702706461 577626466 94058055 191237450 505999710 303952762 699371626 288998501 586464075 741109106 730448416 713378327 7868073 712194477 588630385 937375555 504334611 505904711 80685155 250709090 420704188 52514418 227833330 213829701 227848372 680283494 565466338 753236659 698598658 335798261 743470169 517642415 261266811 810378144 161724059 595845578 641619227 96140075 814576845 256039996 884123600 866831306 208330300 286057097 44573305 697102086 787999142 226728141 311604187 206772014 320939491 79469494 787753747 430824875 363669730 529001455 886781352 207530141 381951381 118908077 789712720 506769530 875739845 437178696 685913321 455627062 95945342 911448662 219859109 895104230 535588263 277478452 73630698 719714199 984275278 28727328 680638929 276340334 465178776 293263339 34406971 14341374 957930959 852480285 983373997 793398199 429621149 1959204 672044458 374007019 290509500 537029370 106114356 206606850 434251958 795921942 667559419 530768833 845147926 790719071 256462855 127250276 711807928 744078833 277463206 857032624 641818075 685683001 916348339 833109214 435515004 253623071 494785188 170773578 746360473 408258961 414075764 837331854 180344187 596890585 713695090 539263579 537790120 188200034 824682687 338465592 189477548 835783569 450056382 426117007 940428799 637541066 819595150 955057003 725127364 44359335 685155447 994542399 287559332 210748232 494002863 668397207 271515677 898174880 725442913 512893608 544420061 405668339 875300293 122409042 494320729 624198987 878086004 295668845 593815878 679985968 403332539 223393992 83731837 798747878 765461772 48474919 505609975 375599341 568189555 297911244 121234796 191374077 513030187 79910834 916936431 317416363 706686930 641176395 685093986 282942650 237949563 600897083 89733259 279395995 615443389 706235401 640315833 555554466 842903578 421474210 705330635 702317470 421761361 60699776 275456497 664219703 544538407 815144456 799754282 347939430 37304854 654434823 608937920 562528707 530177222 421011121 915493166 950278605 725118658 668056296 434413539 921100044 656370169 724655599 868040423 349283573 144722544 191739958 21456751 860698244 539743335 679658632 325731021 473933188 907339810 647703873 53867631 807061890 879820944 101558942 645871030 961265056 579498202 867333871 765780996 964243667 172703103 691307379 471777346 364009470 639887997 325669130 714966256 629100361 935994621 429586646 972973907 455672062 183261366 555074189 247433113 136102559 597757922 906357506 261974994 113685562 507160636 491394419 122730996 291305713 272344424 890407759 662744008 645793329 363034534 504127253 401600452 344290090 61956024 829584385 620204796 1148893 490710395 824758120 986038332 523960098 976279333 786659200 950792268 576058989 857672691 899574544 385844217 792392560 125102369 260413574 495801869 783428490 519528097 278056159 778485144 66009600 185715884 229393276 126350228 823627457 394263442 508280722 353619666 285967151 900332715 360695701 735930258 682866895 202967396 825824413 906627196 367179816 130035417 741679641 39980782 250686910 347866971 482201725 893526619 284185369 729123596 292177607 280823602 316523092 789379736 947742027 995086325 375324684 659303762 490920503 149379778 825648872 419739848 785848330 211375575 396246400 970422519 488592508 91543347 459587077 591685867 901658289 433384414 49756757 978982494 683229208 118413471 189343145 718894278 747449374 529162 888360139 749041877 921902942 792617432 330858567 605375672 312383516 809166975 72048068 457170499 994555020 762992408 978067869 929411786 595733818 850445839 808666486 398756755 12664542 993808880 466898476 990451537 1163341 42423957 577289551 24252760 260438571 176768348 699109971 356519243 373179728 66577656 749732561 399956849 379303564 198149283 637878023 287748756 311280454 644243818 151498149 974465032 899504412 191449681 938123110 357933160 14127980 77681408 277065580 718739949 882074943 499861483 495797290 757432891 890429137 260188343 286509161 58798277 278277601 904512258 103349103 742851283 232644749 923587763 294285010 520830743 95041034 500272816 701848472 740322572 847909992 33364484 843496348 289034564 619905171 536229808 559363181 254498692 756069923 920192493 191414968 116160231 909357907 574402258 941816128 440393230 871405144 178682954 192879121 868687482 325051000 942023981 585042876 355985007 119720957 616346986 532105306 329481934 54272050 505897143 76931740 420756158 394206190 290728415 309000114 845785940 402046049 155060110 902910867 155626327 554285703 730751620 787219585 333894249 551791375 963285600 783218069 325081331 207926344 229068546 537710469 246429705 322403850 221016724 355804617 643692080 443816151 877241587 45246474 967040084 144539682 347181377 912388705 837705421 194068773 144386078 410123745 635241529 540971432 391172052 103185660 98184069 957428702 615058121 358231897 338109053 374006878 486575895 1160353 894635287 366416308 104571792 644996725 532559310 223748144 743843935 311025007 894434085 521974012 867373891 592012496 963256748 45575895 701190578 413943142 542387462 949188695 10786875 540312535 394640121 863643148 328218620 776457029 887390947 526407986 394655954 809564681 295199269 60553825 411631477 33691384 256052909 286015555 72068660 553297864 986189481 311193832 153422927 126004986 652595871 292504678 364321689 897662215 526136904 78783778 660164580 320221941 446995420 328692217 288526687 215134149 146712329 638621150 555297182 410449895 423328076 172902293 787221856 634143130 14012058 999277 175692490 954246005 336449089 435657483 33923824 413948711 380254745 603583717 921788598 401618389 955802431 524505968 95146999 337846892 528012694 166187466 672719732 344722906 3259711 563358564 590652280 467537379 425804188 323072637 307247017 456810457 892365690 413113428 152981552 943771231 537043016 870155312 629658044 406482360 965759057 719276220 964656155 569853710 931785175 287946410 399571417 246429039 738542628 365510536 353590106 771401134 126910709 846655323 758470151 632758488 444308914 202023680 186193459 924387231 41816762 439518503 50489960 850291500 926301462 287329604 357360502 875679533 89972858 334702942 770358577 790912981 320926954 311011301 38821452 764561866 618818826 295750240 574488903 141223625 821431795 700394001 511093994 925883031 654485137 216904717 616849390 646615690 677520525 274480112 615042789 931266313 729998762 853497351 205061398 292542067 319657982 413036331 768499762 820782993 19943568 158875924 346993988 492249239 792856534 249005978 371504221 473000927 426417359 162082293 739303300 769882541 944822586 852009303 604723565 451382703 16364423 66602975 314953186 58877913 402871302 66703457 827710921 956488983 668543884 140561752 756189389 645320670 729161313 527638305 716224307 98196224 250546856 177519241 880440203 221333239 195693158 206079588 886280931 637636890 74523302 563325715 351697596 354178616 902683438 845206878 987714717 729373011 598954747 429176227 814614826 394269804 436809040 511740573 203536928 919428936 376814404 485027931 425338594 951252816 334007786 428576679 262653612 907344359 57236236 667404737 530053841 514449951 167243153 416482129 113693353 724159566 429815634 244152326 374909752 372066153 895587513 221437411 895336008 111856978 324546972 402801093 845650952 783583649 508149113 58655693 279780085 905103258 407240712 30576324 404563446 797921441 442852983 778417136 576006747 804787399 181717832 384933127 891014464 199393975 946864968 843056041 140048118 980803591 898788244 650707552 721743620 509006640 264792923 738407590 397001375 20746776 268498685 416238470 955076791 876843114 111140019 853365552 537913849 394914768 414467361 211776258 833222165 504190300 861894487 206980855 648815345 890199588 364704473 734589613 926519964 591287575 450042900 448311832 760555218 678363903 180048433 702834470 353681257 616556420 322175905 208944120 434941143 311936327 905321043 506322701 765432703 755013696 536669605 612624336 463139926 975555451 756611120 787950078 813352056 20605987 559238908 327699129 400539680 452337029 983755181 867181649 253513968 917924251 972884919 199285650 989530485 921191961 636305481 427090273 593742158 445571645 663588025 248381982 263175196 567942124 114111740 847564722 116435345 585752823 175237811 989514852 729082782 743418144 290783285 602384485 126695655 26447408 549580167 381560025 778209667 167341326 521431253 884794889 628614330 976760155 715154883 524585683 90060020 61390510 997215197 407780839 239610258 140919339 433089191 818279494 668609842 907786387 423143676 750370616 618894070 409489490 738239804 419512125 608298316 21352871 409894947 56014178 443434281 160424926 48224849 650762086 141134321 987206405 726769273 247566426 789380380 471638555 946095215 934354773 890263966 921865595 18322477 843757638 169329616 543217325 682558691 39513673 363350431 607668918 263379231 729341168 206448835 647595876 306714860 454654881 659045379 432444505 564424601 262082886 614920407 479227888 4737644 994250956 480248591 254822137 983838036 427279066 110699349 890915655 394129596 326205734 253381662 905547112 195491990 260582719 990406351 523819311 950631040 986011411 415678520 695665766 505572581 61227691 743144749 939248482 33006989 340427522 989997537 566734990 997820216 651548054 45788870 507729303 940814002 19416127 365886028 313928711 61690424 288792772 709051773 74623788 582022008 676663065 716965343 157541617 58972488 237051315 319407475 267258115 368329441 148775675 865340739 386577463 450150354 168576892 576928622 702087391 742414371 906991626 528486005 101725080 58510335 678340059 831195538 223866596 372688249 365538601 384053119 703169802 822743103 119541673 584984261 666406769 97996543 146754939 901951040 242896277 268001473 235211930 203661446 442495786 396885478 300674793 256063231 191632683 564128936 127689132 423059679 610426512 343522721 758641178 562354986 401342375 569712329 751269984 765422632 540099071 913011862 820948870 334551501 945001996 996337973 904144687 100068578 839488889 980170470 277071348 413841170 628251917 531643770 116460060 552930188 7683472 548637870 231150501 846592315 467757326 103799328 950404538 500903227 452888184 241179010 759949522 986698337 957892898 285196521 394610046 710291218 572893015 149895503 221496453 930106292 301710535 311242424 353329400 579804066 734045367 206527640 672835790 751627786 423597090 116638281 772677420 25094319 133999464 635200639 348450340 593689594 989086400 675436016 916747801 801227089 630190522 898378620 222937646 30473531 388073792 197657214 729162587 359023785 448271186 840228469 601906605 25805464 16493298 328616681 186703708 34685678 865946719 802755470 607150365 952183444 415026107 925952278 295037573 641773870 204041941 959775387 238605572 688902765 847216122 337715523 814843434 831019531 568125039 678810543 628883361 6713466 566679628 803934293 906432632 704976259 517514783 511151753 861381196 715640442 730642157 966717650 719110884 93289752 86544895 619321480 474352357 947262196 928223737 654250269 637864530 469345895 173398533 421935677 923499092 876316217 345511420 423194376 270578115 700367913 112893645 958984987 285358207 972154397 26753034 668935170 519539567 887721958 328189567 973304147 64051005 256820354 275206692 363930280 292875036 979003196 457553115 69616860 662897263 985394513 744956584 699036729 932463779 368947443 848442365 364667022 460654135 647368962 955228414 483294304 933988875 802473053 341098742 953472250 951729360 873359691 537038947 12443004 762328184 293681843 67923567 317361790 824933580 411183140 939615507 898188099 858870280 277871580 249874250 816641825 477214892 482815705 472364893 459525601 302178096 186536731 404051805 745631152 85762774 800044635 786022594 264058560 260324534 577777270 486199242 45274308 980254904 356043494 244593434 356685500 870715059 672361772 760197138 640683515 531854386 946747530 239635388 208070269 240054126 205957368 452441432 154597754 913500293 896704160 487398006 95206563 268408757 271503363 411904208 704862344 253879013 305080051 695049504 907089766 447669802 915487074 406501480 157212705 467310788 820953914 67322791 469370285 839556916 343298307 990419091 742563345 752973326 941493323 581710362 789340433 777786229 532054841 956791738 162410168 328487139 287820873 121469066 304154897 399427422 662773777 173197747 889179593 387866353 526503907 709171946 677312139 140954791 72725243 639802628 332660757 285584280 505256053 496669822 333775685 819729286 466841425 671093343 651920773 642669658 123140302 927151049 59500614 172110030 664162930 345003531 308798437 391249200 721993600 547887437 494005966 300422010 634207906 337971259 406725999 850376248 515731634 106934659 351181925 528343581 740831180 703681466 47869028 829220208 593680475 514983316 131336789 131851091 340737511 58119047 831860295 351009296 23640860 109421596 392182979 819313471 478971780 375223939 244168380 87387473 938263794 175419776 745949640 317360092 523709514 34249835 46549417 976122076 68849307 178030984 438700428 56364575 279234249 966787050 974186629 39547000 993027949 5041129 656546991 456173756 207846078 385766896 236050235 177674114 282452429 707604486 223061800 919951145 722828966 799652704 402452011 954808559 453641756 293248666 22572657 434326221 74261066 738879802 125648581 686276894 991944280 703214806 389813447 713840016 89052046 384185471 188268963 836001482 926242345 827585646 419978099 567433122 639098505 508716099
0 0 0 0 0 0 0 0 0 892679058 802864812 540253653 588817561 38789805 365826149 196105271 827745890 552288241 957998187 252698037 808765244 820565584 729347553 471248425 84074056 754021976 230570461 511104422 440529363 960653984 867535575 53704497 404787068 399021885 806983340 226827148 66327367 585289516 131425756 47509198 85277855 844460693 868015519 593823387 945420672 24365785 508160523 70884296 643636808 464135861 997816792 780479537 29334675 708101259 400385477 327793342 338466548 741766841 984294439 30644492 808728660 97873505 800451327 949702981 471775174 197078651 159161591 382006165 600815430 777786490 294479125 846059435 769716163 761093836 614590958 616378622 341614375 906109187 577133710 554826192 415443447 659673322 341331318 88775305 437515596 776340753 321487811 77390209 286780650 967764510 675059823 977546475 824894245 633918916 557711172 386969198 539777098 760237482 837214278 179762259 391496817 868246011 855114520 882768494 459223939 880107573 740553688 298157577 703720923 780126620 864505436 484219785 787537987 494409101 376329574 191200466 943312668 932416975 684618689 428894788 30794003 846911437 129516796 532527099 217657717 515075221 195612404 257302431 182348706 434924386 747438178 676360804 605547312 639968064 790405474 849422254 124167141 810725622 485861208 111632641 94484476 283790995 939863105 298740128 949826760 896037258 209127869 825769346 263117760 594482373 444906633 306344181 458120227 460119097 927415208 913207335 147591648 520418201 530851196 284349068 526510030 460661772 120968642 305186475 941746869 247987751 995480913 575099551 119329795 645710180 629954217 657746801 798485976 144832234 534725400 870139932 907002766 573216134 182044102 177416481 983160191 328181547 102196218 135537083 685283761 850649339 565636923 471630525 114235128 989899493 331377245 439744540 260458401 143225128 534400264 885168981 662441679 489993423 282055744 225382780 718906633 588768005 760161181 394260437 471692374 572743949 776415816 827571117 670064525 747440601 336264552 173999662 179617448 42089635 100892838 549121671 192885262 283571065 404022737 303487531 335184286 564170967 484932209 770791798 156786066 986701214 510197974 977385222 511978429 487428857 40662176 758715386 469476456 408373832 57980383 113399252 951602389 134651867 235141031 921870425 490524405 434190186 207337082 518944396 685733615 19282587 633578032 877604552 257090166 867508851 632625853 863267638 708237622 958458830 40600433 411221613 571156860 574620071 637202008 599508102 985893998 582787914 425167172 395630288 286701553 879320048 439336313 550162854 856994967 20466119 660052379 403407997 674153373 580776516 819283418 23990586 501413349 901179233 734567170 891970378 846752015 672917921 733516442 248453158 23429357 722827445 176604286 436928145 259881839 98380324 445019209 1936145 210273069 402781824 231900319 153823539 537234823 772371324 125520388 14697927 429992255 464806749 91648150 133391648 369328872 732315511 287978928 188093066 756082171 843859127 803887546 70613381 701351571 775531053 188962291 395130305 9775925 182292305 539241269 702967791 909125496 807342906 575205993 44070462 547156717 336495956 549348602 520012133 153714369 957775012 193138521 543870477 17512004 398351543 59610563 589954852 184907328 962896649 864347334 28772593 173131883 662853788 250967231 640764873 112401869 369136113 952215038 421169321 81974571 118638495 685029379 277086411 254959826 438458040 260436291 419212191 53043678 122573543 15619382 242932705 467446064 982664180 221566827 544133160 90182425 462346185 88174158 649212981 502967791 283669705 650914749 675094 28898164 769231222 976674720 30731015 430785524 398344926 682571677 715750277 942704145 18261360 486806694 699311670 301124123 79300521 885781934 912790622 443014127 464355767 477200495 908701002 952184240 846861631 126282204 418841181 206760842 215703045 486278878 373937916 270968333 189430439 952776336 641358160 162719101 841501442 773819357 821386094 563438977 449074259 207850150 507089076 799825109 544567655 138221262 367948966 15171300 288109068 742639154 758347048 528713706 425494971 756970049 92160557 766081937 113355653 613566197 10094772 300215006 97056191 591031407 341205549 772634252 550371545 114722215 24380378 210761477 510918972 669666650 632038114 92055017 628274234 989914937 157192344 575240718 948000089 105271662 674036762 508403803 142316258 725428232 331875143 505292140 71448734 29102708 458125195 81795593 591393971 405930369 149001915 696962883 346821787 915739872 771648755 657229157 169878118 630819857 69881269 685267073 475698578 963539391 652405008 657655470 321933923 429120945 129411 654098446 591612225 410501199 920621834 724115166 255929698 309909374 525196416 218564478 875579514 470778700 299333910 511309565 816371747 393784702 44661285 923123215 784240700 525400021 942248978 272484671 542845194 260079925 249923403 26328771 952869890 115381006 576559393 300807012 638482780 228299036 618904227 853339851 210510129 365799737 473617854 166263668 92799283 96271376 345976048 413336090 890160499 294431949 860797076 727764311 170872546 533061799 764458789 950922007 290822755 951919307 572636727 295063097 280197505 255328373 330955453 681045696 382399522 341705683 15243744 142187239 596671894 810852689 819976682 372223910 399784234 698829286 967760775 135377599 638733247 357316411 130869729 892029015 251640262 232649645 575153002 205243516 290605270 197096291 987998743 792868079 415170128 85816055 36888164 540398287 138546890 658092880 305283886 723030593 233107338 145256674 209722352 551264872 387187069 237188545 923291161 863101549 855439387 582106604 122403348 913760707 111821278 186594248 506609639 98497661 84620294 396802396 983010177 197605248 27758866 424426946 93863388 483365029 276514497 658125009 167641718 152758081 652118696 88613602 515059997 93651305 552318919 552499608 663473903 719422636 780123426 616147918 815258772 184022755 782946542 951641031 525215783 238025557 728220470 159251159 769697967 790189341 42678317 961427522 564349039 121857932 160849297 294952956 815398444 851348330 335169420 883009632 38569059 954607114 416120443 549826906 369976605 380996037 908009321 621726457 143559152 986892136 23312538 304110564 304692475 489332195 215984704 973418528 529511332 486802606 344289861 512831125 231169137 405454129 775960721 602115793 162461719 273969539 458220832 140205841 649080358 41291199 408434750 321789200 363947843 756091824 501680406 933956246 68735216 602966264 949870874 500995079 76732516 213459250 527824438 972905358 412391187 742607384 969779326 42811262 584189772 47031150 943877190 609407916 578854630 206640538 228924997 739839529 209465823 928455926 190662876 368290240 571594265 147029423 561082480 669072530 887644268 85781324 733978736 49423162 836079279 297775644 504293503 607707433 559253994 986563041 403451232 73216247 785310896 735232599 793175035 466002664 358036538 545533588 950736065 827470429 491534718 797256266 26572311 324568879 227016802 973665965 816933983 710258851 440139792 867696212 360950324 735230837 191382370 334347827 840712714 584134797 373170978 761414542 208857431 459961131 205016529 478147077 591019106 697267703 564967236 616906986 86240726 122552548 922467509 848069561 923391909 39544254 186039328 818109271 948560675 584849408 391948067 468225545 164997844 297234220 741492372 609707151 485181301 283222889 576672038 131667666 639616695 929538718 399196133 713387933 451654293 215231775 768711150 341068234 260793516 88616565 604099785 241406498 78948398 919070043 81132371 133449385 23945184 65107283 714039332 391324250 593457340 47297427 782571979 649862778 572125289 677389942 51351970 116048457 690639940 945301976 89045395 928439585 964286989 826000739 192545255 621722162 221438663 274285086 390505956 41749057 101710441 626468078 715016623 971422704 836882553 637212472 814206112 987302706 367051411 701632341 557774472 471776057 897976962 69837605 294548812 812331594 630011611 260279081 736162151 182794435 73227645 81443464 504193689 911368814 235192768 123592739 126238608 583002302 407574960 174669877 920659402 906900889 858111604 515556000 572725049 545874133 213086319 785586641 16226187 989013541 38799778 338150493 511239272 899590185 728322605 412108633 357728913 54490054 590790476 637456855 44876358 531345895 366834761 852805859 675976366 742611174 505709092 506718199 905885068 288881076 963929038 882285533 135586728 458026510 885527950 841020126 73522917 628100514 302775565 454928627 483748132 213399722 501656285 481981964 759173008 507682868 413734933 706866766 166844089 608982820 22387906 374228612 928791169 181889050 192344285 274765209 689586249 722969851 589801466 886254607 299887193 462456411 454007480 267178465 168228220 167664261 404753108 105871739 12962142 34805298 171301599 898908218 850796456 118975159 242639605 113109849 116483793 437706903 858666252 497290387 362031492 146272890 628028912 694820671 997228027 742776482 118880614 54865262 473534774 493581158 619319005 70753334 511928221 511235136 456716372 629503379 18316075 717226247 257148429 730851624 894512138 825268242 706042418 102401566 109090735 929667435 828764880 95182568 208283263 800476754 726879880 517857784 8469651 831527855 538015776 85236201 57161286 474147222 9239219 838295544 275374360 890349631 30300620 841294691 962764997 87807538 295313250 41570534 451696042 510376864 930525006 940876933 636328914 446905824 528917681 912193024 243219924 250466224 377785600 405358212 285465933 151243827 378202611 25641487 660577796 806605606 188994229 965959036 162920274 693122307 319338505 66806592 845361942 828983766 710649240 699262497 796117268 478425304 375250781 287731309 123096735 53883176 957042518 623726314 823477790 945753924 256732897 779755029 610865736 577543022 553238042 657929430 165161885 273552315 905307088 189055480 800624089 163512770 435316525 75491389 705565436 823324224 481652186 741723870 101064547 167580454 847587278 902477275 517845261 573843931 872742784 420249053 462331683 395072069 595229884 252878783 588140059 263385087 2583842 992453439 939999981 832654764 942415310 881935921 965597384 619787603 180261856 280722889 494471200 886981968 811673135 663497811 155014668 604788998 503250839 120503062 154765696 414643331 293258638 402918906 499271782 370291945 515930787 388195880 118047071 252320319 681172722 156916853 391779826 261351436 474758783 605401044 420855021 487861211 942614386 71787832 105116298 582372295 584342860 544650878 308441264 593806722 390036195 273235914 125794085 694348510 421790240 986523980 773291782 338388137 793516278 646103284 832224291 260339821 382777528 685630469 795106768 104293740 633020950 713312777 51020402 809408391 323074891 686386511 931880777 267862387 398711925 743460403 962655782 896358884 103387862 763947319 809017099 751558331 379361934 487072832 930624339 169822113 357178521 270334872 468479512 808358914 849956420 237819258 931912543 443513650 539697733 938471949 18688123 220428624 54448954 673416050 120136715 284831271 468678767 299871753 304543273 559149352 851498587 841647180 759910783 567822560 120734541 111448842 665044102 89209981 53208846 422123356 386460097 27432635 623611183 53263574 810857106 34081493 241644679 886632308 873624501 911634215 967467387 686269392 871402577 557012959 150626193 631778878 739340863 923094040 894085650 869693886 508002999 166295003 135638456 678977267 568083371 160270148 16273355 908700364 962471940 766079710 473189938 497668470 307232906 674337951 462491615 341504326 140443616 142744463 851210345 15219174 996525494 823864872 679395188 748847849 540479321 530610210 186683408 260728637 494131619 710311230 954522073 791392373 932652735 554691479 831628767 326575288 899961247 693966827 272667657 990713097 841577741 849585260 729151063 233475625 479597521 555139683 659762501 170027920 194357450 966407725 523704955 450994350 78352523 570012679 910062058 797376604 39281483 800814553 386948017 113698389 800649229 483488063 888451004 307538330 751424819 657765576 602375250 894787428 875937030 349375558 160191371 298432926 405289690 937997622 901556075 153199134 168273946 302003686 723382355 50395587 545851584 270091473 852592507 604028995 659150771 912464987 103739386 659724946 869577242 632268892 756242837 338906663 342609825 576244854 774854421 53152673 639900889 467782555 114070873 145065805 460161429 64587175 520995118 877597334 9904972 204859999 23398509 382292514 539874698 692319362 868318470 931997545 741179493 31862284 401888340 918136659 13775952 326365118 199609312 219740222 233100846 415003466 522364543 327726427 48811720 765909553 369387926 221601498 625876784 777519787 571479817 946187333 723489302 903186579 945431034 638673627 418454140 996228432 312400806 13377587 628813581 864728312 270871803 337538563 594326613 397433445 970060112 287744894 345559009 510013011 162521248 654922368 334123006 294863148 47451741 407588368 945672163 708847618 627151850 994221593 821662723 622629850 531638905 456062572 763332471 263165017 127675414 22064648 121644825 20525383 224548277 858942703 371786095 797656249 208649480 154858101 578192875 166370813 743317657 73657336 585799034 269884418 508552597 610369774 887680901 794935899 473923030 54225426 870343139 310391643 399110620 735202457 734839181 406097830 887542399 429005500 686418508 997123278 681468459 237085757 714072403 750935796 809301040 357372779 73659006 662141621 13252843 800941818 680490114 49458160 717327635 337606315 787458869 106145239 261937376 654250465 948297020 345364796 228331267 961471039 961587335 417303406 862797779 486830182 954283419 18027039 772314876 356405779 741394221 918258934 162611544 404084928 220331810 846132622 159289027 661315425 986552834 666908695 14357364 543832587 804714211 595710022 938250514 697385497 210868883 875394020 238402226 195811515 606870600 701455624 291725409 891959269 394627996 163847933 142584211 476585512 844440835 493589365 460247854 291164494 390307552 186637933 441967603 2478043 821292012 574511769 152539931 185653517 237881597 221467827 186277472 330061812 128618901 253875487 300460370 843637775 340729979 968037477 285637917 174298521 754798766 822532981 522728269 14091442 409421386 983696326 338065311 240201741 52675614 751216053 664082012 549128334 862463490 789348119 783966077 693464224 212584256 318674131 129659194 61510303 588474356 934559493 587357088 457306416 290334054 332937022 763963332 977272043 530935922 348528961 415640285 292204021 663316115 382890707 987136845 391379853 616817243 89503850 722730744 48383171 336064445 377706484 449848476 768107753 3666220 713048605 689379944 515702205 299733276 627871412 77663607 46730516 643590980 995687639 673221695 210488130 541439899 887441028 467181189 32221396 618810872 377890116 3011005 483982073 190557839 969789812 424658548 892252657 255103020 612780387 319347485 221633101 830989530 17480422 610949681 187168074 570837933 171277538 219293937 364995430 399288675 758559993 132392118 353514957 827126595 690588862 846930959 656359063 712790664 852240472 522334492 357015629 350014818 907390421 173491842 668097316 495514834 496834159 559919362 68546378 996090697 553564336 126206659 132370116 948393114 149924386 584612260 90908043 735798265 111159542 559883323 401346030 718578724 570497336 604096245 326718490 772809117 662114520 563920143 98925481 130040572 360489438 865587534 381803849 245993176 883239931 336310363 365353261 339088927 381983929 317751120 538760706 600210066 363887563 915165864 61577859 954285891 825391099 847661511 621239535 869882965 203578599 876929720 413132137 926847897 406852542 86271425 796103501 143380599 76299885 98615642 704645971 31421934 150801029 3051047 30544089 901123133 275183920 549685244 838313350 79739036 246680506 358947028 15002004 543153862 899930147 487414081 310934419 707762420 311601061 52280186 542695931 165295696 648306176 664675568 381778190 393090072 626328828 102195464 830369501 597309434 964896013 515308235 743326891 350617052 394601056 780022854 968103781 373062643 855745273 989023385 385632424 941163215 349138536 114483959 303541601 903136665 114259161 551615004 94196063 626113774 821991504 801837826 178248955 835138036 901401803 114047466 575861446 499604993 606968941 705837889 40070486 977796288 782269025 555434091 430012530 438642820 883821155 134864791 325625036 762701549 37717234 681672664 108291935 701934027 802688860 574242612 207347308 629499940 394964751 754905998 96885300 566585547 92018498 229346379 542767546 507311128 547557090 765397700 27367163 57021148 544444766 553008454 640083404 633059333 394625749 889352550 836610302 704195241 474651165 121736924 695747821 530555185 202278345 369796042 890824121 362132464 457298561 789585966 299279519 618815102 972753591 957862144 241801769 875199222 206827905 419618022 588790202 405042476 855883662 196791308 242967021 315175085 583524881 126938132 770377967 696705823 475705413 83691835 483501657 332014453 398519931 565914976 213847748 560434909 449465991 672389303 122671831 411850120 170562198 676562985 764404495 576185391 874863772 612333516 233070766 508248744 334086604 437834633 778092189 642352676 722714195 377675814 302685292 328723821 393661696 636642130 972898776 433536252 436488709 524386503 442545035 840614724 987083710 965698844 571276394 242279904 113911943 45159140 409352737 615924515 264144986 45071169 824986971 320578108 443498294 128680046 509961911 529159216 795583521 775770893 259706109 522587255 862145373 913393948 404039336 590309093 33737590 790339430 729706492 800004392 147367714 957463269 273278069 90375913 986238218 181772623 550522756 563287008 12209918 753929434 314820613 427525383 247069845 183170273 119761730 562480170 144012407 716495805 260237232 923970130 701124504 585485305 505202837 234723145 447891301 780253865 113749471 67279724 245476213 626147117 209888216 886258233 512834268 569789658 195259863 661365290 647213 446525845 547232971 38651294 612952622 708773338 104647475 470190049 407139100 642648253 389676640 615082723 338059240 189262880 651517823 384275978 620198573 348456197 264989148 811667024 558020190 873512534 142613343 786245718 487621333 119908945 462279304 838885090 13214619 390060604 839182549 237751693 984923589 675888170 862223441 587908948 715325880 123071531 1817616 275112502 590794013 660450227 274746150 975590601 757158716 171470023 453036228 747953206 317896849 104698073 557360676 157106048 732661962 427891361 357678730 165905334 28170319 406968150 837615730 626873900 603258570 550702118 907840549 895921139 421521588 306787518 430569470 57935493 838220030 328208993 747636618 841299377 347589782 281794465 597147969 307701957 485134154 707275229 628022618 271389277 783502094 47822292 706428968 612644080 95105557 72408413 832463074 810210905 982970097 638201553 409184008 952126863 67580734 424109159 127511615 321287866 705569930 945657878 394586320 43056285 155149934 895219429 522364588 951510172 162269995 94220271 571741808 8973089 833292252 863593196 237867514 360724123 611920207 568434881 980790788 640247930 649199304 785412970 19395826 330062869 633539824 415980260 439930149 526099490 433719510 536731972 499926647 159943202 633346359 661108802 148172826 445103709 826846982 262791476 908402260 922236751 942398302 120309151 207868183 454205356 25895175 23963562 725272590 320256674 434399225 311317318 264423943 481809184 63794039 737249336 635395925 96457662 788774532 919983831 52642755 117966465 841159021 172749929 794484627 218891895 938375669 576003138 412949800 603771031 774467778 766311412 119690529 770818334 573260622 296051303 613505800 74916047 794972664 286044291 364016852 513190687 933696018 323781993 836008084 688434246 439552263 169416442 630596765 460969278 369208427 69286711 763623511 760977751 911422386 730998184 375041416 174157429 193323323 337761389 344239120 261310227 546745141 570017904 667467132 92222538 593866913 201344660 131782742 523592164 873355829 434651032 458747624 144217322 705086089 867277522 997713482 248720542 187002306 450219205 306613475 791489804 385052266 943107418 922468316 745079302 852994806 371517377 697556127 312590835 976677672 307336070 327113339 57544211 331804730 164290225 237769866 557733696 781167530 811089697 799740521 807055013 909372766 892556962 524113444 501184687 877590217 882294212 943994360 402899573 678742276 557068495 776136934 407822366 917746283 700233235 359771932 466765169 176520425 398429725 963171928 796465424 745750016 324669582 140219385 148864925 609891088 565821490 387476249 175864965 574192856 486238862 856809712 272866664 652347871 973898030 223527502 482443041 192214895 572389559 453193147 153112201 815293557 126787008 202077323 989998371 251045505 574590233 697089313 971879872 263100035 441326507 394821652 964705380 828541864 867379462 616965615 479678605 997739501 958247472 44599383 434403470 694705603 49910656 4620 174215759 295803056 475909621 485575768 776533298 547719536 77057506 688415897 553349796 217951240 240403153 165171753 325509538 629840153 871486595 73784139 860947510 578228906 612469032 710099555 652160629 670039066 378792138 631018512 646814320 514093433 178452182 217400086 977076745 584182778 846433269 630712623 34262333 86439738 751921597 840533554 865881117 863276130 739196059 941278862 557939597 875787762 844307045 702609563 918409705 725183781 140725065 329668958 318681424 269999587 577076835 134553106 94484478 507720160 494982276 442027293 94215518 374079162 169613401 511320716 854157955 846919628 606902123 45393393 654158579 939069769 732779531 271328580 781392079 436322238 951843574 312407725 832181977 564560200 179685763 433615568 456414251 288715105 924688296 725668087 16382146 190385139 84224367 584291488 851043112 899075251 836904306 717314457 108136275 647333977 952149045 631141158 188842037 309377282 942919396 390851164 984187592 681435387 223854927 371945407 101246451 555681955 20890821 483501348 379662544 783580709 717164371 762660663 932370867 19489928 970304130 27632585 552196069 911772968 902908704 937372054 608066550 317890951 973454185 59995387 269306565 159234900 104377033 840750065 221779807 365591028 761133330 776392782 858722188 685219187 183166257 895385384 387835520 307789609 420606907 253748276 958473354 448435671 360219622 15950510 840182882 613513157 562433051 89515484 423082192 677884825 812730668 555831055 539473900 599314557 599692519 371307860 445377263 366652563 545565816 276454243 633375400 204181700 929523691 830512938 899008398 400126597 40950112 530817971 45797021 933345574 391480592 708076022 500195994 18455943 986938319 582851809 529875585 707739082 79526321 727141274 877962676 79716532 954828263 70890720 25077656 107667627 476779568 822454164 882553300 872986810 904679093 990545759 489832938 958153667 175896244 317884678 5696407 215306995 735545534 791860096 401334605 74497000 192304073 411780503 764847445 781042696 712264905 90721068 557733694 204931561 81413331 484298873 966409785 612822770 53965690 320306671 801806399 130080388 59998146 968540475 17099443 469305960 770617943 227603611 356543137 64369216 749340428 7000624 602738505 797662367 412647438 522287426 236605617 986724199 598445568 99427019 564661814 721653889 978828787 944164286 682622519 536916094 22096457 545348686 268636335 244189188 954190899 834298337 272642250 1322333 27098901 256238651 158318405 193102680 312922854 9489979 566820191 351892467 355678867 488108157 31070360 101166326 671635663 103055874 497719386 495519842 465521343 202552279 513917637 397944688 452963468 823501289 530125905 294155721 780549098 60129613 66206506 650410978 492943583 947294492 164692695 879498766 176417166 459342740 44847878 257822225 503728881 601461265 647931508 787437490 770407689 859528945 886263206 183748000 709165337 584555365 426897435 149315752 982792667 185343741 740949469 659647891 22176733 11321101 947775461 112871310 212561913 370457154 199949377 818272467 443108457 112620202 977478545 422240169 624439497 190641066 355079677 464482741 401759442 399658641 709794034 903528147 878344093 924446966 725324870 791327498 185797437 637688473 132780938 588850294 321348167 177960686 196305644 9033161 687199053 470983656 975629442 457441932 824593917 976442794 817371341 413370569 759989039 368105142 172383248 152951843 639810397 193056312 386203534 11232214 863811699 990772252 824998669 532727893 327915596 791169889 173655978 385702280 262980966 108738488 576584626 911205497 118264277 812906676 742968629 419244770 358878638 628471559 282891750 409294538 806012513 136260513 449389401 733491886 395804221 56144768 417430175 292679415 343312640 347923789 220291097 73829471 11878394 297006459 412854163 78574337 117854288 620855103 944118841 492626768 640737032 378663293 925052407 659721451 335282292 238542937 629905406 556923999 981768070 341273889 224378937 407341552 127979314 286253235 741578925 940419015 738890343 653542923 339332644 7451354 125621918 819859796 133390914 393410103 487152198 573327202 726897003 118330940 955125462 11634185 395389989 828311182 501655205 51707167 547446816 427733777 470957843 314626350 667231178 750005020 673856373 749695886 279944910 92795465 827341884 6003038 698257181 986790831 893496800 179856407 353633431 574126434 867094221 411035305 46287651 197146258 727075453 161598687 157712557 129009528 254626944 532037568 248924300 283034591 989195561 216077511 260686136 74597192 545090199 799630319 199460887 419650553 903330458 938808230 80863105 509250607 687258038 358023402 516104714 192282642 464345224 327358947 148065974 641569472 699774728 429212299 887611287 461434566 220495681 593230524 319492110 98053909 747541502 384234700 771906009 560529399 785968408 159531088 625666047 267866786 88406078 168887608 760119525 87302738 847781025 107295179 461849949 79650184 12200436 588236227 781092039 525075401 425991050 49083280 847401869 115540917 373364559 278144477 501498347 828747912 199694108 386614149 483289079 722030747 565953402 610619509 712462818 149636139 771920699 664905990 891059850 333300414 544068717 588195054 893551473 348056052 388582685 215106954 196849114 764403459 233706221 933267471 281914058 111131870 908644238 618423794 145487416 976206517 161091280 673027312 44813013 989530389 637589853 495570139 340555244 113159370 413227908 624170226 19056589 714319485 868285711 523302976 11751562 277220633 340367742 93994747 907650741 971736878 820612281 478400323 2288874 58795250 608991301 370057125 678556685 683687010 717916121 289685231 754516581 196729570 348567074 1442635 109801824 198718832 615728655 572453148 725850305 64224592 228925860 786844813 490582479 479565347 190153459 737704319 277045420 552171643 669162677 827109338 870530230 245580190 89988087 505557076 349455433 794008421 844763391 757631671 903746075 58177940 528671995 508155133 583474235 702126584 424795786 786562700 608455248 902827700 218970670 125800847 5881935 215353581 325375866 951057006 931728892 228573003 355453842 198211517 437189297 996788822 822348849 425942151 937258916 641771776 969216192 809640833 724907128 890060003 797372023 480881813 722552038 642627147 810122869 834578935 142057758 678417718 616623034 316582820 292156062 905065441 504940096 776881197 378539685 53625876 630433646 423163334 728195209 572711217 298929388 874941984 737321191 465347022 315343869 533434217 924841558 924142281 192286459 299473369 836313073 737631752 639244896 899833439 203248283 208417387 952357864 908621093 374709604 983627651 642659197 333643874 203259573 907686444 865725209 172388463 681116690 335359908 892222559 765123343 617978102 446876556 786382627 494244264 871525923 978732723 726873274 770970590 764045072 241474113 979926772 373544469 519492488 373278639 897569486 462201986 190942368 307941497 911650943 188302728 996991462 675654071 848457935 977383667 306211560 837292086 538411433 332453326 940730511 400292354 891203197 854746918 978202580 577235735 192505206 279512856 833033602 148756218 774079517 366651199 775319262 934756418 88650025 783841755 562772392 590850913 486080616 114363415 953634030 282106934 87735516 67916155 609127312 927585255 560336094 280354103 274618118 426528280 252129212 61381376 975870630 896212341 856531446 363167661 238499762 952013611 729790761 137661788 15762981 223575226 117910713 338281661 325532988 621519119 5957855 263052696 287774536 689671768 63973140 396604674 621807604 281799819 353015596 195856761 284499599 236531058 795553721 358613461 277712457 628603674 12982175 216936129 29212004 620123636 55081887 915288701 802092741 883720008 462177849 380806000 773872138 377425678 946342939 34336509 116817948 935606383 990529035 945545264 861800771 101856983 109478794 619598462 830556721 628200243 813082626 671747677 500868215 230405775 802154104 426435816 735737382 525377347 487393506 295878870 13403467 632360558 494683604 675853235 716074968 481913960 224213004 175616755 337139307 849332857 406820937 995114575 990094831 578326783 60389038 828699749 472778171 335160818 377888933 571492515 289712860 418205260 665342804 183406379 101794321 672138612 166329831 545087357 354588402 362561922 699620953 508263025 915412425 724523751 170860651 967535710 844045440 478312762 618702824 795990249 354025493 482114252 128335187 737825808 911181265 507841852 287372365 377414987 696435363 768467733 795023405 102832947 447611416 383225980 172772323 193055890 819087560 194083434 144251982 576064674 389384567 241630698 158599936 562289053 488461079 684606705 244212907 895918777 724672872 467485262 192090453 606392168 885173622 884610258 731378795 973496796 616649862 348323511 323849274 675936281 839892552 88641 910902853 409023655 887905416 920004892 115990117 273434345 993684430 260062968 959085628 805932220 164752688 992593090 661784224 322923164 569607216 726437311 908111634 61391668 179153843 615675752 183448956 718362848 449072833 942269729 372123702 301264063 820186189 950764648 435937320 898920739 202673035 76490735 500680078 153023504 830595187 203429737 806992948 301774900 611197380 578613103 551684073 146176939 913346429 524198476 196111935 603791804 685181854 897639821 504077737 428217704 594414257 806403205 532919033 404455016 597338961 39829669 886779837 426204209 305359389 481476936 423328386 162499599 919656979 717206473 954623319 769697114 271832674 585597959 454288455 896286172 148948303 448179027 327124215 738247193 332758209 276375115 222658565 847416300 574611801 666304605 16408811 741559914 988976885 878738684 461283209 836297322 477211261 328041204 704934427 584328037 340288068 381603651 605184416 794820448 450113494 211734740 712774955 786615970 881227081 574368038 497423153 102098772 889541963 458078490 499245886 369177985 968509070 139833314 681927875 607743093 789588990 218533788 911124170 475653153 320463144 48771403 2919584 214522003 156947660 20910980 526433380 205207016 683028622 100154670 566808274 674249339 114969223 335250900 394944109 674814485 379500520 701592498 152135032 846046735 556417261 824196414 363923724 60039054 196413237 74079731 125496611 327964241 97834714 234959889 3885495 453214913 378169229 542623691 706727317 42990311 551321206 344923401 225225917 932532480 662669382 449007917 111257720 753405121 183355289 183620384 560510424 942290890 738394764 813000658 141982653 610258170 72429622 244950742 148421825 545924741 570320335 137787883 404374167 934189480 175857948 532213120 642839985 190904261 21651737 389532873 286625176 916390830 49491983 186353110 863949825 121895293 161750440 246402349 123132925 930284738 171484417 747529768 159760972 336458781 341259406 92740484 579070756 205884532 395638906 523510555 610219466 257457411 690626101 650311304 580017013 257502049 333856774 177036109 420532033 554874348 551166368 372807014 866741806 40150011 421177990 753287282 592332755 886591377 540908230 440008074 494731533 123054199 581477861 580981579 9356101 176302021 990410952 749940851 642568192 348649860 753264566 454631031 504638837 671764794 478324086 623073843 609677494 531414926 268633058 133971712 151094897 634589508 379117658 7504712 919334177 271351801 315553042 508799109 339551850 127116275 472362305 802965017 458526068 468460795 864492905 250326627 376129296 694452512 3878212 779431466 178374213 482240775 947301562 169404838 553502615 152351668 63248240 227995296 684289412 34224480 638305613 587602970 792591903 971615673 561985642 369551148 924134395 954056896 582145297 533254850 265294238 924153085 533829747 573270805 961976310 134864575 580624550 925281344 578511789 879896034 742912958 624653378 32620329 134921245 59120892 830304925 399883526 175248125 77845679 385193964 387110632 307410955 296494743 820741852 94021515 129212778 397689951 543407884 439804055 608312271 653157670 310954815 738786362 475163408 472155150 928854069 852174052 753087116 37239706 707032720 488904412 491231900 287008342 35978940 781584160 994448267 182674398 796582129 424249045 691498763 413817772 576574895 996382455 133323077 753760450 216542035 315851482 687240877 16802279 518195691 260154144 180444224 296820905 29389400 897756363 928372839 714078008 300614000 796113272 342219761 869263990 242911318 135379965 100483609 616453395 65573755 767532135 715835589 801384355 821300599 681807483 401321394 205407679 46272054 707757545 360144801 373597290 297562341 686887309 389495114 436415791 573009087 253332797 745788821 342991201 801153833 434601452 921137716 382248259 420150009 879578024 824611228 192237419 529603963 368051831 640826610 963141168 508167769 138243853 94936182 575771207 272372262 788811640 40172809 181154764 402989643 39975177 559244657 697301149 114594540 881016704 323725872 64187251 646179888 956080402 903933575 804985881 350649594 85617121 958935270 706280813 423005214 448779754 430375799 364442542 307455869 97658020 428045183 395522310 345448615 621603030 666647747 410779464 31676336 882771171 59896974 855429613 70008771 273500276 394266344 874433615 768395533 114359247 310921181 423566599 478825524 419284614 258919262 626988358 509531948 104674120 392105176 791908595 107509557 395744164 711520829 217980111 236550920 16697353 342678745 510811026 4806717 456684881 840587361 816866724 452249806 784707213 292124619 580811853 436139525 34447279 845088554 212349441 564915326 768826824 951756739 699415676 445564073 415229160 813130870 557792390 612158364 489408263 126650423 666189738 763046044 474675975 527603248 244015872 314799990 897895886 340461925 539331621 338866222 126402643 549638689 498664540 146348388 739535238 452870325 749718336 117378015 578126444 132987727 452554921 827841970 996948345 284128561 651804478 666574816 749169185 832224177 893803319 734371967 899577791 375756077 294838383 94606452 722503161 200961688 267896709 433409151 372637009 138394000 351750130 957824609 637888873 848629681 785040052 647648799 154956338 300035412 930874683 447921557 147086777 483704578 871395275 754952794 209311636 846622274 352879155 2887160 588449647 240655036 688671864 500736054 528906890 149453428 793249457 950581305 412911685 476361485 569781591 742489672 328849540 473651020 398168668 306264769 118327465 606553355 493544486 64296892 5963605 320633384 247739137 833757357 189594676 317063967 6664622 919251961 840025820 787715492 259355131 498826411 504092679 794644037 869700280 137652022 568553347 427176127 427329108 72592955 630271115 219665025 869486200 53917698 951486683 519077752 285081195 697097095 141685183 986810729 307163339 121641891 677653948 362772782 365253698 977395323 613653831 241182041 539957979 487156318 39913827 218815783 234568724 619112343 397757627 711068356 486528834 490542510 742484974 43439493 196620819 149517269 423991558 468497812 813792891 799048519 112834428 186740729 301447584 862683015 254995886 627040207 606944809 610956522 584336358 43677512 343150149 788008517 658994756 914679534 215608156 115695640 789297230 316646000 869325424 758537810 110397000 862748913 650937861 731188819 276198290 89625771 784057969 179277679 840741159 2791465 150125892 239624320 847592385 953813852 308573841 451055201 394450544 980394260 53357391 480759971 570851523 368330025 72092470 789661174 412029079 686873388 184388809 5925883 670225848 575617985 482675980 797785567 996522199 441046649 168036879 993758552 5972933 797487170 34623173 889445203 890230516 355658635 689994545 534144119 998242758 751788889 113962168 607431058 503847737 723706226 68270347 829065330 968853884 494988542 379319674 794714834 484853800 96898547 131049478 71964964 198593877 853483751 930485653 18012966 307824254 426896333 560798875 974273637 345710325 719442813 191255468 775069052 845912097 740395858 498838118 529513906 766530398 834360737 840246345 550808297 919225524 441425028 986459462 399606066 841895452 180258073 47281375 594372849 736464366 634547838 284249672 527916330 137221059 116757261 720702449 373394855 200481341 650972011 877438496 474136781 808578239 584485249 590657912 290976374 402257421 27972106 755458603 714088276 381093986 81664986 672235122 945622493 461815078 585580190 377829735 8215848 522347594 107890230 418098613 332674678 72630500 250293046 278463504 437022478 400359570 329622271 951895772 821674488 209044366 529845895 399127718 289575206 56887278 330659690 900691381 968101184 196551306 666634636 920756918 288702605 197162455 219882294 516030015 331652080 59346857 793663816 343448831 539646459 623941379 263154387 679847669 919648775 588923221 910131970 497869363 559514619 467537426 53362233 931473654 269468878 493482261 220488652 24639362 726968914 252353068 290812582 365299722 890190562 398346538 134061627 358020442 470927065 457469781 242445979 535912124 505626938 279554909 388350528 216958484 907480883 215083242 722432341 632487188 993737383 522949061 902894008 242052415 469906769 53203734 266629239 363334505 533543529 804363572 328405623 671480487 59815434 476704808 326193161 4162747 729471902 127816457 642995023 321017429 831286722 830193805 990543603 20036286 485692534 580530084 858115694 376847238 822577275 168867369 91117964 915798516 296273407 726053374 267027766 244280026 836732531 572601100 707850166 368280952 844834830 932564016 475897150 792825606 331076328 443232301 881714089 686025098 554161344 10687284 374653072 807435642 535569155 117068088 170453581 504647804 604301596 981505462 615784879 272346083 190609213 353365788 397034162 653985168 449311098 89543888 643640660 355876227 706029037 99867751 477868751 922630209 364198033 579386803 19743103 689574941 929143270 313836340 606259249 855071088 436154491 386151864 534286218 520718654 514129975 378493651 84326064 553495158 313245221 427968316 135438483 213873464 168148182 874138249 768604756 768658841 748469892 72013171 685348217 702308614 486608375 297528642 339969629 265319804 906408830 747091629 464048081 983636694 669025272 608578513 754772813 69715149 411427800 563082359 362514248 334197222 136315060 358199862 13392233 474265654 325242246 331036780 192819111 481450786 732127063 107115770 431729 411980016 337759416 354902337 653764203 832688613 605800145 986745613 22540440 966679442 932861179 247977888 239005999 385762714 131903423 818366268 727351427 612537813 180360710 522850285 958528261 688422547 118726544 732598166 687022864 861136413 776502231 202039195 377399090 587674979 429915526 223773012 529762158 514595864 523602970 531887284 704591135 878973397 286443598 643769117 76325693 5919081 547965635 305870116 473291737 367984836 639684350 439945492 773335713 574631191 51105184 782841304 852281235 121842842 47516621 94796233 524027090 949176150 671005567 172920037 851528480 956912483 420509114 574586099 733973969 894776996 771784568 742403437 246806114 311442604 59315280 365158350 869795314 262667278 849359880 934905555 418197710 518364307 336631249 151574308 876669205 801625452 470322046 132667424 454288363 715761902 23764585 959590838 507503975 665794215 728571834 810258687 735795768 965954110 49073155 148026232 977553653 204344689 185857832 929889446 928408605 200285320 502091829 67971873 254093278 635861726 696258959 708324385 330263564 662673137 783093018 764890999 77712719 780394145 256802281 336929028 718849118 438880105 532646242 759692077 947204650 729579990 791396131 594762249 751009480 532950436 609460367 553085653 990660022 905253778 334121881 759343632 705084653 401284931 414292340 641645753 336671541 640272667 824982256 432811262 142564445 172755025 135433597 938289546 587611894 480366695 196664124 568549349 610088582 91143369 214587113 864585865 687981946 952803528 591638325 198783201 751796779 211264714 635539091 812329231 898617003 232336178 579758698 805666810 122560419 953115969 665679337 310500468 539099297 532564158 237763311 234967156 216784922 762981551 672290919 129402461 552558979 68300932 149465534 42828852 497979134 589874960 102051386 757844305 848708042 916015427 987514729 140839857 754503763 474117012 519513198 163094648 185366995 628270516 736315277 888154992 935615921 339005700 24062223 9227161 128279734 295657444 69503082 294852969 903631084 803344973 924197180 119597122 399262577 592350498 605713609 64749301 594078673 829635227 696369097 275155313 821341373 415871069 131247288 36139652 333518724 460613065 410912249 238470565 533809792 834339280 748967436 360672939 178141021 478562130 481034443 615919881 677171922 199122149 363239961 859540790 790362683 600378525 995674014 901297419 231191543 713126558 826117245 4074655 455138934 606688328 261667840 499213721 154024555 443523782 541781967 615812566 133992794 642527089 448368651 538874239 579021931 412617726 58449622 317068052 396039601 78150887 650976699 644515430 668874252 3335220 416772943 354706425 504499938 523492941 433158324 167606323 519486235 24149082 868667529 225938227 410869220 649949171 741956910 784135171 556133882 154574129 394415294 411846880 998216233 686625173 79779376 735647527 688542450 966208796 177413143 727201157 739105975 10250237 670568459 518115848 651579062 117817269 466377813 105872991 335641619 880916047 608186161 161300689 646078983 155791386 677381788 312074086 682838505 336037856 15424088 891829895 367375387 393095133 6332986 808060612 492753871 971883244 599755030 663080199 775138630 798146357 27843294 263929603 271740530 424622589 535152914 6236628 562422263 819860219 267071586 357675795 877211686 454919653 540908502 839121448 528167415 863998947 259273433 960137549 505005701 729298188 630571646 284457258 7682628 829703908 698474041 419045104 774457941 412927646 397871564 526126041 213879369 823608964 64199573 471507685 683088558 15978938 339264694 569139840 47928258 365532921 227869998 686696620 689643522 935400287 797155041 9350309 350762588 898791380 157166239 690021201 766880055 566781439 698284371 799457685 761543277 681818341 442673060 644713575 361193732 880448629 42423491 70464574 291646113 21781314 815589456 67649266 350357034 34676965 847732368 823975968 31545777 539953240 645076510 944509435 311655779 157815293 428376893 889701482 552140794 582992394 193193109 870683096 527803683 83561642 233363103 614248628 488223280 348888294 924809198 833032194 894190622 546493400 181359516 82640544 328447317 490733815 417132061 961421757 245845555 149810788 468843699 604150044 803977625 59443750 418343809 369364314 689049308 855200509 774303123 209116913 279855021 777798784 721354267 556859959 422949683 571983982 927652190 213840641 832493883 954812416 66209481 371869381 478087876 838558503 339258323 578562451 216974772 960887006 830175436 796952962 557032830 736094201 351407848 949833329 347396251 28462006 97128191 820500018 90141340 532199959 696138725 360796277 239314800 281378781 721170760 553664081 309256854 893197272 823560178 845849615 795084453 323911386 437101297 404198203 119653681 917975197 719835494 454118147 635811833 386488361 543861527 983810679 241048066 918757894 988659444 87163465 564131099 97779956 809223875 461273055 807565046 894823247 923987228 126720747 609558749 676491 594810000 673414804 122819846 786264774 775629852 843491060 622892468 143300311 546255036 72572672 760571907 539617716 990336441 310238795 142698266 719043396 936787545 774432115 696082723 684931529 122002157 412995610 448823011 604232781 914158046 42607109 228487047 227056413 715098441 869556186 556647477 252774618 37991697 966335513 303604034 460647894 705985982 857792204 170410893 868364371 524549261 509184611 886123303 121311090 577018055 735714441 171201476 282650202 831305705 495261447 199503035 444247849 7665089 104112316 70560484 638351468 941241485 50983496 41306160 641382817 123869608 135544326 270091453 175191797 313844636 28979188 23521868 48953121 676250701 703937475 902398367 13300648 225721129 815281907 510477493 873619524 570300199 976374635 566062392 184973327 754934564 800310886 814124607 103665685 358685146 10671522 584229575 804469406 474523622 110074059 558282946 908574616 495345296 233499867 257296286 919433545 748926923 604681766 79530933 243273416 794196365 570473797 358334125 225070158 861080213 79746192 892952363 587166656 982003183 729453959 516359718 742837651 597850749 967715140 550462888 119215324 887129094 659536655 302898284 113973012 74758754 109931938 238923958 177478420 51454652 967528597 340797139 2417730 33734243 179648767 229208283 169219366 813401399 147807532 405226972 84710075 268120497 644071021 178123346 170389899 762304867 783609278 147266759 663805223 967177949 349108082 21676552 18911027 353237715 941184014 724027519 394285082 453935325 775759970 631727887 424783039 184611095 972874730 553401702 920106398 415858077 555442002 571881907 617314028 225264942 775781433 951263898 545078727 282006987 567131680 4268518 148440509 48602612 418001747 461668388 960920554 305559696 393857783 119603760 311171992 397474111 285206209 313592704 309048092 230023756 72570636 243483144 719065109 777898657 478203459 505694135 662313445 650103801 524408592 607249370 383450905 792837944 858925959 530842824 495423341 821626780 562197289 900291114 507000026 717315419 653962025 92039500 344840688 458044249 346456646 711147535 303710650 940618984 367111558 228985988 539286456 652391646 954353792 840074288 213622963 305155838 597392750 497052241 474796317 65666691 887270652 890948877 186079841 541166680 363271292 759086182 419081463 285053278 280211422 880931318 400780665 898568600 816522624 632961052 388183291 578462158 675450572 952419603 996354854 726680588 689031552 198151372 746572185 575697450 657315002 308724150 250605827 777934053 457873120 897002431 840734407 715103730 643591971 388799095 811731456 751349225 417169517 539237411 568710097 123706882 942446824 250139371 213779140 958907837 464888229 288440841 514023147 400666228 538021594 506688008 703451083 364316141 236504481 902237069 856128502 68685098 888806399 304989002 276854735 260045321 406789912 74650930 876737488 250848840 682087421 155256871 525525388 827201923 400364892 779625782 311417301 695316434 73165820 1232654 336189501 911114705 756243526 69799701 970083228 396699963 506141441 411263728 385002894 272257871 576074009 558908546 917408102 377191320 122217880 964910244 461828943 673235974 599148854 648106 92173387 847547561 197146682 378913259 603534021 930266200 609419727 46064150 128786199 270154538 447412624 720396279 30129940 430965813 170245525 882742770 551459448 434713101 601316595 667132224 551032979 426273297 28623406 405852382 872509689 575238986 880608502 181516218 463199338 279886982 468945875 700894198 190975821 251756499 247085621 682557540 578285750 508570173 377242172 693487632 431402212 202696057 155473762 957332745 400074285 842160308 833705707 608445676 476699698 240877926 769520759 45970380 33717387 804519551 224122039 590133426 280438798 84995566 88388936 519449787 346444588 280209199 806908600 41741162 231855255 146050561 503458367 781806313 787882223 673253954 807888370 243915213 660986593 887369055 611540544 565437444 633916570 880601652 694555178 505388034 502855973 489957051 512378072 771337786 92716259 61066764 456182198 33340197 850930838 966087792 640083752 630364956 827620351 313900494 342812838 42722960 886375661 704155766 482578837 844431275 203932470 986794731 678333220 65218285 45099795 638485265 923455071 942720166 363251432 118320133 851657828 330544356 955890059 274067066 718731042 4068567 258127063 338546903 306034781 35591500 868451638 971667258 140309932 495748097 795916230 296800164 641628971 445142413 613990612 155200697 836099635 670492920 97518828 180086772 373878554 130651809 630859666 322197028 323853646 662174494 94590172 360496439 464408194 296409487 365837601 869909606 618504402 542314263 503554495 189027309 569222654 450007527 820860004 760138678 114460619 505729229 339517999 195718529 669897602 395582208 391373897 97959734 33194299 834551115 640527555 787977693 755710101 883154357 105873880 669514081 771255019 548952319 55990332 992468392 760004348 841859922 792552376 187739961 642878277 923034432 263910799 301746 346419550 844305507 495540422 356030815 717275392 728803466 164561453 669301718 284753143 357396533 552763965 647878332 805668202 94690148 950199458 601272475 832178024 569401834 198460782 571657402 907575418 822037696 436026062 613409893 166491212 326095898 814960506 845212566 639439981 613284963 534243585 591401071 438388254 736545898 913406406 63825219 261478576 853428771 176763666 243932447 705388630 439095618 204310477 231603804 899920311 317507552 232253363 907409659 683566500 570526057 522964943 530764339 75989204 307436068 748288833 919822751 107055133 117442637 950704928 236432269 659707786 847714146 426595403 524231647 806014277 312860437 698104518 406777046 41522264 101317825 614415936 407430844 527313188 805950230 943404180 356428334 223076854 283814589 293485949 204555339 286834398 766226707 370447819 573999942 541456357 451573788 384633320 5417496 694720417 412119234 737833348 205640450 212079416 60676054 809510247 199644191 582859550 348537130 794394242 948048052 113575879 317130143 115227811 711241391 603999891 752402995 520326594 433692490 231482391 658136228 136725564 102464273 253923794 1298540 797676455 32346001 240471256 218877987 580756309 401727716 845108684 286297165 135868084 163091135 585924236 2966447 787555079 606699984 568335555 783871084 93218957 441795374 473002630 672195043 414497552 785147565 383066601 59377516 656983121 288050603 956756795 732759636 615370397 547011465 887821571 876284277 409190156 515919848 420343176 296296385 124163729 683386243 703277607 237864308 357924145 865894318 460045376 588213331 604165197 953555368 347485065 117032773 427264041 823405174 612931443 340122117 55507576 561535616 646783793 70751203 988950724 496910163 845818563 933216385 772459307 116720921 727835227 156571982 838329697 870383035 342565382 543588820 933837458 773038842 931779889 463859897 867293860 139608990 406297072 352259789 887743151 879186504 156957286 684123099 998119435 78921465 353159721 331765968 727064158 727432946 451205740 254850434 421082795 815824860 516051212 766058865 208067312 893713232 866435973 884703901 404968506 421459747 242434888 298555755 782003121 490498209 280315361 77921305 774818479 817869992 527190537 396350774 173958186 670783336 214679700 912774351 41018870 605757150 199540942 560364062 72646016 816536999 650568125 213954435 25751563 724046392 153055395 314463062 452397691 477719786 455043800 503293190 434524434 733161767 636285060 389102958 607951639 839774241 26958617 775527307 607246261 488315559 372550010 68800906 45640678 528044355 301777327 409156655 259335449 122718163 183670786 272229415 439704378 257119225 176461742 935337792 76834179 551141754 334201002 327517314 538792555 239941336 169969657 944546872 78396997 320075716 152344655 940183466 709111262 749534437 545045999 464257358 647165758 974788353 558411797 397909819 201639119 378878797 697965566 541664146 789315319 982890065 954036240 654999161 950856326 389956622 655502551 488169524 775852455 676824565 899523334 908721033 893601397 736359666 46510350 43900348 188227143 252968486 832856614 180183706 808252171 418086981 655293218 405651801 32327198 111705751 764700556 48681741 924270058 946745949 367627262 320126850 285094733 170090618 349036393 555008402 788799095 370368193 570297691 797843230 735188127 121208584 782507051 74754670 35506414 618011736 278186546 673680375 57930219 149109941 371756797 932918417 164276065 391185208 128685860 574517021 255250439 816307453 493505868 833783940 524479232 593586213 107017934 498352287 972709554 153411701 393942219 229634171 611760343 203585 685706970 189419122 455314124 591155269 52503221 229505082 528094608 788991610 606322086 832118678 870156599 988600999 755922793 202929884 230244396 634801777 77873481 831446532 172591217 884548031 384223578 124623355 457942381 800140617 728804629 106234858 480021949 161190318 916571189 966481187 770891247 878243570 510221594 540205256 787432980 594064654 829246432 177510061 793626785 792840195 588074089 156164833 643936762 227377763 745467999 866221616 29175210 591720037 311774879 547724118 531601307 356479560 523913600 103446065 783529872 323575281 525519414 538810354 530062462 956090243 544957293 435517120 813430696 848994110 414273353 88496564 125801263 886588699 652897598 32266237 119493993 1678482 156377859 595089577 796969396 21434215 789107735 654697627 473879283 65008116 497682829 179551850 57939023 939500228 751740462 412456069 658312711 513496700 616014707 531112293 648373770 28155585 901649557 727067308 56583587 47169433 739174670 285078775 996904259 985148699 239495264 619156883 451896749 104852163 460959042 737868063 541247360 52815834 922751464 709784745 141907323 685520574 62811492 124348218 740807971 621806955 985476436 767511294 859662213 2115488 183635327 720116291 963102792 798853831 301120453 553290963 288662270 652045478 715102117 776837706 180489940 6553363 377165374 108132308 44359120 813576958 653472286 179800208 576188421 858062031 120640295 215826128 172534441 126859512 315181069 950160942 476374767 421118846 898133118 905078777 494320705 352848377 313503401 395263431 260405725 343402254 875003149 671645803 54625505 354669916 531556264 986408720 464240186 170149132 59446132 683414684 813288675 402459434 256949656 329327162 907776266 721058049 995742931 140503574 79540727 206796850 685953800 696556447 311433602 935778505 490407343 143172033 893018640 307180227 460525911 426748841 308120510 487639801 666262806 804214726 376109432 344738807 585649429 406161383 618048047 362950058 12592156 495447714 123854228 683060386 298606759 298460734 564693804 878846279 164846789 344147282 500446032 60945566 437956107 583099677 483922868 686372776 240418181 159697567 507124825 457062591 36774286 557780176 306563351 316634552 128564008 934642422 547046387 56469950 555320568 925264299 65023763 658879450 351777741 89621733 732876921 93537740 110759650 584759000 751725151 840310950 120392370 941654565 547389227 812921805 516418588 324676750 129839361 598432184 768442738 908539139 654104269 371490157 620392571 795617733 794048890 19650314 723486189 800753114 747955117 942083623 533357587 794627450 551040913 111238103 916925522 903250879 642472542 244825591 119454712 378275250 637687568 209695059 836236416 993999919 29744643 320424121 591116175 60524721 390478583 340463729 184983503 1063345 940788020 761340573 283368719 413421915 812920872 825490748 865093775 331063970 336161455 732724685 990988609 502829638 16099075 143612040 429263651 487211714 772452989 182453469 198758623 216879353 739720374 8929968 574882899 335475577 888759965 613450309 183881518 283590238 949570800 420983515 306403533 65027528 441746969 495056632 257508563 914304608 330884775 628324774 680514952 442935413 392527142 71134165 15642702 447035569 484046359 981682675 217544381 395406632 910738597 665078905 447580703 699764616 908083723 826393485 343328111 271289965 324317545 875538350 52827698 471102421 345252546 257298862 808883850 147532515 949914042 878051929 819361288 796810084 530593719 692058634 740668993 233962744 206288565 523620760 256055254 358772021 251218424 444636967 818168625 476299574 189360601 249810819 626123393 883020684 63055650 602482182 443835185 637613476 364448304 310564232 535262299 785237165 72150370 786572041 813131851 313209088 653068289 733727696 427402102 131324487 607455488 59060270 869099939 86512041 616254513 375431101 382085881 544046698 222235346 27311959 417593793 136394827 612547720 307257053 184567152 818012897 788916344 984682077 638846864 58348024 508747566 823308656 745648418 693637997 702131688 8290512 637806818 691253836 454504200 872995021 569719689 353292496 721594919 426534523 193804356 89275700 627750300 885116191 656465687 612516647 203532440 187236092 90803684 341290262 90800085 11614344 316620991 471235174 171463914 478273975 21383402 921188764 18263575 321721451 301419059 790999114 416669811 404989747 16254508 818710371 175799816 659505552 354811392 684934792 125707615 390458372 141084282 424806915 155135150 52668290 873286660 947846917 814550286 596618895 239776225 615886576 412543833 938020172 303658278 833674409 485029225 123812525 982197293 277714133 721483074 373011486 289635816 568825193 889482455 462552754 283275888 632083331 575769433 372995136 680290752 519583170 637191879 312657460 93138195 799601578 236733895 244268867 827428316 980964557 749337160 227054489 918501215 594503053 37251703 48155892 296595057 965266860 74525863 859956059 265369255 196739823 479823868 177752264 84838626 333970249 848326402 951697637 429705507 793199284 603374028 539513077 842285485 735850743 936619894 711133937 441265775 924503790 925692165 233595537 270107552 118314039 465291614 42918688 616737482 564702044 724914788 156937471 367906187 267874806 811021688 550383882 906063731 918634166 476479551 757400887 308539175 468277030 912092290 367839724 31609629 474965915 588199017 156057719 750879196 228425795 979396950 238017979 986459592 790738646 24001318 36399772 756109424 498285461 810042149 638951439 232925542 275235218 967559790 749632390 528701489 132767704 670343625 741793461 107487206 154561879 613627471 789000089 771685592 482876110 469038771 375588378 888359138 125848718 593238301 451148790 911952153 488845641 733073489 421884270 155119348 432670458 51408160 746658416 993057527 276796822 283035814 701264371 767821119 601722977 636388351 346742893 560371794 351054199 531290137 631480453 972730970 520645700 915265002 580288178 964231230 877178047 534738586 61749448 718217830 859335106 991035584 721546035 240708141 834273926 909896945 911173694 902762220 254095246 594016604 814181822 293255987 92339430 197872081 625019377 278116043 116909600 566380968 970405685 818499262 166306384 737204310 529659476 448686770 975172708 913519075 51707492 61944626 483287090 415215816 602364459 415863038 54527297 304061487 277177401 844746431 735243822 800649000 643310323 376075509 694384999 650163303 15927983 316485249 886166813 450936262 872695890 590671799 174794431 603426838 362852615 987274258 398255241 689563286 332782922 498557442 37408538 645821800 223054539 274155309 55679335 487056547 825490777 72368643 892604019 416661663 606685363 402665195 109302636 110559234 254451449 267226263 435072707 708506134 723546247 977040719 92086314 232050763 343830465 125979077 385808687 854501463 986211816 477301928 392076151 232484019 508581977 210920643 602082099 895115712 450782739 735736208 457452353 914457564 173947060 936352275 925994585 591405238 582479471 747832848 94434939 373310283 219198562 971365368 165909315 538804015 530059636 674028993 363534832 212643795 305990479 458325113 160881043 140950836 726260020 672638955 925943511 221301743 77914514 199821615 723712210 537479788 637692238 281518761 348517460 726697172 931109532 851117216 657492208 390221345 409529297 253838774 25350083 426936757 585389047 579661608 263841815 335065099 286130201 360308727 436397612 105873503 215262154 460222108 18603927 59399502 429742048 955796298 631976846 886634374 179734932 230919869 445567003 455190346 8501528 627725238 15649665 202711988 927266525 898339106 749044795 665469800 327093201 670697316 675253570 321027742 308360365 969541728 835754238 254923617 881528355 516261644 944181944 479627189 186983409 716627208 855871165 774212613 764462751 319256121 67272375 120897615 894695526 35769778 79215570 272478745 888675795 726931169 778063696 96926460 392977860 39556160 715371929 468031716 68563180 760478902 324882658 430299270 641901886 496477775 149268892 926039083 294975951 704272412 872462292 170179616 121365721 750362858 374467761 452172401 15252074 73325047 458564474 45777732 707149228 755118247 801186238 210720620 372500601 173535673 80902798 576807104 489903919 658690862 618748939 65110521 822922409 544693103 835009284 362220579 253858557 867035649 225281187 921611481 522924142 727978717 158479036 261856952 603710921 686152753 397765256 400514084 913178253 779113032 848017522 277234960 944750618 445783124 773412320 154139026 854574377 524110614 387062078 535631213 94063053 323494637 995415821 911789258 25795830 439574740 851667853 26753159 139915250 773896380 122713511 886214406 484799517 428353651 514992553 111367468 651475713 686416978 699838328 649994191 455195118 394921320 501627939 721681953 381913836 872214919 440662523 117408188 448507570 388920967 196045921 894565576 163991355 934197932 60935316 608307108 373485526 306141400 738382482 80140424 129896982 881092424 123539372 794748971 214919567 608068399 297573982 633106310 478561091 277242168 423854661 382773518 829704798 53905260 656269622 890534161 699451083 867540334 52236013 804431958 312712883 636599790 113093929 2037464 416305027 17417916 349566013 714660091 530455286 527919250 756638455 111762185 753587328 120505339 246507711 831639471 19085785 729491640 866506934 923046751 399151722 822081214 27967570 497824137 230815400 288550053 740000555 849855704 297865132 993168645 929903798 953257009 470189293 798509457 281102022 730479465 93013845 877513327 420343225 617063673 245458355 101465689 101928701 220389878 630347483 579045858 380045029 412668046 798827144 836006705 408365892 289669115 515271695 779854093 373414561 576050388 826878756 361410041 323530068 435757764 617810118 423515433 930652250 403546518 92115780 257814037 265528477 346381387 776661050 879679748 703109653 810037129 77495887 599269777 177421321 85537982 594175143 434333674 700370316 332247273 423347552 302828354 843467635 723467167 3123330 562255998 237267331 594836091 742130685 704118830 290423056 924606157 429224916 18101118 142719880 319585157 155939156 611345065 900743391 604811062 841518262 470564792 902228713 943245022 901797135 568899468 49220883 485157797 403678916 289439696 811972137 944538732 552172700 767935949 139650713 553643642 932344057 235972981 527429016 825203603 433328473 470619903 807598209 869079185 954856181 965884747 841443114 769622003 122058517 221561151 228231856 421775754 747018930 909466766 767784401 51772656 307430944 382265124 620729981 413683288 149464479 979738555 212865517 825933094 526913033 685971186 495005013 952313633 298631274 378516586 219162955 414411772 258230348 796912489 42061336 341592928 206407761 453040747 468579817 348297111 460492520 14595238 387229318 299324905 806106430 925944688 766687946 792973303 120956912 129057816 914869205 472909430 518609161 146636945 310031918 261997525 944350787 657755914 235666180 298048737 798511644 817804679 749126295 876777907 469245936 547146619 95573332 896726935 359714180 446923941 209752188 242316229 575024008 103113366 229198518 322883924 707584748 604914886 757263251 481844345 499692340 230742613 92526291 924282653 376790165 443479016 335604255 282926085 706023327 506807553 508316815 52857846 337286438 267745628 862022273 145558561 961821003 253534250 497472020 977311129 627031095 769254662 261988598 658428909 841742658 104283438 357208201 332057036 303022982 694353078 940741815 656472564 592865521 514998620 31137269 227274241 169932794 364514954 821298584 856578498 228377820 660342150 65493050 844167426 680207432 213944641 34343635 394178632 475424283 851048834 218189246 341299868 436352169 487875750 711068281 559446050 942965986 254643704 698226120 159756289 194030589 580146656 788525344 499921618 409753202 564587386 188067635 972249646 8921341 366548033 875856940 83009639 85465465 167237817 799672019 726612396 205581712 26570966 4854391 656396875 817839569 878922179 158595846 637441091 433164077 606924904 569323630 26038770 231618874 482813909 524424516 767790127 628642698 57315019 950661002 298239208 297194597 857131850 894392769 872455537 537298735 937448908 892328692 709907922 970074930 126820094 938311443 554436143 242909841 122296631 941403590 492948431 888681776 429925937 686798390 29549904 356561464 275932410 989495957 657975631 665639835 499066408 894920083 755327351 768875054 358131467 788936272 710676303 660996460 716932109 609775600 835812063 710614888 413068454 829864623 297926250 390351317 352910674 814531224 137028802 100783771 11404630 648139347 997778041 386706212 593288944 845345049 783559943 67862804 959584018 113340518 129152707 591151536 564408164 457807220 897372221 778785457 427679327 265711220 172321534 548963004 263034321 570404165 832588624 688024775 634060093 479008771 119394535 565927498 767328426 279503120 744731948 269562887 484355379 374527109 431152303 68041191 110807709 887196322 930636657 382535343 292734492 958042075 460334057 596610458 968998467 996494775 521803472 480015292 107487296 533579767 717863707 618719252 946186693 458351829 749918922 870884034 337309608 18251359 462216471 177833123 426647040 877284485 580293021 817101512 121265244 430880606 727211392 24040661 767601871 515038385 974019605 636939667 593442343 158080751 881277647 544411706 749679371 90838846 213707703 96989038 186770258 156748676 646062743 603474720 286504249 782838259 339607880 884992634 707685754 276617486 203554518 28896638 923075374 449301495 854770934 148927344 462731342 541515794 104895382 279660872 936645666 635340967 448305451 426618287 780772907 422411782 837420613 118055839 278160640 599410187 632332988 530386858 772827758 944809503 563113618 293518653 965672964 207763742 946462426 339857163 854935764 689344825 668799250 601399590 414482974 366788012 150781027 340860111 786965698 69007228 19345625 928040292 407727689 163683305 549420786 836857698 501135320 945744402 270234398 23096450 691127117 42363189 213660489 269708450 558610195 586777923 264475285 988453466 593050370 994222195 962766534 136981818 139809041 810181942 723187567 826208137 569278202 924929618 609780344 246843635 993026834 281276810 78609527 407630663 701858739 223816631 438990497 953075324 202765798 970808422 414365017 365468925 677745558 877660912 678670767 424367008 292861664 666931456 988104426 36814103 609010877 100328443 198058768 788313048 677362592 774796058 853200790 617610481 970374090 357483806 774726676 220045680 784177282 277668362 943136442 437069994 591866875 310837400 542305064 378738262 563860137 391546871 634393616 774560250 649580201 560840404 623422107 343553508 995269183 216055751 766831855 814933335 337989896 993929951 827528859 12787501 354063968 211596648 851064283 871966071 427290873 125390550 738447237 384448508 905157779 725623654 977354189 276597625 913641628 638071000 754654317 754060950 358134224 410875479 211089188 899254694 864821404 877243790 806513171 201786383 964465593 867061428 357688903 479471038 373269115 79583582 458328641 254311411 194035854 465611589 823357108 268679278 138006455 686722392 994705249 168842794 689941163 821550443 714771361 704577229 174319374 493427959 646747142 569490415 24044662 890090048 385727992 163367547 678810746 640132167 700256284 135340674 626642878 34699580 816176888 819245113 391732130 203905839 264587345 519651184 501665777 153031537 349685656 437184806 152444490 759774079 632466703 908377808 982388110 630319043 517601074 83512785 767419503 163097197 364096026 673911402 68745581 77037367 845912540 448529931 314845726 639606788 746781320 526974505 826297645 114760898 229489431 913724466 523609459 521043378 24317686 21222826 632149266 906289491 823222056 539509056 360121336 7533523 881968234 534448755 637385823 139271663 243272699 543131024 239060870 159794617 387314216 306572362 850919501 636492452 41560002 318776087 261412146 390812117 569799103 786494189 232554032 735813239 565084765 314588416 112809646 156618215 724617038 324621573 73081178 80833766 877560646 705630976 773061643 5214838 606104945 681798918 473392360 292169704 601702121 487374919 154643505 472890610 137109196 701032593 592628873 432183766 115470416 28056895 168922556 940879532 854338254 803843908 903424023 430118154 112337836 171736879 175678976 436563249 806776661 941894794 279775148 29202814 607242988 483493763 48450943 846230581 79095815 521116474 193739028 850248284 615544430 506273000 54997533 831085432 965984447 359628526 551487940 157032515 765434772 567534798 261131978 784650730 93219241 197514581 289090427 513505776 500651812 625467820 356193555 877464037 169543361 25157737 863171497 163936455 60431388 424864348 369185347 692552086 354287680 323972610 553788654 69633666 587494593 921979338 204824862 29516794 892866340 712777285 382367695 584768418 936928168 721366148 58850321 228512895 852738723 493060144 300928316 989429426 994881331 585798206 636400713 541094159 687631158 37488885 117483559 404225591 92516255 929144176 585184318 107744738 456657729 94759641 424141319 664648996 713039247 266849141 108062783 643166809 186723593 452339521 239598362 508957855 505632918 965307838 699459475 336988650 60418605 502813026 313889201 249482114 397706352 428255276 572781340 780490070 924000094 281823578 651340767 563541472 819793537 862589471 265085419 968410448 851057712 530808578 259079879 655218746 937745268 487537671 854274380 79986616 228595759 365741429 251708851 365068594 822046735 827416145 811995146 518143706 453274417 157630326 959708443 791309879 371147440 953373697 188494497 184814453 565669121 914112884 548304610 495406042 80479891 434144211 377507803 778703922 528216938 52297535 387648956 813593733 126421213 512065435 90231003 518186952 318296445 14952081 114092067 784595332 611869705 983647593 466372874 306748387 479672681 912394973 784061147 616678555 149874562 526941673 585869583 139474162 625662490 538956911 758648220 52820712 275910650 487797031 195496453 784415155 817732784 953652453 351543999 812476288 937417936 442486480 14456741 834919061 460732945 643064545 103028019 299090123 254879460 822083295 956408947 178265920 975865852 715797239 419400443 568829460 964520805 264594184 194392084 236923678 400298582 773838572 278479548 733009828 600868216 448152832 844325598 884367747 613132222 59539202 466615643 812964827 68262036 925397732 393373339 550574335 449664276 287748163 577062163 573861921 823338310 420633924 137901094 936356364 807121325 292895601 319652350 384611185 101029360 330185283 486600626 843706907 399042371 570641080 801831047 118881055 33571577 823537604 282980781 918197566 372538994 508893828 41532359 843994394 962702761 891605383 982953223 756966954 478913411 79547349 29818404 895402997 945280101 906577327 89838757 851722508 757192853 698938060 687474940 141557264 839999518 299410156 818634457 23403557 357442468 541943101 869787030 941324675 806376626 9886206 526529104 344712067 708068333 624350718 456791007 125088156 510462442 487620090 40805661 711934152 460725110 647183160 314836100 350721305 54909210 896074246 106311434 699279154 963266137 924977168 373831047 658697408 201147280 482017466 810757390 683052853 208668387 626053044 318451571 528321825 869796598 706581127 251000676 47867656 22831420 772112918 169472159 703106859 874002709 713616818 746082388 799880805 412612940 272197682 755546643 118568603 928100237 965965270 623567793 816065969 339882285 36392875 342045899 905814088 971673551 561836182 719762220 693868476 239422613 206472365 493841273 444646401 115454510 469542413 716686011 179311206 244832973 153727094 706412675 117843113 12742277 696543076 710753617 103181943 786432268 447212589 991165515 624834019 796214777 478203163 894560220 443983061 451950722 412315407 406308757 198749151 727930910 957327930 823730721 630140846 801877919 901682142 423929859 828858302 263814341 967126861 685863387 878810655 771583920 534370015 792002370 847152662 884647188 300364929 830952008 364202318 437322359 166878838 884851953 310616388 666465549 486593427 750817743 63494796 218487861 2356491 252558637 304417364 834961151 252788948 585522985 935464630 200656659 110213296 23320134 329830558 750530566 199715606 147644944 890672360 19089181 364331702 12003928 779988411 219092411 661175675 363848325 330303618 493007666 680622057 983885872 481969649 292666325 470833240 858728598 20081760 261576736 790331965 497260803 130459160 954043929 906184779 516728967 332276308 176058353 743161732 863630821 547716594 164842141 217005123 672200558 900348571 547770712 842974845 206970355 903664303 617454225 174153443 385790599 323323917 508813307 83996025 168533584 626409447 872138225 603138378 213993947 59219552 670673436 750131039 453775909 927373684 553702345 844235367 526837534 839700684 356192221 48824968 817896666 153268462 85945386 534399982 714170587 120493888 53009344 959498910 702006672 435841631 572465598 407587042 382650972 769019071 895189846 975673339 180734399 399934854 868392732 815311350 736680567 782324618 648633332 949317033 354840195 96990662 861659483 435238284 701546578 925840332 159967018 706415594 707967203 734281849 173186936 74950143 427506974 488271117 542598022 249622781 850704402 824642758 807714228 593071343 693688190 666376653 377423112 317888816 80247347 86848146 28633283 949990980 614804387 803917648 250050627 925910429 209815741 866668977 962505855 301956973 328971093 648883294 85292198 971358474 485795699 169107388 386181765 621598756 910199393 491169028 713287294 309497548 379177490 180528249 989579480 439107892 94580659 499131579 562805963 671875699 357284343 71933152 126205533 292678915 60824485 389495843 443832401 921633734 956368453 454309208 679035149 888412197 76032057 665102013 298619611 392698527 434444779 976682573 94199005 409547771 795801462 334071775 837005070 194979647 214868860 948452446 957479327 943914993 918365997 622878612 846774602 910860140 525387542 590369506 955529278 980969809 772475515 81351018 824768272 788541275 359074545 604394718 309662197 487327988 541350401 20868909 293681714 263746216 457114948 436034045 415517329 275141844 777314391 322562478 893911783 119495716 31553431 54449545 427482571 717285002 855697904 777687813 988863921 503673041 204320414 594059328 603694916 192809585 947431022 478329787 361006037 857768440 144663477 348363114 803716761 408517126 635479634 814407506 360671881 783220803 341733144 114169300 557450748 989972034 410033715 464505372 689071613 902480852 855892492 977106831 759703341 748191063 100855330 626206007 478358930 446929465 458457732 932990519 453492452 182174744 736241567 56346374 882946547 336323371 140543742 403660385 743587538 330306083 398899809 906219141 832797965 864031761 768291609 375249297 829157116 1110370 524112460 3820171 668589393 627966464 417092152 780129374 874487774 856143050 297541246 631643961 237216457 455672961 155341250 995199892 468263117 92958565 937274375 355406594 765743376 425949998 694646787 166371895 449277898 664659359 310893675 57204258 313714609 163590710 722687610 948933803 703863026 302782060 100347275 189704097 680416489 45215609 718301 692563388 98225927 799887089 186346811 235929530 340415682 54930980 259350633 9505250 40892361 795884607 784373038 157724796 954034570 278491597 175184703 407961706 891856948 706576965 766335322 89695001 473815123 598748486 472458584 524637691 296332273 191048891 566402982 984545675 463351134 260574501 958083617 948985186 361405320 562542285 489644706 519632791 373469009 711425081 70593617 18672620 111766156 192167916 969999197 687393801 146874476 911322058 944718257 113894905 733892458 468244207 575802460 183167495 776166397 1857613 605784553 909260117 714932719 409604637 44758909 165479359 876090439 440079371 492286838 632405153 260067322 46132109 582425888 292169365 643384490 715918035 320725867 179333906 254198157 203415578 974999135 217494570 56488068 16123112 190134167 218672027 631027866 116956614 623311282 922308544 523599898 136963908 988787374 849327252 353981203 695775051 911340621 35369152 174554151 972118638 138965677 435927300 534848724 210093738 114091737 918508055 685772049 149789749 37223798 696276716 364657670 337128615 716244152 618665042 853312004 953569673 217300193 745566660 673315963 228593960 814011321 550687815 341195676 26735877 799716713 340829115 445448190 301949684 600049152 709629698 734514960 847554860 948778684 557738515 827954035 423521839 690179748 251092380 938860668 602701584 795073042 595746692 789267425 395347145 515968442 810063855 109852578 687132739 126935175 192304362 245877447 208184882 285146606 188679126 809908692 494086646 400431873 401784353 488178105 864140956 554997860 103777581 767731502 675932147 284440580 436943810 571659281 917237487 913709935 969083927 474581829 726813944 406547576 807250718 725000981 747392730 818863633 675973643 565895614 519437189 927405334 568062165 443593785 657481202 860755785 773888575 49465711 622144056 937586345 385963735 598555721 526063255 311052084 645937713 226263085 563225099 756651460 237093214 138352177 695804896 53589215 695890441 860996474 258126962 264310119 838302027 164774503 418724738 777588356 773778656 869818349 686676204 211010308 93032958 774428097 296394227 840127207 197368084 80451014 122210934 382599090 57934710 354348103 97502010 190432994 291467421 984716059 968704043 167330460 784200594 260069873 81488586 528194484 715597243 48079858 466999519 182728522 964543600 358251031 285236355 979801727 394361644 271601673 952537034 639368200 201690342 930023901 343808986 679492084 770511865 749780871 707508774 949924898 806530346 542816704 197213835 523513941 569612426 525342751 909012169 252604135 835286204 209678890 922527788 58267631 745912258 187314890 156937211 552449516 736418987 788296248 399892860 771762128 665915911 75612522 761812111 459851199 219618806 994541457 57804067 867348004 256487887 215448913 263688605 582488548 631409790 826533200 53806226 32455924 320413307 830755161 647641611 700628850 205059566 33193257 489493877 346193571 667403319 87864109 515178410 369748466 680985295 853271550 211066120 927976960 491150954 408919392 658380175 96603337 103158359 705025562 46866722 783255564 555176948 511730728 460766392 441398873 530063282 171981262 667188349 388398404 919736623 908823244 948863015 301379882 361315894 80670137 564039617 5903455 766338222 33195339 502383378 318950147 390600541 272829011 761607492 621702177 249995382 216037983 121855276 827374992 977465978 55372784 401652651 563033810 727253152 225444898 767558903 672331774 263861140 618178385 272070572 772184989 267741413 82231146 730185797 805752809 264556727 87138674 324385606 531599953 786299599 12321768 925790625 468203665 881643395 69245090 257461038 392285885 34348856 913891337 438615127 448901225 299658528 15077236 115290029 342589300 874621822 506927610 354752145 620885499 929717972 344253729 583690570 391011830 991337008 824821663 453832130 11719775 745926513 775086513 832227000 155202426 55211619 341675674 81439292 820686673 124478471 818360811 951349295 38457570 939383789 805901693 110306722 688762189 798215252 865799571 803215822 790851655 328700110 196519693 335962554 380053115 471144045 17049319