10000 3022
21367838 102795146 626020043 659628887 537824723 97231444 288335344 336816566 619026744 437917487 134557701 337319145 230376858 781565479 744753196 594112887 875797275 726088759 205071566 875352991 673465328 619727746 297391641 987203886 314157608 261490930 504494129 271511065 177083308 555432169 693771894 390658302 439394276 6839632 282542818 353191077 223750058 195624734 24051090 944442599 867446372 6249536 678145188 348129956 332099804 895920516 419790029 747327576 689699244 743857011 727933649 498974173 670361710 390764761 453257929 877695443 844074377 450362451 960000021 518352573 334669215 525666001 817669664 230367460 632100453 578039932 436000378 599094865 939605509 553782934 638773063 142554301 88337242 278121978 737102639 854936620 514108169 371166735 700073157 715964082 8237250 309622634 334134960 574170003 408480172 49604697 283748368 507118124 717553717 524072133 877537599 148123532 374923099 370452228 86609136 250790893 780072989 23010611 321155802 159739949 723996608 436826932 267619100 61515418 668008272 915100232 336501243 480045464 816495757 929049997 923383931 30216606 839161589 124292337 914810554 538168057 359838810 927214404 97981070 815206334 921978241 54406568 907636525 583327465 547507369 424566249 435200446 189036481 666457075 738631177 77114653 17161360 314694937 857650283 690659704 549062656 885312231 753950200 763678586 671051597 69087849 728334617 56503954 550197630 479133665 950161192 492641697 494516606 472517681 843566703 539415230 310576097 199287245 762621549 715208868 821893954 331768725 92601487 213095451 307058532 109800618 373061100 155708990 810953948 44602797 452945125 629374984 188500207 286566373 671533427 93088717 469075167 788761855 144788503 386771636 802008549 652433646 253184017 970990795 370034265 364778020 120908093 191769060 258857597 680119327 294408755 664193895 289795817 300059360 22180481 812810801 115780771 6239265 483834683 136480484 25881985 360682093 799489682 437915163 670481152 423111072 661374104 29895993 219752309 329031309 559126148 606731077 577445244 788700920 319552972 516898301 829175711 755514724 90819714 182653412 439228811 196150129 252221378 673890567 849903510 45866001 674436763 518257076 713575467 328641729 932541164 419448848 316800726 251439552 353085326 259468031 717961931 63704821 985201647 4810856 629804562 218118843 717800897 553303907 671108666 415860155 363792675 214795482 305199163 898285584 237741537 842120862 933240802 268928047 785509005 574284458 342065880 12004600 342488969 560854404 724178341 288322979 616216896 997248605 437126410 345554915 5828506 84005726 700544081 98008160 554289032 751424415 586544386 576852638 72908789 226050800 852852898 552039246 167047447 766537834 919840532 955079604 115677646 191330720 437456588 394032564 754217915 829198161 340115216 516789440 636513481 628420286 782927445 771356323 599400982 156900265 277355169 494254162 980325671 130296812 124150407 529970562 879206503 774779713 245027864 184926316 304729735 987982062 815221960 223453868 285242765 747645248 710935552 512324850 509274100 546237359 929858248 166036686 895314973 698779239 365806973 895404664 726854490 94459097 803511789 908520362 389567209 518245822 417963190 356009606 997786323 688829612 398682277 653728055 578305526 428318256 305561908 999317002 754140068 235765894 552250441 484226184 7104703 550550698 179033162 113865772 976703815 469347172 772321141 788695939 146808332 326872559 403053132 143178841 566211097 673381121 71089229 182269537 384073844 584617155 392314623 435001041 902336056 188399165 65336554 698457393 396152593 740776054 162820125 141988518 257594575 453040263 749217772 925814594 774767337 772431259 727887109 502692310 681495764 90963758 660776994 41991867 358412355 101384164 739754674 801958140 196104326 683471160 404327624 82109887 508120822 370094111 562742856 234398957 992952195 68383859 135362209 285381004 485042277 706461382 599169469 820173523 247927084 675015600 231459198 346447930 362695893 977231400 589270145 839580620 42560263 757520000 317475711 374678223 635551586 701045707 618231190 27672579 152079335 290602926 418141107 105441026 190635027 991990237 790882231 881954616 765240717 611483284 809866347 971829987 44725637 601685990 95523941 920689928 281193553 567769916 627564184 472657505 15691917 557649807 377857553 252437615 663941681 96240917 543939117 117496743 345265558 577236071 154545753 124358985 871279921 577624738 432692855 922047595 404762185 827314925 619228411 483386126 461478771 178388450 216052371 729069953 35935365 190348248 175614800 909362370 328455683 320291551 702271456 703846447 598215870 383219134 899859313 583328098 264272918 22407408 903422511 789193016 26947761 492123986 836688482 235565556 416623871 219112264 701132495 907210507 331310115 75396832 683692054 865240990 916549067 411595409 501654053 454442890 642984004 153900423 774810013 61711731 242807430 510234208 72871761 115303918 310371197 699545753 304230455 496391784 689321365 124387203 960359400 246403834 231849966 417785951 474061926 524713365 106038617 39975907 652743096 582900177 837161890 743486865 667675925 257961111 524151083 528195480 444332517 774580248 522624721 259832859 122823461 760079418 226670557 193527917 346519566 970031827 420060090 495024559 128339111 62027884 878099962 771622803 360501654 630721184 871071798 30283962 663095116 978968100 792858321 387491490 548603182 846449696 959916097 373209351 960363360 898912417 453074861 440448158 804732052 764906805 989134660 910777323 739729501 864335852 451422531 432409019 193049643 14447003 109805696 125783299 15101213 421574736 904742217 399063561 954153712 821271844 604073379 694866823 464232412 333193518 768330267 65915601 44013779 467699009 143638904 957254180 421370413 112792700 373381418 325832969 125114973 923190880 402157125 193388582 418046166 330145840 882063149 127270384 726182657 521947646 218105248 355045118 902402025 979208102 683432889 22149288 518011859 464531369 806587519 256382553 424396767 758052455 700628217 754928977 507354017 922638729 806218599 197866903 16602758 985061178 685733527 657490130 867025732 375672896 384352433 766433413 15307776 668325579 241075486 881399871 403086179 929861354 98709052 399174606 294800279 672903588 362683531 973925736 124476975 838841022 299122375 123733830 339266646 873762553 530676048 295540426 426842362 796947473 395871997 850078960 427016874 836732524 406953270 359446966 337975804 152357403 496379486 216822133 344071550 786687454 99313978 165526320 609044628 92681135 166969319 651133620 678000497 94320406 729284373 274409840 340825561 602487125 232881397 778051962 760211940 151677585 981210253 59406381 364265347 255670436 320188238 75647522 395714826 393351971 482224218 562993154 57199433 389082687 669271551 587594366 321990970 58830591 45056001 463936638 755127285 852533460 475949688 775486702 206916750 604915824 382406606 672662837 149629926 657675280 399527779 19916085 121602951 190993679 498293837 455837917 745480158 731913050 356442706 137164972 157060814 765050567 708135434 411016603 741123935 233323084 494891305 10229175 425017685 826985872 348897144 578413774 79481728 476128698 608337396 579490327 174136605 946939604 566071370 480917749 396657075 198022680 383225353 331406534 705413658 261322906 305090756 525685912 717791533 580196365 93132137 624282133 178466632 6324972 150377654 215294663 800377173 413211999 270282889 202547568 131982432 464517929 689283349 874138906 607589506 766052955 909551507 357616869 879381493 442438250 378399729 479399717 890928842 810455014 719180149 739097995 425621195 113967916 487729689 33404429 696185742 511907479 247912835 33339993 306195442 729289319 753198466 521959442 141170263 469999400 789994648 325848452 240000941 632806153 436775613 866871895 229867771 835765615 489337395 136157370 184030299 602705560 970157336 392207025 447206832 385593924 976263719 207407686 467267382 793716250 927735068 668970745 329319309 877426770 23075324 200052026 335741415 260538114 326378395 662654750 495201369 204275212 833689313 37766952 150134922 121862437 41105610 23735569 93683442 459174568 722577435 43729481 974907002 443508274 770446731 806760890 529905541 999717790 654052253 494720201 445035933 883616694 958127904 37316263 672091987 922745679 332580931 757779324 532136233 905294295 633030484 814931688 438449794 383944873 858926704 527514837 926136575 844115323 85180609 196618049 140295105 145293233 719717308 815831297 773541753 721835098 492984237 832848231 626701481 394049959 7362132 225472674 448050681 437847316 793557746 808308897 712868643 289731611 381922696 204317102 855170849 112738193 497121192 208144310 146303294 301570288 645177868 818398202 967713948 656768729 112935968 706438250 69386661 724281000 74799316 243425312 159522984 168860261 377617883 189281047 894061107 190662276 627510614 46503726 413949058 650119673 223925770 715422713 505365315 692609615 712802819 555181978 209231893 922944787 735821124 753848306 855517013 141981324 488796364 999661518 561424882 810424541 948202761 679851634 408131893 717066152 66796769 122705728 570121406 526720055 213039120 742125741 450205280 690518493 829952833 170547697 321847976 944129535 586736716 487434218 282542102 791676032 272290417 917008180 34065862 305367562 669099937 248699845 198069528 123755016 702817673 73898686 790706467 915689560 729197340 83239677 793179397 856452709 76011933 758834248 81225062 945892599 767430660 16045202 575982499 696208003 805363505 856418671 497662268 560188313 655124817 710288051 326682470 802156684 362827177 368162338 210797047 987612745 200141244 916654751 832424102 282093822 912601283 444558495 519753425 144495485 4473686 308664761 694415790 201733949 365593164 784276986 865469954 803290706 545580614 99590239 456933358 311782545 94050982 954078814 976932095 967736784 886678420 562615411 430360705 900025311 457072816 169280144 253172339 944997584 376543172 140952710 886771372 678303571 226195225 444394489 744296348 799847108 379040149 198873859 388491938 621419271 498867357 422749727 577871073 426739366 981474172 542701064 93099016 299328182 162627848 912721649 203657684 991177763 898191102 604755417 774154186 585296093 665414484 896745682 864948892 390978979 264858685 289671250 705534116 154488568 414105830 719742369 335813284 826717462 285456368 588700715 719737085 246049414 505393900 314984934 371386497 914602835 969256758 290780057 56193545 556899380 397575814 955820656 60304058 896538367 896338818 410451917 698956815 348580227 986808521 467664358 168948317 50705815 429087678 390506185 462675100 677019839 821266234 367262300 78510266 869176929 618966656 60151571 647985277 665341477 129511835 370496109 649844701 807125692 533679292 159309575 433563890 115048267 285755794 815749264 282236727 266563392 85388115 324372243 666739776 819991995 145295730 887397121 7746679 265696014 479296497 334538340 843313998 76646627 415073678 316614411 405638842 271510831 502058242 147111873 617031005 393112971 109089405 252598489 286315652 576616953 392173598 861002555 95624060 407833332 142792878 332694130 664246558 418967588 92885680 67263215 660964555 751779445 905553455 152085353 787241286 303798963 153850817 380538043 907785641 792348942 815070884 931452789 902146685 99603710 811431876 862252672 20951190 757178544 403846711 261921701 872099753 530149123 202220645 872639575 564379591 968365556 821829981 709520414 150106244 496729121 946335994 951980287 236725681 95507628 915622781 518110381 999865097 954610293 387893568 496870250 595816166 100926580 213701024 300972557 399371609 359818513 229026554 124338958 526829944 71762761 549403696 865283213 312639798 941130035 885967615 234564819 874762784 518529730 246571769 179002706 222930359 370423902 755761835 17049684 951906691 749075078 254448324 655493042 91259120 351171441 74213739 792920509 30439992 313801820 817661728 528146242 598472809 74481372 957371231 240195741 708129824 529409912 166568968 355199797 27340022 248792862 969247102 663135586 170727659 570824776 592872079 744872570 108575168 863993044 115953964 864254435 701143442 484027403 134577622 793075248 384551791 311720664 88497340 86553413 718055517 300893220 295987858 858646523 111803063 921963603 783985785 290886249 703488232 55462837 401341038 329244086 832800705 768815263 197881366 181472565 711573476 680038279 11707906 336902733 724160970 421317767 477268405 561671309 950119863 60528586 96131257 815590864 271772833 656238201 41804025 165256803 477261936 17137467 402748990 793929900 268798650 501628431 544628237 40061056 82847280 161872503 597680418 609594215 632146419 425010354 527577555 861682119 13288553 952203126 126184317 288266765 279078682 10788914 884619701 494056250 384007582 68248988 620602960 265825994 949619347 793474448 37067091 729849201 46317394 720645773 76799528 26916467 231081940 459655707 509863436 176418152 844044656 877865158 403290406 798440141 329394836 80103079 758704191 692754262 558797713 573244236 770510915 266543296 181944358 804338919 670463683 954438891 752178732 43670196 344939505 478347653 425954289 411580140 398128347 963141494 578782751 535334831 252812173 419883902 18057183 62244904 279827088 284482445 16271307 67609039 929850776 603388982 772903998 748208071 930564496 572330769 333116950 918132128 447647092 592420659 665840900 427878368 440146077 289459258 293314435 329074096 799989296 234938785 50796682 762695420 9592887 177842666 429021716 172374262 878464560 81323227 49449204 316066243 775824265 350791454 470300941 581589358 911461043 744891791 115229719 574211462 775569780 574863685 862901005 895712756 203044851 367253066 325083866 941671523 142060410 165681012 809885691 39660877 764178270 674908075 701077758 150396941 609844698 697954320 44452213 570222250 816396830 215579652 199426636 392464787 669119877 506445904 577090818 405226501 299728165 939194571 330389472 879529485 248119521 680086606 325952455 275839372 954260808 7843850 808734513 978887658 227239700 984056217 298035225 328411305 567205071 881786766 283026229 544339821 936086697 820811073 15313925 939500907 975455097 324848606 132492534 806529050 546530328 718132851 393000083 658359613 272106487 160861133 731845575 990652179 721601590 318698889 137806061 853909042 666105537 572252271 552842855 167937019 78451675 403831780 288266425 29539479 187618751 858512852 606503699 118293383 491946879 7215813 761534287 772187540 806723411 261279436 318386791 561072852 466504541 141014023 521427829 959532514 234923914 428403999 31626506 355487749 758514814 474690398 492647799 507601480 367495447 844711926 455572916 776739822 626064601 925400047 556904430 368411471 75223005 880547121 313664889 746033878 58746372 559799237 585328892 703481149 465997529 408554817 802391696 887672856 705304498 178442686 152694061 600027313 682266406 831948628 426900058 581006480 618583881 276543252 665396282 850890664 879561849 468642193 181752949 92494988 29850262 594620632 787524401 492651766 605104032 696392385 379161729 33553602 614860101 776891778 291484690 542067732 123592692 203692330 42838496 15299844 902175190 964574982 449753009 608976591 716501490 60390769 89042338 312631356 483996581 908234599 480730559 521514300 884526284 337481695 470717277 80220604 534641598 232889994 904665483 571030014 827936788 265670010 921678883 912153891 195725079 460576360 255385504 654443409 289530021 419966644 963930922 509673111 598093642 474372869 610878878 738432971 24209 456280438 46865573 187509416 963701683 613357539 738527456 845366171 344739325 927649893 836292730 661135002 670333966 308494260 654748703 626581974 483311553 209800429 751415477 485690976 156219820 401520839 811621528 608451721 368768336 273164552 753123419 506749634 107950046 661196207 790928208 584053704 775396029 720089827 915233604 935555856 667970593 228208887 234546483 100485917 960154060 183985152 792943426 793433798 355543570 367885534 602643499 310451891 223800553 839954534 622250879 640241334 671792169 536180197 678662510 428897984 684632210 469317864 22995914 665744972 237731113 384091015 640493981 602144862 45716253 853511625 703729902 901417389 861175340 201599064 59642585 147735668 686740858 571979206 280132427 84473853 550509144 129192215 11353863 470509134 658193775 160719073 305007712 296942444 826357209 445123797 814733407 493814824 367696730 484965134 183490066 186109317 806227572 598637986 463181908 728499204 103442257 637624991 831974870 321506703 627527241 932454643 71463265 683018436 540595872 655905823 616598263 318245587 229664819 68870067 824191805 61871582 568663074 987141167 356110376 941894591 253239091 330620869 893918607 383713480 412318718 923638370 91384978 332207745 75855596 530931936 908702397 284538155 204100146 380685226 939800938 566622158 202439238 36042362 460827315 167319915 595483964 911830876 588882266 79719026 718258039 654158953 514789526 288618506 665109699 107024008 418325384 196788752 17222492 344871836 412472962 888483971 314044785 472526520 378433574 263628254 270241200 766108890 151659688 453062578 188876299 754521047 505719384 68201607 18575438 630937603 97884485 401924515 369867758 646223064 366254190 514416192 723698096 591171238 609368828 748216925 753650909 638297881 195869295 627434271 915885468 142201673 13462768 960313496 551287969 512133855 885512489 304617400 343479969 350092608 733318885 145967793 128241926 483430378 793982609 932806834 141963431 812352503 961007490 812256090 183909026 653936463 231961694 923041216 992528225 78265009 2122112 881077117 689849387 55892221 18390898 862478426 800509522 492196167 906157060 563538921 102188618 997543674 183116197 911555785 8431850 199783388 664530400 589261584 789903699 613288186 794606772 390194010 227027838 255355637 928345319 899476705 621375204 479970783 439604749 57660676 536038621 830997620 953278647 482307040 897428460 840890121 350721260 177930670 231916128 434788311 589919556 417825561 171870494 135917643 828819585 608828292 378234113 650340159 574864130 976049616 205560355 752869428 843336467 981824366 567589881 417790886 128918618 656925857 12013447 775718985 491669914 25962890 71592420 653295789 931452968 485803799 580107257 281009595 493186285 291187150 128208063 403052593 142931014 976856228 34116979 200358677 830492846 183261423 448261027 466215721 648926462 650703596 378790212 271585210 927505028 731744104 110375467 5063784 674692781 877029700 294310531 78210704 24647139 798715988 362468660 391669916 294286272 296125337 452954338 21315492 841473721 738576731 202577076 886459098 604907139 229526707 733319655 777595721 753490162 22842572 962842674 480504316 701255800 405563923 162414651 414253620 266420787 598622325 977201521 720910359 224938312 31348566 82620490 489015814 73972276 575158092 863496538 938182548 520189269 860092038 139885396 857887821 969173716 146501935 568219778 590643104 489969870 468504245 14055993 206938315 100063751 562319446 121766555 55463450 430133803 855006888 454057064 291740817 50369989 794505016 124167019 729465908 399496551 850225109 107802414 198965492 514476612 27306876 44427878 187102942 668276750 28859071 67796192 382342354 248587136 808191074 744975421 717086682 439339882 616651652 632067492 172806585 257616104 824950251 424051379 481522945 291640915 712057763 888889746 962272171 686104015 599043365 263233060 265446763 605916331 262094886 254361647 791266112 370750264 594330856 433265352 440889997 660153275 665371176 797830713 866545283 898742251 871766534 2739055 218202884 812734039 887792481 840346571 55423459 48516634 821514204 248948059 864624416 414740894 66600631 678886654 693679289 491749692 684809338 604094155 574456328 824103783 236729614 649344217 866609867 707432792 259668729 810064259 424803922 842707194 990058435 38986276 14235060 927963398 175488082 495624051 779213502 540599687 244174803 38806250 385352336 900994625 28560389 583235213 524609204 430339074 981043993 898925504 986714050 425952318 755261270 148118499 757702338 242818088 682746993 113774102 134832118 927032800 483917923 321770085 560130595 191070568 585186200 708479774 428710176 104919985 786466298 50164679 335418072 706239928 843198808 973020704 9164304 865097643 450759981 587528520 179697490 327676771 221195349 855581101 489368479 752067377 769768386 821679615 1368871 290601757 681323608 180995136 329454287 823356631 52036955 992318040 281890770 391172277 151223143 44422079 579647239 444103676 161556543 959566416 437939104 864290367 733883527 615517527 770207693 277366931 829375895 59918006 972030504 285042276 947081513 38741723 951757544 628520057 940713632 112510326 482703212 621164311 994240005 115831663 630724146 253896738 632747228 915852866 442102078 455379501 151026008 319154647 432676279 611674762 921402806 791675147 477101744 570389195 937015573 548389797 527618337 665018212 507437446 260382419 826892586 875605574 459917103 514789521 570514541 897983228 10213779 861240602 625334245 850399998 801209764 9019874 42632012 452159713 438175047 946215907 527019480 514809678 411329152 144639167 576507006 198414705 580943149 347145597 596009328 300092447 154512298 706256765 760154368 868780945 404226290 812751776 929511919 731553728 757591661 872256705 142556645 736435115 529264426 473549284 8258183 211953008 921986106 712622477 591555920 22950650 637497030 623059031 191857239 664584263 309208155 705820262 538678484 917781254 304805943 872835297 397660797 811811106 996572548 608708553 5956041 419939325 635841566 567858134 782644229 729372165 732355563 223564772 22738928 517044305 574379018 493996838 41493160 702506382 561662396 184304784 831123808 410493591 474279026 423005843 41283931 675829544 671059145 778570038 481564917 31631368 934068565 324654520 474355070 918150262 413999268 245533946 409634595 225654104 597625136 702393328 609907005 536186291 514084209 831415313 989370122 855406026 614218660 121868214 661509769 504826321 586203262 867474826 412645669 83171179 337729027 108714567 881866692 711044799 328768499 679933057 399082368 681736600 68162269 522958583 758541885 198360501 219513986 544109393 657167136 418667105 945125959 566020907 692687157 330919827 460165708 386137453 263757329 851970187 515354289 205366890 508189929 649083382 599491894 662091566 569718272 999253814 332780162 775482380 606106806 425936806 627851085 476384305 405887614 598863194 918858570 176463496 76522131 488160563 234975156 196832393 245151369 33210214 569452349 386986560 848558446 397901521 372305527 726040096 164618667 564475384 974348665 935841926 9867766 408598255 957611576 552774400 764495413 435222816 731273182 747509852 4352576 966352094 641763137 662424583 369160799 961882387 156023815 936077878 533229473 250734516 569554987 321068035 472394536 171499097 404540497 630991993 589735222 783447532 30831061 72246792 428523987 584423377 59128857 809504051 805671139 334969891 161738563 9919345 808139639 883325956 27649792 441875011 778333972 793123023 958375454 73009544 256502048 833563717 349635222 579407802 604891483 932289945 786688764 154311628 299102380 405661512 910459867 823168101 227533584 510657164 36370212 913760752 945576479 707393724 73432673 17038603 32737118 176681755 297115244 491791736 525941167 825443276 332461510 498116494 398697924 702014173 13122218 853856407 841284324 430109799 741014882 770649162 216607783 291101281 645636945 176278950 471534893 429395147 972651111 993209397 128226858 598289526 245821532 443075884 766241077 186897389 782613250 431115361 646096321 328843684 229112176 409169252 531631441 62864827 89880965 931814779 801511863 884187444 962876066 18436143 104685899 984487656 719565557 441314507 87421693 309204502 820274232 149630128 895346755 921242430 13492108 9678441 443529027 609393718 135453486 957442104 800656339 933446907 707374140 356547071 874031811 472526488 812376830 603288367 551799969 562973761 99856835 812172146 829444975 917895228 485770782 941601218 464994678 389343473 443878950 297709570 650967445 935248755 195998009 639735195 715138882 65037991 393876447 417826088 667793276 878467571 925735588 201623441 643034359 725137584 207369620 106649512 761849244 108191130 753954730 173702139 100605703 840694720 212093069 39376276 77546094 241439348 85844005 932731115 635499566 831484807 943419356 239473784 560477037 221065989 292421099 495339965 226250540 93492948 193899394 20163022 196242222 615998679 8528559 897180833 56714730 514042925 116793589 116116641 436637536 170536345 586416493 20916249 581434836 682451781 352269275 866625976 245103895 875993016 141337500 903163858 955368957 385684601 861059205 586799616 493563292 474734954 300215087 517748410 20490357 272470109 478600267 749227156 778664922 519976085 645784594 185840272 440075449 636049054 490711395 460807377 673790967 92677162 308712239 969769633 241240858 935426177 766085543 365069623 894455800 820329105 157889105 323300488 889453321 238343848 715340172 69666197 968738370 59727938 468315508 185236283 239170066 2505197 358433450 389981357 725675320 728949156 687726656 982089642 310930066 373497231 115494125 670746827 676102033 877645937 815507529 846664964 888657257 869442444 464171552 367171314 853076388 59303912 516956141 868970447 272217328 585514673 557706922 216115662 145781560 838279292 684670485 775836083 841411195 982611034 103422944 380530090 484219990 793717138 921016879 394588676 236811474 226347076 33364386 527349991 621239651 459683679 82077643 822263242 3190606 977056576 679468273 779960503 76734323 620043429 643096066 820740396 696080380 486265679 473378369 138289788 477214652 95188462 464426689 856898811 35168729 981777572 670791317 202871272 61369052 33862945 508759893 289162223 433898730 298113663 220688377 93978108 713529709 679981525 593578815 195321840 127665187 161149017 105593955 9852695 856484194 722648551 942475412 380963258 664288310 559763495 215363091 758390535 357818286 590998661 777652452 872804384 544990564 555167550 338014029 34189157 179642249 410179906 752280717 625784801 475067569 16444693 894219738 821508870 355213877 13437812 420042059 956958519 631597209 77987822 648402969 467229919 817178274 391552122 943259778 998558047 267259015 285197682 107010447 817248284 836751320 294551821 89997230 253716553 94394750 438606950 452111203 881242785 404598186 621483005 654166705 52816970 557359471 320386159 454626543 774889629 186136719 537374598 675866341 676584552 477559071 252789892 245239442 253771759 305265823 242442990 734682180 322508628 671458390 603520270 252511458 9835934 855980349 434683866 959478699 94668448 621705586 11325171 728617940 965325084 906859112 19344532 871105901 962137539 79119701 257625261 406773031 761829875 822955348 894641351 27482160 145204542 673002717 59110757 837563792 594526897 855940996 585432651 69708865 305199122 770442509 278769668 994182488 457989979 107538870 543775731 876201565 667682015 118937391 370880848 21529081 947268839 709485651 178321431 328129019 564401850 600027422 325944204 258065273 176194874 900811305 935440906 352762331 402722837 87720655 307827425 82915938 762859413 139262803 207886018 283626174 558211414 559592796 200927418 876463293 177512802 790539854 604119417 835986422 882108686 168724805 670852203 72815331 586542762 364683250 398453950 541566270 422838204 977811827 290327949 915123091 833397979 646038366 43787624 552809512 37042714 549046783 595512010 27795142 24590827 652887022 619006605 15307344 211329894 400809439 511166712 473625771 189924183 274780495 259249441 736533166 924162276 931261435 504538256 332981268 187678339 47885427 80529545 750556006 169496547 955136986 52201967 665262158 575809461 614273428 21703010 469325104 242977415 301627021 621732051 832663132 749712055 235403767 165191266 596109630 350371421 400059239 880885593 508035777 514459538 71870076 193860328 184473457 405551163 678524264 310471494 342375110 287333390 751237221 974816302 574529212 244630198 849689947 725069991 630195301 54595713 385152621 130609253 451477765 736266711 234512169 360559075 491968528 899196775 122339885 38240417 820605673 226189198 38576652 364522930 836020485 163279001 634084538 297437432 585277866 146315988 562400567 459885367 178315388 179824830 317297739 340857467 612603470 593859524 407166042 547781397 551373854 703303017 84553476 959076562 117279060 624336214 535884697 353715451 310151354 210548726 997064045 91110932 36806425 849657961 627272012 134388755 464819365 814213778 455824122 291551621 133593831 243592246 708742854 27264759 937892288 215946513 610222181 917457441 393491224 84444912 866190285 1668552 474126100 545843954 19351391 231694255 570699808 466668650 57272604 640088727 147355595 670394979 145958051 135206414 831074991 709764972 451273035 465363592 268267516 732442557 823970868 65427408 684938645 94109958 721309982 454026651 302213260 264581379 468543938 44625453 122956125 411533163 808065022 548835626 958657007 933534577 800335494 732862822 498901955 706800092 266003623 973708323 635610095 454903796 934293168 842099715 756984270 387238234 959509027 379074410 652006503 1262809 183649844 611214364 749007867 454493232 904205449 441789201 383936666 860614640 392642276 695134251 135398047 184084326 977221752 446399470 349345899 534665968 388875625 736239511 567360313 876765559 60029284 693464607 475175842 73077000 767888993 428083100 866222142 953931323 799165352 893111268 270478602 195579839 965032781 503917451 77313547 605413668 130534707 554205185 353732816 205151726 518983682 284544562 608776352 583537648 40641476 686690270 726994399 224062897 610526406 876771082 675301798 450690237 544906632 864979705 907172116 394709728 727237920 666791743 731804915 796403747 600349093 119796665 435891399 809217737 981421168 759014853 306187919 388046576 953494409 391583244 729594631 758451320 54156312 310028250 727732588 204408484 388957174 90284084 749439058 641372115 239314384 43177082 955433741 337864781 673746319 758779645 526269621 307450405 450119088 405304842 893510036 9141456 642664111 821826253 818738326 97896521 802051398 684728183 405890513 867850547 740071972 161424532 169398346 429311978 282123683 68580854 733114852 861794911 862396602 487484450 282017241 191412587 724094746 343579962 854011727 202985358 947946040 441372732 339577771 875802271 147022131 537598789 852324201 215579648 186004801 200078385 146662075 929654962 929903087 820718525 690625828 164298391 631967690 245848222 769415118 736727636 534136837 104156704 780586742 203235200 691326201 60129511 610949874 868038575 221661779 936667153 120558469 835640883 947353284 166297244 499298366 385483426 437458776 591703225 482042651 57388920 51400242 602799954 63536786 667407531 362747789 598643580 957906211 97678389 40009771 475361642 456655261 42753665 336359084 536547826 391914290 632614977 258955941 869374464 227779720 542181412 139714171 862979437 284261577 386818854 858324387 7163056 614605244 722444874 823633475 254728417 780072111 317824067 467999702 959179552 710525447 299594128 827509593 948606611 381804436 570757631 388271785 232976971 499392584 708224888 90677022 847882777 472951804 433871188 495664121 154388750 813219057 493002448 372678892 169253598 482665174 196733407 444593668 139380804 296122911 413991493 286982119 562116331 254709811 667956170 966568880 881466243 92008567 489730107 164471482 917605508 745884369 36682457 659324575 302849855 537192742 826595293 95523291 453224415 675231823 692984402 110597208 777426646 431222966 850854436 842928079 488887769 83488797 946087614 250864962 111677431 137371575 502908419 472781157 28721853 301224658 910041117 202018931 169151741 188419949 201753988 172291507 73960743 970683169 951664593 878785417 516375777 318011280 586733190 101216990 61903885 895861880 535371354 590871130 640806307 137446793 981410187 531871526 557015678 677539141 663075750 488375790 819505629 63288349 331326140 570530379 401967211 205422399 15002662 898859984 110655464 253325517 139402074 480959479 675856904 916066928 408219317 785550698 272023828 888502512 174631806 360086878 605545574 542852207 122182533 746957502 742930912 343708756 401283333 811213452 258350283 625000552 117402660 593173248 622023641 117630677 615970741 610233522 797667827 679007509 375663550 803399156 400590055 253728237 854243648 455522365 416323403 158417496 320101393 519074947 118222345 583153043 893810713 727755919 520076357 362842379 144810044 572916310 428686211 901279066 325354216 433094073 105098833 78279640 522936664 211106839 667875990 114385988 668498501 378352823 751748672 852034135 844894096 100876167 25209291 855807652 790919872 615318881 350000749 958322902 704772187 967132394 181700837 845114447 245776546 584713123 287176323 255842013 863409875 114009025 304423445 340728776 565089814 827922985 289840290 19155447 599388938 978077753 471365198 701877631 307201457 386943001 283147045 158213862 314585503 942489978 763484024 136056519 763602137 876170932 175447575 656742003 827695132 243874578 881598390 469555944 546076679 149026164 319834312 336117432 917889977 494005613 594095712 225313920 991970928 701703399 523400552 939768054 794837316 674706811 726187700 33616364 204395171 227930208 930906899 918394986 294472215 178533304 675285413 240516761 263629064 111571263 81925229 67002633 890420354 228377335 298437977 976360710 108343639 109468100 891779811 572076666 200741907 499447003 47363364 958087288 858294 790919406 77880746 282501451 104297441 27796456 189772341 145497160 45673215 649263011 109201474 737534456 144612578 887645227 500733400 543073375 388599689 742892220 988433734 871879234 379993730 420471882 900277086 859159209 641388228 571915350 638626468 903483041 161942720 139211178 598854589 353766893 327695760 427490023 508428341 634566372 478961661 58370955 921863349 613462313 263062205 268801832 337600312 817924971 199572715 445620141 533422008 646511496 212512709 916400227 825020656 868539634 790587708 652519894 558307645 858309498 566276471 752781513 866398176 538536562 82763916 559667926 692303265 498583237 849179147 798269254 595436794 771341815 165314973 431810758 7598342 981579304 120013073 885794527 50593111 196716986 93713256 300004314 243417307 851063928 491405838 125752567 598976644 338149349 306926330 628049646 349945625 872883504 297249276 412659624 466777060 784090816 74167845 397745060 21721869 470799026 661967850 407234832 897290349 789529419 551759656 936404778 351316893 743909157 255492355 930295094 770178841 735911497 518687262 140063867 596500681 796566993 762971213 567895088 529752236 882270686 566307679 530422130 602595285 854054266 172919716 221369681 317034887 405442940 761254478 621879818 254003421 968270015 147290387 733889621 527197500 156061740 553980310 224529291 737171513 955122266 230436241 981868363 51533285 66893831 930698220 442311561 183995214 435906503 678608165 660247375 837894203 691252284 824594920 474976238 854987474 143888194 922625055 576351890 798305203 204957409 130618424 250131741 968703408 366667915 300067765 681550888 104813017 222871735 255883914 548699700 588630152 746435253 433886541 423523861 259743003 283127027 82505191 750402586 423449924 820454331 918145855 324545484 389686245 944470564 208826313 770789963 208910870 733192476 886523282 205379816 65827814 712647474 855316517 554480414 463009135 654153436 481382439 250073682 665281188 876507263 371861872 89290788 268087742 347643476 971205686 209011463 880422592 855293132 130629414 657511708 630599719 962840503 392594402 427454680 655363476 526909545 773716109 754315197 657563828 860257402 194291799 340642517 929190636 349224913 607391204 47216675 395716375 897273761 725341886 472446025 861932359 620143384 932056268 227030672 218818679 412997610 590599632 172551674 209382161 624623048 877435940 670800113 421768850 645826402 396805011 66916558 145888051 390290505 788626853 618856140 834391094 7615569 689324750 403128438 871576342 798006619 284106473 922927246 423274978 505232304 700723966 143430062 171490529 453704134 986663927 677391164 840779561 401118218 21568129 28375058 882114852 979155359 48427207 238438391 477894152 618790310 252321114 502107653 652698259 881584068 260325105 448639707 228830423 130818593 880453936 965205866 130325891 572067147 150937786 847398065 494299191 481578284 616440187 12186827 850700598 592807523 400132862 171278009 243051730 773797872 613954188 778216850 416554729 283653320 962724591 841897099 739286051 659721330 336297722 53602421 216011285 119976453 407110428 574890544 339117758 33669068 156643391 526512817 67916590 163585973 339804686 63588264 88941825 229093320 242248134 794868991 767254624 486108964 86977049 82572854 230585642 602091715 62069282 562445462 806017492 312603717 630991277 850158732 984101516 70833479 598740595 45685344 327492823 828622831 87974935 974994349 898363944 637360318 475841015 229511256 169208806 814067130 210897250 458738379 906432321 603396481 527235529 765427260 567231137 829774664 757702836 521914693 255495297 236939009 307464964 729246706 261938496 523737898 290074722 659405854 663200049 581647008 599099210 279998028 804835489 936391226 577619305 424398866 11029813 408443986 767773477 897158530 417112268 136371571 930421558 419147741 891629875 219341694 729186279 609497706 159067458 823818116 59409860 859499300 251953541 357829777 233706466 646867790 218460316 469169037 609730274 733419944 326536289 567822723 341397872 251553231 182222127 566326693 924837553 707365584 907170277 368670347 592472648 350900970 838688086 814933684 958786771 268608333 603015865 721915213 156423799 472604716 615102022 962392637 717812280 448896262 431890381 840894237 399704844 634539289 908196138 301723402 936217780 955743182 125651958 707412712 599735100 213682353 288171564 324286040 37665372 844602215 204302234 933448118 692205926 768733 440144147 966215963 58441730 598631812 329740799 579481084 923478896 223704901 84556172 305923850 688094438 526719955 881188231 512371961 926674681 323526628 913434329 217016993 4113859 914336574 41053859 420845865 235785420 113053437 646695024 477572643 533038419 470956575 581271871 269317585 198533566 488107520 229304730 588010178 871690223 929261816 238949798 14051248 119132256 924618737 169974969 45970289 113214867 363692815 715428033 304863031 21894891 816130305 931651261 140587065 469194602 14822802 926270972 436199965 467808577 57524840 665668908 974792063 827973258 351381423 305116107 235928929 805494367 222468274 677519273 870129597 912682075 97728668 97847589 631832814 617851137 117428862 521125315 849531929 686551493 380928419 981300384 921869738 60960393 238743477 798909697 111056658 49030975 450953167 772695500 438633530 536002630 403694404 476226196 4791312 258125040 516970604 230813232 909447066 862253752 837452854 296755743 330669000 552605494 27755276 639261464 764279649 518913805 997697353 443020338 634845284 501489149 528926135 376682972 146788645 390638220 562959372 116211235 353624655 101748864 355263555 305458075 414258027 255730022 292767952 319512576 706933178 642761706 16317301 856333259 293152429 910320261 613518449 988730366 771605793 177946755 559532191 708946945 202449482 467261292 249462729 488020811 978595448 966050261 920214139 313845051 772858777 388140466 70238171 81060924 685018320 38482460 715771555 663258089 224490821 95961075 134873291 109295957 58654192 522997653 120494255 938946549 956124509 782417172 504828466 706333506 814528205 284207355 599682050 398229207 968077200 495629580 453894131 782671620 347419982 146944595 177212139 774493152 681315075 711730517 329981599 637879159 540910288 135356861 501873147 842572729 838848161 170133924 804613261 140799839 85669799 677732997 613220989 565268269 662814973 352557143 44828479 853394714 450816333 779262068 672403915 501228456 499488356 699085271 172428605 245980502 289411144 152890991 152802184 987761600 178378722 884701433 513902382 718735576 322323302 775146127 823488441 886461126 192929055 167926315 69798991 407044477 846236887 457731024 344266095 848870010 782806486 198432183 718484250 662518574 69993708 301212123 435140064 198045009 690847950 72976533 379916915 716606590 812406441 275445889 191880861 528722204 658849458 3065001 250895858 315051990 550396032 101389448 38983737 916087557 166653718 335195919 685405201 709559370 712249036 397538713 758183569 574505399 103021738 609636716 856215559 217522680 126234582 938612797 830607395 672591519 286509439 73668720 200417544 919527203 72005116 595992066 856717119 788144997 967281713 677466055 610199113 60155858 732541081 14067675 954785187 673910764 775241246 714632113 569280135 596011403 605531970 354706262 658139871 214950731 516207879 799044343 310431931 436496106 265245334 898460633 403610055 398257152 330514268 68989915 465706472 624000269 750864075 594888587 98635993 886374454 730300002 572685852 195386277 954116436 750384553 236469214 444357702 347728715 310969527 300922993 988497543 461176193 616799921 10086229 156577203 373902450 154500437 471852763 102706601 277841728 568884634 886990778 850664238 174306557 342775749 169051102 20905662 976973852 927985820 419186143 489571137 266664608 914157313 52388393 73306536 350794482 64934449 240103081 916624528 191075593 442500739 681637926 435666423 893697018 138364562 618103319 379520849 817679742 902282601 661366185 556033772 180329871 850844103 132242029 416100304 683712268 618219784 827107534 905127638 893296738 388734232 776592933 41595896 147192183 415944051 445568915 393254514 132346403 988271945 946103940 261747934 811412852 823460444 519648218 641259946 797252757 234794027 519695089 758190021 303134778 870714086 304456215 242281246 505540257 107401131 754084513 369833835 409065287 254174116 454147930 151916658 488908707 269012906 636702879 953643330 946775805 622143271 304226641 853360285 783209775 958324214 103030007 977966742 116731465 82546287 980733350 489717032 708584391 758365647 135127554 15516424 94416244 872434749 328394821 680796269 181818405 648405511 231136980 993944112 63387785 451846689 276526998 596021049 764790160 1163737 272187686 287855025 317875781 405198640 826434166 733207362 574234293 7947419 111231277 48032300 290256428 231777383 90345224 600358364 493459420 221785275 782863309 909465858 713357607 606988772 18059935 751845764 831192907 762625663 100400446 183807384 105945059 71888980 766700775 663843484 657687483 245237843 40491497 106972392 339826858 748529412 643829844 990306396 715960613 463436276 763119243 951288700 831596020 364267879 729245911 136507698 460140268 415173576 567553295 734005911 909382972 955316956 363136905 217794857 599365304 471084955 84859877 60618681 629561153 129879607 717776507 636394089 984233807 946020216 797154322 254167723 202617959 120837123 836761920 923903258 943634367 584446592 814844022 30330223 380876360 367203545 265390730 458731116 612839251 222771522 516669205 952433167 677333232 669328459 199469482 981037966 773630075 967097432 440482304 106637711 998990109 947238851 648695530 983141153 351220192 877685300 119462726 936398119 966337215 398548145 295825484 21729992 759621605 704305376 938115764 950391601 339272039 530993312 129334456 29329827 743350728 321777210 856182158 974838001 991635542 925484410 648804736 817106410 935342247 240259470 792474886 436597221 594621951 616825324 437682800 864151361 523856991 447574271 898660687 902513863 90022655 122781670 562561776 717893095 896486648 585259287 17859800 383359510 515670187 421921650 97071020 203363156 813343467 546128525 560592508 888347189 54551170 262828792 534538798 376650776 702935828 296503379 569102647 529715615 868510902 193672869 685283267 709363844 440455812 275720319 153392519 248189691 106890030 101928184 628843850 497111961 138568736 323590318 292832058 995840453 809841062 969236928 724793813 33239496 961148758 285446081 255727536 904821001 878455047 485253889 517349538 746855581 282891578 340833830 683824089 384163132 734879653 817676249 300126814 236812539 308951368 594892640 66337406 694000558 322119001 157973354 215366391 787458865 646560872 631272025 160346356 619947604 279434935 709687958 133010032 17510742 523743385 315924735 898697202 159293896 626867217 653033692 137719788 217658842 764807050 505475518 877937794 332133140 216046209 824840365 486198449 40152708 70016794 260892539 631662022 464044482 850775575 705405773 314213928 537331698 14863268 813053866 972916277 519477755 335548654 623140164 283954951 263054617 169571427 666646856 620087379 591065092 541696777 590283758 292267922 479623399 790968288 592945214 26028509 751361990 256603743 178082347 313166076 950637712 669915690 580466128 836404623 133258896 592505403 910116170 926295223 202025560 72148446 349150160 168243212 201987154 753421943 833989864 216192572 484278118 589433624 36016222 420924171 312067050 884238057 642981063 247367688 357091323 306675028 276154558 382070877 542225500 930624981 460244802 91348930 167197059 692488350 685567926 757862781 326899732 149487723 816189017 762105375 712061585 768762577 836056249 969802974 447218271 579868665 788939111 130678896 327717154 586542342 136185839 378161047 401283958 11918440 756164075 565023892 511564213 504642429 307030971 478812552 934927794 937745756 445020453 284065773 127460798 278450286 892240283 672181393 77652509 915870727 656613941 451828593 421236431 377842866 189501905 755863451 86729754 776723693 148265811 434159624 582545065 37243452 501917056 227450426 448117040 932743310 111140430 250069744 538096532 771093278 31924074 818460438 526748203 584156595 66533159 653983611 49544962 512666417 860733897 234390382 914544056 370383445 219099778 982438392 886998667 186056640 553928040 766554888 418883640 884550319 192428848 152636789 421986655 921092692 295344622 992522932 717246615 269195445 105125592 648684621 337482005 389432416 406321726 575191402 340916723 158316277 550274771 316263934 95947544 295087602 956403450 652502769 169838836 368654665 826183227 286083296 575568016 728523322 318568314 486678530 257440594 603846390 654670473 397878345 954752966 43231332 93921186 997661084 352311425 799034118 692520668 898824240 367218309 348858691 421718725 256505527 542118776 793289722 200279845 450282647 165715662 791506955 16413593 323642910 4867016 465443429 654390795 655751995 691853836 218472586 74673636 898330592 570433670 178665363 842198061 994168560 441775607 430810289 319794220 263001891 854349264 72432315 890662140 228003861 182427463 79966949 840745011 71347380 266506888 781245121 372582275 948016088 126262022 742105542 679387887 332429198 245828326 228018682 315695963 780279204 618807033 543758542 109623295 556793749 250965543 713059593 322128359 611636876 368064304 645129862 354274532 766427471 686845944 447904596 667118533 720752918 56849292 533837675 736330245 530699460 653961816 338603458 166887842 885608393 465762159 419399679 306957311 456742509 425487406 820425999 110923753 272176671 527476188 711535822 346569876 80562167 161464853 977639608 821281992 188132606 215264144 570722691 666367451 214099413 521817457 361209485 242603810 336125335 310318107 787052766 593081873 238288360 575551936 453391555 730477241 252444375 744214815 487058346 147151961 668615646 852483203 49532354 200476128 621840384 106249375 299482361 300657559 548228258 724539852 489217988 129980444 162756635 244118436 416020200 777753191 479744542 240062269 839844023 866095962 672946738 885345269 859019601 283279235 258917164 680923341 424963455 972062354 734273571 74394433 240663090 114885426 370862994 574301600 344155025 912904787 352610534 320440265 135892496 851548226 650316921 100384701 778621612 614421235 939023442 908255520 286324696 353827539 424175990 192661234 510274960 977694558 307797798 6349922 262526217 782268321 859972815 73276684 299213424 810436274 682638999 498444067 210121234 829044989 295238590 33430767 160202897 753866873 565657912 443270180 948716202 204364548 608054122 188994816 903165700 790644738 43985473 667011110 581314324 657605006 108033377 529132916 553349714 540292991 750993000 238286468 817177860 945911224 801473052 42656010 481504952 687844000 398250939 17918233 921844379 622013488 229243093 279412313 151328901 985791466 114435588 150734846 741328952 728291494 651822434 427482674 187271863 224779312 916940810 894236295 933524988 97295410 793934682 241562452 45720361 899061149 975927963 702179291 758685770 965234785 468150541 90456584 697307543 705976107 481287672 63939882 688619470 349539257 218664653 510876639 760497063 845546249 984598091 775975748 135708163 953446488 632428676 200392028 839575541 565432247 580057132 287948213 781161558 878282666 676868992 566670377 193346752 151922680 472083399 151040768 187406194 975193945 963974842 129175428 922286569 238324448 745079127 259845068 903256592 904658724 614381498 572907641 430569664 230497943 522262403 985317486 328264368 208017951 274474090 172161510 821221060 913313517 947560006 393265914 739389193 750419499 355943327 939711718 430670379 470744856 237413710 974954759 252567279 875905306 479709471 330258397 531059838 336227236 627995934 842081383 728339222 115958403 152019228 521237113 627191839 7795267 339442738 328955849 47237705 823198660 479516125 548238242 260208741 489383169 634705198 177949716 287903936 37890784 829976434 338827329 535036944 988881265 800435464 256472166 104464762 338616929 243604920 708384662 588877762 886008821 223648845 239857228 732867407 539146452 436017983 922300852 64661831 596125167 999994822 781144130 313085969 59582653 920447947 636989113 924457474 193487539 468483661 131651136 975337135 97620194 806758696 127909740 544939924 793205040 870827966 57896437 193320049 95533031 481039707 173166634 555359774 15047082 864713325 252172513 778461761 594023989 219771706 115523636 176845671 154766496 925306348 279089364 186030992 645312605 159959148 962050577 497881060 810892157 3052004 668417744 383155073 429161381 111322613 900792708 980574191 634849783 722827391 116246792 665200652 507714774 245653714 503346499 961730728 537949090 531605721 323423476 569174124 11260139 752778386 979313185 603752099 167437715 63583708 753927369 472636201 995807344 280086641 334927510 900388361 259788881 593948177 651239464 533858529 339051904 625148184 104519442 159624433 394016731 820472416 90602983 723028443 408346813 960474850 246272662 301519099 432370614 658717066 3237607 629941037 191461443 111295664 125516796 861709180 558495290 817070817 976441893 12252681 310069814 746721812 101732960 569735291 350701135 904315369 123103231 470492558 989363602 557006123 485079668 160965053 482108968 775698317 970423149 382614317 341656429 637230587 162915085 185145741 51753915 30487430 132907045 364650064 453026679 571224665 872838699 441043934 413599450 407031772 534147386 618488210 891484156 110368666 170066812 655773873 394376518 906806914 18687773 347222401 881408125 802199844 276398457 435758409 669806000 20701474 660675103 973904941 6354856 518721238 426439510 633301850 61889201 791127823 160313860 626880809 260419911 957753744 122443859 986406630 816551321 848418095 541164513 8153173 764206323 75800339 306533144 747446705 521682896 254273108 162523240 784843594 331471395 713664333 870468915 713990767 959694842 82639298 209705425 545013073 881955497 817770341 147443050 203533448 280027498 790302219 217019204 883149919 969096454 859025668 655622491 135828108 473673207 960990250 706087801 553030931 179390642 169325972 105874443 322887207 525434433 391719289 613281624 119093335 817099606 199960349 170042489 489891581 782800311 35576290 479348213 635573064 700996329 147888370 847248394 725695726 966240187 403287873 375603205 428568507 638764247 296518423 33862274 352232190 716664874 974199305 601286996 944744152 102177238 270719724 500561310 487756751 939411444 806727998 148675496 590476882 39023627 69267754 795580126 666139253 741069577 69390399 308213837 19241282 835581701 414218335 589676410 685814335 82390268 691772254 85419946 401229102 557218332 632614851 286313389 189923590 107837222 930876923 313257605 805254543 198916652 493047896 818464105 125210926 567054714 185207642 344534726 556992259 488583026 76520247 232345599 591001169 211295372 660665700 893037815 630524671 905382696 888696573 95001636 262291066 725140421 382500841 942716295 213492252 545546113 709339977 501251589 167766365 837951283 264569173 958826814 971542958 3904363 597487069 84986462 327394476 848759584 233179219 48970473 649949157 506053739 78904127 481122892 60916855 390268341 215835728 800080002 71163300 246409592 779449929 821566509 274440991 212937065 362267796 53045990 41668925 300172151 230566739 451686693 88359539 359084520 394539017 60410833 493813426 759878101 399978828 709438284 132193542 229361880 201175163 913775746 234229260 670065455 21598615 566869784 712634469 222434372 785856084 739590037 195606560 630116593 921482902 635408413 859146498 703563039 597945274 947236565 208867608 928472710 257505615 323266852 284423271 254756942 22540315 511611163 635128009 468946128 86355049 634986656 27477015 158023762 410783635 838357544 6387789 63244281 46134970 42295376 994863128 192977688 737177721 479046368 383534997 479935441 598938242 918432337 393161679 833477183 327637247 588137355 908609847 268897956 403306522 277975612 418915391 686533165 686354814 928282579 860108065 900223418 58898225 498066627 486961447 770002039 673079567 162057210 416849687 239902955 831436425 488086707 217958836 644154156 93026505 680299991 891983756 343819688 335581184 257624050 58098894 292340481 65281033 828244333 916789567 531449821 281885329 178991507 796302811 391590756 303667161 415719503 364439626 429718324 919959049 645513496 49959083 829340843 141999702 208129835 39281768 630288125 121125822 591902241 443427826 188743841 54784664 751605266 399156335 177135704 418494062 448109688 996154846 204447985 155081572 73528943 703764862 367249188 955508995 557898892 528870950 385968721 445141958 366988067 338335491 13744072 583098420 878084778 996560159 405022180 236126152 786456504 984436857 63289362 620828992 400560461 488760908 979768672 580833255 210683584 866368301 753900151 502025911 928246699 512437722 832369653 590378278 893557998 157632014 791559249 20593259 376386335 554164365 389387072 652924055 543641116 175913679 416552555 955523014 295443978 714063648 597535851 603644822 765474625 683183294 805935411 685839732 992665874 891826899 749685275 491048806 441283965 745750098 243906367 811751971 923524179 399705299 996246853 466253569 446161442 532395487 718603211 974159190 791236879 210597153 765568376 80972117 726020665 150857121 555495765 516562113 640395725 412909749 70851093 22388056 536423012 4237215 815137069 360740874 679497357 755242964 645489899 152337615 528494762 235717569 173269132 710473316 696250141 223077880 543737223 790621792 216909191 327350371 752230125 223124795 759846387 418927663 682453133 879300894 220263081 895222767 218252850 129914133 599449095 532465563 923534588 319611162 71808734 428890871 839370062 618613655 385283520 40908017 617142075 143145878 204830259 87407841 959460046 517865767 868502726 143598299 480365173 72992857 699909038 489699694 589427299 921382485 491695323 114518049 998117794 940884037 850246254 998191407 95189196 181863444 547035982 151058506 601102894 815479098 777370333 216729382 759028405 526159868 302661900 721107379 454985958 711392834 65727029 773360819 302656843 274501125 904742833 75059790 228834238 532184505 878356117 570036920 417854958 500861734 809131977 366756183 724242792 479726544 489910118 118308406 489350760 248705524 143733953 573032050 680854840 857783589 601362904 186994167 951942306 471377177 369782951 849524284 868057295 758804153 127578205 264144368 91786942 857705674 134429673 679830093 955688307 531844012 513963474 228781978 130860320 122561708 842390839 69065887 173346037 256998465 70880879 126741412 178972706 509288755 18637349 433885668 145003482 791785818 992304387 924097892 119265869 175128062 798174501 984259898 762711623 815349138 591839599 329078640 82998749 265962891 494992527 822998798 518929058 965527918 163642454 600071170 373389321 37186866 132207510 415857496 37291486 603717811 27493966 530697604 923726220 190254936 289375793 25513827 187875092 380060182 465327393 731411922 352713640 366331485 649097397 639923079 950017699 674076790 917731910 490994012 97624502 490682635 925647592 32967867 529367302 334589754 566922897 525646569 748505804 350398917 417261657 624823697 540227009 233187597 999288471 619435894 109945853 673922524 88298279 857404357 682142666 922988028 975556274 217738377 116358273 937762222 430749080 375709383 944603902 492456569 845593469 497320255 522675470 94314887 412145113 609761266 944136523 18173556 320963690 538679620 664078004 317063542 278323949 573974388 815702978 225454682 255272445 622968621 291656107 987573803 837633217 269326553 422517972 907315899 341830393 75261358 811848380 267867646 76091977 857227551 153864203 483647466 101036121 84846303 23395859 345096957 372135434 267612236 975326087 417246852 622404015 823417540 247830001 875552158 333001962 711674719 666045749 800406798 381842878 653429610 481447823 658359870 186064952 812132432 480978465 68226729 271608779 107089971 964303713 784135324 64811037 744804971 120220317 165446655 976114676 737023325 471356345 696272285 254678706 255688544 534882012 558426127 786668068 671025964 314611446 669997578 604722714 987226944 944007199 978623159 185030190 945084857 625442922 439364327 232494180 388637299 173955459 339255907 86513889 545890170 651719533 915840511 602403667 106027370 20455399 822987183 583481281 178155881 494866673 796372131 771414323 499342798 324380068 732842112 538694185 393336640 963884816 777274413 710062461 935747356 427014652 408906936 148593746 635207652 457569426 284462201 390634819 934092462 927827176 916911396 291154176 98814688 532630953 519751873 772303407 31786032 867440590 866551125 791075868 616907541 833203416 615566345 57913004 308548878 43588669 853627484 454976062 690304309 956115519 204178837 701985266 346650455 279776390 72236175 846283228 90278900 899317130 765536790 897063379 378783286 436485809 924105649 354528519 773548845 214778393 105193516 729359461 545709828 191988928 772629107 230804750 896259496 635814356 62132011 755853349 931154038 236702762 510906390 494361310 600068028 99920535 445174025 162686596 589789291 403805961 968950001 477228804 539482974 446420920 231797867 475273836 544273350 749683042 318201313 765848147 622620249 312436457 79778740 705836949 121815861 809912279 59728385 571325380 551460168 423685090 166827904 888117001 338580147 442680942 97289062 866914830 912462102 51896716 792148689 341489380 559102179 771892066 76044507 90815764 24348347 815231559 209739729 294208846 906466473 224597386 346147461 211371741 375458637 701422536 716485518 619783302 554156965 393221301 37624676 587411501 993062174 710020383 239713288 390096250 322632458 547267519 617008521 214762973 53291854 647520903 360802427 757596964 436220966 438727951 526336548 228104810 246681646 163104002 514642539 750939226 589243373 689063935 332746464 343401352 510574404 616571660 468922884 682352796 555623676 265751875 352165801 900785330 249483701 776246506 990791319 626966045 168771101 123742452 16401114 432406417 222346576 833503947 644741956 199233683 672526682 860291011 889630069 87225993 740183640 647822303 924805152 54988224 887421516 167962446 471005547 789928827 826560208 960622194 136125545 60447637 823016383 564559758 944147711 639783972 680220327 206190307 515900835 795019192 259280320 683328218 161334707 215533853 216490081 569487358 73391252 106508412 994922357 283666492 22476205 947434663 769768185 374038086 320797887 154049494 245898526 660562265 181443179 342910489 670377612 391160558 972109418 609511463 704925026 624177624 683132376 110277374 114261889 134658524 962782979 667894233 65031899 654707419 369027080 430006643 312635161 54395531 883274521 979192244 16725926 144928582 729589073 418743145 579611920 282235730 259706475 59172807 579190252 597581713 628233116 374261038 659583561 571564082 996100627 778477560 471022959 837493875 796868039 184093253 848744821 760241494 913474532 294769393 210823577 718021492 403515333 904757371 643587417 457661991 323469812 834555399 341795069 925598814 972211360 842201007 809308935 919008115 599702364 701963601 690115291 223211898 910828570 92640193 820945471 117082711 939195291 584423018 687327030 275968526 891605979 972535728 136892972 369086230 597313604 51884783 786991461 559529692 286083819 103521829 567092393 232402588 158542027 567004580 703768663 544272657 591709137 539646599 335180958 866010085 383773461 100836615 319490101 674488254 254934490 842434971 305188668 744235497 500109397 308088572 523394756 164007325 170841054 552638684 390843785 970087831 797753280 671714403 97775094 671733141 120327214 759503650 586269563 59828830 772504068 919330476 259664176 632374746 46384378 163191256 778613121 302365575 69420420 107955328 965513489 978964283 950920958 262346449 55551333 354635892 278593146 391265899 654402674 443711033 687621240 280799205 571951653 936791868 46403637 922351044 477604603 616108547 493810146 584743499 797862098 15873147 426813115 731231988 653463089 956359202 76127319 584571320 664543600 528133179 283557771 774612449 89274015 797293246 609507753 473296882 17742581 696045297 33623969 550127429 391174126 652228070 819564469 974294435 254911814 282934762 317441082 68574024 374608928 640137273 476348000 657827758 671003100 680206434 856463420 519292786 938513931 715882973 610802728 702669360 265590628 987799785 654706786 362713631 616693964 98792604 190570997 952482057 2912628 980687432 446126913 12290278 153733753 288836129 272764738 64843553 744796660 323461077 257612211 504061607 374113382 866076018 381048510 359914960 67874183 793916683 848701570 856582571 838152567 765485477 697114689 777953094 172181856 664320231 187824401 965734673 207550884 471723001 303093702 25242941 947162122 997889451 705331263 425877810 846373096 887446417 52960217 982604332 285288410 18050897 172542715 588199526 921863361 95405233 471650531 740922858 452923764 135236801 27325417 679241534 886215132 652767716 442392167 517028752 346471396 672501739 901404351 695896780 918513343 668560778 977480852 773259027 277571059 569741033 271685131 960692948 580984916 760684470 840075451 11388118 233532990 175812216 607192309 708222390 775472566 726207990 483952947 679091108 349395124 112315435 391228327 642643625 41173983 19514071 738104286 510671824 243139577 858549911 888089797 978088249 591591855 17755458 412837486 153145713 873893821 467973965 951714542 878710105 865138298 342556395 706902421 291776666 874778400 603174632 370888042 111068879 556727688 982726217 238682464 403616722 552942449 594499762 243881227 327860356 896593285 837025475 470692394 430661340 413996090 992872756 913329215 67770526 282675642 543010233 440822077 656337561 848069730 409062285 288574295 126217343 955345525 193341421 676652546 857823008 290238560 998391535 916917116 260486481 454442411 342111384 259260709 34192101 197338672 157890794 400389325 87528066 383948677 151359188 635357251 901583050 903577437 402340394 315053034 260887062 382823726 737487525 200123928 297238335 533863361 533602159 261462611 33205743 855942201 190467791 850953640 318277283 193508491 945957534 456532593 85041354 600596899 850290235 688794825 726513078 744799920 634166150 134960566 168940683 984184148 248683975 982584043 373417395 982236505 115361337 208657564 25352153 259262495 124885879 50344743 403136309 778452269 989289111 687666675 271765625 503999674 584775168 592044648 81992680 872301768 195861054 677287646 453317857 645311504 799724458 729501188 761954204 546485065 742346717 750291049 271674009 657026737 945664071 407366353 730586655 96814898 686809166 171477387 549577821 530885847 377429867 62427015 262993488 29832564 689279597 262058978 279994129 473983045 249116557 280356061 468717765 567023326 210467671 148565068 835206428 104419325 441844813 529850750 528771441 416145616 959387017 193581318 499954045 852523951 497811529 337689162 741656782 980798422 729094727 622082584 550868981 821949882 246094034 655823162 244230882 557336327 686514036 573681291 420995295 359232766 496050245 850424333 257067577 419960336 628188767 292857511 662742007 655803364 248866013 916969487 637084114 720038091 404446658 789229763 603552114 291636927 503916193 57046013 410149102 326224576 270493812 168610411 942167878 279518170 634021243 71423973 719231708 766511134 901436391 456089621 546087211 127048764 140747775 15961886 270030700 805138922 111278017 550643233 840653508 170899506 106228197 981774386 376223330 375850766 248525254 454265085 138474251 845188459 860303852 158322037 976838478 513366193 715474147 325004050 128916311 239068014 334843367 761792234 636103759 53339601 633054320 658534018 730933305 759907432 873172434 821336728 546514843 940488214 332901240 611207952 341293553 539874942 151401166 265840380 77719058 773965623 533139717 362182791 818010445 830357227 300029203 260635304 614549355 693776004 266089082 381653595 96763997 49100428 863083432 749195241 513161231 542020589 163408571 547438744 468385976 675539793 584257914 555453248 978773234 176785154 128698849 268842011 202003537 565100303 922022188 367413921 540598982 380455222 991108112 580520918 661115622 568667921 658485102 547693329 879659799 819493184 367216078 697606127 465137227 176941983 266908360 215170196 198157842 570840048 535330533 474263984 666058488 462228200 561724776 179761656 352340201 957977821 841093843 772391330 150346926 363667763 112703359 174456713 618961642 2185919 71000926 661963276 967772037 114672981 919782089 358101815 362210660 643547638 847294388 847665865 80344769 271106088 76606560 165665842 549186013 90490782 554253591 754058962 406022504 38181300 784149532 610500041 108917444 981361868 909534832 699729496 29284545 132341076 801283537 776305298 556786991 777050196 627258221 568329597 108942378 955732258 230395817 206466882 734624603 394192620 643685420 876613510 812457648 574982456 526848937 620819596 207595436 30222242 99112801 805784567 543238136 59415479 321700494 249862320 639296188 694841944 315203246 305944017 452504206 32592230 628900322 388265691 189030025 467796900 518626834 667130320 35376396 879172922 195114563 324782182 408662210 556330485 650009048 674717967 557383834 361635066 174217436 997186924 838016607 527787098 798774160 827499208 349435145 985774694 122921089 912783239 275554519 992224238 823856895 438462524 805991220 593157555 963869812 383381491 146869680 14570422 222090088 140360452 470528778 335771035 178304856 22554404 498046119 21580922 782270093 478838501 254244953 298813427 73705663 691892754 361424199 799479320 190395128 950394385 901524443 483102681 409138239 787121329 477501974 260296063 500407871 999999373 285053383 431225425 962231769 210889744 674289310 224213942 814474730 829435484 256609457 130728155 380769083 57764035 443128220 593481376 492840883 10390848 406849809 183464987 156240006 976885582 239829552 23820871 195886934 596277469 493388905 491483217 852763827 54334602 879795258 261696559 75276729 971760533 591166542 710311949 831497475 30805539 326429262 954030371 475277382 714489512 887156677 513124347 916413375 344060271 523832684 80179133 215868362 402896497 832884446 511816602 726515973 491417109 804210690 542712315 538004697 431592428 999124613 73813383 29822394 570889042 412282830 905568538 887834767 262707944 385430957 678515612 442221320 595020929 482861132 120686067 792209007 92536949 952835348 777995629 793069396 413232229 403149501 556899772 360672370 759555104 866930791 888878601 116549785 671687793 912243673 848398984 933526676 520974999 548757250 624470802 624839756 462880350 715277 892099394 989525010 454196014 727675579 24534663 526868508 166360859 12964172 23769610 155866098 957886295 302128001 614628747 537325466 439729274 916491571 123593675 472797691 130433493 110616860 680409345 153475059 895782381 636344389 72632997 150730062 358578983 122811002 365287813 143208067 715485368 748112764 112143834 520023082 571773910 963564858 488021366 953563834 758417611 586380137 981044454 825853899 242417891 529692525 458462128 784087052 212505571 489711805 507700406 877599602 290590276 441552022 614919433 280405948 77151264 710539860 747352621 879122027 218926055 697262716 707761936 217692739 692454732 369729599 716753608 205383932 891339174 287230463 842261198 702800932 236581339 280937081 805529485 102469205 13604387 148911042 473101832 831859571 281103238 189034513 729630621 927588149 728402957 409678658 444911200 319288637 212731074 856653466 418018527 663897593 381760386 341813249 73550436 535076300 540323261 586491451 26434412 273450085 924269902 643260076 670185806 284000885 60251846 885924083 126110657 24042417 633479043 658959223 93653599 86122287 174736728 498979278 280408431 166227951 816364258 353183490 742188971 248108360 405213834 13541144 269284334 458021417 940416480 714813934 740903762 43412360 234785650 121549858 848887859 974586964 583647544 381277123 149285673 972433194 248456356 626741379 856779979 898827486 43498400 431041314 609009930 362797767 569309416 651474711 616774278 788221699 43805163 9143705 991680737 600559863 134323654 268764447 371228717 690165229 541895479 815952325 281813584 11207316 96414961 971059654 582042171 330284549 701204070 371890926 101143927 886714971 298167308 54648898 278215603 734577333 863852322 319752328 262932601 910210944 222246911 467158386 870233556 983593860 511588291 736260976 246240883 28369895 65851529 195894072 135185423 740737720 989864355 436456060 633974563 388677269 445827768 759131031 550671866 924583094 18108240 871611488 587442530 733767964 683001766 621693856 134943133 612964549 750920362 48748928 133423433 515262219 291713749 109098983 487688432 855685652 12293640 28713517 594996563 467630466 774495215 977420296 767184235 377211587 535855472 539082959 262027650 236841682 717704758 375074766 677413866 826474386 94093317 95716652 806977095 383523136 761828759 836569970 642020077 740194982 678274215 975207544 109264341 603134766 393442387 834922226 429128725 276892812 611537810 974305848 261805236 33574010 420942005 586200678 737532390 773848122 550759826 415688217 486550237 750577629 8995983 161823462 533644254 459781956 826467109 246380370 770351134 751487371 454976130 15973557 237042016 709503477 866102521 395348613 509748960 626912218 748908071 942485837 465308601 823932452 308258655 75047435 409455574 525879929 825701267 683207009 274157203 437749387 515047592 215388644 800988980 606582962 180526578 639903266 862794603 924775597 245816371 980806688 285534581 931780788 426244109 749523414 687793889 112169707 292754138 599948234 840183769 379202580 41831899 75073130 42783817 319878300 775683582 881480745 989031953 620915384 276756503 497453757 126596930 403276906 440533909 886415961 288701778 508920438 943283491 720787433 752120670 250892320 130550735 6114707 5328936 340372631 957052997 51061654 45487671 454271548 50027370 576732671 493151705 786172478 725816882 635755050 818755416 901927285 465841045 522602501 159521788 738954482 586702848 79313771 298952064 544167375 45876252 273506523 262469258 726799682 605826273 57892692 85224716 851086795 43198696 601452573 795915552 946274440 225008408 707097982 347460641 58364014 71389189 861095538 967641496 858484327 931633195 287220643 694635144 893336782 725150078 993647211 690415211 426804610 723894528 230643766 305735451 897674572 463968099 953951861 911476871 517631283 534090259 866593779 367664415 644186244 265060240 969884270 867711875 574337351 411970906 175203497 726866482 80755362 457540152 67751109 71063094 319100932 991175643 476351329 887552156 353137129 592335495 906153664 155738354 775845243 331593164 904244122 354555449 684806644 80723736 959687204 29993071 652084336 725861887 570556952 880014533 224744599 480257375 448582889 19342425 618448459 864027829 328226700 807869120 533587520 822131655 60652933 807476529 136601877 895318500 960746997 216075128 471368436 862052746 665477238 854861688 47099728 702984475 102777019 145254043 332953320 710745651 592315912 753288461 799962321 861212802 980200755 527957400 74214770 727029880 418533242 784889963 40234201 651860237 647501821 284896137 128003033 766709427 219867155 129698087 973991619 604136228 307063695 873081218 335040009 74433908 772452637 397574938 824406835 75824778 393941724 713218317 365695275 418294845 682017151 108947504 980710548 649298348 694820770 847918179 300164042 486812470 535861332 801352671 796735658 801815221 781488652 568209557 139264416 822257668 414480585 199065879 659307359 299986611 415242777 700121160 536876932 514404098 133107581 457878445 254078954 463815583 810822604 244004407 449816323 353801738 202293548 535203678 786722624 678719639 790035039 277719911 571065711 795390473 137965543 959069288 232422649 391432143 658975242 271242648 429391986 764258017 834167626 912425919 681435749 235248723 374486571 255064219 638941765 958225894 438568247 818765007 323835803 993753853 801291110 937313627 21820853 406576430 768659307 76302788 121260732 914385407 154199801 644390807 429319239 238331354 224728733 880562969 250981189 526987617 701237857 779981016 520918096 642128372 872646018 485436375 535168684 185322927 314037485 382453177 256418047 112668427 900637609 127860826 842422295 148548042 357008390 446589112 576673000 612700915 211492026 981431024 608914610 873351270 244706174 494377535 340021675 625492334 936907414 596422026 831720869 563122752 23089462 628400202 185374120 209590927 576066124 992136018 456918960 549554816 163278252 163600550 183406750 637994785 823080705 636000819 339647009 237803177 58574918 221640500 485396181 946733837 241721970 732323106 175044067 382648416 287872558 855248220 919770993 408823219 558934366 220471241 750741363 9532229 345844315 149561486 122009184 371473264 55522207 333034719 50016466 519460901 814117752 494597973 831940146 7854310 210287594 272077719 614047288 257761242 771030571 537866732 100352692 494903444 683437432 451490045 191131116 295230408 850669367 618353891 84057166 164320099 214989811 46121541 85773509 609674219 282670500 162381002 444682020 106847038 615494124 8575839 656957798 871701819 922829701 470191534 520854366 978185935 403110398 304693542 657753520 378809893 84612804 955561091 787395382 953713473 802492162 655887038 149204141 159552521 438774364 153477720 244383493 261431005 926800606 284592872 637191957 438655134 255055284 541475897 963609755 763445472 699192541 556743976 827869977 291218785 80888411 674654733 580645703 687835050 896147694 254424398 660800472 172704095 965556768 575446900 89508308 666463368 522985606 48470613 59300370 759507991 129998442 806937229 748835093 301788344 99693378 264511237 111202128 181898940 931706837 814467041 518870102 552786210 383932406 743524910 179898581 780420418 281633079 450667742 447505939 227251386 351627774 235075066 626266086 956480972 78545872 367967908 629110623 206767597 522060275 948510987 677945457 914014800 446654914 63299491 233236359 373180838 295257707 734964293 16126520 633731743 603017690 123364763 430537042 880258915 625391821 854200566 921659486 488746997 476120440 16492293 997500385 64425474 361924648 336266901 530821541 830662339 218967867 238472698 592651537 965150646 755793387 15249154 186964684 734368627 139694652 473160184 300682335 414360476 976981595 632261360 35828229 984524048 329609433 4724880 494783814 867939442 843167935 929253123 717664691 54053725 491849646 358121676 353984093 742224780 761938858 252557527 333058449 455979058 393676826 396606597 916912877 733349649 969513970 69188421 177498527 364084855 261756492 623602606 141679343 291536221 132123779 790650475 149341465 513342958 223535127 388408267 302250475 7892575 202222673 850718828 172285989 808296086 695545510 762565873 900971630 72600477 749241089 552211909 659662111 273763139 838957060 252672385 881529397 504708548 45474043 477528133 12695273 725617325 252389287 480117155 183524979 74163949 27465109 694161266 502045465 559466328 597182008 387145089 443186318 283131059 142507941 183630493 627298858 934978946 188245086 938759876 839199471 894433729 755445581 747854479 198343187 646394629 642772053 965016252 787828172 754146191 323264839 128522101 600565484 89307986 466318081 752310562 899644571 512909825 705956141 941469131 135060501 146394854 212044727 208953904 198892961 655537760 272357644 818409839 68666840 637602974 468516987 211695466 170026004 948247475 363198313 856756033 764395590 171407143 761385470 50346209 825454187 88061089 169798409 881260216 200487135 723286380 878623639 109492604 933626143 813170924 568488330 386701866 680642655 79487631 749346082 693493887 915611314 920645648 173506521 417923132 565237036 270758912 32075102 37318027 329820005 981134492 257139815 368873116 583327754 556805682 422066987 140405338 26703000 186266744 198668148 220094158 482618591 196051802 479751898 429613363 188186745 973878646 448170771 741555311 723127156 611524239 942149149 901157285 528040840 624258985 10377303 287899441 471142167 527256499 77588829 260678419 121792362 757826097 194631672 52822560 871551833 633132967 836374353 876275199 2492767 215622393 804550093 977652434 132372102 698174657 440043222 106904942 174249182 952992820 851835481 97888765 81609615 872199135 78926938 699919968 509050048 555989297 13521503 715621004 858334050 235782158 579579823 622202794 855901772 23502300 985136025 788249068 628170779 975080882 382431423 800760608 623683576 734265813 830592547 906905590 3432066 145783499 786394756 775080070 819143894 495408919 542890963 114532241 714236589 335572439 365700538 32291418 219504135 502578909 415752845 215891178 663285913 584588193 939754586 270472504 882038031 534003965 593644108 437210965 583879497 206254099 124477432 873107238 58940580 874433561 425240426 626372341 683120263 546166798 193970870 289436859 607919849 837056282 7224263 550871609 248276739 823519004 726525863 75530115 945718152 419944348 570129509 373871299 255944472 30785435 714421921 27472040 968167858 357839033 278273406 357875265 48849059 268382736 566604416 711207127 155484712 130331025 198132925 224338631 173741209 27664393 610760425 3978805 504189073 759633900 713632759 301014643 581284689 700758609 842642986 137500322 832240358 638458722 274653754 936475392 403538196 555785030 255684401 733120363 438677289 922141098 480591405 737440641 551017213 921378718 934186659 452785547 791575932 463914191 176233997 386922736 124546637 465676315 909538874 175685241 548023407 984532020 268013343 262064231 977424281 541382957 803960322 16477746 7515263 687713365 413914738 595968429 757265301 653901493 239529804 890540143 49714835 918642498 48121576 395146548 823434222 221602241 994669729 521447404 724703177 966013578 829561551 53016628 101815448 304120174 615550350 293163246 853812745 642210834 506051903 760193676 618056280 773491331 190624692 33806552 751203995 719116203 485137413 275962391 803891090 843309985 597150368 188218093 20483865 837819475 236801068 438063406 770369859 640729840 7266316 835096579 149784972 677840854 783080512 822308895 335220139 372092855 554128619 450669472 799757364 659053994 932893330 890002107 486000071 681285591 642176513 302736444 618891971 626559950 769371506 248932007 830576491 352048185 694370297 934216437 51886105 125975502 255552049 702048864 21340957 957371408 787726758 128318995 252001916 514712002 58149820 270494574 476837739 944422956 528380185 658837752 293276382 780816076 503883730 962488311 467748431 8018110 834452458 691898993 241874469 987340304 686640832 864309735 317089430 100038791 163184784 904924621 552419456 57731928 249229181 407717927 158931467 819109488 915948041 637842375 903038465 423844311 777948724 608393610 406983357 682391456 592992594 665732886 62365271 988429118 637948567 7418460 960438866 743299814 533178388 295835710 409874919 917142708 453391231 918735123 741273121 4696529 590673083 199843070 223669335 276451176 921883169 443620005 283464715 293144192 4241981 295554549 839896536 902449010 700289331 240518548 193385029 204848394 923979529 286650900 488503075 995239390 55094814 15083498 400437848 787781969 211776536 430165561 517473295 9271747 371115514 595820235 71111664 994998862 478825640 333921596 401528436 348507134 169440327 259019989 747693227 199530663 304366450 79373916 840318755 526861447 281287136 977309410 356957156 558860829 827826825 179314276 491977235 352290463 117036691 80928858 271481555 558485367 62010520 60358521 504565977 486706102 695415193 251926088 851917412 114495202 133979059 489105605 85061339 819611199 710305836 921677921 532044821 362686758 168836851 398441460 307181877 897412658 125422847 902995825 604272523 214213123 681058620 751867117 98053653 393701224 272872737 432931579 365181027 303810713 462516605 673766798 420256014 170550326 439720089 438880810 82869556 616575744 867806652 634775516 220203440 581900966 862455740 26069137 584391091 39397806 188588875 862805367 447316023 306902160 471941790 106462713 474038197 665718236 122771171 264511861 13149663 580747302 713724802 125340614 747281065 705668350 791738900 200602898 47477652 845808264 303683033 692045071 245633872 361167926 968416805 710292558 898778233 814441326 165037664 695316803 404519116 433705466 766484559 815558838 718290152 852882203 914064583 232198540 3230388 721738087 261722461 414121062 941919231 720425085 595997147 231397588 159745947 744578460 314876308 362103910 521012353 244533493 399512909 871677983 118569383 202002863 867515746 791703512 648540362 664696624 353443336 277876118 204917099 348209316 30417916 123809071 651322320 517498806 932983499 35861987 27008824 830337101 460067613 987201098 129433881 537125827 31392614 517921072 469591739 372486846 15931974 388587231 702260997 947558823 490752805 449754679 265330348 333728006 292455256 911912841 172821926 64627343 447286812 98027622 852494554 52687276 52824175 794138425 606676641 477894448 131725255 79394346 273675635 273524547 640281596 922835254 568475555 212855221 742875167 446297628 409009192 273795592 198090392 491070088 298590842 393480306 126790762 486266847 55026538 115670439 922318240 679049972 19896817 962599432 992572314 926160241 579744037 166510028 879777059 785119670 202437857 82321292 539486795 45411236 837166672 295893824 226829578 508818828 236617029 465681030 569057589 166838025 839499948 546920049 895059736 413329025 658055148 738015297 148888743 621830744 99394748 320967085 545544324 622683290 618511706 890717597 54979203 937233644 763890532 431832768 764064147 686821424 772074317 668661143 23279538 572588078 274880954 746116677 51885534 622161123 478281904 371284043 50599498 87525962 513675270 561261202 844197111 323590142 263419219 603714843 458261709 339311467 551636667 408568419 223969231 193273913 344522549 902753430 727382491 142541272 133536068 641098153 207785148 73944923 241572967 873609278 751844645 892037628 542777222 25014524 539882285 323499935 266951427 966885913 66567699 795798276 577624274 309225836 902714104 968756485 768329184 728737395 274727108 102976428 660594818 79412420 696846041 722934110 989804096 154136838 990874623 761276191 897803379 178194428 717223938 782627763 233134123 431447533 259832375 609384433 292307273 218754550 974822721 996608907 691255451 61415731 75332623 962889194 549719434 692231944 276741718 113268404 770750999 69571016 870544436 398768919 481590083 492256089 106105726 531440303 978410319 639991897 397159483 787021093 171722569 531600290 582511226 472244965 520167650 371000781 848947011 320552699 980972707 190545896 454904764 243249439 95645530 17672770 44794473 440543499 532800361 622255688 370478242 897955445 454678384 958021772 346305427 639657437 306476756 962024415 63193102 917972268 876566931 430878249 404092766 172433834 672948189 733896376 277479347 239224530 456516309 967506755 265411944 990372272 120338775 526694410 991799746 220607611 766149088 199668648 492598653 616368609 918006851 642745842 318893006 663174822 639047421 194425387 811146101 93616495 256532438 48440657 91070571 773709226 278928852 431619008 436507634 270614527 980765925 313581055 852311953 800020733 144714322 429726436 160500424 30343893 832127963 607602355 517451339 155874080 445740569 730281991 974057320 776367408 110624155 990743024 819878897 817297793 320653213 466816001 358394077 510381122 950523881 43042401 949433162 659417957 616576462 602526113 769328547 582210735 878703615 817315182 235541320 679908530 15109477 726700806 103960744 907242916 715517143 471903999 245409858 278769900 281026895 94043248 380521583 126647461 123351831 178277500 683362694 417620485 728268075 578714297 128779118 145954223 476250747 707225714 167606999 73508770 630680199 770101716 676367232 908125391 362499926 794399912 770023221 977743980 414394388 844106873 65479440 283172495 560015162 102207760 967194798 198148955 852769351 296234348 453864397 396171836 212141442 593813609 160156480 378867256 75589481 68064926 557936040 640721551 928365428 459762258 7891335 226558315 862060003 528819343 253554825 254057774 601045160 173863204 404171468 281410347 330207983 83064826 535018873 781369159 345177435 64524279 37710996 999544388 100564513 736870591 500934914 414391788 19894354 568612248 253294359 166783514 68689705 873650898 656087853 634795489 111629163 83117633 701654470 986260130 4611957 968047414 295639955 699109876 653286926 373710563 62614800 979419681 643853753 680463815 330870079 184802530 312204906 926646694 173453409 616838403 548529379 578639784 26551671 809703403 899601735 906956848 386575875 453610070 968674506 497859534 101673863 107583960 790707712 316917057 814257809 87813581 28789456 969314855 397448388 129200583 96167852 988762896 630278518 914261770 416167609 905583211 903476733 807305064 114134420 771339507 880938583 59262355 550638764 848051755 145992401 51335900 15188300 209968398 234040447 398015712 276892119 233115891 335647167 306922247 952284627 528653061 316845641 105664958 979745779 859148651 344487726 45173933 807048128 767140993 989319699 806007625 995181575 178251178 649072883 791817263 488242801 819019066 826286378 680106168 877541136 268674903 403410592 489485379 478327812 892421948 77166168 878314819 231955349 586782455 339878120 788065171 281742176 54136175 207558541 622566285 128513007 105243252 66913037 203137516 526866251 36588636 753099025 93507716 395382972 206354377 128312729 852897757 768860772 193219161 879864801 408754370 772161657 652625597 745897486 473888463 729941865 793618797 280683389 320154968 261537886 690157370 306232990 605131925 128573730 729114227 651900684 35083340 97157137 739717170 794009671 727105437 636255014 312170297 290131229 885698207 49225738 908920832 153223230 331702472 904959602 109964548 700338441 706802165 243702965 346863324 16352220 661219447 748949778 499993094 247202215 721739851 564839136 449251065 94540986 238465807 363247367 484289442 413911828 661914247 473895872 558847914 911218300 86375917 645709443 944789435 250517909 425455856 777587851 511085106 446939868 906145351 691449768 32011633 61663485 242360449 197518096 523810634 564209783 967005781 663371734 642942265 151474727 516004549 972682406 892483738 182730235 321637808 856275201 220465917 308652633 876579511 867864502 300162981 331319500 531741292 794316258 49449688 114909681 268250484 161460123 859723479 800933292 425247695 523516133 855837854 141601548 72720146 339779846 512844070 932954685 226705317 817575820 321147 610667550 53253893 799549821 216718 444968089 563009830 557965710 908288223 8455004 934118176 172967707 519255963 728428316 559580516 909875662 580041077 397330562 300537610 109049964 591886938 958707256 60220021 4555152 882569318 948524127 617246376 239399197 309346842 316646136 687645376 614371666 286752654 818853225 658062494 639179111 811837208 902600281 551838694 969506257 443070882 17768190 162344520 568997054 570642854 64925886 209063104 355364806 260349416 769531219 72430959 548379253 419430960 125823329 901570244 139931613 206331056 491867798 956077610 454450556 12271296 54137068 76176614 490086015 760869434 351538306 404841088 174012458 552219257 921180239 212823130 671613010 554952476 525336616 363180833 541756491 920893150 836376743 320423926 339422112 994295621 426855425 344260226 104989879 432022976 860011723 480447171 716426028 804390141 151424878 340032736 688291336 652857761 628729640 960742670 708469122 678255878 460217922 472327024 5633125 562542169 773114537 997242001 61695142 248937483 463288883 710775051 515921865 832255231 216143689 977972580 591314525 405851582 708997146 537551900 832077978 195122569 822762670 54464552 90253266 738821830 986402064 470414141 873165184 178364848 922004738 662571811 75855187 133584241 874905479 763932674 620468160 809326513 789987583 101006464 698646346 245090380 155775616 788671677 129491737 760399119 345782901 884882486 674191671 678925989 294760774 294885181 180131999 547585273 660436706 345660928 832578578 849614494 192484936 626318475 355304227 855758387 122236515 787254364 653713872 901113666 624892530 659192719 721680051 130686912 954732615 420456597 264709417 753199929 487056364 600638738 646918973 521449997 790634691 602017467 140650754 957113729 608937545 33692151 97475391 258298832 819999763 93799294 985972387 545795396 992334741 718092398 429852947 772769208 163719117 550316840 1996446 18714266 526262349 585536771 156359111 265712467 676436987 898210742 361972743 642423880 169474030 866499669 7221591 859850561 669625295 108694676 445916955 143890522 455395434 243844284 520168019 127902278 738774926 370986876 632068687 489895476 326110055 117384423 741997013 490733841 540393379 398439871 688906924 958711450 77153538 125834752 336725323 534278900 755166911 19275355 512562478 108157254 380293830 428752448 765158014 329786843 689798872 125843710 354328546 906683536 369901096 355321970 27185753 705279709 29209436 600835001 853969467 658161260 218829914 201458424 614978688 638014328 349024327 368020496 854707988 951009102 852885398 160610243 718945876 292330388 17858540 761607829 231396044 243804289 253573856 468001633 820638870 92297464 666600945 950490591 784374649 304920371 8263177 439934297 754970311 913471382 904743132 901057535 468010532 958488048 551287602 723733256 713525743 205490458 770848244 739365513 192320356 699643114 427962066 56844566 362484113 962325512 709968117 861232612 752569512 971530819 719362408 494762060 857723202 18192458 896507045 812170110 928952438 729898434 317338244 503245506 49914315 955969499 93769528 929982376 178296787 83187881 603149874 622637775 512681727 817437707 992161666 126899005 362792154 132619738 960017558 910645851 114552713 144758089 596829515 323196778 383789321 46644647 217477802 744892369 524776443 928284474 70676409 903579328 343596267 585200857 370472329 807153068 618849763 622228870 762781280 505623417 79003879 538354435 560774807 749382355 248117524 809009486 940598618 644389937 5625441 861871951 737146368 884335029 551310764 226554959 913527156 128028429 202872627 270674611 543622079 605033064 344965899 748003859 53479498 108389966 576019968 242969695 106453617 378807559 793475873 583466784 595957118 502330021 436102309 366334541 911615735 318913439 224140562 655382001 162086094 687864748 436198976 79917566 164748699 972974287 552764057 761706934 693012841 962130578 857004314 928198267 274271099 69558882 662651520 954705109 179607309 128320444 992523903 885267111 432367887 921421758 571085189 468232710 24116369 661662732 438173298 489694892 258913714 751188248 109979785 581720785 366772749 102276426 315533635 619329850 333945217 233837452 514018829 967764463 398542554 447151909 412213052 254053073 234597256 753649494 143319444 681482672 286510506 125883109 437104140 465730611 663682701 763291124 639093211 212788275 258661984 999457675 366378792 117346324 270519162 145515820 613285481 668599355 829366740 687647068 948184406 284115499 816118802 950053179 677352069 125333154 157221688 933192106 666517613 648103935 978044357 388318202 774696632 351597862 780661031 262502951 542142113 29386477 946816680 844851129 996527816 700096565 967373943 974576359 841271034 511512257 634648724 744153674 234987230 639495203 197243221 73395170 840652057 374631279 315439861 256185568 697174215 13618335 56976623 966293455 922822560 898913267 945732026 142804833 836986260 828683321 569040015 6511983 693558685 305262694 502506669 122015643 660477601 420090960 412194955 360364920 958070017 637326677 333984988 796424578 431287614 545863842 592029181 533778098 86039244 888927694 750472879 191128358 174578603 861168147 682924683 372622023 163683233 171345425 680503868 24524480 673547951 902140784 422783133 153730758 292166237 739653676 921632553 195016380 694703405 888451658 499971650 395392165 111865191 817453761 828356327 685001385 93053539 980782604 17760662 626872072 805172320 170724312 54914506 858938034 776096687 45159790 587259303 67805214 103910262 310988635 240312442 381084327 826023032 209517321 360898483 902869599 524557009 39401518 925990620 257743690 198967506 78487246 699749273 640964203 620662091 97509922 251071096 80282500 954143238 93197579 598833053 290244473 889783062 836507774 284550927 97634977 668744220 122617943 43926838 266097048 639655514 743079225 657422241 517673655 604390056 37525900 523740740 535995211 236449093 482088769 649412503 259386685 658032160 651893403 737033163 604815677 782107038 659963936 79790076 82333914 438425290 481589892 260196890 602491937 962445222 755070315 772694990 183054217 677254709 159017523 707736591 641136201 391388099 389397862 452780649 998708635 321683826 80579439 454862419 595611462 713341721 986907852 803037550 343933119 328364468 633702468 723135720 942719700 740411405 24627501 557803922 246359592 715977466 904396009 458700062 345866764 170550322 207458106 375156 521599590 353007238 375476565 871060607 179750534 936700302 449403108 417393052 898375293 342077204 19889652 292921464 256322501 47567804 133002922 590887550 866474428 444476982 476022843 983382952 671006377 575780812 637724941 112421078 449068856 285181369 893684647 473170928 468960132 226649951 222010460 768440869 665791959 361853518 24711496 322626666 430597688 633825853 112696875 777477527 437033502 45410072 303546819 168661636 305172366 982047285 336724400 455566899 591770317 704209391 390897333 157610823 919373827 315381402 263123707 837257290 507589294 496965064 218685672 231936388 391134595 353857295 91486120 351766242 902952259 984937350 677259400 991328188 228718007 217622571 677782440 435673120 893905335 270144045 22577638 204674061 852472039 259654798 419796083 104433232 609321294 468026364 968155936 622615684 17363841 142672451 920018064 693696774 565275247 140570623 499243399 523012847 578414979 740117911 703813842 476211201 616207914 546271816 673950773 634649329 854571065 579913978 344311294 240846680 490685191 457638620 115790151 536394849 11076023 824609452 801207757 976425619 898691702 883958194 660791425 291595497 330914798 722720103 497121907 92847021 783403960 653693759 238765099 888509969 187444964 130137922 329531564 739403211 193994967 197621052 668053390 171309526 292814962 695072032 61774121 533944618 264620294 219117959 211470993 928797314 828939158 447070924 548723133 69364712 748744510 104041741 413878113 45939872 367611488 128615597 650329522 136004362 614037521 17268663 459834744 464229780 810486628 169727895 821235942 999109073 243185386 149993950 76445364 506389024 586406538 659243169 797489594 708561834 972364375 355185382 602900609 555787917 412841141 560354881 675486336 901525982 212682602 113629998 361637974 529090618 706461542 315169091 851905953 382824702 257089594 188532377 485820139 547917944 504469754 838379826 23586562 95798041 274534651 133891749 760387915 847965807 873882845 489881118 413042653 493466538 448889955 964737383 779833264 312261377 183459044 237532697 834375711 638464840 194435328 795371723 694711148 267001368 519434808 716444361 477346306 984529711 585352113 130013117 274510222 96061796 709214759 283077768 669094418 976061754 871278135 36362869 643667088 655402367 136952501 690857848 149849761 66454830 173776337 730140419 984350088 317956232 414695119 962300301 562214237 867670443 550843613 945414256 992066367 873570243 963194302 472463032 334416024 333952683 293846553 561019595 255455333 871477608 769122866 739736709 967770441 77241039 512251734 351793168 659006265 201519483 51611494 295868845 631284712 770363634 550556544 618868800 574082525 362298786 969693974 618276018 415319167 868566809 13323671 268137510 531379531 469813923 819527586 581099804 231843079 186211966 199731666 343606670 565483145 790690902 131028903 936236825 835809008 633273171 233293445 218874813 296864409 886818666 610905327 584912580 465408432 685675680 900688576 207750996 404754964 21363053 808326840 364510390 281423270 174706004 591553851 457591096 575476371 610428309 303016861 301393758 705682385 212069283 534198168 122504941 921209660 673595085 149320564 416133235 313030955 652584223 758823760 998575198 860690955 350312816 224369454 577640256 709619562 675995084 581745260 394483365 639715276 506182651 220629192 661019728 248049780 175258037 737415113 386831169 944270958 829532685 317135619 149226259 916534425 244699741 372244054 246313144 691138804 508807738 523501109 864791838 441661133 457983872 373872062 396215424 893302718 873116303 534315015 806678997 469021721 467823863 203913289 918107909 554751953 600913777 33309188 404449242 12832863 752766292 210567541 857617378 44866947 954313855 461059792 508077822 981884851 229941213 756567722 119388105 658139906 604611402 17201375 982889314 916135339 586994837 731454732 569828952 622427873 880373601 816986560 525342766 735092506 74252358 597956864 565989516 730925506 258269953 782660742 865451203 859959891 258222228 300936939 406337923 668630966 943679624 132477385 882388261 640186869 709622116 703282368 663096749 125587303 799490762 730971831 864785018 690140128 621072193 958101543 951113458 397177865 432110133 534921290 943032680 470162287 261506880 376256379 233948951 68617476 513991391 947248133 90218748 903539212 405826558 233987125 992068823 508045930 415260691 618736846 428828500 889892791 847048460 326036100 733552772 798461939 140078154 925335717 256935803 162284346 943486607 573649505 464991796 679397890 643568941 229671557 255831242 9301687 959850025 982911411 649593750 796577183 54921084 367967443 172460302 561722544 534529214 840052062 907367406 451026328 563672737 247427331 728009513 592240788 366246766 115709104 544523174 498364217 706042019 577069579 636502337 367968315 562371045 723972324 224344572 921071204 476260901 381928780 827821904 264698575 429564819 605553974 453089690 606601108 493522186 540480879 113726421 902241062 428917823 510626248 970180695 550549893 442314490 366046498 593770759 901424883 700383203 123398517 59752546 749736234 679144249 681336741 197566737 809089310 107347192 266637335 301836428 949393366 751405299 592114139 189166660 787401716 20491955 458515138 570784474 106337785 383924925 768935479 514552568 28347584 570554005 381145341 600128692 27582970 117675622 629064102 220828394 120769237 976515083 942749959 532304758 235230407 379833176 648615097 285629749 365141557 458772731 84223097 101047066 914804058 341427262 668509663 476477473 649796721 166204126 272439009 234289183 855145122 837604470 316951625 338147030 586895272 777086209 232161742 468153558 655422350 313527222 222495544 900925326 586428951 758276525 554381580