837 43 24231590486 474662870 532000168 626918402 687849325 862302832 419032636 855619740 383135022 484328045 894929718 190907568 713798700 893351903 673264243 66058458 997945478 734567609 47541591 990556075 40266420 635650260 133159217 387387001 418725832 193376348 970236518 238924144 97814024 379195790 325383431 316140243 279595970 949880370 438575544 265602894 71920753 654773884 769153392 803983394 472834205 540130804 888166900 571509274 318319973 849596980 237543226 362474218 335046568 496960422 695589377 508964115 392975929 701798362 337111491 979946727 270765598 966845353 473911543 905431332 22218682 668196075 867582607 632559849 409661916 151000487 852946385 246273216 282964057 43197967 67500606 48703893 995007475 894310265 162052463 702710558 550084236 384816920 67191920 85210194 828136228 431766050 748773811 945423977 355756592 756137325 395238341 331228725 249601545 600622049 401126433 692527271 752081016 732076240 438734018 438567897 24692965 349644578 598415946 511755635 445117614 235219040 252001445 97757870 171674525 871960060 453319640 947658064 476130760 894909777 776289885 487861143 204934055 930129306 448767302 747142141 480655601 445456338 86755875 358488127 828009193 412902591 208082940 353930972 213186800 419350100 996165815 983372914 324647161 712009932 254897431 306296389 784655538 797381053 63819149 168289322 107229445 186303893 878981449 910336699 108655961 169674204 824572141 854231963 302335810 928628212 553646346 252236486 677260575 658752299 624621614 147923598 64631092 305289274 435024178 712123550 759889379 495063699 645897802 986139381 920696221 798108932 757967261 860255303 398654289 673169059 319710435 636375073 141871866 41809148 158553261 561077623 163250546 354904683 753894468 237541338 211767919 695258033 34601579 351581355 697428227 534429599 33163042 980710066 272429595 810544173 106988490 338775251 301001398 334535605 36323024 340682129 838106655 396939394 76672800 780599813 746238712 594553305 194830496 625771835 249312062 486019013 426354232 917782599 998546814 102143811 148621942 49195890 437683314 851633665 382105183 202820498 659477225 667859789 747189645 309962026 906505178 800574492 22177075 956870240 227770778 293945122 864167962 145790233 25153994 978766733 829771219 510542243 475138422 536840982 893710366 500773535 517697388 863129814 918604067 758824981 113497615 784065227 189386957 522187443 839369969 259266149 432035752 824170987 7709713 955369338 186153264 948602569 94815538 205828137 844524412 466992929 580749248 88475375 710509245 619838858 295999183 358078093 939011146 202533664 55447195 473293409 111842571 88021471 544663150 76565768 135982958 778855794 54224343 738424741 434943292 11134919 320679191 292398126 150134811 247989637 213408829 863926663 974791405 808844132 439461354 977395417 752591997 533307851 968413088 574214177 193856904 786240093 549899118 342703226 868917964 380526478 957498850 535457400 247288903 5976137 75814702 346607974 246183314 152440213 488602994 979133340 502312354 736871309 978440993 296946713 652408106 736057084 706246563 319637797 84932812 213058050 414266058 465543109 390271752 811766629 862957579 485411470 187618448 187215471 361687230 247117649 935654283 772572909 555591240 804852375 359162110 525205294 593582746 193069695 271849690 41420963 384335314 590881935 133549515 653082914 184020269 838065675 616644474 709072480 621783943 895903600 787978150 61816114 941928781 524665616 455970946 515449636 940573353 882797536 168064143 25112284 274472989 827662146 745540209 753620796 669332335 446491823 400507725 200098045 100664216 49869793 69392797 663185771 354304915 121028336 143337855 57930180 844468784 498976261 353101647 188001960 906689107 107301381 960570849 149376206 184661333 653022648 952271077 590831052 723799683 305552306 659081208 539845405 927642775 409680160 799623517 927387617 28938579 805113651 407114208 607853847 62674059 187481495 247803312 851028092 775899380 909650886 317033319 83934894 475984154 730887102 128158408 508290494 949513106 491531476 669354173 563582308 916162687 667887533 689963921 171118152 11476384 43998024 731692573 188332637 951255664 907519995 365976941 111478134 195195900 680674447 178448763 410100339 575480918 962524845 5506375 442054201 909663658 704359429 430568811 856134179 133944313 822728566 50924482 258295376 231855142 831707402 967788327 144084216 541125634 87083555 471630169 501663062 100447821 438561719 688109163 510481409 150601264 750770293 824164621 636166915 86214886 325284955 784748793 545993704 589028800 939514125 74470737 153095317 345709315 810806673 843873269 444816548 407231840 703174868 853119773 833545761 457266166 27116819 160043249 977747374 601193407 432858558 828910162 896583008 30977584 41629051 108806021 85040951 602741342 289304180 24529374 470654538 605495427 684005931 71243576 302579112 736190522 662353563 939716227 317819308 58302075 542153130 512472335 998034135 359438886 222321775 773211856 748598446 640098771 675713503 488896736 619260293 62774006 564775408 651912189 460822723 456678094 529266762 32606660 970034836 280474583 578122899 125203156 232922031 856784921 571737848 155554896 809913085 109174985 545220593 860403394 408623070 322091051 111431392 591561404 818712185 227699270 450539599 332012661 963005769 520077939 283290769 389754201 369463930 291906489 240030792 33106376 201255919 625590898 498479556 586962500 427024783 267009626 768744266 881024518 183980376 823074283 901499689 269008350 787212787 624634658 908595025 430493904 785038274 759242358 905415783 142831048 258802215 766296989 460391518 956192307 77649781 411497563 143823804 26295210 692814658 734686302 129704040 815299863 843081260 294550865 91743415 492257786 798334208 151298790 388077854 361927910 161689899 312171761 113095050 712525405 985273620 470937837 66190879 820116808 722432973 843406376 960426870 838892507 664088635 410904287 845035523 896092895 443030070 821575676 948317288 572481848 211123484 426029258 554618967 542242054 646368206 988888135 175242893 358358027 702500685 255061592 315055507 765205404 295713291 56760626 105221678 381890498 740141130 421240237 760028332 515751360 281593575 440192887 684012846 87449009 389165100 468160594 614164719 147445043 140738196 838463484 298458027 680817943 818156361 62120520 342352792 17955028 772814395 581756841 519567698 315407052 22496284 5660870 651891477 682180415 66541788 687870226 149781111 253478641 520986399 687692495 518310375 60913650 675971019 451395695 974354168 175741477 275233707 670448724 974848304 446140343 846628178 885658455 894504294 611138977 126640846 409030446 862232438 881003605 266905030 771673553 778608731 523111987 643650842 962030449 264965979 365620359 173298600 217698889 551907400 135011030 453815587 353732370 71554636 966182158 160821446 594483548 367005958 502100980 376323867 152791554 519691247 806750295 740013823 778883303 64333366 912967381 412435604 698553682 706321679 694366168 134474889 230186188 752063533 286111894 906889865 214829274 981502534 414796436 525518290 176460132 694296411 809222138 890726529 802647160 104281537 204503939 188767653 221650319 944629406 38820117 200562685 195486243 173981592 341255087 886736920 595824821 545164737 719180364 206211311 539971667 709168874 983748955 496550217 839755 947328824 934162586 465849965 335924202 868947011 103675454 973348706 925932199 255742108 911756018 75488264 212434420 867997383 653653608 705130328 407105852 101911462 203972446 851472539 388831551 673726731 691521635 286427011 934699620 243961499 154561117 586266298 956813447 705479511 127938242 488290423 510298621 889537803 104739745 648405493 460317528 509662322 972849790 431447272 971946799 688102294 957989864 267255263 27736872 261842076 487712742 156768287 970708596 879796649 164219262 650425669 56103875 75822465 522782164 660243890 899932699 536489189 307200677 885889207 965170292 206138641 945508353 773131739 154456449 891289472 591712387 584442806 560784389 897949312 854133870 388136822 841997602 414225095 21345928 227303840 751002936 168542976 172934681 607794497 186629914 801276307 251431515 506682733 663527877 258413800 52539827 69934948 797563710 177726565 313369474 115881233 978118698 676891991 471167011 506271161 255294974 281729976 332379481 505345597 822837279 193058995 297669270 848336684 533273893 125812689 144136705 992537708 874269583 184690802 912957839 327211271 901780917 925343182 359154942 434814389 913924282 655461386 127758405 472620358 749110250 892709656 836312851 116445424 965198786 974459113 561074901 677965832 542140961 570002269 123160839 420883043 487312589 612045721 567972305 664318776 874656623 915889040 153603023 683523529 721299880 505940069 547167125 921310165 795583146 88965552 690307332 870710925 674314460 206525258 42719161 710710441 545454792 498162284 436084110 665176339 318296024 39110378 455443753 564346330 528450610 191284538 840605752 240152810 714141109 906338212 242568885 179740304 363298902 422940862 77110092 111905878 552052026 211271203 919406343 143756736 981704477 837132113 894840238 873685936 294333659 944539628 757127628 312249280 879580562 917193608 497929794 778361849 567992286 736156925 768105154 693484994 242924933 233439381 247136538 299979581 489535147 882370933 634321955 22648591 515620090 223134876 96823456 819493455 564928417 718319726 210457047 912967800 885268572 869695213 428779949 557762768 276504650 703922442 373954364 867900517 274364883 160340085 998904951 468475011 537100632 243582172 5148226 541270468 984488712 119867315 650810323 573626888 629978731 577008774 941733018 848581935 952430716 98919988 20589206 629090918 906817814 430417924 662192819 811010178 536597039 229898106 360591807 61096644 927122117 616374362 914580832 694029615 829038128 423288821 279589423 485880676 845996624 497779403 641306792 845019977 271542888 593320174 510123871 529849241 520727809 458926632 844148265 996551055 756629918 826830951 189978230 52515974 98878070 95761496 119978981 157400889 727611930 108588459 555936378 438116560 838624493 82122469 506342740 249914350 911203672 903922185 128319869 852638464 351248575 751653069 520154537 300775808 718760823 650379325 593154569 421631818 524753695 674234603 712215235 212801324 84578562 105557590 895178123 108809064 286526158 294664532 812679090 862222302 20134930 639722593 716730751 999972499 269078165 316834833 645102553 164654801 14419224 86715061 403937382 869189179 81933610 988971633 331901695 835307047 650504737 135048332 127688732 482070576 787278119 690811537 729289946 991684100 960709185 887532713 275702945 781393420 74800640 951124276 761072884 68209219 257988577 236873589 69329903 808946217 510257440 486935378 727024403 361222930 927534343 292132069 359731792 811772571 762993627 145430520 717155967 966740006 312577476 938748065 562641663 291375592 881531299 590870118 144024357 492551987 203623563 988945173 498209318 992612744 766294991 505343327 703045964 786055713 244178754 838464610 924641660 857531882 507070606 824058692 202457520 876878714 876331248 117092540 296765712 8002980 163960177 355973346 786218872 690747856 53431101 217535087 989935350 827826104 623032551 881023415 90844664 728887445 846256037 833564773 692319888 310031456 877231531 736401973 391645721 538959173 941266886 994420327 948142494 36327084 143636863 827710917 260226322 166554828 804903680 443269808 296759593 531454151 421513317 132814905 632214808 178249122 377680711 54335964 867709512 702544779 176289189 176018863 366142740 950135447 745622964 24423352 397798575 209511877 43578847 605022741 693330764 420678042 116340445 650459505 698379416 408575836 25007512 984116696 312093568 927795737 146735828 679665011 110950014 365188872 672426487 350051790 20450161 426197058 300309310 839911290 770166392 209590000 327104887 37276153 364309174 712538953 264519431 917623056 492953800 77326637 582172523 455721729 316940469 342169296 41669354 624486824 412856630 504538625 476388016 896708581 680974750 271755321 600708512 924730761 298736999 60309732 760021976 542586838 907031504 492550829 776801410 956568929 98265546 592531220 144235168 757859425 349992355 288553611 927687300 310934560 409313928 89917504 968222116 178637419 576443468 229726707 479370587 197511444 513387042 206837295 331351028 261933167 822796774 533950736 848371099 204330323 80854720 663211629 230210502 109786835 532608783 710667590 26512045 617242723 101051913 813199274 67172926 132176025 691263597 904426300 656445045 7200517 614088014 458827377 611951020 238346853 394548418 56604248 846368305 424493521 350474589 338194433 803282177 233079492 194083338 556335342 478882289 662014469 183032094 207262537 599144075 244383851 414740817 299005756 420286918 970352054 905610053 739234064 569072375 929404493 857880970 753500743 697685755 991382084 219913719 943888587 819670305 94754979 571825617 858629194 946357522 576355050 374703377 801669170 82776018 187716965 441899491 986807608 465150256 664594513 23983714 302532357 760584857 761979594 110967528 82623321 130052574 4503144 841916262 873866989 965158777 163666380 782518225 541874953 16014842 282198789 229435882 300992515 544155600 673375198 786827238 128064260 903934406 640115233 849467135 140661940 95976620 235013320 480899489 56285832 848960904 141864385 689599438 855814503 699169053 247709093 958092809 441219914 638229760 479399666 783775249 348724273 627193812 471303434 64707343 470381747 89047657 666922858 996274199 866427796 823711263 110754184 528877703 179711947 533696756 233277419 952240037 920377220 77086571 37318011 814984616 396586435 662848056 744040738 678906690 172952606 794289394 699816679 559796452 162668368 372467113 775010849 234246222 463371882 589927778 448695644 908643513 943979869 430835504 665117478 745980070 85262141 587804023 909762526 934301820 131633025 622680047 260473658 937685541 217121109 947541903 966058559 586673485 430637662 997006082 243257598 209012989 976310919 569185165 749475438 437621635 626435233 55573705 330193655 461961900 536004976 222744420 85324435 435709783 251217462 483274728 229740594 159877106 330461818 6668622 19045648 815514885 284422044 590998729 163845029 839355247 710278998 700645161 672842724 202407389 278159954 276357968 703372602 157930298 695803226 62001600 262981457 571706774 244380154 81104921 400179279 200199097 61991768 110031343 538015594 838437468 648544874 413370021 130715843 240326509 237470513 681468827 905915438 51195119 611627330 897019157 556696814 369643919 85400154 279678803 298862034 787769039 459099727 491163180 415625778 547066096 838999157 373943429 537070256 959515183 830945617 755799270 893065844 237199985 344197568 573512527 19085694 732835701 488477354 596867463 451805469 355296394 687088079 197010060 62528119 100044879 951203219 471034200 47932609 268079601 194507681 112119799 122277698 762698594 390329158 976110544 383981299 665033623 482988786 470174351 767490733 39571462 628976865 814294618 911789275 12027267 995167462 347961549 692990067 333052146 436450536 66926388 139503248 388356612 598788979 207750012 987637701 503694541 8645901 872881736 29170816 286813630 952394472 198451161 926462105 451685434 732535057 494818384 406061512 892283116 539420328 872413462 449600572 3646148 773910433 384760006 953120238 73225825 918972455 962507592 447021244 231179894 283364731 320348912 476721827 558958644 579081938 981760984 836939914 602930484 344525051 354402766 75111026 355547517 594181336 442608330 230202457 4304667 416400538 213010180 173727762 495451411 286040516 662000661 475974794 935016594 928452758 592721082 50779946 983159240 477184907 470330379 107665675 508128346 14340409 960804905 220596125 603220725 520610567 700846841 574878783 215125399 753140176 440366130 465565310 547024564 787633666 652746649 288959621 803556270 521654884 931892332 715835921 151844203 485938465 123209170 520013459 603482438 559500600 180710807 682753125 364423755 933576322 1598526 921748931 956276008 111854355 372900689 408591115 320793604 991619370 411031264 795845199 232040925 969925676 214701633 668143369 503004982 296686645 674460961 65589517 288381676 158936524 728614052 9272265 944726161 41159811 521419983 12552543 45531526 225548644 952334832 217640026 220921866 177011028 784581587 161315952 712221869 633865296 683668553 293203168 591199988 885334644 600624024 997700272 88021687 347783190 12591756 469561804 166074476 553437376 596530199 930795464 312637345 976281635 54720181 468709247 160175221 583403874 305514534 140616602 531117225 5703770 67199703 431298140 550730004 538829087 216678483 767362371 168193636 303709300 657514914 226238878 725604734 794847328 38229183 529835359 253158768