1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 384714192 497698617 10588505 275913060 450478 127084677 984457239 854375050 519707425 639610513 86612507 942564467 103946127 285248271 613467451 449051059 6672062 179091589 908659870 451578155 615208721 186894040 280187941 160907815 695050856 437264171 444021065 594664297 515601208 728029108 596310577 704771482 29948842 860872600 236506541 932197508 806732577 586991015 743860570 726848402 24207554 221949280 341928143 179562116 644748986 324439767 165247662 987645977 294175174 810322012 837952687 721917010 560043969 636442705 608322274 608276805 911100164 905229788 736235580 838249720 71735513 343468809 895720851 566000556 937590272 782776957 396492695 110971399 37809459 254360691 397921413 302073802 980402914 523703560 823786376 522464103 550977171 489252962 343485265 697357129 587501993 536133490 835336859 3547284 702177912 142398910 684092245 437114930 818434219 887413157 512329213 911710602 931434683 576543298 885578142 606408183 137979602 579718491 613943783 409166945 467521390 50445227 635016469 816924881 995800449 10134420 636077831 938512950 945232303 160972305 899333818 532809980 606226688 240523818 653732337 884623602 232538628 342500923 60036299 854086405 342957177 851819393 408204108 327008665 678349560 221526455 410952250 463908393 475142454 78620541 241144667 501919816 984078660 724282257 234521346 355599542 802753255 416009188 910740695 812348681 439632486 960534033 883093895 542745842 819514012 556129174 371994740 856965898 35629134 612646687 147740556 342730809 514973217 341385030 292528541 391578172 125002522 832968806 118487703 732633064 350925031 912430109 221297627 564219174 557259497 224790865 586361476 333951081 380727539 39154864 341736125 392653826 619859182 76041691 209819013 117851151 76977976 827685146 877477413 396017708 695883383 344217939 277155545 805429566 571038090 325069421 631689922 416921995 70458009 889039555 568711491 896230173 490857300 955876686 145944146 834297775 273020847 80209177 398628740 780333415 147097907 41311133 997736596 646959343 308542794 414083122 942429297 424539141 203406767 285542488 359101437 604295229 132480669 48756667 142160570 983099692 833902450 620876295 53753544 410913453 103849538 388058846 567951645 139236159 591206237 906689138 276860793 937741080 177773587 238765082 862720262 310077345 626959905 497495597 128326954 640533843 462027577 639527569 788076193 493544265 236922919 73384823 385078326 357534383 915504940 707968902 272200312 90854776 7025502 932439978 734872389 321307399 433697579 100665385 190701643 847661185 458100949 119538118 125807549 877146632 640221767 921602340 651511583 89285235 360686222 378965818 364806910 347481326 680369938 787350963 153262748 711973181 769601410 353812330 409028253 53010229 792282318 496933829 341829217 261525055 906850318 821126164 494312712 923915019 78085895 389702057 712436612 868315805 82332639 148846176 521381076 407953150 798814828 206159887 291956472 296793567 761138641 210027623 264173101 588433125 665810375 42544429 828396306 222951889 457992316 416484712 333763142 902488285 219941717 416489097 480835040 46896468 821109075 544459264 76050899 594713612 843245207 817026703 451688204 656679946 231633864 523598598 750045721 314181434 983420086 418788357 187438308 460293279 487435218 568592176 213026562 385065555 649757722 727113572 918416270 292786337 252966786 705193802 97586948 993656683 791166787 244382786 63831671 155262437 945695213 958719070 494876229 704402492 442256775 177132996 5028928 174505721 618044900 335615909 845136607 338843438 813574486 177941912 356346843 577023423 965868846 788133907 703646596 541964579 152464566 358358937 667079587 263659840 11177981 123234209 580930828 293882632 990979008 109380365 697305574 411012149 989626063 676671901 35682333 583188892 727325585 529357422 60869879 760472929 415041815 131163527 551307632 210185487 884094571 916171079 897879286 235839345 38743592 117668152 555098666 725224180 778099513 701527660 56830821 542548374 295829263 387364232 101168843 378567578 924125170 815895363 899042775 44811471 499455161 21360161 296532574 185592940 936365431 721438776 552733069 353748835 226240543 537876975 410540640 128255023 551842737 639317741 850650087 62402838 799383131 655659388 836796893 664048644 994889061 513224082 242976878 748199884 976936520 89388934 249568881 208842732 197904214 669723911 699379617 326052989 600899616 371565926 258801951 339118825 849158525 857512166 299225929 188098162 763276024 294699202 490078680 307801594 434497213 909053563 779913966 889858800 526666901 213292100 36501756 295745364 437574091 670122584 14506183 251825106 706081256 147215650 256642415 36902208 178831347 758011529 218530074 187225940 226744575 560980742 614935108 833838105 300321877 405637079 780696850 160757663 952574076 755392821 710448776 718215507 896609266 197457394 568143692 304566015 979920848 908458640 135876270 153633593 241222375 119179285 959646090 805729086 693923873 136804365 189740329 127417687 446419941 953520406 184349996 35929364 500173316 20088000 941867111 294877321 249829657 7545657 66943270 858934367 585099792 316501910 284169716 522490279 828706205 629165683 315439344 930764246 89248742 566861757 231386232 31434225 21642626 809380208 553611686 305007859 276077199 751745811 596952122 779326285 520404364 732215820 22258578 40871914 561953368 97057141 368413927 991607397 442502276 495714272 854486787 667190051 100085077 480883837 471358723 544857858 443109595 480387466 83330835 226547687 227554074 977747985 634553979 349852853 565508167 54103427 461529727 3213899 413299423 181627455 391795356 489684788 314235717 291977671 854218834 711097927 901145143 540902920 720787792 859056298 731548699 230833134 81881937 36431064 836925824 633196612 201044879 73874685 940762749 803377799 865139505 403096395 501094247 661003414 408177963 639776700 781521736 137079981 964697037 843117045 555488055 47186058 667767540 31289041 380404564 419964371 349795409 772529099 318813210 778604952 336673382 258569536 673120294 598435328 760512342 818767443 856129288 181551778 827333521 526510235 555293443 297751011 639841233 795861134 213586623 294589250 975271174 310010175 751147927 262705314 852020960 530103046 888705848 48264594 793912134 970388152 624052472 458173102 810326967 187290110 557893604 282000345 375749715 630578319 230398698 60223281 619466284 860250531 480213524 90924150 251022609 707369645 952814728 672206970 48384797 921997003 254553091 38632622 250953518 755955546 535712914 491230054 904926662 904634838 416382313 222282444 845290378 288225687 751797956 943019707 450528920 727962009 351201822 752085938 163863249 23144876 439009054 364330316 949996968 327616460 690369812 366145179 447966736 956854337 299796915 335223004 973627518 927307267 382964170 463793667 583229236 140011941 641897831 941797796 405511746 653490918 635144993 963706688 333763117 39788311 468232494 315314476 191466703 9689841 871608805 143459259 345934187 244406324 687646351 521236456 574146713 622877046 564015872 90053702 430855148 816848494 381762102 65644838 205531593 899974723 452005249 98147893 920581392 914728821 127507984 927622722 269002486 219377364 436750894 862772027 991409559 838701346 945804688 545078480 384917336 79844575 189378565 726920508 136190828 437984520 367335218 783441840 17472051 350434508 699723673 918822758 739475471 71976917 413275040 853168178 773678824 313702527 868219432 105069194 924263570 28499105 17274264 520610035 270688488 823887037 765219935 749101200 956913797 455932645 900794761 299286541 112031968 823062574 315313607 643559693 114295103 367610507 719033240 13498767 476343937 555234505 372261489 72621088 121422192 885046487 135447002 654876088 806575321 96301701 704738208 537871746 564198602 67205848 912165872 557992400 328116713 98765167 606874347 762408863 399070335 473530328 419156918 375922379 35976672 509489508 297197097 925436859 408702529 704886879 952952435 890222564 923748748 860472938 821742958 673748401 792353791 718280139 530630442 377491961 86864732 575891546 101807389 870513123 253077650 860015205 712616102 456138475 684638904 340716163 828208571 523905293 419247508 397586367 864733727 765379872 49696125 129476164 249091288 26054018 486000062 194771908 603242217 863018213 912093575 703562811 92930226 324073460 390870282 482216309 358559391 634670097 950050829 566453828 216779276 390301511 589983674 413677358 236146910 784425924 240111847 63159879 972185995 332913593 26876123 244161387 689979631 900372333 166445063 173907693 754000718 924118702 353003358 672932807 467139683 663767680 584624194 863457476 275910093 857907252 394803670 369363659 234309161 356072325 715706150 313990528 745145679 732832892 685943199 339658480 375943149 680249655 474188346 452975117 289119528 979370553 683279766 339160470 373324753 337449891 399217640 70107896 643649521 892485943 960307597 44560026 754947586 129207397 16980704 510359904 56906410 311967726 325608266 419759271 65218595 734317114 290342578 481571753 773265776 469188435 65873942 94680095 321337642 424843462 371129706 329692238 966353344 864748590 535143679 774024708 650834828 14536508 477455288 439395624 829925486 525311591 398854151 73370206 558848860 693612105 623025776 707441748 767568362 927400901 627510444 424232771 508359801 318598238 608297671 583639769 463066808 746802241 773433245 364468440 882989995 334113505 321079656 585616029 673580338 128417738 286779932 621507590 818938958 89727625 354656166 833340823 513970029 220603155 716316969 936145508 980429425 599133209 821428383 746097393 263779725 532983483 767125301 928310064 163490562 494156142 680460743 721647314 698154360 720592542 505982305 533204734 503420343 253031856 389371958 963622894 821476340 45564744 756582217 487016374 807626666 78387283 995971298 114230341 392246947 574216159 638193655 850835243 973622261 423981432 674936666 712877307 641407882 539211203 113951033 700021620 472016484 348834691 232020367 468909560 29650371 598917718 690006798 572916223 526228116 905908246 761989685 533207295 43644623 865023965 880477994 161065481 784504906 621957119 966006985 823864161 829397890 966231770 236978248 851970439 949534808 743592753 492597060 394652561 441756846 568471111 102843141 666420264 228211509 398319895 142686964 704408260 597532141 301774426 868801711 529135581 382591566 369012481 133346280 913595532 540950103 396487683 385264918 604987559 693648144 826136644 375801442 977431617 684086952 289180051 3578870 822327296 257028185 226496008 744688826 666708243 896540054 996581790 119625183 380409914 255781678 368467989 599478049 476736444 431976011 893133919 320081430 227543483 169976081 428784069 282400392 658440276 49749597 786912267 929830768 139470779 129948269 357669834 502371152 754328319 303723355 88674315 770231115 534823869 753918119 223611825 755965011 221931991 392713308 343975298 70115584 882772247 987551025 928745467 210234345 550840078 949556506 840357836 287057926 237521829 116216556 522518075 227789974 291259418 807146129 144628422 603038038 514049740 360153664 272930569 921061204 378230031 959471107 211527298 274616548 59242405 313287639 981637785 167003076 34517646 763261531 875948971 4600540 921193405 95346042 576993421 974735963 11959318 948042754 284382770 134478355 959316028 465518335 378443460 458723770 142450500 66788479 596807631 807196063 477083512 206440478 895106234 406378714 798902496 881653073 478310973 880051440 860525727 129530070 879047051 416640799 184539195 828164980 278822484 832702260 480248382 302668111 761260232 757821511 434239556 945981420 991427833 3870129 636919154 680694922 403771322 487578756 637201445 462087489 201156317 869382157 415363702 966954175 771813063 459714694 650749891 542733382 468508499 743542871 977490640 726949841 21061258 52092907 791047263 279794154 741997692 273178656 625599058 523133754 113239525 249163371 667113460 59805151 330009898 669115724 667587683 314676822 113835070 760494741 756928499 255605242 447780698 947282261 795385134 53455372 319891579 224242795 658921744 819998835 60062587 70281341 409578996 223089902 345865975 420166762 792458928 400688973 501282098 184090969 112528017 4946672 636957587 942408452 692331655 598421484 14500289 117629257 127001560 443455919 323033202 199213548 747489054 900502226 745223546 32045718 536537686 593300152 178915920 811777029 65636136 544153539 420910797 537453439 447076046 200792755 698793851 951762794 76318111 384297756 867195125 281399131 378939693 377134363 794198287 205511428 847170118 445886878 407766509 303751342 439079545 68901647 775428113 760912939 767587268 141598985 935110180 927690516 505197232 721414859 264479410 468533350 169981968 705557456 601801194 340406094 782322193 485458123 38938247 629499286 652472850 570825321 310964436 863685603 66310317 327319060 866091388 335202633 758342909 747784880 314560582 276820841 820599872 138516690 293777447 308505939 436517872 130870860 712194649 954126444 837626455 107922787 346857194 715614163 195208964 878046112 389565938 671063118 641386361 118470759 293291482 268413674 486640885 497659570 726601066 170720720 444532206 131076841 64420641 370265966 19045406 959114665 382126045 612736644 453716244 931292186 991611148 319635313 435187313 254829664 111704603 326870959 684116841 955161899 24989161 294098162 228939261 474134648 447710327 855099896 583188823 819442133 152283108 817537136 690494686 435025509 346510656 884554003 766163797 570263744 292629516 23384019 997118123 349841566 219002884 621458368 371372475 774532715 792647779 74521989 956444970 321227186 91717499 457336929 975015904 693865775 420256384 88494060 863671826 911420401 79484777 604634886 490595235 824361379 217917731 944855648 561945950 788657008 222974164 897822557 821882416 82337095 166732164 1456046 372391863 753069462 335965823 276533125 369686715 328883484 4872605 500976946 714964471 509337176 446419443 238375774 251011399 464603095 437383421 480635290 878244938 13938212 844139108 301086814 944475483 648486777 883836496 809181744 588419088 817218746 50000181 628126512 898095872 998234009 916494140 630628129 120776865 634937534 494932626 178075806 853122868 139699225 90408198 421800254 952563120 331262649 429130533 89157889 849233514 131402351 512900862 725680003 993184775 15608206 183312112 904837313 977598083 23058904 250792606 790548687 947410756 402321608 379731571 384271348 630913905 232395825 947839368 672512376 449585449 163578059 683382299 175713797 577319589 772155352 711852316 848259771 534587018 356272141 969901129 763123738 920798390 126321829 364433405 550757043 745836305 432616555 472071447 703233182 781250189 172846641 891377213 714240273 354044223 484691910 896537556 258982231 178185420 889254611 158823790 531499897 573199167 80210029 345551898 803754256 784165004 783943785 943236173 444828695 716949260 835794619 187969907 315093692 219464908 982078280 213511175 380343660 14355975 827080784 351657743 25287841 627277499 234764863 414420271 973637160 13633749 700606412 567002632 741562697 47089341 792089536 567466307 52872831 125997648 72582442 923477334 322594337 810484640 139449696 549827542 339038889 931448742 381003550 687892695 715563413 494771141 369155815 637107456 713198088 275836960 834095184 157255769 968487624 585537383 621167405 213196265 739131941 137940701 829360635 948237236 61240684 722217861 677128378 129443154 650331430 176259724 547404795 566173780 100018066 358664177 241748465 375957210 538673065 430983910 298655869 21965145 192104357 532855743 910753383 925624186 12234902 866238016 813973771 800629748 220129450 93026910 764690667 860431325 138265669 476306348 128859210 560428516 177351195 233715440 852131665 529265709 523368776 230842867 244325081 949780147 290949363 54407406 789228579 835185211 838137465 764560455 793817290 709932462 431339379 340126857 515850883 951299725 511470773 434426039 129093998 886286430 287236996 950533204 779280576 370588418 298717024 209791961 912912502 178028084 548791846 962750113 376457744 534758299 144054246 130645491 775322868 952366294 759397349 649314297 138767626 140288704 303282242 331185236 546679146 723030641 725049853 431038713 276173723 913494897 857182920 787976977 350441178 284921105 943101636 223586920 918900724 107122406 105849519 649199687 949921130 356768222 774936241 14847224 866381029 704354065 660538345 621305671 303581448 819129722 717340735 861035106 281113274 272264413 533197371 205911337 818328133 512739949 75225538 828218054 339796628 228275978 130930517 913354685 650433379 679844297 901566396 494505171 922459065 808075985 804198787 566322583 918765847 3418912 633125959 697278537 804780377 451872582 336571355 691172105 492645137 311857816 242910718 248991519 499946390 43528307 922681692 813665748 611947347 623095126 158564958 554176075 757892993 326671032 757214602 976658389 19892115 398872752 195819070 798358392 599584555 592456647 471046446 261424561 145120670 342701404 74997658 499095050 325968235 586235921 832861253 426332956 259980346 279597734 243642259 75362806 76282336 615893180 948233185 520974346 569583517 58266854 638834258 158157586 309687825 330804827 612617640 236327480 700927711 357276191 304906868 587093404 562508789 537840789 227047831 694464862 840538179 394491103 83211054 370358641 776405684 898844389 978135566 377617647 61266125 708997551 954590814 410350000 483604314 918938890 582873229 35255523 51277491 856569585 355016514 245087619 712315589 869203002 168686734 333915559 908165484 666670311 261690531 68619411 950242708 561718115 329548494 236010667 437630811 85440206 333190040 677409662 979420862 543642254 492803088 523907048 945725024 645065701 78724193 212893140 122336612 15520149 486298303 977290052 16896757 33521604 597978693 277604131 572053516 874688037 720545254 428553727 595748404 397855991 574029741 490867959 347187478 860930720 632402129 479556255 576855881 936351251 120989745 502947074 462464898 229793216 93515725 279285206 67366560 877412926 935496542 485705670 84916828 593861714 716917043 520808888 231206536 83529107 97470568 480087555 664764381 542497150 178838075 270078629 368625987 841631885 335085308 842122865 898834962 454770378 213578149 432176323 244400380 972182168 285766082 802616543 860602522 235206987 16993484 516342564 743855120 650192354 256674646 63527914 932293354 805310993 345535042 896382934 801106060 485884270 638414252 744347438 657573197 569016141 439113063 222820595 512888554 164433946 238630254 135854384 708133996 564621486 110918961 519719044 17151360 719899111 954565144 488204731 744845836 340893266 196477365 967917807 826955167 821887148 954975091 111981127 630224578 190675994 941340192 390702704 386875160 467886598 177259732 175189762 250064781 57322554 33864154 361339805 303393595 12787548 743403917 746043260 314467276 721041881 292926577 664204629 281063132 810993251 983144959 655015211 26838866 479870569 250738782 398239151 543937908 606018515 826400117 187217385 812405239 609151474 762377713 325022527 655506248 37144645 739321354 251946818 469069376 407819662 992589234 617250523 109371132 504716661 275936444 474148902 317026316 157892987 637175751 264988424 139837277 304094682 720424927 691520653 261434227 800663192 308337753 338161206 105494951 628418939 86965717 463228775 363692089 249032453 957168762 443228764 480219596 155451264 33600302 779257695 579886000 316961134 765587875 540042929 404282802 337906144 599438212 88512255 26202073 347526329 735281032 568790304 61227635 465241908 403414324 591523929 532922023 606941690 431734384 821103916 380408983 635509335 163193406 520667971 848936709 792636165 124174214 752297731 819540006 179403125 371123090 708118926 149990096 691972181 582820508 54946217 815432518 925537600 852029585 704771442 940898332 338455353 407926393 714105704 456715044 750925682 309665909 337932755 937761365 277711971 887597337 971875966 704559230 341676464 363282591 260737889 707779279 164951517 414488814 439064636 507998684 459985201 776989891 882545304 82936186 843361484 649296403 759536676 781978152 107853821 41066554 794049725 295937423 175796649 122154884 595091572 877833556 16634301 606251117 662094406 681372481 353123419 710590235 373292072 66410571 558092352 918285271 538711052 182831157 336807389 749117987 968686972 766569367 471746351 662055085 396001297 209958490 337658885 993159314 237485078 64362079 813911828 150751302 944250011 472904558 104675773 580110354 182690155 893503183 670111843 313772821 834478786 743672207 28972489 853048226 199075696 711927750 198036634 490528001 448399942 712041811 201923682 672440923 977481482 935277846 861700561 912508153 539836094 96400914 492578419 458237425 896286329 122409760 517998785 892065283 908354813 550773583 52712595 437027991 178449428 829314875 748023393 964363152 61276865 357895169 306668639 551756601 593797598 265013541 380317567 764853033 408814417 862389619 737707131 432263533 937459953 91911360 269605014 305069236 850670936 38180270 822958859 69595870 542906358 445111261 540094241 151487871 91669936 30429446 287097992 476001412 947084643 222584203 708881938 983977739 667187231 386239693 558735581 270207656 719042046 847529342 381754846 733615592 561340587 389606840 505063188 450087881 394614895 358575216 15201095 991826172 953388047 339584056 988242145 91122981 904746827 426306367 661526106 189234442 576193247 515374251 180685879 863485358 519106125 365803627 426835063 517671984 863198502 309553892 305408369 208069727 784429141 958320318 941588291 794240543 756849373 530842539 107174772 317580382 496274065 18765978 361249479 825018047 520696327 254250146 390147672 20746892 686194910 252355509 848622760 622837200 137552559 405985436 592486114 885365420 485730267 177809196 871477230 22232510 801598907 75932046 628169806 366103153 427388310 859546759 13646221 883338187 197091095 750869408 950488205 308057615 70305092 279220817 744134326 256308134 20258165 591531824 924501677 513935958 692254428 887463584 316156886 772764894 419684344 908357581 17412270 441179946 20372367 257809014 659035220 311104261 846133966 878092037 165385396 342008492 909403848 187314210 600154997 186287254 436369999 124399706 169571508 497180748 319119976 562896049 426524865 163399134 226349502 194639187 500282917 440307029 84272642 461557920 304715641 630038481 333198182 656909134 62039364 946641621 922535296 169555232 693761733 643742553 907151896 887771831 128554994 734958652 362458729 85040444 838328228 212520338 150973911 914615928 227553444 447104382 713795600 187417537 980908679 298707183 932434940 699311660 610295146 841604341 736817074 35416608 304611442 977711067 942996182 138249312 336312477 925549236 400075284 727016516 62350812 897654234 423132733 303981174 594869730 502489922 351123709 736572624 728194864 840724178 745763570 131760500 418208752 334241486 302756738 682990825 968063659 324465497 301403657 898104370 281790951 685440319 769066845 870522745 942252291 142962319 303007350 756830 484680234 292479008 583201924 236167912 67151455 445221607 284738921 945006220 37857769 483492588 93439788 453546258 178195312 576169726 301665302 629675371 385269567 880445514 749093884 463188280 347628854 969328543 555603343 750248118 203925849 649086934 437623773 54324877 426692427 830035706 963715986 709711725 545078965 250629097 530809904 69016014 57471251 41154623 955662205 616772012 181386288 683200599 908231372 580811622 912604991 347941629 689000519 442312450 418280825 408041991 775349007 656881076 254534368 920940611 1222409 940543038 734087432 389105140 282746533 409002469 499888829 879447218 562587392 486436458 360624030 62946081 93096042 748213872 99533173 873361735 133570841 275290689 579118138 55142400 41414807 44499942 97672866 497444529 317453149 137727375 770384086 345510295 904685724 977265632 137324390 643654054 118007668 216042718 412054905 922777985 571537358 986349968 786295789 90759386 254370569 192582013 282982343 987657037 653437660 335132027 345633550 648828906 350947048 750713615 179326504 502478061 572906680 72671413 223869436 822045518 899121813 506668318 398435360 645235351 563405492 77357218 177171666 53033777 380465218 521351029 103673187 35268526 738419478 455165207 250614652 191080581 907753669 368988132 904444603 884223497 914666492 322544272 127488502 416302614 92270827 588027476 388781952 94853460 589606461 151721939 621785352 37572007 303575451 501250233 657356306 260496093 557214234 301354117 647901358 509705109 531600380 68287000 308107335 629599445 368688339 587490005 528806985 19575092 295932208 622890317 306712878 163013865 47107063 601158118 174322125 258827483 277055045 174450110 224875217 291774548 169291689 269171555 299493081 11164806 187388111 109220163 647169977 259135530 973165536 542396858 753135738 101237992 150930186 463462588 434304478 876043341 116411363 303236742 305738930 485458609 272034722 783902567 960645499 479173424 304288625 541223818 639217544 747167233 992634239 403095155 495794123 746827575 619322952 834923216 563551639 48245326 248178406 747613737 753289361 148831367 795619081 655792199 149760687 694234673 825887529 989085182 880540897 675216863 755847201 210303694 575013254 426705120 503112649 772038686 412254595 592694186 465466624 169082584 203273327 479636536 56678416 996224848 826476167 250655113 311856191 17511773 614376276 634022016 329390886 299077847 796632360 476184169 944910405 467770462 699796149 588481908 420667047 531636226 650070303 568442055 410934383 77298743 2952130 534423336 15549652 726826982 281160749 924740554 700582399 654937507 984282710 801385525 175849051 609028826 108149293 324118858 613808085 949110165 607792501 444054672 517166531 427409161 323561248 890942503 90824751 282471833 221706372 302166002 297506380 357961873 531124001 634771743 501933792 4278454 333207275 970168833 785151729 674566639 874582366 268527104 195789339 220173224 345326979 786783204 131998227 967205891 54636550 517454035 233473838 448575997 948623664 215723038 796345260 806841365 289008035 906895089 620111103 377880331 621303656 481669405 274112105 569467789 282963305 601306830 810120419 141731896 686719194 485383165 607503690 986419990 223520639 513880620 347791284 800923378 974903332 561072582 778484698 536467748 292071541 991293900 674287935 238166029 800837620 466244790 415179400 879597371 627304918 579828343 253960826 633693457 650535660 136286772 488445220 272967026 452404569 348326267 242462594 642592677 73377066 486499413 712017684 610035812 718850511 676644814 408047225 483207584 921178577 140183129 409433930 916264179 127617331 979496543 881735766 259813382 55725714 684157686 909384638 111932452 29742074 765985995 891457270 812747314 224637099 451175869 215415873 954849596 147180791 306190028 969624270 346520696 794064999 507896673 686917401 647690574 166743688 134002754 735366485 986873271 502849879 116827801 364789376 15033099 214851572 915329602 475497760 643513007 445877607 675876781 198308719 952010257 672283773 135630544 352347274 643201624 139827380 80525309 214000889 187737040 836387369 820295029 313798057 196594999 650912293 664175632 43346779 77118594 501003412 917908065 576083129 294209375 227025645 215164404 433811078 29538306 692130811 511868912 72121967 290663292 482606308 424343440 108469049 97435149 273603524 776378614 459317611 636666098 786777087 662665895 559029586 66335323 384923943 886933757 641221767 791616654 982451926 193057311 179624749 19398056 897433207 16803058 763997051 289115382 865206341 728998423 768935974 609181776 108427371 683410380 19870834 330395867 610057257 237620815 269538228 75120570 716910221 895717224 869849713 637501337 992597098 667539019 203671789 855220686 614902532 171264248 678075688 549821085 174621555 136810159 740158160 700258290 981542773 463045625 842373440 57231980 257900828 292596085 599780375 450527080 359901973 568273160 541057847 75899021 799300801 107410757 818987149 788106579 359847271 2132073 845267039 425409042 382171466 507798377 361186751 350262617 881185493 464663307 487743292 960236345 619544550 706519772 75519428 652909808 682207783 605354993 263759921 146695175 484455495 671299965 35664742 140397035 474166184 188175527 230174160 556089257 242233784 172750138 356523959 736141350 763253767 364589406 639711766 732702267 738309399 654913721 187224297 121221801 489531899 472427457 544889549 728087364 957510275 75966154 365851798 59176612 476541321 106032446 74814343 338538771 255341981 197754523 864415962 369367202 521760116 200895664 110193123 346404734 637082896 354554414 331273404 659638775 80986800 872844457 50774131 972910391 427132299 829558772 73071650 858330153 157669047 857206160 539767668 645888772 446147224 384914327 339566796 221608214 833996049 850591802 515548376 566130997 543031590 155943136 471841545 811786599 944994640 51894928 792850188 467226239 924308933 57616509 709680628 579608830 754472418 128001537 698753981 60023302 762018491 76860495 930616306 853839815 233471716 757668083 756040750 242291754 241360774 662471104 825396293 187253702 580149845 897154120 424257039 673595329 555142235 842258191 681575761 993491361 599191123 633156619 32463830 441850932 461317603 430903849 346872952 564865330 353289167 960906088 218570452 244835752 347392139 406374829 450961860 637280687 730943825 267590146 683885981 752775876 486198116 308720200 470936722 151220985 587404541 106823223 781957933 246022225 605599652 126652981 436601040 476288055 736417774 582978989 937757515 451039203 193129340 493903330 781193854 868125928 47685268 736436500 620751375 994131877 379171786 994960831 763564886 620323046 196308093 748044042 784581330 756100526 884002212 77822743 742634871 975695465 453391691 611430398 823631013 382707211 578794358 90309320 968367502 126905054 332921071 22775819 359671424 512416585 620024813 515451026 178353883 266038462 611225975 180684337 562135544 886959387 935009774 707093435 849499054 457723782 377283509 950484605 618384785 512664511 405713254 810896205 596603463 716758176 118052435 146135240 135734517 946267142 240266725 103581486 725951729 950340051 140949882 158267770 718252575 110086370 595330210 90292142 727063955 983719862 476608075 502827671 810634858 208657525 469442951 729099130 235212348 850089116 451983428 676240519 965114805 16187590 49681106 51487464 834823306 477420416 974780366 788317177 765926867 67132635 547656483 301305667 740836109 686206694 940693409 927185993 161881458 188468603 997813089 698562661 494663659 614178756 870069770 356914847 457786366 603776360 58970855 126833786 154030197 384148443 758201140 450203671 586054048 316735625 875252948 130925544 420629164 637606645 11059231 523197185 115777507 489058200 169437362 200564080 689216620 635453839 545814877 150210466 250011684 213405347 442170344 306507261 703114425 724670609 807369343 143694265 796795448 672079789 627874512 8808849 622792913 181925069 512830631 72874442 809809477 620011166 81224696 366389736 803922475 249321913 497319133 168465904 15683552 741716775 688677634 564258401 442075111 623725480 915590411 894291436 312370133 396505619 279016938 919268447 43619572 409178804 150459424 839236716 342502089 930015179 729342995 953764617 734761982 514262520 215875511 175887691 547860185 151241028 544667539 291104659 832168564 331854449 73253031 920913992 250503483 106542844 890514805 463399075 320499333 731997761 861242406 366670298 457216218 213063609 812260595 528751131 376334585 906661653 120216093 829629706 261385799 127123622 36444349 495883426 329657989 239084933 181561194 352415720 258425761 763806361 45571121 215336026 949828951 42531016 288498661 223498094 309181956 943976531 419946533 222550665 111405623 604537989 126578067 640009912 878013743 853927317 818929844 723041145 780381988 549455244 275942455 591160504 70830267 157854115 760464916 863758261 570177457 131093013 329245334 260005677 437148758 331204855 143999445 513175274 172906082 832910042 488411754 594376887 987761943 52538804 430925252 253466249 120777508 895773892 976797902 394612831 435455822 811261396 546066220 192439668 810608135 670493236 553589347 500073288 290222218 239077005 19822726 217233391 413411848 919366998 357833510 733468255 497692543 985072219 933426180 696769807 159366585 789911130 765304325 424755518 149851306 775840492 931661584 319887794 364059763 666751203 369244465 269022754 166457732 72132633 651867612 61500612 440842831 663693972 892430850 786022343 419205513 718069630 237758655 326793756 371458195 411598656 246695400 678891791 733673977 306340847 431762565 786478523 331389445 531730794 827325237 154594661 578088755 573600362 189611098 723612174 249255937 354617402 667094793 969914914 300989794 332525931 961554796 101502797 423997640 953378036 829033866 508722225 59893172 751564997 91429335 241467484 834067965 919361667 189324232 513097772 596268783 365147906 341020555 876820447 671626565 300713735 475228403 520651161 892586667 133858586 673571407 324104569 864252508 975453675 654204719 426996842 604993061 137684553 600755819 471749123 318453544 143963152 148514827 144162841 110082163 919598601 529106632 973007284 573469823 336711194 270545261 957454686 74868980 69407600 782924905 95039391 730370221 141175196 298089789 327929573 361716439 660675056 645882326 600204514 963760202 193124936 953409652 376112130 620273851 930192811 638876695 126521953 698380527 589305739 107889374 201279033 472225147 285989194 334324526 17180570 683823224 912976399 363629076 147166739 252094522 659403827 470730011 568377457 729275946 29141920 147458428 929575845 447818516 967279948 621281839 949068256 457354622 965085472 491533739 7211868 492849333 90934608 331545779 915231927 332331996 446510921 51641478 542352741 792593381 177416858 62883128 95642614 728189342 78243418 880322946 805506022 59620480 261782969 757101164 343680228 633451459 677085666 946524955 872293002 99137144 89599636 766477619 911473266 292793820 640107622 524159847 949808609 738449550 179438248 781244818 652248721 305904763 98424242 914832244 85829627 859826603 131090754 755121597 457566885 127875553 312214319 840711824 963324998 71416436 912517298 371818386 933046835 633518153 693329691 633518800 62356852 156786598 540361275 990853377 788416732 370948357 333449234 606247609 819430786 411584026 525092461 165178306 50487010 340843272 251985987 1369461 530145918 946212726 552404290 95773265 337659730 469841652 455197012 261847865 240824504 455764785 468146105 795239309 514151720 720908857 146493661 466543355 270543184 8576766 920388025 781493800 151769767 113769840 394606428 508718221 749272597 620079896 367776766 185737899 142010833 611199946 44231068 576790097 366847676 777635122 779430185 804529586 672003068 354671212 824842149 431767183 131518650 599076928 175817621 624735730 506892677 408829440 365326122 436977923 507181510 914723548 324811347 567623329 881604403 862395518 238396833 178275362 602373400 98802466 107535105 883742044 195313615 848788872 285788833 9667788 26743692 239193518 425961791 426403346 984314534 5848893 798648998 996325714 212141541 840181849 585800564 605567020 94067952 344037878 397800485 720438457 429407269 607186084 54456459 644894510 125111210 909955428 241413765 471684198 691200571 706209694 141323720 525922501 852685000 695264845 906801725 67001953 623509181 686613935 734139145 550161875 854483815 382743575 4805575 961888062 776900075 303266810 514514688 336595183 293033615 162740727 102378685 45105867 146102197 877225941 884043236 620956266 269613465 171023342 706409330 867326875 334891287 831560209 223039301 806209583 339289416 603319428 635709929 557873146 214353493 221925753 111255922 685783780 131736737 404627624 655937851 934822767 590847730 893175393 457951293 372558857 55235962 894989141 417726833 195021863 929698240 844152002 533202137 909059266 149832893 731965499 309373846 315144158 839877563 515315143 386392256 875093876 486756638 905787986 180642265 130708135 574198267 403882346 525147796 480327370 719215493 794144885 42596183 328581935 449849568 795944986 560720195 955695515 66298061 784201336 697901436 667104672 920782336 706280964 91656290 974570834 533418599 547191686 570539227 570591389 206196920 858021658 541993902 937522373 560284064 437840886 90257598 207784470 190403275 869878064 924361810 21892869 984626149 513395507 681830962 748166358 27264022 149554459 854793669 282524603 664634348 269480990 681617857 172931668 49399278 993528977 613107195 870776273 70243292 3214286 672590391 310120208 4790250 385253935 780763978 910298465 840266821 92674507 393677128 254353163 135584777 732417005 795148157 336870225 199621591 165030937 961328410 222695179 940827917 837320818 922360284 821683072 887741112 66044285 712292510 518416327 701399379 892893789 927568430 884089122 744828173 611783498 73049538 365236268 11974585 795363954 421081826 691170427 122537241 751956900 520869014 834830370 801643620 48859917 637682413 101776438 764793860 876088510 843028121 769151024 834418063 250980328 524039440 886661096 943722366 372202049 987283292 859289029 710852499 815349632 435194845 610906331 162237163 218896830 518014718 779509556 527542800 408899946 618266478 148080479 269388498 724518886 969750113 392230811 23578892 587542298 627518206 277458727 195408508 573354714 846928013 581566170 417771240 186061511 428183751 78289293 801284130 483474629 713883379 630883370 390745934 877401198 642153308 918811534 970655065 411737219 283429185 184862460 763190519 691957606 260987314 521192707 622367113 3771191 75681415 685757457 997142289 830515318 803312469 904013590 234548014 79456293 949290428 376848470 909901224 978183714 831318961 107150933 995100013 81752745 303027174 586988742 198535033 136705666 909698546 339721831 973429517 764706399 318884518 404466690 95205590 33522616 826761149 167429183 945019902 479551248 416097389 797863523 463002967 986761867 797203486 204144379 544849314 94734552 299704662 775666609 916604196 487744157 590692142 576238139 631218408 272729450 993068021 88532154 749544452 379379694 975710527 270499862 412980351 568445404 787910405 615687723 272183749 469319262 322045332 970730546 892567807 312107140 682248092 401774768 924813154 846978747 949071567 109478036 289532486 721019731 974435571 600096200 49020714 829770873 551825183 314449050 92159487 390949709 616873791 160007339 457704198 549403411 717238670 567688297 825103310 798664236 661115525 406755046 35414188 171145801 993838027 530144485 171056366 600089987 70676524 689392385 944354375 302924523 892603101 423286733 247757458 687311551 76937229 979479925 344321375 341283860 54559868 487610542 975316828 166777417 461138868 406616090 60800447 554876793 198296776 90009217 832311706 331220547 353389347 794562681 113920723 635287152 6419333 263304475 752446913 827709240 888910417 40196245 290384134 193504387 464120500 903200186 542757948 445214211 424827986 419648395 142745926 697748310 314473513 143363768 461293265 268017377 683605961 23291560 156603947 742258113 152724837 421815646 857760440 334668222 131626218 954516841 648515586 262801372 559266383 718481323 625234566 381967285 399135723 972735711 460469694 139748970 256886257 707868683 827270959 364743047 203420532 798631480 845569359 121291925 342201011 82754460 197872637 512558355 62861134 627460481 194643584 477426951 17111174 400893582 970650050 655123168 304819353 966283638 580489716 741641221 429815018 877608506 661766642 487392861 863791438 58668697 335387685 753700394 164907879 744403496 235446761 164959970 967628523 299762535 756328688 555949815 248181840 746301565 337696850 566787652 592116582 783780294 384499159 166013443 128555245 442151816 320253015 54258326 228255154 682850954 733603209 49923129 33356095 701977561 392725890 79322300 948219094 318685488 403745237 537405970 946804959 178226869 977825393 394630186 581561213 419062696 405319672 16889935 976536911 780879927 715690687 214557024 743298096 48218975 300922033 748215209 1834853 936563505 820943148 615505250 969030603 799945328 321542043 365595854 858342211 218482379 977795230 730636696 158138781 2941766 115693280 171938719 789227861 678935421 805955170 479312980 421733854 302682179 743906052 778934118 333207838 253925293 503621603 262788240 781623858 447079346 743882718 325667236 592422113 843820356 424809116 922253777 60521285 600175340 393594072 191052901 558498721 85085416 682762763 723326295 495902959 424996903 16195929 585660736 48594832 924972726 626486651 431151278 32713010 911903882 78394818 645339708 200952467 647179061 331384046 673176220 980810750 133848647 536103281 900082896 143670813 562478187 121400333 353614505 42125691 856791850 700043213 954870988 638041705 289789690 141152607 367242850 825700277 388785951 488531863 315408937 320139235 671823061 382032255 545590160 18797812 366883496 164795833 31082830 260852274 232683963 798774253 99213532 228242287 249328124 245180670 863084137 334473225 517899461 547688801 135374178 544119723 214830675 57680245 625005740 247111939 527474193 402626024 97045141 205985600 355479594 775197768 900005790 82734912 83035831 107747586 931698021 464867154 703606398 903947957 590237356 286033143 906990903 956228084 753358772 920872992 297479037 346028577 275931615 99546576 475008989 138303367 452651078 451928149 965845106 55322449 413799511 986803022 531963087 56510254 268403769 951065806 28604640 46098161 792074158 313654824 927253069 792378687 93658250 901694957 283268225 243350812 486881398 507860229 861363734 421981033 780853827 653051473 448370426 898534958 117688997 660993593 985317013 963629647 349028087 630206510 184505306 134073340 980890784 861130578 48248304 316222548 844226968 906535324 19603032 313560147 500787400 721922957 238604171 507502646 329539384 523583324 326878122 42467600 946498402 879515989 336656891 52113826 265696177 902326591 466534146 200921098 115890663 246768571 136675513 301597117 619672387 545818003 417074101 150725488 495641654 517114182 612307877 458296462 403578457 588752383 946674851 582358590 527550647 673162976 80359798 845582687 802887177 159847048 961081442 739599202 712376639 326283182 191066408 879634812 916566310 874332926 897455383 542477369 956620664 936041623 960053778 472684596 641433014 180460881 114844483 57022027 563506326 982328310 933036178 227074212 953733741 876303749 827972144 116646010 952896541 748531835 681739035 467312413 754415867 48765786 584753217 370600383 962028050 32325592 605029781 291184319 207055781 183633122 869654099 557709463 407406267 600725770 795156484 287787090 127922344 786073265 822875759 650878474 308012987 968857596 725416002 421395046 329590207 565767533 733322365 338929721 847519769 917700001 747936283 114716578 870694089 990079458 147501269 545080241 535339492 916651905 763116147 897875992 76417311 621146354 606565391 146642356 615214892 92348696 58102742 589149298 718995920 518464242 184830969 830618241 473333793 450365163 41691150 428772493 212884271 326009356 80436613 460659981 88130154 506430183 354540398 10561789 342838639 716179570 328176738 682058601 553238000 733560439 602858786 996545768 760836405 448731577 184380143 170108404 324774833 105470332 593796293 265025934 207902919 58578929 35998479 355575323 661066914 846139101 595327087 450338547 862184907 737660207 220389295 691129206 628623798 933900589 689767763 834609307 18722784 715107551 590136523 329472087 661147731 884624956 107225056 405151383 372787507 623322438 497620822 573252859 342125728 504936288 110949188 2883616 818784000 732694602 773543863 216332960 487271434 881204276 773609471 504355579 169857943 688483484 892618453 428274031 590782770 75040737 37982072 352786860 728294487 585761135 86010978 90048551 314603518 616502226 926785168 17346950 735810016 332589298 939937915 84853043 208129865 276974470 664504350 15882412 147115865 588057340 413963710 886516349 905373553 207972947 823428743 1657853 509608964 61729771 980443744 916643243 203990549 215617025 618166182 544310347 964226114 347206991 438865828 541248447 253249558 820180348 793262536 422021804 16429893 645864422 216130615 445691073 902893499 132223707 988748189 383041209 602761616 130932300 975019310 60488232 422279843 36107946 105815721 937625226 110661968 946657896 351188998 526793461 611541348 607793046 700117177 252590551 926856701 519480735 825746430 458296872 983806947 347383269 768803731 560399803 408421646 852076352 968274449 492026657 363972967 685358403 421884361 900131221 177258225 889843883 256021484 596287674 882020794 847878915 318876840 411592883 520191513 70594880 276551872 880783989 249901405 94635987 406895764 689130274 58501259 130904712 738105380 131869164 358876816 354226787 886311768 836229984 695673206 80287877 334284854 614769284 987565824 510025873 684062323 978922204 907916531 441617191 839887520 419139205 534063037 850638990 336103128 914365030 41371485 147785292 558917309 889627455 228865713 962145753 661624979 925973359 183645940 874325681 808702744 244146968 345136434 679970595 352390964 185639892 637148318 58965322 925315869 777197249 633720194 495911378 3185294 570067279 101478741 677133510 586034417 971361051 647402871 642106644 107712744 983129240 352361459 823876470 583217379 119918605 328063820 29200437 650951379 508531294 679574084 120153432 332325388 729155131 245743472 549125359 32558700 448221626 354905337 931738748 474811348 307156383 535574898 133101523 403866037 299194550 200839032 666823950 879271500 538696736 612591173 114194552 844076985 648469697 141888692 318636745 692842695 256963096 806910702 593394931 589347974 310530395 163546108 280121717 444356143 159251688 896402447 419715140 450055066 253188860 802166772 733156249 227470153 70803317 355087247 525009508 440936417 253129090 77204268 388386729 647555127 17153079 466215818 908647947 30688361 556315476 715825432 539067146 491635617 971055310 261293942 191443682 373465148 852142858 584880532 112491615 355994186 938721307 485021084 748481935 326695352 383573903 20294091 322434029 89062411 655603156 635220634 894253051 928021809 258703723 507149745 521908758 716075613 368131316 244795982 750490641 518231467 470208314 889381295 781539980 622461359 617019507 587284460 370649173 618778219 315179403 187317152 644255841 119768610 96534539 50596703 358296380 120273055 193959298 590201962 340942928 909090505 37011788 784660998 1702140 530984594 152549437 486256963 219987965 806110009 218837605 739807156 73289238 674935854 277201470 581548974 270038594 85949355 169373137 586061133 707870875 496421316 564190903 118454120 622017879 285048739 452079283 788537292 144325745 800762004 342673608 786180899 139977304 856331518 256431420 109581389 69426701 291164260 633631536 156942674 716331671 816566512 799766731 96014961 69207958 304357379 305889146 657607331 626934977 920775270 596050484 669039284 445818646 392225943 890028972 690638208 524369371 162825977 451572486 483589908 197333963 926679045 305379574 107234693 964918707 431453808 16113777 480747060 273877211 354456663 434415420 21484538 887457066 582023997 994881504 390211493 717261195 833151646 549247024 909921703 25175464 302898876 568214787 14796800 11033085 78519148 930884665 667048219 75097987 773668664 335774554 827204331 167239216 308926181 641944082 295882941 101361869 426279820 582418028 462414878 890520012 99897844 260343256 350317323 394390761 433043935 864263537 133085964 962020095 98193072 865345524 925524377 464267494 91162880 888671114 257520916 374437622 471161813 45039899 168842463 23637435 675359838 402973680 63679401 366591706 586291240 432540854 949327880 712104604 901632420 890073936 630045286 898802862 441981397 89692327 443234876 149917562 100967352 792716284 921883328 163416382 539593410 455562402 628590615 346037440 176934627 16411651 225990664 315760270 99606275 183863174 694359394 606402779 510898947 476026418 868120408 142036227 80474897 679631885 455175737 744752049 6883386 315350573 794604616 436421438 563157450 23283532 558899182 497578992 81949435 862918862 182702935 436012947 590472347 253403270 1454175 462873388 503394490 327441539 560708351 478406978 402620138 721981100 383596075 21778308 868931457 253853602 240531311 664105770 864081459 477084503 752143300 596957897 374003294 584077543 939270338 710188090 21466558 937771177 863610612 229738805 192929330 997282288 590880828 486981134 173566496 129403969 352578220 674145794 541705592 387244405 174741710 584266287 125925820 123893915 663318647 357224117 158333594 222600566 265453688 940282275 676264090 686918815 605759098 680130157 676109196 990396116 70587114 632426426 926070317 810695886 47137825 769515705 767073850 379378957 321892635 319348247 597170834 697240970 145470594 949830611 864096607 621869067 217142952 812033844 590325796 41871322 327306390 344040338 416732025 78599283 766923254 415542074 338882694 305931365 584281716 450512013 420706750 464207078 484963516 876094149 335043035 745636105 667303545 676429691 310045560 499358421 511936437 732736774 782150296 385556083 202395394 682240791 370123850 101556391 601626818 415761946 134529300 210000803 769938707 741071203 225574404 335032465 147321122 194442412 832421542 606315255 57451392 301246033 803002097 375013064 708237445 637233565 549428543 580784715 946402210 552445829 489095239 313415606 191201593 487026625 483012169 679416645 632206780 674185552 555440187 215734418 11861598 425857846 427869494 364357304 352933282 92500262 121132258 191278640 355589289 733434432 536837157 408326395 698465814 493158146 904554112 216803694 60809289 775435855 779291104 879686519 35418645 626146782 708523456 330345182 597819585 39959800 778161270 177400359 705703067 126016818 548601743 963276047 491790476 557357782 827627008 161177817 619874752 540713910 556455069 351689493 869478946 37029549 815754953 37760107 128246540 76418075 635547952 534977764 579975658 197577165 332267221 271552742 161304769 582455671 668910843 286446522 408283948 247803763 146220124 815535726 598318266 700856985 192509792 884829088 307386644 741271622 8296090 115321883 795732414 892227013 904229454 500093025 383354656 208642385 414998092 78861739 469962361 356676178 963759562 965519723 757304847 461618919 634680412 811848952 542555342 534395477 44476797 801846542 217782841 140262332 455691503 539299319 183747213 922371820 266918277 372482153 187382741 557252769 298397269 673111381 530935291 264236471 529414802 863224079 440188097 268885550 915557198 282484670 694948897 381568483 675600371 168791595 676451382 369060205 420939812 54217217 42280723 509278019 711417115 628533428 474577201 534591606 469037521 110535070 154208369 489594091 119079282 294464645 385849598 295539569 432187756 882953013 904511854 594772920 646430368 133239658 933322641 906802229 162765034 18055275 503294440 872734565 33974446 69221027 967512050 139217721 793671351 468537337 878293565 132334731 85694628 354976044 337755704 825761792 16000759 766682934 792047976 877620435 946318186 102738935 479716384 222551675 555932349 602408387 380774206 980391929 820321490 138920140 136465316 657298551 95162145 347291947 196831337 560960747 35305003 237535300 156007040 670336498 166824102 948306215 529162292 615230324 400504241 602263510 487035231 211780613 99164800 622252868 852326229 556318075 139759089 794639073 166410696 607222363 192685354 660289651 363371521 683089272 265975611 286008800 186526863 352289354 946349020 806415285 770069631 345722582 684356040 730726230 83577620 546253909 88401103 868051247 761784117 141646684 842250970 858956716 838546870 741938250 65318091 547285613 268606525 808207051 483116595 255563456 970364793 781797701 425695082 398323752 184826533 919479947 100529998 970797674 589851465 522929024 752554838 615143725 135669544 491545772 663952540 407116796 456228359 227033986 113942009 528209428 137980742 423156146 726181751 966825347 98282705 451763594 916776745 625301293 170769897 992524238 995579311 680194288 97998728 174591632 121420546 869678991 385469807 172010541 256057966 856310528 396793280 307777961 179891462 102852039 792158266 75221094 893833676 874043921 787561698 575403907 843067062 878282987 586863952 602014218 404798903 667125636 198255494 402098022 579661475 224747437 341019234 534489947 693903150 862955061 40187743 266064024 522698961 335930946 772063176 281082936 950868609 250062721 243708204 487243527 618385120 642466768 743528239 505948870 41386530 164263539 30034903 590923594 387116959 464051725 198362021 984418915 507252776 202652423 570384307 297813137 274506539 587078679 101711826 625065357 691614433 11418634 34504163 469471085 594808909 552621846 986219996 961740394 305146623 435252389 877513206 736949747 448128823 267875310 565909030 420829241 405200680 908170354 225330591 605503454 122334593 684860656 394843230 913431913 603562611 568521688 312148268 675080355 362266713 420229435 325219352 647199926 981002080 607530272 283981746 913661200 970950003 360457222 572962118 424068891 69701297 444046934 134082105 45079365 807276218 791575972 530611253 336326858 27919945 362638329 101806664 783962093 316180110 407236465 542484693 265453676 664294645 672037496 901835415 79790443 540336284 227204704 736256825 675357326 776736098 469496657 290612903 873686704 364432042 441260462 281477312 650386122 700326307 896271170 525620192 24334442 226044306 838752073 495405108 955685655 623357025 168463780 695565312 878423991 738533654 963586508 834440876 35269066 43540917 973229327 594500507 837529709 932979721 460888367 858745311 739606151 445718544 50949288 487598264 234435079 382868704 688131616 608678539 138756714 264701950 652989435 410147438 714603756 698642105 603488948 186642267 87812023 573458563 488934278 486163132 138813952 689031085 461648817 583480958 633152518 833331813 307785614 951380746 45741891 383241945 679700851 993622419 649080616 331239576 193323507 100449432 233397242 570532242 664821732 808772037 556128758 322934340 427824459 175562981 393962145 956869859 991573754 311347598 650000957 652412170 361363050 218530242 114433487 230316686 59509914 582000697 253636644 186120436 546351694 566662810 354893400 957760043 438745052 317427400 220550333 334570477 774218105 496574889 484932743 796563737 458397327 16279315 108048733 848426140 717669888 129930230 594268647 400372487 379660523 431151622 22475117 256581818 958150179 923815745 537603411 564562526 419446758 359544736 267993632 292516503 234526326 933624302 355317022 948065335 130724388 718552302 477706157 271324155 629225101 4853138 658882319 229994471 973973532 39695632 335242503 871550376 272663049 334693017 565929632 893665862 19304443 941281915 856576943 487317969 205163515 651912239 478505553 783939506 710299930 211604533 167099603 670540204 878256399 467100483 492873844 217694051 99054636 571461265 560569918 300807865 228303704 280615673 79607903 997164927 943066001 71296918 864906075 47239894 382740438 945894929 499340905 179888212 862737318 387991685 890278010 191055586 48319061 848035754 628512310 343102129 835893939 523042995 741969295 139867711 827283679 575528001 986884487 178511323 771598903 510071988 859408727 123348402 188478557 918316692 64360021 474405533 13163101 900354958 419654989 769201535 8357037 933363483 556789461 281793494 353594470 146003504 629037206 620785609 771303040 208523152 2507305 859164841 320003539 444046349 965448814 700087667 814253685 184565511 630110372 558635955 136982722 178547784 222116526 798405434 225070522 137173250 887543871 764592949 799473279 255527924 60727074 978454949 49836437 421292399 12181711 42714480 419284657 981296547 358439737 459678308 241424776 383863915 935369643 225330089 767969792 824376926 74012015 748695593 381157226 466648315 690805787 919552826 36208513 543868783 284199367 286305901 750891581 257199310 125266324 152886116 401456914 835079437 550401807 152199574 650887547 923545721 733583796 473426224 85451922 490296715 354038141 342733325 774020447 792066132 407067373 659342774 474989403 596554180 53628489 759806985 485340969 748956668 666518489 446718080 618123492 67687889 944905667 246166616 497823596 987050556 360103649 848887265 405453470 366985 439234849 247472532 603040441 481906518 870599537 765226479 722871664 698011807 603596513 66136108 482952478 497278850 916730649 747857925 971986121 252818117 323866687 370203135 528661208 625607376 76712447 504980106 723811394 844071336 86923381 432409286 662286526 188248536 975961200 753570076 110757688 537760689 185279425 69334342 58774 373890612 342373086 19991507 545286749 243374894 702323429 847864315 426387954 436096415 909646655 119947772 828579156 554409108 923724443 831490455 101459487 163039992 775941200 615727812 996001306 92391547 893179563 235242047 115878730 71395406 777343205 333490117 746613431 351202426 62520469 352726878 521956164 222874764 442248108 970878970 980799206 201172613 969521188 711868426 830090801 591748590 833436553 446697842 389027351 250409695 521089428 116430018 82915491 652614793 555640325 732630075 647964518 203305592 444452378 631339489 457451515 439637387 542331711 286455837 726865733 935680850 714850606 740609478 386383377 514677853 620487850 710065077 129454887 39081 851958404 159084183 560615476 622687995 183274437 744679883 889763870 732325670 26674204 296269504 228966632 536692678 786019006 843615650 681842093 509878435 825744545 712698257 376811741 424214374 551371687 364097535 306852928 965752268 434028135 760570882 765489086 69093655 31583233 499411202 233579565 788624550 709819328 550498591 288434029 669986939 438000601 830282110 495649651 744412322 960015934 601014201 580300825 394271326 33548967 554082244 496921663 32440671 86946082 84382064 592655066 791450382 134855622 793315724 388226244 21307363 283219670 866379473 154354080 141959031 47177096 631693313 49741255 444604248 487018221 390927825 704967474 282107164 788576111 912045789 72656300 129432564 632278749 953678315 840035478 696291313 486826317 859786185 398148852 428260438 598617989 681039340 576744176 18050899 948597719 853583024 252674716 635866117 129814827 512496628 372572396 412258163 239954613 694204487 690908241 660623450 56225708 153422276 920440439 648400615 692591444 435888868 352950339 898489042 535878821 905337736 227237653 817963975 523116171 644910328 495599313 863088019 516940258 146277897 676616896 789287872 802820878 744698520 261326655 206279559 702127642 246448063 653981815 797545175 630042168 777175986 327193306 153451950 500126109 495697162 664475367 422776219 244378922 833988294 192770782 586969278 126562287 194096438 433948035 750329347 285340538 506315655 162973474 159286544 259122036 720425686 371604316 787628675 48023551 343243148 251345627 502588443 411488355 560192488 926489630 460373117 417525337 931255111 284932506 893569306 574386229 214864205 186865463 631354246 909832476 542708446 593389382 310532110 212656553 683335913 191087572 35234141 943238348 680973235 594229894 342556904 933386841 35850777 171995392 283585875 570370122 109305386 361093827 936142383 161738838 145958128 32212060 959793829 274977999 904298826 676038788 474313466 114241022 687171415 658258846 155260184 876702487 57791482 67891717 14456902 291235742 438158506 423069423 730377591 327201865 58024899 774462059 305670557 163317370 615297714 930509770 819253336 732701244 173106433 305306186 396751208 371976296 384316043 684166030 407501402 241794420 944993224 990915083 227423448 115235916 272847286 281398733 17348443 381440711 483937138 12826758 18945825 136353129 483327137 486818105 242848062 328248014 675068066 793195084 492331750 476081452 62716725 492992524 139573832 427841076 835923515 294240245 65929961 383169598 584843747 745198500 307618066 869047762 413144977 322769062 106866927 329465273 682037121 474657229 37712536 460192845 776999140 143014990 472516535 503071753 18735818 382501217 558682759 776976489 443286308 616064219 593303603 747279689 771129070 524284851 672639028 58254380 252707270 978791721 810065985 591695123 795521022 49551516 397449501 42265447 21111400 141274990 75903308 921670330 736414100 118683781 958737985 768930824 558742070 214152025 161754017 505329981 413816100 537443981 373302714 543755705 210768894 273781658 110092823 7616557 286146456 403282433 659416002 786018669 663171507 753328348 434459502 582950962 143440026 388277203 362213114 55792487 94011858 481011949 369611282 238074209 15130571 886000084 926825742 671841884 772118510 38309023 501429647 240326233 129209256 711947468 659530236 4451463 182979080 947475313 308754596 358464519 962806725 269426289 52612664 894971474 526772973 685250928 908725612 591549104 223842474 122219202 857907455 225817407 201693735 479353434 24505754 264875387 873126796 304053507 571392056 336241059 231140430 184356969 488424795 137591671 993919737 440270483 682156665 114825847 186803261 86917144 905051910 95778539 629701793 10248429 79042622 515335046 896101631 918241487 495457626 865031814 409916373 186472226 174377547 420339115 20719362 919289622 341355807 288307641 301110081 70221558 793930603 562236532 391728627 771367538 635606965 436679899 218041508 681397329 381841680 542732828 302199064 293540442 417828553 209149871 275363514 196473212 165017234 853330913 890280148 196799219 315267681 680953738 615091718 247397177 258441447 913063823 539329399 961470604 881063533 121500392 882305583 38250939 675459809 171148042 56779622 666455492 184650126 102338293 121821482 607832126 25363953 170952598 185894965 14045113 351158703 287642050 166112496 241845946 613058775 644725181 348389414 760410060 928154916 255287985 12438365 683485612 625242131 114902592 429834561 967150731 398437424 551332896 308077231 303831561 422425868 629967274 531430246 221826995 779912670 780820188 647260005 863841788 290084927 570740497 366882952 811721189 835241445 169308402 111472487 50843585 752827480 786436291 267037463 153277663 400181282 655028159 16774286 537736437 688093553 542839904 657327095 493996984 195251028 779659952 850269972 382790315 414334580 928472079 310372233 535961637 507828064 96567061 131289430 5235693 25179368 941910806 140686248 401190455 982706096 646495213 679693955 354961862 949649484 498530915 861075153 940567550 30896445 462645226 458049361 910177019 698753158 663849062 257559535 372397561 104471868 6680741 910872651 224216139 293377323 452413517 87462363 283748712 540772992 268893234 266919132 947824730 521078639 101559316 888726158 719536253 99917642 769237791 411412026 978052906 282778571 808448618 403712012 913834293 514419576 588613076 422994651 670148222 578020114 684611214 674908914 207761716 955763442 863538364 205724709 408529612 182966088 159745255 20672786 515631517 722130513 800925329 150679775 288450579 741670113 425234703 708658719 429176037 34093358 118438281 172376338 871999882 712573859 178030463 158774708 653762785 751400240 189635920 487183457 847440481 734125054 906249900 566146401 335977849 412134887 994563917 88341260 37526450 535203048 315305754 599487234 471302117 986489172 555000797 642124123 129309272 983790166 713763010 805440559 550278700 42706300 301187464 630748087 779432458 765486377 158592882 14474598 456014498 669175046 953529978 308705445 90370960 696438746 997434223 830216379 44362458 384193632 880653545 913945474 247353060 225680138 829900477 349791387 953397093 897886381 699626576 286400960 995846744 530199664 893684409 661249182 82439089 773780360 702975409 216176155 622931586 278216312 296907451 459317333 382021603 292266264 114473908 287073520 588817766 336570454 851058286 962258790 888714824 554202468 973420332 974284456 798659385 567413385 113441002 58233638 509028363 523055862 189158175 730911730 795697403 789890324 99930856 377170311 804978387 94646601 667607300 725744322 782621276 746911065 538375652 292707345 576206407 817507756 812267332 890155945 737474528 728138409 173824019 534502599 973475094 247227620 853285146 622469428 735893992 355206375 653871102 127837925 674691367 61277339 429952407 709615577 233156696 618599974 143909357 904984587 516355902 974731356 143650239 532390755 450084481 883758217 702698386 62181294 57141526 644203796 708441271 684967223 553226032 954374809 9246132 458184540 375618729 837170695 682882111 789322964 312784030 640109895 871288354 370704538 767565814 790420744 987266985 993258512 206062045 742844110 283718535 745444042 103507908 832901521 408503631 619880994 500461430 268174853 117262168 89289239 623278807 616282609 441529691 441107746 986494102 116465045 39717077 725576180 465022101 675636005 871680157 907323663 399778896 650585455 54104273 551139582 763115110 640209420 871715775 272285221 276096071 20998719 817541679 774643220 168378682 213452884 993520411 520784292 926327062 102360257 36842170 912369128 721457459 970299406 358942150 222283421 729663020 520782048 590759751 72529421 730263842 922548955 648219808 507660975 649477750 994109337 545292471 638483013 631280657 987432351 200058416 111153119 937955059 556664309 584711067 463658079 371007005 63188251 553569741 672211395 100304193 277503429 524755610 639624685 582702989 148801079 897991191 267496685 465884818 580990834 102285005 92456657 344869429 165814354 948621026 403782913 866496428 162905635 662515303 875152804 920317336 660386387 198556658 395584647 729130292 807079209 202232903 134876551 819676106 258741548 23955141 336082390 596185637 413202308 484070152 757103332 326882981 156928713 704211445 17654858 748813577 85976623 622791738 567235866 901780426 644797487 64895439 321796567 690945523 259897263 310868380 396434573 19387400 350341460 939308768 429872289 829942444 932474820 985093666 250093946 579240894 728129173 61754025 209465044 9324919 481334653 520323007 502948178 86223836 386295584 250701222 44793761 424766195 89562098 271187854 486275044 273819767 93331099 225813323 558267630 71930762 855719779 919491014 485158971 811098641 973674226 568142138 27417884 267078925 592221779 379875284 641153072 109105180 410839314 154964903 872866807 996428839 46733493 918793332 981313712 513428189 131735143 895694951 848116526 380556953 45054541 566566654 546366051 220700292 218681581 127934728 73691277 741442827 840056718 190469018 23272767 161250344 553310126 946182605 624087233 280107132 256492299 652058081 568777727 427140028 361969338 892809820 939099397 551364025 591698354 149549663 65999454 125749007 39435940 562545992 127423950 566402241 516470944 913228395 535399373 322250025 557203450 216479732 286186091 911109594 713556622 398144161 750067688 591752581 935475003 219361642 380219963 739178556 921696802 740982328 813030752 346680233 92276268 665630508 921610352 295373067 305345497 406001735 461758136 184497427 842378716 953331283 214428808 552869343 402913051 374409444 802855997 734772926 287322501 812139775 841586121 114289433 637730176 105401838 830144008 43216316 547129773 278022192 27969504 657509267 21107468 752342693 265819638 673850432 997053439 815089680 116173699 281424870 610380626 97417905 665551491 895981222 29590237 265981271 225331509 838472159 20729803 147486769 292127816 334054024 862281201 800391957 750498642 377175328 333756408 32115718 329207737 387432138 527084333 389449374 204892135 148949228 329808555 71608634 796762068 217786463 768118133 839799287 763403917 651699557 265919410 648733001 527203922 227655005 664284512 213087539 647066212 111101669 8654335 720158787 205129757 920686649 362159739 249650947 997236481 247336504 877131139 386340901 400556996 104156735 331710266 239413696 129787270 628579068 973829730 986967371 86704582 75329358 793474544 505556659 839234863 405629637 668648889 690582091 387959284 807489221 900638351 596986787 633691282 83220566 126966364 719416041 6039838 127048500 775360588 876570463 339425775 607776339 685127074 62826876 565978279 339663959 557341854 258889200 498391632 594929680 422997545 150009926 294159761 719489868 364321618 316187963 538823197 455897944 551766900 466136132 797056603 197386704 778894396 812463826 906004807 454430304 861853579 564616579 615439047 169755118 243854723 804639467 790367123 299077079 907394355 298975406 647900595 332274265 278041251 23216743 791653787 54785566 551242695 353983720 167840695 541793252 971692887 44733212 955170657 692981658 235308341 895381499 691553080 570468200 988428364 301224534 826464460 782798986 892861500 986384227 525849303 197070253 834530164 355537511 431455603 593477985 909489390 279878044 788005677 12992359 846495435 312187403 489226853 894116579 547938756 118840128 146417114 436254762 707504871 434312894 184500508 582136520 321670617 69166323 252638505 351043483 534646457 661050047 93329075 337347751 763228680 103573053 230710119 75149255 419630769 598470987 611040123 475238747 784846749 837323510 524556467 328631651 713218471 643282573 52169283 763901209 940925108 216558712 589229864 862043019 712293389 57502039 297594837 87165990 366976216 14746362 520688983 754276699 737248310 196955728 32591605 290885918 928004679 782352866 224022971 403177137 492501749 273133009 409731034 858146749 490378842 772274995 927704690 196464903 638917237 328955159 651530758 550477597 253859148 917274476 138884755 235194409 309664273 407672200 657167381 599029712 843987465 233798333 317327842 660735738 417082918 142958244 597952820 206077601 275628472 405539554 602621259 380116268 763080121 658004847 173204846 493317707 647134286 877252911 958780625 948936773 689375477 986572563 230947267 976400502 843797413 930567897 479794659 203060302 454937575 102592129 50732350 982850385 176081292 65098365 610080277 454920017 458074288 50090249 927142084 334811021 85823734 373671382 777632863 488487901 723264250 619801734 148171514 661797861 746281357 9876331 531480649 330857314 459155409 147965901 191424755 64842732 184438058 349987610 533847254 348427188 676453580 879646095 623387383 995932261 378593245 131872673 628057472 703277743 820399644 623872868 668764335 987025884 787662191 381105123 250235493 834616839 703462685 218537199 646488868 176644067 892295515 264182784 113415394 363949212 194416527 373832642 470731928 222125241 476336039 97596805 90175072 582899090 412647295 219075115 537744888 263495480 25954955 269801965 248974288 431554640 4286253 264608766 304004933 97595113 791274971 8758632 494254891 703375281 854776923 234453094 24309889 10850088 922755521 96476460 530049168 487911561 470553658 422839278 100976854 96034460 825218650 174353819 107029272 469404656 830953194 706143393 42686744 419380960 930148124 830990177 320022661 297936567 947236721 853005794 707925980 949376881 759963378 170390872 772725714 414174348 151724160 633348716 191690690 114969105 892902709 537471574 521898986 636576897 206231075 335523465 449563702 132704590 550306727 906998885 14529475 325467358 760158917 658023219 6112261 828340703 690640930 354350633 842931094 981041666 577853181 334176367 578477545 321466425 493450000 77312164 913681566 776956117 797909160 611897150 751994969 478145928 564483258 335558847 26143844 665081964 83095641 878124913 81979953 216186693 926030306 419449158 892512699 516657944 934160153 95902350 552972419 692340316 789245116 230570399 503808738 331933785 723963543 694627232 370807985 747111244 312273117 943383607 781704658 567079341 833151980 391716175 49248454 452893159 258526059 293493434 77841514 49633511 928807485 270251133 43443952 229928908 229397526 840771123 45240792 95912440 66597223 613421643 633572829 414755598 495847593 267001412 247293158 96269109 939190052 140810369 764507296 576653305 778372663 304409584 432325631 841762716 55576130 12591175 30502797 479836684 635439219 334460626 597668648 20677907 49297198 487261050 270787511 694635584 358464007 757437438 699971244 89518715 117676535 887511775 92974038 484104226 520354821 159257142 841782906 204450339 504982240 114222251 586284562 741813877 638400776 4231260 30980117 614984825 735074002 71403729 89659388 595226809 59020645 58329768 186980828 48412654 482386770 380280680 145950439 565657381 531436788 233974560 359636268 945691168 728532196 520063859 203665522 974152006 93365915 785404414 364579504 972300677 940645602 732930201 218763564 760661404 717555488 677034863 487977829 460124779 514366970 81485856 869090240 702706479 798549445 109078996 887960965 943055450 887126280 293839719 583035674 976208697 624708846 283008072 37474330 474940059 44639053 520285070 280774478 384692492 260220866 201155999 821551437 190886803 463741446 462657277 105415550 25208182 705433974 208311211 143151696 367731203 203327474 510958949 653812961 623811349 961245588 47106291 928797255 973017074 574851288 964391097 27471357 889505790 285730965 125745978 204716983 665373093 859274528 93885064 735706908 729352581 612650166 463502469 807121830 499101906 743291739 86924956 857062024 200316713 36861895 724171353 218251038 361162329 154808041 236950163 623983217 176149069 565640288 277750117 218005527 181248706 890356550 553923023 816382362 860024216 106223848 851387467 321537621 774113078 661433674 28021185 28029939 336136042 542632513 732569905 632744622 232929586 225733374 210468896 848612346 798002319 215254905 387603106 272959849 203273712 126808610 683017393 348295369 618060654 809081427 639983182 538424662 148549305 584734026 192962997 468378998 139315587 244603068 390531208 326551424 458894401 549091954 833775509 913906714 756849451 101535832 514292374 251125991 89601077 172435926 438855167 551659234 513023017 699879093 432100298 74386875 761297100 910620243 865349144 279863821 68108285 31958101 745577319 802355167 431161980 376467826 34715584 747219064 845746348 505568187 653771570 110335553 457220842 849109677 398161909 532891165 842492783 713789764 29406766 86413242 856935931 639083462 78799603 110172458 538897527 32693777 297909210 387697232 103481196 359167885 116844218 280156185 45234980 453369832 442593748 750606770 991196919 835875624 407339326 336598357 600409899 746662422 615273993 32397028 987397061 192769039 624024016 534210315 850624247 846111343 522372116 57630360 82313840 514332196 991510131 547142347 858105080 731964651 141182899 791883692 270423768 231784296 675079992 431918851 836914774 887035608 200457531 632901039 382575400 362772210 829491125 357978111 59307543 655712056 158614367 646444974 297261981 238555396 739414116 975847924 531657477 610684881 805270113 453431629 319315023 577623651 695511334 768725373 564081258 950247768 710392708 712701157 67968634 876850691 466192228 994457986 835536852 873100981 5004537 432647953 678483116 654294441 810774106 186513265 886641942 487318491 15193125 521959123 790340360 972149468 361639714 248105979 445890660 507603316 528557529 754811126 710740215 583040807 245253110 583262431 657479799 11722690 371926986 922356514 261250504 936641667 931081312 5805199 463936568 955835303 347128053 387438512 302523063 379002313 114537517 708649434 431093664 756947087 228848382 632057401 232789299 648046135 68875108 244707830 263619930 810506267 756008346 15169292 180608367 863293785 176064443 851519556 174816742 573889299 737559923 598791719 442241725 677195041 392346142 705833572 663072893 975416933 676383000 116692227 992595414 964903888 831967534 371554743 52089722 863725141 414340836 127450362 601627869 41102363 502948222 517863517 576891535 306395471 392109379 326849031 397127021 67794587 665154149 645711944 925902277 146330653 171312923 401501189 863358184 264702938 988782449 163924226 829739011 423555730 984621909 647648014 819275011 23506673 127401713 255410103 879741998 847036568 511083866 333471997 429289350 720940296 954552474 332744966 4191905 653335990 448243041 937361264 829400428 203210193 452385501 903989663 244846916 342231977 60020722 564105805 527970467 599107707 743079452 594819439 906956915 114903554 373835455 471486178 556355900 697087987 134845260 935087878 418635827 565510633 283127025 566750708 366874266 662719311 292410291 869760009 985634501 729299376 548324626 23292221 118382718 9879703 643563407 779579935 464101059 270123018 413308288 692687568 81990867 92285479 154567040 755243859 58151262 967888670 297477730 176572639 176258321 660836208 222258919 150449523 581782257 995509329 961009670 220412947 234756901 819916700 256050296 793202948 900321893 782785638 729483928 916388810 357690163 284626314 762470727 919148546 13389279 444046970 973342722 472308970 889287494 934178436 151483621 16375046 268748874 330474727 412920201 436672968 790330405 610413722 205847679 915126052 222928701 476106760 586129344 112866663 346076894 844848906 456720018 688169067 14825120 78646870 310009342 181762023 7027515 378441241 745154096 680064963 157366396 857572756 310252104 749224608 247086654 603987608 963231634 605558835 791510161 477694191 973237829 928154430 238664341 674549702 758147941 478322916 326006254 632015867 208139141 692812491 28850257 231933459 982708376 941105674 911026198 739882587 340105686 349045848 132812267 71762502 635354527 241218455 828484998 679570863 888238735 354256390 178997013 59349920 581799164 40213604 589122621 210949921 955228380 37908596 155013031 978497450 265655557 502260277 320843717 281697268 834435105 12879600 905822027 500670800 905294737 432537721 323554603 658839649 528179486 733073870 387997499 406019791 976640472 366149800 227912710 719606608 787884735 894519393 203823628 733874236 310810160 466542862 638436487 633140464 769650395 418535695 523471753 175578459 522405468 149841619 47050176 221487576 396048240 274524136 515069993 73455834 308937452 248681639 692955977 410839255 547663536 578832905 135358965 765596617 917373740 71079997 627113363 652811083 115405637 297289568 370705901 606651628 920763794 729121938 957408638 412336424 599956739 327774150 701637989 715989140 969556101 291324525 139321161 892514495 348225457 637583619 372703459 931255367 986453695 977260827 929294598 403873109 127517631 393615353 693229077 426105742 76404873 728763293 157354427 611415759 218178851 747541112 936819129 289619891 418084887 101927782 53408360 745663306 598290089 417825821 585907901 470465860 293440099 333710845 174157173 325553021 513266438 95059474 297004958 166734706 41510536 63677731 198116368 60680155 374298924 446891245 425153819 991876816 615485433 344520625 983836696 23274416 246899298 200872103 841821790 882800387 522357617 880053926 818310720 317804153 367958519 975984999 525935236 745024609 805716572 163369038 699468901 536396791 83946935 552793081 622271012 37507911 645354593 462688403 416418105 22681367 670537430 231063520 266489880 621510284 7851563 89161527 278034092 495861200 417287154 502570536 362114448 712238147 638236693 302748288 936022266 388055866 475880374 984010508 484855161 719656114 974015863 36746805 812851522 441982666 552437382 186743613 807180337 995604034 683265703 660317858 57481902 442085040 63069140 784770332 984225002 225923973 600970045 516333476 519510507 426987878 944109120 773388357 314336626 234637613 636663454 578254277 961353550 264934873 509145617 761050897 207267490 679641683 458123342 248395155 176820155 39026110 255592300 805197662 209124764 806979439 535861708 32675830 556545297 721601955 798312025 712245783 312406964 279234464 332866569 478075243 168124607 478244856 330638011 320606120 549468983 418566273 203206405 43027299 971319839 629147687 273177006 983674602 836287074 564268038 577804138 302935016 718865134 360061428 31660111 293516649 470197475 20193900 14574093 138300992 726398568 340196571 358642309 750594635 152616488 888637517 439232721 165000234 160040215 538921768 86071559 106425260 511279898 87362437 157137567 114629170 67518896 405793216 353936656 191598807 695390989 766677394 928626390 366004831 977447395 295167081 456878532 655682372 53579894 951185996 94328456 449859919 239830839 797593635 194262232 357220544 523866462 789809403 349470311 465789288 751689836 531726738 224597131 447384008 221099427 249412930 885841670 775209544 304990511 16395736 215332884 780806579 842917391 283476459 842260998 166362751 22403245 446034739 196529879 136082557 246191854 870532131 66984391 319693671 240025465 839488522 769380738 585077053 453709787 168122236 678538231 529234873 551349138 139645829 590203419 966883476 800393425 374494503 181066876 682654015 409105911 743753194 128073890 86875554 288203553 398921726 920167444 285745929 895310709 470171247 672420185 771928730 54275656 835274382 760241617 205345096 390948389 654693368 822947998 263484006 214667418 429952270 349464575 488644387 748845808 697315578 855051450 319142962 188113070 488108304 890313551 366901666 634873694 902553505 313997372 455200039 185156215 880457345 592798349 626867396 949687260 692584180 180791439 757392848 902029248 945483937 877876228 570875638 914396250 807249399 583509564 405649624 989742010 617363779 36766311 2411732 76838615 307887296 84101693 436432348 793534231 218977040 670561157 323293242 262941426 709969601 800792193 958562758 995736804 341427768 867319399 303381838 479742549 905451296 828167727 865816314 448677908 50093142 73764628 614434989 449155303 289491657 899070960 448422550 414087152 1517347 461282739 898259326 823946957 60093705 740807599 237952643 679089231 496806579 74986783 521139916 99146631 769549203 562020205 639106022 365133721 787902763 731592391 347006955 469167084 209656303 175112752 377490696 414372311 477679190 102293356 364807893 608861669 803280848 61024671 222595845 358231617 914113176 213532897 308022549 859384512 625900870 545089263 320622142 866542592 718878518 819768905 233336747 503036613 381515810 37831093 932633625 617851714 259540507 85895515 645636124 209943172 527105698 480175078 654105091 899702987 509827616 152128884 663594429 102595453 238101514 909658475 494466849 95267718 826729097 313399264 877216322 738001106 901720527 385420327 174041445 399581562 494654207 639032433 255438078 743792185 892755913 944266447 803431344 428736973 72872328 79098538 566147878 416152977 662934449 760086297 644168244 588282428 656689909 680622749 354116517 816054501 315248659 954492673 311918150 379646395 293631454 867879205 744123983 48738985 110784818 156870596 21169946 650977672 541286786 925771230 427998851 753178164 167877051 484930842 680914217 809211040 488681809 677840100 624147110 109568408 297615133 243272493 294535196 838657632 436807718 843602145 449505667 639886805 410024121 619150220 180471387 690104222 525193949 571694959 313624027 400739522 194642321 324227163 737988378 248830815 723762206 794732085 982314007 350491011 172288029 986654948 887644114 291013261 140780190 661963887 220811194 756966788 786746502 722039322 198447798 634753565 928995341 886412187 626108971 411641190 610924290 327597827 998004864 523891052 233697937 306618105 687643592 664584526 183759388 651187436 143428737 260585286 808650736 901809563 765793005 87748155 458889685 782548553 407136005 50510957 656970686 178672976 966075489 28651821 782611946 337298074 92362487 722543898 342451804 762489886 32930316 191094487 852665889 27896213 290265607 124397180 893646337 302978823 831690132 285000255 565319266 860752666 975305733 247398002 980848239 924948803 944137442 792089250 947753725 114116802 976354597 349023344 786058709 768539787 232529612 14971381 935471574 284833355 977606429 229390520 903131945 843508927 178770156 851033538 214057096 592438609 225507220 552533213 696973804 153876844 301749822 373201481 626782496 862471141 819527230 346908404 270292082 137730999 631387066 830673112 414835579 720700513 531746657 133216102 277758465 166462359 208383917 94550313 495876722 511953300 476948875 330455014 519974911 810772216 374709199 25753132 833572786 107266588 664523954 246176608 809602387 780062846 481509307 914817001 259043372 222562354 603982714 32899954 662570694 972888412 355878756 383935281 470892302 480249998 714198214 258526731 355590828 370056118 459577891 420533142 399000481 903778111 78888668 708805328 914955932 303336397 531713061 171239192 49610696 463380292 298712590 55660663 546789109 281053112 256463118 293177449 347524370 98202981 230717065 734615632 970278419 897434868 538470775 522220300 484148737 279788821 191584377 609085222 438334680 692744109 879491889 993181310 385794331 339947505 63163280 932754784 92451660 566367401 159744653 473529147 465680263 128722476 956920839 252890938 659931603 126406959 1919304 835444272 764417578 866240825 372545112 395302937 276400658 822723022 526559921 171625098 73140243 201283578 729696579 146718421 328736645 86657047 198692521 539940895 82286427 424988051 697992919 850828440 519673758 814857265 290483560 902920043 607997847 640659936 618764834 638549344 60628320 617311192 100938146 769740716 980180303 345380261 941797867 220249305 431625492 304089842 11072316 804381010 226691598 844560661 62425557 531081133 836954627 619652117 332553205 659631854 545464491 116218740 77168160 893008636 332694664 138238733 132416849 223685630 511173202 61424515 551250840 559366714 941840410 129156208 885245526 178381161 595623043 136919530 68228936 142302370 819341923 128615821 833883260 281609121 206398782 355114617 32034689 949386556 172422785 71755943 616516526 837112373 673176609 228210782 518212646 798572535 215537554 431661394 300746670 801341214 556175714 657848218 648976240 39461606 813034320 332790964 140964592 917651859 828861123 281033594 472098763 947077382 981147013 840083260 216168714 17417757 366745043 908808945 825583288 170127665 408752542 297032943 685270015 888550807 458657451 884427979 60610081 408230606 9725730 973272085 610074598 840995498 235095135 461054183 778478749 980076953 278278673 405755912 166065318 696137712 486991138 580967949 876393904 906946789 705851762 23070001 255820346 213147779 345140688 685374202 559183881 342431330 779751442 859210004 198362004 368853707 147202867 948176540 200240908 82925597 590537069 646149479 200515018 370830731 243282717 677738607 509079254 79605201 245211154 142776116 173849463 658741907 725772231 377627810 483443795 427473459 146347433 839114822 355025653 411800698 593676321 943133365 939029130 281449481 828185812 775313324 700757705 11189415 982628391 226052586 708951657 604553950 55871008 515901538 309346786 406193321 756592134 221213191 950458812 243899297 444560154 445085048 285202293 818109088 360462107 914984752 202417310 460312902 360412392 912885839 10689699 577232457 167483111 773428601 479786282 909244842 110177508 50659183 326880435 337154313 630405087 244185936 986699627 969494464 712086515 744886440 53207719 976753974 60743331 107801939 316758777 105472289 900282514 827919205 920801686 809421111 360422541 922091798 968083077 645206207 325494777 584765856 334583781 465180868 759961971 374408144 858645655 333381658 910423339 990962818 807538110 611187664 307654533 125153264 375131718 376129343 484471793 860208474 385971904 913897619 77491249 684332913 166043604 890799238 358425195 417279980 926731025 956450768 321818618 847208738 331344779 476675492 371222766 41789859 120847666 534236161 592653187 29126593 53024591 636135925 312095417 303248304 409838279 941019516 615693097 961464049 227410582 153859966 826216422 951786677 117343564 952131463 181606832 635701992 853513270 3679347 810099968 929746670 144551136 650885546 832665405 812648439 113386438 961089598 990322661 882270521 414675128 481087237 424459715 831548057 788590904 386648960 900802753 676100265 725031112 171425878 102924054 444323898 469653415 458941454 45031408 183519137 2149974 462143241 893472602 272627868 874437786 264966603 83249441 858551619 959749244 479068501 459445337 484498194 323972184 178958862 840522768 927585609 75559446 318594455 45997486 903293150 751673743 94482661 894796222 468990014 33558862 536127454 108576202 538991635 553609086 567063582 143640159 989321871 921138440 392891555 230508481 552034114 827470857 529344488 4153295 145825322 818391859 273377840 870959013 86349413 83527904 737073209 174805073 379869485 163199362 612144353 953857955 503902878 603681423 417948362 985216454 83137918 118013503 90588295 618350250 648512027 485982947 776663655 895475565 4906832 507623116 984728936 912021868 284283462 977751506 303723178 142037690 181165632 766167533 675609928 11033619 670457689 600871197 625179010 154183832 399119778 314678763 90521286 638910128 369776762 610098240 601967468 4794375 29107369 797391813 964281783 497646861 773349854 772004518 985310145 624910424 444864786 643201679 599537131 82092185 642744020 215692878 267436382 470845771 126404128 35873444 589948417 751567021 496705463 582478237 300822350 819697671 193921391 224593679 260762384 124743495 68687482 2609373 882070123 492081910 643962222 459277922 242175548 752166366 607675864 236723321 690460591 117520007 161697133 13614420 831335471 536205820 673462059 186403561 891093496 867480587 726255383 772104480 49008560 438116214 988563330 502012098 409784775 115094181 271731703 804519876 695633856 986546468 362920800 719805666 187280025 536503227 353544584 668583214 44514770 318313357 302476580 45536409 257734361 489834742 973102135 960215022 810915270 969376192 408353917 383070914 468609833 77230556 257376840 360793221 890862502 915024194 396508755 95114460 822235314 428396483 302591834 717242765 339413817 345828906 420339272 217363384 289295524 886784755 474532775 223311546 317938021 691080537 731163194 328894767 911175261 113685794 779568970 164197966 728603187 856561701 532980825 971775520 161226695 344720113 953827233 550116193 991900175 235390074 465322162 278475113 430070010 706472449 731321772 427250417 659248263 90086286 773038958 560210468 622007440 664845057 463156265 536503526 234437205 899778587 223812175 66672156 367353632 228843953 893966158 573348512 923665395 881513962 257245078 278804203 794348959 634420007 986787204 261391346 702891296 71329876 301483424 874406183 596860510 951657897 62694883 742157936 203259301 198374081 629391409 776329998 919472069 739970240 301772068 138853917 532878151 197658212 71721149 385887255 848209310 661799871 864380965 483729747 7574071 363810737 515412108 763831910 444777401 977614015 431547926 735395321 761779018 932460661 597219923 968363885 222253571 31876163 42756055 909417642 478148127 176131214 915014908 672646369 788992061 89344111 589252277 813272493 45495059 894213792 433310381 969654303 338773589 627170590 959484676 529861966 105746527 354887801 286500740 562287596 468507020 338810855 375551977 581077380 737608017 18229229 719152029 891165974 444861167 158145754 527916106 529321665 819203475 583805847 232510947 768329042 778853249 854664286 405106912 159092481 591130313 216247205 759684828 903591882 453061988 307827816 361048216 396524510 605405813 127473658 696439782 211026266 269816533 368267341 802329165 284794245 584635107 862181540 768256810 141141623 133141449 294284658 185666386 492971154 738264357 424568103 8816853 52441480 12566745 963401254 239369745 544936532 2849561 145288982 634744245 673368978 469107526 723048518 763341310 48023223 53459183 914749960 216306825 565524064 744856274 807716391 655796947 750422089 875945549 459969987 474975771 355908703 804900352 72725713 222020863 894287892 793643157 468081328 589329470 674051444 735431824 500983379 711511399 519573756 782359556 565409654 505341212 444812997 889720228 913912800 563863863 208424342 992046455 746471806 883771349 154609485 210571867 417030061 926762458 665150810 512224905 47329114 652714156 849658546 757864030 10150364 688051421 456415613 973309085 778012117 902071000 610412075 491509403 909165434 60955375 883389928 857211325 521894542 989363898 388697215 438373769 330219742 249062411 584048764 765819905 896429134 298359084 811430710 910095374 745300428 252908701 865217166 672295169 814191420 848768626 35889111 986472787 269162989 617311748 568237174 592708059 290156764 464369324 803548582 510588253 375054062 3175006 544230105 384962191 159463976 866835631 136468694 691818895 74241559 295368773 787055515 22593095 476173579 117453448 442367506 771693705 174341881 400348644 644934978 185518717 859139935 485582128 91670149 327475166 368122671 224371515 769742243 420690147 840177341 379230569 622771005 82978648 522498085 516369567 774723528 612879299 799145153 506844996 969660002 367902342 411586209 230364772 66591193 983386089 352513582 161351247 613664192 490647110 108349726 626356059 934773047 911882094 615875745 929884874 470619564 416714842 702649655 160711799 952245891 613735763 7766451 526842502 103540860 209625210 406366251 20229482 580072476 170699450 893407473 38856900 756773934 51439345 800897201 788975488 516183977 407447807 557303710 780255720 747698742 759953364 693582276 106560267 764473476 273751151 743333093 994870315 878301154 863041545 248915291 832546221 653887497 778887379 416616829 780685631 314025029 927534598 171173011 104221576 131585274 98324519 310449069 215060365 687559837 104852631 764339969 961064422 769177011 639713737 609158825 696553498 453500517 855726275 840378933 788411647 144264589 989404883 730125610 261560071 469550249 774519664 982522807 730997391 241424339 550897253 272750570 388614912 498627038 685886972 182802921 818842598 706530779 923995135 412412174 437640717 811465307 291399709 354363120 127940135 290713777 572391537 272846908 452798300 161090159 957239027 383639834 198244352 602389606 561261823 589007696 539087393 844655286 3196365 702153422 469824412 631243832 317134996 171315990 504689958 19671910 791825375 845608981 983581690 712587399 607014361 771133555 926477527 732329663 587607052 886114921 453798601 578404095 18908011 461759976 41634422 286260137 902905681 805280348 966586335 528343672 483142695 23580338 689704625 778907560 769563199 420706117 204905519 303822444 710011647 285276804 634294321 896761534 512028108 457524262 964038131 487587914 945952549 818533456 665325167 841548455 549400843 83253574 382588600 308835540 880874741 470230448 642621021 941766251 556726315 376489225 266822809 924360576 258934169 937911912 992934457 823661811 947826974 940488762 913584665 834555780 230683019 760755022 386497690 211099543 213985947 455528363 330568749 793887872 235453505 956027493 460055092 843853331 53781072 697931681 933935127 184149329 572688548 803642572 48004343 181278548 226680371 598773186 37468911 511509311 976160248 728284034 746473040 167235531 237807327 287852372 863890476 67930090 878277397 709200047 862050228 704233978 54371722 463546507 819057097 527218210 248555006 611576245 775311890 348713808 222189297 56761780 904623293 622120511 800005577 580374343 552781916 781898073 268217651 153585994 928291856 697594062 182429103 536220459 249816400 977171642 967200536 166027737 864548251 114072372 182806766 739800363 810961000 374304220 942888628 475484580 259626831 740777822 337845582 508700762 234596593 961716068 981603034 585329379 333638878 157512296 874455871 709644470 877611145 135109847 684271648 680356711 484569891 729023052 348732353 997266487 717035449 801561625 241236355 13507631 756241060 206131030 720961841 19173709 298024226 755094210 297741631 142576892 285197534 219138450 767245766 185143755 630122101 423752849 226354544 86705928 120245986 343494550 801994442 964680661 847812755 351951129 895037553 7999783 545959064 837534370 30402498 932812390 169401278 584867822 763265291 901939406 722042744 885634517 407465089 475822179 578826766 183455624 977735873 134492217 474837873 166753267 529112998 67675425 390415575 703262314 340511855 655903704 327615460 843930742 384281362 269574148 461603433 745638911 345333592 50443851 518085720 387563474 774133636 427513020 250378779 8314316 85734980 815893689 585898498 549362343 777572112 371174282 111591212 823799856 699532585 749331594 394172753 893283579 192711079 841584204 108991829 770648785 719051485 904991106 25167812 491715335 942574873 617983464 424340044 14202532 311915032 834929270 844861397 765775139 937341224 998159093 88406781 602543620 982110731 592309205 534306166 531034026 601738316 737202948 291889156 483695924 309266559 171557999 835585854 512541318 716506307 437463571 188439791 93841494 824388483 395878417 771723099 775958471 653529555 928863651 325311828 743630678 406213613 231809076 690079578 168539477 297274186 392974995 741979586 57042541 261413248 88418534 38919337 614417434 881333790 670156227 664492296 171561173 771483779 836973132 257295365 505452171 730472480 952569465 351061827 217523730 924659613 516016291 951220605 621245269 706811086 950591272 669546485 981874760 560810065 614698033 783685949 519984097 649076683 851964792 39101746 692834950 64700178 820741707 877699505 388046241 195181860 593478104 129101043 34770972 359577554 467402082 555006545 739857090 449468808 487186640 153573938 60366397 858156637 666295898 459298619 276276989 339300514 252658801 278748730 274136709 245256512 680714928 559177765 632206280 991832262 210746534 96997406 240838609 671146895 370782153 686205175 642128158 409380442 279188085 580737991 404885270 79504649 232702240 29941061 659822124 5098092 369918139 118197830 129752941 228718826 573275206 276564297 250251551 141387893 642153677 498431912 115800230 662622989 119424905 491718237 939483246 689180387 170644440 884678293 281178511 44275975 31065961 408855701 437910930 481261804 451803556 860463074 644248636 108464173 436476392 36677127 24890101 336602163 103647358 342282256 817382542 622261821 9972601 48798192 903045796 907311633 697156525 970867912 405099380 368307024 738232677 601752799 480675973 778545878 745662274 318218039 970697963 587824369 469181336 958761683 42480112 536248765 677563658 995019818 715896188 165548944 438329181 391943832 557063242 730408944 950435950 728249620 964377104 698235304 529188625 649056056 566115454 355995552 786769299 448013601 288358931 558417794 192887311 337124920 657030444 474611986 618097627 455144799 27814829 821407472 804920623 467572641 465116574 557851746 406801457 776256689 674711063 495520521 639843604 580797994 757655137 256290218 82384366 648494478 874603607 180928409 498638225 722150639 265710086 662758082 820391815 380426252 995745452 62457885 733148477 836042389 814080651 749946840 769006547 739730418 525159247 290946244 941564034 759061645 186414149 4996354 23633112 274897750 305299634 357911072 675619123 618647089 250663052 311956030 309746858 372528630 791532683 657535853 570319466 982803400 921502357 900774657 980855775 916536192 964344956 663458711 649464677 790028715 920814392 715034077 880027823 780871651 823135464 906831525 990163190 19806765 589592367 152189946 753499276 709253398 19297216 442332819 654718009 199455087 635807167 426399073 974629642 167083153 506355810 644388490 328084132 354360297 977820826 399996435 914529167 771316004 431619569 865529363 128491839 639944329 823976252 804458724 315879910 119125279 417103572 43895852 355375813 693468283 581417212 420499964 757860871 220746329 751770240 8704337 863960344 497628449 861386602 576932718 442117534 748530086 52026872 875670931 881693834 643162037 346443081 391036084 572129669 77463531 36136076 347100596 463639999 524921899 840523688 574696654 744940570 807752641 699948166 839831565 576280434 415452318 893348946 113437140 887506163 391829775 533100117 473650244 19296885 946035585 141529127 993389640 33270560 805022309 119791781 356303584 121570660 808818158 334254781 656996953 826964593 981632657 607721921 817524298 43202816 444358275 192070678 77327070 145562581 908377150 42471252 286792485 666179178 511068419 217442770 884451865 370507689 773833730 780524988 12248651 989292243 688546714 646084948 23088077 955548954 309708950 449664668 528008993 262502102 100788164 640079990 855053156 389685922 498100866 748928343 324763999 204147164 2190237 418929387 219101947 195757245 249963691 644186873 451997717 688150599 305938439 239766149 457138171 640566554 215433727 958138988