4000
424573775 784108335 989000369 227488078 599423447 762760919 736311767 352231165 20818217 141818164 677291009 534352233 142470624 993209953 496875503 399024407 888763187 289422101 792871528 825545528 717441860 143734501 927603614 246174554 453848250 636842794 627561765 524608325 397494535 346212606 32048624 234608628 819559449 512953468 609773445 220097931 462910519 442700987 736765503 832360212 651037115 953895207 397414190 880301381 399969058 476293447 388156764 305585773 425208583 256077018 495965837 345775475 762189774 507982799 860876666 139565931 493289206 379235756 755198743 600268001 203595418 862549659 796065934 187773133 848554359 375528473 579697377 985423928 215481151 223208207 736690299 320856029 913159713 679809260 170698713 588727524 120090483 407415487 125666017 148023610 124432009 517169056 521264644 267784895 69868447 684415106 334615414 473328061 462382388 158153638 939369663 870647113 1621632 2351596 531130694 210517909 180272305 111655895 760051064 262194639 829745232 309214221 626547546 314502888 619653954 594773168 93350102 688668040 962779338 189669982 556504760 30273913 70372956 686390710 286178951 213409321 514416378 596710410 53174083 516985533 141231391 771184856 205684396 518977591 931534729 126915792 109352918 642004084 257240782 973530385 193229920 348832645 607820236 57683419 739909342 247609368 626496250 202818374 232542102 716838345 377157273 840901084 842547586 671362413 796196888 964443069 48275351 748297409 199371604 590158042 227919973 11662153 266663334 717954094 508206458 933173797 974378298 233792680 654894586 36161020 613623312 462188360 301766505 802439595 505055030 435870593 193743916 577581889 907624170 326476087 471579192 414331548 403923294 58258677 915238022 415094852 298202671 969606627 588434016 106954731 604258547 462271996 167494512 259589756 134121660 706675160 687991872 876171413 392178768 456671031 152114231 315973300 306997040 693529678 924372635 257808380 396771327 229522444 872409038 817061164 921837555 741902633 273470377 985856325 321565294 975227411 537697034 741959263 6063121 110001795 431839576 952953484 856851727 425696562 717614643 170815462 242281260 159423568 610077872 497149931 288659356 846160723 391521639 205327390 116364151 253696850 595091823 657122995 12439302 316349009 442584150 1360889 648944324 892628224 139454376 876584729 142143732 857736301 797199272 760618686 669519494 55037046 744221223 113739412 745410925 381814019 322204107 943477720 519354367 533058199 814341513 251056425 54222682 575462262 278239691 423385461 286726668 621443304 271565338 427173776 193636914 79632153 959353857 642263499 232998947 85198264 281374742 491443335 69131496 80580745 782678866 490845481 596282834 361100187 599757711 730994363 745626327 78608206 371195192 310955416 496471827 816333608 713976449 501219307 995264585 256923077 356791006 465487466 946728393 525313549 624987676 576951302 873656330 23571727 128795293 667198636 861095296 103379122 928579725 184070404 261535070 598597453 383767411 269330192 279767077 649454737 242845068 279229137 209315127 829828651 671549228 379071505 672437506 7730464 835124230 419964013 24440344 439175992 767378943 173387811 557341105 191317782 27322321 303353319 654897492 880719326 198462525 354453568 329318016 420998096 503299135 383178964 155013193 241353014 917115877 80484637 413575831 322270697 701598851 995898354 816297250 988320973 538889577 482501137 716934532 493142864 231251808 583893418 579463575 414501758 18399785 694105991 503908632 12903674 645284356 954988378 683206354 601066052 991302354 205662759 681451970 935054950 260777602 201816665 22473977 358556192 601853645 458239796 834714465 665346173 211406065 374992388 81214127 223030638 375379047 351489454 640361006 354657402 855261268 869577109 75586621 584321969 721164175 543664905 959221184 521079811 587584669 801843471 778840341 344142279 701394696 39572917 449531678 376929259 474864530 782692252 720418229 395390995 979909532 814102892 619275858 468172291 902031328 116204818 841327494 783583768 692816331 601133263 942866259 730956100 581762029 599524408 311232243 502784613 620467854 652642042 652937456 996453934 800501648 992208029 461718347 486602613 210150737 220515941 211148789 624935644 305799905 679671504 607248538 507462268 774043085 342080063 654168407 19343151 757753751 446828765 651715190 520320911 189814520 262052696 736666964 949627399 230161 739135519 960916976 941573992 129269433 977731312 441054148 488013394 195580767 271653220 717690700 600620526 604256308 171684612 922114557 134632758 148061536 857595549 373945905 579202637 530738904 281313532 332132753 753434888 62633005 322671973 131590900 981106328 788205829 780040654 391732227 915262352 5749861 716127665 825554998 62331068 710661401 320146747 907579438 933057975 319961133 756066957 868810748 402096420 93564108 340854379 941241134 388903921 319089401 573047328 448535646 257637063 357517596 947198131 689764481 826946278 667185754 4932773 105912194 138865554 948749412 496143776 827911345 139673535 258636095 571169402 143225235 78252552 407373838 770252648 944887107 264947200 403462392 338199701 805908839 651968312 212424049 648765642 881775294 306877724 297787137 758187724 696583165 477084548 879028148 927686605 284308165 595521490 375674279 640251031 511877759 876556938 502169002 468292956 655757020 538726953 574567720 466821752 289486346 377105545 243495090 545683727 223228564 906238042 414359199 282993390 12709902 787219520 313690748 62705025 660626236 927717841 812998008 699651997 392156595 889007144 838568372 176948358 550275717 703403544 11103467 241503123 832709917 130993652 903575869 770517431 987620604 3183753 309105087 620930214 717128572 924012236 182033382 699413489 850168358 153051115 78720455 608511976 441196156 672878226 65114609 467362765 341921310 47541170 834683073 4613984 799057468 282318173 580042134 438780832 873672199 874945905 476942913 588107151 407477344 970484726 926500945 185320365 20828635 533704410 194447471 151742874 23299457 375457567 309652873 618965619 721710811 968506361 330521163 411803646 81257395 282252181 746500891 819383787 690241465 688303612 851290252 906069097 644436702 625557872 566585349 745635936 461126021 499780878 108643643 794115216 588937416 718839893 981378419 136433255 215753328 32326086 737327506 406027551 21872293 20840442 706704469 978054752 667181515 703310833 558472566 371463574 886055268 438076948 180819070 503378413 725766215 844452005 275635730 961674535 476130002 189120934 380160890 480263471 821740793 443962752 402600602 214831783 29315280 549651599 247063417 884928947 764081582 589497980 228507454 863562632 186660495 96883518 376893359 457014556 949951677 941572283 151058964 960707586 632329144 445001136 748307257 49456296 622622325 947767345 814577883 190460125 130363623 597128486 971569621 577509687 762261472 377221805 872589530 422757375 929191232 565198481 996389041 984629619 533400748 236930154 484307280 576283716 761212714 805033890 533999022 147503065 40072208 940299514 684875114 158418290 1786475 22593378 904821185 838645564 406741737 707269544 488614816 177601186 381764585 317436116 162321889 463203505 694227883 202685260 441883738 388317755 438933445 790975000 519595617 780548096 564551677 609771056 63697585 123852553 671283539 695774625 461656148 750072173 253378443 685498176 903751796 540403594 642048823 584434044 656216972 163030367 201585653 93078538 826698126 496747407 928578837 30283016 225186646 98990273 618996902 432987118 443331720 990360403 853173845 680116890 228125996 969438325 656076781 84801812 149646925 474665673 175072697 905944533 527488997 847580158 295429658 552953721 547418179 406437634 728894222 221492065 677118700 321496881 924991166 848962184 760759755 994230024 9096757 615061593 413621787 235284351 203814380 270178233 921453116 660179051 974991170 294253335 236291811 276092351 76203086 867802839 482874169 632070648 923911653 349600351 619326451 825130542 703199868 968459865 752177683 834931472 185226911 246090527 688211207 757993928 595050728 439171073 809856708 280351149 482262517 163922289 36538635 198079906 554217254 647370384 575341931 781260762 903746998 62630664 819102672 381052631 641544227 275743586 51691832 501995752 882562851 946594695 701194114 997972922 110097561 663078048 826834283 345925506 557534995 189217117 468153472 278830630 868712257 850033847 853006486 893157708 764425475 85770943 500111685 760558480 409045616 45537630 111340838 483548342 933452512 903763231 244231973 242620406 514779893 23017173 533332122 428402734 523333822 649077594 629201801 245916528 188090576 360818721 628663442 978311145 290211221 990317222 162583385 444924805 197959050 98402894 346726889 282906800 252051686 833138119 585062637 900736521 741151447 75163284 701566143 707627034 92444555 729066327 430685936 881308034 790297139 74553331 500207451 658629476 220954713 884359110 139230580 765125700 816525252 815277601 794314543 731924314 440873659 607816017 738348749 36963761 806096860 912211058 573031133 849809383 959932162 644344727 54481902 837586321 631708563 629047755 274565745 552871132 559574233 379454589 456781550 406139625 427333009 105753189 425441809 91385514 820148834 689299655 911199722 464220145 487928101 255467847 9577539 996396311 978428918 787379840 890261137 879144115 865164132 838112372 486938967 685392733 220181821 255904423 455068157 861880733 93292243 72637296 50771174 878921919 90378451 979187188 773073088 329352802 409178330 180754111 462239098 800924166 696415228 275197395 805601226 725537987 681798919 636587754 822963056 318399140 139401778 245309157 940824759 685496691 410290941 46515857 681302500 684385249 188501163 60713269 744606150 926313683 163778255 696790211 692643396 294176915 825122540 892645242 542349360 932996050 305773152 394236756 925561160 773492385 184620919 195957439 454849598 86302005 365161796 693363018 956666923 359244657 988534812 316176003 142593771 15590070 73593897 867512873 290188370 198715504 343278554 878991982 503485269 301732420 180810624 137774085 550875335 865007851 201894378 763126999 875720954 320526338 976791602 439058645 284691339 186434111 164544893 228918053 255483696 328987221 306957586 653743373 165221486 899553715 930348494 837877146 727947282 316325830 918725803 954562742 816953200 841843430 366384441 359484809 54062066 604949479 690052344 882137367 853506348 470575597 143266755 324550371 310622370 23605062 545559588 225163862 980563672 773777263 413821570 903062169 206849 396319170 11146030 167485479 130195531 80566070 341469593 16401905 631140526 826322726 58427872 140539097 261851812 51725883 254053217 144300972 842946112 389687102 114293862 637150901 487041141 525597303 671399824 174972891 305188327 906042562 256603082 535429180 279970448 279630935 908188196 717264838 183965323 799760472 469340722 684432899 441081835 2988616 680162507 676404599 190125819 841320119 238804397 93445334 250741283 868746233 64323243 909864674 568169920 814514426 398455071 613895432 516464820 862905993 370145220 978931120 606259932 363003347 507914568 765257379 897898769 141337530 929265360 765076270 138644555 540419947 489210813 357376081 563462736 282381829 694483273 366314574 187745648 471357676 737454130 302955425 550721549 1133320 587136490 639571254 500622643 190328701 272223062 421007622 170767089 519673312 853861056 334598075 76454080 642578578 904751302 109235209 325097215 440322134 452375788 967274445 596592176 876470697 123336136 539547243 437998566 726962183 229729223 890983037 720037057 932709285 691558414 352203316 750540766 217815354 305962018 55979336 737650650 210274245 257030748 47173111 238641519 373875654 187302170 810396600 40179033 49796915 751692518 253650580 675225162 140337905 742645594 283216444 928676603 480262750 990532602 557968520 957606289 303314088 688353184 599782950 580813178 794073447 65378079 987983268 554141053 233371848 217565750 930982305 635521609 685997870 401613526 623152175 979922890 944651212 604803820 354518978 765900968 593631027 104791152 684998565 839891188 69712463 143564312 660216850 821587257 46739627 103061558 618277533 610991391 608237150 214714881 297766239 429352097 420860994 475737768 859950728 336708115 591382951 456684759 125629137 539355018 849733298 246299923 853933207 934222420 580077456 403280666 881341385 373401777 414748172 186165404 935722905 556048924 77973150 942700843 168496967 277098568 263553186 692282706 958189929 279758996 839677468 236930848 476870290 224261937 453714101 36057791 689358149 500253881 835102088 323173298 58220264 430702047 145712821 799646540 382164296 152485890 588679241 30091506 543121570 505266641 73665912 611933931 560872321 596280857 759246173 526105275 804492218 155121708 164043314 824128426 447410089 977422155 944122405 686832960 962034901 28829619 916499940 227147191 745980693 166847660 674268703 804381430 133500026 131376851 701988843 33878013 228354293 906362849 494601360 540630794 860606968 815386261 991942413 830213570 553530491 805990242 332090963 263193127 740572269 212556487 505379097 378704156 768563754 652815823 168244343 214500279 348487998 962318890 97185809 378098500 372839705 970034951 890860857 171450733 759629701 43565247 737776659 108508320 282423913 603631400 960191743 412255220 458128077 107679957 485096247 651350267 337415790 263002046 370704621 789869999 145924424 409263985 505425542 41769251 566048107 541579005 183246510 219807027 885766968 593539527 378420523 861299712 249375397 209197853 80124670 118812205 962754205 819413310 522827514 118882022 588832592 831818692 854771377 557637615 903575773 464048023 15925092 255731020 286574777 807050856 335795510 231329286 106323947 429241931 307692701 393247947 639167114 584001472 837194852 83942897 309890306 509076599 705892662 295790055 532540617 842721947 358602290 135983850 709441865 26326272 995522577 780814679 379418372 379440042 372898907 898919975 4204595 713017123 502520563 834698216 168584404 86431178 212369858 693715565 678958477 397649555 82543481 340873824 274067090 642567281 825355310 559451021 161158108 855785507 671699359 294709628 582161035 411259144 815276604 914030219 70793517 913132693 989016560 802183065 741684096 213045826 837912437 309700210 561993710 43136838 223378301 206455752 396598230 916716743 288849333 648063362 833255348 418317380 692237196 523328337 380182532 791803932 387423555 103932270 101664343 430107408 498756598 841887405 328221905 227604042 640026521 262502821 452399286 529209560 294460767 590271139 503449316 85058491 379261972 572358458 602466520 247560918 30923106 24985433 413934763 581424456 296550115 343937498 955843473 359467927 458574173 981869482 792992754 907768979 472701545 594919558 444268680 20912786 833607516 95477518 620073889 728375230 956341148 43453362 256386207 55667102 3054496 919817918 222573827 572027631 152358808 878295044 737160478 463123582 366980486 182315257 458010292 806529724 587362354 725936762 271072097 886395266 733850786 128039436 402495520 604573765 93827346 101731568 431185496 940263755 460548242 322670877 925587975 207959609 616050071 288432392 307212333 732634053 33922718 493695431 226602551 708325710 775439466 874821336 382167283 189595534 122504200 63388970 93605379 15207298 647020843 670454296 96096274 483262403 724180670 85988125 250606263 940107239 983533451 858053159 692137953 714733251 519469358 189113098 196800069 957214068 299362289 414590998 44664370 323730069 639470671 626488642 729243477 85821213 440037401 463741910 1961741 980828071 180031768 775832605 415795231 833930035 15409494 351984431 638314817 174956194 678526410 349563294 92749379 797060969 284538836 825565460 439421109 653556857 515616719 362172670 564427705 681715938 221611146 610251181 560944391 28613160 608732320 108739782 435142016 212154656 485430955 972958303 103870787 658661543 696614677 840309141 68559313 466797090 958032659 337788555 93672509 636938371 475681883 489962766 741300453 449422313 366416248 733139103 828461393 645421700 755759790 579752026 314440805 298739932 571142417 274499883 8230491 85769057 595474731 752826523 810556572 296863423 25805134 966280276 74516325 590133016 250178899 84734798 981238306 449021858 769064169 251553218 463356120 991601764 251463301 165180057 429154254 988187552 396614642 546443536 538432193 715768600 302726793 759456799 378499512 797174919 432400724 85958501 175538072 77396675 148343301 684953956 779849303 746703316 493590600 443550522 621331341 667412146 694122393 557187511 526304201 925713634 104687498 996900862 747220399 538557028 653757094 311592217 217503237 662816547 188400795 966653863 581244704 246387714 570091333 674914245 444778134 369665194 278854812 994909203 65218124 368875237 741759563 465264075 607025607 737874733 796203802 682986774 624591371 134444735 842541967 29968357 862993142 868812979 762367688 895401317 546113340 483272463 650972214 338353493 794513597 165308604 839492908 346120630 385809033 806065611 437780160 367646975 31616028 877540662 827403927 47024396 119282383 580381675 302783696 937171402 134821838 898159759 553893514 96581504 957768351 939578750 247318970 27431472 133910103 693795476 48565104 86313299 231745462 708118210 198423428 503206138 412670437 116841037 521934541 582062926 583958669 217732615 362729306 962177636 397492821 752764383 849063417 465842235 256830035 160117055 1852100 581652732 824471340 637109585 250494457 788932868 30074345 296436351 989425460 377348360 837027687 992247673 238514856 945942271 341293402 589384446 445970603 872942069 606337688 107608026 509337780 483786815 333564825 318602650 886959796 702649574 291874608 165090547 608571426 202255426 667769492 838690462 629898892 954882353 848566650 904003152 955346478 898907014 995651835 230962747 595329952 173770463 835339104 601745420 352707004 639965569 682049091 577524756 519450182 788205611 748526535 99509025 19267749 824843360 691255514 421332007 691089127 675435089 607451215 987167341 765905310 755722327 18045554 2961631 356562911 740684755 525999079 576228011 135919253 29781057 832112904 226921629 372693325 209636712 284236934 632384032 494963049 179731043 365654454 710818759 15018347 838856894 282666725 799697548 354104813 758406110 237574005 52995381 447340057 115922446 314004156 981707036 666741340 832918285 432093609 624892732 262415249 810935170 271310436 266635942 766525689 487605819 669453633 398545905 315469489 267704701 794358769 789858933 760562472 731710627 767075695 669594073 579963173 963282484 716276646 858457415 468674651 557963802 496264769 492686797 434493807 724232368 418272798 104845138 208414198 773167714 516378039 934838818 43847502 289666829 25643480 55169744 682334460 592383904 924727998 110653290 615028600 669705161 789492845 984512878 52168029 145803783 63818164 860241631 483682069 311913067 273748267 808442082 380925752 877809927 974619347 885176081 932095666 832725512 297784773 904296493 325411929 980468738 386263874 630295042 598105603 929121909 33822771 111643333 650455358 573955816 875125783 63859504 519334345 365821384 503883106 287525042 578423960 332323335 485584731 527932499 548597366 47848514 531532085 78060496 98256591 17893604 273792839 665056001 346899607 998232961 423996745 683079421 70047398 151583887 407870040 692580575 625006177 434589667 748631229 826095540 466677233 915229867 252679744 314873459 413390307 822463054 685587119 72439056 9481111 720350651 395909559 476259831 876640829 78255712 584529165 982671298 391752956 412161565 386360898 421179500 401788537 615023922 862432121 981976419 535203692 680767753 446846260 227499932 614283646 395874865 857236875 953679722 136523383 71511426 202105771 663926149 918526739 545689516 106559640 592887241 953390268 392656568 700693660 267042583 66877366 282180557 250956925 159222455 720025334 482632997 622637765 265725864 588425822 755620765 641700921 55746126 124623582 160738942 242272608 511081735 757655505 347024303 996005013 852020722 832122261 470855122 698780832 780588522 358279979 731101419 409309400 780290997 531069708 124221706 979422001 213300452 782361101 795273004 408092757 662180687 470229752 734550488 927941225 586582237 804028336 900804142 245424930 365254058 594984079 769993789 143584413 858969255 360015930 264073653 955512180 146622563 534913978 877863519 761809033 834973752 533948572 758916904 619926732 409262503 779878986 725757427 412932864 547182801 634740775 516212813 344250789 411847945 941112246 628626388 330170999 694624858 943614023 647824167 806434121 765262136 910275541 720289069 627890092 987998863 111562946 952040115 497868807 57536206 928374605 392323674 399304985 996559478 637882399 946319362 468097461 218263065 441993291 911464671 823388020 246766541 47241286 757468883 227185285 1570961 538105287 226330574 205949375 573027243 713632636 533849956 834766678 614527411 991649218 973438460 202560478 833950491 504743309 653073341 816685711 895823577 692506827 539090145 32927307 199497603 144531057 991242678 361761596 790036284 409320644 501129003 529903040 774029173 245720161 807367276 720461399 765468315 666651975 289848605 173352257 876105046 610838029 811744291 491581728 976655226 306230874 678428379 299112836 974649024 364450000 305814123 618145329 292463523 386291284 32270498 341266704 95624193 248514585 733097205 287989745 593483870 87368848 18113485 228502225 384042241 627781445 404746360 815332556 81910285 178047739 500113140 673127079 654884101 103733010 39653719 621874263 338416253 195558411 466614852 693614682 788604970 15595800 96895483 890265669 354521824 506209503 144541436 395523418 467311406 54061971 51796606 793738837 3532894 773571812 808198539 325556239 601162466 445948001 909739870 931684181 809417754 784135647 533643626 150211866 613658507 256555510 569575335 682254046 720160889 520683174 835127563 908971078 470358181 805362207 785828156 609007489 776534575 995694819 963510896 66152538 293713129 751543 559265761 642973389 625615730 639558880 197310913 895372090 197708948 9231831 942590513 523088071 16228038 458973515 673203433 80330489 254729053 775471517 524292486 840605869 316415299 992982279 334350222 792974186 73196276 885111240 260084645 23838731 425039698 122464485 781456386 978570134 281691361 26009806 95690802 299361171 158827265 28930569 613281654 663101298 152988585 688112602 228651828 131571398 421325100 183938786 298340092 381259159 808754557 820208577 134946827 818680578 69888634 363986548 128317721 185161589 618226180 561257218 489902131 983108782 986974348 850383837 887183496 95619396 134042834 200879431 887746003 51608633 498729641 453896466 471875964 415962126 63934994 194761365 895336902 721688440 533592513 659758204 55212031 833209060 290870574 179643694 225246836 496262020 269560429 77002950 471739825 969724059 364747474 521191402 51025174 802913697 181753257 208905237 952191357 708510947 521312925 666562519 39869783 240235686 738529397 14813299 889009423 741903768 635680257 129406660 14995080 790618192 595633044 964345969 418899263 961215961 931493718 449818965 894375132 586910317 433119592 458845608 920001770 951618820 227518262 857873579 233190730 752598312 427066878 190297950 30342436 796121463 260500375 549596563 328593931 507163548 5991696 504015441 946134274 562959923 957419696 413027387 391937475 316183891 405819733 384423134 479893664 413616315 59889701 862170412 26546815 329673009 468125868 439747424 800422220 832831062 578245370 835206141 28922545 31707802 438113915 28521277 368355184 968047350 424863300 142693920 887641481 113257047 573460629 218563648 194943183 394043058 716072266 262842992 703988072 597599534 138643061 216750491 99400973 39860676 769614324 943420306 818182225 486115293 145075118 266515763 956404014 252187206 119002512 15219709 592434067 491480867 895702912 409125998 392029819 911402830 732469795 127299436 706444322 718192912 675761074 66239522 146290738 540620171 536876016 774725597 216691987 801720537 298365737 454690909 596785928 530456041 509332410 913684851 32780794 111003272 254626476 524956801 752509146 231787625 866336847 380468290 186863043 939193743 998145396 962740387 616830679 495938633 380036238 675904790 740512477 919095916 910336170 715568251 115413686 310289336 882814187 133100604 34894465 257710271 810125372 895302487 474152130 642413543 176295259 366429829 21826314 820749785 778841164 930600656 966652772 340149731 86424601 264835597 113147756 867063826 86136370 580890129 726108476 231128728 808315547 470258423 73057156 529226149 136756630 810152166 382442309 756152292 455952457 29617923 938344110 959600525 549819946 452392282 945103902 749798872 92141841 549513231 793640771 4968622 242856249 844543630 665101264 124789632 721958949 639725795 266552522 844098725 83677623 626430762 737356117 819339119 961089712 341725120 455426518 744987576 359425136 666016542 58506134 498128013 302108263 768874439 345554341 631826582 65150398 982597232 511986625 546525058 496429727 204796759 962847580 396074839 177887834 757897373 782934446 629958218 68288758 549636806 180298890 375081894 151225900 746753910 501443832 526914283 770964943 517821016 280201822 630710985 36631989 750120543 915975138 674629127 264020615 608940608 978870112 955523796 450101797 823125648 922046470 997038478 824272118 974438121 663345739 709030287 70695335 123017973 158373681 29418284 865115498 581411005 280242170 80377578 899591361 804682561 79237912 41325348 474780880 579698153 840679877 908999377 607344668 961198099 215130194 435305711 291659187 357736587 766217189 791119148 459784657 76775006 716361179 256971507 445242358 675283280 692840885 235684836 135071207 931187377 496095981 569854087 149177589 942090091 357646573 183030855 53048172 357786654 118671361 39746267 167458155 739392420 366368610 720627794 331347686 591572108 687476317 785727744 642128705 299642235 564537702 290592164 452528122 46095455 187851601 530119691 574688334 481740354 738132693 736957633 173705659 271808589 278617898 854162368 219726956 6430792 666783260 42225689 153344713 982018175 929464328 911167007 945568848 498514399 492580169 79247163 578014982 445175619 955047192 436169905 88466661 418927745 795828496 185560611 49051955 973972862 429134841 776996452 627295531 381873391 343859861 280934698 250720590 614316141 866524268 430854948 991767698 354179327 413003681 868130422 810010371 234475980 42620200 118080171 582264479 119053101 597770303 608014223 73788277 914319445 739209541 622223764 694339009 235635776 118060997 922426561 395629110 369742042 206067790 144021225 706968412 708745060 228735376 198681377 82908888 817337269 839062719 438911494 272297664 484232196 199445877 403940940 903660267 16866769 154445932 40612672 814488120 1853087 860146273 472949405 506025691 443548959 258273207 363695261 732712537 883521953 280418188 459125711 753786218 963532790 425115540 879242991 231188977 549866086 73833423 267942804 722733318 81037203 965826070 601217489 10369263 37286973 147574167 317329547 596205296 622231884 618720616 552532921 531132501 561118490 957500290 340808212 434965361 574001685 933938479 970123324 383378897 975735199 357081552 75394294 106662411 204127854 102420826 632366546 634707465 102344544 543552177 598270357 347116165 290335032 583390422 776636626 761686184 424420642 814636294 684533852 57721312 42890176 769542771 232514444 590210498 336011394 212268040 658579932 195303808 204660385 552843401 77351392 660933992 185122031 615652833 862413450 939978458 392651120 48067200 303136634 328941882 756062053 499109853 925777000 135778178 396251125 342668630 628579716 745450645 713792339 916357295 289364169 348333625 638806881 716557830 338587271 349429379 319366312 242479280 837772803 434662062 994586230 185574266 903824318 300793797 260722804 19746565 672814116 237849360 940709741 874353854 64858530 228313967 356169296 111782069 806393979 396751093 642336577 318400415 919199063 822108984 496225487 494109577 257587326 598944858 253211161 333088359 193198697 347729316 944868002 909150543 251860243 554026689 493454637 497704749 108517240 263053976 196439154 702359337 818072381 811180388 455708163 789166051 790583962 85933416 800414077 545085925 240870330 519114404 926031806 583038484 76474171 271834235 641683551 948816529 518598723 410035225 790738714 382756140 533888476 391931188 333077941 563882131 339553908 754755536 56015274 651039334 540119131 354204307 132154760 70435098 417566546 123453230 370336158 641566368 122304705 172105969 225889094 21334606 544834578 886618487 273524098 837489417 56372251 309951508 623911644 405766428 641835673 501967246 780602334 875891001 192623426 137322063 953154892 220867724 235693397 800499454 332999709 228190472 679571748 873587229 227885016 615753172 281634418 469735032 993169455 954810669 694133214 399492213 431002076 781950609 88594121 134250516 212945658 536043834 457456336 971266569 41302177 29446587 496414594 989198478 55745906 503760416 143894471 58449524 647546089 862727147 469781099 997012307 757570907 765621433 973327677 460679492 715582849 640400658 125849617 870972383 374150779 837610476 621328352 506878846 160908152 780165648 539134338 685066904 942996506 753313149 414615731 516102602 528276517 631625565 397880382 955420796 428335935 169426256 867641314 107654566 363371871 246891742 957335405 750632050 242132007 655399637 234016571 875982897 933391422 60693894 589086368 646482485 976138140 726779324 792311017 102351486 281894359 282346497 734523189 661336857 643297613 678893591 296830848 247569940 208863450 436978098 353839583 227783325 829139612 150125088 761981895 803043427 848155480 64498405 535472986 46797735 541721824 255350488 725297588 365221462 339712343 285991120 130231821 491433479 462093224 987961499 345210634 968109696 204834952 762397408 521762020 988979216 833957927 29768569 446160462 346449476 94704878 994661777 601179816 935307187 762503064 283350282 214215847 685052082 510050252 879415588 610059363 269729943 313664057 782336155 619001268 31598654 378528220 131147815 414542064 163563885 279077188 703469309 532123488 630332465 905207666 768525595 31047404 910199472 911327694 738188264 820350271 622120440 353170847 695269366 957732275 412274425 328276666 953472536 83827598 706522312 297449632 756646927 944344350 928930656 427411120 842342696 481000976 743798823 238037096 782894269 208893646 560277701 971361430 556790076 375922483 940578386 756024033 972457704 241405153 23089101 373894017 684776733 237319384 681305852 671436018 429018964 336061519 219106204 145866325 632509242 317706395 842011710 373809708 528223452 145304805 589652451 640629714 834893574 823984396 528433859 321014750 203671595 622646855 249996846 876160499 595732203 173124139 82712223 390798087 312099801 501854222 872061849 396956991 660846562 839594153 559844849 756302657 975932645 641122555 1582092 158136580 908789954 596413247 90650587 495696547 817502462 36102096 935485654 771808271 347203621 596937846 925726831 469346609 69133975 283291473 511071657 144214356 528454001 793759651 625344490 935447845 793713183 865103636 435110292 787280084 495212764 792264031 405956832 426085078 425167798 38532030 366151505 94298539 199687193 620023592 330525128 730690928 718928895 558026370 628831815 288288713 319202028 535933949 169329509 682771431 882935674 891070650 69942829 373244025 979151880 146229721 687357092 372935623 454316287 628363029 166758988 379594204 719320364 255461691 761680286 327316215 75279508 9741050 835814036 192255597 696435889 35794520 959996249 445259758 823458620 488356774 739968870 573939635 424382287 91567145 592536434 697490568 818643305 318919481 145964492 458397879 547972769 423631055 273312057 919539264 963742712 742075672 76192670 929107426 979250714 570123301 208984710 688865015 844280187 41658564 894297923 326455499 364888646 123684666 294879760 957957930 410539306 69964438 681479999 309832414 261600498 229465912 366621861 418901983 608935648 181512844 843234051 17544122 11037664 968154108 933424804 548460950 919686992 630530388 342849361 861715781 407309269 731753046 286440766 925933460 197892644 446380418 817751399 439549869 928812876 595877860 928812744 855213613 249231619 224955728 960083967 11163376 17997474 17806108 570073611 511059729 699375846 714641808 720662156 540065015 963820661 801028191 92826763 84471503 359996425 119552429 416076901 462990973 689771015 273610445 699800180 157494643 973253805 834611848 9943712 604216517 556214066 921021144 607484192 453304653 870073503 690466887 574310180 437996128 165946802 582429888 300259149 455068493 718595723 527385297 92537250 331874500 362730747 120466705 371431745 104487490 490202739 761472850 909815697 956614698 206423382 334102438 575521559 954134729 128913553 141074537 227278751 962029764 851731021 439400332 376447478 895533228 236058424 360025364 393441773 768073052 559600656 220243887 985988045 485062907 516961262 215967316 808700639 966558314 309045047 151862088 804435391 376356148 389607391 725931924 255977536 704455080 665922271 177572816 447791841 130676733 637309798 5434647 656646138 571267795 844553813 920948397 521934978 929954306 181495583 725025094 995885204 632674632 420808928 24880225 687433523 744257138 409358710 118843596 728014464 526727546 450505932 283655474 129271438 631908440 837450554 125488420 284696696 300048044 163813472 876670057 483402485 662461899 21409534 513120552 474998779 591964652 87471789 671548312 871904398 962260724 600163371 743038163 81952070 713084732 792930701 641577773 397857510 774323691 300200360 265710774 277696400 403141108 578296140 223971038 308558450 536647845 730866449 415368237 182044248 310547163 624381083 464083955 373123635 561548845 988997758 262255821 807940602 399838320 151550050 963138317 904382977 521855095 323561895 49207516 407705784 663615354 675331996 481784795 918209076 26640113 13258609 807968947 884154626 418411511 936847443 254216364 652257510 848385358 837974003 840588943 750445040 387591753 29094252 588874062 414225704 913717057 162628063 122412357 862275395 60245593 74918645 935750341 428072558 406012312 359481445 797454588 956761886 956478735 562234946 893622896 208645536 985250196 604027553 685294934 645518612 751975827 528038714 408166912 416325826 647567506 507388812 306834656 499513116 906010493 347672481 202784014 64340708 429929267 722261129 852419510 31299669 81478553 698514076 460414323 159570684 362937522 128653017 960643141 301771465 372007948 308041197 325175380 577815465 925404811 654536681 455156226 927210201 828057159 33809513 337178803 232645925 35459725 215051041 573201867 324805372 605715582 522419874 367203269 333187941 5485245 418316997 165022636 444592840 913806072 155171069 125143842 209491336 919630387 422683890 710275837 871529929 65849828 213222089 155877907 77720448 874750164 698521852 829307399 68050715 497769684 599755509 258514461 577954975 198021617 677866277 683716880 317169888 265809400 527476952 448408763 319573521 863283687 758149814 10226775 963182937 230037123 383856573 891960351 23922570 83658776 786023961 862914994 497213249 396527107 861056364 322759518 694384664 861375617 534966728 865053057 861663075 573187307 643340052 857879080 801250441 551347014 719540374 466900980 470974596 759981318 727591845 165914452 168023391 810384378 341599184 627543270 95649359 48448891 905686464 56013197 755184224 228013010 81542184 129237459 647269173 682230948 993829109 14434230 131570788 628651086 390874360 503561771 895108224 45404123 941531560 297240356 781310155 271503636 261057416 102155673 491172627 439727240 94918620 240081908 574564522 698145435 87101171 133717361 72717352 893137692 179753299 641707622 479523120 654406705 183030821 216415552 648862561 277476816 510290379 784848477 473074022 970189790 12981664 197437548 285463370 385524933 14561603 327726992 264248584 783073059 208646044 322579495 230092304 492297566 741121370 566776443 746051236 769001928 2659283 942011497 528623498 567039210 847316237 538476117 225113412 587871310 390799566 322362828 851125914 437310052 775673052 88581066 803169405 577457707 135626507 25464326 703792749 748968001 844729502 171242324 686385857 701674868 145292513 448569168 231850833 103193428 449578949 538013259 6519733 370772340 16439249 826041139 591153307 902180335 604954021 930280651 197348819 454809027 493956712 381355865 610310958 111610968 364846208 743064254 772919067 404331086 836024149 531065361 692481880 950872466 943398558 673769773 609392174 989013878 89103997 611606272 367764879 255045278 739221096 397169960 584661774 156520089 12438838 726362997 465524185 888617105 187721314 752419697 724266445 333689687 605557433 135723253 411565198 898458425 644053428 741328251 22115174 661812484 460231558 732283715 336870253 175777306 544264468 910465550 26375097 434471424 491379430 51280235 572147443 306575575 802958927 38637205 898298240 342113456 720981293 874229609 135783466 736340647 569364959 561683747 275609177 779784771 130949782 919949616 170076204 631297549 565327481 777117159 126481049 150846327 459326357 862929353 933117977 208212520 937974739 271857073 774164087 103827044 769871391 15123103 967036417 64582808 830836193 694375405 892873438 12898096 260217483 532449125 849800105 822895804 765203577 124177564 962649453 647649133 458529322 802337751 44601026 893515421 922841509 204932924 877617537 574653414 756468992 476771589 867441957 772497193 28335556 51984020 897389909 442569299 796939609 738747540 807534506 992909089 601436457 945967789 395145964 799471989 764226062 724826913 300645192 258400093 585568437 245970463 447611661 815909335 619320431 827788657 582240694 41567083 363722878 965384452 697151220 936027507 509008969 900363801 1934067 790298474 89373140 427175026 418433052 55091287 312829854 422641967 745125586 674699058 99914808 632850348 718211622 523300642 362841538 363611387 166267061 852687277 821220077 329263450 647123576 736141023 851684157 30736997 610828511 576178178 316616300 230849539 378036205 571733502 259907018 887291267 481112899 598341777 115077045 102080247 308173371 411298023 993487610 896834194 431078302 547025325 346066209 813091674 436796531 334136970 146818930 673801544 246391631 224147677 858150386 67060106 895929407 440247430 714391949 278078597 787088143 574427564 347976316 177373510 394624951 641611331 655799060 994234216 108708271 18369784 765753288 842660271 564108413 523341272 15463790 488976593 521793923 656611766 99592932 526269430 46772253 773981940 33426292 839441749 676786650 413486171 604890858 71056552 838369467 107115395 512888969 988534389 743183757 577264418 881822389 551558549 282327839 557109044 758717249 510543542 934102488 389342245 788494217 104355163 517476565 329463688 686962259 865620356 247150182 815475316 361965720 816893249 743805160 639086024 666528483 777423518 235382149 690911331 215743134 589621953 738449226 118655214 510023499 432836737 734870875 833862336 832892063 871119162 458134309 524998340 860744280 792256544 238609332 852603429 799842189 248558494 369030667 197289167 744990693 464777659 426182989 599172381 598015647 805564590 423800110 918642864 838317244 476714844 848983253 826913046 107007999 511912077 464077895 644169959 128133634 133918374 248032474 937643792 898631975 973308610 800040552 798790959 874919574 532625480 362728679 568983910 855094776 593906849 840788409 942188543 150450034 909362732 814330643 567657308 624143469 127447867 555585025 184791043 386474826 114105977 140897507 79410304 60991767 219805862 108939268 406543354 62836218 540016720 929376910 113975311 405863994 525607488 847507533 321613852 579117628 828207008 613294144 918248803 836819155 254717609 228257118 167517846 789693759 211562441 921391423 717510545 461421549 643889962 78168629 434902070 935294752 679669071 128571340 491128875 799786765 768237750 221106499 583510503 574653606 880191738 26544049 87683524 456511221 532828576 171955062 397197020 13706307