3232 2870 93660610 810849882 224497797 871841796 534109557 754132253 835020599 722416535 729204986 948717427 598589404 673289015 383017081 759456958 641209258 648388557 17954412 633607614 907986797 346196676 833712179 344429544 281904754 809327570 109367513 796397252 200350416 996369182 522307372 154811343 39586780 37153233 931240087 956903031 462520234 175486211 99711852 538848264 633132590 629608406 515765911 779914386 684264449 337438386 561170711 869467994 581092410 340022904 963363786 777567112 916157750 744254960 531067988 579395558 231466801 583644582 67006663 41606892 492513105 739445518 167719963 256980706 403547854 691931306 856383490 931723302 734690441 419940507 441239248 416915054 633947374 669504220 367247000 50474146 319117448 765192896 513478180 792842182 129777883 55700000 225198729 16706784 824403865 546212668 10991231 665674087 664425907 927482318 795022698 340813215 363225074 824937120 307975318 704025059 181350662 765558646 783238608 885014156 609032707 165990538 525670413 952840671 199131511 433335300 520435347 383104762 939704510 903683978 119857102 826129042 463329062 813731091 885399566 759282325 1944496 544111009 292738895 326990905 993042009 608426002 961636789 515020486 976444176 706189823 275011494 838611084 374430361 665073859 245337440 166592952 342804836 16717833 946549763 718070446 270389016 230796173 873893508 564978877 388123764 307605841 77061367 198531802 308966952 274406884 161115862 120762683 266525569 850617018 504242633 551686201 198917174 536962077 374663507 669480641 443816733 321067611 564104537 757576383 610134552 284837250 550062758 617226522 330098267 71805236 445589799 961495810 367274266 812489110 864839647 263103633 49172964 115884566 371933359 46274788 936373637 526726673 465161732 841641618 44874437 666911799 157336753 741179122 379536898 938739094 253282406 827783238 520564502 760565547 687214900 426972235 478733843 471739447 611167331 41555785 929916204 302543427 414120791 682520804 201499579 784864121 78514673 331613592 163263631 715585232 148957356 311935423 506631167 985223029 407711890 210013096 249821449 920952790 792426437 184251622 76970190 255416019 704139525 633074131 795569226 181307842 997968699 539496574 171850885 92813462 71435337 777691182 905009295 458253356 359520633 717817207 640844638 33512334 847531066 985902221 394435877 105361751 595214363 795131672 604803101 670167268 417020553 852189210 100264521 692980609 152095113 271460321 950298496 155621769 852604767 78134982 12099695 854664952 517762219 193957928 137696037 783545340 990968763 405116643 177060255 538044705 680881977 369306202 645465298 994517862 65451306 32689089 298294594 369026180 100884547 803704742 987685663 616126912 567239671 547578008 200615104 802823628 797141498 68491329 861572255 200610178 813905355 502167894 227290472 379270855 975932290 872670213 464512377 540279944 487257963 581318253 586920053 926424748 859177110 817296276 13094489 498454554 204274091 110086118 802459091 98781187 260730685 876497628 592161667 476750495 333167709 955047955 418744926 815036750 672794827 14165451 297542650 573497930 104591654 320995130 96681145 161722925 484985555 912915854 497646990 936632769 165572866 475866658 725133561 53666498 183955589 509563060 678775174 472194042 813237855 286483460 304645421 928088997 144779454 355007815 255017584 194411497 445854000 27135147 323587163 753058812 940185845 840235918 138122577 516946280 630357098 988013166 834311754 799642013 266336785 570167800 710483491 576107456 759486098 925739821 330518673 651155212 877744237 728125903 668859222 245262120 955349160 320688054 958876826 355778989 255799357 599856825 725516117 543840964 806997665 51320745 178288270 411647676 229397107 613285389 787386837 183662985 713711356 587515673 536553363 786240788 659064957 169602421 761309617 322728109 555528479 259162727 937147815 85781964 306335007 123196230 41972818 420478044 6077033 535987959 649427048 153630983 735380555 222683819 873908400 47497385 592193716 993409555 995035636 902593017 841160762 431102801 976165067 885331356 998139516 256961584 220571748 814409610 809637687 958439987 363295370 950944228 511262601 745339904 714769050 800114876 399447201 312441592 602041133 73467624 237315830 546569624 402584042 129123594 409891770 538195761 497810140 208852260 112653294 345039271 521712714 722511145 418547114 173064948 442170244 396460774 163882417 441919516 688452559 918819553 923084605 6600719 734977016 318384770 814939555 895137350 158208946 709393367 909801671 234801656 931577362 449191086 292241692 510204249 521443190 991238153 853375525 157467175 921557406 856954949 884760596 846321336 609255358 832735830 136398736 646267071 293195930 264501051 32453720 555842690 838676702 169592494 676493502 659566501 202941425 496700285 49661391 964578599 885712457 953318455 527003385 590687915 16953297 200111754 713809584 721978664 590747001 210571556 803016006 139779860 936157460 409585003 78840232 503257389 581761517 85894442 218106097 869338928 605092601 188774423 710638350 986824004 611328797 829349910 565442148 415908107 612626227 666014442 307508151 987946064 397956843 67004213 413867476 395977934 200198119 893377867 882996987 227492006 590353058 309990099 736013531 498806388 188591245 855865293 585656590 536014227 79191147 943690558 48676242 681851546 271725012 657769026 929531557 716179897 188902342 22403512 209212682 287755699 895789686 695639465 731639870 31460047 948505000 93823318 12970433 36940209 732225967 296082876 505951348 227687108 67843569 110417405 1507233 479078432 824162513 458440034 651595797 63511359 952639825 962119706 804473528 307278907 769899725 931430068 519809896 673214704 397313103 928985604 50486860 796976396 516994956 369383357 133057850 417425027 773317963 414136610 489822052 595492539 290449354 375262465 129210294 848041739 966153538 688192800 822841968 677502548 930070891 347421189 374635757 702296045 308786533 818199327 3388715 664217224 559426446 461539701 966125162 246292270 523164231 126527357 859936288 532472270 424727854 420926461 71367634 546827797 723003572 462320598 305399018 176502786 965511838 475665639 195158214 513226987 385628779 828935954 324336554 437752576 401270872 458486592 626875869 96920705 135751128 239068268 948519976 337833597 767769696 175176658 434375090 979596844 666778293 824623755 527812225 24450011 709042872 39628043 192790837 627442222 128030316 878553578 172394845 11693146 849713817 427742668 683871904 358121507 964141884 375710672 17476845 402717119 562160306 505252102 52071883 342019691 545248666 359477131 63608272 924271457 55240736 829870086 376118537 755964813 97729392 9401456 543581313 744020585 235890699 338237828 159598570 213147519 290886508 306435879 631126630 266353324 485462500 619578794 564438136 154880862 100800056 429054034 965414478 463784635 30684366 230006507 8751901 149706922 381868048 619956986 752549871 899348988 750143594 852532636 71005053 619468379 192335685 637258974 558190167 546980440 40784153 38350878 777174790 166951189 113897684 707312698 942088685 124761922 510360134 645209569 414884620 793511448 587030240 139274574 826010993 423472714 944815811 133275039 885338726 147451321 862373293 119438144 758338344 870254166 771622882 651347296 203299389 47360469 624660340 247188976 811273642 260833132 248838219 538546531 176031277 875370808 450761466 493002604 550204449 302962802 791209668 787044871 427513956 735910427 347795992 966871570 104089043 589648281 617934452 297597835 609617553 271239761 176431138 284793807 750073897 330617727 144987699 501356341 9393270 463316074 250805158 755684726 438562241 789504700 717378870 126551545 201277263 940283454 209778587 544401838 691568852 193773645 574115604 894604489 69571683 143121451 271496941 539793577 296078698 106637514 544267047 188157285 66301624 121399383 715278919 661054256 336070409 639218426 225969083 939250526 51258371 524925091 701426260 48282605 565625046 922878026 317671760 274785050 237254517 52564668 918001567 48317732 490632859 758659676 783682254 966048041 918298282 403804934 80234346 814074510 390575528 557960288 814612323 380024655 787363207 426979819 520738045 724237320 409050067 403979467 279079690 117108630 861507625 572782983 501592022 752174430 75202574 260738640 367029106 593853122 139188824 546911971 928424231 811760649 655274846 562512496 213241875 619738708 828771165 85337697 433470911 586512293 310782436 703008459 175719627 937076915 517908263 251233174 13950661 695783762 615035794 107278728 117249883 354209734 671909115 940976940 244743016 679634293 570774271 497265537 262877174 510666143 411804989 724707664 337750572 629357533 533328365 864525208 700877844 848445780 321831885 544166652 217095474 602121878 333672811 68890922 198720497 760535255 163685047 177585015 352044131 876258162 777334772 352765414 66981599 398267397 812332453 858649707 826244988 668406741 162903074 311650099 367811034 961490122 319292263 263155660 136913854 691713948 936054059 215722614 850249664 217791904 484319667 27824743 24340768 970260312 779933855 854475104 478363468 603663654 786356774 749210831 34914934 249429119 399562900 132423868 782305079 368922874 635495166 458746038 742095857 207337387 525891731 30301427 808738151 329407403 892516619 33879792 671206360 644692097 738955750 463859608 537085488 286499130 445046089 623774171 634211730 464410175 349000151 201457951 323685794 298616196 301872190 634704123 341419374 480008466 53823992 261367755 446692000 188083812 158003336 964591224 403045131 489431605 502673631 720897736 435236042 652477435 253990669 134771508 285742300 176128279 211989810 430161511 808789138 586847388 859114903 692195172 653966461 522431598 153574649 775644803 464594033 849756821 189290026 617254499 192973974 811629373 601567805 911048640 467819045 780786417 342322683 955553666 475277828 261040955 243714372 460413048 158714564 659321853 143548285 971512010 222924876 703185205 633468428 602905565 905596762 886740378 608848193 402503462 764233441 341462108 504671757 662924894 777262408 35478711 565306470 698444008 654210746 897946988 37887188 288589397 140618024 548324800 421063047 822114130 120925192 685235670 52105582 420313452 219411987 489865197 761218249 88873752 85838919 938286461 273122556 198494337 878407484 801028905 540295954 984741989 346033317 876823855 28627416 868859513 217352366 819891769 983927476 180827378 759597875 724257576 599731794 975934906 252115792 352160750 750782985 60589709 829127268 967371025 660065600 653949989 370896825 842447050 764091085 753118903 759605176 347424064 799025573 841474372 437515249 615748679 19845611 743090007 69383510 300440413 57046395 391294360 952465525 18295940 58323225 637997125 787981926 338613024 405357500 214820430 942166066 589979968 41082722 652094101 36091118 6079545 604281260 383336393 444048144 961661582 674745292 514370477 512274695 96886931 599306400 97828657 365650553 679903168 421369403 816617840 287970957 854740684 609326878 888787026 734124183 259966310 104173363 65355852 345424290 419617546 674372950 723646127 573174468 217924842 912311957 980210260 156684837 78907423 100263235 484193534 412388941 312274466 935409998 322418488 555108128 808219573 97999984 591068156 143578075 707184622 639955259 974463685 726106303 611152061 118481846 176080993 686209428 56907516 717131043 732523702 789574234 621815054 492341101 604448588 917872192 574053986 292589744 970625058 71368345 490748813 17569146 828976487 935633782 278861344 241497846 167715813 55726111 533395754 936339735 115915734 847480185 743488561 902149434 70484790 466971126 761146891 773525472 590920005 782382919 581240701 164514594 467846026 165220100 560900225 104279341 114807437 48738439 862326991 28514187 997538174 971421203 658523751 543101621 819662469 124620503 839216639 740382702 538613548 387905466 457832498 536610665 534814131 301132822 96222178 100432908 52742146 418912361 722853370 120231709 528060944 82997486 554138064 818579754 281340704 98958864 392094734 576733228 189513821 26191581 478403980 172435915 379789626 146716354 351787163 94898422 480203406 250485973 42756855 744432333 582048013 507686881 37903410 477174194 551333022 623002567 751603914 146909632 34437401 681604836 122264273 835428883 618856249 206640879 105770367 675709548 139221684 504608544 738988143 734455607 837727004 766654513 37910451 810897701 695832144 921296223 115550894 46612699 137768724 566090114 883651771 281073996 548711613 644390262 568337864 13871648 292025947 223546772 534531588 782744237 546919470 327462245 900553432 737111021 673046551 701349569 56521896 372395708 928784837 415451220 791661472 711491002 430515598 631916027 386716629 14306043 517375137 127416514 357154949 131401122 684387982 658642199 136557955 204697860 248632049 914075142 46434023 204432893 3347908 364330327 178890690 330393401 645728156 852852011 427740042 457114978 310473439 303884469 106919854 296068998 76217663 415192129 232310099 767027931 694936360 333079652 61825971 721629703 883173517 169809839 318466180 739411642 715494284 646471058 326980837 933166691 620204891 574037985 248701744 16025538 584831461 81371621 442570639 13790759 239625352 549328925 63377300 389481809 683165226 543235447 494893249 62233843 475803678 7835196 615352429 312074643 239735293 412143643 161423574 724429522 442462734 982006135 371486669 66942893 501453567 379762919 153195298 891172522 514504604 59507971 720031311 429096104 152855385 626988648 805427809 950708493 668797123 942268859 927603791 315422825 941392665 852545854 283090457 803410546 780886986 531682196 224676222 563883235 435166366 810521935 334670898 313214991 433750578 525815896 694966384 397474372 54115590 719760292 101798367 844767671 367632126 32344385 245592729 16165838 733233565 208861605 841773579 625887497 191199068 563683261 738377562 726855028 960698072 283515054 819461634 777172179 496814798 622541123 126622560 59217768 424327479 497498644 385648073 40509317 540534822 968870226 867956808 207258586 56505021 17486268 514541083 319150496 737154005 337408337 683247349 155274550 178124695 714279217 766120768 190366121 560086014 6710974 460253883 315863983 367465761 544604729 995624424 170941318 111218327 84131330 785668780 147054724 83041071 422727495 630251409 256138039 123145113 399957095 427942582 671286992 285238745 819653090 722831473 586776526 131964976 180066410 788092962 26295751 214427433 938740707 251814619 777646697 892799927 391132106 540774572 876502143 795922453 787011643 500129091 382309990 371263250 597451973 927758634 307141636 487051489 764585539 452636234 304644751 567049114 31572640 784213643 228549967 902985285 582760863 532555707 127260511 303759384 507419839 224150509 279551007 386321390 448479102 247100923 106847870 170844085 68017152 266295602 379247251 247324571 579804901 910366840 340291350 543791376 269761329 137356462 84438487 917086159 911863609 679807815 978578996 642179437 831087545 714900680 591706935 337049078 439531921 931134353 454940615 266565136 921521931 280894486 90558561 342681862 817034974 716568176 383277377 952192299 561152597 467852722 49826157 122709058 997402648 218614517 979949724 200922790 803560835 749308386 811669569 654888551 381635743 818121726 574682742 260130240 550947995 407320660 379590886 888733452 476815802 432950420 376430468 911462095 759377891 649323784 597959666 124202487 878495793 193803918 825318393 422483864 186835319 72818098 876784088 652191038 239309798 98805975 504943850 123540541 302582674 341738320 389527875 402582291 225773489 983649076 254893046 918136655 860976349 918787105 308005624 662577732 507177628 519329483 571383040 606104094 812439487 163932714 200623846 55073996 287954617 552626995 25338695 870622153 130417161 434635209 979797381 104967702 854978100 800960820 498233150 370350740 683490509 21095458 961124862 349500922 240661264 818108540 74824340 402718709 168624442 387169892 749432651 253907743 585390942 890598475 976440999 61668966 762824077 903592765 255659037 956965227 822378815 828499789 257515012 176756424 637712463 552214140 70136679 279129897 759316176 115496864 271454890 217354842 429476865 62198313 264167996 799911272 683736065 426423248 513390226 299163942 226364944 255070168 402930149 385495156 874846887 92592765 292789276 758452664 291501844 22917796 776838648 162575139 119159486 501912735 958784855 170832196 97479702 624449988 165269115 582452480 929836823 100360846 974002779 223171694 187569680 711780989 771748736 264913882 116213503 719285431 682161626 505668633 572295361 57204077 100834196 363165337 332680594 228071702 269487066 867526731 941443015 989224580 431319500 732354625 236976366 269533767 694922483 745403179 837540740 614732778 862792303 665996064 208777308 749052915 182285329 134870105 934314648 597832894 192649053 876566214 431823570 501062762 716631680 568723038 193989967 74769667 807376209 166886083 320073489 223885117 57465660 573185701 767270819 596042649 370968995 296161275 733840368 19896416 659344056 645484167 543382578 128983480 792488245 445757910 550258941 445195724 224176583 408569351 381244765 974454421 299039529 129240319 53355858 898007604 796471950 157433102 806651171 114174536 786369647 960277613 130812758 740968260 449733156 270707786 87560494 246951188 455840433 725042923 76158662 713699054 342669543 471240676 467749637 671384421 989238599 774397180 925233426 767744572 699335461 624720983 257178965 52889868 564241818 848486320 487453462 617238166 25787811 80023457 19656563 168834518 695805804 834741196 614333209 74651169 449282988 989462574 911648097 669184766 853364467 804869236 106808924 587394160 168700360 928781515 129284765 15011179 841877046 839867908 29018547 738180716 339765981 377106714 51357236 844111395 912408529 801985663 620300732 749339667 626918610 797781620 513703837 576663737 237986796 607170948 377013887 726223776 344458790 617660518 356824704 738143796 708098977 863982027 258993418 792153841 490274366 107333950 980403580 243605595 174074965 759905294 435440604 410394193 735843439 135550375 190984158 270311736 110125612 982503219 412347700 852769419 716334342 116810431 565339036 858985962 152379863 445268694 759910620 299382180 327115737 396205869 964751742 62589206 969363239 813687198 261765503 151367836 308812974 607374224 861493278 936377172 229945989 439893166 262348061 643398682 831592484 340597932 788196808 408109696 964687769 752123890 738914072 545213219 160826679 57855322 850899793 414877829 774879752 186888911 629148879 482733726 798422010 938462079 236589295 360321725 161447672 720719794 86561106 31266719 460784851 372896485 380134386 413783385 559309798 604290398 463511768 616501760 651985710 36873922 726045222 134183467 536254437 917341661 927712565 912020542 501875790 764158580 137828333 58772746 893433572 961965018 405283067 381063777 980767784 200625088 599453360 271139558 98846403 198796973 441917052 640620973 515123100 952909334 86533310 573489372 179409994 670310743 636647314 787592992 269426407 406529635 956077171 776941402 507600042 845407306 229011862 444543452 635661931 825293582 302700204 972837146 917923050 183092658 926927111 285321438 520664609 112743699 610862647 745801355 360067626 548244416 59907731 358328232 435651118 794358767 382708900 195248739 688158093 930370874 681323024 648846129 243036898 701213677 835831234 530307679 812810757 883394868 99990153 794522796 114975084 683940122 33996586 394931174 610104542 30899430 826954929 549414372 35360125 322381690 947747810 958273846 303517862 158183136 411586269 602043350 739870511 646511712 870796774 653550380 387389856 27661018 214702148 24955557 804074762 620976062 101546959 345592825 775852061 27235475 822793166 14758885 544479286 102271912 387981562 549796858 521626821 720634367 963348449 977766915 465690723 103413098 627576118 343172125 120457759 969592586 715693366 669381685 729870668 568428208 477455256 290658516 167720753 85618140 434508811 7345118 300483481 155612991 287860214 177111957 101506857 465041186 790792178 383043974 464257680 686103021 535050640 228236600 817933540 621505549 132401447 303002522 751403294 28151071 747265602 330176388 530639062 852338728 271088077 361264873 494860210 139002455 398108808 74245832 418726698 547056895 363414338 776661258 330592843 266728935 450078260 171880248 469051514 573789072 90024767 160973815 218662535 743303784 410440462 531752965 387924088 843840676 131579093 457591662 909127373 426745403 885084227 413578377 412290838 595206487 944414382 717019854 4181623 762491670 419755584 565704504 85115543 423262026 880877383 289649605 855811728 188594476 587545961 325194252 32312420 773479328 936835655 513709952 659277302 712331432 307686892 560990958 87386974 187206921 558826571 213818189 254003253 925912503 983343224 840449104 450584939 723758871 905620396 748988147 256352967 603614257 413048741 68395397 259216684 396102827 517777949 972350228 679249607 656248861 810028025 923593715 749613412 171463552 982871040 739498667 432061035 278143924 577296509 139554172 106364486 542531812 325327118 324895808 342172447 179159059 315301818 365306923 947984141 869298765 317208370 174304833 273790530 986141657 207715679 764278689 754318305 718973744 591718120 914502859 492692106 491730597 710569140 614066046 92152741 857050411 735158575 170953166 902237095 421635693 1711252 613237328 879687060 593936641 165778037 746304645 454581856 380312409 716862196 550816818 760351367 537804141 525296356 605871856 101263781 810934189 229050734 471911604 565301599 976748311 8785777 312610725 803516620 35644015 593179169 802405723 219201844 562320435 585369492 624076160 449391931 972414511 391089405 427708456 977305459 20795055 615219806 667147082 360165088 642697694 491482840 752704466 901952191 5929580 248973027 887523332 940026165 549401900 746569814 658847094 184939681 615646673 996904202 359867427 120989851 683502832 82186896 515461748 482389873 624555298 8362867 268460112 311138664 233693469 500995174 688133997 426607916 43848734 263122999 336219166 212403852 131182828 319843015 12060948 186921687 956531418 639024095 236501297 536471135 928199536 523971246 59808018 28704841 493402078 962900239 448690437 360966834 257480182 443634197 179047042 684996970 427404185 60235591 581596775 694391971 459016232 164730993 471437806 406595825 412688102 611920526 329000621 668294010 614322933 410408726 973297672 735047671 673910624 865547372 43077464 738842547 990861280 629675149 867268181 950801794 723128287 672186343 437073009 413835788 498206547 924959096 994773628 598556234 90818460 962603307 237650132 638798288 716322593 499239538 564570549 113326974 518964349 334790699 898604851 828282872 884051039 259728608 606063638 542351552 49861282 709724394 124370126 329836125 116690282 210410070 335476257 167517334 972694085 585379682 450066 3934861 930237092 343908891 234527001 565993004 221764367 665386322 777453115 754261742 120006768 538732729 998571663 246088499 299418741 707841947 2508288 390917451 862176537 520323502 370712764 518078386 594125091 12696588 863335979 975686498 634846726 162940808 694385687 713244725 399798659 835515250 202936037 974529336 622983377 628063139 80129608 138475639 596576707 556368427 754311414 810390136 402033272 770559608 630864531 685023895 651055992 846153108 674530166 761509644 450061406 829460540 578341680 469063132 659105880 688151859 414022435 254112920 256265937 420499485 512273434 499614161 123084211 78758113 365872159 17880997 674495470 453021474 423233616 872591016 989062324 61997140 881950008 375929484 587279002 786632473 400155166 309262297 75626472 327646221 252502567 627907824 272487493 399182534 27597415 186142987 540691180 665970529 330988273 768402336 343671109 695027287 569759269 500602882 735350967 682946157 788782640 636532964 398823043 492149789 118546600 23705203 635916634 915501664 599501514 261667946 201675776 400782517 608431039 174252056 769213586 603333073 282948912 477615748 769724174 908564955 616770526 236211421 762632099 361026732 749520127 668721628 291468843 220324667 886806160 371243119 219549211 550016982 431248975 383018626 841046554 834649382 344873044 66030608 751595525 795083461 124274004 978162785 327935502 986362736 577417840 470891843 117433896 915528771 982605976 383022735 144270834 322248735 515352391 559188611 547393456 7184802 209040435 18720733 154223320 168465883 824396187 816104074 68428826 233829446 627351966 738023685 890588397 530140416 32823561 798569828 18034421 787117820 254763867 221235613 157339372 665214365 361008679 276474517 378550621 333434647 676187163 984107779 533822204 216816453 553490130 436876757 139195988 947383022 253635655 535066144 752664031 521411210 985637603 617177070 785355393 611197905 406169901 920472190 272933899 753601277 673605449 238470504 62367521 648853440 196952423 585335064 90795945 111015707 409915390 305348594 296376001 326733853 996190521 529472026 633939367 412757190 334949348 104503127 589780764 268922660 904762429 206595899 5475036 960181838 989183056 404155157 56684152 463631451 344602446 643575316 996280154 846976605 381463694 358406348 676000587 693480000 555669906 974658920 895040024 619335654 8014057 343969738 391569530 47630363 117376341 73770718 800484281 66806395 137293121 200545378 54436032 90482364 436934784 387121803 488998290 247628449 951036069 946587988 290292421 324280298 913043147 619282236 447624743 628279437 684288284 872311995 592147885 664807938 173410821 517357382 507991716 428761061 447216241 89620361 87295988 623677836 791206715 332004619 484880768 718182937 469286724 386784086 603136392 909004742 182290442 398390957 305308757 993334378 406790 742585107 536208468 668109097 538050039 335880988 844029591 112026264 334007545 353999424 33674529 945183062 882242781 422794733 738075139 394066002 116971129 187656253 735417799 902215704 191593733 953556749 733501555 656154260 470793317 626671467 105388406 970051714 582796229 142829194 85596114 981397362 777795731 518108356 712985566 189837638 591605347 139356482 201361436 79010924 849264681 949979606 888624135 858335015 281483903 252774541 838329851 701206469 598458602 861073433 413113769 935415452 185025173 267243449 339401876 825439888 848922743 574442284 711991976 855931130 642937017 829195485 651990321 611091676 362197593 190828944 769131286 882402832 716912186 612970988 994774781 312618910 317847788 195965369 279107982 88729082 746402610 67303111 410588787 911006678 105492129 336794806 411501804 579283128 465706691 877194878 300996635 566436214 199393327 524259263 248604088 771559701 532409490 626986879 285566046 653535004 522983690 115329462 804289212 323030239 168824507 876335138 460545513 542627361 25614197 73013423 10282785 927197513 286147470 609936355 240665130 984890438 718050378 821578652 192577544 86962677 485035787 998677366 223364192 640412494 472614351 300453217 633768556 423119278 89945149 487739270 198086986 291512730 178018165 768437367 997278948 630072433 404615372 994780898 129291329 388551730 479666 590331373 487240476 87050028 751269422 640865018 77837931 649992482 406116954 714755709 453296347 828182993 320508561 926420307 889749826 171621146 44625517 561900239 607474307 838278270 898278670 983773949 792933797 653505256 529280980 854160665 593387754 275070715 353197668 132148526 736221792 109689914 99811446 528107916 61916325 552979084 68638103 61460838 435168397 416855279 597505224 76106450 814543944 104907936 951805889 805366349 598757969 816282465 605443811 244808157 142390114 611331895 780622173 369632054 650654262 673458403 595006459 732029174 508156637 944701666 252737085 227422687 525427394 823200924 897813476 852543052 384116369 208475688 21598306 59353827 184975007 695775789 61152921 971701924 579816826 617251256 592169620 468397856 818841341 461778128 731545870 342283573 957590216 704482385 991156358 782084035 736294910 400851392 195904413 774031004 902173620 922115559 512556666 27645444 90326209 302343930 462759639 741344845 32786266 893549834 220095720 656898771 219851602 805153411 435496824 791618997 555096893 22013331 524947530 533634118 426359522 675768312 390601137 122464251 956103264 723929426 47493666 804783853 26543640 482584648 492321097 884115677 139262197 328176483 995881894 247721466 3341198 973310033 242446671 831292723 947791168 559760807 134254764 547440222 107509383 34960568 813684915 75172214 320325747 721841533 597108780 136012438 93008479 704089506 255235469 510214947 866206618 163833936 960308307 420803086 188418709 735553041 667175393 671792915 935332833 449599274 77646646 770591885 808357336 133359863 107689671 500480863 865019373 105124667 63296231 192371720 442556957 823688056 289169165 402339548 478890959 777972586 524561478 459016028 967267450 894613201 234239180 35554293 531291024 434071328 83639890 373519555 593212651 672296375 642949897 829428925 711986579 800759886 382438144 347005260 173334465 436022820 471571604 636829832 886910560 570040410 928067214 558597463 641945033 122035842 164611810 421206694 381338672 667359603 279993877 633506070 208967414 217857634 447212144 996734872 136324107 363615614 442930978 131906882 627572079 544417957 682328421 188911351 86880414 552741717 88221381 41149655 842303453 510327716 242976395 681224728 462402595 744125293 349597531 682929080 54943745 419987723 360363152 872577567 699783488 90578576 950781946 506633674 215036014 635250495 760848469 328408184 305228837 256694575 832262451 397300667 81723762 742583919 343552431 996144425 643732161 921195968 195091028 237284061 617686212 158821125 909456642 386697763 51268157 459608150 672918159 413915126 526214793 466977495 333280399 168770262 151605226 166820433 894938463 588134191 958660981 153855900 287030224 756555466 616815269 414461609 599371636 912363352 614986476 427617416 633339105 313379967 384359121 502474491 299239824 458741797 987317974 482881820 538234300 367830404 450766104 620167092 844171880 231002687 169940751 895875104 676126462 992557415 575129296 899942881 562759218 364302354 800286511 387441498 968422698 17843603 457180423 505268248 182233216 61557778 280085700 654675293 956238938 834928359 956005961 583591208 290168256 725415345 158216250 955757537 719982730 259952234 28979151 824658069 271042553 958463838 107754975 245848255 68697477 295015372 177770711 59504648 822039373 521559537 8312498 255266334 324720133 316616006 174626998 161256928 253268097 316671583 60293355 286546671 936735316 648580322 155091134 211837562 599789668 359203095 266719209 316360669 516022437 877193270 868174464 493544697 608500262 460253920 376225976 695987092 569285053 831817558 62624873 436647488 301034497 883082660 873029898 334389242 515959652 628954465 800990897 839053133 400366521 560661595 179835226 304586406 905997392 313954186 277400274 869247882 396754810 576038701 975295883 347626338 355363898 169663148 339143072 976616739 934285740 730288657 367572584 505405693 872270366 713939942 844604936 166397204 105747774 834432030 476456233 231148277 255508863 57313977 107684838 931045713 5118608 92985917 622288337 510728803 252627370 809350428 386789773 167331178 842364285 380701562 611827599 40378377 258161857 413776680 15373557 697271406 773338015 634839489 996994574 599301491 578464045 413755273 909754074 528826737 111070260 86889151 832847120 617368072 851041594 531491239 791365676 147087850 465104323 372233943 253377610 939627252 596990316 402075604 771155602 541306534 521787354 829260221 683573975 499414759 346664144 511711967 197554102 695769142 933150498 563961595 186376791 328259904 388081259 853775943 42231253 747203045 856738032 486047685 804362404 26502934 435461921 120584045 726427053 809820163 368910356 294380754 697038486 997640377 913186850 198837265 544379397 667507946 366163530 268168077 538375309 993931262 556907034 644940997 494883362 110040573 343045307 797455468 375944337 59343062 420471956 418072021 689168656 900570881 172752205 266392451 799641415 828209209 382859626 448307657 286901996 209384711 392215191 997165018 289579953 751724618 469490968 535281989 687812990 247703836 680269880 535414443 711404393 53503414 924644587 685597287 566192196 177727314 590589410 315363228 293095586 256911175 305082640 1322576 58271659 411981677 186288746 229465652 820109784 878775524 556901714 279887099 888055288 221284413 329857457 864154113 34597322 213530501 901707639 629859571 927966091 553543271 425533784 672544958 97748791 127179939 418090620 358082909 980530460 935162832 91495548 813486004 181127990 420920207 842396813 844677551 894302616 544797033 180315540 502965763 423785903 503086406 728515411 289375119 341285923 590614626 85383257 199052834 189883660 238305554 362317509 881461961 145425321 478190230 378725823 578438404 472358853 740248381 988574726 229002703 211423717 760014720 217336786 618439179 795403992 505045952 379342781 333116340 867945616 404434713 881319114 511685930 569668159 841555181 91980652 732442660 503444329 966747241 901207943 542002562 902560290 681537573 71702027 3665807 517396527 855967272 890564465 158664673 360190202 657040 46447158 284944920 644926939 221051138 424109256 51909845 302761512 813394010 234857496 743403171 440955902 762242563 402529755 612762678 153576773 870997894 655555412 168402135 621103389 617564827 590392475 556806023 841573522 839104108 244497305 211721005 953371166 245558370 1199867 897477798 551788521 2477716 474005264 220553550 56681324 641876694 232225909 4353559 702782414 759991243 21921778 204643792 498134915 385050396 319745085 44897148 333976117 535967076 189545620 85866368 57931690 656296341 874537174 657483311 795808897 53001384 828425638 108686403 404081564 359785375 957080042 785968821 227537821 291302432 838701077 602261540 309049756 798636941 960383175 341607130 462910809 551926349 784316984 439340841 954235491 190152661 463525008 673087697 984439754 844564344 807871617 26117779 518543021 252865163 481505347 828028886 132492342 86218767 698064217 623516708 946415802 651641189 76139065 398260610 780106045 41199974 821473177 392007673 865431390 832812253 784794023 488495838 153212301 852663303 330523464 31253857 402064494 100340375 301014893 745158228 93375338 391891236 264412712 778196730 842195528 28006970 481512949 377602202 636904747 805417401 268857102 377575825 634147564 536836024 256201032 415029583 417296205 882544042 577641641 844686427 444562502 572402950 152986544 697408454 766388074 769360525 500009656 514390474 307644512 180156272 248751396 198271032 49000027 541413597 415189327 775556367 677946986 298183353 872197883 475145666 638424176 562029108 768629001 595436081 128716842 852110376 387761642 149656313 213462947 227109093 584073083 706537126 600875267 322227663 564366485 393604166 84918607 966831552 342119676 988234813 201894334 375867670 779918578 760135059 888268503 926411435 493043649 785117578 15819368 907604761 783260634 619920719 439032695 859659301 233171041 943136626 592652339 680661212 502560273 723232969 915985095 602553010 230879690 405116578 694428248 5836450 530010933 307372075 664895717 447691003 480819744 102962735 891566108 900462706 504795639 91960498 145772660 24386543 833714997 727498761 802838456 689651848 342139685 708576825 767305977 414813609 709744782 844101359 558533697 429134736 544444628 405903262 185168110 656881766 25368574 829352299 710279352 309042057 715208452 501892793 212931110 928979443 478829634 420596309 165828631 782743063 946924470 107250311 383612278 615190450 966734213 897711918 392104639 781186018 76887718 104913829 520594890 523238749 841223287 186058070 314652634 247424351 229963338 746165083 298402041 172122115 310656316 190744228 16352575 115954727 256214240 230082966 968779559 580140348 910638178 950548729 67524612 927523883 439843226 389767819 166264372 685873341 205121039 549481440 107114103 269868797 709109982 415928292 350357498 113310541 562411568 811366953 117194619 266037626 69011170 787646895 114600659 13229224 970002215 245387346 770512355 528049823 318232859 170482583 68306814 834868773 61076544 494347875 225439808 232223666 681668473 822275792 770607470 272169249 755452537 81573008 371719903 107246359 797372828 90779382 822741090 470018079 444932753 850558804 440459521 495579860 181947609 930403687 293464499 837136290 793936800 271927295 734393120 948233629 997234585 17847518 205298407 814074519 189800153 614475985 603281505 559290305 565823581 782266814 215133386 294179260 107777127 797513181 486333146 611738469 501658224 817849028 834579007 231433566 582233972 717944981 126675268 931316290 92093509 786528738 576607698 436901927 900498179 57818920 667434187 649194114 286626482 289448736 795624083 49461406 533226430 998398046 538906340 785728388 290712999 349324430 469699146 395990657 940843490 336933943 253813826 559358244 182778202 671289608 894773859 453194953 325867343 229860658 455148817 962998092 861929536 381005463 118343338 168102689 282411307 337572829 504808060 879913698 216217605 548059780 379222699 121441448 745960331 753542548 705735711 660990221 772097120 819691602 118783086 321163902 933092101 417359276 965649444 65880392 483306480 558126201 260791544 670440350 841046276 982921808 886533586 455168153 341737990 597697441 956718086 680201203 956834194 815735796 80846598 428709367 193270527 651873971 340425427 697056531 670958675 738465804 687613195 718768853 846537714 682403437 725106042 53032660 561091792 626199276 408649076 653658951 682941814 442927223 22025969 980908638 547021552 910316474 163186343 526201782 700422926 467272730 64204860 68074053 664575876 359416238 468720895 599407432 183330923 425214435 601828859 721226957 159379614 821925043 132350823 984391279 180305897 127002635 747863681 83399910 829942293 65307926 780109915 515138156 939481020 227235473 636336033 316300110 736596219 882115442 275128054 463819371 686686613 101910473 633995078 333312341 228698151 688160512 222967126 735924976 643474087 514759431 726219303 673585711 172658632 649169520 525358242 590682195 418299388 559282243 286521451 498636422 371422704 830291936 190408432 186156947 429184054 989151423 730882989 36280908 514751205 199398698 604740572 795895066 123389517 838456906 32218538 65900733 804749496 841805196 999465280 691068411 415149690 812422182 934452917 154046897 545189374 311902340 971040470 331530792 904190758 175997054 797156675 93035600 45111523 85476645 102881516 139511002 130483415 87568937 384977838 613046642 365264197 790095663 156940493 391649143 123731090 551446735 565499297 975918599 463286990 74218535 670003900 596053226 642462388 594504572 229781690 621676346 215503501 470863578 125284215 814656196 177387388 139594202 877562200 735862861 533777886 506920434 401470328 202802049 232996086 65644067 149802540 146833859 905527234 365419836 488335591 684484746 652799479 278030887 377369819 823848446 951912173 626478714 314017963 84561512 668504711 19793568 24770892 812486786 409716826 715731028 100458756 678233375 269623358 59961240 593978735 295450497 322220379 601676223 173272286 997078906 677853752 737725014 433322803 246446682 222639799 623953215 315995233 240183887 970607622 954001744 3855601 704184315 754651357 201415113 332781637 565655785 493765233 432834409 389542466 584169884 978553465 994713528 378624030 98426049 608871746 900715851 271696809 376623786 118409363 777002644 371958692 315852990 651107772 209697980 38276108 532487919 845545283 188268922 624054132 291474487 973559935 542596924 164675010 209509423 525120541 45507359 810499672 787021051 528415567 393475964 741630374 638347515 764945226 841704258 947664159 798555371 459008070 325553165 480533027 314761662 215360005 698940743 424433080 482690898 67603448 452624071 723064005 201898791 888651597 147765920 760559011 356247845 334150807 893502274 832947305 503225420 422451134 238230966 282457338 460900815 289365645 958334562 424131460 292255168 946901313 724873614 493271136 591847425 706166921 383554461 472149074 442530958 911469919 741733555 903301457 672794415 367474624 687856370 156490191 240840930 738859957 665057043 891074957 92071794 727633601 680885471 149531668 215084959 415410330 403023194 846742637 723662894 733294291 172134621 494530019 755753281 575933643 823502294 370886203 42539764 76584745 892551233 25970009 891763136 27786151 598625647 828999555 464697810 229432445 8549485 718954773 954147469 507981581 366050645 868809197 382751431 778483911 901870583 360776203 478942412 205577479 798656657 255793017 435260926 872942938 129590644 218091451 566865665 811434786 110679315 445702285 638926891 157223969 600449467 965682602 255810544 100418628 996888584 754653938 974609771 994322679 205731309 330373283 344076918 373990589 343689966 781497389 780607994 391860880 324541629 462711972 23176058 561697477 693663418 383266558 109421834 16677884 143677065 99647756 584726703 268756395 761514487 935934214 446006705 592079277 887668586 54631124 396467697 388183461 562683554 784410016 703330218 401071457 560751989 745082517 208482895 539013829 119131609 387514788 914236327 312071406 247999632 987018052 37419564 834735716 993990249 144202002 105833250 876168035 111156809 868918484 888470581 86858083 903271893 768456657 445745234 856550832 535218783 109660098 841218622 716918884 825906052 986926773 377513342 96525981 512663745 177100663 46902032 178192675 505651084 976509670 186292286 189655080 478080293 252463735 469975403 448504222 876581709 128333809 373730819 38661960 10712097 853279614 673968922 911952688 862762302 456847870 593103458 64850529 507845848 342669095 384615678 613985735 846371931 291857421 419760215 529396831 273063219 941547330 600337188 859092332 466141552 842276782 739578953 798210141 933994463 340939305 304337097 96034246 117027323 997987955 850926604 987507262 919683988 793261537 250423413 837831950 710720680 354222930 34072403 608446538 227046165 268111303 214296925 970548217 686501703 446778475 880144901 562235979 15286479 220692114 332512445 385533471 139328907 476937071 236687394 324133141 632045039 389791908 609899482 531527193 636112323 570468661 878142758 456572979 785348627 396217677 488785757 423021220 115336057 593722819 5601292 359286719 939452445 37043713 831059855 701413461 694482476 153957474 687453776 615167609 256515875 113913782 266705934 485842498 204419570 890479595 243961825 897038411 551828288 350455312 219426753 912996236 679222592 802624764 949808316 748381059 769612030 994689711 305155715 31846130 451904183 380091049 481147627 77171531 715527381 122784322 508706475 331839769 609736162 923686831 206430641 438035923 337249453 984054181 287740581 470219542 831973753 651788277 292280389 68531745 325093938 672317893 774133415 630196893 608633934 613422077 536786202 484207895 809910457 570890911 242398159 838952155 117336979 973617209 216176874 962892427 709567500 469378939 137755713 687096212 530111687 600397271 950448387 153617506 554440517 445179167 502392226 316644104 158318557 670998763 63524246 895982224 122200344 266186046 76502799 168027640 700465429 829374251 94613097 898566085 355770745 789681658 417305199 317659036 186355810 196938762 369766478 855079199 505861240 578071305 158002108 232285130 334058769 827891209 17735669 442894271 926280879 404137780 712428519 774082293 886558401 380278900 599320161 410871479 475826196 199895032 567669121 433043470 510824574 282155618 444131424 332644167 698232008 425560332 801302555 704401729 288192779 550672329 899694312 115698437 511034423 825719986 347916446 431847609 912351414 520617993 753030225 197959538 482375333 982480427 837373495 704461198 63776358 259578502 503023687 111246132 18283049 900004712 268222086 925794002 862399695 67524114 57521017 250345759 525577401 340507029 573748615 682644259 880931672 692532959 552296501 402731514 318007222 653828819 696355286 69577472 547887958 142960185 82445318 366274768 254803098 521756188 326908342 271169106 72774977 167592805 838130989 256584529 864158562 988790631 967316679 193328077 367659118 505807526 620935248 154559512 421155786 165097986 603392491 400068430 822393080 767731850 547753012 616266622 870018563 39522208 369942872 604926381 789796414 200074321 300845108 421105862 840464057 654756423 508883392 790921368 364361195 216668320 284106839 903261735 194562403 274332421 156127939 988922087 589043111 789158632 607107982 710381274 953521368 15229325 394100265 672889871 124099640 369942457 428303462 9508220 122725818 267643718 920565023 855427166 217780030 912006921 193738282 169521977 686264753 13628638 907335318 208615748 721803899 107344133 1927236 909102987 739204432 48850828 118522409 912989133 994907810 377521670 626679044 965718906 6048168 259549617 220358331 568777829 841298843 984870980 130457294 401979484 304978828 691462466 520962408 183996869 450775035 371481194 621195026 368630008 977430213 476214180 307951005 235413262 68386821 756943725 888989734 343880181 695971553 759325315 19940298 692494860 349683102 599931244 775613703 697049617 646596615 851624510 429979934 377077493 760797862 377674513 287525609 66255356 511620236 787420136 125248583 256038677 572024960 585515470 177717221 10228303 795744167 326453568 993909861 909232027 242478253 96653401 286641847 260358503 293823741 967591540 41208798 595662305 387845164 650293945 472426031 777770048 817150794 735643801 426156964 643846227 96974528 549621545 739788296 285662519 5225386 397779206 1298268 595364604 194742419 116765753 34811459 121939222 469046658 226748558 840286661 824129155 855373149 206160607 233294213 337196712 937763428 792956010 679909572 194174382 68955574 955320407 518893522 991453882 135803844 838380901 152565697 606089589 435429335 301486135 851948547 954359908 98247574 44072045 286946493 8870091 610088745 15550059 977588421 614535448 414314897 635346593 528437292 77836439 520642240 402453950 765090821 434356894 602459915 147259461 622764575 247180954 359290103 832059360 48762546 214539135 282878335 326674137 257934589 208299960 998249368 122199294 6572912 244250502 923931041 754975466 652019676 6792099 693269424 358920772 894464158 875728393 602842640 615278495 523524382 303943685 449954326 199721779 254445152 772723370 782142987 980430904 816592977 126345460 138182891 664907915 199656667 81239497 197065027 417901119 833907694 20374375 261825698 202008736 556664859 866763792 14842999 612394291 571372250 320751629 107093527 302087570 436216906 844079126 947298344 783134188 154107749 888426044 501402031 7214812 211446740 913673648 623901661 628272689 924506357 465421103 769848913 115486206 430840196 999018604 749881271 39494096 752278009 664035538 230614978 780790717 931482237 702079972 91475025 237827605 814186957 71820228 925699477 112339965 182588104 821021548 228090469 297789561 975617653 426619161 220548337 689382381 591210878 545900958 638873790 313947494 658293025 767277683 142494692 548815501 307693687 322729992 309902098 868295640 744584110 207456703 480579933 825983887 95652051 399553335 7825884 169069612 100879813 959505623 411572321 183500179 851072848 595882908 300886586 375851875 134227419 19490909 104732505 380516254 58700228 649313024 72024167 812747258 947253850 996494390 907231112 533211030 88848636 910073137 54276038 4177982 52554304 988070810 38355443 375110537 865323942 186328363 187376410 725487464 110791554 701429849 161158343 748502137 781250600 590656250 847427569 719159075 671726792 417603443 823992910 16551569 778313736 57735348 581747217 932200793 244544701 17098458 378506830 99219559 943650156 580388401 363296882 953984772 874571824 721090067 616763785 620719629 61533438 29566669 278501686 453190559 109850806 805247868 920326669 414530117 267966264 977194576 632352200 259689897 601266718 825450142 831843009 830548968 374126228 185859841 958047246 865983683 796267795 685885318 497218580 696318057 270992749 289969199 527021267 470474842 896883148 295549435 872179467 900795976 770023317 242395000 563403520 261048425 948642978 708155701 958786458 679392257 979427721 459991215 996207196 224278828 280773783 419872641 321270810 288800600 34737435 853378369 40520107 444583346 113582207 902075559 96332979 589734705 936488867 238474997 307203214 836939887 848012356 330390295 68433142 576444017 111858396 173870589 704390319 856950162 909407721 295184723 328981530 945101918 398560258 440564642 163635450 288714536 475361549 917753053 632023171 560016336 891879693 563645173 370351928 897013901 437882633 250543885 95228320 947835771 680388703 390668417 255236715 878335597 17089030 21939810 421855607 224948130 297854167 742198246 56093758 611967393 282851911 511382680 55565505 861265308 9538215 532482278 378767822 564155469 501228406 207853143 994122479 587620938 499648869 256791000 572689016 266641629 389356476 270770176 86111734 957466349 102466339 845864829 812858610 494500021 46580578 221750090 596354918 636046134 985322828 821568552 852305187 549266098 251645539 786401487 595998450 443032333 578381283 605895866 54376170 548776651 575944066 732521519 534763444 53598207 223598239 400597717 368162921 990133683 788837383 37514816 39717051 587142462 783518015 707938327 818564711 776877713 854134187 764968775 349810535 3422358 331015961 64627800 473801151 682942238 872717279 155195211 514478297 10713905 990155467 827955468 897075169 75405573 453987679 842368106 861005545 197973455 838811516 219907411 859849318 158754967 611785268 782438353 844231533 648350646 229943315 800290381 657431543 381753721 436822663 179738436 315992092 36995781 734668873 792600174 338465937 386311910 171784934 323339786 146812575 551881238 233370534 22763252 275227652 287089840 292978733 9406017 357110671 765629869 720706710 192462575 690614276 130561812 72746236 602875316 171946345 248818761 933092215 263496131 22046466 385346659 164401438 391990466 86425476 66894734 323473322 743613696 929604497 364001252 920886508 459460425 713189841 191812794 378028292 517213634 667984 972612860 79031439 64678256 20422140 438985938 256650949 525417355 466462336 257955119 751455681 564830724 756101107 742207738 938277740 739861402 502074856 728407893 249327182 723892568 427027413 519674412 729038961 687613165 674415573 74688623 176407054 783579824 564532889 483930032 323692346 972092854 581228802 421107492 638390998 73825313 497881569 35375018 986402613 164607010 522793223 243841899 959968678 619405316 547439888 657295881 968175178 311669174 662330131 935983754 34666902 769189837 351137945 525299555 944553429 316057399 889611661 844749692 373816715 836058025 700255304 378821999 694603103 409690542 498414113 471612858 801958275 724638501 704317219 639833677 599708569 564074642 926311069 502024887 990500825 755586252 309885714 952556814 174390968 222229225 366636887 576996767 875276886 539111727 367952570 869619843 893928985 919383988 452982338 140194319 143747291 850201832 538919395 379831527 199420825 436396061 164121243 894886150 718003486 669063183 662446044 383279616 333222464 985599036 821541835 911560355 850597908 578029445 314471497 426892399 652796747 493307104 980657780 608221861 464091097 342228908 428114130 752022395 208573432 961847655 961903052 319150053 410945112 292213861 294131011 897551213 563026411 825278674 595476896 916327072 271441506 827707373 394287127 289226337 736657312 524839987 674704787 288229571 284008624 989679514 464469539 989299230 985969906 489752000 903927270 912695584 967207659 865411293 333024003 587845708 696322566 187683072 233296486 76096057 749655815 367990045 114246153 150482753 443124665 172850293 157783741 768468503 395357047 139767135 129023894 641457679 587135379 492071028 851595575 48276655 35358840 536817126 851739375 129998962 290545733 507031804 450834270 821176144 765095413 651529196 627884392 761356075 158947483 644705890 932984235 196876545 426180497 63447330 721269912 37064815 991543634 761735010 771591294 658357227 795841589 871455922 556915977 249817248 967842455 507326073 930201903 120955446 992127126 585598613 687966689 943298231 691449534 308718441 336766326 680189886 217888750 240477659 457810646 447718800 954115406 116221620 557792893 114320580 830283015 693606641 573481876 942367946 643512050 165539318 940580852 459743589 223403418 176027077 882063402 160994760 418634641 966424471 671045716 998222392 252540043 447263619 397118401 824498624 57247542 386538615 197212438 390464758 510128462 132248814 205023393 173320811 683770731 64750746 432072693 727621991 714633883 581086735 161492743 814955882 372253795 199646566 17927621 884677084 545124427 592245300 776244920 53488604 308678036 294841679 183332551 625296201 415844343 167268465 827989288 711322337 743645115 362469977 745575557 808505156 861704455 99054581 186277964 299436150 216640469 383132287 946754551 518177082 81760289 163570165 709955511 187267828 859559223 894038375 834895055 831159042 180981284 221332417 317935062 882059643 164401105 570996845 871005108 302754011 644059599 245061468 191787905 383978657 110878183 463591134 809995999 700856757 839918317 138043135 9015171 840445617 893642449 508580500 430647274 935259622 121295305 907749404 174984048 209123334 572651039 115133731 131059571 455769302 89961795 739287270 923130988 734110168 563042797 869507899 397819246 270636283 861864018 813530478 419015219 243120197 258304844 316715329 632111578 851667024 248347817 308132201 39009854 957597526 426392877 967528235 245966514 721932296 222623559 77471663 267723356 938641838 437915943 176892795 658598133 792491061 870882088 826935046 407588420 306459193 757215856 6149108 761037135 982265732 446985524 420769957 974136297 954467287 415609915 215159580 66223422 331361962 677019226 399485812 508559231 150653234 411021428 183813939 684485098 725333363 951772147 36819247 730207494 201938196 806338930 737397478 783069472 982869120 499275504 58256942 646883661 413713782 966042359 747695748 734759641 482132004 388980841 843741598 968476313 966207472 329973634 726669442 525346496 277708459 929688408 416715512 315616461 250849436 864149800 554674498 478887939 555365932 993958745 584500553 286117242 836903940 824055587 198373583 511390531 273769346 905857949 660802310 116048034 800085200 535460065 681075852 709153856 543448310 630506070 622766389 59480351 377846143 374510078 165680669 462740825 801927714 595394420 81964536 906554888 498252469 919056197 888663103 92536749 36316394 566177295 89375707 540535167 348610531 438883791 784290176 217395088 34989605 641393512 372377326 392985153 385534912 63616720 18238315 918998668 493694187 735295796 845200308 363694705 339052600 686701215 233052382 122453031 517109472 709415697 188089547 777397013 128033120 136755855 144947944 518550045 923516462 328345244 580330002 755517419 135253277 177933725 625964650 448676311 994758988 885693800 14572558 369301064 112203339 666325598 676898906 689557094 501447972 795833160 60768874 142461239 481383901 823108034 450594235 718499166 16438857 660335233 538768683 114129392 686909627 58014877 281663239 382862301 314047682 891963127 400946653 645858365 7891560 988952695 689180864 315071562 42577545 534776702 967201258 815170914 105654801 344296987 485444340 338649755 132172596 224046290 124111045 160888447 642754050 70449979 57405798 512212399 137508439 324687753 545412130 438604119 265767862 392196650 40570549 590049294 156724164 709298178 105553670 77005764 826701559 205888058 393784416 886184078 935735463 131438042 489987132 993924487 784479684 314515193 627380915 323481530 544846862 933036874 977797819 872313819 606947291 800334032 517035293 589510485 845529655 882512275 790120999 819401413 924474873 128389788 42064858 111009755 925393446 281402195 290152380 687326175 54301704 671752870 511163171 637755365 266029511 81814579 850136167 627440857 67596590 802674348 17161669 308535728 563926016 523527670 74912936 863563339 791014983 957913249 620318559 845239700 550243251 360730524 624941560 304549712 916324209 999480307 501328137 956264046 63844070 878630845 922112750 641944715 391418415 980784002 509255867 990857614 306829130 778116852 387702918 529365155 371742309 162751712 95753991 238493950 77092050 518509835 216077915 588531396 379040995 75591353 617094974 369003189 45786612 518584940 129939415 196103882 231344014 833480998 206335163 718053929 577895799 25321860 787273044 963198509 506939367 223022421 533939083 985136396 305022601 802682920 228409117 840667924 763410726 768499763 76699250 911461078 777262642 973674193 173844146 860260962 884824836 679396569 601715893 416411602 367400068 700162673 221829440 287043042 989061843 586876110 926530340 207046400 211264704 212871586 12420493 603885725 644652584 500307333 963507234 666888575 273851162 797958945 523850703 524988414 268753386 213519267 420919118 928159039 673847611 847849589 533998450 777742859 643592170 85765168 216334390 209391230 592295606 10862700 125625521 875958579 104877505 873225436 773262542 207343862 56329566 546286886 841613136 502223596 502377405 320309146 793491478 527095106 402820639 578854602 195109602 965869326 262898959 195577970 632966438 845242093 621986418 279815039 868287396 314774197 480356652 761321531 591653198 191791328 289549518 30420285 439837358 796311332 880654824 891799386 274012765 690768471 895725917 231583255 145631551 894751276 833141939 597304126 666896418 511142549 322598913 762791814 909799642 895928620