910 950403101 994128205 925568677 972443002 912181814 957160050 253160741 284106611 302429518 657426811 673558321 790877257 509906923 710890336 850381238 958060619 562458935 761411351 239400953 644271189 645139424 905610040 580311061 883165009 452173197 951967683 438567709 789230292 274597488 598223162 305426655 415073199 979588582 999009794 563167918 755191257 849937945 924090130 373751909 499398451 46156227 461979816 28980383 636100156 537992190 908777779 930975716 999595927 850803604 935732944 927842050 998675760 678548089 914414791 453414922 766259872 118486337 210938820 624517465 808804834 752468103 772356063 785847578 832993930 870247181 897109048 247536082 849153410 479247986 852928297 456362426 509246235 205653751 281551165 564063763 697393817 747032695 950462663 963982136 990449426 507927666 624178610 300409016 698617964 980991816 996555188 396909196 411578947 859052464 861845495 786029849 920070761 775246400 981280330 865455208 934694520 82149132 304693045 951862086 977147440 289902251 979393169 358728676 820900305 437739281 491499931 612308706 629423138 860247956 866085218 969238010 972507642 542333654 809625497 619969549 633563396 803542392 963541565 575209565 670096267 771304297 925557057 26027866 857395776 350777466 645480175 676994204 916042009 131771361 490576894 219205973 677795561 204556134 979434193 186963429 840585367 205348129 281197624 980391132 994203606 915608134 917023085 823941239 921495886 509303415 974216696 129629131 667774876 681957384 753896712 258512555 808365093 113933510 668780041 522563402 728018404 382966302 694491379 162584408 568463311 809878220 924526133 649171442 964433037 152859480 524605381 823314384 972295183 494465515 927237808 662514193 887227899 753213052 837135219 322675909 950962994 647462196 750821892 499600318 738254224 403275409 536246216 584154434 859214284 98868505 280210854 286735266 722247222 702449367 918561636 192661868 566938696 564134803 755393374 608711535 833945671 905730099 922624783 614783493 694052494 874794657 976841646 308281065 547271740 800847070 988048339 249042927 254639035 192069753 815624178 687395727 905198381 47029910 623410985 11508334 526190170 366177645 965278693 982846879 987819751 667863009 707775812 202539731 841112238 320579999 646171323 525028007 757527674 474194450 839675628 834627008 866442976 982900860 986069066 409046464 792057126 345966834 937446141 751646633 889753138 215913752 886531746 659777650 679269798 200690256 524339482 333211596 657369660 32017065 802199533 367493330 722154405 659962224 882304470 150999861 307289374 271674511 815385009 191138085 560521827 947571907 990930676 511334006 861194489 15074614 855921416 215126836 600257918 75537257 940765995 740476299 756755007 772345968 815291154 568490563 720517935 215426726 999038736 838894707 934356696 795865219 836727437 485759258 623721634 897886160 981172627 580917520 618242825 508121089 750113436 517573162 571660893 615777577 983324287 110285420 576987941 889830974 988284567 803408712 820027944 284255756 355995259 83542762 262808693 640382846 694789864 531524973 592890745 344719254 495600969 450318641 586596176 434967802 996032104 13082840 553928005 722996020 981904531 606916579 814187067 574157806 962123683 420209384 784262427 338128066 901001859 823536124 899697359 227412796 651623506 854447221 977395730 363484003 858207987 467650147 605597370 604310549 644078228 193585712 325447631 809169035 860202511 395336117 920790217 520078684 594732953 444354164 718771712 426954553 685354708 747901441 971799258 988801217 998352117 726337038 896296032 899416773 993913773 723753937 787811354 232133021 235951945 682546490 907432748 374492136 526532401 998162283 999148665 659257788 888563727 423934946 473965370 500952264 595282533 34990150 318258101 75316223 957849097 843093293 876321237 111731297 832373372 113834902 822466506 941689000 992431594 673078512 788438567 984067320 987729404 229520434 390664431 508429776 596066122 70859521 973780964 368216810 540225411 222103419 555121695 798846089 884836339 539619027 742130234 893812617 894107315 652332983 775429319 278389122 998081951 161383986 589949051 976200478 985815645 23596609 304952555 626177086 825431998 739983314 932884396 666926046 854045987 470117758 727789203 455004886 740231609 537764790 725010733 725077579 910611410 98008927 188692458 877335885 937990927 127851960 208484212 513881337 614776962 751792507 939301016 184570175 738625865 392525655 815925370 773747839 917845192 185472963 250943206 861635787 915671992 966098024 973117038 65345020 464321274 758285509 897059317 221703140 269833291 684853699 865807701 950956503 975158600 148061094 281876177 85105682 121095392 713652104 869761786 433657298 562446454 288418635 727899757 15824754 46720334 135560308 512253620 806095059 854960779 668146262 759531678 573660059 865569410 349811030 880995899 23902397 111789481 685284877 694160193 392744034 955148673 837827098 953846947 67490966 884783829 331679976 418306694 183309750 409754246 580753566 966916068 333025443 341677617 564868473 601945380 177347093 558673010 369725284 684899969 349481842 658708615 903055067 995022857 119852281 523641500 310302627 605305538 712654108 861993316 523037544 553172179 337145201 678839403 378447027 711842034 593434505 959244997 866952044 902409828 851605260 896007003 199036781 736993787 608866122 954331518 69317527 432200829 369719713 926879142 657673653 881740735 393113421 845203433 531596650 754935327 162109162 279000589 107935851 992881972 379598599 597538203 628994924 965741960 706739049 766517697 334078052 848300946 169507105 482150373 806011358 902589836 805468944 965120953 833560425 886216823 663591099 717243491 133778604 796630535 275502299 806263254 148568740 302184352 500029228 951520899 902788410 971411005 634716888 821792875 419497660 477006037 700015321 815464057 477709597 644710787 658893642 883427304 846231723 863368078 99789630 151675840 967472201 986425235 933263126 982053400 402987276 447530153 880843008 993672247 476053010 590113632 551138046 923122549 605307649 840012326 633528279 825431746 669623702 964993364 935403031 973728176 139212407 761465087 412407022 619808290 533789522 900453324 676385540 913139924 730289676 840432867 946126610 963352079 790854362 943036939 918577581 993296678 28471208 490983776 351877418 942501144 661544167 790350686 882316170 986761512 539862060 969403180 122793299 971903607 198771445 288947734 734526340 949378925 956064315 982459481 905771048 936035431 720627759 819141284 540834455 566592154 526855177 904913997 306244997 440250162 621917027 771714034 429788546 760149489 266580413 751687166 25928270 768134975 999220286 999868103 795589575 904715558 66270255 113793159 192931678 947411353 458839484 820372637 354466556 859434348 712794377 827869454 536360942 610876135 61540990 534332000 650985928 701595471 400618731 857095307 784769887 940324995 451179683 597755904 394731948 400428506 124970254 989003824 26523990 555458708 313676518 345399734 377815254 867176444 677051514 697518486 18489637 256643821 650851098 945249110 55232455 529184534 988469434 999089102 784501581 860956638 294702286 549870587 661974674 905190565 131453524 140828772 605437954 953206470 348787393 534718891 271171006 690601084 772068023 872349983 679013330 981417499 52709043 237311549 666053403 947407421 866724329 893984602 227247259 396904261 291008021 833832215 386478818 427135404 894445499 987328745 129776123 631521685 624442521 714224590 241135252 608010822 296774308 888270189 475222664 813862630 452303460 681220992 149445369 169122510 75491448 774874969 551047483 731972776 567266916 623074402 324642716 746187115 757405667 772894962 586135592 962747771 419888989 647430120 222848942 705264514 813694002 997450072 914419915 976708623 914877919 974764792 375074165 756664348 270114154 596054764 777749627 972324619 173000881 455162190 626136389 708732958 897421217 914710318 108260716 771885386 75050900 996968146 272239876 503903443 784840545 827948499 218556289 371472245 798829906 965947117 371374820 386797526 512380145 966383020 929084197 947198238 342493191 392225270 206342876 738324794 653776348 904044198 866200999 930504915 835923112 936963281 253327919 373932119 338888148 971670791 480552749 631489885 445304553 452743932 630126814 756003458 660645421 953983837 964852213 969616156 888314448 986096828 592724373 605807440 658613233 769914597 80046195 671442706 188183554 952556432 836155406 974005480 19231145 737240898 450110662 654278704 866017740 968104295 84985409 359881853 331730999 552463862 314855942 465261701 461975833 940442939 58031693 698751849 660018945 998195750 911031713 982640222 104536677 560175669 633646161 895877651 396972209 655318476 536322635 609695738 212244168 886192601 971686436 978241268 590147442 612536717 123131262 268727812 952308146 975813651 71067857 434783755 256345276 523187378 454484621 536722076 48796401 276797189 24891673 500286407 357235233 975053192 598029610 795750426 535754421 752114678 150496095 278873334 925535953 939152540 981424628 993342078 68324707 111799824 367339286 613578444 525961205 822313344 359571683 791491082 289877244 993761558 205507444 675900955 123576263 684887628 652008889 978278373 224450069 481018790 580422571 668006257 617221858 681062354 253904290 559429571 481234448 905609781 853548219 896250641 813774639 949004604 371589434 689967312 493611256 608835888 594759384 716878023 319291388 762001558 954263661 984038364 759159244 800667111 27335255 463268799 61281517 872811749 398468846 464018455 182611043 206049019 895527085 898427782 644102839 944171144 171764742 297237433 703612926 784018048 730002980 902736760 228414495 497686951 492867099 730810191 407576754 810506245 848245515 970380976 403779389 722486787 631761411 639494649 392880006 797190709 41149595 237141457 479518509 599231644 539090722 927864168 679189145 726472687 712210872 825426163 900469520 921828537 727147469 974472008 669203256 863218642 664517205 716864296 608816166 656591342 607403936 654988759 424940694 611278209 186564808 683091291 474527061 551956446 982798211 982892464 960591636 968734899 467754882 600339570 494036697 539825217 670434190 675855277 778785850 959234041 497959675 802852927 18144871 246477506 177157736 341140152 829919017 938085631 872986347 908556397 375804160 783015872 313135504 871228416 499565892 544705129 14595673 380892522 181906443 678244201 295835084 351512283 907147645 997221331 497013585 729820005 212610748 517789267 161723267 886731292 158518880 995869169 784986871 940467641 821437750 930907728 40768293 568880281 985239921 993617803 745599141 786117713 109976830 171953807 22159851 599863889 864718842 886416717 117817686 299762897 783812799 954633408 961161954 988126740 410772313 511824462 815623335 848670115 169127215 913791177 744695978 769853585 345686468 601780504 427823511 447852786 312960159 870342608 308828197 479692510 630386601 963367486 649891583 852544873 464955459 643583244 286889388 403027076 42864382 789573486 329578175 511607774 556345896 957691437 270778806 527156292 807818893 900463528 408121640 929651579 984080607 994273597 698127603 845331611 545519720 729929737 255692886 425497885 104545526 903770937 819828803 979883717 145828690 538579401 294239011 956484610 390879129 986731064 781582988 833398092 537099496 944205566 481197746 817044638 316003747 741143259 855327536 910528351 940192241 999822602 181946523 880318874 673388765 814623840 959883464 975358854 259627774 792580780 569604787 882485309 113844237 456565733 31723537 258980960 323260949 773933116 345894105 659466591 147571176 281163367 779206078 982764744 576274153 656926881 31238783 269770374 276243446 342602853 430114465 528534856 94228540 533699975 76177931 760366843 664843747 699412855 810756659 916530674 179688908 212709552 560955045 937116063 782245322 871820752 265919433 724964882 693222886 943731301 755521810 782732147 443405355 825127135 693792493 939055683 944170098 983391446 673780835 785775806 364723224 551059969 340508764 853619972 119103418 827475294 405872971 633229981 133810971 272342614 824589931 908119575 341688359 483071362 109875799 891125308 245219258 708652311 13645793 868709959 964317510 993853047 511382811 984340422 567031632 610561572 569404778 725652819 623097784 872258762 480424480 850771794 876331495 955863541 236940221 904821853 586791108 830288674 990445339 999061161 835000548 871320662 788903813 918797033 602951151 884866110 299925646 813904950 973040428 985265178 679817604 783813337 262528603 557247316 637283513 640654566 663891786 976512288 176762899 888533894 835922590 904105872 831641842 993095405 864367822 947893808 578394245 625273974 506601130 620634116 917349487 933399042 421963602 497790612 725751237 889344183 930113475 955543720 978757947 996676040 64683829 171274760 508165257 989947225 338315285 718883004 210008588 393812963 450203288 589608381 58147298 566553329 254048151 916779906 365453465 772697938 857124834 880570427 993685530 994103849 785275746 871171143 829020319 896863331 357304208 533826203 453679568 492754537 228489608 780057237 644737023 749392114 72372372 408317345 351546585 564417564 572136616 757204013 18703305 696620658 357818170 729757558 307328052 703257098 362769621 773782233 837964670 940446166 534390114 613976829 901624888 993016307 329276870 998032298 591099677 665131798 977826752 978429552 990062679 998200692 31949700 174219247 507009723 562627661 150362246 238714516 15074087 364690091 272605282 938815457 768258439 940508393 328108295 622572439 133313881 155087045 278673936 617588353 297196692 654011260 533887443 758220367 367942001 789167658 283132180 537347921 773295745 842072157 706072960 711181819 272639240 349584441 121369079 768125013 684789371 990712147 332466806 588937908 305034145 420462545 958964419 991289314 104271100 862181695 451949591 953120587 683359723 715416142 666381889 918200595 716324777 744246636 939890652 992088144 340446397 828911511 680326747 824178580 666725480 964524722 150732287 840674000 474980994 786631254 412075364 952453433 834192926 922629398 977326771 991303335 823100603 909911196 795467557 912274459 812036504 972440195 123749514 660422748 685852720 835987450 994642586 998815510 247055719 934196621 484570967 742805781 750669557 933155527 183966149 667304703 656240643 782336615 837058766 977152281 524387329 965688407 903825922 923307994 591434415 966165065 114789726 571771558 831885578 962783473 58718018 85252920 762885549 900385678 520705563 868570025 56134678 705924194 140931672 846310769 583011062 839048092 81221995 946829203 658765442 671633963 999561844 999968291 75447209 975183250 76364437 758878513 508672649 768397847 708738614 813299916 414070506 655274818 533140529 805521965 217630877 513130559 907835109 961632983 541752246 662910898 590209961 832899806 709500518 901020943 367324341 951081520 773634858 789384296 92237483 288902758 900850850 982798339 721088199 932601019 918259723 939747058 608258892 918304030 352518813 451533930 316105008 625432506 325679238 749147953 417824238 855995300 492616595 687243178 432223552 981004967 253412528 283023394 837551506 866829129 24815749 318063584 419687233 853258708 382853274 689672854 406698993 423493016 490317082 778065045 955851995 972655725 62007369 671292244 876229554 883987476 837091244 994480152 982297435 985618416 293979557 549073499 434304542 593903523 671545444 849693361 312162805 328713790 472160475 889011434 12098669 21307772 606944840 940635426 426932758 769129219 793215871 956572851 841500187 915563014 940222378 942129223 62282658 565527015 176087239 895691788 155453851 311160708 311122580 601075831 701601138 865738173 255123858 988791699 802454755 808202020 658121117 993041296 410936681 526562157 382446031 898751389 858972671 896230490 471549418 537456052 103190287 769221132 836117606 945734083 438487605 814246073 400322764 933635584 533988034 948714319 25008243 90237547 760449197 908580832 25347348 259376402 447244968 724120384 779630885 952616204 115442785 857081513 444598916 718170994 284137795 369874209 788554693 832939389 707173128 815989277 361681447 739953129 104465170 513734647 940404393 969549376 783631402 816597162 298228444 870825572 530811985 888778903 342415634 624621324 464703579 754664411 643433991 832974130 281973490 850541906 310963747 410537425 114666536 994379834 992060674 992326259 247736576 327814222 118757847 434159214 427910949 833647660 977577774 998695037 972635108 975343448 535354991 548383452 226609542 344223907 448505145 518314144 298380198 862485250 185583700 958911670 374806140 774083251 775928878 874590529 979783395 986896541 444736014 875458542 924581464 966484340 218724353 814465915 280109110 577886521 132566432 173125536 57557404 336611312 649210013 730919462 635681303 910071325 577276622 651165576 514837432 893831058 169335619 730138920 629068633 845601782 817888069 979593512 572805403 636715496 906628473 964406645 177544878 438920232 449967943 902909590 708817376 726491324 298761132 755688975 372275436 503075866 962871008 972700853 92984470 326252142 396621639 439286233 695080902 885225698 757035791 949814900 484241660 913460952 543813921 675113732 25609249 919139135 446200458 913034953 843291123 944042333 323523323 534800895 88870704 309661632 858580893 992422620 138521516 159095071 188412010 448467523 331192764 445157994 413296337 848031723 31344819 718945220 839829541 845195602 256251169 893828607 921589156 945676120 153500307 552930931 996882803 998530310 152025879 467187056 751965282 780907318 865221685 932385491 170821246 281805571 496436625 798951394 929214423 967172139 291909719 620090196 856775658 887188869 208377726 333659945 717186872 764096428 411677189 432084249 52143945 334424550 246298726 741726582 252800548 681351533 559275025 960092311 773331076 948865569 693358699 870228734 60757298 399933347 199146168 931274146 228994095 335913888 671255014 984636682 954301368 966320047 928257202 940950821 23644400 802213565 307399466 361381807 963514017 985506630 267610664 306501468 521952397 687982186 905766236 933953533 902440497 961894004 914596286 931870945 500430178 639968290 520755949 826257751 30325576 50424433 847439211 881499480 550422570 922888583 106927154 416589148 675754834 786018766 792402542 975303848 378868093 391880042 336874996 799601039 978974943 994905234 437315973 825950272 412151049 610055576 472007349 888327648 250488406 499095863 111420502 528629978 874599011 985629111 682119007 998310966 422062892 666433708 427219323 859630719 195958439 560494947 253092053 803446171 516827220 578687080 459252923 745614265 241514596 306210883 597519125 932419509 827254172 944312908 122789899 123338072 98778792 339253970 803257168 870555256 819028577 890953283 533906392 562561395 366110968 461314721 766338323 969422709 375591839 784662334 817828658 930886296 542386242 932962981 10248563 804548747 768920138 949784906 796166148 937766931 878693794 941634398 587008353 962718016 251900826 587712609 571498796 655464224 280356632 578202099 902052048 904550022 903274118 991165611 508879863 856074176 282770265 504172476 902961733 903338999 167041108 505441018 628820115 793612461 958235421 984580408 710801608 785646347 396626579 602579417 622670458 900411625 458030360 561328958 281906404 454495157 455556594 614773423 564045378 718068398 923273515 969323503 395338803 659168929 166358643 931377027 340309733 925950693 778246594 824935931 196324488 260201594 723666830 828240950 264745525 954780465 713176982 745250759 305308754 464322791 18183463 447894557 195829870 295560683 416380949 481312598 179223959 542835724 21253927 288038506 111032276 342677542 934412446 949058488 366612008 636180279 267591807 274867060 974267921 988265445 449079464 895679374 759627742 785369297 390068971 881320011 296084557 890761225 37721228 149371174 443079280 775146752 514909703 795244501 252592322 470045493 460948780 809279326 784882478 970375939 457924991 734038074 605186013 866580016 889371594 983468033 346412001 686551210 695737996 899039000 362378652 680972364 198146455 262187742 457649454 984341979 320629566 606362625 850947135 852808533 439310233 762097833 408463511 435335054 73196726 222772442 250607473 978266956 307827925 844386445 61627615 278840700 318775366 919064519 692981486 995669657 860097597 865336567 174792140 861753600 836658939 987408441 125218255 418665979 402494374 872347443 918479857 975056873 338844454 872473951 206251768 250377386 721212078 931308557 696133192 966376104 884334297 919694574 473025820 685166070 796101435 885319502 271039517 981372410 347635869 522078292 683944454 969535731 561945357 828528879 467084310 966190155 486844646 844190101 729867011 838404698 741308664 984251789 459588418 675034920 915230845 959557448 546389149 805609633 806966606 879676938 459718997 839840861 789257791 983769679 762640412 963482550 269148133 653153584 359207514 699804266 512612570 631511634 453804018 921611748 308829364 310153884 812139209 878433402 316859691 677514322 263067536 460653999 235240049 364386194 733961723 910357614 583421962 843240175 207800296 515850990 135020047 238281763 300065528 774634970 79163212 449603932 593456176 674647820 246584357 520138661 339185359 632761649 890828092 977411062 611168752 979433369 118174814 526117197 929041369 934378055 30592902 397227104 942838913 943757519 717156774 769108371 376752842 628393074 990641425 995878698 329533715 723860204 615714810 775618350 421449610 797465122 235384867 803899775 950531978 995797650 629731623 653292126 826740308 872044179 788815026 922048653 273740120 892411272 239066968 743165276 439628287 454853342 967869638 973736349 786496216 918825683 906156218 961476618 400383095 568942476 24010022 489250579 790910355 977511541 877082388 943397929 562672785 573378953 689767093 754432601 510788959 677204419 769170346 867653521 813101847 938683576 823879666 865920339 964563076 968439855 220204422 893751480 28550244 478845002 614850908 656082626 804459843 848295964 857652888 902905711 326468010 574799867 730088968 731050253 617462492 940620018 569453182 962601167 608555550 689914568 170006836 881225599 404477845 786867147 142182833 690361611 277843371 796471830 517599521 932184658 926767264 941499639 283880630 395132156 352605542 985977878 476279014 970528462 915861444 990513901 279491256 526668236 234517538 519185022 77346359 858396185 272762581 349417108 244361291 378263674 821729429 913872934 128498785 688798104 560235702 991772163 24867165 904064808 616362239 622687464 555922047 991653395 155500480 166754249 638017517 927622827 108085825 153578156 659510867 892472482 307141179 743406321 786017729 931613454 546103972 579616824 367140016 851337173 532185513 771071965 357842225 894508451 744479942 849753091 920623009 975372903 185047107 743740485 851929252 977614455 794881354 919021520 628778668 694108694 18786677 823719595 47480469 755891992 238057905 378423936 446876843 601416108 936078576 947856693 54450158 766086648 580329789 669855366 136267506 586354203 636518471 647214032 890044186 918048147 979324249 999531209 528556322 811703906 626826955 908218111 701820340 789077598 121933737 495572777 327750177 451140999 921983739 931960558 378261474 850694818 45233516 648391146 86435027 407756532 95260049 175374510 477951167 934546108 252197840 945706118 419588993 926185239 969130812 985429879 640145012 917039441 659786268 981892005 886105592 976757618 141353339 339023203 982854449 983209511 143669686 881983410 891670663 959355854 670882047 871835751 160167711 558801919 617165792 950679754 972537067 985799476 300420499 370471125 657062235 913103694 772526780 876907180 352800036 932660954 868169600 928469597 283521403 785690349 625168252 789009356 789320117 885769013 384799520 627101822 958138567 965692634 334657257 355319975 284657932 479341938 751205390 987122929 493128036 934410476 25788524 865561325 385462312 934540346 14526284 36594861 580760522 840432124 528536488 681015752 569272700 948980412 314429390 950409442 999065716 999881870 343168242 631914841 325547127 650971050 651782494 656755206 862618695 942435540 849162443 923532145 47319315 353954917 445644609 991531659 207085702 946218400 258488986 691813308 855858391 942931636 329487529 355224227 304112938 395351840 24878986 482205584 307902162 809237751 272086705 543390975 326996754 808035579 81560053 784155762 895093120 958716266 581924725 707572726 18269176 168169904 388408321 545717604 79094607 637949520 242929385 752189200 904958815 955402276 798921121 855081010 702960265 900482329 242393962 599862123 377810317 686273116 368706476 962043368 480833595 626965633 213884391 487428639 416977879 623365682 402671732 404794890 95415082 180277270 780457557 971472262 978493019 979888094 856040403 967109817 367486968 606513278 753887117 934296211 784927004 904137943 658181188 681289223 41624840 943777813 650214416 722741044 690754702 846668654 26763063 69553199 460086759 908025165 816362340 977746226 919887757 987633734 865088825 923350042 247417471 264225341 995800675 996295210 140701602 186211844 968643065 972823524 167357744 382552967 873275647 985164844 103844886 214318524 452354828 982760898 663801755 681986399 957237771 977021894 723761913 736868338 646823643 747735082 942275541 944320253 23364286 222710800 654233748 818780578 141213840 708624505 287318041 503222508 819314828 889850308 633515487 944127764 799932015 984302803 590539797 654898778 340824787 564835728 257994794 452031267 588160089 766450769 211893318 419991435 810712593 843476893 891475564 970773403 846011562 916926842 268287484 875464762 811570523 879412910 426806589 438024336 833526551 917060241 993619101 997804877 235142551 683699498 510648809 669522578 454012711 575031045 761412761 969705839 748389853 810435059 877914176 952333199 531393999 736109222 497468720 826717247 313590270 949652407 115240509 950143734 656243971 677135820 938511393 959777261 424919744 869084589 273928703 541159653 557321402 722265398 577755796 853450107 763985562 768417609 612134868 980666512 779155332 990246722 555106102 691843283 906449537 988708837 235393124 367391660 19344984 534806782 346877661 778880545 546673479 997799796 679837097 923717552 448835091 484406802 393017417 553001630 628646683 903025610 146905672 888109402 279681003 952538445 696077840 832229982 784067417 907603419 783122459 796582995 815530053 854955044 795864102 844264241 538488714 573634111 857173046 936583325 710494941 939446763 837966083 998387785 671206608 793059344 871706702 911261121 826156131 855474792 11684583 737740595 552184961 746578359 324982445 836519803 32460038 714770358 269797951 779832897 682222717 696839441 547368941 892490583 677014490 773729309 408808545 995500968 171889866 671933382 634502197 858661259 419045761 486707879 210467217 855728045 88664692 378179933 557789306 825717026 846644556 911541121 613240949 845399177 890842243 916875408 659595324 789794263 330838479 637634576 50928786 262740131 48997796 478834543 403198707 882695846 162471413 341329398 347383996 492606725 886623504 924102964 333974310 894270338 730414698 764678337 507727440 871711908 609059639 877085345 96310971 488873093 271554894 335034928 939713547 990379685 723801325 955214388 959308210 998635076 86302995 673834147 186855887 657137562 933240370 993664202 567534712 760793600 553186885 721101978 696217402 818799368 66488795 222364128 382273899 501724033 782437017 796698583 17241288 606610970 619961531 643251889 242174815 722106596 908315030 972460377 369548306 400355496 794437956 862952158 809517072 924435845 824977913 960953275 221330639 577401469 764748872 973876019 972713746 999150021 984428260 989417974 147102630 482628835 174666866 454441462 525655524 643599000 688891950 847535149 707952114 989468671 946866191 962308682 258764462 872236402 604626639 835624993 564538144 850354926 746879244 910849117 500414470 706134038 369939451 803112799 48384490 873595093 444637929 632872205 897627312 915312569 820257477 902666265 554312778 956103054 976302252 996997529 262120657 281438304 363977883 443874327 142931197 948838006 799459317 897825600 441186415 733156371 680343571 916242318 168501591 776811991 438230063 600760918 212345943 355351998 724287883 855799410 818816276 927222895 557983835 843301872 430177133 764072615 487712234 828871426 313380345 889408314 802527927 905607884 945802791 992891485 413262115 681287394 781329397 870604131 736386663 843698738 248324508 682385559 12729319 218614888 723555480 829249228 791790140 938552507 95634730 759405202 557948114 666376011 523168160 525248742 467337060 676736483 567381174 742120847 798592519 935591010 870423837 882375961 681749307 760386399 995259541 997574873 175970411 295757745 770345817 961468873 976964703 983600229 40149756 306508541 351380415 884423406 94384834 959968459 273521052 565185468 842093654 965662024 246287189 884911627 539666909 813543485 141005754 832205217 64177799 797591600 992252687 993645596 510556353 528153317 413929867 494793337 759290740 820397746 159378101 794095682 254960456 720279905 562981634 937588382 645350961 942892185 709410272 903963917 541165600 809350842 61325462 497153019 241840693 989200333 812949881 839386814 51959016 953085637 805871384 902641223 392304753 992691418 537349812 790461108 324361034 781182730 743255015 928965762 534192345 688968667 767272039 854206757 636596883 989891867 689679522 867156906 567122504 588368576 249264090 546700058 476188684 537664498 165298952 941696888 268846143 356413040 626468879 866177931 473567717 988759305 182313101 914499260 881620973 989733633 469929452 970267451 128494414 978230452 188806601 354833381 531906771 897143668 958568275 963445495 470730717 481146230 545182273 797794506 700925716 897282501 251897529 682991891 556872874 984333066 73513797 539806356 832249719 899920973 712744413 896019249 585110733 641490192 963772644 981362427 800853756 867072838 422736886 603585608 143896704 804051574 220167321 604345320 773836459 926355269 45980264 430855358 474405333 840306440 725298449 911127796 267734799 891711455 900160147 926540970 792884731 876857667 800982060 938654564 626488764 799336875 82696067 246906234 583046751 960641428 319077497 770371613 170959187 877042539 533245125 699663199 907549241 997621196 800303485 888956155 257239419 307950480 888085284 982623267 499308050 836362471 280291923 868746313 276107763 293913379 836798031 984834030 567163259 760589837 481204121 618088510 367686168 767695833 584736011 978907513 242537283 736278722 199741284 316348778 370523434 690113481 689031085 975028921 453488777 652748981 123864823 481345708 889961396 915425850 143069788 686758085 96473187 441631664 562829964 996955483 465371525 878224136 629420529 883991293 384896723 583606900 382629784 410799922 588745279 827113714 66594652 849264601 938658464 988951305 293864452 566956767 76470578 789413284 650434658 758324954 799220339 890494301 431402283 931215071 133507773 229803059 869874803 936835106 824628018 990349634 704755253 964347984 287984034 478272779 792986213 912943800 530144422 652943787 222072909 869582513 486302627 992320207 87151339 815653424 11462414 720453425 632279138 656795406 659912080 736157657 927798853 997960982 830845081 855235573 451414705 553243016 377181620 925882883 780935102 844324921 992450505 998261947 208659981 858301511 425949243 619393123 218728810 704501543 699036401 713821635 371465509 717302135 296286134 787062605 714847541 926654018 772200942 961260535 459972413 575369574 991958562 994151192 10110633 746491831 846014583 961106488 365134374 413540669 249899461 452574210 108364056 211453975 570326134 640241284 662059013 740348581 492465784 805415556 559201083 976128996 745207333 919992644 733593326 965011044 842387543 877502176 866878167 880512530 645098573 939630071 983789390 987138273 479497942 559941161 984440096 994101249 476302534 912594511 449536091 793497227 988286422 993383300 585902462 915433083 399021348 537161611 818436115 874081569 98601495 240894618 787780098 878021077 420463707 975457675 815670563 949099213 595937445 801694089 605276725 833506266 788003025 836807338 156440948 862019773 68330186 330709813 265747262 513269868 66145512 822303165 232486226 866045877 523879814 587554206 208683169 468144704 455987574 619878125 470277655 700294960 832157133 914145399 363191330 772282743 578392511 829069334 84680966 186284863 536728320 716444642 346664904 966983273 739233427 813119438 121753575 431299028 668034682 695125146 612416760 716075986 133469229 566030140 495386881 900632356 614315246 636792534 389211013 682338728 793025271 984332830 649278328 811521833 717626925 805917289 915043527 971240715 767198172 869148956 184088472 756571464 151225157 593561775 251242018 801190259 533498804 734734139 476083830 533539617 351656180 739023876 865996773 909252472 239162770 419382587 986808424 992354487 942148319 991401282 586154661 816724021 564589349 600775367 194661102 999602185 776516991 954828540 805437814 904529371 478893065 890800139 275171734 630037489 541970157 935062568 872284271 956220993 430200615 475969956 38456756 524456538 875287573 958659721 539852055 840976636 817276166 958057493 423202047 477740614 436952956 631178015 820898533 983615644 470312318 601658952 548710480 728352474 867358194 932077704 184907956 586580738 590010741 971938600 23389407 280168653 412240434 559260261 882264273 984511660 843506194 943532128 823470453 887043198 702131045 965081199 534516649 752681407 677804729 978700271 754214950 765531372 43934269 821256530 227691933 626406162 311716244 972368605 894464657 960520365 687470017 899211297 498336880 904820615 669572060 784107549 803876622 971353479 803626100 992173784 933201074 949145413 417005078 956106946 402755462 584079908 33906338 846980731 362391712 706998043 788704094 989870504 725762868 757674731 890535325 937789353 808464381 839836841 968701653 981639862 980324378 999560988 79119929 395410817 663386438 793399560 17579557 772191341 627453965 978091882 865633441 956380291 495834637 659558584 924637572 971822784 433317391 529676089 509027524 555774778 987717577 990400564 732980720 842078125 901851725 968991609 239444276 746163548 123734578 735975858 39033283 311006503 811609001 947279060 312354139 909674284 492571270 919392361 858247104 978620669 510022845 968036772 243504706 796124739 797697191 910934369 433735937 958088689 871021822 882661461 64623910 411045562 422853173 692896524 423159038 646386749 352438990 414206885 114128885 216091066 914698384 982075314 693174171 779198268 743052243 799759773 223486345 599901725 576960690 689341507 736532813 845637639 814185222 937683854 288876572 462664701 928997872 954721182 643759694 842423974 564848020 864767454 338112698 408995000 145014002 401962352 664260706 824730207 600489705 634010980 351973203 820872605 68902915 182354147 626934063 903932299 982843228 989434781 932002091 960745543 386323238 772531433 79338565 670308140 517976122 635395869 314571966 419792404 979233844 988941854 12209417 348186879 745306386 751429322 666196238 947506479 412941388 758218621 395543881 780096924 415770536 564928136 333381422 702982414 259266823 521419379 216639447 337276179 597386914 628348389 960826981 987037673 172945856 319295359 626021543 979484972 104581093 788821519 695305397 936977163 418850279 833934978 638235604 688718435 332145257 473712454 541648136 697779592 38292495 851989000 287123321 304620257 839017478 879048493 892814642 914019734 841681491 958584049 297912638 635421017 175123189 204958767 770288807 827739340 652648528 672938200 30697812 637558454 556971916 742534716 486696110 802730205 495188604 904312291 372690232 717747975 746685566 818249782 860067009 885570632 147490336 657332610 93396059 424505828 372658796 437086154 495567738 540991622 149524079 281279449 934339213 994720930 950654975 989049132 164110292 820266340 429298078 503777012 820403836 855007210 941106238 956591094 96381282 597614350 897297887 993213985 636383943 926441732 383317310 993754091 518398021 522552966 85192146 413972600 23983154 783213993 11564520 85847440 449916266 631690256 279935292 291287996 316183949 756148378 635631613 962246277 707052551 826302729 796500499 800502294 274812104 658860850 841994352 876645921 838330064 948103103 248501719 421354747 109769623 297241385 220945104 927133197 706275527 940510324 51071616 932358972 977798281 993452981 31097131 389122055 497297340 949697071 47444374 507752134 671350957 940171303 839571109 999210032 969245860 988685178 331991322 598003490 620468298 652687924 151961423 279623360 304042757 536273696 713060325 812199954